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. */
db_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. */
~db_index()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
reset()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
init(db_key_desc * k)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
get_next_hashsize(long unsigned oldsize)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
grow()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 *
lookup(item * index_value,long * how_many_found,db_table * table,bool_t checkTTL)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
remove(item * index_value,entryp recnum)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
add(item * index_value,entryp recnum)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
transfer_aux(XDR * x,pptr ip)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:
pickle_index(char * f,pickle_mode m)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. */
transfer(db_index * dp)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
dump(char * file)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 */
db_index(char * file)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
stats(long * tsize,long * tcount)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
print()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
move_xdr_db_index(db_index * orig)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