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 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 * 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 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 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