/[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 - (hide 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 zoff99 31 /**
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