Home | History | Annotate | Download | only in lhash 
      1 /* Copyright (C) 1995-1998 Eric Young (eay (at) cryptsoft.com)
      2  * All rights reserved.
      3  *
      4  * This package is an SSL implementation written
      5  * by Eric Young (eay (at) cryptsoft.com).
      6  * The implementation was written so as to conform with Netscapes SSL.
      7  *
      8  * This library is free for commercial and non-commercial use as long as
      9  * the following conditions are aheared to.  The following conditions
     10  * apply to all code found in this distribution, be it the RC4, RSA,
     11  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
     12  * included with this distribution is covered by the same copyright terms
     13  * except that the holder is Tim Hudson (tjh (at) cryptsoft.com).
     14  *
     15  * Copyright remains Eric Young's, and as such any Copyright notices in
     16  * the code are not to be removed.
     17  * If this package is used in a product, Eric Young should be given attribution
     18  * as the author of the parts of the library used.
     19  * This can be in the form of a textual message at program startup or
     20  * in documentation (online or textual) provided with the package.
     21  *
     22  * Redistribution and use in source and binary forms, with or without
     23  * modification, are permitted provided that the following conditions
     24  * are met:
     25  * 1. Redistributions of source code must retain the copyright
     26  *    notice, this list of conditions and the following disclaimer.
     27  * 2. Redistributions in binary form must reproduce the above copyright
     28  *    notice, this list of conditions and the following disclaimer in the
     29  *    documentation and/or other materials provided with the distribution.
     30  * 3. All advertising materials mentioning features or use of this software
     31  *    must display the following acknowledgement:
     32  *    "This product includes cryptographic software written by
     33  *     Eric Young (eay (at) cryptsoft.com)"
     34  *    The word 'cryptographic' can be left out if the rouines from the library
     35  *    being used are not cryptographic related :-).
     36  * 4. If you include any Windows specific code (or a derivative thereof) from
     37  *    the apps directory (application code) you must include an acknowledgement:
     38  *    "This product includes software written by Tim Hudson (tjh (at) cryptsoft.com)"
     39  *
     40  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
     41  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     42  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     43  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
     44  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     45  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     46  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     47  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     48  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     49  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     50  * SUCH DAMAGE.
     51  *
     52  * The licence and distribution terms for any publically available version or
     53  * derivative of this code cannot be changed.  i.e. this code cannot simply be
     54  * copied and put under another distribution licence
     55  * [including the GNU Public Licence.] */
     56 
     57 #include <openssl/lhash.h>
     58 
     59 #include <assert.h>
     60 #include <limits.h>
     61 #include <string.h>
     62 
     63 #include <openssl/mem.h>
     64 
     65 #include "../internal.h"
     66 
     67 
     68 /* kMinNumBuckets is the minimum size of the buckets array in an |_LHASH|. */
     69 static const size_t kMinNumBuckets = 16;
     70 
     71 /* kMaxAverageChainLength contains the maximum, average chain length. When the
     72  * average chain length exceeds this value, the hash table will be resized. */
     73 static const size_t kMaxAverageChainLength = 2;
     74 static const size_t kMinAverageChainLength = 1;
     75 
     76 _LHASH *lh_new(lhash_hash_func hash, lhash_cmp_func comp) {
     77   _LHASH *ret = OPENSSL_malloc(sizeof(_LHASH));
     78   if (ret == NULL) {
     79     return NULL;
     80   }
     81   OPENSSL_memset(ret, 0, sizeof(_LHASH));
     82 
     83   ret->num_buckets = kMinNumBuckets;
     84   ret->buckets = OPENSSL_malloc(sizeof(LHASH_ITEM *) * ret->num_buckets);
     85   if (ret->buckets == NULL) {
     86     OPENSSL_free(ret);
     87     return NULL;
     88   }
     89   OPENSSL_memset(ret->buckets, 0, sizeof(LHASH_ITEM *) * ret->num_buckets);
     90 
     91   ret->comp = comp;
     92   ret->hash = hash;
     93   return ret;
     94 }
     95 
     96 void lh_free(_LHASH *lh) {
     97   if (lh == NULL) {
     98     return;
     99   }
    100 
    101   for (size_t i = 0; i < lh->num_buckets; i++) {
    102     LHASH_ITEM *next;
    103     for (LHASH_ITEM *n = lh->buckets[i]; n != NULL; n = next) {
    104       next = n->next;
    105       OPENSSL_free(n);
    106     }
    107   }
    108 
    109   OPENSSL_free(lh->buckets);
    110   OPENSSL_free(lh);
    111 }
    112 
    113 size_t lh_num_items(const _LHASH *lh) { return lh->num_items; }
    114 
    115 /* get_next_ptr_and_hash returns a pointer to the pointer that points to the
    116  * item equal to |data|. In other words, it searches for an item equal to |data|
    117  * and, if it's at the start of a chain, then it returns a pointer to an
    118  * element of |lh->buckets|, otherwise it returns a pointer to the |next|
    119  * element of the previous item in the chain. If an element equal to |data| is
    120  * not found, it returns a pointer that points to a NULL pointer. If |out_hash|
    121  * is not NULL, then it also puts the hash value of |data| in |*out_hash|. */
    122 static LHASH_ITEM **get_next_ptr_and_hash(const _LHASH *lh, uint32_t *out_hash,
    123                                           const void *data) {
    124   const uint32_t hash = lh->hash(data);
    125   LHASH_ITEM *cur, **ret;
    126 
    127   if (out_hash != NULL) {
    128     *out_hash = hash;
    129   }
    130 
    131   ret = &lh->buckets[hash % lh->num_buckets];
    132   for (cur = *ret; cur != NULL; cur = *ret) {
    133     if (lh->comp(cur->data, data) == 0) {
    134       break;
    135     }
    136     ret = &cur->next;
    137   }
    138 
    139   return ret;
    140 }
    141 
    142 void *lh_retrieve(const _LHASH *lh, const void *data) {
    143   LHASH_ITEM **next_ptr;
    144 
    145   next_ptr = get_next_ptr_and_hash(lh, NULL, data);
    146 
    147   if (*next_ptr == NULL) {
    148     return NULL;
    149   }
    150 
    151   return (*next_ptr)->data;
    152 }
    153 
    154 /* lh_rebucket allocates a new array of |new_num_buckets| pointers and
    155  * redistributes the existing items into it before making it |lh->buckets| and
    156  * freeing the old array. */
    157 static void lh_rebucket(_LHASH *lh, const size_t new_num_buckets) {
    158   LHASH_ITEM **new_buckets, *cur, *next;
    159   size_t i, alloc_size;
    160 
    161   alloc_size = sizeof(LHASH_ITEM *) * new_num_buckets;
    162   if (alloc_size / sizeof(LHASH_ITEM*) != new_num_buckets) {
    163     return;
    164   }
    165 
    166   new_buckets = OPENSSL_malloc(alloc_size);
    167   if (new_buckets == NULL) {
    168     return;
    169   }
    170   OPENSSL_memset(new_buckets, 0, alloc_size);
    171 
    172   for (i = 0; i < lh->num_buckets; i++) {
    173     for (cur = lh->buckets[i]; cur != NULL; cur = next) {
    174       const size_t new_bucket = cur->hash % new_num_buckets;
    175       next = cur->next;
    176       cur->next = new_buckets[new_bucket];
    177       new_buckets[new_bucket] = cur;
    178     }
    179   }
    180 
    181   OPENSSL_free(lh->buckets);
    182 
    183   lh->num_buckets = new_num_buckets;
    184   lh->buckets = new_buckets;
    185 }
    186 
    187 /* lh_maybe_resize resizes the |buckets| array if needed. */
    188 static void lh_maybe_resize(_LHASH *lh) {
    189   size_t avg_chain_length;
    190 
    191   if (lh->callback_depth > 0) {
    192     /* Don't resize the hash if we are currently iterating over it. */
    193     return;
    194   }
    195 
    196   assert(lh->num_buckets >= kMinNumBuckets);
    197   avg_chain_length = lh->num_items / lh->num_buckets;
    198 
    199   if (avg_chain_length > kMaxAverageChainLength) {
    200     const size_t new_num_buckets = lh->num_buckets * 2;
    201 
    202     if (new_num_buckets > lh->num_buckets) {
    203       lh_rebucket(lh, new_num_buckets);
    204     }
    205   } else if (avg_chain_length < kMinAverageChainLength &&
    206              lh->num_buckets > kMinNumBuckets) {
    207     size_t new_num_buckets = lh->num_buckets / 2;
    208 
    209     if (new_num_buckets < kMinNumBuckets) {
    210       new_num_buckets = kMinNumBuckets;
    211     }
    212 
    213     lh_rebucket(lh, new_num_buckets);
    214   }
    215 }
    216 
    217 int lh_insert(_LHASH *lh, void **old_data, void *data) {
    218   uint32_t hash;
    219   LHASH_ITEM **next_ptr, *item;
    220 
    221   *old_data = NULL;
    222   next_ptr = get_next_ptr_and_hash(lh, &hash, data);
    223 
    224 
    225   if (*next_ptr != NULL) {
    226     /* An element equal to |data| already exists in the hash table. It will be
    227      * replaced. */
    228     *old_data = (*next_ptr)->data;
    229     (*next_ptr)->data = data;
    230     return 1;
    231   }
    232 
    233   /* An element equal to |data| doesn't exist in the hash table yet. */
    234   item = OPENSSL_malloc(sizeof(LHASH_ITEM));
    235   if (item == NULL) {
    236     return 0;
    237   }
    238 
    239   item->data = data;
    240   item->hash = hash;
    241   item->next = NULL;
    242   *next_ptr = item;
    243   lh->num_items++;
    244   lh_maybe_resize(lh);
    245 
    246   return 1;
    247 }
    248 
    249 void *lh_delete(_LHASH *lh, const void *data) {
    250   LHASH_ITEM **next_ptr, *item, *ret;
    251 
    252   next_ptr = get_next_ptr_and_hash(lh, NULL, data);
    253 
    254   if (*next_ptr == NULL) {
    255     /* No such element. */
    256     return NULL;
    257   }
    258 
    259   item = *next_ptr;
    260   *next_ptr = item->next;
    261   ret = item->data;
    262   OPENSSL_free(item);
    263 
    264   lh->num_items--;
    265   lh_maybe_resize(lh);
    266 
    267   return ret;
    268 }
    269 
    270 static void lh_doall_internal(_LHASH *lh, void (*no_arg_func)(void *),
    271                               void (*arg_func)(void *, void *), void *arg) {
    272   if (lh == NULL) {
    273     return;
    274   }
    275 
    276   if (lh->callback_depth < UINT_MAX) {
    277     /* |callback_depth| is a saturating counter. */
    278     lh->callback_depth++;
    279   }
    280 
    281   for (size_t i = 0; i < lh->num_buckets; i++) {
    282     LHASH_ITEM *next;
    283     for (LHASH_ITEM *cur = lh->buckets[i]; cur != NULL; cur = next) {
    284       next = cur->next;
    285       if (arg_func) {
    286         arg_func(cur->data, arg);
    287       } else {
    288         no_arg_func(cur->data);
    289       }
    290     }
    291   }
    292 
    293   if (lh->callback_depth < UINT_MAX) {
    294     lh->callback_depth--;
    295   }
    296 
    297   /* The callback may have added or removed elements and the non-zero value of
    298    * |callback_depth| will have suppressed any resizing. Thus any needed
    299    * resizing is done here. */
    300   lh_maybe_resize(lh);
    301 }
    302 
    303 void lh_doall(_LHASH *lh, void (*func)(void *)) {
    304   lh_doall_internal(lh, func, NULL, NULL);
    305 }
    306 
    307 void lh_doall_arg(_LHASH *lh, void (*func)(void *, void *), void *arg) {
    308   lh_doall_internal(lh, NULL, func, arg);
    309 }
    310 
    311 uint32_t lh_strhash(const char *c) {
    312   /* The following hash seems to work very well on normal text strings
    313    * no collisions on /usr/dict/words and it distributes on %2^n quite
    314    * well, not as good as MD5, but still good. */
    315   unsigned long ret = 0;
    316   long n;
    317   unsigned long v;
    318   int r;
    319 
    320   if ((c == NULL) || (*c == '\0')) {
    321     return (ret);
    322   }
    323 
    324   n = 0x100;
    325   while (*c) {
    326     v = n | (*c);
    327     n += 0x100;
    328     r = (int)((v >> 2) ^ v) & 0x0f;
    329     ret = (ret << r) | (ret >> (32 - r));
    330     ret &= 0xFFFFFFFFL;
    331     ret ^= v * v;
    332     c++;
    333   }
    334 
    335   return ((ret >> 16) ^ ret);
    336 }
    337