1 /* $Id$ */
2 /*
3 * Copyright (C) 2008-2011 Teluu Inc. (http://www.teluu.com)
4 * Copyright (C) 2003-2008 Benny Prijono <benny@prijono.org>
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19 */
20 #include <pj/hash.h>
21 #include <pj/log.h>
22 #include <pj/string.h>
23 #include <pj/pool.h>
24 #include <pj/os.h>
25 #include <pj/ctype.h>
26 #include <pj/assert.h>
27
28 /**
29 * The hash multiplier used to calculate hash value.
30 */
31 #define PJ_HASH_MULTIPLIER 33
32
33
34 struct pj_hash_entry
35 {
36 struct pj_hash_entry *next;
37 void *key;
38 pj_uint32_t hash;
39 pj_uint32_t keylen;
40 void *value;
41 };
42
43
44 struct pj_hash_table_t
45 {
46 pj_hash_entry **table;
47 unsigned count, rows;
48 pj_hash_iterator_t iterator;
49 };
50
51
52
pj_hash_calc(pj_uint32_t hash,const void * key,unsigned keylen)53 PJ_DEF(pj_uint32_t) pj_hash_calc(pj_uint32_t hash, const void *key,
54 unsigned keylen)
55 {
56 PJ_CHECK_STACK();
57
58 if (keylen==PJ_HASH_KEY_STRING) {
59 const pj_uint8_t *p = (const pj_uint8_t*)key;
60 for ( ; *p; ++p ) {
61 hash = (hash * PJ_HASH_MULTIPLIER) + *p;
62 }
63 } else {
64 const pj_uint8_t *p = (const pj_uint8_t*)key,
65 *end = p + keylen;
66 for ( ; p!=end; ++p) {
67 hash = (hash * PJ_HASH_MULTIPLIER) + *p;
68 }
69 }
70 return hash;
71 }
72
pj_hash_calc_tolower(pj_uint32_t hval,char * result,const pj_str_t * key)73 PJ_DEF(pj_uint32_t) pj_hash_calc_tolower( pj_uint32_t hval,
74 char *result,
75 const pj_str_t *key)
76 {
77 long i;
78
79 for (i=0; i<key->slen; ++i) {
80 int lower = pj_tolower(key->ptr[i]);
81 if (result)
82 result[i] = (char)lower;
83
84 hval = hval * PJ_HASH_MULTIPLIER + lower;
85 }
86
87 return hval;
88 }
89
90
pj_hash_create(pj_pool_t * pool,unsigned size)91 PJ_DEF(pj_hash_table_t*) pj_hash_create(pj_pool_t *pool, unsigned size)
92 {
93 pj_hash_table_t *h;
94 unsigned table_size;
95
96 /* Check that PJ_HASH_ENTRY_BUF_SIZE is correct. */
97 PJ_ASSERT_RETURN(sizeof(pj_hash_entry)<=PJ_HASH_ENTRY_BUF_SIZE, NULL);
98
99 h = PJ_POOL_ALLOC_T(pool, pj_hash_table_t);
100 h->count = 0;
101
102 PJ_LOG( 6, ("hashtbl", "hash table %p created from pool %s", h, pj_pool_getobjname(pool)));
103
104 /* size must be 2^n - 1.
105 round-up the size to this rule, except when size is 2^n, then size
106 will be round-down to 2^n-1.
107 */
108 table_size = 8;
109 do {
110 table_size <<= 1;
111 } while (table_size < size);
112 table_size -= 1;
113
114 h->rows = table_size;
115 h->table = (pj_hash_entry**)
116 pj_pool_calloc(pool, table_size+1, sizeof(pj_hash_entry*));
117 return h;
118 }
119
find_entry(pj_pool_t * pool,pj_hash_table_t * ht,const void * key,unsigned keylen,void * val,pj_uint32_t * hval,void * entry_buf,pj_bool_t lower)120 static pj_hash_entry **find_entry( pj_pool_t *pool, pj_hash_table_t *ht,
121 const void *key, unsigned keylen,
122 void *val, pj_uint32_t *hval,
123 void *entry_buf, pj_bool_t lower)
124 {
125 pj_uint32_t hash;
126 pj_hash_entry **p_entry, *entry;
127
128 if (hval && *hval != 0) {
129 hash = *hval;
130 if (keylen==PJ_HASH_KEY_STRING) {
131 keylen = (unsigned)pj_ansi_strlen((const char*)key);
132 }
133 } else {
134 /* This slightly differs with pj_hash_calc() because we need
135 * to get the keylen when keylen is PJ_HASH_KEY_STRING.
136 */
137 hash=0;
138 if (keylen==PJ_HASH_KEY_STRING) {
139 const pj_uint8_t *p = (const pj_uint8_t*)key;
140 for ( ; *p; ++p ) {
141 if (lower)
142 hash = hash * PJ_HASH_MULTIPLIER + pj_tolower(*p);
143 else
144 hash = hash * PJ_HASH_MULTIPLIER + *p;
145 }
146 keylen = (unsigned)(p - (const unsigned char*)key);
147 } else {
148 const pj_uint8_t *p = (const pj_uint8_t*)key,
149 *end = p + keylen;
150 for ( ; p!=end; ++p) {
151 if (lower)
152 hash = hash * PJ_HASH_MULTIPLIER + pj_tolower(*p);
153 else
154 hash = hash * PJ_HASH_MULTIPLIER + *p;
155 }
156 }
157
158 /* Report back the computed hash. */
159 if (hval)
160 *hval = hash;
161 }
162
163 /* scan the linked list */
164 for (p_entry = &ht->table[hash & ht->rows], entry=*p_entry;
165 entry;
166 p_entry = &entry->next, entry = *p_entry)
167 {
168 if (entry->hash==hash && entry->keylen==keylen &&
169 ((lower && pj_ansi_strnicmp((const char*)entry->key,
170 (const char*)key, keylen)==0) ||
171 (!lower && pj_memcmp(entry->key, key, keylen)==0)))
172 {
173 break;
174 }
175 }
176
177 if (entry || val==NULL)
178 return p_entry;
179
180 /* Entry not found, create a new one.
181 * If entry_buf is specified, use it. Otherwise allocate from pool.
182 */
183 if (entry_buf) {
184 entry = (pj_hash_entry*)entry_buf;
185 } else {
186 /* Pool must be specified! */
187 PJ_ASSERT_RETURN(pool != NULL, NULL);
188
189 entry = PJ_POOL_ALLOC_T(pool, pj_hash_entry);
190 PJ_LOG(6, ("hashtbl",
191 "%p: New p_entry %p created, pool used=%u, cap=%u",
192 ht, entry, pj_pool_get_used_size(pool),
193 pj_pool_get_capacity(pool)));
194 }
195 entry->next = NULL;
196 entry->hash = hash;
197 if (pool) {
198 entry->key = pj_pool_alloc(pool, keylen);
199 pj_memcpy(entry->key, key, keylen);
200 } else {
201 entry->key = (void*)key;
202 }
203 entry->keylen = keylen;
204 entry->value = val;
205 *p_entry = entry;
206
207 ++ht->count;
208
209 return p_entry;
210 }
211
pj_hash_get(pj_hash_table_t * ht,const void * key,unsigned keylen,pj_uint32_t * hval)212 PJ_DEF(void *) pj_hash_get( pj_hash_table_t *ht,
213 const void *key, unsigned keylen,
214 pj_uint32_t *hval)
215 {
216 pj_hash_entry *entry;
217 entry = *find_entry( NULL, ht, key, keylen, NULL, hval, NULL, PJ_FALSE);
218 return entry ? entry->value : NULL;
219 }
220
pj_hash_get_lower(pj_hash_table_t * ht,const void * key,unsigned keylen,pj_uint32_t * hval)221 PJ_DEF(void *) pj_hash_get_lower( pj_hash_table_t *ht,
222 const void *key, unsigned keylen,
223 pj_uint32_t *hval)
224 {
225 pj_hash_entry *entry;
226 entry = *find_entry( NULL, ht, key, keylen, NULL, hval, NULL, PJ_TRUE);
227 return entry ? entry->value : NULL;
228 }
229
hash_set(pj_pool_t * pool,pj_hash_table_t * ht,const void * key,unsigned keylen,pj_uint32_t hval,void * value,void * entry_buf,pj_bool_t lower)230 static void hash_set( pj_pool_t *pool, pj_hash_table_t *ht,
231 const void *key, unsigned keylen, pj_uint32_t hval,
232 void *value, void *entry_buf, pj_bool_t lower )
233 {
234 pj_hash_entry **p_entry;
235
236 p_entry = find_entry( pool, ht, key, keylen, value, &hval, entry_buf,
237 lower);
238 if (*p_entry) {
239 if (value == NULL) {
240 /* delete entry */
241 PJ_LOG(6, ("hashtbl", "%p: p_entry %p deleted", ht, *p_entry));
242 *p_entry = (*p_entry)->next;
243 --ht->count;
244
245 } else {
246 /* overwrite */
247 (*p_entry)->value = value;
248 PJ_LOG(6, ("hashtbl", "%p: p_entry %p value set to %p", ht,
249 *p_entry, value));
250 }
251 }
252 }
253
pj_hash_set(pj_pool_t * pool,pj_hash_table_t * ht,const void * key,unsigned keylen,pj_uint32_t hval,void * value)254 PJ_DEF(void) pj_hash_set( pj_pool_t *pool, pj_hash_table_t *ht,
255 const void *key, unsigned keylen, pj_uint32_t hval,
256 void *value )
257 {
258 hash_set(pool, ht, key, keylen, hval, value, NULL, PJ_FALSE);
259 }
260
pj_hash_set_lower(pj_pool_t * pool,pj_hash_table_t * ht,const void * key,unsigned keylen,pj_uint32_t hval,void * value)261 PJ_DEF(void) pj_hash_set_lower( pj_pool_t *pool, pj_hash_table_t *ht,
262 const void *key, unsigned keylen,
263 pj_uint32_t hval, void *value )
264 {
265 hash_set(pool, ht, key, keylen, hval, value, NULL, PJ_TRUE);
266 }
267
pj_hash_set_np(pj_hash_table_t * ht,const void * key,unsigned keylen,pj_uint32_t hval,pj_hash_entry_buf entry_buf,void * value)268 PJ_DEF(void) pj_hash_set_np( pj_hash_table_t *ht,
269 const void *key, unsigned keylen,
270 pj_uint32_t hval, pj_hash_entry_buf entry_buf,
271 void *value)
272 {
273 hash_set(NULL, ht, key, keylen, hval, value, (void *)entry_buf, PJ_FALSE);
274 }
275
pj_hash_set_np_lower(pj_hash_table_t * ht,const void * key,unsigned keylen,pj_uint32_t hval,pj_hash_entry_buf entry_buf,void * value)276 PJ_DEF(void) pj_hash_set_np_lower( pj_hash_table_t *ht,
277 const void *key, unsigned keylen,
278 pj_uint32_t hval,
279 pj_hash_entry_buf entry_buf,
280 void *value)
281 {
282 hash_set(NULL, ht, key, keylen, hval, value, (void *)entry_buf, PJ_TRUE);
283 }
284
pj_hash_count(pj_hash_table_t * ht)285 PJ_DEF(unsigned) pj_hash_count( pj_hash_table_t *ht )
286 {
287 return ht->count;
288 }
289
pj_hash_first(pj_hash_table_t * ht,pj_hash_iterator_t * it)290 PJ_DEF(pj_hash_iterator_t*) pj_hash_first( pj_hash_table_t *ht,
291 pj_hash_iterator_t *it )
292 {
293 it->index = 0;
294 it->entry = NULL;
295
296 for (; it->index <= ht->rows; ++it->index) {
297 it->entry = ht->table[it->index];
298 if (it->entry) {
299 break;
300 }
301 }
302
303 return it->entry ? it : NULL;
304 }
305
pj_hash_next(pj_hash_table_t * ht,pj_hash_iterator_t * it)306 PJ_DEF(pj_hash_iterator_t*) pj_hash_next( pj_hash_table_t *ht,
307 pj_hash_iterator_t *it )
308 {
309 it->entry = it->entry->next;
310 if (it->entry) {
311 return it;
312 }
313
314 for (++it->index; it->index <= ht->rows; ++it->index) {
315 it->entry = ht->table[it->index];
316 if (it->entry) {
317 break;
318 }
319 }
320
321 return it->entry ? it : NULL;
322 }
323
pj_hash_this(pj_hash_table_t * ht,pj_hash_iterator_t * it)324 PJ_DEF(void*) pj_hash_this( pj_hash_table_t *ht, pj_hash_iterator_t *it )
325 {
326 PJ_CHECK_STACK();
327 PJ_UNUSED_ARG(ht);
328 return it->entry->value;
329 }
330
331 #if 0
332 void pj_hash_dump_collision( pj_hash_table_t *ht )
333 {
334 unsigned min=0xFFFFFFFF, max=0;
335 unsigned i;
336 char line[120];
337 int len, totlen = 0;
338
339 for (i=0; i<=ht->rows; ++i) {
340 unsigned count = 0;
341 pj_hash_entry *entry = ht->table[i];
342 while (entry) {
343 ++count;
344 entry = entry->next;
345 }
346 if (count < min)
347 min = count;
348 if (count > max)
349 max = count;
350 len = pj_snprintf( line+totlen, sizeof(line)-totlen, "%3d:%3d ", i, count);
351 if (len < 1)
352 break;
353 totlen += len;
354
355 if ((i+1) % 10 == 0) {
356 line[totlen] = '\0';
357 PJ_LOG(4,(__FILE__, line));
358 }
359 }
360
361 PJ_LOG(4,(__FILE__,"Count: %d, min: %d, max: %d\n", ht->count, min, max));
362 }
363 #endif
364
365
366