Debian Codegraph @

lib/base/dict.c

raw
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
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 NULL
76 };
77
78 static size_t
79 isprime(size_t p)
80 {
81 size_t q, i;
82
83 for(i = 2 ; i < p; i++) {
84 q = p / i;
85
86 if (i * q == p)
87 return 0;
88 if (i * i > p)
89 return 1;
90 }
91 return 1;
92 }
93
94 static size_t
95 findprime(size_t p)
96 {
97 if (p % 2 == 0)
98 p++;
99
100 while (isprime(p) == 0)
101 p += 2;
102
103 return p;
104 }
105
106 /**
107 * Allocate an array
108 *
109 * @return A new allocated array, free with heim_release()
110 */
111
112 heim_dict_t
113 heim_dict_create(size_t size)
114 {
115 heim_dict_t dict;
116
117 dict = _heim_alloc_object(&dict_object, sizeof(*dict));
118
119 dict->size = findprime(size);
120 if (dict->size == 0) {
121 heim_release(dict);
122 return NULL;
123 }
124
125 dict->tab = calloc(dict->size, sizeof(dict->tab[0]));
126 if (dict->tab == NULL) {
127 dict->size = 0;
128 heim_release(dict);
129 return NULL;
130 }
131
132 return dict;
133 }
134
135 /**
136 * Get type id of an dict
137 *
138 * @return the type id
139 */
140
141 heim_tid_t
142 heim_dict_get_type_id(void)
143 {
144 return HEIM_TID_DICT;
145 }
146
147 /* Intern search function */
148
149 static struct hashentry *
150 _search(heim_dict_t dict, heim_object_t ptr)
151 {
152 unsigned long v = heim_get_hash(ptr);
153 struct hashentry *p;
154
155 for (p = dict->tab[v % dict->size]; p != NULL; p = p->next)
156 if (heim_cmp(ptr, p->key) == 0)
157 return p;
158
159 return NULL;
160 }
161
162 /**
163 * Search for element in hash table
164 *
165 * @value dict the dict to search in
166 * @value key the key to search for
167 *
168 * @return a not-retained copy of the value for key or NULL if not found
169 */
170
171 heim_object_t
172 heim_dict_get_value(heim_dict_t dict, heim_object_t key)
173 {
174 struct hashentry *p;
175 p = _search(dict, key);
176 if (p == NULL)
177 return NULL;
178
179 return p->value;
180 }
181
182 /**
183 * Search for element in hash table
184 *
185 * @value dict the dict to search in
186 * @value key the key to search for
187 *
188 * @return a retained copy of the value for key or NULL if not found
189 */
190
191 heim_object_t
192 heim_dict_copy_value(heim_dict_t dict, heim_object_t key)
193 {
194 struct hashentry *p;
195 p = _search(dict, key);
196 if (p == NULL)
197 return NULL;
198
199 return heim_retain(p->value);
200 }
201
202 /**
203 * Add key and value to dict
204 *
205 * @value dict the dict to add too
206 * @value key the key to add
207 * @value value the value to add
208 *
209 * @return 0 if added, errno if not
210 */
211
212 int
213 heim_dict_set_value(heim_dict_t dict, heim_object_t key, heim_object_t value)
214 {
215 struct hashentry **tabptr, *h;
216
217 h = _search(dict, key);
218 if (h) {
219 heim_release(h->value);
220 h->value = heim_retain(value);
221 } else {
222 unsigned long v;
223
224 h = malloc(sizeof(*h));
225 if (h == NULL)
226 return ENOMEM;
227
228 h->key = heim_retain(key);
229 h->value = heim_retain(value);
230
231 v = heim_get_hash(key);
232
233 tabptr = &dict->tab[v % dict->size];
234 h->next = *tabptr;
235 *tabptr = h;
236 h->prev = tabptr;
237 if (h->next)
238 h->next->prev = &h->next;
239 }
240
241 return 0;
242 }
243
244 /**
245 * Delete element with key key
246 *
247 * @value dict the dict to delete from
248 * @value key the key to delete
249 */
250
251 void
252 heim_dict_delete_key(heim_dict_t dict, heim_object_t key)
253 {
254 struct hashentry *h = _search(dict, key);
255
256 if (h == NULL)
257 return;
258
259 heim_release(h->key);
260 heim_release(h->value);
261
262 if ((*(h->prev) = h->next) != NULL)
263 h->next->prev = h->prev;
264
265 free(h);
266 }
267
268 /**
269 * Do something for each element
270 *
271 * @value dict the dict to interate over
272 * @value func the function to search for
273 * @value arg argument to func
274 */
275
276 void
277 heim_dict_iterate_f(heim_dict_t dict, void *arg, heim_dict_iterator_f_t func)
278 {
279 struct hashentry **h, *g;
280
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);
284 }
285
286 #ifdef __BLOCKS__
287 /**
288 * Do something for each element
289 *
290 * @value dict the dict to interate over
291 * @value func the function to search for
292 */
293
294 void
295 heim_dict_iterate(heim_dict_t dict, void (^func)(heim_object_t, heim_object_t))
296 {
297 struct hashentry **h, *g;
298
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);
302 }
303 #endif