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