1/* Copyright (C) 1993, 1995, 1996, 1997 Free Software Foundation, Inc. 2 This file is part of the GNU C Library. 3 Contributed by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 1993. 4 5 The GNU C Library is free software; you can redistribute it and/or 6 modify it under the terms of the GNU Lesser General Public License as 7 published by the Free Software Foundation; either version 2.1 of the 8 License, or (at your option) any later version. 9 10 The GNU C Library is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13 Lesser General Public License for more details. 14 15 You should have received a copy of the GNU Lesser General Public 16 License along with the GNU C Library; see the file COPYING.LIB. If not, 17 write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, 18 Boston, MA 02111-1307, USA. */ 19 20#include <errno.h> 21#include <malloc.h> 22#include <string.h> 23 24#define __USE_GNU 25#ifndef __set_errno 26#define __set_errno(e) errno = (e) 27#endif 28#include <search.h> 29 30/* [Aho,Sethi,Ullman] Compilers: Principles, Techniques and Tools, 1986 31 [Knuth] The Art of Computer Programming, part 3 (6.4) */ 32 33 34/* The reentrant version has no static variables to maintain the state. 35 Instead the interface of all functions is extended to take an argument 36 which describes the current status. */ 37typedef struct _ENTRY 38{ 39 unsigned int used; 40 ENTRY entry; 41} 42_ENTRY; 43 44 45/* For the used double hash method the table size has to be a prime. To 46 correct the user given table size we need a prime test. This trivial 47 algorithm is adequate because 48 a) the code is (most probably) called a few times per program run and 49 b) the number is small because the table must fit in the core */ 50static int 51isprime (unsigned int number) 52{ 53 /* no even number will be passed */ 54 unsigned int div = 3; 55 56 while (div * div < number && number % div != 0) 57 div += 2; 58 59 return number % div != 0; 60} 61 62 63/* Before using the hash table we must allocate memory for it. 64 Test for an existing table are done. We allocate one element 65 more as the found prime number says. This is done for more effective 66 indexing as explained in the comment for the hsearch function. 67 The contents of the table is zeroed, especially the field used 68 becomes zero. */ 69int 70hcreate_r (nel, htab) 71 size_t nel; 72 struct hsearch_data *htab; 73{ 74 /* Test for correct arguments. */ 75 if (htab == NULL) 76 { 77 __set_errno (EINVAL); 78 return 0; 79 } 80 81 /* There is still another table active. Return with error. */ 82 if (htab->table != NULL) 83 return 0; 84 85 /* Change nel to the first prime number not smaller as nel. */ 86 nel |= 1; /* make odd */ 87 while (!isprime (nel)) 88 nel += 2; 89 90 htab->size = nel; 91 htab->filled = 0; 92 93 /* allocate memory and zero out */ 94 htab->table = (_ENTRY *) calloc (htab->size + 1, sizeof (_ENTRY)); 95 if (htab->table == NULL) 96 return 0; 97 98 /* everything went alright */ 99 return 1; 100} 101 102 103/* After using the hash table it has to be destroyed. The used memory can 104 be freed and the local static variable can be marked as not used. */ 105void 106hdestroy_r (htab) 107 struct hsearch_data *htab; 108{ 109 /* Test for correct arguments. */ 110 if (htab == NULL) 111 { 112 __set_errno (EINVAL); 113 return; 114 } 115 116 if (htab->table != NULL) 117 /* free used memory */ 118 free (htab->table); 119 120 /* the sign for an existing table is an value != NULL in htable */ 121 htab->table = NULL; 122} 123 124 125/* This is the search function. It uses double hashing with open addressing. 126 The argument item.key has to be a pointer to an zero terminated, most 127 probably strings of chars. The function for generating a number of the 128 strings is simple but fast. It can be replaced by a more complex function 129 like ajw (see [Aho,Sethi,Ullman]) if the needs are shown. 130 131 We use an trick to speed up the lookup. The table is created by hcreate 132 with one more element available. This enables us to use the index zero 133 special. This index will never be used because we store the first hash 134 index in the field used where zero means not used. Every other value 135 means used. The used field can be used as a first fast comparison for 136 equality of the stored and the parameter value. This helps to prevent 137 unnecessary expensive calls of strcmp. */ 138int 139hsearch_r (item, action, retval, htab) 140 ENTRY item; 141 ACTION action; 142 ENTRY **retval; 143 struct hsearch_data *htab; 144{ 145 unsigned int hval; 146 unsigned int count; 147 unsigned int len = strlen (item.key); 148 unsigned int idx; 149 150 /* Compute an value for the given string. Perhaps use a better method. */ 151 hval = len; 152 count = len; 153 while (count-- > 0) 154 { 155 hval <<= 4; 156 hval += item.key[count]; 157 } 158 159 /* First hash function: simply take the modulo but prevent zero. */ 160 hval %= htab->size; 161 if (hval == 0) 162 ++hval; 163 164 /* The first index tried. */ 165 idx = hval; 166 167 if (htab->table[idx].used) 168 { 169 /* Further action might be required according to the action value. */ 170 unsigned hval2; 171 172 if (htab->table[idx].used == hval 173 && strcmp (item.key, htab->table[idx].entry.key) == 0) 174 { 175 if (action == ENTER) 176 htab->table[idx].entry.data = item.data; 177 178 *retval = &htab->table[idx].entry; 179 return 1; 180 } 181 182 /* Second hash function, as suggested in [Knuth] */ 183 hval2 = 1 + hval % (htab->size - 2); 184 185 do 186 { 187 /* Because SIZE is prime this guarantees to step through all 188 available indexes. */ 189 if (idx <= hval2) 190 idx = htab->size + idx - hval2; 191 else 192 idx -= hval2; 193 194 /* If we visited all entries leave the loop unsuccessfully. */ 195 if (idx == hval) 196 break; 197 198 /* If entry is found use it. */ 199 if (htab->table[idx].used == hval 200 && strcmp (item.key, htab->table[idx].entry.key) == 0) 201 { 202 if (action == ENTER) 203 htab->table[idx].entry.data = item.data; 204 205 *retval = &htab->table[idx].entry; 206 return 1; 207 } 208 } 209 while (htab->table[idx].used); 210 } 211 212 /* An empty bucket has been found. */ 213 if (action == ENTER) 214 { 215 /* If table is full and another entry should be entered return 216 with error. */ 217 if (action == ENTER && htab->filled == htab->size) 218 { 219 __set_errno (ENOMEM); 220 *retval = NULL; 221 return 0; 222 } 223 224 htab->table[idx].used = hval; 225 htab->table[idx].entry = item; 226 227 ++htab->filled; 228 229 *retval = &htab->table[idx].entry; 230 return 1; 231 } 232 233 __set_errno (ESRCH); 234 *retval = NULL; 235 return 0; 236} 237