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