diff options
Diffstat (limited to 'src/htgen.h')
| -rw-r--r-- | src/htgen.h | 131 |
1 files changed, 127 insertions, 4 deletions
diff --git a/src/htgen.h b/src/htgen.h index c12ed71..9101e01 100644 --- a/src/htgen.h +++ b/src/htgen.h @@ -21,6 +21,8 @@ /* #define HT_VAL_STATIC_LEN sizeof(int) */ #define HT_VAL_GUESS_LEN(_val) strlen(_val) + +/* this function shouldn't do anything if it is called with a value of HT_VAL_SENTINEL */ #define HT_VAL_FREE(_val) free(_val) #define HT_VAL_SENTINEL NULL @@ -29,7 +31,7 @@ #define HT_KEYTYPE_CREF const char * /* will receive two HT_KEYTYPEs */ -/* bad equality function LOL */ +/* bad equality function LOL (shouldn't use strcmp) */ #define HT_KEY_EQ(_val1, _len1, _val2, _len2) (((_len1) == (_len2)) && !strcmp(_val1, _val2)) #define HT_KEY_COPY(_key, _sz) (strdup(_key)) @@ -118,8 +120,11 @@ HT_VALTYPE HT__NS(getn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, bool * int HT__NS(put)(HT__TYPE *ht, HT_KEYTYPE_CREF key, HT_VALTYPE_CREF val); int HT__NS(putn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, HT_VALTYPE_CREF val, size_t vallen); -HT_VALTYPE HT__NS(swap)(HT__TYPE *ht, HT_KEYTYPE_CREF key, HT_VALTYPE_CREF val); -HT_VALTYPE HT__NS(swapn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, HT_VALTYPE_CREF val, size_t *vallen); +int HT__NS(remove)(HT__TYPE *ht, HT_KEYTYPE_CREF key); +int HT__NS(removen)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen); + +HT_VALTYPE HT__NS(pop)(HT__TYPE *ht, HT_KEYTYPE_CREF key, bool *found); +HT_VALTYPE HT__NS(popn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, bool *found); /* implementations */ @@ -275,6 +280,8 @@ void HT__NS(clear)(HT__TYPE *ht) ht->asize = ht->rsize = 0; } +#define HT__KEY_MATCH_EXACT(_node, _hash, _key, _keylen) (((_node)->hash == (_hash)) && (HT_KEY_EQ((_node)->key, HT__NODE_KEYLEN(_node), _key, _keylen))) + HT__NODE *HT__NS(_search)(HT__NODE *table, size_t tablecap, const HT__HASHTYPE hash, HT_KEYTYPE_CREF key, size_t keylen, bool vacant) { size_t tryidx = (size_t)((uintmax_t)hash % tablecap); @@ -287,7 +294,7 @@ HT__NODE *HT__NS(_search)(HT__NODE *table, size_t tablecap, const HT__HASHTYPE h do { node = table + tryidx; - if (node->full && !node->deleted && node->hash == hash && HT_KEY_EQ(node->key, HT__NODE_KEYLEN(node), key, keylen)) { + if (node->full && !node->deleted && HT__KEY_MATCH_EXACT(node, hash, key, keylen)) { fprintf(stderr, "found node %zu: matches\n", tryidx); return node; } @@ -305,6 +312,50 @@ HT__NODE *HT__NS(_search)(HT__NODE *table, size_t tablecap, const HT__HASHTYPE h return NULL; } +HT__NODE *HT__NS(_search_ahead)(HT__NODE *table, HT__NODE *start, size_t tablecap, const HT__HASHTYPE hash, HT_KEYTYPE_CREF key, size_t keylen) +{ + size_t startidx = (size_t)((uintmax_t)hash % tablecap); + size_t tryidx = ((start - table) + 1) % tablecap; + + HT__NODE *node; + + do { + node = table + tryidx; + + if (!node->full) return NULL; + + if (!node->deleted && HT__KEY_MATCH_EXACT(node, hash, key, keylen)) { + return node; + } + + tryidx = (tryidx + 1) % tablecap; + } while (tryidx != startidx); + + return NULL; +} + +int HT__NS(_node_erase)(HT__TYPE *ht, HT__NODE *node) +{ + if (!node->full || node->deleted) return 0; + node->deleted = true; + --ht->asize; + + HT_KEY_FREE(node->key); + HT_VAL_FREE(node->val); + + return 1; +} + +void HT__NS(_search_ahead_erase)(HT__TYPE *ht, HT__NODE *start) +{ + HT__NODE *found = HT__NS(_search_ahead)(ht->table, start, ht->capacity, start->hash, start->key, start->keylen); + if (!found) { + return; + } + + HT__NS(_node_erase)(ht, found); +} + int HT__NS(_node_set)(HT__TYPE *ht, HT__NODE *node, const HT__HASHTYPE hash, HT_KEYTYPE_CREF key, size_t keylen, HT_VALTYPE_CREF val, size_t vallen) { if (node->full) { @@ -336,6 +387,8 @@ int HT__NS(_node_set)(HT__TYPE *ht, HT__NODE *node, const HT__HASHTYPE hash, HT_ node->deleted = false; /* node is now filled */ ++ht->asize; + + HT__NS(_search_ahead_erase)(ht, node); return 0; } @@ -438,6 +491,48 @@ HT_VALTYPE HT__NS(getn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, bool * return node->val; } +int HT__NS(remove)(HT__TYPE *ht, HT_KEYTYPE_CREF key) +{ + return HT__NS(removen)(ht, key, 0); +} + +int HT__NS(removen)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen) +{ + if (!keylen) keylen = HT__GUESS_KEYLEN(key); + + const HT__HASHTYPE hash = HT_KEY_HASH(key, keylen); + HT__NODE *node = HT__NS(_search)(ht->table, ht->capacity, hash, key, keylen, false); + + if (!node) return 0; + + return HT__NS(_node_erase)(ht, node); +} + +HT_VALTYPE HT__NS(pop)(HT__TYPE *ht, HT_KEYTYPE_CREF key, bool *found) +{ + return HT__NS(popn)(ht, key, 0, found); +} + +HT_VALTYPE HT__NS(popn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, bool *found) +{ + if (!keylen) keylen = HT__GUESS_KEYLEN(key); + + const HT__HASHTYPE hash = HT_KEY_HASH(key, keylen); + HT__NODE *node = HT__NS(_search)(ht->table, ht->capacity, hash, key, keylen, false); + + if (!node) { + if (found) *found = false; + return NULL; + } + + if (found) *found = true; + + HT_VALTYPE val = node->val; + node->val = HT_VAL_SENTINEL; + HT__NS(_node_erase)(ht, node); + return val; +} + void HT__NS(_debug_table)(HT__TYPE *ht) { fprintf(stderr, HT__STR(HT__TYPE) " debug: cap: %zu, asize: %zu, rsize: %zu, lf: %f\n", @@ -458,3 +553,31 @@ void HT__NS(_debug_table)(HT__TYPE *ht) } #endif + +/* undefine all of the configuration parameters */ + +#undef HT_PREFIX +#undef HT_VALTYPE +#undef HT_VALTYPE_CREF + +#undef HT_HASHTYPE +#undef HT_KEY_HASH + +#undef HT_VAL_COPY +#undef HT_VAL_STATIC_LEN +#undef HT_VAL_GUESS_LEN + +#undef HT_VAL_FREE +#undef HT_VAL_SENTINEL + +#undef HT_KEYTYPE +#undef HT_KEYTYPE_CREF +#undef HT_KEY_EQ +#undef HT_KEY_COPY +#undef HT_KEY_FREE + +#undef HT_KEY_STATIC_LEN +#undef HT_KEY_GUESS_LEN + +#undef HT_KEY_FMT +#undef HT_VAL_FMT |