User:Ledrug/bits

<lang c>#include <stdio.h>

1. include <stdlib.h>
2. include <stdint.h>
3. include <string.h>

typedef uint32_t hash_t;

typedef struct hash_value_t { void *data; char *key; struct hash_value_t *chain; } hash_value_t;

typedef struct hash_table_t { hash_value_t **v, *pool; size_t n, cap; } hash_table_t, *htbl;

inline hash_t hash(char *s) { hash_t hash; for (hash = 0; *s; s++) { hash += *s; hash += (hash << 10); hash ^= (hash >> 6); } hash += hash << 3; hash ^= hash >> 11; hash += hash << 15; return hash; }

htbl hash_new(size_t size) { htbl h = calloc(1, sizeof(hash_table_t)); if (!size) size = 4;

for (h->cap = 1; h->cap < size; h->cap <<= 1);

h->v = calloc(h->cap, sizeof(hash_value_t*)); h->pool = 0; return h; }

hash_value_t *hash_get_storage(htbl t) { size_t len; hash_value_t *p = t->pool; if (!p) { len = 1024; if (len > t->cap) len = t->cap; t->pool = calloc(len, sizeof(hash_value_t)); for (p = t->pool; len > 1; len --) p->chain = p + 1; p = t->pool; } t->pool = p->chain; return p; }

void hash_insert_node(htbl t, hash_value_t *p) { size_t idx = hash(p->key) % t->cap; p->chain = t->v[idx]; t->v[idx] = p; }

void hash_expand(htbl t) { size_t i, c = t->cap; hash_value_t *p, *tmp;

t->v = realloc(t->v, sizeof(hash_value_t*) * c * 2); memset(t->v + c, 0, c * sizeof(hash_table_t*));

t->cap *= 2; for (i = 0; i < c; i++) { p = t->v[i]; if (!p) continue;

t->v[i] = 0; while (p) { tmp = p->chain; p->chain = 0; hash_insert_node(t, p); p = tmp; } } }

void hash_insert(htbl t, char *s, void *data) { hash_value_t *p = hash_get_storage(t); if (t->n * 5 >= t->cap * 4) hash_expand(t); p->key = strdup(s); p->data = data; hash_insert_node(t, p); t->n ++; }

void* hash_remove(htbl t, char *s) { size_t idx = hash(s) % t->cap; hash_value_t *head = 0, *p = t->v[idx];

while (p) { if (!strcmp(p->key, s)) break; head = p; p = p->chain; } if (!p) return 0;

free(p->key);

if (head) head->chain = p->chain; else t->v[idx] = p->chain;

p->chain = t->pool; t->pool = p; t->n--; return p->data; }

void* hash_lookup(htbl t, char *s) { size_t idx = hash(s) % t->cap; hash_value_t *p; p = t->v[idx]; while (p) { if (!strcmp(p->key, s)) return p->data; p = p->chain; } return (void*)-1; }</lang>