1 |
/**
|
2 |
* ZANavi, Zoff Android Navigation system.
|
3 |
* Copyright (C) 2012 Zoff <zoff@zoff.cc>
|
4 |
*
|
5 |
*
|
6 |
* patched to work with integers instead of strings
|
7 |
*
|
8 |
*
|
9 |
* This program is free software; you can redistribute it and/or
|
10 |
* modify it under the terms of the GNU General Public License
|
11 |
* version 2 as published by the Free Software Foundation.
|
12 |
*
|
13 |
* This program is distributed in the hope that it will be useful,
|
14 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
15 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
16 |
* GNU General Public License for more details.
|
17 |
*
|
18 |
* You should have received a copy of the GNU General Public License
|
19 |
* along with this program; if not, write to the
|
20 |
* Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
|
21 |
* Boston, MA 02110-1301, USA.
|
22 |
*/
|
23 |
|
24 |
/* Creation date: 2005-06-24 21:22:09
|
25 |
* Authors: Don
|
26 |
* Change log:
|
27 |
*/
|
28 |
|
29 |
/* Copyright (c) 2005 Don Owens
|
30 |
All rights reserved.
|
31 |
|
32 |
This code is released under the BSD license:
|
33 |
|
34 |
Redistribution and use in source and binary forms, with or without
|
35 |
modification, are permitted provided that the following conditions
|
36 |
are met:
|
37 |
|
38 |
* Redistributions of source code must retain the above copyright
|
39 |
notice, this list of conditions and the following disclaimer.
|
40 |
|
41 |
* Redistributions in binary form must reproduce the above
|
42 |
copyright notice, this list of conditions and the following
|
43 |
disclaimer in the documentation and/or other materials provided
|
44 |
with the distribution.
|
45 |
|
46 |
* Neither the name of the author nor the names of its
|
47 |
contributors may be used to endorse or promote products derived
|
48 |
from this software without specific prior written permission.
|
49 |
|
50 |
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
|
51 |
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
|
52 |
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
|
53 |
FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
|
54 |
COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
|
55 |
INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
|
56 |
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
|
57 |
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
|
58 |
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
|
59 |
STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
|
60 |
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
|
61 |
OF THE POSSIBILITY OF SUCH DAMAGE.
|
62 |
*/
|
63 |
|
64 |
#ifndef _CFU_HASH_H_
|
65 |
#define _CFU_HASH_H_
|
66 |
|
67 |
#include <cfu.h>
|
68 |
|
69 |
#include <sys/types.h>
|
70 |
#include <stdio.h>
|
71 |
|
72 |
#ifdef __cplusplus
|
73 |
extern "C" {
|
74 |
#endif
|
75 |
|
76 |
/* The hash table itself. */
|
77 |
struct cfuhash_table;
|
78 |
typedef struct cfuhash_table cfuhash_table_t;
|
79 |
|
80 |
/* Prototype for a pointer to a hashing function. */
|
81 |
typedef u_int32_t (*cfuhash_function_t)(const void *key, size_t length);
|
82 |
|
83 |
/* Prototype for a pointer to a free function. */
|
84 |
typedef void (*cfuhash_free_fn_t)(void *data);
|
85 |
|
86 |
/* Prototype for a pointer to a function that determines whether
|
87 |
* or not to remove an entry from the hash.
|
88 |
*/
|
89 |
typedef int (*cfuhash_remove_fn_t)(void *key, size_t key_size, void *data, size_t data_size,
|
90 |
void *arg);
|
91 |
|
92 |
/* Prototype for a pointer to a function to be called foreach
|
93 |
* key/value pair in the hash by cfuhash_foreach(). Iteration
|
94 |
* stops if a non-zero value is returned.
|
95 |
*/
|
96 |
typedef int (*cfuhash_foreach_fn_t)(void *key, size_t key_size, void *data, size_t data_size,
|
97 |
void *arg);
|
98 |
|
99 |
/* Creates a new hash table. */
|
100 |
extern cfuhash_table_t * cfuhash_new();
|
101 |
|
102 |
/* Creates a new hash table with the specified size (number of
|
103 |
* buckets).
|
104 |
*/
|
105 |
extern cfuhash_table_t * cfuhash_new_with_initial_size(size_t size);
|
106 |
|
107 |
/* Creates a new hash table with the specified flags. Pass zero
|
108 |
* for flags if you want the defaults.
|
109 |
*/
|
110 |
extern cfuhash_table_t * cfuhash_new_with_flags(u_int32_t flags);
|
111 |
|
112 |
/* Same as cfuhash_new() except automatically calls cfuhash_set_free_fn(). */
|
113 |
extern cfuhash_table_t * cfuhash_new_with_free_fn(cfuhash_free_fn_t ff);
|
114 |
|
115 |
/* Copies entries in src to dst */
|
116 |
extern int cfuhash_copy(cfuhash_table_t *src, cfuhash_table_t *dst);
|
117 |
|
118 |
/* Returns a new hash containing entries from both hash tables.
|
119 |
* For any entries with the same key, the one from ht2 wins.
|
120 |
*/
|
121 |
extern cfuhash_table_t * cfuhash_merge(cfuhash_table_t *ht1, cfuhash_table_t *ht2,
|
122 |
u_int32_t flags);
|
123 |
|
124 |
/* Sets the hashing function to use when computing which bucket to add
|
125 |
* entries to. It should return a 32-bit unsigned integer. By
|
126 |
* default, Perl's hashing algorithm is used.
|
127 |
*/
|
128 |
extern int cfuhash_set_hash_function(cfuhash_table_t *ht, cfuhash_function_t hf);
|
129 |
|
130 |
/* Sets the thresholds for when to rehash. The ratio
|
131 |
* num_entries/buckets is compared against low and high. If it is
|
132 |
* below 'low' or above 'high', the hash will shrink or grow,
|
133 |
* respectively, unless the flags say to do otherwise.
|
134 |
*/
|
135 |
extern int cfuhash_set_thresholds(cfuhash_table_t *ht, float low, float high);
|
136 |
|
137 |
/* Sets the function to use when removing an entry from the hash,
|
138 |
* i.e., when replacing an existing entry, deleting an entry, or
|
139 |
* clearing the hash. It is passed the value of the entry as a
|
140 |
* void *.
|
141 |
*/
|
142 |
extern int cfuhash_set_free_function(cfuhash_table_t * ht, cfuhash_free_fn_t ff);
|
143 |
|
144 |
/* Returns the hash's flags. See below for flag definitions. */
|
145 |
extern u_int32_t cfuhash_get_flags(cfuhash_table_t *ht);
|
146 |
|
147 |
/* Sets a flag. */
|
148 |
extern u_int32_t cfuhash_set_flag(cfuhash_table_t *ht, u_int32_t flag);
|
149 |
|
150 |
/* Clears a flag. */
|
151 |
extern u_int32_t cfuhash_clear_flag(cfuhash_table_t *ht, u_int32_t new_flag);
|
152 |
|
153 |
/* Returns the value for the entry with given key. If key_size is -1,
|
154 |
* key is assumed to be a null-terminated string. If data_size is not
|
155 |
* NULL, the size of the value is placed into data_size.
|
156 |
*/
|
157 |
extern int cfuhash_get_data(cfuhash_table_t *ht, long long key, size_t key_size,
|
158 |
long *data, size_t *data_size);
|
159 |
|
160 |
/* Returns 1 if an entry with the given key exists in the hash, 0 otherwise. */
|
161 |
extern int cfuhash_exists_data(cfuhash_table_t *ht, long long key, size_t key_size);
|
162 |
|
163 |
/* Inserts the given data value into the hash and associates it with
|
164 |
* key. If key_size is -1, key is assumed to be a null-terminated
|
165 |
* string. If data_size is -1, it is assumed to be a null-terminated
|
166 |
* string (it's length will be calculated using strlen). If
|
167 |
* data_size is zero, it will be returned as zero when the value is
|
168 |
* requested.
|
169 |
*/
|
170 |
extern int cfuhash_put_data(cfuhash_table_t *ht, long long key, size_t key_size, long data,
|
171 |
size_t data_size, void *r);
|
172 |
|
173 |
/* Clears the hash table (deletes all entries). */
|
174 |
extern void cfuhash_clear(cfuhash_table_t *ht);
|
175 |
|
176 |
/* Deletes the entry in the hash associated with key. If the entry
|
177 |
* existed, it's value will be returned.
|
178 |
*/
|
179 |
extern void * cfuhash_delete_data(cfuhash_table_t *ht, const void *key, size_t key_size);
|
180 |
|
181 |
/* Returns all the keys from the hash. The number of keys is placed
|
182 |
* into the value pointed to by num_keys. If key_sizes is not NULL,
|
183 |
* it will be set to an array of key sizes. If fast is zero, copies
|
184 |
* of the keys are returned. Otherwise, pointers to the real keys
|
185 |
* will be returned.
|
186 |
*/
|
187 |
extern void **cfuhash_keys_data(cfuhash_table_t *ht, size_t *num_keys, size_t **key_sizes,
|
188 |
int fast);
|
189 |
|
190 |
/* Initializes a loop over all the key/value pairs in the hash. It
|
191 |
* returns the first key/value pair (see cfuhash_next_data()). 1 is
|
192 |
* returned if there are any entries in the hash. 0 is returned
|
193 |
* otherwise.
|
194 |
*/
|
195 |
extern int cfuhash_each_data(cfuhash_table_t *ht, void **key, size_t *key_size, void **data,
|
196 |
size_t *data_size);
|
197 |
|
198 |
/* Gets the next key/value pair from the hash. You must initialize
|
199 |
* the loop using cfuhash_each_data() before calling this function.
|
200 |
* If a entry is left to return, 1 is returned from the function. 0
|
201 |
* is returned if there are no more entries in the hash.
|
202 |
*/
|
203 |
extern int cfuhash_next_data(cfuhash_table_t *ht, void **key, size_t *key_size, void **data,
|
204 |
size_t *data_size);
|
205 |
|
206 |
/* Iterates over the key/value pairs in the hash, passing each one
|
207 |
* to r_fn, and removes all entries for which r_fn returns true.
|
208 |
* If ff is not NULL, it is the passed the data to be freed. arg
|
209 |
* is passed to r_fn.
|
210 |
*/
|
211 |
extern size_t cfuhash_foreach_remove(cfuhash_table_t *ht, cfuhash_remove_fn_t r_fn,
|
212 |
cfuhash_free_fn_t ff, void *arg);
|
213 |
|
214 |
/* Iterates over the key/value pairs in the hash, passing each one
|
215 |
* to fe_fn, along with arg. This locks the hash, so do not call
|
216 |
* any operations on the hash from within fe_fn unless you really
|
217 |
* know what you're doing. A non-zero return value from fe_fn()
|
218 |
* stops the iteration.
|
219 |
*/
|
220 |
extern size_t cfuhash_foreach(cfuhash_table_t *ht, cfuhash_foreach_fn_t fe_fn, void *arg);
|
221 |
|
222 |
/* Frees all resources allocated by the hash. If ff is not NULL, it
|
223 |
* is called for each hash entry with the value of the entry passed as
|
224 |
* its only argument. If ff is not NULL, it overrides any function
|
225 |
* set previously with cfuhash_set_free_function().
|
226 |
*/
|
227 |
extern int cfuhash_destroy(cfuhash_table_t *ht);
|
228 |
|
229 |
extern int cfuhash_destroy_with_free_fn(cfuhash_table_t *ht, cfuhash_free_fn_t ff);
|
230 |
|
231 |
/* Rebuild the hash to better accomodate the number of entries. See
|
232 |
* cfuhash_set_thresholds().
|
233 |
*/
|
234 |
extern int cfuhash_rehash(cfuhash_table_t *ht);
|
235 |
|
236 |
/* Returns the number entries in the hash. */
|
237 |
extern size_t cfuhash_num_entries(cfuhash_table_t *ht);
|
238 |
|
239 |
/* Returns the number of buckets allocated for the hash. */
|
240 |
extern size_t cfuhash_num_buckets(cfuhash_table_t *ht);
|
241 |
|
242 |
/* Returns the number of buckets actually used out of the total number
|
243 |
* allocated for the hash.
|
244 |
*/
|
245 |
extern size_t cfuhash_num_buckets_used(cfuhash_table_t *ht);
|
246 |
|
247 |
/* Assumes all the keys and values are null-terminated strings and
|
248 |
* returns a bencoded string representing the hash (see
|
249 |
* http://www.bittorrent.com/protocol.html)
|
250 |
*/
|
251 |
extern char * cfuhash_bencode_strings(cfuhash_table_t *ht);
|
252 |
|
253 |
/* Locks the hash. Use this with the each and next functions for
|
254 |
* concurrency control. Note that the hash is locked automatically
|
255 |
* when doing inserts and deletes, so if you lock the hash and then
|
256 |
* try to insert something into it, you may get into a deadlock,
|
257 |
* depending on your system defaults for how mutexes work.
|
258 |
*/
|
259 |
extern int cfuhash_lock(cfuhash_table_t *ht);
|
260 |
|
261 |
/* Unlocks the hash. Use this with the each an next functions for
|
262 |
* concurrency control. The caveat for cfuhash_lcok() also applies to
|
263 |
* this function.
|
264 |
*/
|
265 |
extern int cfuhash_unlock(cfuhash_table_t *ht);
|
266 |
|
267 |
/* Pretty print the hash's key/value pairs to the stream fp. It is
|
268 |
* assumed that all the keys and values are null-terminated strings.
|
269 |
*/
|
270 |
extern int cfuhash_pretty_print(cfuhash_table_t *ht, FILE *fp);
|
271 |
|
272 |
/* These are like the _data versions of these functions, with the
|
273 |
* following exceptions:
|
274 |
* 1) They assume that the key provided is a null-terminated string.
|
275 |
* 2) They don't worry about the size of the data.
|
276 |
* 3) Returned keys or values are the return value of the function.
|
277 |
*/
|
278 |
extern void * cfuhash_get(cfuhash_table_t *ht, const char *key);
|
279 |
extern int cfuhash_exists(cfuhash_table_t *ht, const char *key);
|
280 |
extern void * cfuhash_put(cfuhash_table_t *ht, const char *key, void *data);
|
281 |
extern void * cfuhash_delete(cfuhash_table_t *ht, const char *key);
|
282 |
extern int cfuhash_each(cfuhash_table_t *ht, char **key, void **data);
|
283 |
extern int cfuhash_next(cfuhash_table_t *ht, char **key, void **data);
|
284 |
extern void **cfuhash_keys(cfuhash_table_t *ht, size_t *num_keys, int fast);
|
285 |
|
286 |
|
287 |
/* hash table flags */
|
288 |
#define CFUHASH_NOCOPY_KEYS 1 /* do not copy the key when inserting a hash entry */
|
289 |
#define CFUHASH_NO_LOCKING (1 << 1) /* do not make the hash thread-safe */
|
290 |
#define CFUHASH_FROZEN (1 << 2) /* do not rehash when the size thresholds are reached */
|
291 |
#define CFUHASH_FROZEN_UNTIL_GROWS (1 << 3) /* do not shrink the hash until it has grown */
|
292 |
#define CFUHASH_FREE_DATA (1 << 4) /* call free() on each value when the hash is destroyed */
|
293 |
#define CFUHASH_IGNORE_CASE (1 << 5) /* treat keys case-insensitively */
|
294 |
|
295 |
|
296 |
#ifdef __cplusplus
|
297 |
}
|
298 |
#endif
|
299 |
|
300 |
#endif
|