Home | History | Annotate | Download | only in libnisdb
      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