1/*- 2 * Copyright (c) 2004-2009 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 if ((table = (MM_Hash *) mm_calloc(mm, 1, sizeof(MM_Hash))) == NULL) 22 return NULL; 23 table->mm = mm; 24 table->dtor = dtor; 25 26 return table; 27} 28 29void mm_hash_free(MM_Hash *table) 30{ 31 MM_Bucket *cur; 32 MM_Bucket *next; 33 int i; 34 35 for (i = 0; i < MM_HASH_SIZE; i++) { 36 cur = table->buckets[i]; 37 while (cur) { 38 next = cur->next; 39 40 if (table->dtor) table->dtor(cur->data); 41 mm_free(table->mm, cur->key); 42 mm_free(table->mm, cur); 43 44 cur = next; 45 } 46 } 47 mm_free(table->mm, table); 48} 49 50static unsigned int hash_hash(const char *key, int length) 51{ 52 unsigned int hash = 0; 53 54 while (--length) 55 hash = hash * 65599 + *key++; 56 57 return hash; 58} 59 60void *mm_hash_find(MM_Hash *table, const void *key, int length) 61{ 62 MM_Bucket *b; 63 unsigned int hash = hash_hash((const char *)key, length) % MM_HASH_SIZE; 64 65 for (b = table->buckets[ hash ]; b; b = b->next) { 66 if (hash != b->hash) continue; 67 if (length != b->length) continue; 68 if (memcmp(key, b->key, length)) continue; 69 70 return b->data; 71 } 72 73 return NULL; 74} 75 76void mm_hash_update(MM_Hash *table, char *key, int length, void *data) 77{ 78 MM_Bucket *b, p; 79 unsigned int hash; 80 81 hash = hash_hash(key, length) % MM_HASH_SIZE; 82 83 for(b = table->buckets[ hash ]; b; b = b->next) { 84 if (hash != b->hash) continue; 85 if (length != b->length) continue; 86 if (memcmp(key, b->key, length)) continue; 87 if (table->dtor) table->dtor(b->data); 88 b->data = data; 89 } 90 if(!b) { 91 if ((b = (MM_Bucket *) mm_malloc( 92 table->mm, sizeof(MM_Bucket))) == NULL) 93 return; 94 if ((b->key = (char *) mm_malloc( 95 table->mm, length + 1)) == NULL) { 96 free(b); 97 return; 98 } 99 memcpy(b->key, key, length); 100 b->key[length] = 0; 101 b->length = length; 102 b->hash = hash; 103 b->data = data; 104 b->next = table->buckets[ hash ]; 105 table->buckets[ hash ] = b; 106 } 107 table->nElements++; 108} 109 110void mm_hash_delete(MM_Hash *table, char *key, int length) 111{ 112 MM_Bucket *b; 113 MM_Bucket *prev = NULL; 114 unsigned int hash; 115 116 hash = hash_hash(key, length) % MM_HASH_SIZE; 117 for (b = table->buckets[ hash ]; b; b = b->next) { 118 if (hash != b->hash || length != b->length || memcmp(key, b->key, length)) { 119 prev = b; 120 continue; 121 } 122 123 /* unlink */ 124 if (prev) { 125 prev->next = b->next; 126 } else { 127 table->buckets[hash] = b->next; 128 } 129 130 if (table->dtor) table->dtor(b->data); 131 mm_free(table->mm, b->key); 132 mm_free(table->mm, b); 133 134 break; 135 } 136} 137 138/* 139Local variables: 140tab-width: 4 141c-basic-offset: 4 142End: 143vim600: noet sw=4 ts=4 fdm=marker 144vim<600: noet sw=4 ts=4 145*/ 146