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