usr/src/lib/libnisdb/db_index.cc

   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 }