Line data    Source code

       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      202884 : dict_dealloc(void *ptr)
      52             : {
      53      202884 :     heim_dict_t dict = ptr;
      54        6826 :     struct hashentry **h, *g, *i;
      55             : 
      56     1420188 :     for (h = dict->tab; h < &dict->tab[dict->size]; ++h) {
      57     2166325 :         for (g = h[0]; g; g = i) {
      58      949021 :             i = g->next;
      59      949021 :             heim_release(g->key);
      60      949021 :             heim_release(g->value);
      61      949021 :             free(g);
      62             :         }
      63             :     }
      64      202884 :     free(dict->tab);
      65      202884 : }
      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      333262 : isprime(size_t p)
      80             : {
      81       11889 :     size_t q, i;
      82             : 
      83     1023380 :     for(i = 2 ; i < p; i++) {
      84      921938 :         q = p / i;
      85             : 
      86      921938 :         if (i * q == p)
      87           0 :             return 0;
      88      921938 :         if (i * i > p)
      89      223344 :             return 1;
      90             :     }
      91       98029 :     return 1;
      92             : }
      93             : 
      94             : static size_t
      95      333262 : findprime(size_t p)
      96             : {
      97      333262 :     if (p % 2 == 0)
      98      101442 :         p++;
      99             : 
     100      345151 :     while (isprime(p) == 0)
     101           0 :         p += 2;
     102             : 
     103      333262 :     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      333262 : heim_dict_create(size_t size)
     114             : {
     115       11889 :     heim_dict_t dict;
     116             : 
     117      333262 :     dict = _heim_alloc_object(&dict_object, sizeof(*dict));
     118      333262 :     if (dict == NULL)
     119           0 :         return NULL;
     120             : 
     121      333262 :     dict->size = findprime(size);
     122      333262 :     if (dict->size == 0) {
     123           0 :         heim_release(dict);
     124           0 :         return NULL;
     125             :     }
     126             : 
     127      333262 :     dict->tab = calloc(dict->size, sizeof(dict->tab[0]));
     128      333262 :     if (dict->tab == NULL) {
     129           0 :         dict->size = 0;
     130           0 :         heim_release(dict);
     131           0 :         return NULL;
     132             :     }
     133             : 
     134      321373 :     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           0 : heim_dict_get_type_id(void)
     145             : {
     146           0 :     return HEIM_TID_DICT;
     147             : }
     148             : 
     149             : /* Intern search function */
     150             : 
     151             : static struct hashentry *
     152     4914511 : _search(heim_dict_t dict, heim_object_t ptr)
     153             : {
     154     4914511 :     uintptr_t v = heim_get_hash(ptr);
     155      163585 :     struct hashentry *p;
     156             : 
     157     6069289 :     for (p = dict->tab[v % dict->size]; p != NULL; p = p->next)
     158     3180652 :         if (heim_cmp(ptr, p->key) == 0)
     159     2025874 :             return p;
     160             : 
     161     2791218 :     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      967803 : heim_dict_get_value(heim_dict_t dict, heim_object_t key)
     175             : {
     176       35605 :     struct hashentry *p;
     177      967803 :     p = _search(dict, key);
     178      967803 :     if (p == NULL)
     179      815964 :         return NULL;
     180             : 
     181      120930 :     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     2808820 : heim_dict_copy_value(heim_dict_t dict, heim_object_t key)
     195             : {
     196       85849 :     struct hashentry *p;
     197     2808820 :     p = _search(dict, key);
     198     2808820 :     if (p == NULL)
     199      936410 :         return NULL;
     200             : 
     201     1845691 :     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     1137888 : heim_dict_set_value(heim_dict_t dict, heim_object_t key, heim_object_t value)
     216             : {
     217       42131 :     struct hashentry **tabptr, *h;
     218             : 
     219     1137888 :     h = _search(dict, key);
     220     1137888 :     if (h) {
     221       59253 :         heim_release(h->value);
     222       59253 :         h->value = heim_retain(value);
     223             :     } else {
     224       39791 :         uintptr_t v;
     225             : 
     226     1078635 :         h = malloc(sizeof(*h));
     227     1078635 :         if (h == NULL)
     228           0 :             return ENOMEM;
     229             : 
     230     1078635 :         h->key = heim_retain(key);
     231     1078635 :         h->value = heim_retain(value);
     232             : 
     233     1078635 :         v = heim_get_hash(key);
     234             : 
     235     1078635 :         tabptr = &dict->tab[v % dict->size];
     236     1078635 :         h->next = *tabptr;
     237     1078635 :         *tabptr = h;
     238     1078635 :         h->prev = tabptr;
     239     1078635 :         if (h->next)
     240      305345 :             h->next->prev = &h->next;
     241             :     }
     242             : 
     243     1095757 :     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           0 : heim_dict_delete_key(heim_dict_t dict, heim_object_t key)
     255             : {
     256           0 :     struct hashentry *h = _search(dict, key);
     257             : 
     258           0 :     if (h == NULL)
     259           0 :         return;
     260             : 
     261           0 :     heim_release(h->key);
     262           0 :     heim_release(h->value);
     263             : 
     264           0 :     if ((*(h->prev) = h->next) != NULL)
     265           0 :         h->next->prev = h->prev;
     266             : 
     267           0 :     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     1437578 : heim_dict_iterate_f(heim_dict_t dict, void *arg, heim_dict_iterator_f_t func)
     280             : {
     281       43780 :     struct hashentry **h, *g;
     282             : 
     283    17250936 :     for (h = dict->tab; h < &dict->tab[dict->size]; ++h)
     284    18098515 :         for (g = *h; g; g = g->next)
     285     2285157 :             func(g->key, g->value, arg);
     286     1437578 : }
     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