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.c365
1 files changed, 365 insertions, 0 deletions
diff --git a/src/backend/utils/sort/lselect.c b/src/backend/utils/sort/lselect.c
new file mode 100644
index 00000000000..1f92e48d838
--- /dev/null
+++ b/src/backend/utils/sort/lselect.c
@@ -0,0 +1,365 @@
+/*-------------------------------------------------------------------------
+ *
+ * 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.1.1.1 1996/07/09 06:22:10 scrappy Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+#include <string.h>
+#include <stdio.h>
+
+#include "c.h"
+
+#include "storage/buf.h"
+#include "access/skey.h"
+#include "access/heapam.h"
+#include "access/htup.h"
+#include "utils/rel.h"
+
+#include "utils/psort.h"
+#include "utils/lselect.h"
+
+extern Relation SortRdesc; /* later static */
+
+/*
+ * PUTTUP - writes the next tuple
+ * ENDRUN - mark end of run
+ * GETLEN - reads the length of the next tuple
+ * ALLOCTUP - returns space for the new tuple
+ * SETTUPLEN - stores the length into the tuple
+ * GETTUP - reads the tuple
+ *
+ * Note:
+ * LEN field must be a short; FP is a stream
+ */
+
+#define PUTTUP(TUP, FP) fwrite((char *)TUP, (TUP)->t_len, 1, FP)
+#define ENDRUN(FP) fwrite((char *)&shortzero, sizeof (shortzero), 1, FP)
+#define GETLEN(LEN, FP) fread(&(LEN), sizeof (shortzero), 1, FP)
+#define ALLOCTUP(LEN) ((HeapTuple)malloc((unsigned)LEN))
+#define GETTUP(TUP, LEN, FP)\
+ fread((char *)(TUP) + sizeof (shortzero), 1, (LEN) - sizeof (shortzero), FP)
+#define SETTUPLEN(TUP, LEN) (TUP)->t_len = LEN
+
+/*
+ * USEMEM - record use of memory
+ * FREEMEM - record freeing of memory
+ * FULLMEM - 1 iff a tuple will fit
+ */
+
+#define USEMEM(AMT) SortMemory -= (AMT)
+#define FREEMEM(AMT) SortMemory += (AMT)
+#define LACKMEM() (SortMemory <= BLCKSZ) /* not accurate */
+
+/*
+ * 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)
+{
+ register struct leftist *root, *majorLeftist, *minorLeftist;
+ int dist;
+
+ if (tuplecmp(pt->lt_tuple, qt->lt_tuple)) {
+ 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);
+ 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)
+{
+ register struct leftist *left, *right;
+
+ if (! tuplecmp(root->lt_tuple, new1->lt_tuple)) {
+ 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);
+ 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 */
+{
+ register 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);
+
+ FREEMEM(sizeof (struct leftist));
+ FREE(tp);
+ return(tup);
+}
+
+/*
+ * puttuple - inserts new tuple into tree
+ *
+ * Returns:
+ * NULL iff failed ALLOC()
+ *
+ * Note:
+ * Currently never returns NULL BUG
+ */
+int
+puttuple(struct leftist **treep, HeapTuple newtuple, int devnum)
+{
+ register struct leftist *new1;
+ register struct leftist *tp;
+
+ new1 = (struct leftist *) malloc((unsigned) sizeof (struct leftist));
+ USEMEM(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);
+ return(1);
+}
+
+
+/*
+ * dumptuples - stores all the tuples in tree into file
+ */
+void
+dumptuples(FILE *file)
+{
+ register struct leftist *tp;
+ register struct leftist *newp;
+ HeapTuple tup;
+
+ tp = Tuples;
+ while (tp != NULL) {
+ tup = tp->lt_tuple;
+ if (tp->lt_dist == 1) /* lt_right == NULL */
+ newp = tp->lt_left;
+ else
+ newp = lmerge(tp->lt_left, tp->lt_right);
+ FREEMEM(sizeof (struct leftist));
+ FREE(tp);
+ PUTTUP(tup, file);
+ FREEMEM(tup->t_len);
+ FREE(tup);
+ tp = newp;
+ }
+ Tuples = NULL;
+}
+
+/*
+ * tuplecmp - Compares two tuples with respect CmpList
+ *
+ * Returns:
+ * 1 if left < right ;0 otherwise
+ * Assumtions:
+ */
+int
+tuplecmp(HeapTuple ltup, HeapTuple rtup)
+{
+ register char *lattr, *rattr;
+ int nkey = 0;
+ extern int Nkeys;
+ extern ScanKey Key;
+ int result = 0;
+ bool isnull;
+
+ if (ltup == (HeapTuple)NULL)
+ return(0);
+ if (rtup == (HeapTuple)NULL)
+ return(1);
+ while (nkey < Nkeys && !result) {
+ lattr = heap_getattr(ltup, InvalidBuffer,
+ Key[nkey].sk_attno,
+ RelationGetTupleDescriptor(SortRdesc),
+ &isnull);
+ if (isnull)
+ return(0);
+ rattr = heap_getattr(rtup, InvalidBuffer,
+ Key[nkey].sk_attno,
+ RelationGetTupleDescriptor(SortRdesc),
+ &isnull);
+ if (isnull)
+ return(1);
+ if (Key[nkey].sk_flags & SK_COMMUTE) {
+ if (!(result = (long) (*Key[nkey].sk_func) (rattr, lattr)))
+ result = -(long) (*Key[nkey].sk_func) (lattr, rattr);
+ } else if (!(result = (long) (*Key[nkey].sk_func) (lattr, rattr)))
+ result = -(long) (*Key[nkey].sk_func) (rattr, lattr);
+ nkey++;
+ }
+ return (result == 1);
+}
+
+#ifdef EBUG
+void
+checktree(struct leftist *tree)
+{
+ int lnodes;
+ int rnodes;
+
+ if (tree == NULL) {
+ puts("Null tree.");
+ return;
+ }
+ lnodes = checktreer(tree->lt_left, 1);
+ rnodes = checktreer(tree->lt_right, 1);
+ 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))
+ printf("%d:\tLeft child < parent.\n");
+ if (rnodes > 0)
+ if (tuplecmp(tree->lt_right->lt_tuple, tree->lt_tuple))
+ printf("%d:\tRight child < parent.\n");
+ printf("Tree has %d nodes\n", 1 + lnodes + rnodes);
+}
+
+int
+checktreer(struct leftist *tree, int level)
+{
+ int lnodes, rnodes;
+ int error = 0;
+
+ if (tree == NULL)
+ return(0);
+ lnodes = checktreer(tree->lt_left, level + 1);
+ rnodes = checktreer(tree->lt_right, level + 1);
+ 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)) {
+ error = 1;
+ printf("%d:\tLeft child < parent.\n");
+ }
+ if (rnodes > 0)
+ if (tuplecmp(tree->lt_right->lt_tuple, tree->lt_tuple)) {
+ 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-05-19 03:40:38 +0000