1 /* _ _ 2 ** _ __ ___ ___ __| | ___ ___| | mod_ssl 3 ** | '_ ` _ \ / _ \ / _` | / __/ __| | Apache Interface to OpenSSL 4 ** | | | | | | (_) | (_| | \__ \__ \ | www.modssl.org 5 ** |_| |_| |_|\___/ \__,_|___|___/___/_| ftp.modssl.org 6 ** |_____| 7 ** ssl_util_table.h 8 ** High Performance Hash Table Header 9 */ 10 11 /* ==================================================================== 12 * Copyright (c) 1999-2003 Ralf S. Engelschall. All rights reserved. 13 * 14 * Redistribution and use in source and binary forms, with or without 15 * modification, are permitted provided that the following conditions 16 * are met: 17 * 18 * 1. Redistributions of source code must retain the above copyright 19 * notice, this list of conditions and the following disclaimer. 20 * 21 * 2. Redistributions in binary form must reproduce the above copyright 22 * notice, this list of conditions and the following 23 * disclaimer in the documentation and/or other materials 24 * provided with the distribution. 25 * 26 * 3. All advertising materials mentioning features or use of this 27 * software must display the following acknowledgment: 28 * "This product includes software developed by 29 * Ralf S. Engelschall <rse@engelschall.com> for use in the 30 * mod_ssl project (http://www.modssl.org/)." 31 * 32 * 4. The names "mod_ssl" must not be used to endorse or promote 33 * products derived from this software without prior written 34 * permission. For written permission, please contact 35 * rse@engelschall.com. 36 * 37 * 5. Products derived from this software may not be called "mod_ssl" 38 * nor may "mod_ssl" appear in their names without prior 39 * written permission of Ralf S. Engelschall. 40 * 41 * 6. Redistributions of any form whatsoever must retain the following 42 * acknowledgment: 43 * "This product includes software developed by 44 * Ralf S. Engelschall <rse@engelschall.com> for use in the 45 * mod_ssl project (http://www.modssl.org/)." 46 * 47 * THIS SOFTWARE IS PROVIDED BY RALF S. ENGELSCHALL ``AS IS'' AND ANY 48 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 49 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 50 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL RALF S. ENGELSCHALL OR 51 * HIS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 52 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 53 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 54 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 55 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 56 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 57 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 58 * OF THE POSSIBILITY OF SUCH DAMAGE. 59 * ==================================================================== 60 */ 61 62 /* 63 * Generic hash table defines 64 * Table 4.1.0 July-28-1998 65 * 66 * This library is a generic open hash table with buckets and 67 * linked lists. It is pretty high performance. Each element 68 * has a key and a data. The user indexes on the key to find the 69 * data. 70 * 71 * Copyright 1998 by Gray Watson <gray@letters.com> 72 * 73 * Permission to use, copy, modify, and distribute this software for any 74 * purpose and without fee is hereby granted, provided that the above 75 * copyright notice and this permission notice appear in all copies, 76 * and that the name of Gray Watson not be used in advertising or 77 * publicity pertaining to distribution of the document or software 78 * without specific, written prior permission. 79 * 80 * Gray Watson makes no representations about the suitability of the 81 * software described herein for any purpose. It is provided "as is" 82 * without express or implied warranty. 83 */ 84 85 #ifndef SSL_UTIL_TABLE_H 86 #define SSL_UTIL_TABLE_H 87 88 #ifdef __cplusplus 89 extern "C" { 90 #endif /* __cplusplus */ 91 92 /* 93 * To build a "key" in any of the below routines, pass in a pointer to 94 * the key and its size [i.e. sizeof(int), etc]. With any of the 95 * "key" or "data" arguments, if their size is < 0, it will do an 96 * internal strlen of the item and add 1 for the \0. 97 * 98 * If you are using firstkey() and nextkey() functions, be careful if, 99 * after starting your firstkey loop, you use delete or insert, it 100 * will not crash but may produce interesting results. If you are 101 * deleting from firstkey to NULL it will work fine. 102 */ 103 104 /* return types for table functions */ 105 #define TABLE_ERROR_NONE 1 /* no error from function */ 106 #define TABLE_ERROR_PNT 2 /* bad table pointer */ 107 #define TABLE_ERROR_ARG_NULL 3 /* buffer args were null */ 108 #define TABLE_ERROR_SIZE 4 /* size of data was bad */ 109 #define TABLE_ERROR_OVERWRITE 5 /* key exists and we cant overwrite */ 110 #define TABLE_ERROR_NOT_FOUND 6 /* key does not exist */ 111 #define TABLE_ERROR_ALLOC 7 /* memory allocation error */ 112 #define TABLE_ERROR_LINEAR 8 /* no linear access started */ 113 #define TABLE_ERROR_OPEN 9 /* could not open file */ 114 #define TABLE_ERROR_SEEK 10 /* could not seek to pos in file */ 115 #define TABLE_ERROR_READ 11 /* could not read from file */ 116 #define TABLE_ERROR_WRITE 12 /* could not write to file */ 117 #define TABLE_ERROR_EMPTY 13 /* table is empty */ 118 #define TABLE_ERROR_NOT_EMPTY 14 /* table contains data */ 119 #define TABLE_ERROR_ALIGNMENT 15 /* invalid alignment value */ 120 121 /* 122 * Table flags set with table_attr. 123 */ 124 125 /* 126 * Automatically adjust the number of table buckets on the fly. 127 * Whenever the number of entries gets above some threshold, the 128 * number of buckets is realloced to a new size and each entry is 129 * re-hashed. Although this may take some time when it re-hashes, the 130 * table will perform better over time. 131 */ 132 #define TABLE_FLAG_AUTO_ADJUST (1<<0) 133 134 /* 135 * If the above auto-adjust flag is set, also adjust the number of 136 * table buckets down as we delete entries. 137 */ 138 #define TABLE_FLAG_ADJUST_DOWN (1<<1) 139 140 /* structure to walk through the fields in a linear order */ 141 typedef struct { 142 unsigned int tl_magic; /* magic structure to ensure correct init */ 143 unsigned int tl_bucket_c; /* where in the table buck array we are */ 144 unsigned int tl_entry_c; /* in the bucket, which entry we are on */ 145 } table_linear_t; 146 147 typedef int (*table_compare_t)(const void *key1, const int key1_size, 148 const void *data1, const int data1_size, 149 const void *key2, const int key2_size, 150 const void *data2, const int data2_size); 151 152 #ifndef TABLE_PRIVATE 153 typedef void table_t; 154 typedef void table_entry_t; 155 #endif 156 157 /* 158 * Prototypes 159 */ 160 extern table_t *table_alloc(const unsigned int bucket_n, int *error_p, void *(*malloc_f)(size_t size), void *(*calloc_f)(size_t number, size_t size), void *(*realloc_f)(void *ptr, size_t size), void (*free_f)(void *ptr)); 161 extern int table_attr(table_t *table_p, const int attr); 162 extern int table_set_data_alignment(table_t *table_p, const int alignment); 163 extern int table_clear(table_t *table_p); 164 extern int table_free(table_t *table_p); 165 extern int table_insert_kd(table_t *table_p, const void *key_buf, const int key_size, const void *data_buf, const int data_size, void **key_buf_p, void **data_buf_p, const char overwrite_b); 166 extern int table_insert(table_t *table_p, const void *key_buf, const int key_size, const void *data_buf, const int data_size, void **data_buf_p, const char overwrite_b); 167 extern int table_retrieve(table_t *table_p, const void *key_buf, const int key_size, void **data_buf_p, int *data_size_p); 168 extern int table_delete(table_t *table_p, const void *key_buf, const int key_size, void **data_buf_p, int *data_size_p); 169 extern int table_delete_first(table_t *table_p, void **key_buf_p, int *key_size_p, void **data_buf_p, int *data_size_p); 170 extern int table_info(table_t *table_p, int *num_buckets_p, int *num_entries_p); 171 extern int table_adjust(table_t *table_p, const int bucket_n); 172 extern const char *table_strerror(const int error); 173 extern int table_type_size(void); 174 extern int table_first(table_t *table_p, void **key_buf_p, int *key_size_p, void **data_buf_p, int *data_size_p); 175 extern int table_next(table_t *table_p, void **key_buf_p, int *key_size_p, void **data_buf_p, int *data_size_p); 176 extern int table_this(table_t *table_p, void **key_buf_p, int *key_size_p, void **data_buf_p, int *data_size_p); 177 extern int table_first_r(table_t *table_p, table_linear_t *linear_p, void **key_buf_p, int *key_size_p, void **data_buf_p, int *data_size_p); 178 extern int table_next_r(table_t *table_p, table_linear_t *linear_p, void **key_buf_p, int *key_size_p, void **data_buf_p, int *data_size_p); 179 extern int table_this_r(table_t *table_p, table_linear_t *linear_p, void **key_buf_p, int *key_size_p, void **data_buf_p, int *data_size_p); 180 extern table_t *table_read(const char *path, int *error_p, void *(*malloc_f)(size_t size), void *(*calloc_f)(size_t number, size_t size), void *(*realloc_f)(void *ptr, size_t size), void (*free_f)(void *ptr)); 181 extern int table_write(const table_t *table_p, const char *path, const int mode); 182 extern table_entry_t **table_order(table_t *table_p, table_compare_t compare, int *num_entries_p, int *error_p); 183 extern int table_entry_info(table_t *table_p, table_entry_t *entry_p, void **key_buf_p, int *key_size_p, void **data_buf_p, int *data_size_p); 184 185 #ifdef __cplusplus 186 } 187 #endif /* __cplusplus */ 188 189 #endif /* ! SSL_UTIL_TABLE_H */ 190