heimdal Extra files required for merge up to current heimdal
[sfrench/samba-autobuild/.git] / source4 / heimdal / base / dict.c
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 dict_dealloc(void *ptr)
52 {
53     heim_dict_t dict = ptr;
54     struct hashentry **h, *g, *i;
55
56     for (h = dict->tab; h < &dict->tab[dict->size]; ++h) {
57         for (g = h[0]; g; g = i) {
58             i = g->next;
59             heim_release(g->key);
60             heim_release(g->value);
61             free(g);
62         }
63     }
64     free(dict->tab);
65 }
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 isprime(size_t p)
79 {
80     int q, i;
81
82     for(i = 2 ; i < p; i++) {
83         q = p / i;
84
85         if (i * q == p)
86             return 0;
87         if (i * i > p)
88             return 1;
89     }
90     return 1;
91 }
92
93 static size_t
94 findprime(size_t p)
95 {
96     if (p % 2 == 0)
97         p++;
98
99     while (isprime(p) == 0)
100         p += 2;
101
102     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 heim_dict_create(size_t size)
113 {
114     heim_dict_t dict;
115
116     dict = _heim_alloc_object(&dict_object, sizeof(*dict));
117
118     dict->size = findprime(size);
119     if (dict->size == 0) {
120         heim_release(dict);
121         return NULL;
122     }
123
124     dict->tab = calloc(dict->size, sizeof(dict->tab[0]));
125     if (dict->tab == NULL) {
126         dict->size = 0;
127         heim_release(dict);
128         return NULL;
129     }
130
131     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 heim_dict_get_type_id(void)
142 {
143     return HEIM_TID_DICT;
144 }
145
146 /* Intern search function */
147
148 static struct hashentry *
149 _search(heim_dict_t dict, heim_object_t ptr)
150 {
151     unsigned long v = heim_get_hash(ptr);
152     struct hashentry *p;
153
154     for (p = dict->tab[v % dict->size]; p != NULL; p = p->next)
155         if (heim_cmp(ptr, p->key) == 0)
156             return p;
157
158     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 heim_dict_copy_value(heim_dict_t dict, heim_object_t key)
172 {
173     struct hashentry *p;
174     p = _search(dict, key);
175     if (p == NULL)
176         return NULL;
177
178     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 heim_dict_add_value(heim_dict_t dict, heim_object_t key, heim_object_t value)
193 {
194     struct hashentry **tabptr, *h;
195
196     h = _search(dict, key);
197     if (h) {
198         heim_release(h->value);
199         h->value = heim_retain(value);
200     } else {
201         unsigned long v;
202
203         h = malloc(sizeof(*h));
204         if (h == NULL)
205             return ENOMEM;
206
207         h->key = heim_retain(key);
208         h->value = heim_retain(value);
209
210         v = heim_get_hash(key);
211
212         tabptr = &dict->tab[v % dict->size];
213         h->next = *tabptr;
214         *tabptr = h;
215         h->prev = tabptr;
216         if (h->next)
217             h->next->prev = &h->next;
218     }
219
220     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 heim_dict_delete_key(heim_dict_t dict, heim_object_t key)
232 {
233     struct hashentry *h = _search(dict, key);
234
235     if (h == NULL)
236         return;
237
238     heim_release(h->key);
239     heim_release(h->value);
240
241     if ((*(h->prev) = h->next) != NULL)
242         h->next->prev = h->prev;
243
244     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 heim_dict_iterate_f(heim_dict_t dict, heim_dict_iterator_f_t func, void *arg)
257 {
258     struct hashentry **h, *g;
259
260     for (h = dict->tab; h < &dict->tab[dict->size]; ++h)
261         for (g = *h; g; g = g->next)
262             func(g->key, g->value, arg);
263 }
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