1 /* 2 * Copyright 2003-2004 Brandon Long 3 * All Rights Reserved. 4 * 5 * ClearSilver Templating System 6 * 7 * This code is made available under the terms of the ClearSilver License. 8 * http://www.clearsilver.net/license.hdf 9 * 10 */ 11 12 #include "cs_config.h" 13 14 #include <stdlib.h> 15 #include <string.h> 16 17 #include "neo_misc.h" 18 #include "neo_err.h" 19 #include "neo_hash.h" 20 21 static NEOERR *_hash_resize(NE_HASH *hash); 22 static NE_HASHNODE **_hash_lookup_node (NE_HASH *hash, void *key, UINT32 *hashv); 23 24 NEOERR *ne_hash_init (NE_HASH **hash, NE_HASH_FUNC hash_func, NE_COMP_FUNC comp_func) 25 { 26 NE_HASH *my_hash = NULL; 27 28 my_hash = (NE_HASH *) calloc(1, sizeof(NE_HASH)); 29 if (my_hash == NULL) 30 return nerr_raise(NERR_NOMEM, "Unable to allocate memory for NE_HASH"); 31 32 my_hash->size = 256; 33 my_hash->num = 0; 34 my_hash->hash_func = hash_func; 35 my_hash->comp_func = comp_func; 36 37 my_hash->nodes = (NE_HASHNODE **) calloc (my_hash->size, sizeof(NE_HASHNODE *)); 38 if (my_hash->nodes == NULL) 39 { 40 free(my_hash); 41 return nerr_raise(NERR_NOMEM, "Unable to allocate memory for NE_HASHNODES"); 42 } 43 44 *hash = my_hash; 45 46 return STATUS_OK; 47 } 48 49 void ne_hash_destroy (NE_HASH **hash) 50 { 51 NE_HASH *my_hash; 52 NE_HASHNODE *node, *next; 53 int x; 54 55 if (hash == NULL || *hash == NULL) 56 return; 57 58 my_hash = *hash; 59 60 for (x = 0; x < my_hash->size; x++) 61 { 62 node = my_hash->nodes[x]; 63 while (node) 64 { 65 next = node->next; 66 free(node); 67 node = next; 68 } 69 } 70 free(my_hash->nodes); 71 my_hash->nodes = NULL; 72 free(my_hash); 73 *hash = NULL; 74 } 75 76 NEOERR *ne_hash_insert(NE_HASH *hash, void *key, void *value) 77 { 78 UINT32 hashv; 79 NE_HASHNODE **node; 80 81 node = _hash_lookup_node(hash, key, &hashv); 82 83 if (*node) 84 { 85 (*node)->value = value; 86 } 87 else 88 { 89 *node = (NE_HASHNODE *) malloc(sizeof(NE_HASHNODE)); 90 if (node == NULL) 91 return nerr_raise(NERR_NOMEM, "Unable to allocate NE_HASHNODE"); 92 93 (*node)->hashv = hashv; 94 (*node)->key = key; 95 (*node)->value = value; 96 (*node)->next = NULL; 97 } 98 hash->num++; 99 100 return _hash_resize(hash); 101 } 102 103 void *ne_hash_lookup(NE_HASH *hash, void *key) 104 { 105 NE_HASHNODE *node; 106 107 node = *_hash_lookup_node(hash, key, NULL); 108 109 return (node) ? node->value : NULL; 110 } 111 112 void *ne_hash_remove(NE_HASH *hash, void *key) 113 { 114 NE_HASHNODE **node, *remove; 115 void *value = NULL; 116 117 node = _hash_lookup_node(hash, key, NULL); 118 if (*node) 119 { 120 remove = *node; 121 *node = remove->next; 122 value = remove->value; 123 free(remove); 124 hash->num--; 125 } 126 return value; 127 } 128 129 int ne_hash_has_key(NE_HASH *hash, void *key) 130 { 131 NE_HASHNODE *node; 132 133 node = *_hash_lookup_node(hash, key, NULL); 134 135 if (node) return 1; 136 return 0; 137 } 138 139 void *ne_hash_next(NE_HASH *hash, void **key) 140 { 141 NE_HASHNODE **node = 0; 142 UINT32 hashv, bucket; 143 144 if (*key) 145 { 146 node = _hash_lookup_node(hash, key, NULL); 147 148 if (*node) 149 { 150 bucket = (*node)->hashv & (hash->size - 1); 151 } 152 else 153 { 154 hashv = hash->hash_func(*key); 155 bucket = hashv & (hash->size - 1); 156 } 157 } 158 else 159 { 160 bucket = 0; 161 } 162 163 if (*node) 164 { 165 if ((*node)->next) 166 { 167 *key = (*node)->next->key; 168 return (*node)->next->value; 169 } 170 bucket++; 171 } 172 173 while (bucket < hash->size) 174 { 175 if (hash->nodes[bucket]) 176 { 177 *key = hash->nodes[bucket]->key; 178 return hash->nodes[bucket]->value; 179 } 180 bucket++; 181 } 182 183 return NULL; 184 } 185 186 static NE_HASHNODE **_hash_lookup_node (NE_HASH *hash, void *key, UINT32 *o_hashv) 187 { 188 UINT32 hashv, bucket; 189 NE_HASHNODE **node; 190 191 hashv = hash->hash_func(key); 192 if (o_hashv) *o_hashv = hashv; 193 bucket = hashv & (hash->size - 1); 194 /* ne_warn("Lookup %s %d %d", key, hashv, bucket); */ 195 196 node = &(hash->nodes[bucket]); 197 198 if (hash->comp_func) 199 { 200 while (*node && !(hash->comp_func((*node)->key, key))) 201 node = &(*node)->next; 202 } 203 else 204 { 205 /* No comp_func means we're doing pointer comparisons */ 206 while (*node && (*node)->key != key) 207 node = &(*node)->next; 208 } 209 210 /* ne_warn("Node %x", node); */ 211 return node; 212 } 213 214 /* Ok, we're doing some weirdness here... */ 215 static NEOERR *_hash_resize(NE_HASH *hash) 216 { 217 NE_HASHNODE **new_nodes; 218 NE_HASHNODE *entry, *prev; 219 int x, next_bucket; 220 int orig_size = hash->size; 221 UINT32 hash_mask; 222 223 if (hash->size > hash->num) 224 return STATUS_OK; 225 226 /* We always double in size */ 227 new_nodes = (NE_HASHNODE **) realloc (hash->nodes, (hash->size*2) * sizeof(NE_HASHNODE)); 228 if (new_nodes == NULL) 229 return nerr_raise(NERR_NOMEM, "Unable to allocate memory to resize NE_HASH"); 230 231 hash->nodes = new_nodes; 232 orig_size = hash->size; 233 hash->size = hash->size*2; 234 235 /* Initialize new parts */ 236 for (x = orig_size; x < hash->size; x++) 237 { 238 hash->nodes[x] = NULL; 239 } 240 241 hash_mask = hash->size - 1; 242 243 for (x = 0; x < orig_size; x++) 244 { 245 prev = NULL; 246 next_bucket = x + orig_size; 247 for (entry = hash->nodes[x]; 248 entry; 249 entry = prev ? prev->next : hash->nodes[x]) 250 { 251 if ((entry->hashv & hash_mask) != x) 252 { 253 if (prev) 254 { 255 prev->next = entry->next; 256 } 257 else 258 { 259 hash->nodes[x] = entry->next; 260 } 261 entry->next = hash->nodes[next_bucket]; 262 hash->nodes[next_bucket] = entry; 263 } 264 else 265 { 266 prev = entry; 267 } 268 } 269 } 270 271 return STATUS_OK; 272 } 273 274 int ne_hash_str_comp(const void *a, const void *b) 275 { 276 return !strcmp((const char *)a, (const char *)b); 277 } 278 279 UINT32 ne_hash_str_hash(const void *a) 280 { 281 return ne_crc((unsigned char *)a, strlen((const char *)a)); 282 } 283 284 int ne_hash_int_comp(const void *a, const void *b) 285 { 286 if (a == b) return 1; 287 return 0; 288 } 289 290 UINT32 ne_hash_int_hash(const void *a) 291 { 292 return (UINT32)(long)(a); 293 } 294
