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