2020-09-12 05:49:10 -07:00
|
|
|
/*
|
|
|
|
musl license, hsearch.c originally written by Szabolcs Nagy
|
|
|
|
|
|
|
|
Copyright © 2005-2020 Rich Felker, et al.
|
|
|
|
|
|
|
|
Permission is hereby granted, free of charge, to any person obtaining
|
|
|
|
a copy of this software and associated documentation files (the
|
|
|
|
"Software"), to deal in the Software without restriction, including
|
|
|
|
without limitation the rights to use, copy, modify, merge, publish,
|
|
|
|
distribute, sublicense, and/or sell copies of the Software, and to
|
|
|
|
permit persons to whom the Software is furnished to do so, subject to
|
|
|
|
the following conditions:
|
|
|
|
|
|
|
|
The above copyright notice and this permission notice shall be
|
|
|
|
included in all copies or substantial portions of the Software.
|
|
|
|
|
|
|
|
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
|
|
|
|
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
|
|
|
|
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
|
|
|
|
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
|
|
|
|
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
|
|
|
|
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
|
|
|
|
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
|
|
|
|
*/
|
|
|
|
|
|
|
|
#include <stdlib.h>
|
|
|
|
#include <string.h>
|
|
|
|
#include "hsearch.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
|
|
|
|
*/
|
|
|
|
|
|
|
|
typedef struct htab_entry {
|
|
|
|
char *key;
|
|
|
|
htab_value data;
|
|
|
|
} htab_entry;
|
|
|
|
|
|
|
|
struct elem {
|
|
|
|
htab_entry item;
|
|
|
|
size_t hash;
|
|
|
|
};
|
|
|
|
|
|
|
|
struct htab {
|
|
|
|
struct elem *elems;
|
|
|
|
size_t mask;
|
|
|
|
size_t used;
|
2020-09-15 12:28:19 -07:00
|
|
|
size_t seed;
|
htab: prevent filling up of table with tombstones
as pointed out by @craigbarnes [0], using the latest fix for
the tombstone issue, it's possible to provoke a situation
that causes an endless loop when all free slots in the table
are filled up with tombstones and htab_find() is called.
therefore we need to account for those as well when deciding
if there's a need to call resize() so there's never more than
75% of the table used by either dead or live items.
the resize() serves as a rehash which gets rid of all deleted
entries, and it might cause the table size to shrink if
htab_insert() is called after a lot of items have been removed.
[0]: https://github.com/rofl0r/htab/issues/1#issuecomment-800094442
testcase:
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hsearch.h"
#define HTAB_OOM_TEST
#include "hsearch.c"
static char *xstrdup(const char *str)
{
char *dup = strdup(str);
assert(dup);
return dup;
}
void utoa(unsigned number, char* buffer) {
int lentest, len = 0, i, start = 0;
lentest = number;
do {
len++;
lentest /= 10;
} while(lentest);
buffer[start+len] = 0;
do {
i = number % 10;
buffer[start+len - 1] = '0' + i;
number -= i;
len -= 1;
number /= 10;
} while (number);
}
#define TESTSIZE 8
#define KEEP 1
static char* notorious[TESTSIZE];
static void prep() {
srand(0);
char buf[16];
size_t filled = 0;
while(filled < TESTSIZE) {
utoa(rand(), buf);
size_t idx = keyhash(buf) & (TESTSIZE-1);
if(!notorious[idx]) {
notorious[idx] = xstrdup(buf);
++filled;
}
}
}
int main(void)
{
struct htab *h = htab_create(TESTSIZE);
size_t i;
assert(h);
prep();
for(i=0; i<TESTSIZE; ++i) {
char *key = notorious[i];
printf("[%zu] = \"%s\"\n", i, key);
int r = htab_insert(h, key, HTV_N(42));
if(!r == 1) {
printf("element %zu couldn't be inserted\n", i);
break;
}
assert(r == 1);
// Ensure newly inserted entry can be found
assert(htab_find(h, key));
if(i >= KEEP) htab_delete(h, key);
}
htab_find(h, "looooop");
return 0;
}
2021-03-16 14:33:30 -07:00
|
|
|
size_t dead;
|
2020-09-12 05:49:10 -07:00
|
|
|
};
|
|
|
|
|
|
|
|
#define MINSIZE 8
|
|
|
|
#define MAXSIZE ((size_t)-1/2 + 1)
|
|
|
|
|
|
|
|
#define CASE_INSENSITIVE
|
|
|
|
#ifdef CASE_INSENSITIVE
|
|
|
|
#include <ctype.h>
|
|
|
|
#include <strings.h>
|
|
|
|
#define LOWER_OR_NOT(X) tolower(X)
|
|
|
|
#define STRCMP(X, Y) strcasecmp(X, Y)
|
|
|
|
#else
|
|
|
|
#define LOWER_OR_NOT(X) X
|
|
|
|
#define STRCMP(X, Y) strcmp(X, Y)
|
|
|
|
#endif
|
|
|
|
|
2020-09-15 12:28:19 -07:00
|
|
|
static size_t keyhash(const char *k, size_t seed)
|
2020-09-12 05:49:10 -07:00
|
|
|
{
|
|
|
|
const unsigned char *p = (const void *)k;
|
2020-09-15 12:28:19 -07:00
|
|
|
size_t h = seed;
|
2020-09-12 05:49:10 -07:00
|
|
|
|
|
|
|
while (*p)
|
|
|
|
h = 31*h + LOWER_OR_NOT(*p++);
|
|
|
|
return h;
|
|
|
|
}
|
|
|
|
|
|
|
|
static int resize(struct htab *htab, size_t nel)
|
|
|
|
{
|
|
|
|
size_t newsize;
|
|
|
|
size_t i, j;
|
|
|
|
struct elem *e, *newe;
|
|
|
|
struct elem *oldtab = htab->elems;
|
|
|
|
struct elem *oldend = htab->elems + htab->mask + 1;
|
|
|
|
|
|
|
|
if (nel > MAXSIZE)
|
|
|
|
nel = MAXSIZE;
|
|
|
|
for (newsize = MINSIZE; newsize < nel; newsize *= 2);
|
|
|
|
htab->elems = calloc(newsize, sizeof *htab->elems);
|
|
|
|
if (!htab->elems) {
|
|
|
|
htab->elems = oldtab;
|
|
|
|
return 0;
|
|
|
|
}
|
|
|
|
htab->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->elems + (i & htab->mask);
|
|
|
|
if (!newe->item.key)
|
|
|
|
break;
|
|
|
|
}
|
|
|
|
*newe = *e;
|
|
|
|
}
|
|
|
|
free(oldtab);
|
|
|
|
return 1;
|
|
|
|
}
|
|
|
|
|
2021-03-13 17:06:35 -08:00
|
|
|
static struct elem *lookup(struct htab *htab, const char *key, size_t hash, size_t dead)
|
2020-09-12 05:49:10 -07:00
|
|
|
{
|
|
|
|
size_t i, j;
|
|
|
|
struct elem *e;
|
|
|
|
|
|
|
|
for (i=hash,j=1; ; i+=j++) {
|
|
|
|
e = htab->elems + (i & htab->mask);
|
2021-03-13 17:06:35 -08:00
|
|
|
if ((!e->item.key && (!e->hash || e->hash == dead)) ||
|
2020-09-12 05:49:10 -07:00
|
|
|
(e->hash==hash && STRCMP(e->item.key, key)==0))
|
|
|
|
break;
|
|
|
|
}
|
|
|
|
return e;
|
|
|
|
}
|
|
|
|
|
|
|
|
struct htab *htab_create(size_t nel)
|
|
|
|
{
|
|
|
|
struct htab *r = calloc(1, sizeof *r);
|
|
|
|
if(r && !resize(r, nel)) {
|
|
|
|
free(r);
|
|
|
|
r = 0;
|
|
|
|
}
|
2020-09-15 12:28:19 -07:00
|
|
|
r->seed = rand();
|
2020-09-12 05:49:10 -07:00
|
|
|
return r;
|
|
|
|
}
|
|
|
|
|
|
|
|
void htab_destroy(struct htab *htab)
|
|
|
|
{
|
|
|
|
free(htab->elems);
|
|
|
|
free(htab);
|
|
|
|
}
|
|
|
|
|
2021-03-13 17:06:35 -08:00
|
|
|
static struct elem *htab_find_elem(struct htab *htab, const char* key)
|
2020-09-12 05:49:10 -07:00
|
|
|
{
|
2020-09-15 12:28:19 -07:00
|
|
|
size_t hash = keyhash(key, htab->seed);
|
2021-03-13 17:06:35 -08:00
|
|
|
struct elem *e = lookup(htab, key, hash, 0);
|
2020-09-12 05:49:10 -07:00
|
|
|
|
|
|
|
if (e->item.key) {
|
2021-03-13 17:06:35 -08:00
|
|
|
return e;
|
2020-09-12 05:49:10 -07:00
|
|
|
}
|
|
|
|
return 0;
|
|
|
|
}
|
|
|
|
|
|
|
|
htab_value* htab_find(struct htab *htab, const char* key)
|
|
|
|
{
|
2021-03-13 17:06:35 -08:00
|
|
|
struct elem *e = htab_find_elem(htab, key);
|
|
|
|
if(!e) return 0;
|
|
|
|
return &e->item.data;
|
2020-09-12 05:49:10 -07:00
|
|
|
}
|
|
|
|
|
2021-03-14 09:06:10 -07:00
|
|
|
htab_value* htab_find2(struct htab *htab, const char* key, char **saved_key)
|
|
|
|
{
|
|
|
|
struct elem *e = htab_find_elem(htab, key);
|
|
|
|
if(!e) return 0;
|
|
|
|
*saved_key = e->item.key;
|
|
|
|
return &e->item.data;
|
|
|
|
}
|
|
|
|
|
2020-09-12 05:49:10 -07:00
|
|
|
int htab_delete(struct htab *htab, const char* key)
|
|
|
|
{
|
2021-03-13 17:06:35 -08:00
|
|
|
struct elem *e = htab_find_elem(htab, key);
|
|
|
|
if(!e) return 0;
|
|
|
|
e->item.key = 0;
|
|
|
|
e->hash = 0xdeadc0de;
|
|
|
|
--htab->used;
|
htab: prevent filling up of table with tombstones
as pointed out by @craigbarnes [0], using the latest fix for
the tombstone issue, it's possible to provoke a situation
that causes an endless loop when all free slots in the table
are filled up with tombstones and htab_find() is called.
therefore we need to account for those as well when deciding
if there's a need to call resize() so there's never more than
75% of the table used by either dead or live items.
the resize() serves as a rehash which gets rid of all deleted
entries, and it might cause the table size to shrink if
htab_insert() is called after a lot of items have been removed.
[0]: https://github.com/rofl0r/htab/issues/1#issuecomment-800094442
testcase:
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hsearch.h"
#define HTAB_OOM_TEST
#include "hsearch.c"
static char *xstrdup(const char *str)
{
char *dup = strdup(str);
assert(dup);
return dup;
}
void utoa(unsigned number, char* buffer) {
int lentest, len = 0, i, start = 0;
lentest = number;
do {
len++;
lentest /= 10;
} while(lentest);
buffer[start+len] = 0;
do {
i = number % 10;
buffer[start+len - 1] = '0' + i;
number -= i;
len -= 1;
number /= 10;
} while (number);
}
#define TESTSIZE 8
#define KEEP 1
static char* notorious[TESTSIZE];
static void prep() {
srand(0);
char buf[16];
size_t filled = 0;
while(filled < TESTSIZE) {
utoa(rand(), buf);
size_t idx = keyhash(buf) & (TESTSIZE-1);
if(!notorious[idx]) {
notorious[idx] = xstrdup(buf);
++filled;
}
}
}
int main(void)
{
struct htab *h = htab_create(TESTSIZE);
size_t i;
assert(h);
prep();
for(i=0; i<TESTSIZE; ++i) {
char *key = notorious[i];
printf("[%zu] = \"%s\"\n", i, key);
int r = htab_insert(h, key, HTV_N(42));
if(!r == 1) {
printf("element %zu couldn't be inserted\n", i);
break;
}
assert(r == 1);
// Ensure newly inserted entry can be found
assert(htab_find(h, key));
if(i >= KEEP) htab_delete(h, key);
}
htab_find(h, "looooop");
return 0;
}
2021-03-16 14:33:30 -07:00
|
|
|
++htab->dead;
|
2020-09-12 05:49:10 -07:00
|
|
|
return 1;
|
|
|
|
}
|
|
|
|
|
|
|
|
int htab_insert(struct htab *htab, char* key, htab_value value)
|
|
|
|
{
|
htab: prevent filling up of table with tombstones
as pointed out by @craigbarnes [0], using the latest fix for
the tombstone issue, it's possible to provoke a situation
that causes an endless loop when all free slots in the table
are filled up with tombstones and htab_find() is called.
therefore we need to account for those as well when deciding
if there's a need to call resize() so there's never more than
75% of the table used by either dead or live items.
the resize() serves as a rehash which gets rid of all deleted
entries, and it might cause the table size to shrink if
htab_insert() is called after a lot of items have been removed.
[0]: https://github.com/rofl0r/htab/issues/1#issuecomment-800094442
testcase:
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hsearch.h"
#define HTAB_OOM_TEST
#include "hsearch.c"
static char *xstrdup(const char *str)
{
char *dup = strdup(str);
assert(dup);
return dup;
}
void utoa(unsigned number, char* buffer) {
int lentest, len = 0, i, start = 0;
lentest = number;
do {
len++;
lentest /= 10;
} while(lentest);
buffer[start+len] = 0;
do {
i = number % 10;
buffer[start+len - 1] = '0' + i;
number -= i;
len -= 1;
number /= 10;
} while (number);
}
#define TESTSIZE 8
#define KEEP 1
static char* notorious[TESTSIZE];
static void prep() {
srand(0);
char buf[16];
size_t filled = 0;
while(filled < TESTSIZE) {
utoa(rand(), buf);
size_t idx = keyhash(buf) & (TESTSIZE-1);
if(!notorious[idx]) {
notorious[idx] = xstrdup(buf);
++filled;
}
}
}
int main(void)
{
struct htab *h = htab_create(TESTSIZE);
size_t i;
assert(h);
prep();
for(i=0; i<TESTSIZE; ++i) {
char *key = notorious[i];
printf("[%zu] = \"%s\"\n", i, key);
int r = htab_insert(h, key, HTV_N(42));
if(!r == 1) {
printf("element %zu couldn't be inserted\n", i);
break;
}
assert(r == 1);
// Ensure newly inserted entry can be found
assert(htab_find(h, key));
if(i >= KEEP) htab_delete(h, key);
}
htab_find(h, "looooop");
return 0;
}
2021-03-16 14:33:30 -07:00
|
|
|
size_t hash = keyhash(key, htab->seed), oh;
|
2021-03-13 17:06:35 -08:00
|
|
|
struct elem *e = lookup(htab, key, hash, 0xdeadc0de);
|
2020-09-12 05:49:10 -07:00
|
|
|
if(e->item.key) {
|
|
|
|
/* it's not allowed to overwrite existing data */
|
|
|
|
return 0;
|
|
|
|
}
|
|
|
|
|
htab: prevent filling up of table with tombstones
as pointed out by @craigbarnes [0], using the latest fix for
the tombstone issue, it's possible to provoke a situation
that causes an endless loop when all free slots in the table
are filled up with tombstones and htab_find() is called.
therefore we need to account for those as well when deciding
if there's a need to call resize() so there's never more than
75% of the table used by either dead or live items.
the resize() serves as a rehash which gets rid of all deleted
entries, and it might cause the table size to shrink if
htab_insert() is called after a lot of items have been removed.
[0]: https://github.com/rofl0r/htab/issues/1#issuecomment-800094442
testcase:
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hsearch.h"
#define HTAB_OOM_TEST
#include "hsearch.c"
static char *xstrdup(const char *str)
{
char *dup = strdup(str);
assert(dup);
return dup;
}
void utoa(unsigned number, char* buffer) {
int lentest, len = 0, i, start = 0;
lentest = number;
do {
len++;
lentest /= 10;
} while(lentest);
buffer[start+len] = 0;
do {
i = number % 10;
buffer[start+len - 1] = '0' + i;
number -= i;
len -= 1;
number /= 10;
} while (number);
}
#define TESTSIZE 8
#define KEEP 1
static char* notorious[TESTSIZE];
static void prep() {
srand(0);
char buf[16];
size_t filled = 0;
while(filled < TESTSIZE) {
utoa(rand(), buf);
size_t idx = keyhash(buf) & (TESTSIZE-1);
if(!notorious[idx]) {
notorious[idx] = xstrdup(buf);
++filled;
}
}
}
int main(void)
{
struct htab *h = htab_create(TESTSIZE);
size_t i;
assert(h);
prep();
for(i=0; i<TESTSIZE; ++i) {
char *key = notorious[i];
printf("[%zu] = \"%s\"\n", i, key);
int r = htab_insert(h, key, HTV_N(42));
if(!r == 1) {
printf("element %zu couldn't be inserted\n", i);
break;
}
assert(r == 1);
// Ensure newly inserted entry can be found
assert(htab_find(h, key));
if(i >= KEEP) htab_delete(h, key);
}
htab_find(h, "looooop");
return 0;
}
2021-03-16 14:33:30 -07:00
|
|
|
oh = e->hash; /* save old hash in case it's tombstone marker */
|
2020-09-12 05:49:10 -07:00
|
|
|
e->item.key = key;
|
|
|
|
e->item.data = value;
|
|
|
|
e->hash = hash;
|
htab: prevent filling up of table with tombstones
as pointed out by @craigbarnes [0], using the latest fix for
the tombstone issue, it's possible to provoke a situation
that causes an endless loop when all free slots in the table
are filled up with tombstones and htab_find() is called.
therefore we need to account for those as well when deciding
if there's a need to call resize() so there's never more than
75% of the table used by either dead or live items.
the resize() serves as a rehash which gets rid of all deleted
entries, and it might cause the table size to shrink if
htab_insert() is called after a lot of items have been removed.
[0]: https://github.com/rofl0r/htab/issues/1#issuecomment-800094442
testcase:
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hsearch.h"
#define HTAB_OOM_TEST
#include "hsearch.c"
static char *xstrdup(const char *str)
{
char *dup = strdup(str);
assert(dup);
return dup;
}
void utoa(unsigned number, char* buffer) {
int lentest, len = 0, i, start = 0;
lentest = number;
do {
len++;
lentest /= 10;
} while(lentest);
buffer[start+len] = 0;
do {
i = number % 10;
buffer[start+len - 1] = '0' + i;
number -= i;
len -= 1;
number /= 10;
} while (number);
}
#define TESTSIZE 8
#define KEEP 1
static char* notorious[TESTSIZE];
static void prep() {
srand(0);
char buf[16];
size_t filled = 0;
while(filled < TESTSIZE) {
utoa(rand(), buf);
size_t idx = keyhash(buf) & (TESTSIZE-1);
if(!notorious[idx]) {
notorious[idx] = xstrdup(buf);
++filled;
}
}
}
int main(void)
{
struct htab *h = htab_create(TESTSIZE);
size_t i;
assert(h);
prep();
for(i=0; i<TESTSIZE; ++i) {
char *key = notorious[i];
printf("[%zu] = \"%s\"\n", i, key);
int r = htab_insert(h, key, HTV_N(42));
if(!r == 1) {
printf("element %zu couldn't be inserted\n", i);
break;
}
assert(r == 1);
// Ensure newly inserted entry can be found
assert(htab_find(h, key));
if(i >= KEEP) htab_delete(h, key);
}
htab_find(h, "looooop");
return 0;
}
2021-03-16 14:33:30 -07:00
|
|
|
if (++htab->used + htab->dead > htab->mask - htab->mask/4) {
|
2020-09-12 05:49:10 -07:00
|
|
|
if (!resize(htab, 2*htab->used)) {
|
|
|
|
htab->used--;
|
|
|
|
e->item.key = 0;
|
htab: prevent filling up of table with tombstones
as pointed out by @craigbarnes [0], using the latest fix for
the tombstone issue, it's possible to provoke a situation
that causes an endless loop when all free slots in the table
are filled up with tombstones and htab_find() is called.
therefore we need to account for those as well when deciding
if there's a need to call resize() so there's never more than
75% of the table used by either dead or live items.
the resize() serves as a rehash which gets rid of all deleted
entries, and it might cause the table size to shrink if
htab_insert() is called after a lot of items have been removed.
[0]: https://github.com/rofl0r/htab/issues/1#issuecomment-800094442
testcase:
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hsearch.h"
#define HTAB_OOM_TEST
#include "hsearch.c"
static char *xstrdup(const char *str)
{
char *dup = strdup(str);
assert(dup);
return dup;
}
void utoa(unsigned number, char* buffer) {
int lentest, len = 0, i, start = 0;
lentest = number;
do {
len++;
lentest /= 10;
} while(lentest);
buffer[start+len] = 0;
do {
i = number % 10;
buffer[start+len - 1] = '0' + i;
number -= i;
len -= 1;
number /= 10;
} while (number);
}
#define TESTSIZE 8
#define KEEP 1
static char* notorious[TESTSIZE];
static void prep() {
srand(0);
char buf[16];
size_t filled = 0;
while(filled < TESTSIZE) {
utoa(rand(), buf);
size_t idx = keyhash(buf) & (TESTSIZE-1);
if(!notorious[idx]) {
notorious[idx] = xstrdup(buf);
++filled;
}
}
}
int main(void)
{
struct htab *h = htab_create(TESTSIZE);
size_t i;
assert(h);
prep();
for(i=0; i<TESTSIZE; ++i) {
char *key = notorious[i];
printf("[%zu] = \"%s\"\n", i, key);
int r = htab_insert(h, key, HTV_N(42));
if(!r == 1) {
printf("element %zu couldn't be inserted\n", i);
break;
}
assert(r == 1);
// Ensure newly inserted entry can be found
assert(htab_find(h, key));
if(i >= KEEP) htab_delete(h, key);
}
htab_find(h, "looooop");
return 0;
}
2021-03-16 14:33:30 -07:00
|
|
|
e->hash = oh;
|
2020-09-12 05:49:10 -07:00
|
|
|
return 0;
|
|
|
|
}
|
htab: prevent filling up of table with tombstones
as pointed out by @craigbarnes [0], using the latest fix for
the tombstone issue, it's possible to provoke a situation
that causes an endless loop when all free slots in the table
are filled up with tombstones and htab_find() is called.
therefore we need to account for those as well when deciding
if there's a need to call resize() so there's never more than
75% of the table used by either dead or live items.
the resize() serves as a rehash which gets rid of all deleted
entries, and it might cause the table size to shrink if
htab_insert() is called after a lot of items have been removed.
[0]: https://github.com/rofl0r/htab/issues/1#issuecomment-800094442
testcase:
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hsearch.h"
#define HTAB_OOM_TEST
#include "hsearch.c"
static char *xstrdup(const char *str)
{
char *dup = strdup(str);
assert(dup);
return dup;
}
void utoa(unsigned number, char* buffer) {
int lentest, len = 0, i, start = 0;
lentest = number;
do {
len++;
lentest /= 10;
} while(lentest);
buffer[start+len] = 0;
do {
i = number % 10;
buffer[start+len - 1] = '0' + i;
number -= i;
len -= 1;
number /= 10;
} while (number);
}
#define TESTSIZE 8
#define KEEP 1
static char* notorious[TESTSIZE];
static void prep() {
srand(0);
char buf[16];
size_t filled = 0;
while(filled < TESTSIZE) {
utoa(rand(), buf);
size_t idx = keyhash(buf) & (TESTSIZE-1);
if(!notorious[idx]) {
notorious[idx] = xstrdup(buf);
++filled;
}
}
}
int main(void)
{
struct htab *h = htab_create(TESTSIZE);
size_t i;
assert(h);
prep();
for(i=0; i<TESTSIZE; ++i) {
char *key = notorious[i];
printf("[%zu] = \"%s\"\n", i, key);
int r = htab_insert(h, key, HTV_N(42));
if(!r == 1) {
printf("element %zu couldn't be inserted\n", i);
break;
}
assert(r == 1);
// Ensure newly inserted entry can be found
assert(htab_find(h, key));
if(i >= KEEP) htab_delete(h, key);
}
htab_find(h, "looooop");
return 0;
}
2021-03-16 14:33:30 -07:00
|
|
|
htab->dead = 0;
|
|
|
|
} else if (oh == 0xdeadc0de) {
|
|
|
|
/* re-used tomb */
|
|
|
|
--htab->dead;
|
2020-09-12 05:49:10 -07:00
|
|
|
}
|
|
|
|
return 1;
|
|
|
|
}
|
|
|
|
|
|
|
|
size_t htab_next(struct htab *htab, size_t iterator, char** key, htab_value **v)
|
|
|
|
{
|
|
|
|
size_t i;
|
|
|
|
for(i=iterator;i<htab->mask+1;++i) {
|
|
|
|
struct elem *e = htab->elems + i;
|
|
|
|
if(e->item.key) {
|
|
|
|
*key = e->item.key;
|
|
|
|
*v = &e->item.data;
|
|
|
|
return i+1;
|
|
|
|
}
|
|
|
|
}
|
|
|
|
return 0;
|
|
|
|
}
|