1/* $Id: hash.c,v 1.1.1.1 2006-12-04 00:45:28 Exp $ */ 2 3/* 4 * Copyright (C) International Business Machines Corp., 2003 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. Neither the name of the project nor the names of its contributors 16 * may be used to endorse or promote products derived from this software 17 * without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND 20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 * ARE DISCLAIMED. IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE 23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 29 * SUCH DAMAGE. 30 */ 31 32/* Author: Elizabeth Kon, beth@us.ibm.com */ 33 34#include <stdint.h> 35#include <stdlib.h> 36#include <stdio.h> 37#include <syslog.h> 38 39#include "hash.h" 40 41#ifdef __GNUC__ 42extern void dprintf(int, const char *, ...) 43 __attribute__ ((__format__(__printf__, 2, 3))); 44#else 45extern void dprintf __P((int, const char *, ...)); 46#endif 47 48struct hash_table * hash_table_create ( 49 unsigned int hash_size, 50 unsigned int (*hash_function)(const void *hash_key), 51 void * (*find_hashkey)(const void *data), 52 int (*compare_hashkey)(const void *data, const void *hashkey)) 53{ 54 int i; 55 struct hash_table *hash_tbl; 56 hash_tbl = malloc(sizeof(struct hash_table)); 57 if (!hash_tbl) { 58 dprintf(LOG_ERR, "Couldn't allocate hash table"); 59 return NULL; 60 } 61 hash_tbl->hash_list = malloc(sizeof(struct hashlist_element *)*hash_size); 62 for (i=0; i<hash_size; i++) { 63 hash_tbl->hash_list[i] = NULL; 64 } 65 hash_tbl->hash_count = 0; 66 hash_tbl->hash_size = hash_size; 67 hash_tbl->hash_function = hash_function; 68 hash_tbl->find_hashkey = find_hashkey; 69 hash_tbl->compare_hashkey = compare_hashkey; 70 return hash_tbl; 71} 72 73int hash_add(struct hash_table *hash_tbl, const void *key, void *data) 74{ 75 int index; 76 struct hashlist_element *element; 77 element = (struct hashlist_element *)malloc(sizeof(struct hashlist_element)); 78 if(!element){ 79 dprintf(LOG_ERR, "Could not malloc hashlist_element"); 80 return (-1); 81 } 82 if (hash_full(hash_tbl)) { 83 grow_hash(hash_tbl); 84 } 85 index = hash_tbl->hash_function(key) % hash_tbl->hash_size; 86 if (hash_search(hash_tbl, key)) { 87 dprintf(LOG_DEBUG, "hash_add: duplicated item"); 88 return HASH_COLLISION; 89 } 90 element->next = hash_tbl->hash_list[index]; 91 hash_tbl->hash_list[index] = element; 92 element->data = data; 93 hash_tbl->hash_count++; 94 return 0; 95} 96 97int hash_delete(struct hash_table *hash_tbl, const void *key) 98{ 99 int index; 100 struct hashlist_element *element, *prev_element = NULL; 101 index = hash_tbl->hash_function(key) % hash_tbl->hash_size; 102 element = hash_tbl->hash_list[index]; 103 while (element) { 104 if (MATCH == hash_tbl->compare_hashkey(element->data, key)) { 105 if(prev_element){ 106 prev_element->next = element->next; 107 } else { 108 hash_tbl->hash_list[index] = element->next; 109 } 110 element->next = NULL; 111 free(element); 112 hash_tbl->hash_count--; 113 return 0; 114 } 115 prev_element = element; 116 element = element->next; 117 } 118 return HASH_ITEM_NOT_FOUND; 119} 120 121void * hash_search(struct hash_table *hash_tbl, const void *key) 122{ 123 int index; 124 struct hashlist_element *element; 125 index = hash_tbl->hash_function(key) % hash_tbl->hash_size; 126 element = hash_tbl->hash_list[index]; 127 while (element) { 128 if (MATCH == hash_tbl->compare_hashkey(element->data, key)) { 129 return element->data; 130 } 131 element = element->next; 132 } 133 return NULL; 134} 135 136int hash_full(struct hash_table *hash_tbl) { 137 int rc = 0; 138 if((hash_tbl->hash_count)*100/(hash_tbl->hash_size) > 90) rc = 1; 139 return rc; 140} 141 142int grow_hash(struct hash_table *hash_tbl) { 143 int i, hash_size, index; 144 struct hashlist_element *element, *oldnext; 145 struct hash_table *new_table; 146 void *key; 147 hash_size = 2*hash_tbl->hash_size; 148 new_table = hash_table_create(hash_size, hash_tbl->hash_function, 149 hash_tbl->find_hashkey, hash_tbl->compare_hashkey); 150 if (!new_table) { 151 dprintf(LOG_ERR, "couldn't grow hash table"); 152 return (-1); 153 } 154 for (i = 0; i < hash_tbl->hash_size; i++) { 155 element = hash_tbl->hash_list[i]; 156 while (element) { 157 key = hash_tbl->find_hashkey(element->data); 158 index = new_table->hash_function(key) % hash_size; 159 oldnext = element->next; 160 element->next = new_table->hash_list[index]; 161 new_table->hash_list[index] = element; 162 new_table->hash_count++; 163 element = oldnext; 164 } 165 } 166 free(hash_tbl->hash_list); 167 hash_tbl->hash_count = new_table->hash_count; 168 hash_tbl->hash_size = hash_size; 169 hash_tbl->hash_list = new_table->hash_list; 170 free(new_table); 171 return 0; 172} 173