1/* 2 * This program is free software; you can redistribute it and/or 3 * modify it under the terms of the GNU General Public License as 4 * published by the Free Software Foundation; either version 2 of 5 * the License, or (at your option) any later version. 6 * 7 * This program is distributed in the hope that it will be useful, 8 * but WITHOUT ANY WARRANTY; without even the implied warranty of 9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 10 * GNU General Public License for more details. 11 * 12 * You should have received a copy of the GNU General Public License 13 * along with this program; if not, write to the Free Software 14 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, 15 * MA 02111-1307 USA 16 */ 17/* 18 * Part of Very Secure FTPd 19 * Licence: GPL v2 20 * Author: Chris Evans 21 * hash.c 22 * 23 * Routines to handle simple hash table lookups and modifications. 24 */ 25 26#include "hash.h" 27#include "sysutil.h" 28#include "utility.h" 29 30struct hash_node 31{ 32 void* p_key; 33 void* p_value; 34 struct hash_node* p_prev; 35 struct hash_node* p_next; 36}; 37 38struct hash 39{ 40 unsigned int buckets; 41 unsigned int key_size; 42 unsigned int value_size; 43 hashfunc_t hash_func; 44 struct hash_node** p_nodes; 45}; 46 47/* Internal functions */ 48struct hash_node** hash_get_bucket(struct hash* p_hash, void* p_key); 49struct hash_node* hash_get_node_by_key(struct hash* p_hash, void* p_key); 50 51struct hash* 52hash_alloc(unsigned int buckets, unsigned int key_size, 53 unsigned int value_size, hashfunc_t hash_func) 54{ 55 unsigned int size; 56 struct hash* p_hash = vsf_sysutil_malloc(sizeof(*p_hash)); 57 p_hash->buckets = buckets; 58 p_hash->key_size = key_size; 59 p_hash->value_size = value_size; 60 p_hash->hash_func = hash_func; 61 size = sizeof(struct hash_node*) * buckets; 62 p_hash->p_nodes = vsf_sysutil_malloc(size); 63 vsf_sysutil_memclr(p_hash->p_nodes, size); 64 return p_hash; 65} 66 67void* 68hash_lookup_entry(struct hash* p_hash, void* p_key) 69{ 70 struct hash_node* p_node = hash_get_node_by_key(p_hash, p_key); 71 if (!p_node) 72 { 73 return p_node; 74 } 75 return p_node->p_value; 76} 77 78void 79hash_add_entry(struct hash* p_hash, void* p_key, void* p_value) 80{ 81 struct hash_node** p_bucket; 82 struct hash_node* p_new_node; 83 if (hash_lookup_entry(p_hash, p_key)) 84 { 85 bug("duplicate hash key"); 86 } 87 p_bucket = hash_get_bucket(p_hash, p_key); 88 p_new_node = vsf_sysutil_malloc(sizeof(*p_new_node)); 89 p_new_node->p_prev = 0; 90 p_new_node->p_next = 0; 91 p_new_node->p_key = vsf_sysutil_malloc(p_hash->key_size); 92 vsf_sysutil_memcpy(p_new_node->p_key, p_key, p_hash->key_size); 93 p_new_node->p_value = vsf_sysutil_malloc(p_hash->value_size); 94 vsf_sysutil_memcpy(p_new_node->p_value, p_value, p_hash->value_size); 95 96 if (!*p_bucket) 97 { 98 *p_bucket = p_new_node; 99 } 100 else 101 { 102 p_new_node->p_next = *p_bucket; 103 (*p_bucket)->p_prev = p_new_node; 104 *p_bucket = p_new_node; 105 } 106} 107 108void 109hash_free_entry(struct hash* p_hash, void* p_key) 110{ 111 struct hash_node* p_node = hash_get_node_by_key(p_hash, p_key); 112 if (!p_node) 113 { 114 bug("hash node not found"); 115 } 116 vsf_sysutil_free(p_node->p_key); 117 vsf_sysutil_free(p_node->p_value); 118 119 if (p_node->p_prev) 120 { 121 p_node->p_prev->p_next = p_node->p_next; 122 } 123 else 124 { 125 struct hash_node** p_bucket = hash_get_bucket(p_hash, p_key); 126 *p_bucket = p_node->p_next; 127 } 128 if (p_node->p_next) 129 { 130 p_node->p_next->p_prev = p_node->p_prev; 131 } 132 133 vsf_sysutil_free(p_node); 134} 135 136struct hash_node** 137hash_get_bucket(struct hash* p_hash, void* p_key) 138{ 139 unsigned int bucket = (*p_hash->hash_func)(p_hash->buckets, p_key); 140 if (bucket >= p_hash->buckets) 141 { 142 bug("bad bucket lookup"); 143 } 144 return &(p_hash->p_nodes[bucket]); 145} 146 147struct hash_node* 148hash_get_node_by_key(struct hash* p_hash, void* p_key) 149{ 150 struct hash_node** p_bucket = hash_get_bucket(p_hash, p_key); 151 struct hash_node* p_node = *p_bucket; 152 if (!p_node) 153 { 154 return p_node; 155 } 156 while (p_node != 0 && 157 vsf_sysutil_memcmp(p_key, p_node->p_key, p_hash->key_size) != 0) 158 { 159 p_node = p_node->p_next; 160 } 161 return p_node; 162} 163 164