| /* |
| * Copyright 2003-2004 Brandon Long |
| * All Rights Reserved. |
| * |
| * ClearSilver Templating System |
| * |
| * This code is made available under the terms of the ClearSilver License. |
| * http://www.clearsilver.net/license.hdf |
| * |
| */ |
| |
| #include "cs_config.h" |
| |
| #include <stdlib.h> |
| #include <string.h> |
| |
| #include "neo_misc.h" |
| #include "neo_err.h" |
| #include "neo_hash.h" |
| |
| static NEOERR *_hash_resize(NE_HASH *hash); |
| static NE_HASHNODE **_hash_lookup_node (NE_HASH *hash, void *key, UINT32 *hashv); |
| |
| NEOERR *ne_hash_init (NE_HASH **hash, NE_HASH_FUNC hash_func, NE_COMP_FUNC comp_func) |
| { |
| NE_HASH *my_hash = NULL; |
| |
| my_hash = (NE_HASH *) calloc(1, sizeof(NE_HASH)); |
| if (my_hash == NULL) |
| return nerr_raise(NERR_NOMEM, "Unable to allocate memory for NE_HASH"); |
| |
| my_hash->size = 256; |
| my_hash->num = 0; |
| my_hash->hash_func = hash_func; |
| my_hash->comp_func = comp_func; |
| |
| my_hash->nodes = (NE_HASHNODE **) calloc (my_hash->size, sizeof(NE_HASHNODE *)); |
| if (my_hash->nodes == NULL) |
| { |
| free(my_hash); |
| return nerr_raise(NERR_NOMEM, "Unable to allocate memory for NE_HASHNODES"); |
| } |
| |
| *hash = my_hash; |
| |
| return STATUS_OK; |
| } |
| |
| void ne_hash_destroy (NE_HASH **hash) |
| { |
| NE_HASH *my_hash; |
| NE_HASHNODE *node, *next; |
| int x; |
| |
| if (hash == NULL || *hash == NULL) |
| return; |
| |
| my_hash = *hash; |
| |
| for (x = 0; x < my_hash->size; x++) |
| { |
| node = my_hash->nodes[x]; |
| while (node) |
| { |
| next = node->next; |
| free(node); |
| node = next; |
| } |
| } |
| free(my_hash->nodes); |
| my_hash->nodes = NULL; |
| free(my_hash); |
| *hash = NULL; |
| } |
| |
| NEOERR *ne_hash_insert(NE_HASH *hash, void *key, void *value) |
| { |
| UINT32 hashv; |
| NE_HASHNODE **node; |
| |
| node = _hash_lookup_node(hash, key, &hashv); |
| |
| if (*node) |
| { |
| (*node)->value = value; |
| } |
| else |
| { |
| *node = (NE_HASHNODE *) malloc(sizeof(NE_HASHNODE)); |
| if (node == NULL) |
| return nerr_raise(NERR_NOMEM, "Unable to allocate NE_HASHNODE"); |
| |
| (*node)->hashv = hashv; |
| (*node)->key = key; |
| (*node)->value = value; |
| (*node)->next = NULL; |
| } |
| hash->num++; |
| |
| return _hash_resize(hash); |
| } |
| |
| void *ne_hash_lookup(NE_HASH *hash, void *key) |
| { |
| NE_HASHNODE *node; |
| |
| node = *_hash_lookup_node(hash, key, NULL); |
| |
| return (node) ? node->value : NULL; |
| } |
| |
| void *ne_hash_remove(NE_HASH *hash, void *key) |
| { |
| NE_HASHNODE **node, *remove; |
| void *value = NULL; |
| |
| node = _hash_lookup_node(hash, key, NULL); |
| if (*node) |
| { |
| remove = *node; |
| *node = remove->next; |
| value = remove->value; |
| free(remove); |
| hash->num--; |
| } |
| return value; |
| } |
| |
| int ne_hash_has_key(NE_HASH *hash, void *key) |
| { |
| NE_HASHNODE *node; |
| |
| node = *_hash_lookup_node(hash, key, NULL); |
| |
| if (node) return 1; |
| return 0; |
| } |
| |
| void *ne_hash_next(NE_HASH *hash, void **key) |
| { |
| NE_HASHNODE **node = 0; |
| UINT32 hashv, bucket; |
| |
| if (*key) |
| { |
| node = _hash_lookup_node(hash, key, NULL); |
| |
| if (*node) |
| { |
| bucket = (*node)->hashv & (hash->size - 1); |
| } |
| else |
| { |
| hashv = hash->hash_func(*key); |
| bucket = hashv & (hash->size - 1); |
| } |
| } |
| else |
| { |
| bucket = 0; |
| } |
| |
| if (*node) |
| { |
| if ((*node)->next) |
| { |
| *key = (*node)->next->key; |
| return (*node)->next->value; |
| } |
| bucket++; |
| } |
| |
| while (bucket < hash->size) |
| { |
| if (hash->nodes[bucket]) |
| { |
| *key = hash->nodes[bucket]->key; |
| return hash->nodes[bucket]->value; |
| } |
| bucket++; |
| } |
| |
| return NULL; |
| } |
| |
| static NE_HASHNODE **_hash_lookup_node (NE_HASH *hash, void *key, UINT32 *o_hashv) |
| { |
| UINT32 hashv, bucket; |
| NE_HASHNODE **node; |
| |
| hashv = hash->hash_func(key); |
| if (o_hashv) *o_hashv = hashv; |
| bucket = hashv & (hash->size - 1); |
| /* ne_warn("Lookup %s %d %d", key, hashv, bucket); */ |
| |
| node = &(hash->nodes[bucket]); |
| |
| if (hash->comp_func) |
| { |
| while (*node && !(hash->comp_func((*node)->key, key))) |
| node = &(*node)->next; |
| } |
| else |
| { |
| /* No comp_func means we're doing pointer comparisons */ |
| while (*node && (*node)->key != key) |
| node = &(*node)->next; |
| } |
| |
| /* ne_warn("Node %x", node); */ |
| return node; |
| } |
| |
| /* Ok, we're doing some weirdness here... */ |
| static NEOERR *_hash_resize(NE_HASH *hash) |
| { |
| NE_HASHNODE **new_nodes; |
| NE_HASHNODE *entry, *prev; |
| int x, next_bucket; |
| int orig_size = hash->size; |
| UINT32 hash_mask; |
| |
| if (hash->size > hash->num) |
| return STATUS_OK; |
| |
| /* We always double in size */ |
| new_nodes = (NE_HASHNODE **) realloc (hash->nodes, (hash->size*2) * sizeof(NE_HASHNODE)); |
| if (new_nodes == NULL) |
| return nerr_raise(NERR_NOMEM, "Unable to allocate memory to resize NE_HASH"); |
| |
| hash->nodes = new_nodes; |
| orig_size = hash->size; |
| hash->size = hash->size*2; |
| |
| /* Initialize new parts */ |
| for (x = orig_size; x < hash->size; x++) |
| { |
| hash->nodes[x] = NULL; |
| } |
| |
| hash_mask = hash->size - 1; |
| |
| for (x = 0; x < orig_size; x++) |
| { |
| prev = NULL; |
| next_bucket = x + orig_size; |
| for (entry = hash->nodes[x]; |
| entry; |
| entry = prev ? prev->next : hash->nodes[x]) |
| { |
| if ((entry->hashv & hash_mask) != x) |
| { |
| if (prev) |
| { |
| prev->next = entry->next; |
| } |
| else |
| { |
| hash->nodes[x] = entry->next; |
| } |
| entry->next = hash->nodes[next_bucket]; |
| hash->nodes[next_bucket] = entry; |
| } |
| else |
| { |
| prev = entry; |
| } |
| } |
| } |
| |
| return STATUS_OK; |
| } |
| |
| int ne_hash_str_comp(const void *a, const void *b) |
| { |
| return !strcmp((const char *)a, (const char *)b); |
| } |
| |
| UINT32 ne_hash_str_hash(const void *a) |
| { |
| return ne_crc((unsigned char *)a, strlen((const char *)a)); |
| } |
| |
| int ne_hash_int_comp(const void *a, const void *b) |
| { |
| if (a == b) return 1; |
| return 0; |
| } |
| |
| UINT32 ne_hash_int_hash(const void *a) |
| { |
| return (UINT32)(long)(a); |
| } |