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