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
38struct hashentry {
39    struct hashentry **prev;
40    struct hashentry *next;
41    heim_object_t key;
42    heim_object_t value;
43};
44
45struct heim_dict_data {
46    size_t size;
47    struct hashentry **tab;
48};
49
50static void
51dict_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
67struct 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
77static size_t
78isprime(size_t p)
79{
80    size_t 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
93static size_t
94findprime(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
111heim_dict_t
112heim_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
140heim_tid_t
141heim_dict_get_type_id(void)
142{
143    return HEIM_TID_DICT;
144}
145
146/* Intern search function */
147
148static 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
170heim_object_t
171heim_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
191int
192heim_dict_set_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
230void
231heim_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
255void
256heim_dict_iterate_f(heim_dict_t dict, void *arg, heim_dict_iterator_f_t func)
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
273void
274heim_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
283