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 2009 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 */ 26 27 #include <stdio.h> 28 #include <stdlib.h> 29 #include <string.h> 30 #include "hashset.h" 31 #include "mountd.h" 32 #include <sys/sdt.h> 33 34 /* 35 * HASHSET is hash table managing pointers to a set of keys 36 * (set is a collection without duplicates). The public interface 37 * of the HASHSET is similar to the java.util.Set interface. 38 * Unlike the libc `hsearch' based hash table, this implementation 39 * does allow multiple instances of HASHSET within a single application, 40 * and the HASHSET_ITERATOR allows to iterate through the entire set 41 * using h_next(). 42 * 43 * HASHSET does not store actual keys but only pointers to keys. Hence the 44 * data remains intact when HASHSET grows (resizes itself). HASHSET accesses 45 * the actual key data only through the hash and equal functions given 46 * as arguments to h_create. 47 * 48 * Hash collisions are resolved with linked lists. 49 */ 50 51 typedef struct HashSetEntry { 52 uint_t e_hash; /* Hash value */ 53 const void *e_key; /* Pointer to a key */ 54 struct HashSetEntry *e_next; 55 } ENTRY; 56 57 struct HashSet { 58 ENTRY **h_table; /* Pointer to an array of ENTRY'ies */ 59 uint_t h_tableSize; /* Size of the array */ 60 uint_t h_count; /* Current count */ 61 uint_t h_threshold; /* loadFactor threshold */ 62 float h_loadFactor; /* Current loadFactor (h_count/h_tableSize( */ 63 uint_t (*h_hash) (const void *); 64 int (*h_equal) (const void *, const void *); 65 }; 66 67 struct HashSetIterator { 68 HASHSET i_h; 69 uint_t i_indx; 70 ENTRY *i_e; 71 uint_t i_coll; 72 }; 73 74 static void rehash(HASHSET h); 75 76 #define DEFAULT_INITIALCAPACITY 1 77 #define DEFAULT_LOADFACTOR 0.75 78 79 /* 80 * Create a HASHSET 81 * - HASHSET is a hash table of pointers to keys 82 * - duplicate keys are not allowed 83 * - the HASHSET is opaque and can be accessed only through the h_ functions 84 * - two keys k1 and k2 are considered equal if the result of equal(k1, k2) 85 * is non-zero 86 * - the function hash(key) is used to compute hash values for keys; if 87 * keys are "equal" the values returned by the hash function must be 88 * identical. 89 */ 90 91 HASHSET 92 h_create(uint_t (*hash) (const void *), 93 int (*equal) (const void *, const void *), 94 uint_t initialCapacity, 95 float loadFactor) 96 { 97 HASHSET h; 98 99 if (initialCapacity == 0) 100 initialCapacity = DEFAULT_INITIALCAPACITY; 101 102 if (loadFactor < 0.0) 103 loadFactor = DEFAULT_LOADFACTOR; 104 105 h = exmalloc(sizeof (*h)); 106 107 if (h == NULL) 108 return (NULL); 109 110 h->h_table = exmalloc(initialCapacity * sizeof (ENTRY *)); 111 112 (void) memset(h->h_table, 0, initialCapacity * sizeof (ENTRY *)); 113 114 if (h->h_table == NULL) { 115 free(h); 116 return (NULL); 117 } 118 h->h_tableSize = initialCapacity; 119 h->h_hash = hash; 120 h->h_equal = equal; 121 h->h_loadFactor = loadFactor; 122 h->h_threshold = (uint_t)(initialCapacity * loadFactor); 123 h->h_count = 0; 124 125 return (h); 126 } 127 128 /* 129 * Return a pointer to a matching key 130 */ 131 132 const void * 133 h_get(const HASHSET h, void *key) 134 { 135 uint_t hash = h->h_hash(key); 136 uint_t i = hash % h->h_tableSize; 137 ENTRY *e; 138 139 for (e = h->h_table[i]; e; e = e->e_next) 140 if (e->e_hash == hash && h->h_equal(e->e_key, key)) 141 return (e->e_key); 142 143 return (NULL); 144 } 145 146 /* 147 * Rehash (grow) HASHSET 148 * - called when loadFactor exceeds threshold 149 * - new size is 2*old_size+1 150 */ 151 152 static void 153 rehash(HASHSET h) 154 { 155 uint_t i = h->h_tableSize; 156 uint_t newtabSize = 2 * i + 1; 157 ENTRY **newtab = exmalloc(newtabSize * sizeof (ENTRY *)); 158 159 (void) memset(newtab, 0, newtabSize * sizeof (ENTRY *)); 160 161 while (i--) { 162 ENTRY *e, *next; 163 164 for (e = h->h_table[i]; e; e = next) { 165 uint_t k = e->e_hash % newtabSize; 166 167 next = (ENTRY *) e->e_next; 168 e->e_next = (ENTRY *) newtab[k]; 169 newtab[k] = e; 170 } 171 } 172 173 h->h_threshold = (uint_t)(newtabSize * h->h_loadFactor); 174 h->h_tableSize = newtabSize; 175 free(h->h_table); 176 h->h_table = newtab; 177 } 178 179 /* 180 * Store a key into a HASHSET 181 * - if there is already an "equal" key then the new key will not 182 * be stored and the function returns a pointer to an existing key 183 * - otherwise the function stores pointer to the new key and return NULL 184 */ 185 186 const void * 187 h_put(HASHSET h, const void *key) 188 { 189 uint_t hash = h->h_hash(key); 190 uint_t indx = hash % h->h_tableSize; 191 ENTRY *e; 192 193 for (e = h->h_table[indx]; e; e = e->e_next) 194 if (e->e_hash == hash && h->h_equal(e->e_key, key)) 195 return (key); 196 197 if (h->h_count >= h->h_threshold) { 198 rehash(h); 199 200 indx = hash % h->h_tableSize; 201 } 202 203 e = exmalloc(sizeof (ENTRY)); 204 e->e_hash = hash; 205 e->e_key = (void *) key; 206 e->e_next = h->h_table[indx]; 207 208 h->h_table[indx] = e; 209 h->h_count++; 210 211 DTRACE_PROBE2(mountd, hashset, h->h_count, h->h_loadFactor); 212 213 return (NULL); 214 } 215 216 /* 217 * Delete a key 218 * - if there is no "equal" key in the HASHSET the fuction returns NULL 219 * - otherwise the function returns a pointer to the deleted key 220 */ 221 222 const void * 223 h_delete(HASHSET h, const void *key) 224 { 225 uint_t hash = h->h_hash(key); 226 uint_t indx = hash % h->h_tableSize; 227 ENTRY *e, *prev; 228 229 for (e = h->h_table[indx], prev = NULL; e; prev = e, e = e->e_next) { 230 if (e->e_hash == hash && h->h_equal(e->e_key, key)) { 231 key = e->e_key; 232 if (prev) 233 prev->e_next = e->e_next; 234 else 235 h->h_table[indx] = e->e_next; 236 free(e); 237 return (key); 238 } 239 } 240 241 return (NULL); 242 } 243 244 /* 245 * Return an opaque HASHSET_ITERATOR (to be used in h_next()) 246 */ 247 248 HASHSET_ITERATOR 249 h_iterator(HASHSET h) 250 { 251 HASHSET_ITERATOR i = exmalloc(sizeof (*i)); 252 253 i->i_h = h; 254 i->i_indx = h->h_tableSize; 255 i->i_e = NULL; 256 i->i_coll = 0; 257 258 return (i); 259 } 260 261 /* 262 * Return a pointer to a next key 263 */ 264 265 const void * 266 h_next(HASHSET_ITERATOR i) 267 { 268 const void *key; 269 270 while (i->i_e == NULL) { 271 if (i->i_indx-- == 0) 272 return (NULL); 273 274 i->i_e = i->i_h->h_table[i->i_indx]; 275 } 276 277 key = i->i_e->e_key; 278 i->i_e = i->i_e->e_next; 279 280 if (i->i_e) 281 i->i_coll++; 282 283 return (key); 284 } 285