1 /* $NetBSD: dict.c,v 1.2 2017/01/28 21:31:45 christos Exp $ */
2
3 /*
4 * Copyright (c) 2002, 1997 Kungliga Tekniska Högskolan
5 * (Royal Institute of Technology, Stockholm, Sweden).
6 * All rights reserved.
7 *
8 * Portions Copyright (c) 2010 Apple Inc. All rights reserved.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 *
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 *
17 * 2. Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in the
19 * documentation and/or other materials provided with the distribution.
20 *
21 * 3. Neither the name of the Institute nor the names of its contributors
22 * may be used to endorse or promote products derived from this software
23 * without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35 * SUCH DAMAGE.
36 */
37
38 #include "baselocl.h"
39
40 struct hashentry {
41 struct hashentry **prev;
42 struct hashentry *next;
43 heim_object_t key;
44 heim_object_t value;
45 };
46
47 struct heim_dict_data {
48 size_t size;
49 struct hashentry **tab;
50 };
51
52 static void
dict_dealloc(void * ptr)53 dict_dealloc(void *ptr)
54 {
55 heim_dict_t dict = ptr;
56 struct hashentry **h, *g, *i;
57
58 for (h = dict->tab; h < &dict->tab[dict->size]; ++h) {
59 for (g = h[0]; g; g = i) {
60 i = g->next;
61 heim_release(g->key);
62 heim_release(g->value);
63 free(g);
64 }
65 }
66 free(dict->tab);
67 }
68
69 struct heim_type_data dict_object = {
70 HEIM_TID_DICT,
71 "dict-object",
72 NULL,
73 dict_dealloc,
74 NULL,
75 NULL,
76 NULL,
77 NULL
78 };
79
80 static size_t
isprime(size_t p)81 isprime(size_t p)
82 {
83 size_t q, i;
84
85 for(i = 2 ; i < p; i++) {
86 q = p / i;
87
88 if (i * q == p)
89 return 0;
90 if (i * i > p)
91 return 1;
92 }
93 return 1;
94 }
95
96 static size_t
findprime(size_t p)97 findprime(size_t p)
98 {
99 if (p % 2 == 0)
100 p++;
101
102 while (isprime(p) == 0)
103 p += 2;
104
105 return p;
106 }
107
108 /**
109 * Allocate an array
110 *
111 * @return A new allocated array, free with heim_release()
112 */
113
114 heim_dict_t
heim_dict_create(size_t size)115 heim_dict_create(size_t size)
116 {
117 heim_dict_t dict;
118
119 dict = _heim_alloc_object(&dict_object, sizeof(*dict));
120
121 dict->size = findprime(size);
122 if (dict->size == 0) {
123 heim_release(dict);
124 return NULL;
125 }
126
127 dict->tab = calloc(dict->size, sizeof(dict->tab[0]));
128 if (dict->tab == NULL) {
129 dict->size = 0;
130 heim_release(dict);
131 return NULL;
132 }
133
134 return dict;
135 }
136
137 /**
138 * Get type id of an dict
139 *
140 * @return the type id
141 */
142
143 heim_tid_t
heim_dict_get_type_id(void)144 heim_dict_get_type_id(void)
145 {
146 return HEIM_TID_DICT;
147 }
148
149 /* Intern search function */
150
151 static struct hashentry *
_search(heim_dict_t dict,heim_object_t ptr)152 _search(heim_dict_t dict, heim_object_t ptr)
153 {
154 unsigned long v = heim_get_hash(ptr);
155 struct hashentry *p;
156
157 for (p = dict->tab[v % dict->size]; p != NULL; p = p->next)
158 if (heim_cmp(ptr, p->key) == 0)
159 return p;
160
161 return NULL;
162 }
163
164 /**
165 * Search for element in hash table
166 *
167 * @value dict the dict to search in
168 * @value key the key to search for
169 *
170 * @return a not-retained copy of the value for key or NULL if not found
171 */
172
173 heim_object_t
heim_dict_get_value(heim_dict_t dict,heim_object_t key)174 heim_dict_get_value(heim_dict_t dict, heim_object_t key)
175 {
176 struct hashentry *p;
177 p = _search(dict, key);
178 if (p == NULL)
179 return NULL;
180
181 return p->value;
182 }
183
184 /**
185 * Search for element in hash table
186 *
187 * @value dict the dict to search in
188 * @value key the key to search for
189 *
190 * @return a retained copy of the value for key or NULL if not found
191 */
192
193 heim_object_t
heim_dict_copy_value(heim_dict_t dict,heim_object_t key)194 heim_dict_copy_value(heim_dict_t dict, heim_object_t key)
195 {
196 struct hashentry *p;
197 p = _search(dict, key);
198 if (p == NULL)
199 return NULL;
200
201 return heim_retain(p->value);
202 }
203
204 /**
205 * Add key and value to dict
206 *
207 * @value dict the dict to add too
208 * @value key the key to add
209 * @value value the value to add
210 *
211 * @return 0 if added, errno if not
212 */
213
214 int
heim_dict_set_value(heim_dict_t dict,heim_object_t key,heim_object_t value)215 heim_dict_set_value(heim_dict_t dict, heim_object_t key, heim_object_t value)
216 {
217 struct hashentry **tabptr, *h;
218
219 h = _search(dict, key);
220 if (h) {
221 heim_release(h->value);
222 h->value = heim_retain(value);
223 } else {
224 unsigned long v;
225
226 h = malloc(sizeof(*h));
227 if (h == NULL)
228 return ENOMEM;
229
230 h->key = heim_retain(key);
231 h->value = heim_retain(value);
232
233 v = heim_get_hash(key);
234
235 tabptr = &dict->tab[v % dict->size];
236 h->next = *tabptr;
237 *tabptr = h;
238 h->prev = tabptr;
239 if (h->next)
240 h->next->prev = &h->next;
241 }
242
243 return 0;
244 }
245
246 /**
247 * Delete element with key key
248 *
249 * @value dict the dict to delete from
250 * @value key the key to delete
251 */
252
253 void
heim_dict_delete_key(heim_dict_t dict,heim_object_t key)254 heim_dict_delete_key(heim_dict_t dict, heim_object_t key)
255 {
256 struct hashentry *h = _search(dict, key);
257
258 if (h == NULL)
259 return;
260
261 heim_release(h->key);
262 heim_release(h->value);
263
264 if ((*(h->prev) = h->next) != NULL)
265 h->next->prev = h->prev;
266
267 free(h);
268 }
269
270 /**
271 * Do something for each element
272 *
273 * @value dict the dict to interate over
274 * @value func the function to search for
275 * @value arg argument to func
276 */
277
278 void
heim_dict_iterate_f(heim_dict_t dict,void * arg,heim_dict_iterator_f_t func)279 heim_dict_iterate_f(heim_dict_t dict, void *arg, heim_dict_iterator_f_t func)
280 {
281 struct hashentry **h, *g;
282
283 for (h = dict->tab; h < &dict->tab[dict->size]; ++h)
284 for (g = *h; g; g = g->next)
285 func(g->key, g->value, arg);
286 }
287
288 #ifdef __BLOCKS__
289 /**
290 * Do something for each element
291 *
292 * @value dict the dict to interate over
293 * @value func the function to search for
294 */
295
296 void
297 heim_dict_iterate(heim_dict_t dict, void (^func)(heim_object_t, heim_object_t))
298 {
299 struct hashentry **h, *g;
300
301 for (h = dict->tab; h < &dict->tab[dict->size]; ++h)
302 for (g = *h; g; g = g->next)
303 func(g->key, g->value);
304 }
305 #endif
306