1/*- 2 * Copyright (c) 2004,2008 Oracle. All rights reserved. 3 * 4 * http://www.apache.org/licenses/LICENSE-2.0.txt 5 * 6 * authors: Thies C. Arntzen <thies@php.net> 7 * Sterling Hughes <sterling@php.net> 8 * George Schlossnagle <george@omniti.com> 9 */ 10extern "C" 11{ 12#include <stdlib.h> 13#include <string.h> 14#include "mm_hash.h" 15} 16 17MM_Hash *mm_hash_new(MM *mm, MM_HashDtor dtor) 18{ 19 MM_Hash *table; 20 21 table = (MM_Hash *) mm_calloc(mm, 1, sizeof(MM_Hash)); 22 table->mm = mm; 23 table->dtor = dtor; 24 25 return table; 26} 27 28void mm_hash_free(MM_Hash *table) 29{ 30 MM_Bucket *cur; 31 MM_Bucket *next; 32 int i; 33 34 for (i = 0; i < MM_HASH_SIZE; i++) { 35 cur = table->buckets[i]; 36 while (cur) { 37 next = cur->next; 38 39 if (table->dtor) table->dtor(cur->data); 40 mm_free(table->mm, cur->key); 41 mm_free(table->mm, cur); 42 43 cur = next; 44 } 45 } 46 mm_free(table->mm, table); 47} 48 49static unsigned int hash_hash(const char *key, int length) 50{ 51 unsigned int hash = 0; 52 53 while (--length) 54 hash = hash * 65599 + *key++; 55 56 return hash; 57} 58 59void *mm_hash_find(MM_Hash *table, const void *key, int length) 60{ 61 MM_Bucket *b; 62 unsigned int hash = hash_hash((const char *)key, length) % MM_HASH_SIZE; 63 64 for (b = table->buckets[ hash ]; b; b = b->next) { 65 if (hash != b->hash) continue; 66 if (length != b->length) continue; 67 if (memcmp(key, b->key, length)) continue; 68 69 return b->data; 70 } 71 72 return NULL; 73} 74 75void mm_hash_update(MM_Hash *table, char *key, int length, void *data) 76{ 77 MM_Bucket *b, p; 78 unsigned int hash; 79 80 hash = hash_hash(key, length) % MM_HASH_SIZE; 81 82 for(b = table->buckets[ hash ]; b; b = b->next) { 83 if (hash != b->hash) continue; 84 if (length != b->length) continue; 85 if (memcmp(key, b->key, length)) continue; 86 if (table->dtor) table->dtor(b->data); 87 b->data = data; 88 } 89 if(!b) { 90 b = (MM_Bucket *) mm_malloc(table->mm, sizeof(MM_Bucket)); 91 b->key = (char *) mm_malloc(table->mm, length + 1); 92 memcpy(b->key, key, length); 93 b->key[length] = 0; 94 b->length = length; 95 b->hash = hash; 96 b->data = data; 97 b->next = table->buckets[ hash ]; 98 table->buckets[ hash ] = b; 99 } 100 table->nElements++; 101} 102 103void mm_hash_delete(MM_Hash *table, char *key, int length) 104{ 105 MM_Bucket *b; 106 MM_Bucket *prev = NULL; 107 unsigned int hash; 108 109 hash = hash_hash(key, length) % MM_HASH_SIZE; 110 for (b = table->buckets[ hash ]; b; b = b->next) { 111 if (hash != b->hash || length != b->length || memcmp(key, b->key, length)) { 112 prev = b; 113 continue; 114 } 115 116 /* unlink */ 117 if (prev) { 118 prev->next = b->next; 119 } else { 120 table->buckets[hash] = b->next; 121 } 122 123 if (table->dtor) table->dtor(b->data); 124 mm_free(table->mm, b->key); 125 mm_free(table->mm, b); 126 127 break; 128 } 129} 130 131/* 132Local variables: 133tab-width: 4 134c-basic-offset: 4 135End: 136vim600: noet sw=4 ts=4 fdm=marker 137vim<600: noet sw=4 ts=4 138*/ 139