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
  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 };
  76
  77 static size_t
  78 isprime(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
  93 static size_t
  94 findprime(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
 111 heim_dict_t
 112 heim_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
 140 heim_tid_t
 141 heim_dict_get_type_id(void)
 142 {
 143     return HEIM_TID_DICT;
 144 }
 145
 146 /* Intern search function */
 147
 148 static 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 not-retained copy of the value for key or NULL if not found
 168  */
 169
 170 heim_object_t
 171 heim_dict_get_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 p->value;
 179 }
 180
 181 /**
 182  * Search for element in hash table
 183  *
 184  * @value dict the dict to search in
 185  * @value key the key to search for
 186  *
 187  * @return a retained copy of the value for key or NULL if not found
 188  */
 189
 190 heim_object_t
 191 heim_dict_copy_value(heim_dict_t dict, heim_object_t key)
 192 {
 193     struct hashentry *p;
 194     p = _search(dict, key);
 195     if (p == NULL)
 196         return NULL;
 197
 198     return heim_retain(p->value);
 199 }
 200
 201 /**
 202  * Add key and value to dict
 203  *
 204  * @value dict the dict to add too
 205  * @value key the key to add
 206  * @value value the value to add
 207  *
 208  * @return 0 if added, errno if not
 209  */
 210
 211 int
 212 heim_dict_set_value(heim_dict_t dict, heim_object_t key, heim_object_t value)
 213 {
 214     struct hashentry **tabptr, *h;
 215
 216     h = _search(dict, key);
 217     if (h) {
 218         heim_release(h->value);
 219         h->value = heim_retain(value);
 220     } else {
 221         unsigned long v;
 222
 223         h = malloc(sizeof(*h));
 224         if (h == NULL)
 225             return ENOMEM;
 226
 227         h->key = heim_retain(key);
 228         h->value = heim_retain(value);
 229
 230         v = heim_get_hash(key);
 231
 232         tabptr = &dict->tab[v % dict->size];
 233         h->next = *tabptr;
 234         *tabptr = h;
 235         h->prev = tabptr;
 236         if (h->next)
 237             h->next->prev = &h->next;
 238     }
 239
 240     return 0;
 241 }
 242
 243 /**
 244  * Delete element with key key
 245  *
 246  * @value dict the dict to delete from
 247  * @value key the key to delete
 248  */
 249
 250 void
 251 heim_dict_delete_key(heim_dict_t dict, heim_object_t key)
 252 {
 253     struct hashentry *h = _search(dict, key);
 254
 255     if (h == NULL)
 256         return;
 257
 258     heim_release(h->key);
 259     heim_release(h->value);
 260
 261     if ((*(h->prev) = h->next) != NULL)
 262         h->next->prev = h->prev;
 263
 264     free(h);
 265 }
 266
 267 /**
 268  * Do something for each element
 269  *
 270  * @value dict the dict to interate over
 271  * @value func the function to search for
 272  * @value arg argument to func
 273  */
 274
 275 void
 276 heim_dict_iterate_f(heim_dict_t dict, void *arg, heim_dict_iterator_f_t func)
 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, arg);
 283 }
 284
 285 #ifdef __BLOCKS__
 286 /**
 287  * Do something for each element
 288  *
 289  * @value dict the dict to interate over
 290  * @value func the function to search for
 291  */
 292
 293 void
 294 heim_dict_iterate(heim_dict_t dict, void (^func)(heim_object_t, heim_object_t))
 295 {
 296     struct hashentry **h, *g;
 297
 298     for (h = dict->tab; h < &dict->tab[dict->size]; ++h)
 299         for (g = *h; g; g = g->next)
 300             func(g->key, g->value);
 301 }
 302 #endif