| |
| |
| |
| |
| |
| |
| |
| |
| |
| #include "hash.h" |
| #include "sysutil.h" |
| #include "utility.h" |
| |
| struct hash_node |
| { |
| void* p_key; |
| void* p_value; |
| struct hash_node* p_prev; |
| struct hash_node* p_next; |
| }; |
| |
| struct hash |
| { |
| unsigned int buckets; |
| unsigned int key_size; |
| unsigned int value_size; |
| hashfunc_t hash_func; |
| struct hash_node** p_nodes; |
| }; |
| |
| |
| struct hash_node** hash_get_bucket(struct hash* p_hash, void* p_key); |
| struct hash_node* hash_get_node_by_key(struct hash* p_hash, void* p_key); |
| |
| struct hash* |
| hash_alloc(unsigned int buckets, unsigned int key_size, |
| unsigned int value_size, hashfunc_t hash_func) |
| { |
| unsigned int size; |
| struct hash* p_hash = vsf_sysutil_malloc(sizeof(*p_hash)); |
| p_hash->buckets = buckets; |
| p_hash->key_size = key_size; |
| p_hash->value_size = value_size; |
| p_hash->hash_func = hash_func; |
| size = (unsigned int) sizeof(struct hash_node*) * buckets; |
| p_hash->p_nodes = vsf_sysutil_malloc(size); |
| vsf_sysutil_memclr(p_hash->p_nodes, size); |
| return p_hash; |
| } |
| |
| void* |
| hash_lookup_entry(struct hash* p_hash, void* p_key) |
| { |
| struct hash_node* p_node = hash_get_node_by_key(p_hash, p_key); |
| if (!p_node) |
| { |
| return p_node; |
| } |
| return p_node->p_value; |
| } |
| |
| void |
| hash_add_entry(struct hash* p_hash, void* p_key, void* p_value) |
| { |
| struct hash_node** p_bucket; |
| struct hash_node* p_new_node; |
| if (hash_lookup_entry(p_hash, p_key)) |
| { |
| bug("duplicate hash key"); |
| } |
| p_bucket = hash_get_bucket(p_hash, p_key); |
| p_new_node = vsf_sysutil_malloc(sizeof(*p_new_node)); |
| p_new_node->p_prev = 0; |
| p_new_node->p_next = 0; |
| p_new_node->p_key = vsf_sysutil_malloc(p_hash->key_size); |
| vsf_sysutil_memcpy(p_new_node->p_key, p_key, p_hash->key_size); |
| p_new_node->p_value = vsf_sysutil_malloc(p_hash->value_size); |
| vsf_sysutil_memcpy(p_new_node->p_value, p_value, p_hash->value_size); |
| |
| if (!*p_bucket) |
| { |
| *p_bucket = p_new_node; |
| } |
| else |
| { |
| p_new_node->p_next = *p_bucket; |
| (*p_bucket)->p_prev = p_new_node; |
| *p_bucket = p_new_node; |
| } |
| } |
| |
| void |
| hash_free_entry(struct hash* p_hash, void* p_key) |
| { |
| struct hash_node* p_node = hash_get_node_by_key(p_hash, p_key); |
| if (!p_node) |
| { |
| bug("hash node not found"); |
| } |
| vsf_sysutil_free(p_node->p_key); |
| vsf_sysutil_free(p_node->p_value); |
| |
| if (p_node->p_prev) |
| { |
| p_node->p_prev->p_next = p_node->p_next; |
| } |
| else |
| { |
| struct hash_node** p_bucket = hash_get_bucket(p_hash, p_key); |
| *p_bucket = p_node->p_next; |
| } |
| if (p_node->p_next) |
| { |
| p_node->p_next->p_prev = p_node->p_prev; |
| } |
| |
| vsf_sysutil_free(p_node); |
| } |
| |
| struct hash_node** |
| hash_get_bucket(struct hash* p_hash, void* p_key) |
| { |
| unsigned int bucket = (*p_hash->hash_func)(p_hash->buckets, p_key); |
| if (bucket >= p_hash->buckets) |
| { |
| bug("bad bucket lookup"); |
| } |
| return &(p_hash->p_nodes[bucket]); |
| } |
| |
| struct hash_node* |
| hash_get_node_by_key(struct hash* p_hash, void* p_key) |
| { |
| struct hash_node** p_bucket = hash_get_bucket(p_hash, p_key); |
| struct hash_node* p_node = *p_bucket; |
| if (!p_node) |
| { |
| return p_node; |
| } |
| while (p_node != 0 && |
| vsf_sysutil_memcmp(p_key, p_node->p_key, p_hash->key_size) != 0) |
| { |
| p_node = p_node->p_next; |
| } |
| return p_node; |
| } |
| |