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
32 static int hash_string(const char *, long);
33
34 hash *
make_hash(size_t size)35 make_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
48 hash *
make_ihash(size_t size)49 make_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
62 char **
get_hash(hash * tbl,char * key)63 get_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
113 char **
find_hash(hash * tbl,const char * key)114 find_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
136 char *
del_hash(hash * tbl,const char * key)137 del_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
200 size_t
operate_hash(hash * tbl,void (* ptr)(),const char * usr_arg)201 operate_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
214 size_t
operate_hash_addr(hash * tbl,void (* ptr)(),const char * usr_arg)215 operate_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
228 void
destroy_hash(hash * tbl,int (* ptr)(),const char * usr_arg)229 destroy_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
249 static int
hash_string(const char * s,long modulo)250 hash_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