From 336fc48784469029365f066d860e1e932d35fa6b Mon Sep 17 00:00:00 2001 From: David Given Date: Sat, 17 Dec 2016 20:22:20 +0100 Subject: [PATCH] Replace smap with string-based hashtables; add some boilerplate to make sets and hashtables of strings easier to use. --- modules/src/data/hashtable.c | 20 ++++++++++ modules/src/data/hashtable.h | 8 +++- modules/src/data/set.h | 3 ++ modules/src/data/smap.c | 74 ------------------------------------ modules/src/data/smap.h | 31 --------------- util/mcgg/registers.c | 57 ++++++++++++++++++--------- 6 files changed, 69 insertions(+), 124 deletions(-) delete mode 100644 modules/src/data/smap.c delete mode 100644 modules/src/data/smap.h diff --git a/modules/src/data/hashtable.c b/modules/src/data/hashtable.c index b76df03b8..f11882528 100644 --- a/modules/src/data/hashtable.c +++ b/modules/src/data/hashtable.c @@ -1,6 +1,7 @@ #include #include #include +#include #include "hashtable.h" struct hashnode @@ -22,6 +23,25 @@ bool standard_pointer_comparison_function(void* key1, void* key2) return (key1 == key2); } +uint32_t standard_string_hash_function(void* key) +{ + char* s = key; + uint32_t hash = 0; + + while (*s) + { + hash = ((hash << 5) + hash) ^ *s; + s++; + } + + return hash; +} + +bool standard_string_comparison_function(void* key1, void* key2) +{ + return strcmp(key1, key2) == 0; +} + static void lazy_init(struct hashtable* ht) { if (!ht->num_buckets) diff --git a/modules/src/data/hashtable.h b/modules/src/data/hashtable.h index f5617b3f5..bdcf600ef 100644 --- a/modules/src/data/hashtable.h +++ b/modules/src/data/hashtable.h @@ -9,15 +9,21 @@ typedef bool cmpfunction_t(void* key1, void* key2); extern uint32_t standard_pointer_hash_function(void* key); extern bool standard_pointer_comparison_function(void* key1, void* key2); +extern uint32_t standard_string_hash_function(void* key); +extern bool standard_string_comparison_function(void* key1, void* key2); + struct hashtable { - unsigned int num_buckets; /* power of 2 */ hashfunction_t* hashfunction; cmpfunction_t* cmpfunction; + unsigned int num_buckets; /* power of 2 */ struct hashnode** buckets; int size; }; +#define HASHTABLE_OF_STRINGS \ + { standard_string_hash_function, standard_string_comparison_function } + struct hashtable_iterator { /* Public */ diff --git a/modules/src/data/set.h b/modules/src/data/set.h index 5069ca0f1..6d0322903 100644 --- a/modules/src/data/set.h +++ b/modules/src/data/set.h @@ -10,6 +10,9 @@ struct set struct hashtable table; }; +#define SET_OF_STRINGS \ + { HASHTABLE_OF_STRINGS } + extern void set_empty(struct set* s); extern void set_reset(struct set* s); diff --git a/modules/src/data/smap.c b/modules/src/data/smap.c deleted file mode 100644 index 312241a20..000000000 --- a/modules/src/data/smap.c +++ /dev/null @@ -1,74 +0,0 @@ -#include -#include -#include -#include "smap.h" - -static void append(void* mapp, const char* left, void* right) -{ - struct smap* map = mapp; - struct smap_node* node; - - if (map->count == map->max) - { - int newmax = (map->max == 0) ? 8 : (map->max * 2); - struct smap_node* newarray = realloc(map->item, newmax * sizeof(*newarray)); - - map->max = newmax; - map->item = newarray; - } - - node = &map->item[map->count]; - map->count++; - - node->left = left; - node->right = right; -} - -void smap_put(void* mapp, const char* left, void* right) -{ - struct smap* map = mapp; - int i; - - for (i=0; icount; i++) - { - struct smap_node* node = &map->item[i]; - if (strcmp(node->left, left) == 0) - { - node->right = right; - return; - } - } - - append(map, left, right); -} - -void smap_add(void* mapp, const char* left, void* right) -{ - struct smap* map = mapp; - int i; - - for (i=0; icount; i++) - { - struct smap_node* node = &map->item[i]; - if ((strcmp(node->left, left) == 0) && (node->right == right)) - return; - } - - append(map, left, right); -} - -void* smap_get(void* mapp, const char* left) -{ - struct smap* map = mapp; - int i; - - for (i=0; icount; i++) - { - struct smap_node* node = &map->item[i]; - if (strcmp(node->left, left) == 0) - return node->right; - } - - return NULL; -} - diff --git a/modules/src/data/smap.h b/modules/src/data/smap.h deleted file mode 100644 index 7ccdb51de..000000000 --- a/modules/src/data/smap.h +++ /dev/null @@ -1,31 +0,0 @@ -#ifndef SMAP_H -#define SMAP_H - -struct smap_node -{ - const char* left; - void* right; -}; - -/* Danger, Will Robinson! The type and the macro must be compatible. */ - -struct smap -{ - struct smap_node* item; - int count; - int max; -}; - -#define SMAPOF(RIGHT) \ - struct { \ - struct { const char* left; RIGHT* right; }* item; \ - int count; \ - int max; \ - } - -extern void smap_put(void* map, const char* left, void* right); -extern void smap_add(void* map, const char* left, void* right); -extern void* smap_get(void* map, const char* left); - -#endif - diff --git a/util/mcgg/registers.c b/util/mcgg/registers.c index 6a47514c7..b35a6f940 100644 --- a/util/mcgg/registers.c +++ b/util/mcgg/registers.c @@ -10,13 +10,14 @@ #include "stringlist.h" #include "iburg.h" #include "registers.h" +#include "hashtable.h" -static SMAPOF(struct reg) registers; -static SMAPOF(struct regattr) registerattrs; +static struct hashtable registers = HASHTABLE_OF_STRINGS; +static struct hashtable registerattrs = HASHTABLE_OF_STRINGS; struct reg* makereg(const char* id) { - struct reg* p = smap_get(®isters, id); + struct reg* p = hashtable_get(®isters, (void*)id); static int number = 0; if (p) @@ -25,7 +26,7 @@ struct reg* makereg(const char* id) p->name = id; p->number = number++; array_append(&p->aliases, p); - smap_put(®isters, id, p); + hashtable_put(®isters, (void*)id, p); return p; } @@ -40,12 +41,12 @@ void setregnames(struct reg* reg, struct stringlist* names) struct regattr* findregattr(const char* id) { - return smap_get(®isterattrs, id); + return hashtable_get(®isterattrs, (void*)id); } struct regattr* makeregattr(const char* id) { - struct regattr* p = smap_get(®isterattrs, id); + struct regattr* p = hashtable_get(®isterattrs, (void*)id); static int number = 0; if (p) @@ -53,14 +54,14 @@ struct regattr* makeregattr(const char* id) p = calloc(1, sizeof(*p)); p->name = id; p->number = number++; - smap_put(®isterattrs, id, p); + hashtable_put(®isterattrs, (void*)id, p); return p; } void addregattr(struct reg* reg, const char* id) { - struct regattr* p = smap_get(®isterattrs, id); + struct regattr* p = hashtable_get(®isterattrs, (void*) id); if (!p) p = makeregattr(id); @@ -85,7 +86,7 @@ void addregaliases(struct reg* reg, struct stringlist* aliases) while (f) { - struct reg* r = smap_get(®isters, f->data); + struct reg* r = hashtable_get(®isters, (void*)f->data); if (!r) yyerror("register '%s' is not defined here", f->data); @@ -98,7 +99,7 @@ void addregaliases(struct reg* reg, struct stringlist* aliases) struct regattr* getregattr(const char* id) { - struct regattr* p = smap_get(®isterattrs, id); + struct regattr* p = hashtable_get(®isterattrs, (void*)id); if (!p) yyerror("'%s' is not the name of a register class", id); return p; @@ -107,11 +108,20 @@ struct regattr* getregattr(const char* id) void emitregisterattrs(void) { int i; + struct regattr* regattrs[registerattrs.size]; + struct hashtable_iterator hit = {}; + + while (hashtable_next(®isterattrs, &hit)) + { + struct regattr* rc = hit.value; + assert((rc->number >= 0) && (rc->number < registerattrs.size)); + regattrs[rc->number] = rc; + } print("const char* %Pregister_class_names[] = {\n"); - for (i=0; inumber == i); print("%1\"%s\",\n", rc->name); @@ -124,10 +134,19 @@ void emitregisterattrs(void) void emitregisters(void) { int i, j; + struct reg* regs[registers.size]; + struct hashtable_iterator hit = {}; + + while (hashtable_next(®isters, &hit)) + { + struct reg* r = hit.value; + assert((r->number >= 0) && (r->number < registers.size)); + regs[r->number] = r; + } - for (i=0; iname); for (j=0; jaliases.count; j++) @@ -135,9 +154,9 @@ void emitregisters(void) print("NULL\n};\n"); } - for (i=0; iname); if (r->names) @@ -155,14 +174,16 @@ void emitregisters(void) } print("const struct %Pregister_data %Pregister_data[] = {\n"); - for (i=0; inumber == i); print("%1{ \"%s\", 0x%x, %Pregister_names_%d_%s, %Pregister_aliases_%d_%s },\n", r->name, r->attrs, i, r->name, i, r->name); } + print("%1{ NULL }\n"); print("};\n\n"); } -- 2.34.1