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