1/*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License (the "License").
6 * You may not use this file except in compliance with the License.
7 *
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 * or http://www.opensolaris.org/os/licensing.
10 * See the License for the specific language governing permissions
11 * and limitations under the License.
12 *
13 * When distributing Covered Code, include this CDDL HEADER in each
14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 * If applicable, add the following below this CDDL HEADER, with the
16 * fields enclosed by brackets "[]" replaced with your own identifying
17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 *
19 * CDDL HEADER END
20 */
21
22/*
23 * Copyright (c) 1996, 2010, Oracle and/or its affiliates. All rights reserved.
24 */
25#include <stdio.h>
26#include <stdlib.h>
27#include <string.h>
28#include <synch.h>
29#include <memory.h>
30#include "hash.h"
31
32static int    hash_string(const char *, long);
33
34hash *
35make_hash(size_t size)
36{
37	hash	*ptr;
38
39	ptr = malloc(sizeof (*ptr));
40	ptr->size = size;
41	ptr->table = malloc((size_t)(sizeof (hash_entry *) * size));
42	(void) memset((char *)ptr->table, 0, sizeof (hash_entry *) * size);
43	ptr->start = NULL;
44	ptr->hash_type = String_Key;
45	return (ptr);
46}
47
48hash *
49make_ihash(size_t size)
50{
51	hash	*ptr;
52
53	ptr = malloc(sizeof (*ptr));
54	ptr->size = size;
55	ptr->table = malloc(sizeof (hash_entry *) * size);
56	(void) memset((char *)ptr->table, 0, sizeof (hash_entry *) * size);
57	ptr->start = NULL;
58	ptr->hash_type = Integer_Key;
59	return (ptr);
60}
61
62char **
63get_hash(hash *tbl, char *key)
64{
65	long		bucket;
66	hash_entry	*tmp, *new;
67
68	if (tbl->hash_type == String_Key) {
69		tmp = tbl->table[bucket = hash_string(key, tbl->size)];
70	} else {
71		tmp = tbl->table[bucket = labs((long)key) % tbl->size];
72	}
73
74	if (tbl->hash_type == String_Key) {
75		while (tmp != NULL) {
76			if (strcmp(tmp->key, key) == 0) {
77				return (&tmp->data);
78			}
79			tmp = tmp->next_entry;
80		}
81	} else {
82		while (tmp != NULL) {
83			if (tmp->key == key) {
84				return (&tmp->data);
85			}
86			tmp = tmp->next_entry;
87		}
88	}
89
90	/*
91	 * not found....
92	 * insert new entry into bucket...
93	 */
94	new = malloc(sizeof (*new));
95	new->key = ((tbl->hash_type == String_Key)?strdup(key):key);
96
97	/*
98	 * hook into chain from tbl...
99	 */
100	new->right_entry = NULL;
101	new->left_entry = tbl->start;
102	tbl->start = new;
103
104	/*
105	 * hook into bucket chain
106	 */
107	new->next_entry = tbl->table[bucket];
108	tbl->table[bucket] = new;
109	new->data = NULL;		/* so we know that it is new */
110	return (&new->data);
111}
112
113char **
114find_hash(hash *tbl, const char *key)
115{
116	hash_entry 	*tmp;
117
118	if (tbl->hash_type == String_Key) {
119		tmp = tbl->table[hash_string(key, tbl->size)];
120		for (; tmp != NULL; tmp = tmp->next_entry) {
121			if (strcmp(tmp->key, key) == 0) {
122				return (&tmp->data);
123			}
124		}
125	} else {
126		tmp = tbl->table[labs((long)key) % tbl->size];
127		for (; tmp != NULL; tmp = tmp->next_entry) {
128			if (tmp->key == key) {
129				return (&tmp->data);
130			}
131		}
132	}
133	return (NULL);
134}
135
136char *
137del_hash(hash *tbl, const char *key)
138{
139	ulong_t bucket;
140	hash_entry * tmp, * prev = NULL;
141
142	if (tbl->hash_type == String_Key) {
143		bucket = hash_string(key, tbl->size);
144	} else {
145		bucket = labs((long)key) % tbl->size;
146	}
147
148	if ((tmp = tbl->table[bucket]) == NULL) {
149		return (NULL);
150	} else {
151		if (tbl->hash_type == String_Key) {
152			while (tmp != NULL) {
153				if (strcmp(tmp->key, key) == 0) {
154					break;  /* found item to delete ! */
155				}
156				prev = tmp;
157				tmp  = tmp->next_entry;
158			}
159		} else {
160			while (tmp != NULL) {
161				if (tmp->key == key) {
162					break;
163				}
164				prev = tmp;
165				tmp  = tmp->next_entry;
166			}
167		}
168		if (tmp == NULL) {
169			return (NULL); /* not found */
170		}
171	}
172
173	/*
174	 * tmp now points to entry marked for deletion, prev to
175	 * item preceding in bucket chain or NULL if tmp is first.
176	 * remove from bucket chain first....
177	 */
178	if (tbl->hash_type == String_Key) {
179		free(tmp->key);
180	}
181	if (prev != NULL) {
182		prev->next_entry = tmp->next_entry;
183	} else {
184		tbl->table[bucket] = tmp->next_entry;
185	}
186
187	/*
188	 * now remove from tbl chain....
189	 */
190	if (tmp->right_entry != NULL) { /* not first in chain.... */
191		tmp->right_entry->left_entry = (tmp->left_entry ?
192		    tmp->left_entry->right_entry: NULL);
193	} else {
194		tbl->start = (tmp->left_entry ?tmp->left_entry->right_entry:
195		    NULL);
196	}
197	return (tmp->data);
198}
199
200size_t
201operate_hash(hash *tbl, void (*ptr)(), const char *usr_arg)
202{
203	hash_entry	*tmp = tbl->start;
204	size_t		c = 0;
205
206	while (tmp) {
207		(*ptr)(tmp->data, usr_arg, tmp->key);
208		tmp = tmp->left_entry;
209		c++;
210	}
211	return (c);
212}
213
214size_t
215operate_hash_addr(hash *tbl, void (*ptr)(), const char *usr_arg)
216{
217	hash_entry	*tmp = tbl->start;
218	size_t		c = 0;
219
220	while (tmp) {
221		(*ptr)(&(tmp->data), usr_arg, tmp->key);
222		tmp = tmp->left_entry;
223		c++;
224	}
225	return (c);
226}
227
228void
229destroy_hash(hash *tbl, int (*ptr)(), const char *usr_arg)
230{
231	hash_entry * tmp = tbl->start, * prev;
232
233	while (tmp) {
234		if (ptr) {
235			(void) (*ptr)(tmp->data, usr_arg, tmp->key);
236		}
237
238		if (tbl->hash_type == String_Key) {
239			free(tmp->key);
240		}
241		prev = tmp;
242		tmp = tmp->left_entry;
243		free((char *)prev);
244	}
245	free((char *)tbl->table);
246	free(tbl);
247}
248
249static int
250hash_string(const char *s, long modulo)
251{
252	unsigned int	result = 0;
253	int		i = 1;
254
255	while (*s != NULL) {
256		result += (*s++ << i++);
257	}
258
259	/* LINTED */
260	return ((int)(result % modulo));
261}
262