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