1/* 2 * Copyright (c) 2011-12 Apple Inc. All Rights Reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23 24/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 25 * All rights reserved. 26 * 27 * This package is an SSL implementation written 28 * by Eric Young (eay@cryptsoft.com). 29 * The implementation was written so as to conform with Netscapes SSL. 30 * 31 * This library is free for commercial and non-commercial use as long as 32 * the following conditions are aheared to. The following conditions 33 * apply to all code found in this distribution, be it the RC4, RSA, 34 * lhash, DES, etc., code; not just the SSL code. The SSL documentation 35 * included with this distribution is covered by the same copyright terms 36 * except that the holder is Tim Hudson (tjh@cryptsoft.com). 37 * 38 * Copyright remains Eric Young's, and as such any Copyright notices in 39 * the code are not to be removed. 40 * If this package is used in a product, Eric Young should be given attribution 41 * as the author of the parts of the library used. 42 * This can be in the form of a textual message at program startup or 43 * in documentation (online or textual) provided with the package. 44 * 45 * Redistribution and use in source and binary forms, with or without 46 * modification, are permitted provided that the following conditions 47 * are met: 48 * 1. Redistributions of source code must retain the copyright 49 * notice, this list of conditions and the following disclaimer. 50 * 2. Redistributions in binary form must reproduce the above copyright 51 * notice, this list of conditions and the following disclaimer in the 52 * documentation and/or other materials provided with the distribution. 53 * 3. All advertising materials mentioning features or use of this software 54 * must display the following acknowledgement: 55 * "This product includes cryptographic software written by 56 * Eric Young (eay@cryptsoft.com)" 57 * The word 'cryptographic' can be left out if the rouines from the library 58 * being used are not cryptographic related :-). 59 * 4. If you include any Windows specific code (or a derivative thereof) from 60 * the apps directory (application code) you must include an acknowledgement: 61 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 62 * 63 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 64 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 65 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 66 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 67 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 68 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 69 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 70 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 71 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 72 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 73 * SUCH DAMAGE. 74 * 75 * The licence and distribution terms for any publically available version or 76 * derivative of this code cannot be changed. i.e. this code cannot simply be 77 * copied and put under another distribution licence 78 * [including the GNU Public Licence.] 79 */ 80 81/* Header for dynamic hash table routines 82 * Author - Eric Young 83 */ 84 85#ifndef _OSSL_LHASH_H_ 86#define _OSSL_LHASH_H_ 87 88#include <stdio.h> 89 90#include "ossl-bio.h" 91 92/* symbol rewrite */ 93#define lh_new ossl_lh_new 94#define lh_free ossl_lh_free 95#define lh_insert ossl_lh_insert 96#define lh_delete ossl_lh_delete 97#define lh_retrieve ossl_lh_retrieve 98#define lh_doall ossl_lh_doall 99#define lh_doall_arg ossl_lh_doall_arg 100#define lh_strhash ossl_lh_strhash 101#define lh_num_items ossl_lh_num_items 102 103#define lh_stats ossl_lh_stats 104#define lh_node_stats ossl_lh_node_stats 105#define lh_node_usage_stats ossl_lh_node_usage_stats 106 107#define lh_stats_bio ossl_lh_stats_bio 108#define lh_node_stats_bio ossl_lh_node_stats_bio 109#define lh_node_usage_stats_bio ossl_lh_node_usage_stats_bio 110 111#ifdef __cplusplus 112extern "C" { 113#endif 114 115typedef struct lhash_node_st { 116 void * data; 117 struct lhash_node_st * next; 118#ifndef NO_HASH_COMP 119 unsigned long hash; 120#endif 121} LHASH_NODE; 122 123typedef int (*LHASH_COMP_FN_TYPE)(const void *, const void *); 124typedef unsigned long (*LHASH_HASH_FN_TYPE)(const void *); 125typedef void (*LHASH_DOALL_FN_TYPE)(void *); 126typedef void (*LHASH_DOALL_ARG_FN_TYPE)(void *, void *); 127 128/* Macros for declaring and implementing type-safe wrappers for LHASH callbacks. 129 * This way, callbacks can be provided to LHASH structures without function 130 * pointer casting and the macro-defined callbacks provide per-variable casting 131 * before deferring to the underlying type-specific callbacks. NB: It is 132 * possible to place a "static" in front of both the DECLARE and IMPLEMENT 133 * macros if the functions are strictly internal. */ 134 135/* First: "hash" functions */ 136#define DECLARE_LHASH_HASH_FN(f_name, o_type) \ 137 unsigned long f_name ## _LHASH_HASH(const void *); 138#define IMPLEMENT_LHASH_HASH_FN(f_name, o_type) \ 139 unsigned long f_name ## _LHASH_HASH(const void *arg) { \ 140 o_type a = (o_type)arg; \ 141 return f_name(a); } 142#define LHASH_HASH_FN(f_name) f_name ## _LHASH_HASH 143 144/* Second: "compare" functions */ 145#define DECLARE_LHASH_COMP_FN(f_name, o_type) \ 146 int f_name ## _LHASH_COMP(const void *, const void *); 147#define IMPLEMENT_LHASH_COMP_FN(f_name, o_type) \ 148 int f_name ## _LHASH_COMP(const void *arg1, const void *arg2) { \ 149 o_type a = (o_type)arg1; \ 150 o_type b = (o_type)arg2; \ 151 return f_name(a, b); } 152#define LHASH_COMP_FN(f_name) f_name ## _LHASH_COMP 153 154/* Third: "doall" functions */ 155#define DECLARE_LHASH_DOALL_FN(f_name, o_type) \ 156 void f_name ## _LHASH_DOALL(void *); 157#define IMPLEMENT_LHASH_DOALL_FN(f_name, o_type) \ 158 void f_name ## _LHASH_DOALL(void *arg) { \ 159 o_type a = (o_type)arg; \ 160 f_name(a); } 161#define LHASH_DOALL_FN(f_name) f_name ## _LHASH_DOALL 162 163/* Fourth: "doall_arg" functions */ 164#define DECLARE_LHASH_DOALL_ARG_FN(f_name, o_type, a_type) \ 165 void f_name ## _LHASH_DOALL_ARG(void *, void *); 166#define IMPLEMENT_LHASH_DOALL_ARG_FN(f_name, o_type, a_type) \ 167 void f_name ## _LHASH_DOALL_ARG(void *arg1, void *arg2) { \ 168 o_type a = (o_type)arg1; \ 169 a_type b = (a_type)arg2; \ 170 f_name(a, b); } 171#define LHASH_DOALL_ARG_FN(f_name) f_name ## _LHASH_DOALL_ARG 172 173typedef struct lhash_st { 174 LHASH_NODE ** b; 175 LHASH_COMP_FN_TYPE comp; 176 LHASH_HASH_FN_TYPE hash; 177 unsigned int num_nodes; 178 unsigned int num_alloc_nodes; 179 unsigned int p; 180 unsigned int pmax; 181 unsigned long up_load; /* load times 256 */ 182 unsigned long down_load; /* load times 256 */ 183 unsigned long num_items; 184 185 unsigned long num_expands; 186 unsigned long num_expand_reallocs; 187 unsigned long num_contracts; 188 unsigned long num_contract_reallocs; 189 unsigned long num_hash_calls; 190 unsigned long num_comp_calls; 191 unsigned long num_insert; 192 unsigned long num_replace; 193 unsigned long num_delete; 194 unsigned long num_no_delete; 195 unsigned long num_retrieve; 196 unsigned long num_retrieve_miss; 197 unsigned long num_hash_comps; 198 199 int error; 200} LHASH; 201 202#define LH_LOAD_MULT 256 203 204/* Indicates a malloc() error in the last call, this is only bad 205 * in lh_insert(). */ 206#define lh_error(lh) ((lh)->error) 207 208LHASH *lh_new(LHASH_HASH_FN_TYPE h, LHASH_COMP_FN_TYPE c); 209void lh_free(LHASH *lh); 210void *lh_insert(LHASH *lh, void *data); 211void *lh_delete(LHASH *lh, const void *data); 212void *lh_retrieve(LHASH *lh, const void *data); 213void lh_doall(LHASH *lh, LHASH_DOALL_FN_TYPE func); 214void lh_doall_arg(LHASH *lh, LHASH_DOALL_ARG_FN_TYPE func, void *arg); 215unsigned long lh_strhash(const char *c); 216unsigned long lh_num_items(const LHASH *lh); 217 218void lh_stats(const LHASH *lh, FILE *out); 219void lh_node_stats(const LHASH *lh, FILE *out); 220void lh_node_usage_stats(const LHASH *lh, FILE *out); 221 222void lh_stats_bio(const LHASH *lh, BIO *out); 223void lh_node_stats_bio(const LHASH *lh, BIO *out); 224void lh_node_usage_stats_bio(const LHASH *lh, BIO *out); 225 226#ifdef __cplusplus 227} 228#endif 229 230#endif /* _OSSL_LHASH_H_ */ 231