xref: /illumos-gate/usr/src/cmd/sgs/link_audit/common/hash.c (revision e2294b844b9f4bfc375e88fd1260d9a39ffc82e1)
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 != '\0') {
256 		result += (*s++ << i++);
257 	}
258 
259 	/* LINTED */
260 	return ((int)(result % modulo));
261 }
262