97 	HTAB *hashp;  in __hash_open()  local
102 	if (!(hashp = (HTAB *)calloc(1, sizeof(HTAB))))  in __hash_open()
104 	hashp->fp = -1;  in __hash_open()
112 	hashp->flags = flags;  in __hash_open()
119 		if ((hashp->fp = _open(file, flags | O_CLOEXEC, mode)) == -1)  in __hash_open()
121 		new_table = _fstat(hashp->fp, &statbuf) == 0 &&  in __hash_open()
128 		if (!(hashp = init_hash(hashp, file, info)))  in __hash_open()
133 			hashp->hash = info->hash;  in __hash_open()
135 			hashp->hash = __default_hash;  in __hash_open()
137 		hdrsize = _read(hashp->fp, &hashp->hdr, sizeof(HASHHDR));  in __hash_open()
139 		swap_header(hashp);  in __hash_open()
146 		if (hashp->MAGIC != HASHMAGIC)  in __hash_open()
149 		if (hashp->VERSION != HASHVERSION &&  in __hash_open()
150 		    hashp->VERSION != OLDHASHVERSION)  in __hash_open()
152 		if ((int32_t)hashp->hash(CHARKEY, sizeof(CHARKEY)) != hashp->H_CHARKEY)  in __hash_open()
159 		nsegs = howmany(hashp->MAX_BUCKET + 1, hashp->SGSIZE);  in __hash_open()
160 		if (alloc_segs(hashp, nsegs))  in __hash_open()
167 		bpages = (hashp->SPARES[hashp->OVFL_POINT] +  in __hash_open()
168 		    (hashp->BSIZE << BYTE_SHIFT) - 1) >>  in __hash_open()
169 		    (hashp->BSHIFT + BYTE_SHIFT);  in __hash_open()
171 		hashp->nmaps = bpages;  in __hash_open()
172 		(void)memset(&hashp->mapp[0], 0, bpages * sizeof(u_int32_t *));  in __hash_open()
177 		__buf_init(hashp, info->cachesize);  in __hash_open()
179 		__buf_init(hashp, DEF_BUFSIZE);  in __hash_open()
181 	hashp->new_file = new_table;  in __hash_open()
182 	hashp->save_file = file && (flags & O_RDWR);  in __hash_open()
183 	hashp->cbucket = -1;  in __hash_open()
186 		hdestroy(hashp);  in __hash_open()
190 	dbp->internal = hashp;  in __hash_open()
204 	    "TABLE POINTER   ", hashp,  in __hash_open()
205 	    "BUCKET SIZE     ", hashp->BSIZE,  in __hash_open()
206 	    "BUCKET SHIFT    ", hashp->BSHIFT,  in __hash_open()
207 	    "DIRECTORY SIZE  ", hashp->DSIZE,  in __hash_open()
208 	    "SEGMENT SIZE    ", hashp->SGSIZE,  in __hash_open()
209 	    "SEGMENT SHIFT   ", hashp->SSHIFT,  in __hash_open()
210 	    "FILL FACTOR     ", hashp->FFACTOR,  in __hash_open()
211 	    "MAX BUCKET      ", hashp->MAX_BUCKET,  in __hash_open()
212 	    "OVFL POINT	     ", hashp->OVFL_POINT,  in __hash_open()
213 	    "LAST FREED      ", hashp->LAST_FREED,  in __hash_open()
214 	    "HIGH MASK       ", hashp->HIGH_MASK,  in __hash_open()
215 	    "LOW  MASK       ", hashp->LOW_MASK,  in __hash_open()
216 	    "NSEGS           ", hashp->nsegs,  in __hash_open()
217 	    "NKEYS           ", hashp->NKEYS);  in __hash_open()
225 	if (hashp != NULL)  in __hash_open()
226 		(void)_close(hashp->fp);  in __hash_open()
229 	free(hashp);  in __hash_open()
237 	HTAB *hashp;  in hash_close()  local
243 	hashp = (HTAB *)dbp->internal;  in hash_close()
244 	retval = hdestroy(hashp);  in hash_close()
252 	HTAB *hashp;  in hash_fd()  local
257 	hashp = (HTAB *)dbp->internal;  in hash_fd()
258 	if (hashp->fp == -1) {  in hash_fd()
262 	return (hashp->fp);  in hash_fd()
267 init_hash(HTAB *hashp, const char *file, const HASHINFO *info)  in init_hash()  argument
273 	hashp->NKEYS = 0;  in init_hash()
274 	hashp->LORDER = BYTE_ORDER;  in init_hash()
275 	hashp->BSIZE = DEF_BUCKET_SIZE;  in init_hash()
276 	hashp->BSHIFT = DEF_BUCKET_SHIFT;  in init_hash()
277 	hashp->SGSIZE = DEF_SEGSIZE;  in init_hash()
278 	hashp->SSHIFT = DEF_SEGSIZE_SHIFT;  in init_hash()
279 	hashp->DSIZE = DEF_DIRSIZE;  in init_hash()
280 	hashp->FFACTOR = DEF_FFACTOR;  in init_hash()
281 	hashp->hash = __default_hash;  in init_hash()
282 	memset(hashp->SPARES, 0, sizeof(hashp->SPARES));  in init_hash()
283 	memset(hashp->BITMAPS, 0, sizeof (hashp->BITMAPS));  in init_hash()
289 		hashp->BSIZE = statbuf.st_blksize;  in init_hash()
290 		if (hashp->BSIZE > MAX_BSIZE)  in init_hash()
291 			hashp->BSIZE = MAX_BSIZE;  in init_hash()
292 		hashp->BSHIFT = __log2(hashp->BSIZE);  in init_hash()
298 			hashp->BSHIFT = __log2(info->bsize);  in init_hash()
299 			hashp->BSIZE = 1 << hashp->BSHIFT;  in init_hash()
300 			if (hashp->BSIZE > MAX_BSIZE) {  in init_hash()
306 			hashp->FFACTOR = info->ffactor;  in init_hash()
308 			hashp->hash = info->hash;  in init_hash()
317 			hashp->LORDER = info->lorder;  in init_hash()
321 	if (init_htab(hashp, nelem))  in init_hash()
324 		return (hashp);  in init_hash()
333 init_htab(HTAB *hashp, int nelem)  in init_htab()  argument
342 	nelem = (nelem - 1) / hashp->FFACTOR + 1;  in init_htab()
347 	hashp->SPARES[l2] = l2 + 1;  in init_htab()
348 	hashp->SPARES[l2 + 1] = l2 + 1;  in init_htab()
349 	hashp->OVFL_POINT = l2;  in init_htab()
350 	hashp->LAST_FREED = 2;  in init_htab()
353 	if (__ibitmap(hashp, OADDR_OF(l2, 1), l2 + 1, 0))  in init_htab()
356 	hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1;  in init_htab()
357 	hashp->HIGH_MASK = (nbuckets << 1) - 1;  in init_htab()
358 	hashp->HDRPAGES = ((MAX(sizeof(HASHHDR), MINHDRSIZE) - 1) >>  in init_htab()
359 	    hashp->BSHIFT) + 1;  in init_htab()
361 	nsegs = (nbuckets - 1) / hashp->SGSIZE + 1;  in init_htab()
364 	if (nsegs > hashp->DSIZE)  in init_htab()
365 		hashp->DSIZE = nsegs;  in init_htab()
366 	return (alloc_segs(hashp, nsegs));  in init_htab()
376 hdestroy(HTAB *hashp)  in hdestroy()  argument
390 	    hashp->NKEYS, hashp->MAX_BUCKET, hashp->nsegs);  in hdestroy()
394 		    "spares[%d] = %d\n", i, hashp->SPARES[i]);  in hdestroy()
400 	if (__buf_free(hashp, 1, hashp->save_file))  in hdestroy()
402 	if (hashp->dir) {  in hdestroy()
403 		free(*hashp->dir);	/* Free initial segments */  in hdestroy()
405 		while (hashp->exsegs--)  in hdestroy()
406 			free(hashp->dir[--hashp->nsegs]);  in hdestroy()
407 		free(hashp->dir);  in hdestroy()
409 	if (flush_meta(hashp) && !save_errno)  in hdestroy()
412 	for (i = 0; i < hashp->nmaps; i++)  in hdestroy()
413 		if (hashp->mapp[i])  in hdestroy()
414 			free(hashp->mapp[i]);  in hdestroy()
415 	if (hashp->tmp_key)  in hdestroy()
416 		free(hashp->tmp_key);  in hdestroy()
417 	if (hashp->tmp_buf)  in hdestroy()
418 		free(hashp->tmp_buf);  in hdestroy()
420 	if (hashp->fp != -1) {  in hdestroy()
421 		if (hashp->save_file)  in hdestroy()
422 			(void)_fsync(hashp->fp);  in hdestroy()
423 		(void)_close(hashp->fp);  in hdestroy()
426 	free(hashp);  in hdestroy()
444 	HTAB *hashp;  in hash_sync()  local
454 	hashp = (HTAB *)dbp->internal;  in hash_sync()
455 	if (!hashp->save_file)  in hash_sync()
457 	if (__buf_free(hashp, 0, 1) || flush_meta(hashp))  in hash_sync()
459 	if (hashp->fp != -1 && _fsync(hashp->fp) != 0)  in hash_sync()
461 	hashp->new_file = 0;  in hash_sync()
471 flush_meta(HTAB *hashp)  in flush_meta()  argument
479 	if (!hashp->save_file)  in flush_meta()
481 	hashp->MAGIC = HASHMAGIC;  in flush_meta()
482 	hashp->VERSION = HASHVERSION;  in flush_meta()
483 	hashp->H_CHARKEY = hashp->hash(CHARKEY, sizeof(CHARKEY));  in flush_meta()
485 	fp = hashp->fp;  in flush_meta()
486 	whdrp = &hashp->hdr;  in flush_meta()
489 	swap_header_copy(&hashp->hdr, whdrp);  in flush_meta()
496 			hashp->error = errno;  in flush_meta()
500 		if (hashp->mapp[i])  in flush_meta()
501 			if (__put_page(hashp, (char *)hashp->mapp[i],  in flush_meta()
502 				hashp->BITMAPS[i], 0, 1))  in flush_meta()
519 	HTAB *hashp;  in hash_get()  local
521 	hashp = (HTAB *)dbp->internal;  in hash_get()
523 		hashp->error = errno = EINVAL;  in hash_get()
526 	if ((hashp->flags & O_ACCMODE) == O_WRONLY) {  in hash_get()
527 		hashp->error = errno = EPERM;  in hash_get()
530 	return (hash_access(hashp, HASH_GET, (DBT *)key, data));  in hash_get()
536 	HTAB *hashp;  in hash_put()  local
538 	hashp = (HTAB *)dbp->internal;  in hash_put()
540 		hashp->error = errno = EINVAL;  in hash_put()
543 	if ((hashp->flags & O_ACCMODE) == O_RDONLY) {  in hash_put()
544 		hashp->error = errno = EPERM;  in hash_put()
547 	return (hash_access(hashp, flag == R_NOOVERWRITE ?  in hash_put()
555 	HTAB *hashp;  in hash_delete()  local
557 	hashp = (HTAB *)dbp->internal;  in hash_delete()
559 		hashp->error = errno = EINVAL;  in hash_delete()
562 	if ((hashp->flags & O_ACCMODE) == O_RDONLY) {  in hash_delete()
563 		hashp->error = errno = EPERM;  in hash_delete()
566 	return (hash_access(hashp, HASH_DELETE, (DBT *)key, NULL));  in hash_delete()
573 hash_access(HTAB *hashp, ACTION action, DBT *key, DBT *val)  in hash_access()  argument
586 	off = hashp->BSIZE;  in hash_access()
589 	rbufp = __get_buf(hashp, __call_hash(hashp, kp, size), NULL, 0);  in hash_access()
609 			rbufp = __get_buf(hashp, *bp, rbufp, 0);  in hash_access()
618 			off = hashp->BSIZE;  in hash_access()
621 			    __find_bigpair(hashp, rbufp, ndx, kp, size)) > 0)  in hash_access()
626 				    __find_last_page(hashp, &bufp))) {  in hash_access()
631 				rbufp = __get_buf(hashp, pageno, bufp, 0);  in hash_access()
640 				off = hashp->BSIZE;  in hash_access()
651 		if (__addel(hashp, rbufp, key, val)) {  in hash_access()
673 			if (__big_return(hashp, rbufp, ndx, val, 0))  in hash_access()
681 		if ((__delpair(hashp, rbufp, ndx)) ||  in hash_access()
682 		    (__addel(hashp, rbufp, key, val))) {  in hash_access()
688 		if (__delpair(hashp, rbufp, ndx))  in hash_access()
703 	HTAB *hashp;  in hash_seq()  local
706 	hashp = (HTAB *)dbp->internal;  in hash_seq()
708 		hashp->error = errno = EINVAL;  in hash_seq()
715 		hashp->cbucket = 0;  in hash_seq()
716 		hashp->cndx = 1;  in hash_seq()
717 		hashp->cpage = NULL;  in hash_seq()
718 	} else if (hashp->cbucket < 0) { /* R_NEXT */  in hash_seq()
723 		if (!(bufp = hashp->cpage)) {  in hash_seq()
724 			for (bucket = hashp->cbucket;  in hash_seq()
725 			    bucket <= hashp->MAX_BUCKET;  in hash_seq()
726 			    bucket++, hashp->cndx = 1) {  in hash_seq()
727 				bufp = __get_buf(hashp, bucket, NULL, 0);  in hash_seq()
730 				hashp->cpage = bufp;  in hash_seq()
735 			hashp->cbucket = bucket;  in hash_seq()
736 			if ((u_int32_t)hashp->cbucket > hashp->MAX_BUCKET) {  in hash_seq()
737 				hashp->cbucket = -1;  in hash_seq()
741 			bp = (u_int16_t *)hashp->cpage->page;  in hash_seq()
743 				hashp->cndx += 2;  in hash_seq()
744 				if (hashp->cndx > bp[0]) {  in hash_seq()
745 					hashp->cpage = NULL;  in hash_seq()
746 					hashp->cbucket++;  in hash_seq()
747 					hashp->cndx = 1;  in hash_seq()
757 		while (bp[hashp->cndx + 1] == OVFLPAGE) {  in hash_seq()
758 			bufp = hashp->cpage =  in hash_seq()
759 			    __get_buf(hashp, bp[hashp->cndx], bufp, 0);  in hash_seq()
763 			hashp->cndx = 1;  in hash_seq()
766 			hashp->cpage = NULL;  in hash_seq()
767 			++hashp->cbucket;  in hash_seq()
770 	ndx = hashp->cndx;  in hash_seq()
772 		if (__big_keydata(hashp, bufp, key, data, 1))  in hash_seq()
775 		if (hashp->cpage == NULL)  in hash_seq()
777 		key->data = (u_char *)hashp->cpage->page + bp[ndx];  in hash_seq()
778 		key->size = (ndx > 1 ? bp[ndx - 1] : hashp->BSIZE) - bp[ndx];  in hash_seq()
779 		data->data = (u_char *)hashp->cpage->page + bp[ndx + 1];  in hash_seq()
793 __expand_table(HTAB *hashp)  in __expand_table()  argument
801 	new_bucket = ++hashp->MAX_BUCKET;  in __expand_table()
802 	old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK);  in __expand_table()
804 	new_segnum = new_bucket >> hashp->SSHIFT;  in __expand_table()
807 	if (new_segnum >= hashp->nsegs) {  in __expand_table()
809 		if (new_segnum >= hashp->DSIZE) {  in __expand_table()
811 			dirsize = hashp->DSIZE * sizeof(SEGMENT *);  in __expand_table()
812 			if (!hash_realloc(&hashp->dir, dirsize, dirsize << 1))  in __expand_table()
814 			hashp->DSIZE = dirsize << 1;  in __expand_table()
816 		if ((hashp->dir[new_segnum] =  in __expand_table()
817 		    calloc(hashp->SGSIZE, sizeof(SEGMENT))) == NULL)  in __expand_table()
819 		hashp->exsegs++;  in __expand_table()
820 		hashp->nsegs++;  in __expand_table()
827 	spare_ndx = __log2(hashp->MAX_BUCKET + 1);  in __expand_table()
828 	if (spare_ndx > hashp->OVFL_POINT) {  in __expand_table()
829 		hashp->SPARES[spare_ndx] = hashp->SPARES[hashp->OVFL_POINT];  in __expand_table()
830 		hashp->OVFL_POINT = spare_ndx;  in __expand_table()
833 	if (new_bucket > hashp->HIGH_MASK) {  in __expand_table()
835 		hashp->LOW_MASK = hashp->HIGH_MASK;  in __expand_table()
836 		hashp->HIGH_MASK = new_bucket | hashp->LOW_MASK;  in __expand_table()
839 	return (__split_page(hashp, old_bucket, new_bucket));  in __expand_table()
861 __call_hash(HTAB *hashp, char *k, int len)  in __call_hash()  argument
865 	n = hashp->hash(k, len);  in __call_hash()
866 	bucket = n & hashp->HIGH_MASK;  in __call_hash()
867 	if (bucket > hashp->MAX_BUCKET)  in __call_hash()
868 		bucket = bucket & hashp->LOW_MASK;  in __call_hash()
878 alloc_segs(HTAB *hashp, int nsegs)  in alloc_segs()  argument
885 	if ((hashp->dir =  in alloc_segs()
886 	    calloc(hashp->DSIZE, sizeof(SEGMENT *))) == NULL) {  in alloc_segs()
888 		(void)hdestroy(hashp);  in alloc_segs()
892 	hashp->nsegs = nsegs;  in alloc_segs()
896 	if ((store = calloc(nsegs << hashp->SSHIFT, sizeof(SEGMENT))) == NULL) {  in alloc_segs()
898 		(void)hdestroy(hashp);  in alloc_segs()
903 		hashp->dir[i] = &store[i << hashp->SSHIFT];  in alloc_segs()
940 swap_header(HTAB *hashp)  in swap_header()  argument
945 	hdrp = &hashp->hdr;  in swap_header()