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.
#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
--- /dev/null
+#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;
+}
--- /dev/null
+#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;
+}
--- /dev/null
+#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;
+}
+
+
--- /dev/null
+#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);
+}
projects / musl / commitdiff