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