From febbd12d00883a716a9edca25011f8aa306b859b Mon Sep 17 00:00:00 2001 From: Rich Felker Date: Sat, 25 Jun 2011 18:18:57 -0400 Subject: [PATCH] XSI search.h API implementation by Szabolcs Nagy --- COPYRIGHT | 8 +- include/search.h | 36 ++++++++- src/search/hsearch.c | 118 +++++++++++++++++++++++++++ src/search/insque.c | 32 ++++++++ src/search/lsearch.c | 31 +++++++ src/search/tsearch_avl.c | 171 +++++++++++++++++++++++++++++++++++++++ 6 files changed, 392 insertions(+), 4 deletions(-) create mode 100644 src/search/hsearch.c create mode 100644 src/search/insque.c create mode 100644 src/search/lsearch.c create mode 100644 src/search/tsearch_avl.c 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 + +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 +#include +#include + +/* +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 + +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 +#include + +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 +#include + +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); +} -- 2.25.1