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
40static 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. */
56db_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. */
68db_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 */
76void
77db_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 */
107void
108db_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 */
117static long unsigned
118get_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 */
141void
142db_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 */
188db_index_entry *
189db_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 */
227db_status
228db_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 */
267db_status
268db_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. */
312static bool_t
313transfer_aux(XDR* x, pptr ip)
314{
315	return (xdr_db_index(x, (db_index*) ip));
316}
317
318class 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. */
328int
329db_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 */
348db_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 */
369void
370db_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. */
379void
380db_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
400db_status
401db_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