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