From 4a079556fda3d05d8f7b0f1978b60e3c2982ba4c Mon Sep 17 00:00:00 2001 From: Not Zed Date: Sun, 10 May 2020 08:24:28 +0930 Subject: [PATCH] Allow for static initialisation. remove set_create set_init clears fields EZ_SET_INIT takes callback parameters set_put creates the table if necessary other functions noop on an unallocated table (mask == 0) --- ez-set.c | 90 ++++++++++++++++++++++++++---------------------------- ez-set.h | 20 ++++++------ test-set.c | 60 +++++++++++++++++++++++++----------- 3 files changed, 96 insertions(+), 74 deletions(-) diff --git a/ez-set.c b/ez-set.c index 00ac3fc..0705bef 100644 --- a/ez-set.c +++ b/ez-set.c @@ -53,7 +53,7 @@ static ez_node *set_lookup(ez_set *h, const ez_node *key, unsigned int hash, ez_ scan = scan->u.set.next; } *pp = p; - + return scan; } @@ -92,7 +92,6 @@ static void set_rehash(ez_set *h, int newsize) { h->mask = mask; } - /** * Find the next non-empty chain. */ @@ -112,51 +111,32 @@ static void *scan_next_chain(ez_set *h, ez_set_scan *scan, int idx) { /* ********************************************************************** */ /* Main api */ -ez_set *ez_set_new(unsigned int (*hash)(const void *), int (*equals)(const void *, const void *), void (*efree)(void *)) { - ez_set *h = malloc(sizeof(*h)); - - if (h) { - h->table = calloc(sizeof(ez_node), 16); - h->mask = 15; - h->hash = hash; - h->equals = equals; - h->free = efree; - h->count = 0; - - if (!h->table) { - free(h); - return NULL; - } - } - - return h; -} - -void ez_set_free(ez_set *h) { - if (h) { - ez_set_clear(h); - free(h->table); - free(h); - } +void ez_set_init(ez_set *h, unsigned int (*hash)(const void *), int (*equals)(const void *, const void *), void (*efree)(void *)) { + h->table = NULL; + h->mask = 0; + h->count = 0; + h->hash = hash; + h->equals = equals; + h->free = efree; } void ez_set_clear(ez_set *h) { - for (int i=0;i<=h->mask;i++) { - ez_node *e = h->table[i]; - - while (e) { - ez_node *n = ez_node_next(e); - if (h->free) - h->free(e); - e = n; + if (h->mask) { + for (int i=0;i<=h->mask;i++) { + ez_node *e = h->table[i]; + + while (e) { + ez_node *n = ez_node_next(e); + if (h->free) + h->free(e); + e = n; + } + h->table[i] = NULL; } - h->table[i] = NULL; - } - h->count = 0; - - if (h->mask > 15) { - h->table = realloc(h->table, 16 * sizeof(ez_node)); - h->mask = 15; + free(h->table); + h->table = NULL; + h->mask = 0; + h->count = 0; } } @@ -167,8 +147,15 @@ int ez_set_size(ez_set *h) { void *ez_set_put(ez_set *h, void *ep) { ez_node *e = ep, *scan, *p; + if (h->mask == 0) { + h->table = calloc(sizeof(*h->table), 16); + if (!h->table) + return ep; + h->mask = 15; + } + // Entries are only ever hashed once, here. - e->u.set.hash = h->hash(e); + e->u.set.hash = h->hash(e); scan = set_lookup(h, e, e->u.set.hash, &p); // insert new node, possibly unlinking old one @@ -190,7 +177,11 @@ void *ez_set_put(ez_set *h, void *ep) { void *ez_set_get(ez_set *h, const void *ep) { const struct ez_node *e = ep; struct ez_node *p; - unsigned int hash = ez_set_node_hash(h, e); + unsigned int hash; + + if (h->mask == 0) return NULL; + + hash = ez_set_node_hash(h, e); return set_lookup(h, e, hash, &p); } @@ -198,8 +189,11 @@ void *ez_set_get(ez_set *h, const void *ep) { void *ez_set_remove(ez_set *h, const void *ep) { const ez_node *e = ep; struct ez_node *scan, *p; - unsigned int hash = ez_set_node_hash(h, e); + unsigned int hash; + + if (h->mask == 0) return NULL; + hash = ez_set_node_hash(h, e); scan = set_lookup(h, e, hash, &p); if (scan) { // unlink old node @@ -216,6 +210,8 @@ void *ez_set_remove(ez_set *h, const void *ep) { /* Set iterator */ void *ez_set_scan_init(ez_set *h, ez_set_scan *scan) { + if (h->mask == 0) return NULL; + scan->set = h; scan_next_chain(h, scan, 0); @@ -268,7 +264,7 @@ unsigned int ez_hash_string(const char *s) { while (*s) //hash = (*s++) + (hash << 5) + hash; hash = hash * 33 + (*s++); - + return hash; } diff --git a/ez-set.h b/ez-set.h index d453db0..beacf76 100644 --- a/ez-set.h +++ b/ez-set.h @@ -59,6 +59,13 @@ struct ez_set { void (*free)(void *); }; +/** + * Static initialiser for a set. + * + * struct ez_set set = EZ_INIT_SET(set, hash, equals, free); + */ +#define EZ_INIT_SET(s, shash, sequals, sfree) { .hash = shash, .equals = sequals, .free = sfree } + /** * State data for iterator. */ @@ -70,21 +77,14 @@ struct ez_set_scan { }; /** - * Create a new set. + * Initialises an empty set. * - * @param h uninitialised set. + * @param set uninitialised set. * @param hash function which hashes entries. * @param equals function which compares entries for equality. * @param efree used to free nodes. May be null. */ -ez_set *ez_set_new(unsigned int (*hash)(const void *), int (*equals)(const void *, const void *), void (*efree)(void *)); - -/** - * Free the set. - * - * The set will be cleared first. - */ -void ez_set_free(ez_set *h); +void ez_set_init(ez_set *set, unsigned int (*hash)(const void *), int (*equals)(const void *, const void *), void (*efree)(void *)); /** * Clear all entries and reset the internal size. diff --git a/test-set.c b/test-set.c index 32b210a..5f5cbb0 100644 --- a/test-set.c +++ b/test-set.c @@ -31,20 +31,36 @@ static void entry_free(void *d) { free(a); } -int main(int argc, char **argv) { +static int load_words(ez_set *set) { FILE *fp = fopen("/usr/share/dict/words", "r"); char word[256]; - ez_set *set; int count = 0; - set = ez_set_new(entry_hash, entry_equals, entry_free); - - while (fgets(word, 256, fp)) { - size_t len = strlen(word); - if (len > 0) { + if (!fp) + fp = fopen("words", "r"); + + if (fp) { + while (fgets(word, 256, fp)) { + size_t len = strlen(word); + if (len > 0) { + struct entry *e = malloc(sizeof(*e)); + + word[len-1] = 0; + e->value = strdup(word); + + e = ez_set_put(set, e); + if (e) { + printf("duplicate! %s\n", e->value); + } + count += 1; + } + } + fclose(fp); + } else { + for (int i=0;i<10000;i++) { struct entry *e = malloc(sizeof(*e)); - word[len-1] = 0; + sprintf(word, "%x", i*7); e->value = strdup(word); e = ez_set_put(set, e); @@ -54,7 +70,18 @@ int main(int argc, char **argv) { count += 1; } } - fclose(fp); + + return count; +} + +int main(int argc, char **argv) { + ez_set setv, *set; + int count; + + ez_set_init(&setv, entry_hash, entry_equals, entry_free); + set = &setv; + + count = load_words(set); // calc some stats int min = 1000, max = 0; @@ -98,7 +125,7 @@ int main(int argc, char **argv) { e = ez_set_get(set, &key); printf("lookup %s = %p %s\n", key.value, e, e ? e->value : ""); } - + ez_set_scan scan; // iterate @@ -111,8 +138,9 @@ int main(int argc, char **argv) { printf("set_clear\n"); ez_set_clear(set); printf(" size %d\n", ez_set_size(set)); -#if 0 - + + count = load_words(set); + // iterate and clear all struct entry *e; e = ez_set_scan_init(set, &scan); @@ -124,13 +152,11 @@ int main(int argc, char **argv) { rcount ++; //printf(" %s\n", p->value); - + free(p->value); free(p); } - printf("size %d rcount %d\n", ez_set_size(set), rcount); -#endif + printf("size %d remove count %d\n", ez_set_size(set), rcount); - ez_set_free(set); + ez_set_clear(set); } - -- 2.39.5