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