granicus.if.org Git - postgresql/blob - src/backend/utils/sort/lselect.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * lselect.c--
   4  *        leftist tree selection algorithm (linked priority queue--Knuth, Vol.3,
   5  *        pp.150-52)
   6  *
   7  * Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $Header: /cvsroot/pgsql/src/backend/utils/sort/Attic/lselect.c,v 1.11 1998/01/31 04:39:12 momjian Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 #include <string.h>
  16 #include <stdio.h>
  17
  18 #include "postgres.h"
  19
  20 #include "storage/buf.h"
  21 #include "access/skey.h"
  22 #include "access/heapam.h"
  23 #include "access/htup.h"
  24 #include "utils/rel.h"
  25
  26 #include "utils/psort.h"
  27 #include "utils/lselect.h"
  28
  29 /*
  30  *              lmerge                  - merges two leftist trees into one
  31  *
  32  *              Note:
  33  *                              Enforcing the rule that pt->lt_dist >= qt->lt_dist may
  34  *                              simplifify much of the code.  Removing recursion will not
  35  *                              speed up code significantly.
  36  */
  37 struct leftist *
  38 lmerge(struct leftist * pt, struct leftist * qt, LeftistContext context)
  39 {
  40         register struct leftist *root,
  41                            *majorLeftist,
  42                            *minorLeftist;
  43         int                     dist;
  44
  45         if (tuplecmp(pt->lt_tuple, qt->lt_tuple, context))
  46         {
  47                 root = pt;
  48                 majorLeftist = qt;
  49         }
  50         else
  51         {
  52                 root = qt;
  53                 majorLeftist = pt;
  54         }
  55         if (root->lt_left == NULL)
  56                 root->lt_left = majorLeftist;
  57         else
  58         {
  59                 if ((minorLeftist = root->lt_right) != NULL)
  60                         majorLeftist = lmerge(majorLeftist, minorLeftist, context);
  61                 if ((dist = root->lt_left->lt_dist) < majorLeftist->lt_dist)
  62                 {
  63                         root->lt_dist = 1 + dist;
  64                         root->lt_right = root->lt_left;
  65                         root->lt_left = majorLeftist;
  66                 }
  67                 else
  68                 {
  69                         root->lt_dist = 1 + majorLeftist->lt_dist;
  70                         root->lt_right = majorLeftist;
  71                 }
  72         }
  73         return (root);
  74 }
  75
  76 static struct leftist *
  77 linsert(struct leftist * root, struct leftist * new1, LeftistContext context)
  78 {
  79         register struct leftist *left,
  80                            *right;
  81
  82         if (!tuplecmp(root->lt_tuple, new1->lt_tuple, context))
  83         {
  84                 new1->lt_left = root;
  85                 return (new1);
  86         }
  87         left = root->lt_left;
  88         right = root->lt_right;
  89         if (right == NULL)
  90         {
  91                 if (left == NULL)
  92                         root->lt_left = new1;
  93                 else
  94                 {
  95                         root->lt_right = new1;
  96                         root->lt_dist = 2;
  97                 }
  98                 return (root);
  99         }
 100         right = linsert(right, new1, context);
 101         if (right->lt_dist < left->lt_dist)
 102         {
 103                 root->lt_dist = 1 + left->lt_dist;
 104                 root->lt_left = right;
 105                 root->lt_right = left;
 106         }
 107         else
 108         {
 109                 root->lt_dist = 1 + right->lt_dist;
 110                 root->lt_right = right;
 111         }
 112         return (root);
 113 }
 114
 115 /*
 116  *              gettuple                - returns tuple at top of tree (Tuples)
 117  *
 118  *              Returns:
 119  *                              tuple at top of tree, NULL if failed ALLOC()
 120  *                              *devnum is set to the devnum of tuple returned
 121  *                              *treep is set to the new tree
 122  *
 123  *              Note:
 124  *                              *treep must not be NULL
 125  *                              NULL is currently never returned BUG
 126  */
 127 HeapTuple
 128 gettuple(struct leftist ** treep,
 129                  short *devnum,                 /* device from which tuple came */
 130                  LeftistContext context)
 131 {
 132         register struct leftist *tp;
 133         HeapTuple       tup;
 134
 135         tp = *treep;
 136         tup = tp->lt_tuple;
 137         *devnum = tp->lt_devnum;
 138         if (tp->lt_dist == 1)           /* lt_left == NULL */
 139                 *treep = tp->lt_left;
 140         else
 141                 *treep = lmerge(tp->lt_left, tp->lt_right, context);
 142
 143         pfree (tp);
 144         return (tup);
 145 }
 146
 147 /*
 148  *              puttuple                - inserts new tuple into tree
 149  *
 150  *              Returns:
 151  *                              NULL iff failed ALLOC()
 152  *
 153  *              Note:
 154  *                              Currently never returns NULL BUG
 155  */
 156 void
 157 puttuple(struct leftist ** treep,
 158                  HeapTuple newtuple,
 159                  short devnum,
 160                  LeftistContext context)
 161 {
 162         register struct leftist *new1;
 163         register struct leftist *tp;
 164
 165         new1 = (struct leftist *) palloc((unsigned) sizeof(struct leftist));
 166         new1->lt_dist = 1;
 167         new1->lt_devnum = devnum;
 168         new1->lt_tuple = newtuple;
 169         new1->lt_left = NULL;
 170         new1->lt_right = NULL;
 171         if ((tp = *treep) == NULL)
 172                 *treep = new1;
 173         else
 174                 *treep = linsert(tp, new1, context);
 175         return;
 176 }
 177
 178
 179 /*
 180  *              tuplecmp                - Compares two tuples with respect CmpList
 181  *
 182  *              Returns:
 183  *                              1 if left < right ;0 otherwise
 184  *              Assumtions:
 185  */
 186 int
 187 tuplecmp(HeapTuple ltup, HeapTuple rtup, LeftistContext context)
 188 {
 189         register Datum lattr,
 190                                 rattr;
 191         int                     nkey = 0;
 192         int                     result = 0;
 193         bool            isnull;
 194
 195         if (ltup == (HeapTuple) NULL)
 196                 return (0);
 197         if (rtup == (HeapTuple) NULL)
 198                 return (1);
 199         while (nkey < context->nKeys && !result)
 200         {
 201                 lattr = heap_getattr(ltup,
 202                                                          context->scanKeys[nkey].sk_attno,
 203                                                          context->tupDesc, &isnull);
 204                 if (isnull)
 205                         return (0);
 206                 rattr = heap_getattr(rtup,
 207                                                          context->scanKeys[nkey].sk_attno,
 208                                                          context->tupDesc,
 209                                                          &isnull);
 210                 if (isnull)
 211                         return (1);
 212                 if (context->scanKeys[nkey].sk_flags & SK_COMMUTE)
 213                 {
 214                         if (!(result =
 215                            (long) (*fmgr_faddr(&context->scanKeys[nkey].sk_func)) (rattr, lattr)))
 216                                 result =
 217                                         -(long) (*fmgr_faddr(&context->scanKeys[nkey].sk_func)) (lattr, rattr);
 218                 }
 219                 else if (!(result =
 220                            (long) (*fmgr_faddr(&context->scanKeys[nkey].sk_func)) (lattr, rattr)))
 221                         result =
 222                                 -(long) (*fmgr_faddr(&context->scanKeys[nkey].sk_func)) (rattr, lattr);
 223                 nkey++;
 224         }
 225         return (result == 1);
 226 }
 227
 228 #ifdef  EBUG
 229 void
 230 checktree(struct leftist * tree, LeftistContext context)
 231 {
 232         int                     lnodes;
 233         int                     rnodes;
 234
 235         if (tree == NULL)
 236         {
 237                 puts("Null tree.");
 238                 return;
 239         }
 240         lnodes = checktreer(tree->lt_left, 1, context);
 241         rnodes = checktreer(tree->lt_right, 1, context);
 242         if (lnodes < 0)
 243         {
 244                 lnodes = -lnodes;
 245                 puts("0:\tBad left side.");
 246         }
 247         if (rnodes < 0)
 248         {
 249                 rnodes = -rnodes;
 250                 puts("0:\tBad right side.");
 251         }
 252         if (lnodes == 0)
 253         {
 254                 if (rnodes != 0)
 255                         puts("0:\tLeft and right reversed.");
 256                 if (tree->lt_dist != 1)
 257                         puts("0:\tDistance incorrect.");
 258         }
 259         else if (rnodes == 0)
 260         {
 261                 if (tree->lt_dist != 1)
 262                         puts("0:\tDistance incorrect.");
 263         }
 264         else if (tree->lt_left->lt_dist < tree->lt_right->lt_dist)
 265         {
 266                 puts("0:\tLeft and right reversed.");
 267                 if (tree->lt_dist != 1 + tree->lt_left->lt_dist)
 268                         puts("0:\tDistance incorrect.");
 269         }
 270         else if (tree->lt_dist != 1 + tree->lt_right->lt_dist)
 271                 puts("0:\tDistance incorrect.");
 272         if (lnodes > 0)
 273                 if (tuplecmp(tree->lt_left->lt_tuple, tree->lt_tuple, context))
 274                         printf("%d:\tLeft child < parent.\n");
 275         if (rnodes > 0)
 276                 if (tuplecmp(tree->lt_right->lt_tuple, tree->lt_tuple, context))
 277                         printf("%d:\tRight child < parent.\n");
 278         printf("Tree has %d nodes\n", 1 + lnodes + rnodes);
 279 }
 280
 281 int
 282 checktreer(struct leftist * tree, int level, LeftistContext context)
 283 {
 284         int                     lnodes,
 285                                 rnodes;
 286         int                     error = 0;
 287
 288         if (tree == NULL)
 289                 return (0);
 290         lnodes = checktreer(tree->lt_left, level + 1, context);
 291         rnodes = checktreer(tree->lt_right, level + 1, context);
 292         if (lnodes < 0)
 293         {
 294                 error = 1;
 295                 lnodes = -lnodes;
 296                 printf("%d:\tBad left side.\n", level);
 297         }
 298         if (rnodes < 0)
 299         {
 300                 error = 1;
 301                 rnodes = -rnodes;
 302                 printf("%d:\tBad right side.\n", level);
 303         }
 304         if (lnodes == 0)
 305         {
 306                 if (rnodes != 0)
 307                 {
 308                         error = 1;
 309                         printf("%d:\tLeft and right reversed.\n", level);
 310                 }
 311                 if (tree->lt_dist != 1)
 312                 {
 313                         error = 1;
 314                         printf("%d:\tDistance incorrect.\n", level);
 315                 }
 316         }
 317         else if (rnodes == 0)
 318         {
 319                 if (tree->lt_dist != 1)
 320                 {
 321                         error = 1;
 322                         printf("%d:\tDistance incorrect.\n", level);
 323                 }
 324         }
 325         else if (tree->lt_left->lt_dist < tree->lt_right->lt_dist)
 326         {
 327                 error = 1;
 328                 printf("%d:\tLeft and right reversed.\n", level);
 329                 if (tree->lt_dist != 1 + tree->lt_left->lt_dist)
 330                         printf("%d:\tDistance incorrect.\n", level);
 331         }
 332         else if (tree->lt_dist != 1 + tree->lt_right->lt_dist)
 333         {
 334                 error = 1;
 335                 printf("%d:\tDistance incorrect.\n", level);
 336         }
 337         if (lnodes > 0)
 338                 if (tuplecmp(tree->lt_left->lt_tuple, tree->lt_tuple, context))
 339                 {
 340                         error = 1;
 341                         printf("%d:\tLeft child < parent.\n");
 342                 }
 343         if (rnodes > 0)
 344                 if (tuplecmp(tree->lt_right->lt_tuple, tree->lt_tuple, context))
 345                 {
 346                         error = 1;
 347                         printf("%d:\tRight child < parent.\n");
 348                 }
 349         if (error)
 350                 return (-1 + -lnodes + -rnodes);
 351         return (1 + lnodes + rnodes);
 352 }
 353
 354 #endif