1 /*
2 * Copyright (c) 2002, 1997 Kungliga Tekniska Högskolan
3 * (Royal Institute of Technology, Stockholm, Sweden).
4 * All rights reserved.
5 *
6 * Portions Copyright (c) 2010 Apple Inc. All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 *
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 *
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.
18 *
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.
22 *
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
33 * SUCH DAMAGE.
34 */
35
36 #include "baselocl.h"
37
38 struct hashentry {
39 struct hashentry **prev;
40 struct hashentry *next;
41 heim_object_t key;
42 heim_object_t value;
43 };
44
45 struct heim_dict_data {
46 size_t size;
47 struct hashentry **tab;
48 };
49
50 static void
dict_dealloc(void * ptr)51 dict_dealloc(void *ptr)
52 {
53 heim_dict_t dict = ptr;
54 struct hashentry **h, *g, *i;
55
56 for (h = dict->tab; h < &dict->tab[dict->size]; ++h) {
57 for (g = h[0]; g; g = i) {
58 i = g->next;
59 heim_release(g->key);
60 heim_release(g->value);
61 free(g);
62 }
63 }
64 free(dict->tab);
65 }
66
67 struct heim_type_data dict_object = {
68 HEIM_TID_DICT,
69 "dict-object",
70 NULL,
71 dict_dealloc,
72 NULL,
73 NULL,
74 NULL
75 };
76
77 static size_t
isprime(size_t p)78 isprime(size_t p)
79 {
80 size_t q, i;
81
82 for(i = 2 ; i < p; i++) {
83 q = p / i;
84
85 if (i * q == p)
86 return 0;
87 if (i * i > p)
88 return 1;
89 }
90 return 1;
91 }
92
93 static size_t
findprime(size_t p)94 findprime(size_t p)
95 {
96 if (p % 2 == 0)
97 p++;
98
99 while (isprime(p) == 0)
100 p += 2;
101
102 return p;
103 }
104
105 /**
106 * Allocate an array
107 *
108 * @return A new allocated array, free with heim_release()
109 */
110
111 heim_dict_t
heim_dict_create(size_t size)112 heim_dict_create(size_t size)
113 {
114 heim_dict_t dict;
115
116 dict = _heim_alloc_object(&dict_object, sizeof(*dict));
117
118 dict->size = findprime(size);
119 if (dict->size == 0) {
120 heim_release(dict);
121 return NULL;
122 }
123
124 dict->tab = calloc(dict->size, sizeof(dict->tab[0]));
125 if (dict->tab == NULL) {
126 dict->size = 0;
127 heim_release(dict);
128 return NULL;
129 }
130
131 return dict;
132 }
133
134 /**
135 * Get type id of an dict
136 *
137 * @return the type id
138 */
139
140 heim_tid_t
heim_dict_get_type_id(void)141 heim_dict_get_type_id(void)
142 {
143 return HEIM_TID_DICT;
144 }
145
146 /* Intern search function */
147
148 static struct hashentry *
_search(heim_dict_t dict,heim_object_t ptr)149 _search(heim_dict_t dict, heim_object_t ptr)
150 {
151 unsigned long v = heim_get_hash(ptr);
152 struct hashentry *p;
153
154 for (p = dict->tab[v % dict->size]; p != NULL; p = p->next)
155 if (heim_cmp(ptr, p->key) == 0)
156 return p;
157
158 return NULL;
159 }
160
161 /**
162 * Search for element in hash table
163 *
164 * @value dict the dict to search in
165 * @value key the key to search for
166 *
167 * @return a retained copy of the value for key or NULL if not found
168 */
169
170 heim_object_t
heim_dict_copy_value(heim_dict_t dict,heim_object_t key)171 heim_dict_copy_value(heim_dict_t dict, heim_object_t key)
172 {
173 struct hashentry *p;
174 p = _search(dict, key);
175 if (p == NULL)
176 return NULL;
177
178 return heim_retain(p->value);
179 }
180
181 /**
182 * Add key and value to dict
183 *
184 * @value dict the dict to add too
185 * @value key the key to add
186 * @value value the value to add
187 *
188 * @return 0 if added, errno if not
189 */
190
191 int
heim_dict_add_value(heim_dict_t dict,heim_object_t key,heim_object_t value)192 heim_dict_add_value(heim_dict_t dict, heim_object_t key, heim_object_t value)
193 {
194 struct hashentry **tabptr, *h;
195
196 h = _search(dict, key);
197 if (h) {
198 heim_release(h->value);
199 h->value = heim_retain(value);
200 } else {
201 unsigned long v;
202
203 h = malloc(sizeof(*h));
204 if (h == NULL)
205 return ENOMEM;
206
207 h->key = heim_retain(key);
208 h->value = heim_retain(value);
209
210 v = heim_get_hash(key);
211
212 tabptr = &dict->tab[v % dict->size];
213 h->next = *tabptr;
214 *tabptr = h;
215 h->prev = tabptr;
216 if (h->next)
217 h->next->prev = &h->next;
218 }
219
220 return 0;
221 }
222
223 /**
224 * Delete element with key key
225 *
226 * @value dict the dict to delete from
227 * @value key the key to delete
228 */
229
230 void
heim_dict_delete_key(heim_dict_t dict,heim_object_t key)231 heim_dict_delete_key(heim_dict_t dict, heim_object_t key)
232 {
233 struct hashentry *h = _search(dict, key);
234
235 if (h == NULL)
236 return;
237
238 heim_release(h->key);
239 heim_release(h->value);
240
241 if ((*(h->prev) = h->next) != NULL)
242 h->next->prev = h->prev;
243
244 free(h);
245 }
246
247 /**
248 * Do something for each element
249 *
250 * @value dict the dict to interate over
251 * @value func the function to search for
252 * @value arg argument to func
253 */
254
255 void
heim_dict_iterate_f(heim_dict_t dict,heim_dict_iterator_f_t func,void * arg)256 heim_dict_iterate_f(heim_dict_t dict, heim_dict_iterator_f_t func, void *arg)
257 {
258 struct hashentry **h, *g;
259
260 for (h = dict->tab; h < &dict->tab[dict->size]; ++h)
261 for (g = *h; g; g = g->next)
262 func(g->key, g->value, arg);
263 }
264
265 #ifdef __BLOCKS__
266 /**
267 * Do something for each element
268 *
269 * @value dict the dict to interate over
270 * @value func the function to search for
271 */
272
273 void
274 heim_dict_iterate(heim_dict_t dict, void (^func)(heim_object_t, heim_object_t))
275 {
276 struct hashentry **h, *g;
277
278 for (h = dict->tab; h < &dict->tab[dict->size]; ++h)
279 for (g = *h; g; g = g->next)
280 func(g->key, g->value);
281 }
282 #endif
283