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
  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
 119     dict->size = findprime(size);
 120     if (dict->size == 0) {
 121         heim_release(dict);
 122         return NULL;
 123     }
 124
 125     dict->tab = calloc(dict->size, sizeof(dict->tab[0]));
 126     if (dict->tab == NULL) {
 127         dict->size = 0;
 128         heim_release(dict);
 129         return NULL;
 130     }
 131
 132     return dict;
 133 }
 134
 135 /**
 136  * Get type id of an dict
 137  *
 138  * @return the type id
 139  */
 140
 141 heim_tid_t
 142 heim_dict_get_type_id(void)
 143 {
 144     return HEIM_TID_DICT;
 145 }
 146
 147 /* Intern search function */
 148
 149 static struct hashentry *
 150 _search(heim_dict_t dict, heim_object_t ptr)
 151 {
 152     uintptr_t v = heim_get_hash(ptr);
 153     struct hashentry *p;
 154
 155     for (p = dict->tab[v % dict->size]; p != NULL; p = p->next)
 156         if (heim_cmp(ptr, p->key) == 0)
 157             return p;
 158
 159     return NULL;
 160 }
 161
 162 /**
 163  * Search for element in hash table
 164  *
 165  * @value dict the dict to search in
 166  * @value key the key to search for
 167  *
 168  * @return a not-retained copy of the value for key or NULL if not found
 169  */
 170
 171 heim_object_t
 172 heim_dict_get_value(heim_dict_t dict, heim_object_t key)
 173 {
 174     struct hashentry *p;
 175     p = _search(dict, key);
 176     if (p == NULL)
 177         return NULL;
 178
 179     return p->value;
 180 }
 181
 182 /**
 183  * Search for element in hash table
 184  *
 185  * @value dict the dict to search in
 186  * @value key the key to search for
 187  *
 188  * @return a retained copy of the value for key or NULL if not found
 189  */
 190
 191 heim_object_t
 192 heim_dict_copy_value(heim_dict_t dict, heim_object_t key)
 193 {
 194     struct hashentry *p;
 195     p = _search(dict, key);
 196     if (p == NULL)
 197         return NULL;
 198
 199     return heim_retain(p->value);
 200 }
 201
 202 /**
 203  * Add key and value to dict
 204  *
 205  * @value dict the dict to add too
 206  * @value key the key to add
 207  * @value value the value to add
 208  *
 209  * @return 0 if added, errno if not
 210  */
 211
 212 int
 213 heim_dict_set_value(heim_dict_t dict, heim_object_t key, heim_object_t value)
 214 {
 215     struct hashentry **tabptr, *h;
 216
 217     h = _search(dict, key);
 218     if (h) {
 219         heim_release(h->value);
 220         h->value = heim_retain(value);
 221     } else {
 222         uintptr_t v;
 223
 224         h = malloc(sizeof(*h));
 225         if (h == NULL)
 226             return ENOMEM;
 227
 228         h->key = heim_retain(key);
 229         h->value = heim_retain(value);
 230
 231         v = heim_get_hash(key);
 232
 233         tabptr = &dict->tab[v % dict->size];
 234         h->next = *tabptr;
 235         *tabptr = h;
 236         h->prev = tabptr;
 237         if (h->next)
 238             h->next->prev = &h->next;
 239     }
 240
 241     return 0;
 242 }
 243
 244 /**
 245  * Delete element with key key
 246  *
 247  * @value dict the dict to delete from
 248  * @value key the key to delete
 249  */
 250
 251 void
 252 heim_dict_delete_key(heim_dict_t dict, heim_object_t key)
 253 {
 254     struct hashentry *h = _search(dict, key);
 255
 256     if (h == NULL)
 257         return;
 258
 259     heim_release(h->key);
 260     heim_release(h->value);
 261
 262     if ((*(h->prev) = h->next) != NULL)
 263         h->next->prev = h->prev;
 264
 265     free(h);
 266 }
 267
 268 /**
 269  * Do something for each element
 270  *
 271  * @value dict the dict to interate over
 272  * @value func the function to search for
 273  * @value arg argument to func
 274  */
 275
 276 void
 277 heim_dict_iterate_f(heim_dict_t dict, void *arg, heim_dict_iterator_f_t func)
 278 {
 279     struct hashentry **h, *g;
 280
 281     for (h = dict->tab; h < &dict->tab[dict->size]; ++h)
 282         for (g = *h; g; g = g->next)
 283             func(g->key, g->value, arg);
 284 }
 285
 286 #ifdef __BLOCKS__
 287 /**
 288  * Do something for each element
 289  *
 290  * @value dict the dict to interate over
 291  * @value func the function to search for
 292  */
 293
 294 void
 295 heim_dict_iterate(heim_dict_t dict, void (^func)(heim_object_t, heim_object_t))
 296 {
 297     struct hashentry **h, *g;
 298
 299     for (h = dict->tab; h < &dict->tab[dict->size]; ++h)
 300         for (g = *h; g; g = g->next)
 301             func(g->key, g->value);
 302 }
 303 #endif