XSI search.h API implementation by Szabolcs Nagy

6 files changed, 392 insertions, 4 deletions

diff --git a/COPYRIGHT b/COPYRIGHT
index 9ff66471..73887f22 100644
--- a/COPYRIGHT
+++ b/COPYRIGHT
@@ -23,9 +23,11 @@ The smoothsort implementation (src/stdlib/qsort.c) is Copyright © 2011
 Valentin Ochs and is licensed under an MIT-style license compatible
 with the GNU LGPL.
 
-The BSD PRNG implementation (src/prng/random.c) is Copyright © 2011
-Szabolcs Nagy and is licensed under very permissive terms (see the
-source).
+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. See individual files
 for their copyright status.
diff --git a/include/search.h b/include/search.h
index 9254ed0c..f1246ade 100644
--- a/include/search.h
+++ b/include/search.h
@@ -1,6 +1,40 @@
 #ifndef _SEARCH_H
 #define _SEARCH_H
 
-// FIXME!!!
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#define __NEED_size_t
+#include <bits/alltypes.h>
+
+typedef enum { FIND, ENTER } ACTION;
+typedef enum { preorder, postorder, endorder, leaf } VISIT;
+
+typedef struct {
+	char *key;
+	void *data;
+} ENTRY;
+
+int hcreate(size_t);
+void hdestroy(void);
+ENTRY *hsearch(ENTRY, ACTION);
+
+void insque(void *, void *);
+void remque(void *);
+
+void *lsearch(const void *, void *, size_t *, size_t,
+	int (*)(const void *, const void *));
+void *lfind(const void *, const void *, size_t *, size_t,
+	int (*)(const void *, const void *));
+
+void *tdelete(const void *, void **, int(*)(const void *, const void *));
+void *tfind(const void *, void *const *, int(*)(const void *, const void *));
+void *tsearch(const void *, void **, int (*)(const void *, const void *));
+void twalk(const void *, void (*)(const void *, VISIT, int));
+
+#ifdef __cplusplus
+}
+#endif
 
 #endif
diff --git a/src/search/hsearch.c b/src/search/hsearch.c
new file mode 100644
index 00000000..be856b2a
--- /dev/null
+++ b/src/search/hsearch.c
@@ -0,0 +1,118 @@
+#include <stdlib.h>
+#include <string.h>
+#include <search.h>
+
+/*
+open addressing hash table with 2^n table size
+quadratic probing is used in case of hash collision
+tab indices and hash are size_t
+after resize fails with ENOMEM the state of tab is still usable
+
+with the posix api items cannot be iterated and length cannot be queried
+*/
+
+#define MINSIZE 8
+#define MAXSIZE ((size_t)-1/2 + 1)
+
+struct entry {
+	ENTRY item;
+	size_t hash;
+};
+
+static size_t mask;
+static size_t used;
+static struct entry *tab;
+
+static size_t keyhash(char *k)
+{
+	unsigned char *p = (void *)k;
+	size_t h = 0;
+
+	while (*p)
+		h = 31*h + *p++;
+	return h;
+}
+
+static int resize(size_t nel)
+{
+	size_t newsize;
+	size_t i, j;
+	struct entry *e, *newe;
+	struct entry *oldtab = tab;
+	struct entry *oldend = tab + mask + 1;
+
+	if (nel > MAXSIZE)
+		nel = MAXSIZE;
+	for (newsize = MINSIZE; newsize < nel; newsize *= 2);
+	tab = calloc(newsize, sizeof *tab);
+	if (!tab) {
+		tab = oldtab;
+		return 0;
+	}
+	mask = newsize - 1;
+	if (!oldtab)
+		return 1;
+	for (e = oldtab; e < oldend; e++)
+		if (e->item.key) {
+			for (i=e->hash,j=1; ; i+=j++) {
+				newe = tab + (i & mask);
+				if (!newe->item.key)
+					break;
+			}
+			*newe = *e;
+		}
+	free(oldtab);
+	return 1;
+}
+
+int hcreate(size_t nel)
+{
+	mask = 0;
+	used = 0;
+	tab = 0;
+	return resize(nel);
+}
+
+void hdestroy(void)
+{
+	free(tab);
+	tab = 0;
+	mask = 0;
+	used = 0;
+}
+
+static struct entry *lookup(char *key, size_t hash)
+{
+	size_t i, j;
+	struct entry *e;
+
+	for (i=hash,j=1; ; i+=j++) {
+		e = tab + (i & mask);
+		if (!e->item.key ||
+		    (e->hash==hash && strcmp(e->item.key, key)==0))
+			break;
+	}
+	return e;
+}
+
+ENTRY *hsearch(ENTRY item, ACTION action)
+{
+	size_t hash = keyhash(item.key);
+	struct entry *e = lookup(item.key, hash);
+
+	if (e->item.key)
+		return &e->item;
+	if (action == FIND)
+		return 0;
+	e->item = item;
+	e->hash = hash;
+	if (++used > mask - mask/4) {
+		if (!resize(2*used)) {
+			used--;
+			e->item.key = 0;
+			return 0;
+		}
+		e = lookup(item.key, hash);
+	}
+	return &e->item;
+}
diff --git a/src/search/insque.c b/src/search/insque.c
new file mode 100644
index 00000000..b7475d84
--- /dev/null
+++ b/src/search/insque.c
@@ -0,0 +1,32 @@
+#include <search.h>
+
+struct node {
+	struct node *next;
+	struct node *prev;
+};
+
+void insque(void *element, void *pred)
+{
+	struct node *e = element;
+	struct node *p = pred;
+
+	if (!p) {
+		e->next = e->prev = 0;
+		return;
+	}
+	e->next = p->next;
+	e->prev = p;
+	p->next = e;
+	if (e->next)
+		e->next->prev = e;
+}
+
+void remque(void *element)
+{
+	struct node *e = element;
+
+	if (e->next)
+		e->next->prev = e->prev;
+	if (e->prev)
+		e->prev->next = e->next;
+}
diff --git a/src/search/lsearch.c b/src/search/lsearch.c
new file mode 100644
index 00000000..63f31922
--- /dev/null
+++ b/src/search/lsearch.c
@@ -0,0 +1,31 @@
+#include <search.h>
+#include <string.h>
+
+void *lsearch(const void *key, void *base, size_t *nelp, size_t width,
+	int (*compar)(const void *, const void *))
+{
+	char (*p)[width] = base;
+	size_t n = *nelp;
+	size_t i;
+
+	for (i = 0; i < n; i++)
+		if (compar(p[i], key) == 0)
+			return p[i];
+	*nelp = n+1;
+	return memcpy(p[n], key, width);
+}
+
+void *lfind(const void *key, const void *base, size_t *nelp,
+	size_t width, int (*compar)(const void *, const void *))
+{
+	char (*p)[width] = (void *)base;
+	size_t n = *nelp;
+	size_t i;
+
+	for (i = 0; i < n; i++)
+		if (compar(p[i], key) == 0)
+			return p[i];
+	return 0;
+}
+
+
diff --git a/src/search/tsearch_avl.c b/src/search/tsearch_avl.c
new file mode 100644
index 00000000..f5c2cf61
--- /dev/null
+++ b/src/search/tsearch_avl.c
@@ -0,0 +1,171 @@
+#include <stdlib.h>
+#include <search.h>
+
+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 *), int *new)
+{
+	struct node *r = *n;
+	int c;
+
+	if (!r) {
+		*n = r = malloc(sizeof **n);
+		if (r) {
+			r->key = k;
+			r->left = r->right = 0;
+			r->height = 1;
+		}
+		*new = 1;
+		return r;
+	}
+	c = cmp(k, r->key);
+	if (c == 0)
+		return r;
+	if (c < 0)
+		r = insert(&r->left, k, cmp, new);
+	else
+		r = insert(&r->right, k, cmp, new);
+	if (*new)
+		*n = balance(*n);
+	return r;
+}
+
+static struct node *movr(struct node *n, struct node *r) {
+	if (!n)
+		return r;
+	n->right = movr(n->right, r);
+	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;
+		*n = movr(r->left, 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 *))
+{
+	/* last argument is arbitrary non-null pointer
+	   which is returned when the root node is deleted */
+	return remove((void*)rootp, key, compar, *rootp);
+}
+
+void *tfind(const void *key, void *const *rootp,
+	int(*compar)(const void *, const void *))
+{
+	return find(*rootp, key, compar);
+}
+
+void *tsearch(const void *key, void **rootp,
+	int (*compar)(const void *, const void *))
+{
+	int new = 0;
+	return insert((void*)rootp, key, compar, &new);
+}
+
+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);
+}