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 /* kMinNumBuckets is the minimum size of the buckets array in an |_LHASH|. */
     66 static const size_t kMinNumBuckets = 16;
     67 
     68 /* kMaxAverageChainLength contains the maximum, average chain length. When the
     69  * average chain length exceeds this value, the hash table will be resized. */
     70 static const size_t kMaxAverageChainLength = 2;
     71 static const size_t kMinAverageChainLength = 1;
     72 
     73 _LHASH *lh_new(lhash_hash_func hash, lhash_cmp_func comp) {
     74   _LHASH *ret;
     75 
     76   ret = OPENSSL_malloc(sizeof(_LHASH));
     77   if (ret == NULL) {
     78     return NULL;
     79   }
     80   memset(ret, 0, sizeof(_LHASH));
     81 
     82   ret->num_buckets = kMinNumBuckets;
     83   ret->buckets = OPENSSL_malloc(sizeof(LHASH_ITEM *) * ret->num_buckets);
     84   if (ret->buckets == NULL) {
     85     OPENSSL_free(ret);
     86     return NULL;
     87   }
     88   memset(ret->buckets, 0, sizeof(LHASH_ITEM *) * ret->num_buckets);
     89 
     90   ret->comp = comp;
     91   if (ret->comp == NULL) {
     92     ret->comp = (lhash_cmp_func) strcmp;
     93   }
     94   ret->hash = hash;
     95   if (ret->hash == NULL) {
     96     ret->hash = (lhash_hash_func) lh_strhash;
     97   }
     98 
     99   return ret;
    100 }
    101 
    102 void lh_free(_LHASH *lh) {
    103   size_t i;
    104   LHASH_ITEM *n, *next;
    105 
    106   if (lh == NULL) {
    107     return;
    108   }
    109 
    110   for (i = 0; i < lh->num_buckets; i++) {
    111     for (n = lh->buckets[i]; n != NULL; n = next) {
    112       next = n->next;
    113       OPENSSL_free(n);
    114     }
    115   }
    116 
    117   OPENSSL_free(lh->buckets);
    118   OPENSSL_free(lh);
    119 }
    120 
    121 size_t lh_num_items(const _LHASH *lh) { return lh->num_items; }
    122 
    123 /* get_next_ptr_and_hash returns a pointer to the pointer that points to the
    124  * item equal to |data|. In other words, it searches for an item equal to |data|
    125  * and, if it's at the start of a chain, then it returns a pointer to an
    126  * element of |lh->buckets|, otherwise it returns a pointer to the |next|
    127  * element of the previous item in the chain. If an element equal to |data| is
    128  * not found, it returns a pointer that points to a NULL pointer. If |out_hash|
    129  * is not NULL, then it also puts the hash value of |data| in |*out_hash|. */
    130 static LHASH_ITEM **get_next_ptr_and_hash(const _LHASH *lh, uint32_t *out_hash,
    131                                           const void *data) {
    132   const uint32_t hash = lh->hash(data);
    133   LHASH_ITEM *cur, **ret;
    134 
    135   if (out_hash != NULL) {
    136     *out_hash = hash;
    137   }
    138 
    139   ret = &lh->buckets[hash % lh->num_buckets];
    140   for (cur = *ret; cur != NULL; cur = *ret) {
    141     if (lh->comp(cur->data, data) == 0) {
    142       break;
    143     }
    144     ret = &cur->next;
    145   }
    146 
    147   return ret;
    148 }
    149 
    150 void *lh_retrieve(const _LHASH *lh, const void *data) {
    151   LHASH_ITEM **next_ptr;
    152 
    153   next_ptr = get_next_ptr_and_hash(lh, NULL, data);
    154 
    155   if (*next_ptr == NULL) {
    156     return NULL;
    157   }
    158 
    159   return (*next_ptr)->data;
    160 }
    161 
    162 /* lh_rebucket allocates a new array of |new_num_buckets| pointers and
    163  * redistributes the existing items into it before making it |lh->buckets| and
    164  * freeing the old array. */
    165 static void lh_rebucket(_LHASH *lh, const size_t new_num_buckets) {
    166   LHASH_ITEM **new_buckets, *cur, *next;
    167   size_t i, alloc_size;
    168 
    169   alloc_size = sizeof(LHASH_ITEM *) * new_num_buckets;
    170   if (alloc_size / sizeof(LHASH_ITEM*) != new_num_buckets) {
    171     return;
    172   }
    173 
    174   new_buckets = OPENSSL_malloc(alloc_size);
    175   if (new_buckets == NULL) {
    176     return;
    177   }
    178   memset(new_buckets, 0, alloc_size);
    179 
    180   for (i = 0; i < lh->num_buckets; i++) {
    181     for (cur = lh->buckets[i]; cur != NULL; cur = next) {
    182       const size_t new_bucket = cur->hash % new_num_buckets;
    183       next = cur->next;
    184       cur->next = new_buckets[new_bucket];
    185       new_buckets[new_bucket] = cur;
    186     }
    187   }
    188 
    189   OPENSSL_free(lh->buckets);
    190 
    191   lh->num_buckets = new_num_buckets;
    192   lh->buckets = new_buckets;
    193 }
    194 
    195 /* lh_maybe_resize resizes the |buckets| array if needed. */
    196 static void lh_maybe_resize(_LHASH *lh) {
    197   size_t avg_chain_length;
    198 
    199   if (lh->callback_depth > 0) {
    200     /* Don't resize the hash if we are currently iterating over it. */
    201     return;
    202   }
    203 
    204   assert(lh->num_buckets >= kMinNumBuckets);
    205   avg_chain_length = lh->num_items / lh->num_buckets;
    206 
    207   if (avg_chain_length > kMaxAverageChainLength) {
    208     const size_t new_num_buckets = lh->num_buckets * 2;
    209 
    210     if (new_num_buckets > lh->num_buckets) {
    211       lh_rebucket(lh, new_num_buckets);
    212     }
    213   } else if (avg_chain_length < kMinAverageChainLength &&
    214              lh->num_buckets > kMinNumBuckets) {
    215     size_t new_num_buckets = lh->num_buckets / 2;
    216 
    217     if (new_num_buckets < kMinNumBuckets) {
    218       new_num_buckets = kMinNumBuckets;
    219     }
    220 
    221     lh_rebucket(lh, new_num_buckets);
    222   }
    223 }
    224 
    225 int lh_insert(_LHASH *lh, void **old_data, void *data) {
    226   uint32_t hash;
    227   LHASH_ITEM **next_ptr, *item;
    228 
    229   *old_data = NULL;
    230   next_ptr = get_next_ptr_and_hash(lh, &hash, data);
    231 
    232 
    233   if (*next_ptr != NULL) {
    234     /* An element equal to |data| already exists in the hash table. It will be
    235      * replaced. */
    236     *old_data = (*next_ptr)->data;
    237     (*next_ptr)->data = data;
    238     return 1;
    239   }
    240 
    241   /* An element equal to |data| doesn't exist in the hash table yet. */
    242   item = OPENSSL_malloc(sizeof(LHASH_ITEM));
    243   if (item == NULL) {
    244     return 0;
    245   }
    246 
    247   item->data = data;
    248   item->hash = hash;
    249   item->next = NULL;
    250   *next_ptr = item;
    251   lh->num_items++;
    252   lh_maybe_resize(lh);
    253 
    254   return 1;
    255 }
    256 
    257 void *lh_delete(_LHASH *lh, const void *data) {
    258   LHASH_ITEM **next_ptr, *item, *ret;
    259 
    260   next_ptr = get_next_ptr_and_hash(lh, NULL, data);
    261 
    262   if (*next_ptr == NULL) {
    263     /* No such element. */
    264     return NULL;
    265   }
    266 
    267   item = *next_ptr;
    268   *next_ptr = item->next;
    269   ret = item->data;
    270   OPENSSL_free(item);
    271 
    272   lh->num_items--;
    273   lh_maybe_resize(lh);
    274 
    275   return ret;
    276 }
    277 
    278 static void lh_doall_internal(_LHASH *lh, void (*no_arg_func)(void *),
    279                               void (*arg_func)(void *, void *), void *arg) {
    280   size_t i;
    281   LHASH_ITEM *cur, *next;
    282 
    283   if (lh == NULL) {
    284     return;
    285   }
    286 
    287   if (lh->callback_depth < UINT_MAX) {
    288     /* |callback_depth| is a saturating counter. */
    289     lh->callback_depth++;
    290   }
    291 
    292   for (i = 0; i < lh->num_buckets; i++) {
    293     for (cur = lh->buckets[i]; cur != NULL; cur = next) {
    294       next = cur->next;
    295       if (arg_func) {
    296         arg_func(cur->data, arg);
    297       } else {
    298         no_arg_func(cur->data);
    299       }
    300     }
    301   }
    302 
    303   if (lh->callback_depth < UINT_MAX) {
    304     lh->callback_depth--;
    305   }
    306 
    307   /* The callback may have added or removed elements and the non-zero value of
    308    * |callback_depth| will have suppressed any resizing. Thus any needed
    309    * resizing is done here. */
    310   lh_maybe_resize(lh);
    311 }
    312 
    313 void lh_doall(_LHASH *lh, void (*func)(void *)) {
    314   lh_doall_internal(lh, func, NULL, NULL);
    315 }
    316 
    317 void lh_doall_arg(_LHASH *lh, void (*func)(void *, void *), void *arg) {
    318   lh_doall_internal(lh, NULL, func, arg);
    319 }
    320 
    321 uint32_t lh_strhash(const char *c) {
    322   /* The following hash seems to work very well on normal text strings
    323    * no collisions on /usr/dict/words and it distributes on %2^n quite
    324    * well, not as good as MD5, but still good. */
    325   unsigned long ret = 0;
    326   long n;
    327   unsigned long v;
    328   int r;
    329 
    330   if ((c == NULL) || (*c == '\0')) {
    331     return (ret);
    332   }
    333 
    334   n = 0x100;
    335   while (*c) {
    336     v = n | (*c);
    337     n += 0x100;
    338     r = (int)((v >> 2) ^ v) & 0x0f;
    339     ret = (ret << r) | (ret >> (32 - r));
    340     ret &= 0xFFFFFFFFL;
    341     ret ^= v * v;
    342     c++;
    343   }
    344 
    345   return ((ret >> 16) ^ ret);
    346 }
    347