[PATCH] new tsearch implementation

[PATCH] new tsearch implementation

[Szabolcs Nagy]

[-- Attachment #1: Type: text/plain, Size: 233 bytes --]

new code that's a bit faster and smaller.

with simple benchmark of randomly adding/deleting nodes
new code is about 1.5s vs old 2s on my laptop (many
tsearch/tdelete operations on a tree size around 1000
nodes and depth around 10).

[-- Attachment #2: 0001-new-tsearch-implementation.patch --]
[-- Type: text/x-diff, Size: 13046 bytes --]

From 57e62eb255d835ba6801f704c4c1aabd28d34804 Mon Sep 17 00:00:00 2001
From: Szabolcs Nagy <nsz@port70.net>
Date: Sun, 21 Aug 2016 20:06:56 +0000
Subject: [PATCH] new tsearch implementation

Rewrote the AVL tree implementation:

- It is now non-recursive with fixed stack usage (large enough for
worst case tree height). twalk and tdestroy are still recursive as
that's smaller/simpler.

- Moved unrelated interfaces into separate translation units.

- The node structure is changed to use indexed children instead of
left/right pointers, this simplifies the balancing logic.

- Using void * pointers instead of struct node * in various places,
because this better fits the api (node address is passed in a void**
argument, so it is tempting to incorrectly cast it to struct node **).

- As a further performance improvement the rebalancing now stops
when it is not needed (subtree height is unchanged). Otherwise
the behaviour should be the same as before (checked over generated
random inputs that the resulting tree shape is equivalent).

- Removed the old copyright notice (including prng related one: it
should be licensed under the same terms as the rest of the project).

.text size of pic tsearch + tfind + tdelete + twalk:

   x86_64 i386 aarch64  arm mips powerpc ppc64le  sh4 m68k s390x
old   941  899    1220 1068 1852    1400    1600 1008 1008  1488
new   857  881    1040  976 1564    1192    1360  736  820  1408
---
 COPYRIGHT                |   6 --
 src/search/tdelete.c     |  49 ++++++++++
 src/search/tdestroy.c    |  13 +--
 src/search/tfind.c       |  20 ++++
 src/search/tsearch.c     |  88 +++++++++++++++++
 src/search/tsearch.h     |  13 +++
 src/search/tsearch_avl.c | 204 ---------------------------------------
 src/search/twalk.c       |  22 +++++
 8 files changed, 196 insertions(+), 219 deletions(-)
 create mode 100644 src/search/tdelete.c
 create mode 100644 src/search/tfind.c
 create mode 100644 src/search/tsearch.c
 create mode 100644 src/search/tsearch.h
 delete mode 100644 src/search/tsearch_avl.c
 create mode 100644 src/search/twalk.c

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..54f9f699
--- /dev/null
+++ b/src/search/tsearch.c
@@ -0,0 +1,88 @@
+#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);
+}
-- 
2.18.0

Re: [PATCH] new tsearch implementation

[Rich Felker]

On Wed, Sep 19, 2018 at 02:02:47AM +0200, Szabolcs Nagy wrote:
> new code that's a bit faster and smaller.
> 
> with simple benchmark of randomly adding/deleting nodes
> new code is about 1.5s vs old 2s on my laptop (many
> tsearch/tdelete operations on a tree size around 1000
> nodes and depth around 10).

> From 57e62eb255d835ba6801f704c4c1aabd28d34804 Mon Sep 17 00:00:00 2001
> From: Szabolcs Nagy <nsz@port70.net>
> Date: Sun, 21 Aug 2016 20:06:56 +0000
> Subject: [PATCH] new tsearch implementation
> 
> Rewrote the AVL tree implementation:
> 
> - It is now non-recursive with fixed stack usage (large enough for
> worst case tree height). twalk and tdestroy are still recursive as
> that's smaller/simpler.
> 
> - Moved unrelated interfaces into separate translation units.
> 
> - The node structure is changed to use indexed children instead of
> left/right pointers, this simplifies the balancing logic.
> 
> - Using void * pointers instead of struct node * in various places,
> because this better fits the api (node address is passed in a void**
> argument, so it is tempting to incorrectly cast it to struct node **).
> 
> - As a further performance improvement the rebalancing now stops
> when it is not needed (subtree height is unchanged). Otherwise
> the behaviour should be the same as before (checked over generated
> random inputs that the resulting tree shape is equivalent).
> 
> - Removed the old copyright notice (including prng related one: it
> should be licensed under the same terms as the rest of the project).
> 
> .text size of pic tsearch + tfind + tdelete + twalk:
> 
>    x86_64 i386 aarch64  arm mips powerpc ppc64le  sh4 m68k s390x
> old   941  899    1220 1068 1852    1400    1600 1008 1008  1488
> new   857  881    1040  976 1564    1192    1360  736  820  1408

Nice! Given that you seem to have done heavy testing I didn't read the
code with a lot of scrutiny, but it all looks good from a casual
reading.

> ---
>  COPYRIGHT                |   6 --
>  src/search/tdelete.c     |  49 ++++++++++
>  src/search/tdestroy.c    |  13 +--
>  src/search/tfind.c       |  20 ++++
>  src/search/tsearch.c     |  88 +++++++++++++++++
>  src/search/tsearch.h     |  13 +++
>  src/search/tsearch_avl.c | 204 ---------------------------------------
>  src/search/twalk.c       |  22 +++++
>  8 files changed, 196 insertions(+), 219 deletions(-)
>  create mode 100644 src/search/tdelete.c
>  create mode 100644 src/search/tfind.c
>  create mode 100644 src/search/tsearch.c
>  create mode 100644 src/search/tsearch.h
>  delete mode 100644 src/search/tsearch_avl.c
>  create mode 100644 src/search/twalk.c
> 
> 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.

This part fails to apply because your MUA reencoded the attachment to
latin1. Not a big problem (piping thru iconv -f latin1 fixed it) but
it's something you might want to be aware of. Ideally mutt should have
a way to tell it not to reencode attachments, ever, but this generally
works to avoid the problem assuming your data is UTF-8:

set send_charset="us-ascii:utf-8"

> diff --git a/src/search/tsearch.c b/src/search/tsearch.c
> new file mode 100644
> index 00000000..54f9f699
> --- /dev/null
> +++ b/src/search/tsearch.c
> @@ -0,0 +1,88 @@
> +#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

These comments trigger -Wcomment since they have lines ending in \ in
a //-form comment. I think the easiest solution is converting them to
the style of /**/ comment used elsewhere, with *'s lined up in each
line.

Rich

Re: [PATCH] new tsearch implementation

[Szabolcs Nagy]

* Rich Felker <dalias@libc.org> [2018-09-19 21:24:11 -0400]:
> On Wed, Sep 19, 2018 at 02:02:47AM +0200, Szabolcs Nagy wrote:
> > -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.
> 
> This part fails to apply because your MUA reencoded the attachment to
> latin1. Not a big problem (piping thru iconv -f latin1 fixed it) but
> it's something you might want to be aware of. Ideally mutt should have
> a way to tell it not to reencode attachments, ever, but this generally
> works to avoid the problem assuming your data is UTF-8:
> 
> set send_charset="us-ascii:utf-8"
...
> > +		//  / \             / \
> > +		// A   y    -->    x   D
> > +		//    / \         / \
> > +		//   z   D       A   z
> 
> These comments trigger -Wcomment since they have lines ending in \ in
> a //-form comment. I think the easiest solution is converting them to
> the style of /**/ comment used elsewhere, with *'s lined up in each
> line.
> 

oops, yes, that's a reasonable fix.
i can send an updated patch later if you need it.