1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
|
/* $Id: hash.h 4208 2012-07-18 07:52:33Z ming $ */
/*
* Copyright (C) 2008-2011 Teluu Inc. (http://www.teluu.com)
* Copyright (C) 2003-2008 Benny Prijono <benny@prijono.org>
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
#ifndef __PJ_HASH_H__
#define __PJ_HASH_H__
/**
* @file hash.h
* @brief Hash Table.
*/
#include <pj/types.h>
PJ_BEGIN_DECL
/**
* @defgroup PJ_HASH Hash Table
* @ingroup PJ_DS
* @{
* A hash table is a dictionary in which keys are mapped to array positions by
* hash functions. Having the keys of more than one item map to the same
* position is called a collision. In this library, we will chain the nodes
* that have the same key in a list.
*/
/**
* If this constant is used as keylen, then the key is interpreted as
* NULL terminated string.
*/
#define PJ_HASH_KEY_STRING ((unsigned)-1)
/**
* This indicates the size of of each hash entry.
*/
#define PJ_HASH_ENTRY_BUF_SIZE (3*sizeof(void*) + 2*sizeof(pj_uint32_t))
/**
* Type declaration for entry buffer, used by #pj_hash_set_np()
*/
typedef void *pj_hash_entry_buf[(PJ_HASH_ENTRY_BUF_SIZE+sizeof(void*)-1)/(sizeof(void*))];
/**
* This is the function that is used by the hash table to calculate hash value
* of the specified key.
*
* @param hval the initial hash value, or zero.
* @param key the key to calculate.
* @param keylen the length of the key, or PJ_HASH_KEY_STRING to treat
* the key as null terminated string.
*
* @return the hash value.
*/
PJ_DECL(pj_uint32_t) pj_hash_calc(pj_uint32_t hval,
const void *key, unsigned keylen);
/**
* Convert the key to lowercase and calculate the hash value. The resulting
* string is stored in \c result.
*
* @param hval The initial hash value, normally zero.
* @param result Optional. Buffer to store the result, which must be enough
* to hold the string.
* @param key The input key to be converted and calculated.
*
* @return The hash value.
*/
PJ_DECL(pj_uint32_t) pj_hash_calc_tolower(pj_uint32_t hval,
char *result,
const pj_str_t *key);
/**
* Create a hash table with the specified 'bucket' size.
*
* @param pool the pool from which the hash table will be allocated from.
* @param size the bucket size, which will be round-up to the nearest 2^n-1
*
* @return the hash table.
*/
PJ_DECL(pj_hash_table_t*) pj_hash_create(pj_pool_t *pool, unsigned size);
/**
* Get the value associated with the specified key.
*
* @param ht the hash table.
* @param key the key to look for.
* @param keylen the length of the key, or PJ_HASH_KEY_STRING to use the
* string length of the key.
* @param hval if this argument is not NULL and the value is not zero,
* the value will be used as the computed hash value. If
* the argument is not NULL and the value is zero, it will
* be filled with the computed hash upon return.
*
* @return the value associated with the key, or NULL if the key is not found.
*/
PJ_DECL(void *) pj_hash_get( pj_hash_table_t *ht,
const void *key, unsigned keylen,
pj_uint32_t *hval );
/**
* Variant of #pj_hash_get() with the key being converted to lowercase when
* calculating the hash value.
*
* @see pj_hash_get()
*/
PJ_DECL(void *) pj_hash_get_lower( pj_hash_table_t *ht,
const void *key, unsigned keylen,
pj_uint32_t *hval );
/**
* Associate/disassociate a value with the specified key. If value is not
* NULL and entry already exists, the entry's value will be overwritten.
* If value is not NULL and entry does not exist, a new one will be created
* with the specified pool. Otherwise if value is NULL, entry will be
* deleted if it exists.
*
* @param pool the pool to allocate the new entry if a new entry has to be
* created.
* @param ht the hash table.
* @param key the key. If pool is not specified, the key MUST point to
* buffer that remains valid for the duration of the entry.
* @param keylen the length of the key, or PJ_HASH_KEY_STRING to use the
* string length of the key.
* @param hval if the value is not zero, then the hash table will use
* this value to search the entry's index, otherwise it will
* compute the key. This value can be obtained when calling
* #pj_hash_get().
* @param value value to be associated, or NULL to delete the entry with
* the specified key.
*/
PJ_DECL(void) pj_hash_set( pj_pool_t *pool, pj_hash_table_t *ht,
const void *key, unsigned keylen, pj_uint32_t hval,
void *value );
/**
* Variant of #pj_hash_set() with the key being converted to lowercase when
* calculating the hash value.
*
* @see pj_hash_set()
*/
PJ_DECL(void) pj_hash_set_lower( pj_pool_t *pool, pj_hash_table_t *ht,
const void *key, unsigned keylen,
pj_uint32_t hval, void *value );
/**
* Associate/disassociate a value with the specified key. This function works
* like #pj_hash_set(), except that it doesn't use pool (hence the np -- no
* pool suffix). If new entry needs to be allocated, it will use the entry_buf.
*
* @param ht the hash table.
* @param key the key.
* @param keylen the length of the key, or PJ_HASH_KEY_STRING to use the
* string length of the key.
* @param hval if the value is not zero, then the hash table will use
* this value to search the entry's index, otherwise it will
* compute the key. This value can be obtained when calling
* #pj_hash_get().
* @param entry_buf Buffer which will be used for the new entry, when one needs
* to be created.
* @param value value to be associated, or NULL to delete the entry with
* the specified key.
*/
PJ_DECL(void) 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);
/**
* Variant of #pj_hash_set_np() with the key being converted to lowercase
* when calculating the hash value.
*
* @see pj_hash_set_np()
*/
PJ_DECL(void) 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);
/**
* Get the total number of entries in the hash table.
*
* @param ht the hash table.
*
* @return the number of entries in the hash table.
*/
PJ_DECL(unsigned) pj_hash_count( pj_hash_table_t *ht );
/**
* Get the iterator to the first element in the hash table.
*
* @param ht the hash table.
* @param it the iterator for iterating hash elements.
*
* @return the iterator to the hash element, or NULL if no element presents.
*/
PJ_DECL(pj_hash_iterator_t*) pj_hash_first( pj_hash_table_t *ht,
pj_hash_iterator_t *it );
/**
* Get the next element from the iterator.
*
* @param ht the hash table.
* @param it the hash iterator.
*
* @return the next iterator, or NULL if there's no more element.
*/
PJ_DECL(pj_hash_iterator_t*) pj_hash_next( pj_hash_table_t *ht,
pj_hash_iterator_t *it );
/**
* Get the value associated with a hash iterator.
*
* @param ht the hash table.
* @param it the hash iterator.
*
* @return the value associated with the current element in iterator.
*/
PJ_DECL(void*) pj_hash_this( pj_hash_table_t *ht,
pj_hash_iterator_t *it );
/**
* @}
*/
PJ_END_DECL
#endif
|
