]> git.saurik.com Git - apple/libc.git/blob - db/hash/hash.c
projects / apple / libc.git / blob
? search:


8ba3c8f8eeec9a3375b0c4962773a34ec8909662
[apple/libc.git] / db / hash / hash.c
1 /*
2 * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_LICENSE_HEADER_START@
5 *
6 * Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved.
7 *
8 * This file contains Original Code and/or Modifications of Original Code
9 * as defined in and that are subject to the Apple Public Source License
10 * Version 2.0 (the 'License'). You may not use this file except in
11 * compliance with the License. Please obtain a copy of the License at
12 * http://www.opensource.apple.com/apsl/ and read it before using this
13 * file.
14 *
15 * The Original Code and all software distributed under the License are
16 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
17 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
18 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
20 * Please see the License for the specific language governing rights and
21 * limitations under the License.
22 *
23 * @APPLE_LICENSE_HEADER_END@
24 */
25 /*
26 * Copyright (c) 1990, 1993
27 * The Regents of the University of California. All rights reserved.
28 *
29 * This code is derived from software contributed to Berkeley by
30 * Margo Seltzer.
31 *
32 * Redistribution and use in source and binary forms, with or without
33 * modification, are permitted provided that the following conditions
34 * are met:
35 * 1. Redistributions of source code must retain the above copyright
36 * notice, this list of conditions and the following disclaimer.
37 * 2. Redistributions in binary form must reproduce the above copyright
38 * notice, this list of conditions and the following disclaimer in the
39 * documentation and/or other materials provided with the distribution.
40 * 3. All advertising materials mentioning features or use of this software
41 * must display the following acknowledgement:
42 * This product includes software developed by the University of
43 * California, Berkeley and its contributors.
44 * 4. Neither the name of the University nor the names of its contributors
45 * may be used to endorse or promote products derived from this software
46 * without specific prior written permission.
47 *
48 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
49 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
50 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
51 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
52 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
53 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
54 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
55 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
56 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
57 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
58 * SUCH DAMAGE.
59 */
60
61
62 #include <sys/param.h>
63 #include <sys/stat.h>
64
65 #include <errno.h>
66 #include <fcntl.h>
67 #include <stdio.h>
68 #include <stdlib.h>
69 #include <string.h>
70 #include <unistd.h>
71 #ifdef DEBUG
72 #include <assert.h>
73 #endif
74
75 #include <db.h>
76 #include "hash.h"
77 #include "page.h"
78 #include "extern.h"
79
80 static int alloc_segs __P((HTAB *, int));
81 static int flush_meta __P((HTAB *));
82 static int hash_access __P((HTAB *, ACTION, DBT *, DBT *));
83 static int hash_close __P((DB *));
84 static int hash_delete __P((const DB *, const DBT *, u_int));
85 static int hash_fd __P((const DB *));
86 static int hash_get __P((const DB *, const DBT *, DBT *, u_int));
87 static int hash_put __P((const DB *, DBT *, const DBT *, u_int));
88 static void *hash_realloc __P((SEGMENT **, int, int));
89 static int hash_seq __P((const DB *, DBT *, DBT *, u_int));
90 static int hash_sync __P((const DB *, u_int));
91 static int hdestroy __P((HTAB *));
92 static HTAB *init_hash __P((HTAB *, const char *, HASHINFO *));
93 static int init_htab __P((HTAB *, int));
94 #if BYTE_ORDER == LITTLE_ENDIAN
95 static void swap_header __P((HTAB *));
96 static void swap_header_copy __P((HASHHDR *, HASHHDR *));
97 #endif
98
99 /* Fast arithmetic, relying on powers of 2, */
100 #define MOD(x, y) ((x) & ((y) - 1))
101
102 #define RETURN_ERROR(ERR, LOC) { save_errno = ERR; goto LOC; }
103
104 /* Return values */
105 #define SUCCESS (0)
106 #define ERROR (-1)
107 #define ABNORMAL (1)
108
109 #ifdef HASH_STATISTICS
110 long hash_accesses, hash_collisions, hash_expansions, hash_overflows;
111 #endif
112
113 /************************** INTERFACE ROUTINES ***************************/
114 /* OPEN/CLOSE */
115
116 extern DB *
117 __hash_open(file, flags, mode, info, dflags)
118 const char *file;
119 int flags, mode, dflags;
120 const HASHINFO *info; /* Special directives for create */
121 {
122 HTAB *hashp;
123 struct stat statbuf;
124 DB *dbp;
125 int bpages, hdrsize, new_table, nsegs, save_errno;
126
127 if ((flags & O_ACCMODE) == O_WRONLY) {
128 errno = EINVAL;
129 return (NULL);
130 }
131
132 if (!(hashp = (HTAB *)calloc(1, sizeof(HTAB))))
133 return (NULL);
134 hashp->fp = -1;
135
136 /*
137 * Even if user wants write only, we need to be able to read
138 * the actual file, so we need to open it read/write. But, the
139 * field in the hashp structure needs to be accurate so that
140 * we can check accesses.
141 */
142 hashp->flags = flags;
143
144 new_table = 0;
145 if (!file || (flags & O_TRUNC) ||
146 (stat(file, &statbuf) && (errno == ENOENT))) {
147 if (errno == ENOENT)
148 errno = 0; /* Just in case someone looks at errno */
149 new_table = 1;
150 }
151 if (file) {
152 if ((hashp->fp = open(file, flags, mode)) == -1)
153 RETURN_ERROR(errno, error0);
154 (void)fcntl(hashp->fp, F_SETFD, 1);
155 }
156 if (new_table) {
157 if (!(hashp = init_hash(hashp, file, (HASHINFO *)info)))
158 RETURN_ERROR(errno, error1);
159 } else {
160 /* Table already exists */
161 if (info && info->hash)
162 hashp->hash = info->hash;
163 else
164 hashp->hash = __default_hash;
165
166 hdrsize = read(hashp->fp, &hashp->hdr, sizeof(HASHHDR));
167 #if BYTE_ORDER == LITTLE_ENDIAN
168 swap_header(hashp);
169 #endif
170 if (hdrsize == -1)
171 RETURN_ERROR(errno, error1);
172 if (hdrsize != sizeof(HASHHDR))
173 RETURN_ERROR(EFTYPE, error1);
174 /* Verify file type, versions and hash function */
175 if (hashp->MAGIC != HASHMAGIC)
176 RETURN_ERROR(EFTYPE, error1);
177 #define OLDHASHVERSION 1
178 if (hashp->VERSION != HASHVERSION &&
179 hashp->VERSION != OLDHASHVERSION)
180 RETURN_ERROR(EFTYPE, error1);
181 if (hashp->hash(CHARKEY, sizeof(CHARKEY)) != hashp->H_CHARKEY)
182 RETURN_ERROR(EFTYPE, error1);
183 /*
184 * Figure out how many segments we need. Max_Bucket is the
185 * maximum bucket number, so the number of buckets is
186 * max_bucket + 1.
187 */
188 nsegs = (hashp->MAX_BUCKET + 1 + hashp->SGSIZE - 1) /
189 hashp->SGSIZE;
190 hashp->nsegs = 0;
191 if (alloc_segs(hashp, nsegs))
192 /*
193 * If alloc_segs fails, table will have been destroyed
194 * and errno will have been set.
195 */
196 return (NULL);
197 /* Read in bitmaps */
198 bpages = (hashp->SPARES[hashp->OVFL_POINT] +
199 (hashp->BSIZE << BYTE_SHIFT) - 1) >>
200 (hashp->BSHIFT + BYTE_SHIFT);
201
202 hashp->nmaps = bpages;
203 (void)memset(&hashp->mapp[0], 0, bpages * sizeof(u_long *));
204 }
205
206 /* Initialize Buffer Manager */
207 if (info && info->cachesize)
208 __buf_init(hashp, info->cachesize);
209 else
210 __buf_init(hashp, DEF_BUFSIZE);
211
212 hashp->new_file = new_table;
213 hashp->save_file = file && (hashp->flags & O_RDWR);
214 hashp->cbucket = -1;
215 if (!(dbp = (DB *)malloc(sizeof(DB)))) {
216 save_errno = errno;
217 hdestroy(hashp);
218 errno = save_errno;
219 return (NULL);
220 }
221 dbp->internal = hashp;
222 dbp->close = hash_close;
223 dbp->del = hash_delete;
224 dbp->fd = hash_fd;
225 dbp->get = hash_get;
226 dbp->put = hash_put;
227 dbp->seq = hash_seq;
228 dbp->sync = hash_sync;
229 dbp->type = DB_HASH;
230
231 #ifdef DEBUG
232 (void)fprintf(stderr,
233 "%s\n%s%x\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%x\n%s%x\n%s%d\n%s%d\n",
234 "init_htab:",
235 "TABLE POINTER ", hashp,
236 "BUCKET SIZE ", hashp->BSIZE,
237 "BUCKET SHIFT ", hashp->BSHIFT,
238 "DIRECTORY SIZE ", hashp->DSIZE,
239 "SEGMENT SIZE ", hashp->SGSIZE,
240 "SEGMENT SHIFT ", hashp->SSHIFT,
241 "FILL FACTOR ", hashp->FFACTOR,
242 "MAX BUCKET ", hashp->MAX_BUCKET,
243 "OVFL POINT ", hashp->OVFL_POINT,
244 "LAST FREED ", hashp->LAST_FREED,
245 "HIGH MASK ", hashp->HIGH_MASK,
246 "LOW MASK ", hashp->LOW_MASK,
247 "NSEGS ", hashp->nsegs,
248 "NKEYS ", hashp->NKEYS);
249 #endif
250 #ifdef HASH_STATISTICS
251 hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0;
252 #endif
253 return (dbp);
254
255 error1:
256 if (hashp != NULL)
257 (void)close(hashp->fp);
258
259 error0:
260 free(hashp);
261 errno = save_errno;
262 return (NULL);
263 }
264
265 static int
266 hash_close(dbp)
267 DB *dbp;
268 {
269 HTAB *hashp;
270 int retval;
271
272 if (!dbp)
273 return (ERROR);
274
275 hashp = (HTAB *)dbp->internal;
276 retval = hdestroy(hashp);
277 free(dbp);
278 return (retval);
279 }
280
281 static int
282 hash_fd(dbp)
283 const DB *dbp;
284 {
285 HTAB *hashp;
286
287 if (!dbp)
288 return (ERROR);
289
290 hashp = (HTAB *)dbp->internal;
291 if (hashp->fp == -1) {
292 errno = ENOENT;
293 return (-1);
294 }
295 return (hashp->fp);
296 }
297
298 /************************** LOCAL CREATION ROUTINES **********************/
299 static HTAB *
300 init_hash(hashp, file, info)
301 HTAB *hashp;
302 const char *file;
303 HASHINFO *info;
304 {
305 struct stat statbuf;
306 int nelem;
307
308 nelem = 1;
309 hashp->NKEYS = 0;
310 hashp->LORDER = BYTE_ORDER;
311 hashp->BSIZE = DEF_BUCKET_SIZE;
312 hashp->BSHIFT = DEF_BUCKET_SHIFT;
313 hashp->SGSIZE = DEF_SEGSIZE;
314 hashp->SSHIFT = DEF_SEGSIZE_SHIFT;
315 hashp->DSIZE = DEF_DIRSIZE;
316 hashp->FFACTOR = DEF_FFACTOR;
317 hashp->hash = __default_hash;
318 memset(hashp->SPARES, 0, sizeof(hashp->SPARES));
319 memset(hashp->BITMAPS, 0, sizeof (hashp->BITMAPS));
320
321 /* Fix bucket size to be optimal for file system */
322 if (file != NULL) {
323 if (stat(file, &statbuf))
324 return (NULL);
325 hashp->BSIZE = statbuf.st_blksize;
326 hashp->BSHIFT = __log2(hashp->BSIZE);
327 }
328
329 if (info) {
330 if (info->bsize) {
331 /* Round pagesize up to power of 2 */
332 hashp->BSHIFT = __log2(info->bsize);
333 hashp->BSIZE = 1 << hashp->BSHIFT;
334 if (hashp->BSIZE > MAX_BSIZE) {
335 errno = EINVAL;
336 return (NULL);
337 }
338 }
339 if (info->ffactor)
340 hashp->FFACTOR = info->ffactor;
341 if (info->hash)
342 hashp->hash = info->hash;
343 if (info->nelem)
344 nelem = info->nelem;
345 if (info->lorder) {
346 if (info->lorder != BIG_ENDIAN &&
347 info->lorder != LITTLE_ENDIAN) {
348 errno = EINVAL;
349 return (NULL);
350 }
351 hashp->LORDER = info->lorder;
352 }
353 }
354 /* init_htab should destroy the table and set errno if it fails */
355 if (init_htab(hashp, nelem))
356 return (NULL);
357 else
358 return (hashp);
359 }
360 /*
361 * This calls alloc_segs which may run out of memory. Alloc_segs will destroy
362 * the table and set errno, so we just pass the error information along.
363 *
364 * Returns 0 on No Error
365 */
366 static int
367 init_htab(hashp, nelem)
368 HTAB *hashp;
369 int nelem;
370 {
371 register int nbuckets, nsegs;
372 int l2;
373
374 /*
375 * Divide number of elements by the fill factor and determine a
376 * desired number of buckets. Allocate space for the next greater
377 * power of two number of buckets.
378 */
379 nelem = (nelem - 1) / hashp->FFACTOR + 1;
380
381 l2 = __log2(MAX(nelem, 2));
382 nbuckets = 1 << l2;
383
384 hashp->SPARES[l2] = l2 + 1;
385 hashp->SPARES[l2 + 1] = l2 + 1;
386 hashp->OVFL_POINT = l2;
387 hashp->LAST_FREED = 2;
388
389 /* First bitmap page is at: splitpoint l2 page offset 1 */
390 if (__init_bitmap(hashp, OADDR_OF(l2, 1), l2 + 1, 0))
391 return (-1);
392
393 hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1;
394 hashp->HIGH_MASK = (nbuckets << 1) - 1;
395 hashp->HDRPAGES = ((MAX(sizeof(HASHHDR), MINHDRSIZE) - 1) >>
396 hashp->BSHIFT) + 1;
397
398 nsegs = (nbuckets - 1) / hashp->SGSIZE + 1;
399 nsegs = 1 << __log2(nsegs);
400
401 if (nsegs > hashp->DSIZE)
402 hashp->DSIZE = nsegs;
403 return (alloc_segs(hashp, nsegs));
404 }
405
406 /********************** DESTROY/CLOSE ROUTINES ************************/
407
408 /*
409 * Flushes any changes to the file if necessary and destroys the hashp
410 * structure, freeing all allocated space.
411 */
412 static int
413 hdestroy(hashp)
414 HTAB *hashp;
415 {
416 int i, save_errno;
417
418 save_errno = 0;
419
420 #ifdef HASH_STATISTICS
421 (void)fprintf(stderr, "hdestroy: accesses %ld collisions %ld\n",
422 hash_accesses, hash_collisions);
423 (void)fprintf(stderr, "hdestroy: expansions %ld\n",
424 hash_expansions);
425 (void)fprintf(stderr, "hdestroy: overflows %ld\n",
426 hash_overflows);
427 (void)fprintf(stderr, "keys %ld maxp %d segmentcount %d\n",
428 hashp->NKEYS, hashp->MAX_BUCKET, hashp->nsegs);
429
430 for (i = 0; i < NCACHED; i++)
431 (void)fprintf(stderr,
432 "spares[%d] = %d\n", i, hashp->SPARES[i]);
433 #endif
434 /*
435 * Call on buffer manager to free buffers, and if required,
436 * write them to disk.
437 */
438 if (__buf_free(hashp, 1, hashp->save_file))
439 save_errno = errno;
440 if (hashp->dir) {
441 free(*hashp->dir); /* Free initial segments */
442 /* Free extra segments */
443 while (hashp->exsegs--)
444 free(hashp->dir[--hashp->nsegs]);
445 free(hashp->dir);
446 }
447 if (flush_meta(hashp) && !save_errno)
448 save_errno = errno;
449 /* Free Bigmaps */
450 for (i = 0; i < hashp->nmaps; i++)
451 if (hashp->mapp[i])
452 free(hashp->mapp[i]);
453
454 if (hashp->fp != -1)
455 (void)close(hashp->fp);
456
457 free(hashp);
458
459 if (save_errno) {
460 errno = save_errno;
461 return (ERROR);
462 }
463 return (SUCCESS);
464 }
465 /*
466 * Write modified pages to disk
467 *
468 * Returns:
469 * 0 == OK
470 * -1 ERROR
471 */
472 static int
473 hash_sync(dbp, flags)
474 const DB *dbp;
475 u_int flags;
476 {
477 HTAB *hashp;
478
479 if (flags != 0) {
480 errno = EINVAL;
481 return (ERROR);
482 }
483
484 if (!dbp)
485 return (ERROR);
486
487 hashp = (HTAB *)dbp->internal;
488 if (!hashp->save_file)
489 return (0);
490 if (__buf_free(hashp, 0, 1) || flush_meta(hashp))
491 return (ERROR);
492 hashp->new_file = 0;
493 return (0);
494 }
495
496 /*
497 * Returns:
498 * 0 == OK
499 * -1 indicates that errno should be set
500 */
501 static int
502 flush_meta(hashp)
503 HTAB *hashp;
504 {
505 HASHHDR *whdrp;
506 #if BYTE_ORDER == LITTLE_ENDIAN
507 HASHHDR whdr;
508 #endif
509 int fp, i, wsize;
510
511 if (!hashp->save_file)
512 return (0);
513 hashp->MAGIC = HASHMAGIC;
514 hashp->VERSION = HASHVERSION;
515 hashp->H_CHARKEY = hashp->hash(CHARKEY, sizeof(CHARKEY));
516
517 fp = hashp->fp;
518 whdrp = &hashp->hdr;
519 #if BYTE_ORDER == LITTLE_ENDIAN
520 whdrp = &whdr;
521 swap_header_copy(&hashp->hdr, whdrp);
522 #endif
523 if ((lseek(fp, (off_t)0, SEEK_SET) == -1) ||
524 ((wsize = write(fp, whdrp, sizeof(HASHHDR))) == -1))
525 return (-1);
526 else
527 if (wsize != sizeof(HASHHDR)) {
528 errno = EFTYPE;
529 hashp->error = errno;
530 return (-1);
531 }
532 for (i = 0; i < NCACHED; i++)
533 if (hashp->mapp[i])
534 if (__put_page(hashp, (char *)hashp->mapp[i],
535 hashp->BITMAPS[i], 0, 1))
536 return (-1);
537 return (0);
538 }
539
540 /*******************************SEARCH ROUTINES *****************************/
541 /*
542 * All the access routines return
543 *
544 * Returns:
545 * 0 on SUCCESS
546 * 1 to indicate an external ERROR (i.e. key not found, etc)
547 * -1 to indicate an internal ERROR (i.e. out of memory, etc)
548 */
549 static int
550 hash_get(dbp, key, data, flag)
551 const DB *dbp;
552 const DBT *key;
553 DBT *data;
554 u_int flag;
555 {
556 HTAB *hashp;
557
558 hashp = (HTAB *)dbp->internal;
559 if (flag) {
560 hashp->error = errno = EINVAL;
561 return (ERROR);
562 }
563 return (hash_access(hashp, HASH_GET, (DBT *)key, data));
564 }
565
566 static int
567 hash_put(dbp, key, data, flag)
568 const DB *dbp;
569 DBT *key;
570 const DBT *data;
571 u_int flag;
572 {
573 HTAB *hashp;
574
575 hashp = (HTAB *)dbp->internal;
576 if (flag && flag != R_NOOVERWRITE) {
577 hashp->error = errno = EINVAL;
578 return (ERROR);
579 }
580 if ((hashp->flags & O_ACCMODE) == O_RDONLY) {
581 hashp->error = errno = EPERM;
582 return (ERROR);
583 }
584 return (hash_access(hashp, flag == R_NOOVERWRITE ?
585 HASH_PUTNEW : HASH_PUT, (DBT *)key, (DBT *)data));
586 }
587
588 static int
589 hash_delete(dbp, key, flag)
590 const DB *dbp;
591 const DBT *key;
592 u_int flag; /* Ignored */
593 {
594 HTAB *hashp;
595
596 hashp = (HTAB *)dbp->internal;
597 if (flag && flag != R_CURSOR) {
598 hashp->error = errno = EINVAL;
599 return (ERROR);
600 }
601 if ((hashp->flags & O_ACCMODE) == O_RDONLY) {
602 hashp->error = errno = EPERM;
603 return (ERROR);
604 }
605 return (hash_access(hashp, HASH_DELETE, (DBT *)key, NULL));
606 }
607
608 /*
609 * Assume that hashp has been set in wrapper routine.
610 */
611 static int
612 hash_access(hashp, action, key, val)
613 HTAB *hashp;
614 ACTION action;
615 DBT *key, *val;
616 {
617 register BUFHEAD *rbufp;
618 BUFHEAD *bufp, *save_bufp;
619 register u_short *bp;
620 register int n, ndx, off, size;
621 register char *kp;
622 u_short pageno;
623
624 #ifdef HASH_STATISTICS
625 hash_accesses++;
626 #endif
627
628 off = hashp->BSIZE;
629 size = key->size;
630 kp = (char *)key->data;
631 rbufp = __get_buf(hashp, __call_hash(hashp, kp, size), NULL, 0);
632 if (!rbufp)
633 return (ERROR);
634 save_bufp = rbufp;
635
636 /* Pin the bucket chain */
637 rbufp->flags |= BUF_PIN;
638 for (bp = (u_short *)rbufp->page, n = *bp++, ndx = 1; ndx < n;)
639 if (bp[1] >= REAL_KEY) {
640 /* Real key/data pair */
641 if (size == off - *bp &&
642 memcmp(kp, rbufp->page + *bp, size) == 0)
643 goto found;
644 off = bp[1];
645 #ifdef HASH_STATISTICS
646 hash_collisions++;
647 #endif
648 bp += 2;
649 ndx += 2;
650 } else if (bp[1] == OVFLPAGE) {
651 rbufp = __get_buf(hashp, *bp, rbufp, 0);
652 if (!rbufp) {
653 save_bufp->flags &= ~BUF_PIN;
654 return (ERROR);
655 }
656 /* FOR LOOP INIT */
657 bp = (u_short *)rbufp->page;
658 n = *bp++;
659 ndx = 1;
660 off = hashp->BSIZE;
661 } else if (bp[1] < REAL_KEY) {
662 if ((ndx =
663 __find_bigpair(hashp, rbufp, ndx, kp, size)) > 0)
664 goto found;
665 if (ndx == -2) {
666 bufp = rbufp;
667 if (!(pageno =
668 __find_last_page(hashp, &bufp))) {
669 ndx = 0;
670 rbufp = bufp;
671 break; /* FOR */
672 }
673 rbufp = __get_buf(hashp, pageno, bufp, 0);
674 if (!rbufp) {
675 save_bufp->flags &= ~BUF_PIN;
676 return (ERROR);
677 }
678 /* FOR LOOP INIT */
679 bp = (u_short *)rbufp->page;
680 n = *bp++;
681 ndx = 1;
682 off = hashp->BSIZE;
683 } else {
684 save_bufp->flags &= ~BUF_PIN;
685 return (ERROR);
686 }
687 }
688
689 /* Not found */
690 switch (action) {
691 case HASH_PUT:
692 case HASH_PUTNEW:
693 if (__addel(hashp, rbufp, key, val)) {
694 save_bufp->flags &= ~BUF_PIN;
695 return (ERROR);
696 } else {
697 save_bufp->flags &= ~BUF_PIN;
698 return (SUCCESS);
699 }
700 case HASH_GET:
701 case HASH_DELETE:
702 default:
703 save_bufp->flags &= ~BUF_PIN;
704 return (ABNORMAL);
705 }
706
707 found:
708 switch (action) {
709 case HASH_PUTNEW:
710 save_bufp->flags &= ~BUF_PIN;
711 return (ABNORMAL);
712 case HASH_GET:
713 bp = (u_short *)rbufp->page;
714 if (bp[ndx + 1] < REAL_KEY) {
715 if (__big_return(hashp, rbufp, ndx, val, 0))
716 return (ERROR);
717 } else {
718 val->data = (u_char *)rbufp->page + (int)bp[ndx + 1];
719 val->size = bp[ndx] - bp[ndx + 1];
720 }
721 break;
722 case HASH_PUT:
723 if ((__delpair(hashp, rbufp, ndx)) ||
724 (__addel(hashp, rbufp, key, val))) {
725 save_bufp->flags &= ~BUF_PIN;
726 return (ERROR);
727 }
728 break;
729 case HASH_DELETE:
730 if (__delpair(hashp, rbufp, ndx))
731 return (ERROR);
732 break;
733 default:
734 abort();
735 }
736 save_bufp->flags &= ~BUF_PIN;
737 return (SUCCESS);
738 }
739
740 static int
741 hash_seq(dbp, key, data, flag)
742 const DB *dbp;
743 DBT *key, *data;
744 u_int flag;
745 {
746 register u_int bucket;
747 register BUFHEAD *bufp;
748 HTAB *hashp;
749 u_short *bp, ndx;
750
751 hashp = (HTAB *)dbp->internal;
752 if (flag && flag != R_FIRST && flag != R_NEXT) {
753 hashp->error = errno = EINVAL;
754 return (ERROR);
755 }
756 #ifdef HASH_STATISTICS
757 hash_accesses++;
758 #endif
759 if ((hashp->cbucket < 0) || (flag == R_FIRST)) {
760 hashp->cbucket = 0;
761 hashp->cndx = 1;
762 hashp->cpage = NULL;
763 }
764
765 for (bp = NULL; !bp || !bp[0]; ) {
766 if (!(bufp = hashp->cpage)) {
767 for (bucket = hashp->cbucket;
768 bucket <= hashp->MAX_BUCKET;
769 bucket++, hashp->cndx = 1) {
770 bufp = __get_buf(hashp, bucket, NULL, 0);
771 if (!bufp)
772 return (ERROR);
773 hashp->cpage = bufp;
774 bp = (u_short *)bufp->page;
775 if (bp[0])
776 break;
777 }
778 hashp->cbucket = bucket;
779 if (hashp->cbucket > hashp->MAX_BUCKET) {
780 hashp->cbucket = -1;
781 return (ABNORMAL);
782 }
783 } else
784 bp = (u_short *)hashp->cpage->page;
785
786 #ifdef DEBUG
787 assert(bp);
788 assert(bufp);
789 #endif
790 while (bp[hashp->cndx + 1] == OVFLPAGE) {
791 bufp = hashp->cpage =
792 __get_buf(hashp, bp[hashp->cndx], bufp, 0);
793 if (!bufp)
794 return (ERROR);
795 bp = (u_short *)(bufp->page);
796 hashp->cndx = 1;
797 }
798 if (!bp[0]) {
799 hashp->cpage = NULL;
800 ++hashp->cbucket;
801 }
802 }
803 ndx = hashp->cndx;
804 if (bp[ndx + 1] < REAL_KEY) {
805 if (__big_keydata(hashp, bufp, key, data, 1))
806 return (ERROR);
807 } else {
808 key->data = (u_char *)hashp->cpage->page + bp[ndx];
809 key->size = (ndx > 1 ? bp[ndx - 1] : hashp->BSIZE) - bp[ndx];
810 data->data = (u_char *)hashp->cpage->page + bp[ndx + 1];
811 data->size = bp[ndx] - bp[ndx + 1];
812 ndx += 2;
813 if (ndx > bp[0]) {
814 hashp->cpage = NULL;
815 hashp->cbucket++;
816 hashp->cndx = 1;
817 } else
818 hashp->cndx = ndx;
819 }
820 return (SUCCESS);
821 }
822
823 /********************************* UTILITIES ************************/
824
825 /*
826 * Returns:
827 * 0 ==> OK
828 * -1 ==> Error
829 */
830 extern int
831 __expand_table(hashp)
832 HTAB *hashp;
833 {
834 u_int old_bucket, new_bucket;
835 int dirsize, new_segnum, spare_ndx;
836
837 #ifdef HASH_STATISTICS
838 hash_expansions++;
839 #endif
840 new_bucket = ++hashp->MAX_BUCKET;
841 old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK);
842
843 new_segnum = new_bucket >> hashp->SSHIFT;
844
845 /* Check if we need a new segment */
846 if (new_segnum >= hashp->nsegs) {
847 /* Check if we need to expand directory */
848 if (new_segnum >= hashp->DSIZE) {
849 /* Reallocate directory */
850 dirsize = hashp->DSIZE * sizeof(SEGMENT *);
851 if (!hash_realloc(&hashp->dir, dirsize, dirsize << 1))
852 return (-1);
853 hashp->DSIZE = dirsize << 1;
854 }
855 if ((hashp->dir[new_segnum] =
856 (SEGMENT)calloc(hashp->SGSIZE, sizeof(SEGMENT))) == NULL)
857 return (-1);
858 hashp->exsegs++;
859 hashp->nsegs++;
860 }
861 /*
862 * If the split point is increasing (MAX_BUCKET's log base 2
863 * * increases), we need to copy the current contents of the spare
864 * split bucket to the next bucket.
865 */
866 spare_ndx = __log2(hashp->MAX_BUCKET + 1);
867 if (spare_ndx > hashp->OVFL_POINT) {
868 hashp->SPARES[spare_ndx] = hashp->SPARES[hashp->OVFL_POINT];
869 hashp->OVFL_POINT = spare_ndx;
870 }
871
872 if (new_bucket > hashp->HIGH_MASK) {
873 /* Starting a new doubling */
874 hashp->LOW_MASK = hashp->HIGH_MASK;
875 hashp->HIGH_MASK = new_bucket | hashp->LOW_MASK;
876 }
877 /* Relocate records to the new bucket */
878 return (__split_page(hashp, old_bucket, new_bucket));
879 }
880
881 /*
882 * If realloc guarantees that the pointer is not destroyed if the realloc
883 * fails, then this routine can go away.
884 */
885 static void *
886 hash_realloc(p_ptr, oldsize, newsize)
887 SEGMENT **p_ptr;
888 int oldsize, newsize;
889 {
890 register void *p;
891
892 if (p = malloc(newsize)) {
893 memmove(p, *p_ptr, oldsize);
894 memset((char *)p + oldsize, 0, newsize - oldsize);
895 free(*p_ptr);
896 *p_ptr = p;
897 }
898 return (p);
899 }
900
901 extern u_int
902 __call_hash(hashp, k, len)
903 HTAB *hashp;
904 char *k;
905 int len;
906 {
907 int n, bucket;
908
909 n = hashp->hash(k, len);
910 bucket = n & hashp->HIGH_MASK;
911 if (bucket > hashp->MAX_BUCKET)
912 bucket = bucket & hashp->LOW_MASK;
913 return (bucket);
914 }
915
916 /*
917 * Allocate segment table. On error, destroy the table and set errno.
918 *
919 * Returns 0 on success
920 */
921 static int
922 alloc_segs(hashp, nsegs)
923 HTAB *hashp;
924 int nsegs;
925 {
926 register int i;
927 register SEGMENT store;
928
929 int save_errno;
930
931 if ((hashp->dir =
932 (SEGMENT *)calloc(hashp->DSIZE, sizeof(SEGMENT *))) == NULL) {
933 save_errno = errno;
934 (void)hdestroy(hashp);
935 errno = save_errno;
936 return (-1);
937 }
938 /* Allocate segments */
939 if ((store =
940 (SEGMENT)calloc(nsegs << hashp->SSHIFT, sizeof(SEGMENT))) == NULL) {
941 save_errno = errno;
942 (void)hdestroy(hashp);
943 errno = save_errno;
944 return (-1);
945 }
946 for (i = 0; i < nsegs; i++, hashp->nsegs++)
947 hashp->dir[i] = &store[i << hashp->SSHIFT];
948 return (0);
949 }
950
951 #if BYTE_ORDER == LITTLE_ENDIAN
952 /*
953 * Hashp->hdr needs to be byteswapped.
954 */
955 static void
956 swap_header_copy(srcp, destp)
957 HASHHDR *srcp, *destp;
958 {
959 int i;
960
961 P_32_COPY(srcp->magic, destp->magic);
962 P_32_COPY(srcp->version, destp->version);
963 P_32_COPY(srcp->lorder, destp->lorder);
964 P_32_COPY(srcp->bsize, destp->bsize);
965 P_32_COPY(srcp->bshift, destp->bshift);
966 P_32_COPY(srcp->dsize, destp->dsize);
967 P_32_COPY(srcp->ssize, destp->ssize);
968 P_32_COPY(srcp->sshift, destp->sshift);
969 P_32_COPY(srcp->ovfl_point, destp->ovfl_point);
970 P_32_COPY(srcp->last_freed, destp->last_freed);
971 P_32_COPY(srcp->max_bucket, destp->max_bucket);
972 P_32_COPY(srcp->high_mask, destp->high_mask);
973 P_32_COPY(srcp->low_mask, destp->low_mask);
974 P_32_COPY(srcp->ffactor, destp->ffactor);
975 P_32_COPY(srcp->nkeys, destp->nkeys);
976 P_32_COPY(srcp->hdrpages, destp->hdrpages);
977 P_32_COPY(srcp->h_charkey, destp->h_charkey);
978 for (i = 0; i < NCACHED; i++) {
979 P_32_COPY(srcp->spares[i], destp->spares[i]);
980 P_16_COPY(srcp->bitmaps[i], destp->bitmaps[i]);
981 }
982 }
983
984 static void
985 swap_header(hashp)
986 HTAB *hashp;
987 {
988 HASHHDR *hdrp;
989 int i;
990
991 hdrp = &hashp->hdr;
992
993 M_32_SWAP(hdrp->magic);
994 M_32_SWAP(hdrp->version);
995 M_32_SWAP(hdrp->lorder);
996 M_32_SWAP(hdrp->bsize);
997 M_32_SWAP(hdrp->bshift);
998 M_32_SWAP(hdrp->dsize);
999 M_32_SWAP(hdrp->ssize);
1000 M_32_SWAP(hdrp->sshift);
1001 M_32_SWAP(hdrp->ovfl_point);
1002 M_32_SWAP(hdrp->last_freed);
1003 M_32_SWAP(hdrp->max_bucket);
1004 M_32_SWAP(hdrp->high_mask);
1005 M_32_SWAP(hdrp->low_mask);
1006 M_32_SWAP(hdrp->ffactor);
1007 M_32_SWAP(hdrp->nkeys);
1008 M_32_SWAP(hdrp->hdrpages);
1009 M_32_SWAP(hdrp->h_charkey);
1010 for (i = 0; i < NCACHED; i++) {
1011 M_32_SWAP(hdrp->spares[i]);
1012 M_16_SWAP(hdrp->bitmaps[i]);
1013 }
1014 }
1015 #endif
mirror of libc