/[zanavi_public1]/navit/navit/maptool/cfuhash.h
ZANavi

Contents of /navit/navit/maptool/cfuhash.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 31 - (show annotations) (download)
Mon Feb 4 17:41:59 2013 UTC (11 years, 1 month ago) by zoff99
File MIME type: text/plain
File size: 12729 byte(s)
new map version, lots of fixes and experimental new features
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

   
Visit the ZANavi Wiki