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