Anonymous user
User:Ledrug/bits: Difference between revisions
m
no edit summary
mNo edit summary |
mNo edit summary |
||
Line 1:
<lang c>#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#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)
{
hash_value_t *p = t->pool;
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;
t->v[idx] = p;
}
void hash_expand(htbl t)
{
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;
}
}
}
{
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)
{
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>
|