1 /* $NetBSD: dict.c,v 1.1.1.1 2011/04/13 18:14:32 elric Exp $ */ 2 3 /* 4 * Copyright (c) 2002, 1997 Kungliga Tekniska Högskolan 5 * (Royal Institute of Technology, Stockholm, Sweden). 6 * All rights reserved. 7 * 8 * Portions Copyright (c) 2010 Apple Inc. All rights reserved. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 14 * 1. Redistributions of source code must retain the above copyright 15 * notice, this list of conditions and the following disclaimer. 16 * 17 * 2. Redistributions in binary form must reproduce the above copyright 18 * notice, this list of conditions and the following disclaimer in the 19 * documentation and/or other materials provided with the distribution. 20 * 21 * 3. Neither the name of the Institute nor the names of its contributors 22 * may be used to endorse or promote products derived from this software 23 * without specific prior written permission. 24 * 25 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND 26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 28 * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE 29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 35 * SUCH DAMAGE. 36 */ 37 38 #include "baselocl.h" 39 40 struct hashentry { 41 struct hashentry **prev; 42 struct hashentry *next; 43 heim_object_t key; 44 heim_object_t value; 45 }; 46 47 struct heim_dict_data { 48 size_t size; 49 struct hashentry **tab; 50 }; 51 52 static void 53 dict_dealloc(void *ptr) 54 { 55 heim_dict_t dict = ptr; 56 struct hashentry **h, *g, *i; 57 58 for (h = dict->tab; h < &dict->tab[dict->size]; ++h) { 59 for (g = h[0]; g; g = i) { 60 i = g->next; 61 heim_release(g->key); 62 heim_release(g->value); 63 free(g); 64 } 65 } 66 free(dict->tab); 67 } 68 69 struct heim_type_data dict_object = { 70 HEIM_TID_DICT, 71 "dict-object", 72 NULL, 73 dict_dealloc, 74 NULL, 75 NULL, 76 NULL 77 }; 78 79 static size_t 80 isprime(size_t p) 81 { 82 int q, i; 83 84 for(i = 2 ; i < p; i++) { 85 q = p / i; 86 87 if (i * q == p) 88 return 0; 89 if (i * i > p) 90 return 1; 91 } 92 return 1; 93 } 94 95 static size_t 96 findprime(size_t p) 97 { 98 if (p % 2 == 0) 99 p++; 100 101 while (isprime(p) == 0) 102 p += 2; 103 104 return p; 105 } 106 107 /** 108 * Allocate an array 109 * 110 * @return A new allocated array, free with heim_release() 111 */ 112 113 heim_dict_t 114 heim_dict_create(size_t size) 115 { 116 heim_dict_t dict; 117 118 dict = _heim_alloc_object(&dict_object, sizeof(*dict)); 119 120 dict->size = findprime(size); 121 if (dict->size == 0) { 122 heim_release(dict); 123 return NULL; 124 } 125 126 dict->tab = calloc(dict->size, sizeof(dict->tab[0])); 127 if (dict->tab == NULL) { 128 dict->size = 0; 129 heim_release(dict); 130 return NULL; 131 } 132 133 return dict; 134 } 135 136 /** 137 * Get type id of an dict 138 * 139 * @return the type id 140 */ 141 142 heim_tid_t 143 heim_dict_get_type_id(void) 144 { 145 return HEIM_TID_DICT; 146 } 147 148 /* Intern search function */ 149 150 static struct hashentry * 151 _search(heim_dict_t dict, heim_object_t ptr) 152 { 153 unsigned long v = heim_get_hash(ptr); 154 struct hashentry *p; 155 156 for (p = dict->tab[v % dict->size]; p != NULL; p = p->next) 157 if (heim_cmp(ptr, p->key) == 0) 158 return p; 159 160 return NULL; 161 } 162 163 /** 164 * Search for element in hash table 165 * 166 * @value dict the dict to search in 167 * @value key the key to search for 168 * 169 * @return a retained copy of the value for key or NULL if not found 170 */ 171 172 heim_object_t 173 heim_dict_copy_value(heim_dict_t dict, heim_object_t key) 174 { 175 struct hashentry *p; 176 p = _search(dict, key); 177 if (p == NULL) 178 return NULL; 179 180 return heim_retain(p->value); 181 } 182 183 /** 184 * Add key and value to dict 185 * 186 * @value dict the dict to add too 187 * @value key the key to add 188 * @value value the value to add 189 * 190 * @return 0 if added, errno if not 191 */ 192 193 int 194 heim_dict_add_value(heim_dict_t dict, heim_object_t key, heim_object_t value) 195 { 196 struct hashentry **tabptr, *h; 197 198 h = _search(dict, key); 199 if (h) { 200 heim_release(h->value); 201 h->value = heim_retain(value); 202 } else { 203 unsigned long v; 204 205 h = malloc(sizeof(*h)); 206 if (h == NULL) 207 return ENOMEM; 208 209 h->key = heim_retain(key); 210 h->value = heim_retain(value); 211 212 v = heim_get_hash(key); 213 214 tabptr = &dict->tab[v % dict->size]; 215 h->next = *tabptr; 216 *tabptr = h; 217 h->prev = tabptr; 218 if (h->next) 219 h->next->prev = &h->next; 220 } 221 222 return 0; 223 } 224 225 /** 226 * Delete element with key key 227 * 228 * @value dict the dict to delete from 229 * @value key the key to delete 230 */ 231 232 void 233 heim_dict_delete_key(heim_dict_t dict, heim_object_t key) 234 { 235 struct hashentry *h = _search(dict, key); 236 237 if (h == NULL) 238 return; 239 240 heim_release(h->key); 241 heim_release(h->value); 242 243 if ((*(h->prev) = h->next) != NULL) 244 h->next->prev = h->prev; 245 246 free(h); 247 } 248 249 /** 250 * Do something for each element 251 * 252 * @value dict the dict to interate over 253 * @value func the function to search for 254 * @value arg argument to func 255 */ 256 257 void 258 heim_dict_iterate_f(heim_dict_t dict, heim_dict_iterator_f_t func, void *arg) 259 { 260 struct hashentry **h, *g; 261 262 for (h = dict->tab; h < &dict->tab[dict->size]; ++h) 263 for (g = *h; g; g = g->next) 264 func(g->key, g->value, arg); 265 } 266 267 #ifdef __BLOCKS__ 268 /** 269 * Do something for each element 270 * 271 * @value dict the dict to interate over 272 * @value func the function to search for 273 */ 274 275 void 276 heim_dict_iterate(heim_dict_t dict, void (^func)(heim_object_t, heim_object_t)) 277 { 278 struct hashentry **h, *g; 279 280 for (h = dict->tab; h < &dict->tab[dict->size]; ++h) 281 for (g = *h; g; g = g->next) 282 func(g->key, g->value); 283 } 284 #endif 285