2 * Copyright (c) 2002, 1997 Kungliga Tekniska Högskolan
3 * (Royal Institute of Technology, Stockholm, Sweden).
6 * Portions Copyright (c) 2010 Apple Inc. All rights reserved.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
19 * 3. Neither the name of the Institute nor the names of its contributors
20 * may be used to endorse or promote products derived from this software
21 * without specific prior written permission.
23 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
39 struct hashentry **prev;
40 struct hashentry *next;
45 struct heim_dict_data {
47 struct hashentry **tab;
51 dict_dealloc(void *ptr)
53 heim_dict_t dict = ptr;
54 struct hashentry **h, *g, *i;
56 for (h = dict->tab; h < &dict->tab[dict->size]; ++h) {
57 for (g = h[0]; g; g = i) {
60 heim_release(g->value);
67 struct heim_type_data dict_object = {
83 for(i = 2 ; i < p; i++) {
100 while (isprime(p) == 0)
109 * @return A new allocated array, free with heim_release()
113 heim_dict_create(size_t size)
117 dict = _heim_alloc_object(&dict_object, sizeof(*dict));
119 dict->size = findprime(size);
120 if (dict->size == 0) {
125 dict->tab = calloc(dict->size, sizeof(dict->tab[0]));
126 if (dict->tab == NULL) {
136 * Get type id of an dict
138 * @return the type id
142 heim_dict_get_type_id(void)
144 return HEIM_TID_DICT;
147 /* Intern search function */
149 static struct hashentry *
150 _search(heim_dict_t dict, heim_object_t ptr)
152 unsigned long v = heim_get_hash(ptr);
155 for (p = dict->tab[v % dict->size]; p != NULL; p = p->next)
156 if (heim_cmp(ptr, p->key) == 0)
163 * Search for element in hash table
165 * @value dict the dict to search in
166 * @value key the key to search for
168 * @return a not-retained copy of the value for key or NULL if not found
172 heim_dict_get_value(heim_dict_t dict, heim_object_t key)
175 p = _search(dict, key);
183 * Search for element in hash table
185 * @value dict the dict to search in
186 * @value key the key to search for
188 * @return a retained copy of the value for key or NULL if not found
192 heim_dict_copy_value(heim_dict_t dict, heim_object_t key)
195 p = _search(dict, key);
199 return heim_retain(p->value);
203 * Add key and value to dict
205 * @value dict the dict to add too
206 * @value key the key to add
207 * @value value the value to add
209 * @return 0 if added, errno if not
213 heim_dict_set_value(heim_dict_t dict, heim_object_t key, heim_object_t value)
215 struct hashentry **tabptr, *h;
217 h = _search(dict, key);
219 heim_release(h->value);
220 h->value = heim_retain(value);
224 h = malloc(sizeof(*h));
228 h->key = heim_retain(key);
229 h->value = heim_retain(value);
231 v = heim_get_hash(key);
233 tabptr = &dict->tab[v % dict->size];
238 h->next->prev = &h->next;
245 * Delete element with key key
247 * @value dict the dict to delete from
248 * @value key the key to delete
252 heim_dict_delete_key(heim_dict_t dict, heim_object_t key)
254 struct hashentry *h = _search(dict, key);
259 heim_release(h->key);
260 heim_release(h->value);
262 if ((*(h->prev) = h->next) != NULL)
263 h->next->prev = h->prev;
269 * Do something for each element
271 * @value dict the dict to interate over
272 * @value func the function to search for
273 * @value arg argument to func
277 heim_dict_iterate_f(heim_dict_t dict, void *arg, heim_dict_iterator_f_t func)
279 struct hashentry **h, *g;
281 for (h = dict->tab; h < &dict->tab[dict->size]; ++h)
282 for (g = *h; g; g = g->next)
283 func(g->key, g->value, arg);
288 * Do something for each element
290 * @value dict the dict to interate over
291 * @value func the function to search for
295 heim_dict_iterate(heim_dict_t dict, void (^func)(heim_object_t, heim_object_t))
297 struct hashentry **h, *g;
299 for (h = dict->tab; h < &dict->tab[dict->size]; ++h)
300 for (g = *h; g; g = g->next)
301 func(g->key, g->value);