crypto/external/bsd/heimdal/dist/base/dict.c

   1 /*      $NetBSD: dict.c,v 1.1.1.2 2014/04/24 12:45:26 pettai Exp $      */
   2
   3 /*
   4  * Copyright (c) 2002, 1997 Kungliga Tekniska Högskolan
   5  * (Royal Institute of Technology, Stockholm, Sweden).
   6  * All rights reserved.
   7  *
   8  * Portions Copyright (c) 2010 Apple Inc. All rights reserved.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  *
  14  * 1. Redistributions of source code must retain the above copyright
  15  *    notice, this list of conditions and the following disclaimer.
  16  *
  17  * 2. Redistributions in binary form must reproduce the above copyright
  18  *    notice, this list of conditions and the following disclaimer in the
  19  *    documentation and/or other materials provided with the distribution.
  20  *
  21  * 3. Neither the name of the Institute nor the names of its contributors
  22  *    may be used to endorse or promote products derived from this software
  23  *    without specific prior written permission.
  24  *
  25  * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
  26  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  27  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  28  * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
  29  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  30  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  31  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  32  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  33  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  34  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  35  * SUCH DAMAGE.
  36  */
  37
  38 #include "baselocl.h"
  39
  40 struct hashentry {
  41     struct hashentry **prev;
  42     struct hashentry *next;
  43     heim_object_t key;
  44     heim_object_t value;
  45 };
  46
  47 struct heim_dict_data {
  48     size_t size;
  49     struct hashentry **tab;
  50 };
  51
  52 static void
  53 dict_dealloc(void *ptr)
  54 {
  55     heim_dict_t dict = ptr;
  56     struct hashentry **h, *g, *i;
  57
  58     for (h = dict->tab; h < &dict->tab[dict->size]; ++h) {
  59         for (g = h[0]; g; g = i) {
  60             i = g->next;
  61             heim_release(g->key);
  62             heim_release(g->value);
  63             free(g);
  64         }
  65     }
  66     free(dict->tab);
  67 }
  68
  69 struct heim_type_data dict_object = {
  70     HEIM_TID_DICT,
  71     "dict-object",
  72     NULL,
  73     dict_dealloc,
  74     NULL,
  75     NULL,
  76     NULL
  77 };
  78
  79 static size_t
  80 isprime(size_t p)
  81 {
  82     size_t q, i;
  83
  84     for(i = 2 ; i < p; i++) {
  85         q = p / i;
  86
  87         if (i * q == p)
  88             return 0;
  89         if (i * i > p)
  90             return 1;
  91     }
  92     return 1;
  93 }
  94
  95 static size_t
  96 findprime(size_t p)
  97 {
  98     if (p % 2 == 0)
  99         p++;
 100
 101     while (isprime(p) == 0)
 102         p += 2;
 103
 104     return p;
 105 }
 106
 107 /**
 108  * Allocate an array
 109  *
 110  * @return A new allocated array, free with heim_release()
 111  */
 112
 113 heim_dict_t
 114 heim_dict_create(size_t size)
 115 {
 116     heim_dict_t dict;
 117
 118     dict = _heim_alloc_object(&dict_object, sizeof(*dict));
 119
 120     dict->size = findprime(size);
 121     if (dict->size == 0) {
 122         heim_release(dict);
 123         return NULL;
 124     }
 125
 126     dict->tab = calloc(dict->size, sizeof(dict->tab[0]));
 127     if (dict->tab == NULL) {
 128         dict->size = 0;
 129         heim_release(dict);
 130         return NULL;
 131     }
 132
 133     return dict;
 134 }
 135
 136 /**
 137  * Get type id of an dict
 138  *
 139  * @return the type id
 140  */
 141
 142 heim_tid_t
 143 heim_dict_get_type_id(void)
 144 {
 145     return HEIM_TID_DICT;
 146 }
 147
 148 /* Intern search function */
 149
 150 static struct hashentry *
 151 _search(heim_dict_t dict, heim_object_t ptr)
 152 {
 153     unsigned long v = heim_get_hash(ptr);
 154     struct hashentry *p;
 155
 156     for (p = dict->tab[v % dict->size]; p != NULL; p = p->next)
 157         if (heim_cmp(ptr, p->key) == 0)
 158             return p;
 159
 160     return NULL;
 161 }
 162
 163 /**
 164  * Search for element in hash table
 165  *
 166  * @value dict the dict to search in
 167  * @value key the key to search for
 168  *
 169  * @return a retained copy of the value for key or NULL if not found
 170  */
 171
 172 heim_object_t
 173 heim_dict_copy_value(heim_dict_t dict, heim_object_t key)
 174 {
 175     struct hashentry *p;
 176     p = _search(dict, key);
 177     if (p == NULL)
 178         return NULL;
 179
 180     return heim_retain(p->value);
 181 }
 182
 183 /**
 184  * Add key and value to dict
 185  *
 186  * @value dict the dict to add too
 187  * @value key the key to add
 188  * @value value the value to add
 189  *
 190  * @return 0 if added, errno if not
 191  */
 192
 193 int
 194 heim_dict_add_value(heim_dict_t dict, heim_object_t key, heim_object_t value)
 195 {
 196     struct hashentry **tabptr, *h;
 197
 198     h = _search(dict, key);
 199     if (h) {
 200         heim_release(h->value);
 201         h->value = heim_retain(value);
 202     } else {
 203         unsigned long v;
 204
 205         h = malloc(sizeof(*h));
 206         if (h == NULL)
 207             return ENOMEM;
 208
 209         h->key = heim_retain(key);
 210         h->value = heim_retain(value);
 211
 212         v = heim_get_hash(key);
 213
 214         tabptr = &dict->tab[v % dict->size];
 215         h->next = *tabptr;
 216         *tabptr = h;
 217         h->prev = tabptr;
 218         if (h->next)
 219             h->next->prev = &h->next;
 220     }
 221
 222     return 0;
 223 }
 224
 225 /**
 226  * Delete element with key key
 227  *
 228  * @value dict the dict to delete from
 229  * @value key the key to delete
 230  */
 231
 232 void
 233 heim_dict_delete_key(heim_dict_t dict, heim_object_t key)
 234 {
 235     struct hashentry *h = _search(dict, key);
 236
 237     if (h == NULL)
 238         return;
 239
 240     heim_release(h->key);
 241     heim_release(h->value);
 242
 243     if ((*(h->prev) = h->next) != NULL)
 244         h->next->prev = h->prev;
 245
 246     free(h);
 247 }
 248
 249 /**
 250  * Do something for each element
 251  *
 252  * @value dict the dict to interate over
 253  * @value func the function to search for
 254  * @value arg argument to func
 255  */
 256
 257 void
 258 heim_dict_iterate_f(heim_dict_t dict, heim_dict_iterator_f_t func, void *arg)
 259 {
 260     struct hashentry **h, *g;
 261
 262     for (h = dict->tab; h < &dict->tab[dict->size]; ++h)
 263         for (g = *h; g; g = g->next)
 264             func(g->key, g->value, arg);
 265 }
 266
 267 #ifdef __BLOCKS__
 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  */
 274
 275 void
 276 heim_dict_iterate(heim_dict_t dict, void (^func)(heim_object_t, heim_object_t))
 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);
 283 }
 284 #endif