X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=src%2Fsearch%2Fhsearch.c;h=b3ac8796e70fd00d6251949b308db7761b156e97;hb=5ff3eea91fa6bdce25b3a35644433f68e076beca;hp=88edb2634b533853ddf9356f83e804689f83e18a;hpb=fe1ba7dbf187e34985896b40d469d84a7a4a98d0;p=musl diff --git a/src/search/hsearch.c b/src/search/hsearch.c index 88edb263..b3ac8796 100644 --- a/src/search/hsearch.c +++ b/src/search/hsearch.c @@ -2,7 +2,6 @@ #include #include #include -#include "libc.h" /* open addressing hash table with 2^n table size @@ -16,22 +15,17 @@ with the posix api items cannot be iterated and length cannot be queried #define MINSIZE 8 #define MAXSIZE ((size_t)-1/2 + 1) -struct elem { - ENTRY item; - size_t hash; -}; - struct __tab { - struct elem *elems; + ENTRY *entries; size_t mask; size_t used; }; static struct hsearch_data htab; -int __hcreate_r(size_t, struct hsearch_data *); -void __hdestroy_r(struct hsearch_data *); -int __hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *); +static int __hcreate_r(size_t, struct hsearch_data *); +static void __hdestroy_r(struct hsearch_data *); +static int __hsearch_r(ENTRY, ACTION, ENTRY **, struct hsearch_data *); static size_t keyhash(char *k) { @@ -47,26 +41,26 @@ static int resize(size_t nel, struct hsearch_data *htab) { size_t newsize; size_t i, j; - struct elem *e, *newe; - struct elem *oldtab = htab->__tab->elems; - struct elem *oldend = htab->__tab->elems + htab->__tab->mask + 1; + ENTRY *e, *newe; + ENTRY *oldtab = htab->__tab->entries; + ENTRY *oldend = htab->__tab->entries + htab->__tab->mask + 1; if (nel > MAXSIZE) nel = MAXSIZE; for (newsize = MINSIZE; newsize < nel; newsize *= 2); - htab->__tab->elems = calloc(newsize, sizeof *htab->__tab->elems); - if (!htab->__tab->elems) { - htab->__tab->elems = oldtab; + htab->__tab->entries = calloc(newsize, sizeof *htab->__tab->entries); + if (!htab->__tab->entries) { + htab->__tab->entries = oldtab; return 0; } htab->__tab->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 = htab->__tab->elems + (i & htab->__tab->mask); - if (!newe->item.key) + if (e->key) { + for (i=keyhash(e->key),j=1; ; i+=j++) { + newe = htab->__tab->entries + (i & htab->__tab->mask); + if (!newe->key) break; } *newe = *e; @@ -85,15 +79,14 @@ void hdestroy(void) __hdestroy_r(&htab); } -static struct elem *lookup(char *key, size_t hash, struct hsearch_data *htab) +static ENTRY *lookup(char *key, size_t hash, struct hsearch_data *htab) { size_t i, j; - struct elem *e; + ENTRY *e; for (i=hash,j=1; ; i+=j++) { - e = htab->__tab->elems + (i & htab->__tab->mask); - if (!e->item.key || - (e->hash==hash && strcmp(e->item.key, key)==0)) + e = htab->__tab->entries + (i & htab->__tab->mask); + if (!e->key || strcmp(e->key, key) == 0) break; } return e; @@ -107,7 +100,7 @@ ENTRY *hsearch(ENTRY item, ACTION action) return e; } -int __hcreate_r(size_t nel, struct hsearch_data *htab) +static int __hcreate_r(size_t nel, struct hsearch_data *htab) { int r; @@ -123,39 +116,38 @@ int __hcreate_r(size_t nel, struct hsearch_data *htab) } weak_alias(__hcreate_r, hcreate_r); -void __hdestroy_r(struct hsearch_data *htab) +static void __hdestroy_r(struct hsearch_data *htab) { - if (htab->__tab) free(htab->__tab->elems); + if (htab->__tab) free(htab->__tab->entries); free(htab->__tab); htab->__tab = 0; } weak_alias(__hdestroy_r, hdestroy_r); -int __hsearch_r(ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab) +static int __hsearch_r(ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab) { size_t hash = keyhash(item.key); - struct elem *e = lookup(item.key, hash, htab); + ENTRY *e = lookup(item.key, hash, htab); - if (e->item.key) { - *retval = &e->item; + if (e->key) { + *retval = e; return 1; } if (action == FIND) { *retval = 0; return 0; } - e->item = item; - e->hash = hash; + *e = item; if (++htab->__tab->used > htab->__tab->mask - htab->__tab->mask/4) { if (!resize(2*htab->__tab->used, htab)) { htab->__tab->used--; - e->item.key = 0; + e->key = 0; *retval = 0; return 0; } e = lookup(item.key, hash, htab); } - *retval = &e->item; + *retval = e; return 1; } weak_alias(__hsearch_r, hsearch_r);