100 	HTAB *hashp;  in __hash_open()  local
110 	if (!(hashp = (HTAB *)calloc(1, sizeof(HTAB))))  in __hash_open()
112 	hashp->fp = -1;  in __hash_open()
120 	hashp->flags = flags;  in __hash_open()
123 		if ((hashp->fp = _open(file, flags | O_CLOEXEC, mode)) == -1)  in __hash_open()
125 		new_table = _fstat(hashp->fp, &statbuf) == 0 &&  in __hash_open()
131 		if (!(hashp = init_hash(hashp, file, info)))  in __hash_open()
136 			hashp->hash = info->hash;  in __hash_open()
138 			hashp->hash = __default_hash;  in __hash_open()
140 		hdrsize = _read(hashp->fp, &hashp->hdr, sizeof(HASHHDR));  in __hash_open()
142 		swap_header(hashp);  in __hash_open()
149 		if (hashp->MAGIC != HASHMAGIC)  in __hash_open()
152 		if (hashp->VERSION != HASHVERSION &&  in __hash_open()
153 		    hashp->VERSION != OLDHASHVERSION)  in __hash_open()
155 		if ((int32_t)hashp->hash(CHARKEY, sizeof(CHARKEY)) != hashp->H_CHARKEY)  in __hash_open()
162 		nsegs = howmany(hashp->MAX_BUCKET + 1, hashp->SGSIZE);  in __hash_open()
163 		if (alloc_segs(hashp, nsegs))  in __hash_open()
170 		bpages = (hashp->SPARES[hashp->OVFL_POINT] +  in __hash_open()
171 		    (hashp->BSIZE << BYTE_SHIFT) - 1) >>  in __hash_open()
172 		    (hashp->BSHIFT + BYTE_SHIFT);  in __hash_open()
174 		hashp->nmaps = bpages;  in __hash_open()
175 		(void)memset(&hashp->mapp[0], 0, bpages * sizeof(u_int32_t *));  in __hash_open()
180 		__buf_init(hashp, info->cachesize);  in __hash_open()
182 		__buf_init(hashp, DEF_BUFSIZE);  in __hash_open()
184 	hashp->new_file = new_table;  in __hash_open()
185 	hashp->save_file = file && (hashp->flags & O_RDWR);  in __hash_open()
186 	hashp->cbucket = -1;  in __hash_open()
189 		hdestroy(hashp);  in __hash_open()
193 	dbp->internal = hashp;  in __hash_open()
207 	    "TABLE POINTER   ", hashp,  in __hash_open()
208 	    "BUCKET SIZE     ", hashp->BSIZE,  in __hash_open()
209 	    "BUCKET SHIFT    ", hashp->BSHIFT,  in __hash_open()
210 	    "DIRECTORY SIZE  ", hashp->DSIZE,  in __hash_open()
211 	    "SEGMENT SIZE    ", hashp->SGSIZE,  in __hash_open()
212 	    "SEGMENT SHIFT   ", hashp->SSHIFT,  in __hash_open()
213 	    "FILL FACTOR     ", hashp->FFACTOR,  in __hash_open()
214 	    "MAX BUCKET      ", hashp->MAX_BUCKET,  in __hash_open()
215 	    "OVFL POINT	     ", hashp->OVFL_POINT,  in __hash_open()
216 	    "LAST FREED      ", hashp->LAST_FREED,  in __hash_open()
217 	    "HIGH MASK       ", hashp->HIGH_MASK,  in __hash_open()
218 	    "LOW  MASK       ", hashp->LOW_MASK,  in __hash_open()
219 	    "NSEGS           ", hashp->nsegs,  in __hash_open()
220 	    "NKEYS           ", hashp->NKEYS);  in __hash_open()
228 	if (hashp != NULL)  in __hash_open()
229 		(void)_close(hashp->fp);  in __hash_open()
232 	free(hashp);  in __hash_open()
240 	HTAB *hashp;  in hash_close()  local
246 	hashp = (HTAB *)dbp->internal;  in hash_close()
247 	retval = hdestroy(hashp);  in hash_close()
255 	HTAB *hashp;  in hash_fd()  local
260 	hashp = (HTAB *)dbp->internal;  in hash_fd()
261 	if (hashp->fp == -1) {  in hash_fd()
265 	return (hashp->fp);  in hash_fd()
270 init_hash(HTAB *hashp, const char *file, const HASHINFO *info)  in init_hash()  argument
276 	hashp->NKEYS = 0;  in init_hash()
277 	hashp->LORDER = BYTE_ORDER;  in init_hash()
278 	hashp->BSIZE = DEF_BUCKET_SIZE;  in init_hash()
279 	hashp->BSHIFT = DEF_BUCKET_SHIFT;  in init_hash()
280 	hashp->SGSIZE = DEF_SEGSIZE;  in init_hash()
281 	hashp->SSHIFT = DEF_SEGSIZE_SHIFT;  in init_hash()
282 	hashp->DSIZE = DEF_DIRSIZE;  in init_hash()
283 	hashp->FFACTOR = DEF_FFACTOR;  in init_hash()
284 	hashp->hash = __default_hash;  in init_hash()
285 	memset(hashp->SPARES, 0, sizeof(hashp->SPARES));  in init_hash()
286 	memset(hashp->BITMAPS, 0, sizeof (hashp->BITMAPS));  in init_hash()
292 		hashp->BSIZE = statbuf.st_blksize;  in init_hash()
293 		if (hashp->BSIZE > MAX_BSIZE)  in init_hash()
294 			hashp->BSIZE = MAX_BSIZE;  in init_hash()
295 		hashp->BSHIFT = __log2(hashp->BSIZE);  in init_hash()
301 			hashp->BSHIFT = __log2(info->bsize);  in init_hash()
302 			hashp->BSIZE = 1 << hashp->BSHIFT;  in init_hash()
303 			if (hashp->BSIZE > MAX_BSIZE) {  in init_hash()
309 			hashp->FFACTOR = info->ffactor;  in init_hash()
311 			hashp->hash = info->hash;  in init_hash()
320 			hashp->LORDER = info->lorder;  in init_hash()
324 	if (init_htab(hashp, nelem))  in init_hash()
327 		return (hashp);  in init_hash()
336 init_htab(HTAB *hashp, int nelem)  in init_htab()  argument
345 	nelem = (nelem - 1) / hashp->FFACTOR + 1;  in init_htab()
350 	hashp->SPARES[l2] = l2 + 1;  in init_htab()
351 	hashp->SPARES[l2 + 1] = l2 + 1;  in init_htab()
352 	hashp->OVFL_POINT = l2;  in init_htab()
353 	hashp->LAST_FREED = 2;  in init_htab()
356 	if (__ibitmap(hashp, OADDR_OF(l2, 1), l2 + 1, 0))  in init_htab()
359 	hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1;  in init_htab()
360 	hashp->HIGH_MASK = (nbuckets << 1) - 1;  in init_htab()
361 	hashp->HDRPAGES = ((MAX(sizeof(HASHHDR), MINHDRSIZE) - 1) >>  in init_htab()
362 	    hashp->BSHIFT) + 1;  in init_htab()
364 	nsegs = (nbuckets - 1) / hashp->SGSIZE + 1;  in init_htab()
367 	if (nsegs > hashp->DSIZE)  in init_htab()
368 		hashp->DSIZE = nsegs;  in init_htab()
369 	return (alloc_segs(hashp, nsegs));  in init_htab()
379 hdestroy(HTAB *hashp)  in hdestroy()  argument
393 	    hashp->NKEYS, hashp->MAX_BUCKET, hashp->nsegs);  in hdestroy()
397 		    "spares[%d] = %d\n", i, hashp->SPARES[i]);  in hdestroy()
403 	if (__buf_free(hashp, 1, hashp->save_file))  in hdestroy()
405 	if (hashp->dir) {  in hdestroy()
406 		free(*hashp->dir);	/* Free initial segments */  in hdestroy()
408 		while (hashp->exsegs--)  in hdestroy()
409 			free(hashp->dir[--hashp->nsegs]);  in hdestroy()
410 		free(hashp->dir);  in hdestroy()
412 	if (flush_meta(hashp) && !save_errno)  in hdestroy()
415 	for (i = 0; i < hashp->nmaps; i++)  in hdestroy()
416 		if (hashp->mapp[i])  in hdestroy()
417 			free(hashp->mapp[i]);  in hdestroy()
418 	if (hashp->tmp_key)  in hdestroy()
419 		free(hashp->tmp_key);  in hdestroy()
420 	if (hashp->tmp_buf)  in hdestroy()
421 		free(hashp->tmp_buf);  in hdestroy()
423 	if (hashp->fp != -1) {  in hdestroy()
424 		if (hashp->save_file)  in hdestroy()
425 			(void)_fsync(hashp->fp);  in hdestroy()
426 		(void)_close(hashp->fp);  in hdestroy()
429 	free(hashp);  in hdestroy()
447 	HTAB *hashp;  in hash_sync()  local
457 	hashp = (HTAB *)dbp->internal;  in hash_sync()
458 	if (!hashp->save_file)  in hash_sync()
460 	if (__buf_free(hashp, 0, 1) || flush_meta(hashp))  in hash_sync()
462 	if (hashp->fp != -1 && _fsync(hashp->fp) != 0)  in hash_sync()
464 	hashp->new_file = 0;  in hash_sync()
474 flush_meta(HTAB *hashp)  in flush_meta()  argument
482 	if (!hashp->save_file)  in flush_meta()
484 	hashp->MAGIC = HASHMAGIC;  in flush_meta()
485 	hashp->VERSION = HASHVERSION;  in flush_meta()
486 	hashp->H_CHARKEY = hashp->hash(CHARKEY, sizeof(CHARKEY));  in flush_meta()
488 	fp = hashp->fp;  in flush_meta()
489 	whdrp = &hashp->hdr;  in flush_meta()
492 	swap_header_copy(&hashp->hdr, whdrp);  in flush_meta()
499 			hashp->error = errno;  in flush_meta()
503 		if (hashp->mapp[i])  in flush_meta()
504 			if (__put_page(hashp, (char *)hashp->mapp[i],  in flush_meta()
505 				hashp->BITMAPS[i], 0, 1))  in flush_meta()
522 	HTAB *hashp;  in hash_get()  local
524 	hashp = (HTAB *)dbp->internal;  in hash_get()
526 		hashp->error = errno = EINVAL;  in hash_get()
529 	return (hash_access(hashp, HASH_GET, (DBT *)key, data));  in hash_get()
535 	HTAB *hashp;  in hash_put()  local
537 	hashp = (HTAB *)dbp->internal;  in hash_put()
539 		hashp->error = errno = EINVAL;  in hash_put()
542 	if ((hashp->flags & O_ACCMODE) == O_RDONLY) {  in hash_put()
543 		hashp->error = errno = EPERM;  in hash_put()
546 	return (hash_access(hashp, flag == R_NOOVERWRITE ?  in hash_put()
554 	HTAB *hashp;  in hash_delete()  local
556 	hashp = (HTAB *)dbp->internal;  in hash_delete()
558 		hashp->error = errno = EINVAL;  in hash_delete()
561 	if ((hashp->flags & O_ACCMODE) == O_RDONLY) {  in hash_delete()
562 		hashp->error = errno = EPERM;  in hash_delete()
565 	return (hash_access(hashp, HASH_DELETE, (DBT *)key, NULL));  in hash_delete()
572 hash_access(HTAB *hashp, ACTION action, DBT *key, DBT *val)  in hash_access()  argument
585 	off = hashp->BSIZE;  in hash_access()
588 	rbufp = __get_buf(hashp, __call_hash(hashp, kp, size), NULL, 0);  in hash_access()
608 			rbufp = __get_buf(hashp, *bp, rbufp, 0);  in hash_access()
617 			off = hashp->BSIZE;  in hash_access()
620 			    __find_bigpair(hashp, rbufp, ndx, kp, size)) > 0)  in hash_access()
625 				    __find_last_page(hashp, &bufp))) {  in hash_access()
630 				rbufp = __get_buf(hashp, pageno, bufp, 0);  in hash_access()
639 				off = hashp->BSIZE;  in hash_access()
650 		if (__addel(hashp, rbufp, key, val)) {  in hash_access()
672 			if (__big_return(hashp, rbufp, ndx, val, 0))  in hash_access()
680 		if ((__delpair(hashp, rbufp, ndx)) ||  in hash_access()
681 		    (__addel(hashp, rbufp, key, val))) {  in hash_access()
687 		if (__delpair(hashp, rbufp, ndx))  in hash_access()
702 	HTAB *hashp;  in hash_seq()  local
705 	hashp = (HTAB *)dbp->internal;  in hash_seq()
707 		hashp->error = errno = EINVAL;  in hash_seq()
713 	if ((hashp->cbucket < 0) || (flag == R_FIRST)) {  in hash_seq()
714 		hashp->cbucket = 0;  in hash_seq()
715 		hashp->cndx = 1;  in hash_seq()
716 		hashp->cpage = NULL;  in hash_seq()
720 		if (!(bufp = hashp->cpage)) {  in hash_seq()
721 			for (bucket = hashp->cbucket;  in hash_seq()
722 			    bucket <= hashp->MAX_BUCKET;  in hash_seq()
723 			    bucket++, hashp->cndx = 1) {  in hash_seq()
724 				bufp = __get_buf(hashp, bucket, NULL, 0);  in hash_seq()
727 				hashp->cpage = bufp;  in hash_seq()
732 			hashp->cbucket = bucket;  in hash_seq()
733 			if ((u_int32_t)hashp->cbucket > hashp->MAX_BUCKET) {  in hash_seq()
734 				hashp->cbucket = -1;  in hash_seq()
738 			bp = (u_int16_t *)hashp->cpage->page;  in hash_seq()
740 				hashp->cndx += 2;  in hash_seq()
741 				if (hashp->cndx > bp[0]) {  in hash_seq()
742 					hashp->cpage = NULL;  in hash_seq()
743 					hashp->cbucket++;  in hash_seq()
744 					hashp->cndx = 1;  in hash_seq()
754 		while (bp[hashp->cndx + 1] == OVFLPAGE) {  in hash_seq()
755 			bufp = hashp->cpage =  in hash_seq()
756 			    __get_buf(hashp, bp[hashp->cndx], bufp, 0);  in hash_seq()
760 			hashp->cndx = 1;  in hash_seq()
763 			hashp->cpage = NULL;  in hash_seq()
764 			++hashp->cbucket;  in hash_seq()
767 	ndx = hashp->cndx;  in hash_seq()
769 		if (__big_keydata(hashp, bufp, key, data, 1))  in hash_seq()
772 		if (hashp->cpage == NULL)  in hash_seq()
774 		key->data = (u_char *)hashp->cpage->page + bp[ndx];  in hash_seq()
775 		key->size = (ndx > 1 ? bp[ndx - 1] : hashp->BSIZE) - bp[ndx];  in hash_seq()
776 		data->data = (u_char *)hashp->cpage->page + bp[ndx + 1];  in hash_seq()
790 __expand_table(HTAB *hashp)  in __expand_table()  argument
798 	new_bucket = ++hashp->MAX_BUCKET;  in __expand_table()
799 	old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK);  in __expand_table()
801 	new_segnum = new_bucket >> hashp->SSHIFT;  in __expand_table()
804 	if (new_segnum >= hashp->nsegs) {  in __expand_table()
806 		if (new_segnum >= hashp->DSIZE) {  in __expand_table()
808 			dirsize = hashp->DSIZE * sizeof(SEGMENT *);  in __expand_table()
809 			if (!hash_realloc(&hashp->dir, dirsize, dirsize << 1))  in __expand_table()
811 			hashp->DSIZE = dirsize << 1;  in __expand_table()
813 		if ((hashp->dir[new_segnum] =  in __expand_table()
814 		    calloc(hashp->SGSIZE, sizeof(SEGMENT))) == NULL)  in __expand_table()
816 		hashp->exsegs++;  in __expand_table()
817 		hashp->nsegs++;  in __expand_table()
824 	spare_ndx = __log2(hashp->MAX_BUCKET + 1);  in __expand_table()
825 	if (spare_ndx > hashp->OVFL_POINT) {  in __expand_table()
826 		hashp->SPARES[spare_ndx] = hashp->SPARES[hashp->OVFL_POINT];  in __expand_table()
827 		hashp->OVFL_POINT = spare_ndx;  in __expand_table()
830 	if (new_bucket > hashp->HIGH_MASK) {  in __expand_table()
832 		hashp->LOW_MASK = hashp->HIGH_MASK;  in __expand_table()
833 		hashp->HIGH_MASK = new_bucket | hashp->LOW_MASK;  in __expand_table()
836 	return (__split_page(hashp, old_bucket, new_bucket));  in __expand_table()
858 __call_hash(HTAB *hashp, char *k, int len)  in __call_hash()  argument
862 	n = hashp->hash(k, len);  in __call_hash()
863 	bucket = n & hashp->HIGH_MASK;  in __call_hash()
864 	if (bucket > hashp->MAX_BUCKET)  in __call_hash()
865 		bucket = bucket & hashp->LOW_MASK;  in __call_hash()
875 alloc_segs(HTAB *hashp, int nsegs)  in alloc_segs()  argument
882 	if ((hashp->dir =  in alloc_segs()
883 	    calloc(hashp->DSIZE, sizeof(SEGMENT *))) == NULL) {  in alloc_segs()
885 		(void)hdestroy(hashp);  in alloc_segs()
889 	hashp->nsegs = nsegs;  in alloc_segs()
893 	if ((store = calloc(nsegs << hashp->SSHIFT, sizeof(SEGMENT))) == NULL) {  in alloc_segs()
895 		(void)hdestroy(hashp);  in alloc_segs()
900 		hashp->dir[i] = &store[i << hashp->SSHIFT];  in alloc_segs()
937 swap_header(HTAB *hashp)  in swap_header()  argument
942 	hdrp = &hashp->hdr;  in swap_header()