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