1226031Sstas/* 2226031Sstas * Copyright (c) 2002, 1997 Kungliga Tekniska H��gskolan 3226031Sstas * (Royal Institute of Technology, Stockholm, Sweden). 4226031Sstas * All rights reserved. 5226031Sstas * 6226031Sstas * Portions Copyright (c) 2010 Apple Inc. All rights reserved. 7226031Sstas * 8226031Sstas * Redistribution and use in source and binary forms, with or without 9226031Sstas * modification, are permitted provided that the following conditions 10226031Sstas * are met: 11226031Sstas * 12226031Sstas * 1. Redistributions of source code must retain the above copyright 13226031Sstas * notice, this list of conditions and the following disclaimer. 14226031Sstas * 15226031Sstas * 2. Redistributions in binary form must reproduce the above copyright 16226031Sstas * notice, this list of conditions and the following disclaimer in the 17226031Sstas * documentation and/or other materials provided with the distribution. 18226031Sstas * 19226031Sstas * 3. Neither the name of the Institute nor the names of its contributors 20226031Sstas * may be used to endorse or promote products derived from this software 21226031Sstas * without specific prior written permission. 22226031Sstas * 23226031Sstas * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND 24226031Sstas * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 25226031Sstas * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 26226031Sstas * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE 27226031Sstas * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 28226031Sstas * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 29226031Sstas * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30226031Sstas * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31226031Sstas * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 32226031Sstas * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33226031Sstas * SUCH DAMAGE. 34226031Sstas */ 35226031Sstas 36226031Sstas#include "baselocl.h" 37226031Sstas 38226031Sstasstruct hashentry { 39226031Sstas struct hashentry **prev; 40226031Sstas struct hashentry *next; 41226031Sstas heim_object_t key; 42226031Sstas heim_object_t value; 43226031Sstas}; 44226031Sstas 45226031Sstasstruct heim_dict_data { 46226031Sstas size_t size; 47226031Sstas struct hashentry **tab; 48226031Sstas}; 49226031Sstas 50226031Sstasstatic void 51226031Sstasdict_dealloc(void *ptr) 52226031Sstas{ 53226031Sstas heim_dict_t dict = ptr; 54226031Sstas struct hashentry **h, *g, *i; 55226031Sstas 56226031Sstas for (h = dict->tab; h < &dict->tab[dict->size]; ++h) { 57226031Sstas for (g = h[0]; g; g = i) { 58226031Sstas i = g->next; 59226031Sstas heim_release(g->key); 60226031Sstas heim_release(g->value); 61226031Sstas free(g); 62226031Sstas } 63226031Sstas } 64226031Sstas free(dict->tab); 65226031Sstas} 66226031Sstas 67226031Sstasstruct heim_type_data dict_object = { 68226031Sstas HEIM_TID_DICT, 69226031Sstas "dict-object", 70226031Sstas NULL, 71226031Sstas dict_dealloc, 72226031Sstas NULL, 73226031Sstas NULL, 74226031Sstas NULL 75226031Sstas}; 76226031Sstas 77226031Sstasstatic size_t 78226031Sstasisprime(size_t p) 79226031Sstas{ 80226031Sstas size_t q, i; 81226031Sstas 82226031Sstas for(i = 2 ; i < p; i++) { 83226031Sstas q = p / i; 84226031Sstas 85226031Sstas if (i * q == p) 86226031Sstas return 0; 87226031Sstas if (i * i > p) 88226031Sstas return 1; 89226031Sstas } 90226031Sstas return 1; 91226031Sstas} 92226031Sstas 93226031Sstasstatic size_t 94226031Sstasfindprime(size_t p) 95226031Sstas{ 96226031Sstas if (p % 2 == 0) 97226031Sstas p++; 98226031Sstas 99226031Sstas while (isprime(p) == 0) 100226031Sstas p += 2; 101226031Sstas 102226031Sstas return p; 103226031Sstas} 104226031Sstas 105226031Sstas/** 106226031Sstas * Allocate an array 107226031Sstas * 108226031Sstas * @return A new allocated array, free with heim_release() 109226031Sstas */ 110226031Sstas 111226031Sstasheim_dict_t 112226031Sstasheim_dict_create(size_t size) 113226031Sstas{ 114226031Sstas heim_dict_t dict; 115226031Sstas 116226031Sstas dict = _heim_alloc_object(&dict_object, sizeof(*dict)); 117226031Sstas 118226031Sstas dict->size = findprime(size); 119226031Sstas if (dict->size == 0) { 120226031Sstas heim_release(dict); 121226031Sstas return NULL; 122226031Sstas } 123226031Sstas 124226031Sstas dict->tab = calloc(dict->size, sizeof(dict->tab[0])); 125226031Sstas if (dict->tab == NULL) { 126226031Sstas dict->size = 0; 127226031Sstas heim_release(dict); 128226031Sstas return NULL; 129226031Sstas } 130226031Sstas 131226031Sstas return dict; 132226031Sstas} 133226031Sstas 134226031Sstas/** 135226031Sstas * Get type id of an dict 136226031Sstas * 137226031Sstas * @return the type id 138226031Sstas */ 139226031Sstas 140226031Sstasheim_tid_t 141226031Sstasheim_dict_get_type_id(void) 142226031Sstas{ 143226031Sstas return HEIM_TID_DICT; 144226031Sstas} 145226031Sstas 146226031Sstas/* Intern search function */ 147226031Sstas 148226031Sstasstatic struct hashentry * 149226031Sstas_search(heim_dict_t dict, heim_object_t ptr) 150226031Sstas{ 151226031Sstas unsigned long v = heim_get_hash(ptr); 152226031Sstas struct hashentry *p; 153226031Sstas 154226031Sstas for (p = dict->tab[v % dict->size]; p != NULL; p = p->next) 155226031Sstas if (heim_cmp(ptr, p->key) == 0) 156226031Sstas return p; 157226031Sstas 158226031Sstas return NULL; 159226031Sstas} 160226031Sstas 161226031Sstas/** 162226031Sstas * Search for element in hash table 163226031Sstas * 164226031Sstas * @value dict the dict to search in 165226031Sstas * @value key the key to search for 166226031Sstas * 167226031Sstas * @return a retained copy of the value for key or NULL if not found 168226031Sstas */ 169226031Sstas 170226031Sstasheim_object_t 171226031Sstasheim_dict_copy_value(heim_dict_t dict, heim_object_t key) 172226031Sstas{ 173226031Sstas struct hashentry *p; 174226031Sstas p = _search(dict, key); 175226031Sstas if (p == NULL) 176226031Sstas return NULL; 177226031Sstas 178226031Sstas return heim_retain(p->value); 179226031Sstas} 180226031Sstas 181226031Sstas/** 182226031Sstas * Add key and value to dict 183226031Sstas * 184226031Sstas * @value dict the dict to add too 185226031Sstas * @value key the key to add 186226031Sstas * @value value the value to add 187226031Sstas * 188226031Sstas * @return 0 if added, errno if not 189226031Sstas */ 190226031Sstas 191226031Sstasint 192226031Sstasheim_dict_add_value(heim_dict_t dict, heim_object_t key, heim_object_t value) 193226031Sstas{ 194226031Sstas struct hashentry **tabptr, *h; 195226031Sstas 196226031Sstas h = _search(dict, key); 197226031Sstas if (h) { 198226031Sstas heim_release(h->value); 199226031Sstas h->value = heim_retain(value); 200226031Sstas } else { 201226031Sstas unsigned long v; 202226031Sstas 203226031Sstas h = malloc(sizeof(*h)); 204226031Sstas if (h == NULL) 205226031Sstas return ENOMEM; 206226031Sstas 207226031Sstas h->key = heim_retain(key); 208226031Sstas h->value = heim_retain(value); 209226031Sstas 210226031Sstas v = heim_get_hash(key); 211226031Sstas 212226031Sstas tabptr = &dict->tab[v % dict->size]; 213226031Sstas h->next = *tabptr; 214226031Sstas *tabptr = h; 215226031Sstas h->prev = tabptr; 216226031Sstas if (h->next) 217226031Sstas h->next->prev = &h->next; 218226031Sstas } 219226031Sstas 220226031Sstas return 0; 221226031Sstas} 222226031Sstas 223226031Sstas/** 224226031Sstas * Delete element with key key 225226031Sstas * 226226031Sstas * @value dict the dict to delete from 227226031Sstas * @value key the key to delete 228226031Sstas */ 229226031Sstas 230226031Sstasvoid 231226031Sstasheim_dict_delete_key(heim_dict_t dict, heim_object_t key) 232226031Sstas{ 233226031Sstas struct hashentry *h = _search(dict, key); 234226031Sstas 235226031Sstas if (h == NULL) 236226031Sstas return; 237226031Sstas 238226031Sstas heim_release(h->key); 239226031Sstas heim_release(h->value); 240226031Sstas 241226031Sstas if ((*(h->prev) = h->next) != NULL) 242226031Sstas h->next->prev = h->prev; 243226031Sstas 244226031Sstas free(h); 245226031Sstas} 246226031Sstas 247226031Sstas/** 248226031Sstas * Do something for each element 249226031Sstas * 250226031Sstas * @value dict the dict to interate over 251226031Sstas * @value func the function to search for 252226031Sstas * @value arg argument to func 253226031Sstas */ 254226031Sstas 255226031Sstasvoid 256226031Sstasheim_dict_iterate_f(heim_dict_t dict, heim_dict_iterator_f_t func, void *arg) 257226031Sstas{ 258226031Sstas struct hashentry **h, *g; 259226031Sstas 260226031Sstas for (h = dict->tab; h < &dict->tab[dict->size]; ++h) 261226031Sstas for (g = *h; g; g = g->next) 262226031Sstas func(g->key, g->value, arg); 263226031Sstas} 264226031Sstas 265226031Sstas#ifdef __BLOCKS__ 266226031Sstas/** 267226031Sstas * Do something for each element 268226031Sstas * 269226031Sstas * @value dict the dict to interate over 270226031Sstas * @value func the function to search for 271226031Sstas */ 272226031Sstas 273226031Sstasvoid 274226031Sstasheim_dict_iterate(heim_dict_t dict, void (^func)(heim_object_t, heim_object_t)) 275226031Sstas{ 276226031Sstas struct hashentry **h, *g; 277226031Sstas 278226031Sstas for (h = dict->tab; h < &dict->tab[dict->size]; ++h) 279226031Sstas for (g = *h; g; g = g->next) 280226031Sstas func(g->key, g->value); 281226031Sstas} 282226031Sstas#endif 283