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 204196 : dict_dealloc(void *ptr)
52 : {
53 204196 : heim_dict_t dict = ptr;
54 6826 : struct hashentry **h, *g, *i;
55 :
56 1429372 : for (h = dict->tab; h < &dict->tab[dict->size]; ++h) {
57 2180810 : for (g = h[0]; g; g = i) {
58 955634 : i = g->next;
59 955634 : heim_release(g->key);
60 955634 : heim_release(g->value);
61 955634 : free(g);
62 : }
63 : }
64 204196 : free(dict->tab);
65 204196 : }
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 334974 : isprime(size_t p)
80 : {
81 11889 : size_t q, i;
82 :
83 1027904 : for(i = 2 ; i < p; i++) {
84 925806 : q = p / i;
85 :
86 925806 : if (i * q == p)
87 0 : return 0;
88 925806 : if (i * i > p)
89 224400 : return 1;
90 : }
91 98685 : return 1;
92 : }
93 :
94 : static size_t
95 334974 : findprime(size_t p)
96 : {
97 334974 : if (p % 2 == 0)
98 102098 : p++;
99 :
100 346863 : while (isprime(p) == 0)
101 0 : p += 2;
102 :
103 334974 : 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 334974 : heim_dict_create(size_t size)
114 : {
115 11889 : heim_dict_t dict;
116 :
117 334974 : dict = _heim_alloc_object(&dict_object, sizeof(*dict));
118 334974 : if (dict == NULL)
119 0 : return NULL;
120 :
121 334974 : dict->size = findprime(size);
122 334974 : if (dict->size == 0) {
123 0 : heim_release(dict);
124 0 : return NULL;
125 : }
126 :
127 334974 : dict->tab = calloc(dict->size, sizeof(dict->tab[0]));
128 334974 : if (dict->tab == NULL) {
129 0 : dict->size = 0;
130 0 : heim_release(dict);
131 0 : return NULL;
132 : }
133 :
134 323085 : 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 4949493 : _search(heim_dict_t dict, heim_object_t ptr)
153 : {
154 4949493 : uintptr_t v = heim_get_hash(ptr);
155 163603 : struct hashentry *p;
156 :
157 6112610 : for (p = dict->tab[v % dict->size]; p != NULL; p = p->next)
158 3204390 : if (heim_cmp(ptr, p->key) == 0)
159 2041273 : return p;
160 :
161 2810792 : 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 974716 : heim_dict_get_value(heim_dict_t dict, heim_object_t key)
175 : {
176 35605 : struct hashentry *p;
177 974716 : p = _search(dict, key);
178 974716 : if (p == NULL)
179 821794 : return NULL;
180 :
181 122013 : 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 2829342 : heim_dict_copy_value(heim_dict_t dict, heim_object_t key)
195 : {
196 85867 : struct hashentry *p;
197 2829342 : p = _search(dict, key);
198 2829342 : if (p == NULL)
199 943139 : return NULL;
200 :
201 1859475 : 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 1145435 : heim_dict_set_value(heim_dict_t dict, heim_object_t key, heim_object_t value)
216 : {
217 42131 : struct hashentry **tabptr, *h;
218 :
219 1145435 : h = _search(dict, key);
220 1145435 : if (h) {
221 59785 : heim_release(h->value);
222 59785 : h->value = heim_retain(value);
223 : } else {
224 39791 : uintptr_t v;
225 :
226 1085650 : h = malloc(sizeof(*h));
227 1085650 : if (h == NULL)
228 0 : return ENOMEM;
229 :
230 1085650 : h->key = heim_retain(key);
231 1085650 : h->value = heim_retain(value);
232 :
233 1085650 : v = heim_get_hash(key);
234 :
235 1085650 : tabptr = &dict->tab[v % dict->size];
236 1085650 : h->next = *tabptr;
237 1085650 : *tabptr = h;
238 1085650 : h->prev = tabptr;
239 1085650 : if (h->next)
240 307538 : h->next->prev = &h->next;
241 : }
242 :
243 1103304 : 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 1448295 : heim_dict_iterate_f(heim_dict_t dict, void *arg, heim_dict_iterator_f_t func)
280 : {
281 43789 : struct hashentry **h, *g;
282 :
283 17379540 : for (h = dict->tab; h < &dict->tab[dict->size]; ++h)
284 18233076 : for (g = *h; g; g = g->next)
285 2301831 : func(g->key, g->value, arg);
286 1448295 : }
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
|
