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 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 heim_retain(p->value);
 179 }
 180
 181 /**
 182  * Add key and value to dict
 183  *
 184  * @value dict the dict to add too
 185  * @value key the key to add
 186  * @value value the value to add
 187  *
 188  * @return 0 if added, errno if not
 189  */
 190
 191 int
 192 heim_dict_set_value(heim_dict_t dict, heim_object_t key, heim_object_t value)
 193 {
 194     struct hashentry **tabptr, *h;
 195
 196     h = _search(dict, key);
 197     if (h) {
 198         heim_release(h->value);
 199         h->value = heim_retain(value);
 200     } else {
 201         unsigned long v;
 202
 203         h = malloc(sizeof(*h));
 204         if (h == NULL)
 205             return ENOMEM;
 206
 207         h->key = heim_retain(key);
 208         h->value = heim_retain(value);
 209
 210         v = heim_get_hash(key);
 211
 212         tabptr = &dict->tab[v % dict->size];
 213         h->next = *tabptr;
 214         *tabptr = h;
 215         h->prev = tabptr;
 216         if (h->next)
 217             h->next->prev = &h->next;
 218     }
 219
 220     return 0;
 221 }
 222
 223 /**
 224  * Delete element with key key
 225  *
 226  * @value dict the dict to delete from
 227  * @value key the key to delete
 228  */
 229
 230 void
 231 heim_dict_delete_key(heim_dict_t dict, heim_object_t key)
 232 {
 233     struct hashentry *h = _search(dict, key);
 234
 235     if (h == NULL)
 236         return;
 237
 238     heim_release(h->key);
 239     heim_release(h->value);
 240
 241     if ((*(h->prev) = h->next) != NULL)
 242         h->next->prev = h->prev;
 243
 244     free(h);
 245 }
 246
 247 /**
 248  * Do something for each element
 249  *
 250  * @value dict the dict to interate over
 251  * @value func the function to search for
 252  * @value arg argument to func
 253  */
 254
 255 void
 256 heim_dict_iterate_f(heim_dict_t dict, heim_dict_iterator_f_t func, void *arg)
 257 {
 258     struct hashentry **h, *g;
 259
 260     for (h = dict->tab; h < &dict->tab[dict->size]; ++h)
 261         for (g = *h; g; g = g->next)
 262             func(g->key, g->value, arg);
 263 }
 264
 265 #ifdef __BLOCKS__
 266 /**
 267  * Do something for each element
 268  *
 269  * @value dict the dict to interate over
 270  * @value func the function to search for
 271  */
 272
 273 void
 274 heim_dict_iterate(heim_dict_t dict, void (^func)(heim_object_t, heim_object_t))
 275 {
 276     struct hashentry **h, *g;
 277
 278     for (h = dict->tab; h < &dict->tab[dict->size]; ++h)
 279         for (g = *h; g; g = g->next)
 280             func(g->key, g->value);
 281 }
 282 #endif