summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--COPYRIGHT6
-rw-r--r--src/search/tdelete.c49
-rw-r--r--src/search/tdestroy.c13
-rw-r--r--src/search/tfind.c20
-rw-r--r--src/search/tsearch.c92
-rw-r--r--src/search/tsearch.h13
-rw-r--r--src/search/tsearch_avl.c204
-rw-r--r--src/search/twalk.c22
8 files changed, 200 insertions, 219 deletions
diff --git a/COPYRIGHT b/COPYRIGHT
index 8c3a6d19..b8a76045 100644
--- a/COPYRIGHT
+++ b/COPYRIGHT
@@ -126,12 +126,6 @@ in jurisdictions that may not recognize the public domain.
The smoothsort implementation (src/stdlib/qsort.c) is Copyright © 2011
Valentin Ochs and is licensed under an MIT-style license.
-The BSD PRNG implementation (src/prng/random.c) and XSI search API
-(src/search/*.c) functions are Copyright © 2011 Szabolcs Nagy and
-licensed under following terms: "Permission to use, copy, modify,
-and/or distribute this code for any purpose with or without fee is
-hereby granted. There is no warranty."
-
The x86_64 port was written by Nicholas J. Kain and is licensed under
the standard MIT terms.
diff --git a/src/search/tdelete.c b/src/search/tdelete.c
new file mode 100644
index 00000000..b8bb924b
--- /dev/null
+++ b/src/search/tdelete.c
@@ -0,0 +1,49 @@
+#include <stdlib.h>
+#include <search.h>
+#include "tsearch.h"
+
+void *tdelete(const void *restrict key, void **restrict rootp,
+ int(*cmp)(const void *, const void *))
+{
+ if (!rootp)
+ return 0;
+
+ void **a[MAXH+1];
+ struct node *n = *rootp;
+ struct node *parent;
+ struct node *child;
+ int i=0;
+ /* *a[0] is an arbitrary non-null pointer that is returned when
+ the root node is deleted. */
+ a[i++] = rootp;
+ a[i++] = rootp;
+ for (;;) {
+ if (!n)
+ return 0;
+ int c = cmp(key, n->key);
+ if (!c)
+ break;
+ a[i++] = &n->a[c>0];
+ n = n->a[c>0];
+ }
+ parent = *a[i-2];
+ if (n->a[0]) {
+ /* free the preceding node instead of the deleted one. */
+ struct node *deleted = n;
+ a[i++] = &n->a[0];
+ n = n->a[0];
+ while (n->a[1]) {
+ a[i++] = &n->a[1];
+ n = n->a[1];
+ }
+ deleted->key = n->key;
+ child = n->a[0];
+ } else {
+ child = n->a[1];
+ }
+ /* freed node has at most one child, move it up and rebalance. */
+ free(n);
+ *a[--i] = child;
+ while (--i && __tsearch_balance(a[i]));
+ return parent;
+}
diff --git a/src/search/tdestroy.c b/src/search/tdestroy.c
index 5f9e197d..699a901c 100644
--- a/src/search/tdestroy.c
+++ b/src/search/tdestroy.c
@@ -1,12 +1,7 @@
#define _GNU_SOURCE
#include <stdlib.h>
#include <search.h>
-
-struct node {
- void *key;
- struct node *left;
- struct node *right;
-};
+#include "tsearch.h"
void tdestroy(void *root, void (*freekey)(void *))
{
@@ -14,8 +9,8 @@ void tdestroy(void *root, void (*freekey)(void *))
if (r == 0)
return;
- tdestroy(r->left, freekey);
- tdestroy(r->right, freekey);
- if (freekey) freekey(r->key);
+ tdestroy(r->a[0], freekey);
+ tdestroy(r->a[1], freekey);
+ if (freekey) freekey((void *)r->key);
free(r);
}
diff --git a/src/search/tfind.c b/src/search/tfind.c
new file mode 100644
index 00000000..9e1cf98f
--- /dev/null
+++ b/src/search/tfind.c
@@ -0,0 +1,20 @@
+#include <search.h>
+#include "tsearch.h"
+
+void *tfind(const void *key, void *const *rootp,
+ int(*cmp)(const void *, const void *))
+{
+ if (!rootp)
+ return 0;
+
+ struct node *n = *rootp;
+ for (;;) {
+ if (!n)
+ break;
+ int c = cmp(key, n->key);
+ if (!c)
+ break;
+ n = n->a[c>0];
+ }
+ return n;
+}
diff --git a/src/search/tsearch.c b/src/search/tsearch.c
new file mode 100644
index 00000000..0de27d05
--- /dev/null
+++ b/src/search/tsearch.c
@@ -0,0 +1,92 @@
+#include <stdlib.h>
+#include <search.h>
+#include "tsearch.h"
+
+static inline int height(struct node *n) { return n ? n->h : 0; }
+
+static int rot(void **p, struct node *x, int dir /* deeper side */)
+{
+ struct node *y = x->a[dir];
+ struct node *z = y->a[!dir];
+ int hx = x->h;
+ int hz = height(z);
+ if (hz > height(y->a[dir])) {
+ /*
+ * x
+ * / \ dir z
+ * A y / \
+ * / \ --> x y
+ * z D /| |\
+ * / \ A B C D
+ * B C
+ */
+ x->a[dir] = z->a[!dir];
+ y->a[!dir] = z->a[dir];
+ z->a[!dir] = x;
+ z->a[dir] = y;
+ x->h = hz;
+ y->h = hz;
+ z->h = hz+1;
+ } else {
+ /*
+ * x y
+ * / \ / \
+ * A y --> x D
+ * / \ / \
+ * z D A z
+ */
+ x->a[dir] = z;
+ y->a[!dir] = x;
+ x->h = hz+1;
+ y->h = hz+2;
+ z = y;
+ }
+ *p = z;
+ return z->h - hx;
+}
+
+/* balance *p, return 0 if height is unchanged. */
+int __tsearch_balance(void **p)
+{
+ struct node *n = *p;
+ int h0 = height(n->a[0]);
+ int h1 = height(n->a[1]);
+ if (h0 - h1 + 1u < 3u) {
+ int old = n->h;
+ n->h = h0<h1 ? h1+1 : h0+1;
+ return n->h - old;
+ }
+ return rot(p, n, h0<h1);
+}
+
+void *tsearch(const void *key, void **rootp,
+ int (*cmp)(const void *, const void *))
+{
+ if (!rootp)
+ return 0;
+
+ void **a[MAXH];
+ struct node *n = *rootp;
+ struct node *r;
+ int i=0;
+ a[i++] = rootp;
+ for (;;) {
+ if (!n)
+ break;
+ int c = cmp(key, n->key);
+ if (!c)
+ return n;
+ a[i++] = &n->a[c>0];
+ n = n->a[c>0];
+ }
+ r = malloc(sizeof *r);
+ if (!r)
+ return 0;
+ r->key = key;
+ r->a[0] = r->a[1] = 0;
+ r->h = 1;
+ /* insert new node, rebalance ancestors. */
+ *a[--i] = r;
+ while (i && __tsearch_balance(a[--i]));
+ return r;
+}
diff --git a/src/search/tsearch.h b/src/search/tsearch.h
new file mode 100644
index 00000000..37d11d73
--- /dev/null
+++ b/src/search/tsearch.h
@@ -0,0 +1,13 @@
+#include <search.h>
+#include <features.h>
+
+/* AVL tree height < 1.44*log2(nodes+2)-0.3, MAXH is a safe upper bound. */
+#define MAXH (sizeof(void*)*8*3/2)
+
+struct node {
+ const void *key;
+ void *a[2];
+ int h;
+};
+
+hidden int __tsearch_balance(void **);
diff --git a/src/search/tsearch_avl.c b/src/search/tsearch_avl.c
deleted file mode 100644
index 57194c84..00000000
--- a/src/search/tsearch_avl.c
+++ /dev/null
@@ -1,204 +0,0 @@
-#include <stdlib.h>
-#include <search.h>
-
-/*
-avl tree implementation using recursive functions
-the height of an n node tree is less than 1.44*log2(n+2)-1
-(so the max recursion depth in case of a tree with 2^32 nodes is 45)
-*/
-
-struct node {
- const void *key;
- struct node *left;
- struct node *right;
- int height;
-};
-
-static int delta(struct node *n) {
- return (n->left ? n->left->height:0) - (n->right ? n->right->height:0);
-}
-
-static void updateheight(struct node *n) {
- n->height = 0;
- if (n->left && n->left->height > n->height)
- n->height = n->left->height;
- if (n->right && n->right->height > n->height)
- n->height = n->right->height;
- n->height++;
-}
-
-static struct node *rotl(struct node *n) {
- struct node *r = n->right;
- n->right = r->left;
- r->left = n;
- updateheight(n);
- updateheight(r);
- return r;
-}
-
-static struct node *rotr(struct node *n) {
- struct node *l = n->left;
- n->left = l->right;
- l->right = n;
- updateheight(n);
- updateheight(l);
- return l;
-}
-
-static struct node *balance(struct node *n) {
- int d = delta(n);
-
- if (d < -1) {
- if (delta(n->right) > 0)
- n->right = rotr(n->right);
- return rotl(n);
- } else if (d > 1) {
- if (delta(n->left) < 0)
- n->left = rotl(n->left);
- return rotr(n);
- }
- updateheight(n);
- return n;
-}
-
-static struct node *find(struct node *n, const void *k,
- int (*cmp)(const void *, const void *))
-{
- int c;
-
- if (!n)
- return 0;
- c = cmp(k, n->key);
- if (c == 0)
- return n;
- if (c < 0)
- return find(n->left, k, cmp);
- else
- return find(n->right, k, cmp);
-}
-
-static struct node *insert(struct node *n, const void *k,
- int (*cmp)(const void *, const void *), struct node **found)
-{
- struct node *r;
- int c;
-
- if (!n) {
- n = malloc(sizeof *n);
- if (n) {
- n->key = k;
- n->left = n->right = 0;
- n->height = 1;
- }
- *found = n;
- return n;
- }
- c = cmp(k, n->key);
- if (c == 0) {
- *found = n;
- return 0;
- }
- r = insert(c < 0 ? n->left : n->right, k, cmp, found);
- if (r) {
- if (c < 0)
- n->left = r;
- else
- n->right = r;
- r = balance(n);
- }
- return r;
-}
-
-static struct node *remove_rightmost(struct node *n, struct node **rightmost)
-{
- if (!n->right) {
- *rightmost = n;
- return n->left;
- }
- n->right = remove_rightmost(n->right, rightmost);
- return balance(n);
-}
-
-static struct node *remove(struct node **n, const void *k,
- int (*cmp)(const void *, const void *), struct node *parent)
-{
- int c;
-
- if (!*n)
- return 0;
- c = cmp(k, (*n)->key);
- if (c == 0) {
- struct node *r = *n;
- if (r->left) {
- r->left = remove_rightmost(r->left, n);
- (*n)->left = r->left;
- (*n)->right = r->right;
- *n = balance(*n);
- } else
- *n = r->right;
- free(r);
- return parent;
- }
- if (c < 0)
- parent = remove(&(*n)->left, k, cmp, *n);
- else
- parent = remove(&(*n)->right, k, cmp, *n);
- if (parent)
- *n = balance(*n);
- return parent;
-}
-
-void *tdelete(const void *restrict key, void **restrict rootp,
- int(*compar)(const void *, const void *))
-{
- if (!rootp)
- return 0;
- struct node *n = *rootp;
- struct node *ret;
- /* last argument is arbitrary non-null pointer
- which is returned when the root node is deleted */
- ret = remove(&n, key, compar, n);
- *rootp = n;
- return ret;
-}
-
-void *tfind(const void *key, void *const *rootp,
- int(*compar)(const void *, const void *))
-{
- if (!rootp)
- return 0;
- return find(*rootp, key, compar);
-}
-
-void *tsearch(const void *key, void **rootp,
- int (*compar)(const void *, const void *))
-{
- struct node *update;
- struct node *ret;
- if (!rootp)
- return 0;
- update = insert(*rootp, key, compar, &ret);
- if (update)
- *rootp = update;
- return ret;
-}
-
-static void walk(const struct node *r, void (*action)(const void *, VISIT, int), int d)
-{
- if (r == 0)
- return;
- if (r->left == 0 && r->right == 0)
- action(r, leaf, d);
- else {
- action(r, preorder, d);
- walk(r->left, action, d+1);
- action(r, postorder, d);
- walk(r->right, action, d+1);
- action(r, endorder, d);
- }
-}
-
-void twalk(const void *root, void (*action)(const void *, VISIT, int))
-{
- walk(root, action, 0);
-}
diff --git a/src/search/twalk.c b/src/search/twalk.c
new file mode 100644
index 00000000..53821cda
--- /dev/null
+++ b/src/search/twalk.c
@@ -0,0 +1,22 @@
+#include <search.h>
+#include "tsearch.h"
+
+static void walk(const struct node *r, void (*action)(const void *, VISIT, int), int d)
+{
+ if (!r)
+ return;
+ if (r->h == 1)
+ action(r, leaf, d);
+ else {
+ action(r, preorder, d);
+ walk(r->a[0], action, d+1);
+ action(r, postorder, d);
+ walk(r->a[1], action, d+1);
+ action(r, endorder, d);
+ }
+}
+
+void twalk(const void *root, void (*action)(const void *, VISIT, int))
+{
+ walk(root, action, 0);
+}
generated by cgit v1.2.1 (git 2.18.0) at 2024-11-23 14:36:29 +0000