/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * * This package is an SSL implementation written * by Eric Young (eay@cryptsoft.com). * The implementation was written so as to conform with Netscapes SSL. * * This library is free for commercial and non-commercial use as long as * the following conditions are aheared to. The following conditions * apply to all code found in this distribution, be it the RC4, RSA, * lhash, DES, etc., code; not just the SSL code. The SSL documentation * included with this distribution is covered by the same copyright terms * except that the holder is Tim Hudson (tjh@cryptsoft.com). * * Copyright remains Eric Young's, and as such any Copyright notices in * the code are not to be removed. * If this package is used in a product, Eric Young should be given attribution * as the author of the parts of the library used. * This can be in the form of a textual message at program startup or * in documentation (online or textual) provided with the package. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 3. All advertising materials mentioning features or use of this software * must display the following acknowledgement: * "This product includes cryptographic software written by * Eric Young (eay@cryptsoft.com)" * The word 'cryptographic' can be left out if the rouines from the library * being used are not cryptographic related :-). * 4. If you include any Windows specific code (or a derivative thereof) from * the apps directory (application code) you must include an acknowledgement: * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" * * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * The licence and distribution terms for any publically available version or * derivative of this code cannot be changed. i.e. this code cannot simply be * copied and put under another distribution licence * [including the GNU Public Licence.] */ #include <openssl/lhash.h> #include <assert.h> #include <limits.h> #include <string.h> #include <openssl/mem.h> #include "internal.h" #include "../internal.h" // kMinNumBuckets is the minimum size of the buckets array in an |_LHASH|. static const size_t kMinNumBuckets = …; // kMaxAverageChainLength contains the maximum, average chain length. When the // average chain length exceeds this value, the hash table will be resized. static const size_t kMaxAverageChainLength = …; static const size_t kMinAverageChainLength = …; // lhash_item_st is an element of a hash chain. It points to the opaque data // for this element and to the next item in the chain. The linked-list is NULL // terminated. LHASH_ITEM; struct lhash_st { … }; _LHASH *OPENSSL_lh_new(lhash_hash_func hash, lhash_cmp_func comp) { … } void OPENSSL_lh_free(_LHASH *lh) { … } size_t OPENSSL_lh_num_items(const _LHASH *lh) { … } // get_next_ptr_and_hash returns a pointer to the pointer that points to the // item equal to |data|. In other words, it searches for an item equal to |data| // and, if it's at the start of a chain, then it returns a pointer to an // element of |lh->buckets|, otherwise it returns a pointer to the |next| // element of the previous item in the chain. If an element equal to |data| is // not found, it returns a pointer that points to a NULL pointer. If |out_hash| // is not NULL, then it also puts the hash value of |data| in |*out_hash|. static LHASH_ITEM **get_next_ptr_and_hash(const _LHASH *lh, uint32_t *out_hash, const void *data, lhash_hash_func_helper call_hash_func, lhash_cmp_func_helper call_cmp_func) { … } // get_next_ptr_by_key behaves like |get_next_ptr_and_hash| but takes a key // which may be a different type from the values stored in |lh|. static LHASH_ITEM **get_next_ptr_by_key(const _LHASH *lh, const void *key, uint32_t key_hash, int (*cmp_key)(const void *key, const void *value)) { … } void *OPENSSL_lh_retrieve(const _LHASH *lh, const void *data, lhash_hash_func_helper call_hash_func, lhash_cmp_func_helper call_cmp_func) { … } void *OPENSSL_lh_retrieve_key(const _LHASH *lh, const void *key, uint32_t key_hash, int (*cmp_key)(const void *key, const void *value)) { … } // lh_rebucket allocates a new array of |new_num_buckets| pointers and // redistributes the existing items into it before making it |lh->buckets| and // freeing the old array. static void lh_rebucket(_LHASH *lh, const size_t new_num_buckets) { … } // lh_maybe_resize resizes the |buckets| array if needed. static void lh_maybe_resize(_LHASH *lh) { … } int OPENSSL_lh_insert(_LHASH *lh, void **old_data, void *data, lhash_hash_func_helper call_hash_func, lhash_cmp_func_helper call_cmp_func) { … } void *OPENSSL_lh_delete(_LHASH *lh, const void *data, lhash_hash_func_helper call_hash_func, lhash_cmp_func_helper call_cmp_func) { … } void OPENSSL_lh_doall_arg(_LHASH *lh, void (*func)(void *, void *), void *arg) { … }