Line data Source code
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 HEIM_CALLCONV
51 142046 : dict_dealloc(void *ptr)
52 : {
53 142046 : heim_dict_t dict = ptr;
54 : struct hashentry **h, *g, *i;
55 :
56 994322 : for (h = dict->tab; h < &dict->tab[dict->size]; ++h) {
57 1473209 : for (g = h[0]; g; g = i) {
58 620933 : i = g->next;
59 620933 : heim_release(g->key);
60 620933 : heim_release(g->value);
61 620933 : free(g);
62 : }
63 : }
64 142046 : free(dict->tab);
65 142046 : }
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 207258 : isprime(size_t p)
80 : {
81 : size_t q, i;
82 :
83 592505 : for(i = 2 ; i < p; i++) {
84 521482 : q = p / i;
85 :
86 521482 : if (i * q == p)
87 0 : return 0;
88 521482 : if (i * i > p)
89 136235 : return 1;
90 : }
91 71023 : return 1;
92 : }
93 :
94 : static size_t
95 207258 : findprime(size_t p)
96 : {
97 207258 : if (p % 2 == 0)
98 71023 : p++;
99 :
100 414516 : while (isprime(p) == 0)
101 0 : p += 2;
102 :
103 207258 : 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 207258 : heim_dict_create(size_t size)
114 : {
115 : heim_dict_t dict;
116 :
117 207258 : dict = _heim_alloc_object(&dict_object, sizeof(*dict));
118 207258 : if (dict == NULL)
119 0 : return NULL;
120 :
121 207258 : dict->size = findprime(size);
122 207258 : if (dict->size == 0) {
123 0 : heim_release(dict);
124 0 : return NULL;
125 : }
126 :
127 207258 : dict->tab = calloc(dict->size, sizeof(dict->tab[0]));
128 207258 : if (dict->tab == NULL) {
129 0 : dict->size = 0;
130 0 : heim_release(dict);
131 0 : return NULL;
132 : }
133 :
134 207258 : return dict;
135 : }
136 :
137 : /**
138 : * Get type id of an dict
139 : *
140 : * @return the type id
141 : */
142 :
143 : heim_tid_t
144 0 : heim_dict_get_type_id(void)
145 : {
146 0 : return HEIM_TID_DICT;
147 : }
148 :
149 : /* Intern search function */
150 :
151 : static struct hashentry *
152 3115990 : _search(heim_dict_t dict, heim_object_t ptr)
153 : {
154 3115990 : uintptr_t v = heim_get_hash(ptr);
155 : struct hashentry *p;
156 :
157 3749638 : for (p = dict->tab[v % dict->size]; p != NULL; p = p->next)
158 1921200 : if (heim_cmp(ptr, p->key) == 0)
159 1287552 : return p;
160 :
161 1828438 : 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
174 563803 : heim_dict_get_value(heim_dict_t dict, heim_object_t key)
175 : {
176 : struct hashentry *p;
177 563803 : p = _search(dict, key);
178 563803 : if (p == NULL)
179 488399 : return NULL;
180 :
181 75404 : 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
194 1848259 : heim_dict_copy_value(heim_dict_t dict, heim_object_t key)
195 : {
196 : struct hashentry *p;
197 1848259 : p = _search(dict, key);
198 1848259 : if (p == NULL)
199 654520 : return NULL;
200 :
201 1193739 : 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
215 703928 : heim_dict_set_value(heim_dict_t dict, heim_object_t key, heim_object_t value)
216 : {
217 : struct hashentry **tabptr, *h;
218 :
219 703928 : h = _search(dict, key);
220 703928 : if (h) {
221 18409 : heim_release(h->value);
222 18409 : h->value = heim_retain(value);
223 : } else {
224 : uintptr_t v;
225 :
226 685519 : h = malloc(sizeof(*h));
227 685519 : if (h == NULL)
228 0 : return ENOMEM;
229 :
230 685519 : h->key = heim_retain(key);
231 685519 : h->value = heim_retain(value);
232 :
233 685519 : v = heim_get_hash(key);
234 :
235 685519 : tabptr = &dict->tab[v % dict->size];
236 685519 : h->next = *tabptr;
237 685519 : *tabptr = h;
238 685519 : h->prev = tabptr;
239 685519 : if (h->next)
240 187843 : h->next->prev = &h->next;
241 : }
242 :
243 703928 : 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
254 0 : heim_dict_delete_key(heim_dict_t dict, heim_object_t key)
255 : {
256 0 : struct hashentry *h = _search(dict, key);
257 :
258 0 : if (h == NULL)
259 0 : return;
260 :
261 0 : heim_release(h->key);
262 0 : heim_release(h->value);
263 :
264 0 : if ((*(h->prev) = h->next) != NULL)
265 0 : h->next->prev = h->prev;
266 :
267 0 : 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
279 960145 : heim_dict_iterate_f(heim_dict_t dict, void *arg, heim_dict_iterator_f_t func)
280 : {
281 : struct hashentry **h, *g;
282 :
283 11521740 : for (h = dict->tab; h < &dict->tab[dict->size]; ++h)
284 12071650 : for (g = *h; g; g = g->next)
285 1510055 : func(g->key, g->value, arg);
286 960145 : }
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
|
