1/* 2 * Part of Very Secure FTPd 3 * Licence: GPL v2 4 * Author: Chris Evans 5 * hash.c 6 * 7 * Routines to handle simple hash table lookups and modifications. 8 */ 9 10#include "hash.h" 11#include "sysutil.h" 12#include "utility.h" 13 14struct hash_node 15{ 16 void* p_key; 17 void* p_value; 18 struct hash_node* p_prev; 19 struct hash_node* p_next; 20}; 21 22struct hash 23{ 24 unsigned int buckets; 25 unsigned int key_size; 26 unsigned int value_size; 27 hashfunc_t hash_func; 28 struct hash_node** p_nodes; 29}; 30 31/* Internal functions */ 32struct hash_node** hash_get_bucket(struct hash* p_hash, void* p_key); 33struct hash_node* hash_get_node_by_key(struct hash* p_hash, void* p_key); 34 35struct hash* 36hash_alloc(unsigned int buckets, unsigned int key_size, 37 unsigned int value_size, hashfunc_t hash_func) 38{ 39 unsigned int size; 40 struct hash* p_hash = vsf_sysutil_malloc(sizeof(*p_hash)); 41 p_hash->buckets = buckets; 42 p_hash->key_size = key_size; 43 p_hash->value_size = value_size; 44 p_hash->hash_func = hash_func; 45 size = sizeof(struct hash_node*) * buckets; 46 p_hash->p_nodes = vsf_sysutil_malloc(size); 47 vsf_sysutil_memclr(p_hash->p_nodes, size); 48 return p_hash; 49} 50 51void* 52hash_lookup_entry(struct hash* p_hash, void* p_key) 53{ 54 struct hash_node* p_node = hash_get_node_by_key(p_hash, p_key); 55 if (!p_node) 56 { 57 return p_node; 58 } 59 return p_node->p_value; 60} 61 62void 63hash_add_entry(struct hash* p_hash, void* p_key, void* p_value) 64{ 65 struct hash_node** p_bucket; 66 struct hash_node* p_new_node; 67 if (hash_lookup_entry(p_hash, p_key)) 68 { 69 bug("duplicate hash key"); 70 } 71 p_bucket = hash_get_bucket(p_hash, p_key); 72 p_new_node = vsf_sysutil_malloc(sizeof(*p_new_node)); 73 p_new_node->p_prev = 0; 74 p_new_node->p_next = 0; 75 p_new_node->p_key = vsf_sysutil_malloc(p_hash->key_size); 76 vsf_sysutil_memcpy(p_new_node->p_key, p_key, p_hash->key_size); 77 p_new_node->p_value = vsf_sysutil_malloc(p_hash->value_size); 78 vsf_sysutil_memcpy(p_new_node->p_value, p_value, p_hash->value_size); 79 80 if (!*p_bucket) 81 { 82 *p_bucket = p_new_node; 83 } 84 else 85 { 86 p_new_node->p_next = *p_bucket; 87 (*p_bucket)->p_prev = p_new_node; 88 *p_bucket = p_new_node; 89 } 90} 91 92void 93hash_free_entry(struct hash* p_hash, void* p_key) 94{ 95 struct hash_node* p_node = hash_get_node_by_key(p_hash, p_key); 96 if (!p_node) 97 { 98 bug("hash node not found"); 99 } 100 vsf_sysutil_free(p_node->p_key); 101 vsf_sysutil_free(p_node->p_value); 102 103 if (p_node->p_prev) 104 { 105 p_node->p_prev->p_next = p_node->p_next; 106 } 107 else 108 { 109 struct hash_node** p_bucket = hash_get_bucket(p_hash, p_key); 110 *p_bucket = p_node->p_next; 111 } 112 if (p_node->p_next) 113 { 114 p_node->p_next->p_prev = p_node->p_prev; 115 } 116 117 vsf_sysutil_free(p_node); 118} 119 120struct hash_node** 121hash_get_bucket(struct hash* p_hash, void* p_key) 122{ 123 unsigned int bucket = (*p_hash->hash_func)(p_hash->buckets, p_key); 124 if (bucket >= p_hash->buckets) 125 { 126 bug("bad bucket lookup"); 127 } 128 return &(p_hash->p_nodes[bucket]); 129} 130 131struct hash_node* 132hash_get_node_by_key(struct hash* p_hash, void* p_key) 133{ 134 struct hash_node** p_bucket = hash_get_bucket(p_hash, p_key); 135 struct hash_node* p_node = *p_bucket; 136 if (!p_node) 137 { 138 return p_node; 139 } 140 while (p_node != 0 && 141 vsf_sysutil_memcmp(p_key, p_node->p_key, p_hash->key_size) != 0) 142 { 143 p_node = p_node->p_next; 144 } 145 return p_node; 146} 147 148