about summary refs log tree commit diff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-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
7 files changed, 200 insertions, 213 deletions
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-pink 1.4.1 (git 2.36.1) at 2024-11-19 00:05:20 +0000