aboutsummaryrefslogtreecommitdiff
path: root/src/backend/utils/sort/lselect.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/backend/utils/sort/lselect.c')
-rw-r--r--src/backend/utils/sort/lselect.c355
1 files changed, 0 insertions, 355 deletions
diff --git a/src/backend/utils/sort/lselect.c b/src/backend/utils/sort/lselect.c
deleted file mode 100644
index 7f521b821f4..00000000000
--- a/src/backend/utils/sort/lselect.c
+++ /dev/null
@@ -1,355 +0,0 @@
-/*-------------------------------------------------------------------------
- *
- * lselect.c
- * leftist tree selection algorithm (linked priority queue--Knuth, Vol.3,
- * pp.150-52)
- *
- * Copyright (c) 1994, Regents of the University of California
- *
- *
- * IDENTIFICATION
- * $Header: /cvsroot/pgsql/src/backend/utils/sort/Attic/lselect.c,v 1.19 1999/07/17 20:18:16 momjian Exp $
- *
- *-------------------------------------------------------------------------
- */
-
-#include "postgres.h"
-
-
-#include "access/heapam.h"
-#include "utils/lselect.h"
-
-/*
- * lmerge - merges two leftist trees into one
- *
- * Note:
- * Enforcing the rule that pt->lt_dist >= qt->lt_dist may
- * simplifify much of the code. Removing recursion will not
- * speed up code significantly.
- */
-struct leftist *
-lmerge(struct leftist * pt, struct leftist * qt, LeftistContext context)
-{
- struct leftist *root,
- *majorLeftist,
- *minorLeftist;
- int dist;
-
- if (tuplecmp(pt->lt_tuple, qt->lt_tuple, context))
- {
- root = pt;
- majorLeftist = qt;
- }
- else
- {
- root = qt;
- majorLeftist = pt;
- }
- if (root->lt_left == NULL)
- root->lt_left = majorLeftist;
- else
- {
- if ((minorLeftist = root->lt_right) != NULL)
- majorLeftist = lmerge(majorLeftist, minorLeftist, context);
- if ((dist = root->lt_left->lt_dist) < majorLeftist->lt_dist)
- {
- root->lt_dist = 1 + dist;
- root->lt_right = root->lt_left;
- root->lt_left = majorLeftist;
- }
- else
- {
- root->lt_dist = 1 + majorLeftist->lt_dist;
- root->lt_right = majorLeftist;
- }
- }
- return root;
-}
-
-static struct leftist *
-linsert(struct leftist * root, struct leftist * new1, LeftistContext context)
-{
- struct leftist *left,
- *right;
-
- if (!tuplecmp(root->lt_tuple, new1->lt_tuple, context))
- {
- new1->lt_left = root;
- return new1;
- }
- left = root->lt_left;
- right = root->lt_right;
- if (right == NULL)
- {
- if (left == NULL)
- root->lt_left = new1;
- else
- {
- root->lt_right = new1;
- root->lt_dist = 2;
- }
- return root;
- }
- right = linsert(right, new1, context);
- if (right->lt_dist < left->lt_dist)
- {
- root->lt_dist = 1 + left->lt_dist;
- root->lt_left = right;
- root->lt_right = left;
- }
- else
- {
- root->lt_dist = 1 + right->lt_dist;
- root->lt_right = right;
- }
- return root;
-}
-
-/*
- * gettuple - returns tuple at top of tree (Tuples)
- *
- * Returns:
- * tuple at top of tree, NULL if failed ALLOC()
- * *devnum is set to the devnum of tuple returned
- * *treep is set to the new tree
- *
- * Note:
- * *treep must not be NULL
- * NULL is currently never returned BUG
- */
-HeapTuple
-gettuple(struct leftist ** treep,
- short *devnum, /* device from which tuple came */
- LeftistContext context)
-{
- struct leftist *tp;
- HeapTuple tup;
-
- tp = *treep;
- tup = tp->lt_tuple;
- *devnum = tp->lt_devnum;
- if (tp->lt_dist == 1) /* lt_left == NULL */
- *treep = tp->lt_left;
- else
- *treep = lmerge(tp->lt_left, tp->lt_right, context);
-
- pfree(tp);
- return tup;
-}
-
-/*
- * puttuple - inserts new tuple into tree
- *
- * Returns:
- * NULL iff failed ALLOC()
- *
- * Note:
- * Currently never returns NULL BUG
- */
-void
-puttuple(struct leftist ** treep,
- HeapTuple newtuple,
- short devnum,
- LeftistContext context)
-{
- struct leftist *new1;
- struct leftist *tp;
-
- new1 = (struct leftist *) palloc((unsigned) sizeof(struct leftist));
- new1->lt_dist = 1;
- new1->lt_devnum = devnum;
- new1->lt_tuple = newtuple;
- new1->lt_left = NULL;
- new1->lt_right = NULL;
- if ((tp = *treep) == NULL)
- *treep = new1;
- else
- *treep = linsert(tp, new1, context);
- return;
-}
-
-
-/*
- * tuplecmp - Compares two tuples with respect CmpList
- *
- * Returns:
- * 1 if left < right ;0 otherwise
- * Assumtions:
- */
-int
-tuplecmp(HeapTuple ltup, HeapTuple rtup, LeftistContext context)
-{
- int nkey;
- int result = 0;
-
- if (ltup == (HeapTuple) NULL)
- return 0;
- if (rtup == (HeapTuple) NULL)
- return 1;
- for (nkey = 0; nkey < context->nKeys; nkey++)
- {
- ScanKey thisKey = & context->scanKeys[nkey];
- Datum lattr,
- rattr;
- bool lisnull,
- risnull;
-
- lattr = heap_getattr(ltup, thisKey->sk_attno,
- context->tupDesc, &lisnull);
- rattr = heap_getattr(rtup, thisKey->sk_attno,
- context->tupDesc, &risnull);
- if (lisnull)
- {
- if (risnull)
- continue; /* treat two nulls as equal */
- return 0; /* else, a null sorts after all else */
- }
- if (risnull)
- return 1;
- if (thisKey->sk_flags & SK_COMMUTE)
- {
- if (!(result =
- (long) (*fmgr_faddr(&thisKey->sk_func)) (rattr, lattr)))
- result =
- -(long) (*fmgr_faddr(&thisKey->sk_func)) (lattr, rattr);
- }
- else
- {
- if (!(result =
- (long) (*fmgr_faddr(&thisKey->sk_func)) (lattr, rattr)))
- result =
- -(long) (*fmgr_faddr(&thisKey->sk_func)) (rattr, lattr);
- }
- if (result)
- break;
- }
- return result == 1;
-}
-
-#ifdef EBUG
-void
-checktree(struct leftist * tree, LeftistContext context)
-{
- int lnodes;
- int rnodes;
-
- if (tree == NULL)
- {
- puts("Null tree.");
- return;
- }
- lnodes = checktreer(tree->lt_left, 1, context);
- rnodes = checktreer(tree->lt_right, 1, context);
- if (lnodes < 0)
- {
- lnodes = -lnodes;
- puts("0:\tBad left side.");
- }
- if (rnodes < 0)
- {
- rnodes = -rnodes;
- puts("0:\tBad right side.");
- }
- if (lnodes == 0)
- {
- if (rnodes != 0)
- puts("0:\tLeft and right reversed.");
- if (tree->lt_dist != 1)
- puts("0:\tDistance incorrect.");
- }
- else if (rnodes == 0)
- {
- if (tree->lt_dist != 1)
- puts("0:\tDistance incorrect.");
- }
- else if (tree->lt_left->lt_dist < tree->lt_right->lt_dist)
- {
- puts("0:\tLeft and right reversed.");
- if (tree->lt_dist != 1 + tree->lt_left->lt_dist)
- puts("0:\tDistance incorrect.");
- }
- else if (tree->lt_dist != 1 + tree->lt_right->lt_dist)
- puts("0:\tDistance incorrect.");
- if (lnodes > 0)
- if (tuplecmp(tree->lt_left->lt_tuple, tree->lt_tuple, context))
- printf("%d:\tLeft child < parent.\n");
- if (rnodes > 0)
- if (tuplecmp(tree->lt_right->lt_tuple, tree->lt_tuple, context))
- printf("%d:\tRight child < parent.\n");
- printf("Tree has %d nodes\n", 1 + lnodes + rnodes);
-}
-
-int
-checktreer(struct leftist * tree, int level, LeftistContext context)
-{
- int lnodes,
- rnodes;
- int error = 0;
-
- if (tree == NULL)
- return 0;
- lnodes = checktreer(tree->lt_left, level + 1, context);
- rnodes = checktreer(tree->lt_right, level + 1, context);
- if (lnodes < 0)
- {
- error = 1;
- lnodes = -lnodes;
- printf("%d:\tBad left side.\n", level);
- }
- if (rnodes < 0)
- {
- error = 1;
- rnodes = -rnodes;
- printf("%d:\tBad right side.\n", level);
- }
- if (lnodes == 0)
- {
- if (rnodes != 0)
- {
- error = 1;
- printf("%d:\tLeft and right reversed.\n", level);
- }
- if (tree->lt_dist != 1)
- {
- error = 1;
- printf("%d:\tDistance incorrect.\n", level);
- }
- }
- else if (rnodes == 0)
- {
- if (tree->lt_dist != 1)
- {
- error = 1;
- printf("%d:\tDistance incorrect.\n", level);
- }
- }
- else if (tree->lt_left->lt_dist < tree->lt_right->lt_dist)
- {
- error = 1;
- printf("%d:\tLeft and right reversed.\n", level);
- if (tree->lt_dist != 1 + tree->lt_left->lt_dist)
- printf("%d:\tDistance incorrect.\n", level);
- }
- else if (tree->lt_dist != 1 + tree->lt_right->lt_dist)
- {
- error = 1;
- printf("%d:\tDistance incorrect.\n", level);
- }
- if (lnodes > 0)
- if (tuplecmp(tree->lt_left->lt_tuple, tree->lt_tuple, context))
- {
- error = 1;
- printf("%d:\tLeft child < parent.\n");
- }
- if (rnodes > 0)
- if (tuplecmp(tree->lt_right->lt_tuple, tree->lt_tuple, context))
- {
- error = 1;
- printf("%d:\tRight child < parent.\n");
- }
- if (error)
- return -1 + -lnodes + -rnodes;
- return 1 + lnodes + rnodes;
-}
-
-#endif
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-15 02:10:55 +0000