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 2007 Sun Microsystems, Inc.  All rights reserved.
24  * Use is subject to license terms.
25  */
26 
27 #include <stdlib.h>
28 #include <assert.h>
29 #include <pthread.h>
30 
31 #include "sip_hash.h"
32 
33 /*
34  * This file implements functions that add, search or remove an object
35  * from the hash table. The object is opaque to the hash functions. To add
36  * an object to the hash table, the caller provides the hash table,
37  * the object and the index into the hash table. To search an object,
38  * the caller provides the hash table, the digest (opaque), the index into
39  * the hash table and the function that does the actual match. Similarly,
40  * for removing an object, the caller provides the hash table, the digest
41  * (opaque), the index into the hash table and the function that does
42  * the acutal deletion of the object - if the deletion is successful,
43  * the object is taken off of the hash table.
44  */
45 
46 /*
47  * Given an object and the hash index, add it to the given hash table
48  */
49 int
sip_hash_add(sip_hash_t * sip_hash,void * obj,int hindex)50 sip_hash_add(sip_hash_t	*sip_hash, void *obj, int hindex)
51 {
52 	sip_hash_obj_t	*new_obj;
53 	sip_hash_t	*hash_entry;
54 
55 	assert(obj != NULL);
56 
57 	new_obj = (sip_hash_obj_t *)malloc(sizeof (*new_obj));
58 	if (new_obj == NULL)
59 		return (-1);
60 	new_obj->sip_obj = obj;
61 	new_obj->next_obj = NULL;
62 	new_obj->prev_obj = NULL;
63 	hash_entry = &sip_hash[hindex];
64 	(void) pthread_mutex_lock(&hash_entry->sip_hash_mutex);
65 	if (hash_entry->hash_count == 0) {
66 		assert(hash_entry->hash_head == NULL);
67 		assert(hash_entry->hash_tail == NULL);
68 		hash_entry->hash_head = new_obj;
69 	} else {
70 		hash_entry->hash_tail->next_obj = new_obj;
71 		new_obj->prev_obj = hash_entry->hash_tail;
72 	}
73 	hash_entry->hash_tail = new_obj;
74 	hash_entry->hash_count++;
75 	(void) pthread_mutex_unlock(&hash_entry->sip_hash_mutex);
76 	return (0);
77 }
78 
79 /*
80  * Given the hash table, the digest to be searched for,  index into the hash
81  * table and the function to do the actual matching, return the object,
82  * if found.
83  */
84 void *
sip_hash_find(sip_hash_t * sip_hash,void * digest,int hindex,boolean_t (* match_func)(void *,void *))85 sip_hash_find(sip_hash_t *sip_hash, void *digest, int hindex,
86     boolean_t (*match_func)(void *, void *))
87 {
88 	int		count;
89 	sip_hash_obj_t	*tmp;
90 	sip_hash_t	*hash_entry;
91 
92 	hash_entry =  &sip_hash[hindex];
93 	(void) pthread_mutex_lock(&hash_entry->sip_hash_mutex);
94 	tmp = hash_entry->hash_head;
95 	for (count = 0; count < hash_entry->hash_count; count++) {
96 		if (match_func(tmp->sip_obj, digest)) {
97 			(void) pthread_mutex_unlock(
98 			    &hash_entry->sip_hash_mutex);
99 			return (tmp->sip_obj);
100 		}
101 		tmp = tmp->next_obj;
102 	}
103 	(void) pthread_mutex_unlock(&hash_entry->sip_hash_mutex);
104 	return (NULL);
105 }
106 
107 /*
108  * Walk the hash table and invoke func on each object. 'arg' is passed
109  * to 'func'
110  */
111 void
sip_walk_hash(sip_hash_t * sip_hash,void (* func)(void *,void *),void * arg)112 sip_walk_hash(sip_hash_t *sip_hash, void (*func)(void *, void *), void *arg)
113 {
114 	sip_hash_t	*hash_entry;
115 	int		count;
116 	int		hcount;
117 	sip_hash_obj_t	*tmp;
118 
119 	for (count = 0; count < SIP_HASH_SZ; count++) {
120 		hash_entry =  &sip_hash[count];
121 		(void) pthread_mutex_lock(&hash_entry->sip_hash_mutex);
122 		tmp = hash_entry->hash_head;
123 		for (hcount = 0; hcount < hash_entry->hash_count; hcount++) {
124 			assert(tmp->sip_obj != NULL);
125 			func(tmp->sip_obj, arg);
126 			tmp = tmp->next_obj;
127 		}
128 		(void) pthread_mutex_unlock(&hash_entry->sip_hash_mutex);
129 	}
130 }
131 
132 /*
133  * Given the hash table, the digest to be searched for,  the index into the
134  * hash table and the  delete function provided to do the actual deletion,
135  * remove the object from the hash table (i.e. only if the object is deleted).
136  */
137 void
sip_hash_delete(sip_hash_t * sip_hash,void * digest,int hindex,boolean_t (* del_func)(void *,void *,int *))138 sip_hash_delete(sip_hash_t *sip_hash, void *digest, int hindex,
139     boolean_t (*del_func)(void *, void *, int *))
140 {
141 	sip_hash_t	*hash_entry;
142 	int		count;
143 	sip_hash_obj_t	*tmp;
144 	int		found;
145 
146 	hash_entry =  &sip_hash[hindex];
147 	(void) pthread_mutex_lock(&hash_entry->sip_hash_mutex);
148 	tmp = hash_entry->hash_head;
149 	for (count = 0; count < hash_entry->hash_count; count++) {
150 		if (del_func(tmp->sip_obj, digest, &found)) {
151 			if (tmp == hash_entry->hash_head) {
152 				if (tmp->next_obj != NULL) {
153 					hash_entry->hash_head = tmp->next_obj;
154 					tmp->next_obj->prev_obj = NULL;
155 				} else {
156 					assert(hash_entry->hash_tail ==
157 					    hash_entry->hash_head);
158 					hash_entry->hash_head = NULL;
159 					hash_entry->hash_tail = NULL;
160 				}
161 			} else {
162 				sip_hash_obj_t	*next = tmp->next_obj;
163 
164 				if (next != NULL) {
165 					tmp->prev_obj->next_obj = next;
166 					next->prev_obj = tmp->prev_obj;
167 				} else {
168 					assert(hash_entry->hash_tail == tmp);
169 					tmp->prev_obj->next_obj = NULL;
170 					hash_entry->hash_tail =
171 					    tmp->prev_obj;
172 				}
173 			}
174 			tmp->prev_obj = NULL;
175 			tmp->next_obj = NULL;
176 			free(tmp);
177 			hash_entry->hash_count--;
178 			(void) pthread_mutex_unlock(
179 			    &hash_entry->sip_hash_mutex);
180 			return;
181 		/*
182 		 * If we found the object, we are done
183 		 */
184 		} else if (found == 1) {
185 			(void) pthread_mutex_unlock(
186 			    &hash_entry->sip_hash_mutex);
187 			return;
188 		}
189 		tmp = tmp->next_obj;
190 	}
191 	(void) pthread_mutex_unlock(&hash_entry->sip_hash_mutex);
192 }
193