lib/base/dict.c

   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
  38 struct hashentry {
  39     struct hashentry **prev;
  40     struct hashentry *next;
  41     heim_object_t key;
  42     heim_object_t value;
  43 };
  44
  45 struct heim_dict_data {
  46     size_t size;
  47     struct hashentry **tab;
  48 };
  49
  50 static void HEIM_CALLCONV
  51 dict_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
  67 struct heim_type_data dict_object = {
  68     HEIM_TID_DICT,
  69     "dict-object",
  70     NULL,
  71     dict_dealloc,
  72     NULL,
  73     NULL,
  74     NULL,
  75     NULL
  76 };
  77
  78 static size_t
  79 isprime(size_t p)
  80 {
  81     size_t q, i;
  82
  83     for(i = 2 ; i < p; i++) {
  84         q = p / i;
  85
  86         if (i * q == p)
  87             return 0;
  88         if (i * i > p)
  89             return 1;
  90     }
  91     return 1;
  92 }
  93
  94 static size_t
  95 findprime(size_t p)
  96 {
  97     if (p % 2 == 0)
  98         p++;
  99
 100     while (isprime(p) == 0)
 101         p += 2;
 102
 103     return p;
 104 }
 105
 106 /**
 107  * Allocate an array
 108  *
 109  * @return A new allocated array, free with heim_release()
 110  */
 111
 112 heim_dict_t
 113 heim_dict_create(size_t size)
 114 {
 115     heim_dict_t dict;
 116
 117     dict = _heim_alloc_object(&dict_object, sizeof(*dict));
 118     if (dict == NULL)
 119         return NULL;
 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     uintptr_t 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         uintptr_t 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