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 * db_index.cc 24 * 25 * Copyright 1988-2002 Sun Microsystems, Inc. All rights reserved. 26 * Use is subject to license terms. 27 */ 28 29 #pragma ident "%Z%%M% %I% %E% SMI" 30 31 #include <stdio.h> 32 #include <malloc.h> 33 #include "db_headers.h" 34 #include "db_index.h" 35 #include "db_pickle.h" 36 37 #include "nisdb_mt.h" 38 #include "nisdb_rw.h" 39 40 static int hashsizes[] = { /* hashtable sizes */ 41 11, 42 113, 43 337, 44 977, 45 2053, 46 4073, 47 8011, 48 16001, 49 0 50 }; 51 52 // prevents wrap around numbers from being passed 53 #define CALLOC_LIMIT 536870911 54 55 /* Constructor: creates empty index. */ 56 db_index::db_index() 57 { 58 tab = NULL; 59 table_size = 0; 60 count = 0; 61 case_insens = FALSE; 62 INITRW(index); 63 /* grow(); */ 64 } 65 66 67 /* Destructor: deletes index, including all associated db_index_entry. */ 68 db_index::~db_index() 69 { 70 WRITELOCKV(this, "w db_index::~db_index"); 71 reset(); 72 DESTROYRW(index); 73 } 74 75 /* Get rid of table and all associated entries, and reset counters */ 76 void 77 db_index::reset() 78 { 79 db_index_entry * curr, *n; 80 int i; 81 82 WRITELOCKV(this, "w db_index::reset"); 83 /* Add sanity test in case table was corrupted */ 84 if (tab != NULL) { 85 for (i = 0; i < table_size; i++) { // go through table 86 curr = tab[i]; 87 while (curr != NULL) { // go through bucket 88 n = curr->getnextentry(); 89 delete curr; 90 curr = n; 91 } 92 } 93 } 94 95 delete tab; // get rid of table itself 96 97 tab = NULL; 98 table_size = count = 0; 99 WRITEUNLOCKV(this, "wu db_index::reset"); 100 } 101 102 103 /* 104 * Initialize index according to the specification of the key descriptor 105 * Currently, only affects case_insens flag of index. 106 */ 107 void 108 db_index::init(db_key_desc * k) 109 { 110 WRITELOCKV(this, "w db_index::init"); 111 if ((k->key_flags)&DB_KEY_CASE) 112 case_insens = TRUE; 113 WRITEUNLOCKV(this, "wu db_index::init"); 114 } 115 116 /* Returns the next size to use for the hash table */ 117 static long unsigned 118 get_next_hashsize(long unsigned oldsize) 119 { 120 long unsigned newsize = 0, n; 121 if (oldsize == 0) 122 newsize = hashsizes[0]; 123 else { 124 for (n = 0; newsize = hashsizes[n++]; ) 125 if (oldsize == newsize) { 126 newsize = hashsizes[n]; /* get next size */ 127 break; 128 } 129 if (newsize == 0) 130 newsize = oldsize * 2 + 1; /* just double */ 131 } 132 return (newsize); 133 } 134 135 /* 136 * Grow the current hashtable upto the next size. 137 * The contents of the existing hashtable is copied to the new one and 138 * relocated according to its hashvalue relative to the new size. 139 * Old table is deleted after the relocation. 140 */ 141 void 142 db_index::grow() 143 { 144 long unsigned oldsize = table_size, i; 145 db_index_entry_p * oldtab = tab; 146 147 WRITELOCKV(this, "w db_index::grow"); 148 table_size = get_next_hashsize(table_size); 149 150 #ifdef DEBUG 151 if (debug > 3) 152 fprintf(ddt, "savehash GROWING to %d\n", table_size); 153 #endif 154 155 if (table_size > CALLOC_LIMIT) { 156 table_size = oldsize; 157 WRITEUNLOCKV(this, 158 "wu db_index::grow: table size exceeds calloc limit"); 159 FATAL("db_index::grow: table size exceeds calloc limit", 160 DB_MEMORY_LIMIT); 161 } 162 163 if ((tab = (db_index_entry_p*) 164 calloc((unsigned int) table_size, 165 sizeof (db_index_entry_p))) == NULL) { 166 tab = oldtab; // restore previous table info 167 table_size = oldsize; 168 WRITEUNLOCKV(this, 169 "wu db_index::grow: cannot allocate space"); 170 FATAL("db_index::grow: cannot allocate space", DB_MEMORY_LIMIT); 171 } 172 173 if (oldtab != NULL) { // must transfer contents of old to new 174 for (i = 0; i < oldsize; i++) { 175 oldtab[i]->relocate(tab, table_size); 176 } 177 delete oldtab; // delete old hashtable 178 } 179 WRITEUNLOCKV(this, "wu db_index::grow"); 180 } 181 182 /* 183 * Look up given index value in hashtable. 184 * Return pointer to db_index_entries that match the given value, linked 185 * via the 'next_result' pointer. Return in 'how_many_found' the size 186 * of this list. Return NULL if not found. 187 */ 188 db_index_entry * 189 db_index::lookup(item *index_value, long *how_many_found, 190 db_table *table, bool_t checkTTL) 191 { 192 register unsigned long hval; 193 unsigned long bucket; 194 db_index_entry *ret; 195 196 READLOCK(this, NULL, "r db_index::lookup"); 197 if (index_value == NULL || table_size == 0 || tab == NULL) { 198 READUNLOCK(this, NULL, "ru db_index::lookup"); 199 return (NULL); 200 } 201 hval = index_value->get_hashval(case_insens); 202 bucket = hval % table_size; 203 204 db_index_entry_p fst = tab[bucket ]; 205 206 if (fst != NULL) 207 ret = fst->lookup(case_insens, hval, 208 index_value, how_many_found); 209 else 210 ret = NULL; 211 212 if (ret != NULL && checkTTL && table != NULL) { 213 if (!table->cacheValid(ret->getlocation())) 214 ret = NULL; 215 } 216 217 READUNLOCK(this, ret, "ru db_index::lookup"); 218 return (ret); 219 } 220 221 /* 222 * Remove the entry with the given index value and location 'recnum'. 223 * If successful, return DB_SUCCESS; otherwise DB_NOTUNIQUE if index_value 224 * is null; DB_NOTFOUND if entry is not found. 225 * If successful, decrement count of number of entries in hash table. 226 */ 227 db_status 228 db_index::remove(item* index_value, entryp recnum) 229 { 230 register unsigned long hval; 231 unsigned long bucket; 232 register db_index_entry *fst; 233 db_status ret; 234 235 if (index_value == NULL) 236 return (DB_NOTUNIQUE); 237 WRITELOCK(this, DB_LOCK_ERROR, "w db_index::remove"); 238 if (table_size == 0 || tab == NULL) { 239 WRITEUNLOCK(this, DB_NOTFOUND, "wu db_index::remove"); 240 return (DB_NOTFOUND); 241 } 242 hval = index_value->get_hashval(case_insens); 243 244 bucket = hval % table_size; 245 246 fst = tab[bucket]; 247 if (fst == NULL) 248 ret = DB_NOTFOUND; 249 else if (fst->remove(&tab[bucket], case_insens, hval, index_value, 250 recnum)) { 251 --count; 252 ret = DB_SUCCESS; 253 } else 254 ret = DB_NOTFOUND; 255 WRITEUNLOCK(this, ret, "wu db_index::remove"); 256 return (ret); 257 } 258 259 /* 260 * Add a new index entry with the given index value and location 'recnum'. 261 * Return DB_NOTUNIQUE, if entry with identical index_value and recnum 262 * already exists. If entry is added, return DB_SUCCESS. 263 * Increment count of number of entries in index table and grow table 264 * if number of entries equals size of table. 265 * Note that a copy of index_value is made for new entry. 266 */ 267 db_status 268 db_index::add(item* index_value, entryp recnum) 269 { 270 register unsigned long hval; 271 272 if (index_value == NULL) 273 return (DB_NOTUNIQUE); 274 275 hval = index_value->get_hashval(case_insens); 276 277 WRITELOCK(this, DB_LOCK_ERROR, "w db_index::add"); 278 if (tab == NULL) grow(); 279 280 db_index_entry_p fst, newbucket; 281 unsigned long bucket; 282 bucket = hval %table_size; 283 fst = tab[bucket]; 284 if (fst == NULL) { /* Empty bucket */ 285 if ((newbucket = new db_index_entry(hval, index_value, 286 recnum, tab[bucket])) == NULL) { 287 WRITEUNLOCK(this, DB_MEMORY_LIMIT, 288 "wu db_index::add"); 289 FATAL3("db_index::add: cannot allocate space", 290 DB_MEMORY_LIMIT, DB_MEMORY_LIMIT); 291 } 292 tab[bucket] = newbucket; 293 } else if (fst->add(&tab[bucket], case_insens, 294 hval, index_value, recnum)) { 295 /* do nothing */ 296 } else { 297 WRITEUNLOCK(this, DB_NOTUNIQUE, "wu db_index::add"); 298 return (DB_NOTUNIQUE); 299 } 300 301 /* increase hash table size if number of entries equals table size */ 302 if (++count > table_size) 303 grow(); 304 305 WRITEUNLOCK(this, DB_SUCCESS, "wu db_index::add"); 306 return (DB_SUCCESS); 307 } 308 309 /* ************************* pickle_index ********************* */ 310 311 /* Does the actual writing to/from file specific for db_index structure. */ 312 static bool_t 313 transfer_aux(XDR* x, pptr ip) 314 { 315 return (xdr_db_index(x, (db_index*) ip)); 316 } 317 318 class pickle_index: public pickle_file { 319 public: 320 pickle_index(char *f, pickle_mode m) : pickle_file(f, m) {} 321 322 /* Transfers db_index structure pointed to by dp to/from file. */ 323 int transfer(db_index* dp) 324 { return (pickle_file::transfer((pptr) dp, &transfer_aux)); } 325 }; 326 327 /* Dumps this index to named file. */ 328 int 329 db_index::dump(char *file) 330 { 331 int ret; 332 pickle_index f(file, PICKLE_WRITE); 333 334 WRITELOCK(this, -1, "w db_index::dump"); 335 int status = f.transfer(this); 336 337 if (status == 1) 338 ret = -1; /* cannot open for write */ 339 else 340 ret = status; 341 WRITEUNLOCK(this, ret, "wu db_index::dump"); 342 } 343 344 /* 345 * Constructor: creates index by loading it from the specified file. 346 * If loading fails, creates empty index. 347 */ 348 db_index::db_index(char *file) 349 { 350 pickle_index f(file, PICKLE_READ); 351 tab = NULL; 352 table_size = count = 0; 353 354 /* load new hashbuf */ 355 if (f.transfer(this) < 0) { 356 /* Load failed; reset. */ 357 tab = NULL; 358 table_size = count = 0; 359 } 360 361 INITRW(index); 362 } 363 364 365 /* 366 * Return in 'tsize' the table_size, and 'tcount' the number of entries 367 * in the table. 368 */ 369 void 370 db_index::stats(long *tsize, long *tcount) 371 { 372 READLOCKV(this, "r db_index::stats"); 373 *tsize = table_size; 374 *tcount = count; 375 READUNLOCKV(this, "ru db_index::stats"); 376 } 377 378 /* Print all entries in the table. */ 379 void 380 db_index::print() 381 { 382 long i; 383 384 READLOCKV(this, "r db_index::print"); 385 /* Add sanity check in case table corrupted */ 386 if (tab != NULL) { 387 for (i = 0; i < table_size; i++) { 388 if (tab[i] != NULL) 389 tab[i]->print_all(); 390 } 391 } 392 READUNLOCKV(this, "ru db_index::print"); 393 } 394 395 /* 396 * Moves an index from an xdr index. Upon completion, original index's tab 397 * will be NULL. 398 */ 399 400 db_status 401 db_index::move_xdr_db_index(db_index *orig) 402 { 403 table_size = orig->table_size; 404 orig->table_size = 0; 405 count = orig->count; 406 orig->count = 0; 407 case_insens = orig->case_insens; 408 tab = orig->tab; 409 orig->tab = NULL; 410 411 return (DB_SUCCESS); 412 } 413