2 * Copyright (c) 1990, 1993, 1994
3 * The Regents of the University of California. All rights reserved.
5 * This code is derived from software contributed to Berkeley by
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
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.
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
38 #include <sys/param.h>
57 static int32_t flush_meta
__P((HTAB
*));
58 static int32_t hash_access
__P((HTAB
*, ACTION
, const DBT
*, DBT
*));
59 static int32_t hash_close
__P((DB
*));
60 static int32_t hash_delete
__P((const DB
*, const DBT
*, u_int32_t
));
61 static int32_t hash_fd
__P((const DB
*));
62 static int32_t hash_get
__P((const DB
*, const DBT
*, DBT
*, u_int32_t
));
63 static int32_t hash_put
__P((const DB
*, DBT
*, const DBT
*, u_int32_t
));
64 static int32_t hash_seq
__P((const DB
*, DBT
*, DBT
*, u_int32_t
));
65 static int32_t hash_sync
__P((const DB
*, u_int32_t
));
66 static int32_t hdestroy
__P((HTAB
*));
67 static int32_t cursor_get
__P((const DB
*, CURSOR
*, DBT
*, DBT
*, \
69 static int32_t cursor_delete
__P((const DB
*, CURSOR
*, u_int32_t
));
70 static HTAB
*init_hash
__P((HTAB
*, const char *, const HASHINFO
*));
71 static int32_t init_htab
__P((HTAB
*, int32_t));
72 #if DB_BYTE_ORDER == DB_LITTLE_ENDIAN
73 static void swap_header
__P((HTAB
*));
74 static void swap_header_copy
__P((HASHHDR
*, HASHHDR
*));
76 static u_int32_t hget_header
__P((HTAB
*, u_int32_t
));
77 static void hput_header
__P((HTAB
*));
79 #define RETURN_ERROR(ERR, LOC) { save_errno = ERR; goto LOC; }
86 #ifdef HASH_STATISTICS
87 u_int32_t hash_accesses
, hash_collisions
, hash_expansions
, hash_overflows
,
91 /************************** INTERFACE ROUTINES ***************************/
95 __kdb2_hash_open(file
, flags
, mode
, info
, dflags
)
97 int32_t flags
, mode
, dflags
;
98 const HASHINFO
*info
; /* Special directives for create */
104 int32_t bpages
, csize
, new_table
, save_errno
, specified_file
;
106 if ((flags
& O_ACCMODE
) == O_WRONLY
) {
110 if (!(hashp
= (HTAB
*)calloc(1, sizeof(HTAB
))))
114 /* set this now, before file goes away... */
115 specified_file
= (file
!= NULL
);
118 * If we are root and thus have access to /var/run, then use
119 * it, else tempnam(3) will use /var/tmp.
121 if (!(file
= tempnam("/var/run", NULL
))) {
123 * No memory here is not the only failure
124 * possibility, but probably the most likely.
131 /* store the file name so that we can unlink it later */
134 fprintf(stderr
, dgettext(TEXT_DOMAIN
,
135 "Using file name %s.\n"), file
);
139 * Even if user wants write only, we need to be able to read
140 * the actual file, so we need to open it read/write. But, the
141 * field in the hashp structure needs to be accurate so that
142 * we can check accesses.
144 hashp
->flags
= flags
;
145 hashp
->save_file
= specified_file
&& (hashp
->flags
& O_RDWR
);
148 if (!file
|| (flags
& O_TRUNC
) ||
149 (stat(file
, &statbuf
) && (errno
== ENOENT
))) {
151 errno
= 0; /* In case someone looks at errno. */
155 if ((hashp
->fp
= open(file
, flags
|O_BINARY
, mode
)) == -1)
156 RETURN_ERROR(errno
, error0
);
157 (void)fcntl(hashp
->fp
, F_SETFD
, 1);
160 /* Process arguments to set up hash table header. */
162 if (!(hashp
= init_hash(hashp
, file
, info
)))
163 RETURN_ERROR(errno
, error1
);
165 /* Table already exists */
166 if (info
&& info
->hash
)
167 hashp
->hash
= info
->hash
;
169 hashp
->hash
= __default_hash
;
171 /* copy metadata from page into header */
172 if (hget_header(hashp
,
173 (info
&& info
->bsize
? info
->bsize
: DEF_BUCKET_SIZE
)) !=
175 RETURN_ERROR(EFTYPE
, error1
);
177 /* Verify file type, versions and hash function */
178 if (hashp
->hdr
.magic
!= HASHMAGIC
)
179 RETURN_ERROR(EFTYPE
, error1
);
180 #define OLDHASHVERSION 1
181 if (hashp
->hdr
.version
!= HASHVERSION
&&
182 hashp
->hdr
.version
!= OLDHASHVERSION
)
183 RETURN_ERROR(EFTYPE
, error1
);
184 if (hashp
->hash(CHARKEY
, sizeof(CHARKEY
))
185 != hashp
->hdr
.h_charkey
)
186 RETURN_ERROR(EFTYPE
, error1
);
188 * Figure out how many segments we need. Max_Bucket is the
189 * maximum bucket number, so the number of buckets is
193 /* Read in bitmaps */
194 bpages
= (hashp
->hdr
.spares
[hashp
->hdr
.ovfl_point
] +
195 (hashp
->hdr
.bsize
<< BYTE_SHIFT
) - 1) >>
196 (hashp
->hdr
.bshift
+ BYTE_SHIFT
);
198 hashp
->nmaps
= bpages
;
199 (void)memset(&hashp
->mapp
[0], 0, bpages
* sizeof(u_int32_t
*));
203 mpool_key
.data
= (u_int8_t
*)file
;
204 mpool_key
.size
= strlen(file
);
206 if (info
&& info
->cachesize
)
207 csize
= info
->cachesize
/ hashp
->hdr
.bsize
;
209 csize
= DEF_CACHESIZE
/ hashp
->hdr
.bsize
;
210 hashp
->mp
= mpool_open(&mpool_key
, hashp
->fp
, hashp
->hdr
.bsize
, csize
);
213 RETURN_ERROR(errno
, error1
);
214 mpool_filter(hashp
->mp
, __pgin_routine
, __pgout_routine
, hashp
);
217 * For a new table, set up the bitmaps.
220 init_htab(hashp
, info
&& info
->nelem
? info
->nelem
: 1))
223 /* initialize the cursor queue */
224 TAILQ_INIT(&hashp
->curs_queue
);
225 hashp
->seq_cursor
= NULL
;
228 /* get a chunk of memory for our split buffer */
229 hashp
->split_buf
= (PAGE16
*)malloc(hashp
->hdr
.bsize
);
230 if (!hashp
->split_buf
)
233 hashp
->new_file
= new_table
;
235 if (!(dbp
= (DB
*)malloc(sizeof(DB
))))
238 dbp
->internal
= hashp
;
239 dbp
->close
= hash_close
;
240 dbp
->del
= hash_delete
;
245 dbp
->sync
= hash_sync
;
249 (void)fprintf(stderr
,
250 "%s\n%s%lx\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",
252 "TABLE POINTER ", (void *)hashp
,
253 "BUCKET SIZE ", hashp
->hdr
.bsize
,
254 "BUCKET SHIFT ", hashp
->hdr
.bshift
,
255 "FILL FACTOR ", hashp
->hdr
.ffactor
,
256 "MAX BUCKET ", hashp
->hdr
.max_bucket
,
257 "OVFL POINT ", hashp
->hdr
.ovfl_point
,
258 "LAST FREED ", hashp
->hdr
.last_freed
,
259 "HIGH MASK ", hashp
->hdr
.high_mask
,
260 "LOW MASK ", hashp
->hdr
.low_mask
,
261 "NKEYS ", hashp
->hdr
.nkeys
);
263 #ifdef HASH_STATISTICS
264 hash_overflows
= hash_accesses
= hash_collisions
= hash_expansions
= 0;
277 (void)close(hashp
->fp
);
281 free((void*)(hashp
->fname
)); /* SUNW14resync */
297 hashp
= (HTAB
*)dbp
->internal
;
298 retval
= hdestroy(hashp
);
312 hashp
= (HTAB
*)dbp
->internal
;
313 if (hashp
->fp
== -1) {
320 /************************** LOCAL CREATION ROUTINES **********************/
322 init_hash(hashp
, file
, info
)
325 const HASHINFO
*info
;
329 hashp
->hdr
.nkeys
= 0;
330 hashp
->hdr
.lorder
= DB_BYTE_ORDER
;
331 hashp
->hdr
.bsize
= DEF_BUCKET_SIZE
;
332 hashp
->hdr
.bshift
= DEF_BUCKET_SHIFT
;
333 hashp
->hdr
.ffactor
= DEF_FFACTOR
;
334 hashp
->hash
= __default_hash
;
335 memset(hashp
->hdr
.spares
, 0, sizeof(hashp
->hdr
.spares
));
336 memset(hashp
->hdr
.bitmaps
, 0, sizeof(hashp
->hdr
.bitmaps
));
338 /* Fix bucket size to be optimal for file system */
340 if (stat(file
, &statbuf
))
342 hashp
->hdr
.bsize
= statbuf
.st_blksize
;
343 hashp
->hdr
.bshift
= __log2(hashp
->hdr
.bsize
);
347 /* Round pagesize up to power of 2 */
348 hashp
->hdr
.bshift
= __log2(info
->bsize
);
349 hashp
->hdr
.bsize
= 1 << hashp
->hdr
.bshift
;
350 if (hashp
->hdr
.bsize
> MAX_BSIZE
) {
356 hashp
->hdr
.ffactor
= info
->ffactor
;
358 hashp
->hash
= info
->hash
;
360 if ((info
->lorder
!= DB_BIG_ENDIAN
) &&
361 (info
->lorder
!= DB_LITTLE_ENDIAN
)) {
365 hashp
->hdr
.lorder
= info
->lorder
;
372 * Returns 0 on No Error
375 init_htab(hashp
, nelem
)
379 int32_t l2
, nbuckets
;
382 * Divide number of elements by the fill factor and determine a
383 * desired number of buckets. Allocate space for the next greater
384 * power of two number of buckets.
386 nelem
= (nelem
- 1) / hashp
->hdr
.ffactor
+ 1;
388 l2
= __log2(MAX(nelem
, 2));
391 hashp
->hdr
.spares
[l2
] = l2
+ 1;
392 hashp
->hdr
.spares
[l2
+ 1] = l2
+ 1;
393 hashp
->hdr
.ovfl_point
= l2
;
394 hashp
->hdr
.last_freed
= 2;
396 hashp
->hdr
.max_bucket
= hashp
->hdr
.low_mask
= nbuckets
- 1;
397 hashp
->hdr
.high_mask
= (nbuckets
<< 1) - 1;
400 * The number of header pages is the size of the header divided by
401 * the amount of freespace on header pages (the page size - the
402 * size of 1 integer where the length of the header info on that
403 * page is stored) plus another page if it didn't divide evenly.
405 hashp
->hdr
.hdrpages
=
406 (sizeof(HASHHDR
) / (hashp
->hdr
.bsize
- HEADER_OVERHEAD
)) +
407 (((sizeof(HASHHDR
) % (hashp
->hdr
.bsize
- HEADER_OVERHEAD
)) == 0)
410 /* Create pages for these buckets */
412 for (i = 0; i <= hashp->hdr.max_bucket; i++) {
413 if (__new_page(hashp, (u_int32_t)i, A_BUCKET) != 0)
418 /* First bitmap page is at: splitpoint l2 page offset 1 */
419 if (__ibitmap(hashp
, OADDR_OF(l2
, 1), l2
+ 1, 0))
426 * Functions to get/put hash header. We access the file directly.
429 hget_header(hashp
, page_size
)
433 u_int32_t num_copied
;
438 hdr_dest
= (u_int8_t
*)&hashp
->hdr
;
442 * This should not be printing to stderr on a "normal" error case.
444 lseek(hashp
->fp
, 0, SEEK_SET
);
445 num_copied
= read(hashp
->fp
, hdr_dest
, sizeof(HASHHDR
));
446 if (num_copied
!= sizeof(HASHHDR
)) {
447 /* Solaris Kerberos: Make sure to print a newline */
448 fprintf(stderr
, dgettext(TEXT_DOMAIN
,
449 "hash: could not retrieve header\n"));
452 #if DB_BYTE_ORDER == DB_LITTLE_ENDIAN
463 #if DB_BYTE_ORDER == DB_LITTLE_ENDIAN
466 u_int32_t num_copied
, i
;
471 #if DB_BYTE_ORDER == DB_LITTLE_ENDIAN
473 swap_header_copy(&hashp
->hdr
, whdrp
);
476 lseek(hashp
->fp
, 0, SEEK_SET
);
477 num_copied
= write(hashp
->fp
, whdrp
, sizeof(HASHHDR
));
478 if (num_copied
!= sizeof(HASHHDR
))
479 /* Solaris Kerberos: Make sure to print a newline */
480 (void)fprintf(stderr
, dgettext(TEXT_DOMAIN
,
481 "hash: could not write hash header\n"));
485 /********************** DESTROY/CLOSE ROUTINES ************************/
488 * Flushes any changes to the file if necessary and destroys the hashp
489 * structure, freeing all allocated space.
499 #ifdef HASH_STATISTICS
501 (void)fprintf(stderr
, dgettext(TEXT_DOMAIN
,
502 "hdestroy: accesses %ld collisions %ld\n"),
503 hash_accesses
, hash_collisions
);
504 (void)fprintf(stderr
,
505 dgettext(TEXT_DOMAIN
,
506 "hdestroy: expansions %ld\n"), hash_expansions
);
507 (void)fprintf(stderr
,
508 dgettext(TEXT_DOMAIN
,
509 "hdestroy: overflows %ld\n"), hash_overflows
);
510 (void)fprintf(stderr
,
511 dgettext(TEXT_DOMAIN
,
512 "hdestroy: big key/data pages %ld\n"), hash_bigpages
);
513 (void)fprintf(stderr
,
514 "keys %ld maxp %d\n", hashp
->hdr
.nkeys
, hashp
->hdr
.max_bucket
);
516 for (i
= 0; i
< NCACHED
; i
++)
517 (void)fprintf(stderr
,
518 "spares[%d] = %d\n", i
, hashp
->hdr
.spares
[i
]);
522 if (flush_meta(hashp
) && !save_errno
)
525 /* Free the split page */
526 if (hashp
->split_buf
)
527 free(hashp
->split_buf
);
529 /* Free the big key and big data returns */
530 if (hashp
->bigkey_buf
)
531 free(hashp
->bigkey_buf
);
532 if (hashp
->bigdata_buf
)
533 free(hashp
->bigdata_buf
);
535 /* XXX This should really iterate over the cursor queue, but
536 it's not clear how to do that, and the only cursor a hash
537 table ever creates is the one used by hash_seq(). Passing
538 NULL as the first arg is also a kludge, but I know that
539 it's never used, so I do it. The intent is to plug the
540 memory leak. Correctness can come later. */
542 if (hashp
->seq_cursor
)
543 hashp
->seq_cursor
->delete(NULL
, hashp
->seq_cursor
, 0);
545 /* shut down mpool */
546 mpool_sync(hashp
->mp
);
547 mpool_close(hashp
->mp
);
550 (void)close(hashp
->fp
);
553 * *** This may cause problems if hashp->fname is set in any case
554 * other than the case that we are generating a temporary file name.
555 * Note that the new version of mpool should support temporary
556 * files within mpool itself.
558 if (hashp
->fname
&& !hashp
->save_file
) {
560 fprintf(stderr
, dgettext(TEXT_DOMAIN
,
561 "Unlinking file %s.\n"), hashp
->fname
);
563 /* we need to chmod the file to allow it to be deleted... */
564 chmod(hashp
->fname
, 0700);
565 unlink(hashp
->fname
);
566 /* destroy the temporary name */
567 free((void *)(hashp
->fname
)); /* SUNW14resync */
579 * Write modified pages to disk
586 hash_sync(dbp
, flags
)
592 hashp
= (HTAB
*)dbp
->internal
;
596 * Check success/failure conditions.
598 return (flush_meta(hashp
) || mpool_sync(hashp
->mp
));
604 * -1 indicates that errno should be set
612 if (!hashp
->save_file
)
614 hashp
->hdr
.magic
= HASHMAGIC
;
615 hashp
->hdr
.version
= HASHVERSION
;
616 hashp
->hdr
.h_charkey
= hashp
->hash(CHARKEY
, sizeof(CHARKEY
));
618 /* write out metadata */
621 for (i
= 0; i
< NCACHED
; i
++)
622 if (hashp
->mapp
[i
]) {
623 if (__put_page(hashp
,
624 (PAGE16
*)hashp
->mapp
[i
], A_BITMAP
, 1))
626 hashp
->mapp
[i
] = NULL
;
631 /*******************************SEARCH ROUTINES *****************************/
633 * All the access routines return
637 * 1 to indicate an external ERROR (i.e. key not found, etc)
638 * -1 to indicate an internal ERROR (i.e. out of memory, etc)
641 /* *** make sure this is true! */
644 hash_get(dbp
, key
, data
, flag
)
652 hashp
= (HTAB
*)dbp
->internal
;
654 hashp
->local_errno
= errno
= EINVAL
;
657 return (hash_access(hashp
, HASH_GET
, key
, data
));
661 hash_put(dbp
, key
, data
, flag
)
669 hashp
= (HTAB
*)dbp
->internal
;
670 if (flag
&& flag
!= R_NOOVERWRITE
) {
671 hashp
->local_errno
= errno
= EINVAL
;
674 if ((hashp
->flags
& O_ACCMODE
) == O_RDONLY
) {
675 hashp
->local_errno
= errno
= EPERM
;
678 return (hash_access(hashp
, flag
== R_NOOVERWRITE
?
679 HASH_PUTNEW
: HASH_PUT
, key
, (DBT
*)data
));
683 hash_delete(dbp
, key
, flag
)
686 u_int32_t flag
; /* Ignored */
690 hashp
= (HTAB
*)dbp
->internal
;
692 hashp
->local_errno
= errno
= EINVAL
;
695 if ((hashp
->flags
& O_ACCMODE
) == O_RDONLY
) {
696 hashp
->local_errno
= errno
= EPERM
;
700 return (hash_access(hashp
, HASH_DELETE
, key
, NULL
));
704 * Assume that hashp has been set in wrapper routine.
707 hash_access(hashp
, action
, key
, val
)
713 DBT page_key
, page_val
;
719 #ifdef HASH_STATISTICS
726 * Set up item_info so that we're looking for space to add an item
727 * as we cycle through the pages looking for the key.
729 if (action
== HASH_PUT
|| action
== HASH_PUTNEW
) {
730 if (ISBIG(key
->size
+ val
->size
, hashp
))
731 item_info
.seek_size
= PAIR_OVERHEAD
;
733 item_info
.seek_size
= key
->size
+ val
->size
;
735 item_info
.seek_size
= 0;
736 item_info
.seek_found_page
= 0;
738 bucket
= __call_hash(hashp
, (int8_t *)key
->data
, key
->size
);
741 __get_item_reset(hashp
, &cursor
);
743 cursor
.bucket
= bucket
;
745 __get_item_next(hashp
, &cursor
, &page_key
, &page_val
, &item_info
);
746 if (item_info
.status
== ITEM_ERROR
)
748 if (item_info
.status
== ITEM_NO_MORE
)
751 if (item_info
.key_off
== BIGPAIR
) {
754 * 0 is a valid index.
756 if (__find_bigpair(hashp
, &cursor
, (int8_t *)key
->data
,
759 } else if (key
->size
== page_key
.size
&&
760 !memcmp(key
->data
, page_key
.data
, key
->size
))
763 #ifdef HASH_STATISTICS
766 __get_item_done(hashp
, &cursor
);
769 * At this point, item_info will list either the last page in
770 * the chain, or the last page in the chain plus a pgno for where
771 * to find the first page in the chain with space for the
772 * item we wish to add.
779 if (__addel(hashp
, &item_info
, key
, val
, num_items
, 0))
788 if (item_info
.caused_expand
)
789 __expand_table(hashp
);
792 found
: __get_item_done(hashp
, &cursor
);
796 /* mpool_put(hashp->mp, pagep, 0); */
799 if (item_info
.key_off
== BIGPAIR
) {
800 if (__big_return(hashp
, &item_info
, val
, 0))
803 val
->data
= page_val
.data
;
804 val
->size
= page_val
.size
;
806 /* *** data may not be available! */
809 if (__delpair(hashp
, &cursor
, &item_info
) ||
810 __addel(hashp
, &item_info
, key
, val
, UNKNOWN
, 0))
812 __get_item_done(hashp
, &cursor
);
813 if (item_info
.caused_expand
)
814 __expand_table(hashp
);
817 if (__delpair(hashp
, &cursor
, &item_info
))
826 /* ****************** CURSORS ********************************** */
834 new_curs
= (CURSOR
*)malloc(sizeof(struct cursor_t
));
838 (struct item_info
*)malloc(sizeof(struct item_info
));
839 if (!new_curs
->internal
) {
843 new_curs
->get
= cursor_get
;
844 new_curs
->delete = cursor_delete
;
846 new_curs
->bucket
= 0;
847 new_curs
->pgno
= INVALID_PGNO
;
850 new_curs
->pagep
= NULL
;
852 /* place onto queue of cursors */
853 hashp
= (HTAB
*)dbp
->internal
;
854 TAILQ_INSERT_TAIL(&hashp
->curs_queue
, new_curs
, queue
);
860 cursor_get(dbp
, cursorp
, key
, val
, flags
)
869 hashp
= (HTAB
*)dbp
->internal
;
871 if (flags
&& flags
!= R_FIRST
&& flags
!= R_NEXT
) {
872 hashp
->local_errno
= errno
= EINVAL
;
875 #ifdef HASH_STATISTICS
879 item_info
.seek_size
= 0;
881 if (flags
== R_FIRST
)
882 __get_item_first(hashp
, cursorp
, key
, val
, &item_info
);
884 __get_item_next(hashp
, cursorp
, key
, val
, &item_info
);
887 * This needs to be changed around. As is, get_item_next advances
888 * the pointers on the page but this function actually advances
889 * bucket pointers. This works, since the only other place we
890 * use get_item_next is in hash_access which only deals with one
891 * bucket at a time. However, there is the problem that certain other
892 * functions (such as find_bigpair and delpair) depend on the
893 * pgndx member of the cursor. Right now, they are using pngdx - 1
894 * since indices refer to the __next__ item that is to be fetched
895 * from the page. This is ugly, as you may have noticed, whoever
896 * you are. The best solution would be to depend on item_infos to
897 * deal with _current_ information, and have the cursors only
898 * deal with _next_ information. In that scheme, get_item_next
899 * would also advance buckets. Version 3...
904 * Must always enter this loop to do error handling and
905 * check for big key/data pair.
908 if (item_info
.status
== ITEM_OK
) {
909 if (item_info
.key_off
== BIGPAIR
&&
910 __big_keydata(hashp
, cursorp
->pagep
, key
, val
,
915 } else if (item_info
.status
!= ITEM_NO_MORE
)
918 __put_page(hashp
, cursorp
->pagep
, A_RAW
, 0);
919 cursorp
->ndx
= cursorp
->pgndx
= 0;
921 cursorp
->pgno
= INVALID_PGNO
;
922 cursorp
->pagep
= NULL
;
923 if (cursorp
->bucket
> hashp
->hdr
.max_bucket
)
925 __get_item_next(hashp
, cursorp
, key
, val
, &item_info
);
928 __get_item_done(hashp
, cursorp
);
933 cursor_delete(dbp
, cursor
, flags
)
938 /* XXX this is empirically determined, so it might not be completely
939 correct, but it seems to work. At the very least it fixes
942 free(cursor
->internal
);
949 hash_seq(dbp
, key
, val
, flag
)
957 * Seq just uses the default cursor to go sequecing through the
958 * database. Note that the default cursor is the first in the list.
961 hashp
= (HTAB
*)dbp
->internal
;
962 if (!hashp
->seq_cursor
)
963 hashp
->seq_cursor
= __cursor_creat(dbp
);
965 return (hashp
->seq_cursor
->get(dbp
, hashp
->seq_cursor
, key
, val
, flag
));
968 /********************************* UTILITIES ************************/
976 __expand_table(hashp
)
979 u_int32_t old_bucket
, new_bucket
;
982 #ifdef HASH_STATISTICS
985 new_bucket
= ++hashp
->hdr
.max_bucket
;
986 old_bucket
= (hashp
->hdr
.max_bucket
& hashp
->hdr
.low_mask
);
988 /* Get a page for this new bucket */
989 if (__new_page(hashp
, new_bucket
, A_BUCKET
) != 0)
993 * If the split point is increasing (hdr.max_bucket's log base 2
994 * increases), we need to copy the current contents of the spare
995 * split bucket to the next bucket.
997 spare_ndx
= __log2(hashp
->hdr
.max_bucket
+ 1);
998 if (spare_ndx
> hashp
->hdr
.ovfl_point
) {
999 hashp
->hdr
.spares
[spare_ndx
] = hashp
->hdr
.spares
[hashp
->hdr
.ovfl_point
];
1000 hashp
->hdr
.ovfl_point
= spare_ndx
;
1002 if (new_bucket
> hashp
->hdr
.high_mask
) {
1003 /* Starting a new doubling */
1004 hashp
->hdr
.low_mask
= hashp
->hdr
.high_mask
;
1005 hashp
->hdr
.high_mask
= new_bucket
| hashp
->hdr
.low_mask
;
1007 if (BUCKET_TO_PAGE(new_bucket
) > MAX_PAGES(hashp
)) {
1008 fprintf(stderr
,dgettext(TEXT_DOMAIN
,
1009 "hash: Cannot allocate new bucket. Pages exhausted.\n"));
1012 /* Relocate records to the new bucket */
1013 return (__split_page(hashp
, old_bucket
, new_bucket
));
1017 __call_hash(hashp
, k
, len
)
1024 n
= hashp
->hash(k
, len
);
1025 bucket
= n
& hashp
->hdr
.high_mask
;
1026 if (bucket
> hashp
->hdr
.max_bucket
)
1027 bucket
= bucket
& hashp
->hdr
.low_mask
;
1031 #if DB_BYTE_ORDER == DB_LITTLE_ENDIAN
1033 * Hashp->hdr needs to be byteswapped.
1036 swap_header_copy(srcp
, destp
)
1037 HASHHDR
*srcp
, *destp
;
1041 P_32_COPY(srcp
->magic
, destp
->magic
);
1042 P_32_COPY(srcp
->version
, destp
->version
);
1043 P_32_COPY(srcp
->lorder
, destp
->lorder
);
1044 P_32_COPY(srcp
->bsize
, destp
->bsize
);
1045 P_32_COPY(srcp
->bshift
, destp
->bshift
);
1046 P_32_COPY(srcp
->ovfl_point
, destp
->ovfl_point
);
1047 P_32_COPY(srcp
->last_freed
, destp
->last_freed
);
1048 P_32_COPY(srcp
->max_bucket
, destp
->max_bucket
);
1049 P_32_COPY(srcp
->high_mask
, destp
->high_mask
);
1050 P_32_COPY(srcp
->low_mask
, destp
->low_mask
);
1051 P_32_COPY(srcp
->ffactor
, destp
->ffactor
);
1052 P_32_COPY(srcp
->nkeys
, destp
->nkeys
);
1053 P_32_COPY(srcp
->hdrpages
, destp
->hdrpages
);
1054 P_32_COPY(srcp
->h_charkey
, destp
->h_charkey
);
1055 for (i
= 0; i
< NCACHED
; i
++) {
1056 P_32_COPY(srcp
->spares
[i
], destp
->spares
[i
]);
1057 P_16_COPY(srcp
->bitmaps
[i
], destp
->bitmaps
[i
]);
1070 M_32_SWAP(hdrp
->magic
);
1071 M_32_SWAP(hdrp
->version
);
1072 M_32_SWAP(hdrp
->lorder
);
1073 M_32_SWAP(hdrp
->bsize
);
1074 M_32_SWAP(hdrp
->bshift
);
1075 M_32_SWAP(hdrp
->ovfl_point
);
1076 M_32_SWAP(hdrp
->last_freed
);
1077 M_32_SWAP(hdrp
->max_bucket
);
1078 M_32_SWAP(hdrp
->high_mask
);
1079 M_32_SWAP(hdrp
->low_mask
);
1080 M_32_SWAP(hdrp
->ffactor
);
1081 M_32_SWAP(hdrp
->nkeys
);
1082 M_32_SWAP(hdrp
->hdrpages
);
1083 M_32_SWAP(hdrp
->h_charkey
);
1084 for (i
= 0; i
< NCACHED
; i
++) {
1085 M_32_SWAP(hdrp
->spares
[i
]);
1086 M_16_SWAP(hdrp
->bitmaps
[i
]);
1089 #endif /* DB_BYTE_ORDER == DB_LITTLE_ENDIAN */