5 * This file is part of Maemo Mapper.
7 * Maemo Mapper is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
12 * Maemo Mapper is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with Maemo Mapper. If not, see <http://www.gnu.org/licenses/>.
21 * Parts of this code have been ported from Xastir by Rob Williams (10 Aug 2008):
23 * * XASTIR, Amateur Station Tracking and Information Reporting
24 * Copyright (C) 1999,2000 Frank Giannandrea
25 * Copyright (C) 2000-2007 The Xastir Group
26 * Copyright (C) 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk>
35 #ifndef __HASHTABLE_CWC22_H__
36 #define __HASHTABLE_CWC22_H__
42 * struct hashtable *h;
44 * struct some_value *v;
46 * static unsigned int hash_from_key_fn( void *k );
47 * static int keys_equal_fn ( void *key1, void *key2 );
49 * h = create_hashtable(16, hash_from_key_fn, keys_equal_fn);
50 * k = (struct some_key *) malloc(sizeof(struct some_key));
51 * v = (struct some_value *) malloc(sizeof(struct some_value));
53 * (initialise k and v to suitable values)
55 * if (! hashtable_insert(h,k,v) )
58 * if (NULL == (found = hashtable_search(h,k) ))
59 * { printf("not found!"); }
61 * if (NULL == (found = hashtable_remove(h,k) ))
62 * { printf("Not found\n"); }
66 /* Macros may be used to define type-safe(r) hashtable access functions, with
67 * methods specialized to take known key and value types as parameters.
71 * Insert this at the start of your file:
73 * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value);
74 * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value);
75 * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value);
77 * This defines the functions 'insert_some', 'search_some' and 'remove_some'.
78 * These operate just like hashtable_insert etc., with the same parameters,
79 * but their function signatures have 'struct some_key *' rather than
80 * 'void *', and hence can generate compile time errors if your program is
81 * supplying incorrect data as a key (and similarly for value).
83 * Note that the hash and key equality functions passed to create_hashtable
84 * still take 'void *' parameters instead of 'some key *'. This shouldn't be
85 * a difficult issue as they're only defined and passed once, and the other
86 * functions will ensure that only valid keys are supplied to them.
88 * The cost for this checking is increased code size and runtime overhead
89 * - if performance is important, it may be worth switching back to the
90 * unsafe methods once your program has been debugged with the safe methods.
91 * This just requires switching to some simple alternative defines - eg:
92 * #define insert_some hashtable_insert
96 /*****************************************************************************
99 * @name create_hashtable
100 * @param minsize minimum initial size of hashtable
101 * @param hashfunction function for hashing keys
102 * @param key_eq_fn function for determining key equality
103 * @return newly created hashtable or NULL on failure
107 create_hashtable(unsigned int minsize,
108 unsigned int (*hashfunction) (void*),
109 int (*key_eq_fn) (void*,void*));
111 /*****************************************************************************
114 * @name hashtable_insert
115 * @param h the hashtable to insert into
116 * @param k the key - hashtable claims ownership and will free on removal
117 * @param v the value - does not claim ownership
118 * @return non-zero for successful insertion
120 * This function will cause the table to expand if the insertion would take
121 * the ratio of entries to table size over the maximum load factor.
123 * This function does not check for repeated insertions with a duplicate key.
124 * The value returned when using a duplicate key is undefined -- when
125 * the hashtable changes size, the order of retrieval of duplicate key
126 * entries is reversed.
127 * If in doubt, remove before insert.
131 hashtable_insert(struct hashtable *h, void *k, void *v);
133 #define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \
134 int fnname (struct hashtable *h, keytype *k, valuetype *v) \
136 return hashtable_insert(h,k,v); \
139 /*****************************************************************************
142 * @name hashtable_search
143 * @param h the hashtable to search
144 * @param k the key to search for - does not claim ownership
145 * @return the value associated with the key, or NULL if none found
149 hashtable_search(struct hashtable *h, void *k);
151 #define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \
152 valuetype * fnname (struct hashtable *h, keytype *k) \
154 return (valuetype *) (hashtable_search(h,k)); \
157 /*****************************************************************************
160 * @name hashtable_remove
161 * @param h the hashtable to remove the item from
162 * @param k the key to search for - does not claim ownership
163 * @return the value associated with the key, or NULL if none found
166 void * /* returns value */
167 hashtable_remove(struct hashtable *h, void *k);
169 #define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype) \
170 valuetype * fnname (struct hashtable *h, keytype *k) \
172 return (valuetype *) (hashtable_remove(h,k)); \
176 /*****************************************************************************
179 * @name hashtable_count
180 * @param h the hashtable
181 * @return the number of items stored in the hashtable
184 hashtable_count(struct hashtable *h);
187 /*****************************************************************************
190 * @name hashtable_destroy
191 * @param h the hashtable
192 * @param free_values whether to call 'free' on the remaining values
196 hashtable_destroy(struct hashtable *h, int free_values);
198 #endif /* __HASHTABLE_CWC22_H__ */
200 #endif // INCLUDE_APRS
203 * Copyright (C) 2002 Christopher Clark <firstname.lastname@cl.cam.ac.uk>
205 * Permission is hereby granted, free of charge, to any person obtaining a copy
206 * of this software and associated documentation files (the "Software"), to
207 * deal in the Software without restriction, including without limitation the
208 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
209 * sell copies of the Software, and to permit persons to whom the Software is
210 * furnished to do so, subject to the following conditions:
212 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
213 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
214 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
215 * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
216 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
217 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.