int hash_string(const unsigned char *s, int n)
{
- int h = 0;
+ unsigned h = 0;
while (*s) {
h += (h << 7) + *s++;
}
- h = (h * SOMEPRIME) % n;
- h = (h >= 0) ? h : h + n;
- return (h % n);
+ return (h * SOMEPRIME) % n;
}
-HASH *hash_create(int nelem)
+hash_t *hash_init(hash_t *table, int nelem, int allow_dup)
{
- HASH *table = p_new(HASH, 1);
-
- if (nelem == 0)
- nelem = 2;
-
- table->nelem = nelem;
+ table->dupes = allow_dup;
+ table->nelem = MAX(nelem, 2);
table->curnelem = 0;
- table->table = p_new(struct hash_elem *, nelem);
+ table->table = p_new(struct hash_elem *, table->nelem);
return table;
}
-HASH *hash_resize(HASH *ptr, int nelem)
+/* ptr pointer to the hash table to be freed
+ * destroy() function to call to free the ->data member (optional)
+ */
+void hash_wipe(hash_t *h, void (*dtor)(void *))
+{
+ int i;
+
+ for (i = 0; i < h->nelem; i++) {
+ struct hash_elem *elem, *tmp;
+
+ for (elem = h->table[i]; elem;) {
+ tmp = elem;
+ elem = elem->next;
+ if (dtor)
+ dtor(tmp->data);
+ p_delete(&tmp);
+ }
+ }
+ p_delete(&h->table);
+}
+
+void hash_resize(hash_t *ptr, int nelem)
{
- HASH *table;
- struct hash_elem *elem, *tmp;
+ hash_t table;
int i;
- table = hash_create (nelem);
+ /* XXX hack: we know the has was correct, no dupe checks is fater */
+ hash_init(&table, nelem, 1);
for (i = 0; i < ptr->nelem; i++) {
+ struct hash_elem *elem, *tmp;
for (elem = ptr->table[i]; elem;) {
tmp = elem;
elem = elem->next;
- hash_insert(table, tmp->key, tmp->data, 1);
+ hash_insert(&table, tmp->key, tmp->data);
p_delete(&tmp);
}
}
- p_delete(&ptr->table);
- p_delete(&ptr);
- return table;
+ p_delete(&ptr->table);
+ ptr->nelem = table.nelem;
+ ptr->table = table.table;
}
/* table hash table to update
* data data to associate with `key'
* allow_dup if nonzero, duplicate keys are allowed in the table
*/
-int hash_insert(HASH *table, const char *key, void *data, int allow_dup)
+int hash_insert(hash_t *table, const char *key, void *data)
{
struct hash_elem *ptr;
int h;
ptr->key = key;
ptr->data = data;
- if (allow_dup) {
+ if (table->dupes) {
ptr->next = table->table[h];
table->table[h] = ptr;
table->curnelem++;
} else {
- struct hash_elem *tmp, *last;
- int r;
+ struct hash_elem **e;
+
+ for (e = &table->table[h]; *e; e = &(*e)->next) {
+ int r = m_strcmp((*e)->key, key);
- for (tmp = table->table[h], last = NULL; tmp; last = tmp, tmp = tmp->next) {
- r = m_strcmp(tmp->key, key);
if (r == 0) {
p_delete(&ptr);
return (-1);
if (r > 0)
break;
}
- if (last) {
- last->next = ptr;
- } else {
- table->table[h] = ptr;
- }
- ptr->next = tmp;
+ ptr->next = *e;
+ *e = ptr;
table->curnelem++;
}
return h;
}
-void *hash_find_hash(const HASH *table, int hash, const char *key)
+void *hash_find(const hash_t *table, const char *key)
{
+ int hash = hash_string((unsigned char*)key, table->nelem);
struct hash_elem *ptr;
for (ptr = table->table[hash]; ptr; ptr = ptr->next) {
return NULL;
}
-void hash_delete_hash(HASH *table, int hash, const char *key, const void *data,
- void (*destroy)(void *))
+void hash_remove(hash_t *table, const char *key, const void *data,
+ void (*destroy)(void *))
{
+ int hash = hash_string((unsigned char*)key, table->nelem);
struct hash_elem *ptr = table->table[hash];
struct hash_elem **last = &table->table[hash];
}
}
-/* ptr pointer to the hash table to be freed
- * destroy() function to call to free the ->data member (optional)
- */
-void hash_destroy(HASH **ptr, void (*destroy)(void *))
-{
- int i;
- HASH *pptr = *ptr;
- struct hash_elem *elem, *tmp;
-
- for (i = 0; i < pptr->nelem; i++) {
- for (elem = pptr->table[i]; elem;) {
- tmp = elem;
- elem = elem->next;
- if (destroy)
- destroy (tmp->data);
- p_delete(&tmp);
- }
- }
- p_delete(&pptr->table);
- p_delete(ptr);
-}
-
-void hash_map(HASH *table,
+void hash_map(hash_t *table,
void (*mapfunc)(const char* key, void* data, unsigned long more),
unsigned long more)
{