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