11573Srgrimes/*- 214287Spst * Copyright (c) 1990, 1993, 1994 31573Srgrimes * The Regents of the University of California. All rights reserved. 41573Srgrimes * 51573Srgrimes * This code is derived from software contributed to Berkeley by 61573Srgrimes * Margo Seltzer. 71573Srgrimes * 81573Srgrimes * Redistribution and use in source and binary forms, with or without 91573Srgrimes * modification, are permitted provided that the following conditions 101573Srgrimes * are met: 111573Srgrimes * 1. Redistributions of source code must retain the above copyright 121573Srgrimes * notice, this list of conditions and the following disclaimer. 131573Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 141573Srgrimes * notice, this list of conditions and the following disclaimer in the 151573Srgrimes * documentation and/or other materials provided with the distribution. 161573Srgrimes * 4. Neither the name of the University nor the names of its contributors 171573Srgrimes * may be used to endorse or promote products derived from this software 181573Srgrimes * without specific prior written permission. 191573Srgrimes * 201573Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 211573Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 221573Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 231573Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 241573Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 251573Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 261573Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 271573Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 281573Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 291573Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 301573Srgrimes * SUCH DAMAGE. 311573Srgrimes */ 321573Srgrimes 331573Srgrimes#if defined(LIBC_SCCS) && !defined(lint) 3414287Spststatic char sccsid[] = "@(#)hash.c 8.9 (Berkeley) 6/16/94"; 351573Srgrimes#endif /* LIBC_SCCS and not lint */ 3692889Sobrien#include <sys/cdefs.h> 3792889Sobrien__FBSDID("$FreeBSD$"); 381573Srgrimes 3971579Sdeischen#include "namespace.h" 401573Srgrimes#include <sys/param.h> 411573Srgrimes#include <sys/stat.h> 421573Srgrimes 431573Srgrimes#include <errno.h> 441573Srgrimes#include <fcntl.h> 451573Srgrimes#include <stdio.h> 461573Srgrimes#include <stdlib.h> 471573Srgrimes#include <string.h> 481573Srgrimes#include <unistd.h> 491573Srgrimes#ifdef DEBUG 501573Srgrimes#include <assert.h> 511573Srgrimes#endif 5271579Sdeischen#include "un-namespace.h" 531573Srgrimes 541573Srgrimes#include <db.h> 551573Srgrimes#include "hash.h" 561573Srgrimes#include "page.h" 571573Srgrimes#include "extern.h" 581573Srgrimes 5992905Sobrienstatic int alloc_segs(HTAB *, int); 6092905Sobrienstatic int flush_meta(HTAB *); 6192905Sobrienstatic int hash_access(HTAB *, ACTION, DBT *, DBT *); 6292905Sobrienstatic int hash_close(DB *); 6392905Sobrienstatic int hash_delete(const DB *, const DBT *, u_int32_t); 6492905Sobrienstatic int hash_fd(const DB *); 6592905Sobrienstatic int hash_get(const DB *, const DBT *, DBT *, u_int32_t); 6692905Sobrienstatic int hash_put(const DB *, DBT *, const DBT *, u_int32_t); 6792905Sobrienstatic void *hash_realloc(SEGMENT **, int, int); 6892905Sobrienstatic int hash_seq(const DB *, DBT *, DBT *, u_int32_t); 6992905Sobrienstatic int hash_sync(const DB *, u_int32_t); 7092905Sobrienstatic int hdestroy(HTAB *); 71169979Sdelphijstatic HTAB *init_hash(HTAB *, const char *, const HASHINFO *); 7292905Sobrienstatic int init_htab(HTAB *, int); 731573Srgrimes#if BYTE_ORDER == LITTLE_ENDIAN 7492905Sobrienstatic void swap_header(HTAB *); 7592905Sobrienstatic void swap_header_copy(HASHHDR *, HASHHDR *); 761573Srgrimes#endif 771573Srgrimes 781573Srgrimes/* Fast arithmetic, relying on powers of 2, */ 791573Srgrimes#define MOD(x, y) ((x) & ((y) - 1)) 801573Srgrimes 811573Srgrimes#define RETURN_ERROR(ERR, LOC) { save_errno = ERR; goto LOC; } 821573Srgrimes 831573Srgrimes/* Return values */ 841573Srgrimes#define SUCCESS (0) 851573Srgrimes#define ERROR (-1) 861573Srgrimes#define ABNORMAL (1) 871573Srgrimes 881573Srgrimes#ifdef HASH_STATISTICS 8914287Spstint hash_accesses, hash_collisions, hash_expansions, hash_overflows; 901573Srgrimes#endif 911573Srgrimes 921573Srgrimes/************************** INTERFACE ROUTINES ***************************/ 931573Srgrimes/* OPEN/CLOSE */ 941573Srgrimes 95189291Sdelphij/* ARGSUSED */ 96189291SdelphijDB * 97189291Sdelphij__hash_open(const char *file, int flags, int mode, 98189291Sdelphij const HASHINFO *info, /* Special directives for create */ 99189291Sdelphij int dflags) 1001573Srgrimes{ 1011573Srgrimes HTAB *hashp; 1021573Srgrimes struct stat statbuf; 1031573Srgrimes DB *dbp; 1041573Srgrimes int bpages, hdrsize, new_table, nsegs, save_errno; 1051573Srgrimes 1061573Srgrimes if ((flags & O_ACCMODE) == O_WRONLY) { 1071573Srgrimes errno = EINVAL; 1081573Srgrimes return (NULL); 1091573Srgrimes } 1101573Srgrimes 1111573Srgrimes if (!(hashp = (HTAB *)calloc(1, sizeof(HTAB)))) 1121573Srgrimes return (NULL); 1131573Srgrimes hashp->fp = -1; 1141573Srgrimes 1151573Srgrimes /* 1161573Srgrimes * Even if user wants write only, we need to be able to read 1171573Srgrimes * the actual file, so we need to open it read/write. But, the 1181573Srgrimes * field in the hashp structure needs to be accurate so that 1191573Srgrimes * we can check accesses. 1201573Srgrimes */ 1211573Srgrimes hashp->flags = flags; 1221573Srgrimes 1231573Srgrimes if (file) { 124254222Sjilles if ((hashp->fp = _open(file, flags | O_CLOEXEC, mode)) == -1) 1251573Srgrimes RETURN_ERROR(errno, error0); 126190495Sdelphij new_table = _fstat(hashp->fp, &statbuf) == 0 && 127190495Sdelphij statbuf.st_size == 0 && (flags & O_ACCMODE) != O_RDONLY; 128190495Sdelphij } else 129190495Sdelphij new_table = 1; 13014244Spst 1311573Srgrimes if (new_table) { 132169979Sdelphij if (!(hashp = init_hash(hashp, file, info))) 1331573Srgrimes RETURN_ERROR(errno, error1); 1341573Srgrimes } else { 1351573Srgrimes /* Table already exists */ 1361573Srgrimes if (info && info->hash) 1371573Srgrimes hashp->hash = info->hash; 1381573Srgrimes else 1391573Srgrimes hashp->hash = __default_hash; 1401573Srgrimes 14156698Sjasone hdrsize = _read(hashp->fp, &hashp->hdr, sizeof(HASHHDR)); 1421573Srgrimes#if BYTE_ORDER == LITTLE_ENDIAN 1431573Srgrimes swap_header(hashp); 1441573Srgrimes#endif 1451573Srgrimes if (hdrsize == -1) 1461573Srgrimes RETURN_ERROR(errno, error1); 1471573Srgrimes if (hdrsize != sizeof(HASHHDR)) 1481573Srgrimes RETURN_ERROR(EFTYPE, error1); 1491573Srgrimes /* Verify file type, versions and hash function */ 1501573Srgrimes if (hashp->MAGIC != HASHMAGIC) 1511573Srgrimes RETURN_ERROR(EFTYPE, error1); 1521573Srgrimes#define OLDHASHVERSION 1 1531573Srgrimes if (hashp->VERSION != HASHVERSION && 1541573Srgrimes hashp->VERSION != OLDHASHVERSION) 1551573Srgrimes RETURN_ERROR(EFTYPE, error1); 156190484Sdelphij if ((int32_t)hashp->hash(CHARKEY, sizeof(CHARKEY)) != hashp->H_CHARKEY) 1571573Srgrimes RETURN_ERROR(EFTYPE, error1); 1581573Srgrimes /* 1591573Srgrimes * Figure out how many segments we need. Max_Bucket is the 1601573Srgrimes * maximum bucket number, so the number of buckets is 1611573Srgrimes * max_bucket + 1. 1621573Srgrimes */ 1631573Srgrimes nsegs = (hashp->MAX_BUCKET + 1 + hashp->SGSIZE - 1) / 1641573Srgrimes hashp->SGSIZE; 1651573Srgrimes if (alloc_segs(hashp, nsegs)) 1661573Srgrimes /* 1671573Srgrimes * If alloc_segs fails, table will have been destroyed 1681573Srgrimes * and errno will have been set. 1691573Srgrimes */ 1701573Srgrimes return (NULL); 1711573Srgrimes /* Read in bitmaps */ 1721573Srgrimes bpages = (hashp->SPARES[hashp->OVFL_POINT] + 1731573Srgrimes (hashp->BSIZE << BYTE_SHIFT) - 1) >> 1741573Srgrimes (hashp->BSHIFT + BYTE_SHIFT); 1751573Srgrimes 1761573Srgrimes hashp->nmaps = bpages; 17714287Spst (void)memset(&hashp->mapp[0], 0, bpages * sizeof(u_int32_t *)); 1781573Srgrimes } 1791573Srgrimes 1801573Srgrimes /* Initialize Buffer Manager */ 1811573Srgrimes if (info && info->cachesize) 1821573Srgrimes __buf_init(hashp, info->cachesize); 1831573Srgrimes else 1841573Srgrimes __buf_init(hashp, DEF_BUFSIZE); 1851573Srgrimes 1861573Srgrimes hashp->new_file = new_table; 1871573Srgrimes hashp->save_file = file && (hashp->flags & O_RDWR); 1881573Srgrimes hashp->cbucket = -1; 1891573Srgrimes if (!(dbp = (DB *)malloc(sizeof(DB)))) { 1901573Srgrimes save_errno = errno; 1911573Srgrimes hdestroy(hashp); 1921573Srgrimes errno = save_errno; 1931573Srgrimes return (NULL); 1941573Srgrimes } 1951573Srgrimes dbp->internal = hashp; 1961573Srgrimes dbp->close = hash_close; 1971573Srgrimes dbp->del = hash_delete; 1981573Srgrimes dbp->fd = hash_fd; 1991573Srgrimes dbp->get = hash_get; 2001573Srgrimes dbp->put = hash_put; 2011573Srgrimes dbp->seq = hash_seq; 2021573Srgrimes dbp->sync = hash_sync; 2031573Srgrimes dbp->type = DB_HASH; 2041573Srgrimes 2051573Srgrimes#ifdef DEBUG 2061573Srgrimes (void)fprintf(stderr, 207135024Skuriyama"%s\n%s%p\n%s%d\n%s%d\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", 2081573Srgrimes "init_htab:", 2091573Srgrimes "TABLE POINTER ", hashp, 2101573Srgrimes "BUCKET SIZE ", hashp->BSIZE, 2111573Srgrimes "BUCKET SHIFT ", hashp->BSHIFT, 2121573Srgrimes "DIRECTORY SIZE ", hashp->DSIZE, 2131573Srgrimes "SEGMENT SIZE ", hashp->SGSIZE, 2141573Srgrimes "SEGMENT SHIFT ", hashp->SSHIFT, 2151573Srgrimes "FILL FACTOR ", hashp->FFACTOR, 2161573Srgrimes "MAX BUCKET ", hashp->MAX_BUCKET, 2171573Srgrimes "OVFL POINT ", hashp->OVFL_POINT, 2181573Srgrimes "LAST FREED ", hashp->LAST_FREED, 2191573Srgrimes "HIGH MASK ", hashp->HIGH_MASK, 2201573Srgrimes "LOW MASK ", hashp->LOW_MASK, 2211573Srgrimes "NSEGS ", hashp->nsegs, 2221573Srgrimes "NKEYS ", hashp->NKEYS); 2231573Srgrimes#endif 2241573Srgrimes#ifdef HASH_STATISTICS 2251573Srgrimes hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0; 2261573Srgrimes#endif 2271573Srgrimes return (dbp); 2281573Srgrimes 2291573Srgrimeserror1: 2301573Srgrimes if (hashp != NULL) 23156698Sjasone (void)_close(hashp->fp); 2321573Srgrimes 2331573Srgrimeserror0: 2341573Srgrimes free(hashp); 2351573Srgrimes errno = save_errno; 2361573Srgrimes return (NULL); 2371573Srgrimes} 2381573Srgrimes 2391573Srgrimesstatic int 240189291Sdelphijhash_close(DB *dbp) 2411573Srgrimes{ 2421573Srgrimes HTAB *hashp; 2431573Srgrimes int retval; 2441573Srgrimes 2451573Srgrimes if (!dbp) 2461573Srgrimes return (ERROR); 2471573Srgrimes 2481573Srgrimes hashp = (HTAB *)dbp->internal; 2491573Srgrimes retval = hdestroy(hashp); 2501573Srgrimes free(dbp); 2511573Srgrimes return (retval); 2521573Srgrimes} 2531573Srgrimes 2541573Srgrimesstatic int 255189291Sdelphijhash_fd(const DB *dbp) 2561573Srgrimes{ 2571573Srgrimes HTAB *hashp; 2581573Srgrimes 2591573Srgrimes if (!dbp) 2601573Srgrimes return (ERROR); 2611573Srgrimes 2621573Srgrimes hashp = (HTAB *)dbp->internal; 2631573Srgrimes if (hashp->fp == -1) { 2641573Srgrimes errno = ENOENT; 2651573Srgrimes return (-1); 2661573Srgrimes } 2671573Srgrimes return (hashp->fp); 2681573Srgrimes} 2691573Srgrimes 2701573Srgrimes/************************** LOCAL CREATION ROUTINES **********************/ 2711573Srgrimesstatic HTAB * 272189291Sdelphijinit_hash(HTAB *hashp, const char *file, const HASHINFO *info) 2731573Srgrimes{ 2741573Srgrimes struct stat statbuf; 2751573Srgrimes int nelem; 2761573Srgrimes 2771573Srgrimes nelem = 1; 2781573Srgrimes hashp->NKEYS = 0; 2791573Srgrimes hashp->LORDER = BYTE_ORDER; 2801573Srgrimes hashp->BSIZE = DEF_BUCKET_SIZE; 2811573Srgrimes hashp->BSHIFT = DEF_BUCKET_SHIFT; 2821573Srgrimes hashp->SGSIZE = DEF_SEGSIZE; 2831573Srgrimes hashp->SSHIFT = DEF_SEGSIZE_SHIFT; 2841573Srgrimes hashp->DSIZE = DEF_DIRSIZE; 2851573Srgrimes hashp->FFACTOR = DEF_FFACTOR; 2861573Srgrimes hashp->hash = __default_hash; 2871573Srgrimes memset(hashp->SPARES, 0, sizeof(hashp->SPARES)); 2881573Srgrimes memset(hashp->BITMAPS, 0, sizeof (hashp->BITMAPS)); 2891573Srgrimes 2901573Srgrimes /* Fix bucket size to be optimal for file system */ 2911573Srgrimes if (file != NULL) { 2921573Srgrimes if (stat(file, &statbuf)) 2931573Srgrimes return (NULL); 2941573Srgrimes hashp->BSIZE = statbuf.st_blksize; 295206178Savg if (hashp->BSIZE > MAX_BSIZE) 296206178Savg hashp->BSIZE = MAX_BSIZE; 2971573Srgrimes hashp->BSHIFT = __log2(hashp->BSIZE); 2981573Srgrimes } 2991573Srgrimes 3001573Srgrimes if (info) { 3011573Srgrimes if (info->bsize) { 3021573Srgrimes /* Round pagesize up to power of 2 */ 3031573Srgrimes hashp->BSHIFT = __log2(info->bsize); 3041573Srgrimes hashp->BSIZE = 1 << hashp->BSHIFT; 3051573Srgrimes if (hashp->BSIZE > MAX_BSIZE) { 3061573Srgrimes errno = EINVAL; 3071573Srgrimes return (NULL); 3081573Srgrimes } 3091573Srgrimes } 3101573Srgrimes if (info->ffactor) 3111573Srgrimes hashp->FFACTOR = info->ffactor; 3121573Srgrimes if (info->hash) 3131573Srgrimes hashp->hash = info->hash; 3141573Srgrimes if (info->nelem) 3151573Srgrimes nelem = info->nelem; 3161573Srgrimes if (info->lorder) { 3171573Srgrimes if (info->lorder != BIG_ENDIAN && 3181573Srgrimes info->lorder != LITTLE_ENDIAN) { 3191573Srgrimes errno = EINVAL; 3201573Srgrimes return (NULL); 3211573Srgrimes } 3221573Srgrimes hashp->LORDER = info->lorder; 3231573Srgrimes } 3241573Srgrimes } 3251573Srgrimes /* init_htab should destroy the table and set errno if it fails */ 3261573Srgrimes if (init_htab(hashp, nelem)) 3271573Srgrimes return (NULL); 3281573Srgrimes else 3291573Srgrimes return (hashp); 3301573Srgrimes} 3311573Srgrimes/* 3321573Srgrimes * This calls alloc_segs which may run out of memory. Alloc_segs will destroy 3331573Srgrimes * the table and set errno, so we just pass the error information along. 3341573Srgrimes * 3351573Srgrimes * Returns 0 on No Error 3361573Srgrimes */ 3371573Srgrimesstatic int 338189291Sdelphijinit_htab(HTAB *hashp, int nelem) 3391573Srgrimes{ 340190489Sdelphij int nbuckets, nsegs, l2; 3411573Srgrimes 3421573Srgrimes /* 3431573Srgrimes * Divide number of elements by the fill factor and determine a 3441573Srgrimes * desired number of buckets. Allocate space for the next greater 3451573Srgrimes * power of two number of buckets. 3461573Srgrimes */ 3471573Srgrimes nelem = (nelem - 1) / hashp->FFACTOR + 1; 3481573Srgrimes 3491573Srgrimes l2 = __log2(MAX(nelem, 2)); 3501573Srgrimes nbuckets = 1 << l2; 3511573Srgrimes 3521573Srgrimes hashp->SPARES[l2] = l2 + 1; 3531573Srgrimes hashp->SPARES[l2 + 1] = l2 + 1; 3541573Srgrimes hashp->OVFL_POINT = l2; 3551573Srgrimes hashp->LAST_FREED = 2; 3561573Srgrimes 3571573Srgrimes /* First bitmap page is at: splitpoint l2 page offset 1 */ 35814287Spst if (__ibitmap(hashp, OADDR_OF(l2, 1), l2 + 1, 0)) 3591573Srgrimes return (-1); 3601573Srgrimes 3611573Srgrimes hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1; 3621573Srgrimes hashp->HIGH_MASK = (nbuckets << 1) - 1; 3631573Srgrimes hashp->HDRPAGES = ((MAX(sizeof(HASHHDR), MINHDRSIZE) - 1) >> 3641573Srgrimes hashp->BSHIFT) + 1; 3651573Srgrimes 3661573Srgrimes nsegs = (nbuckets - 1) / hashp->SGSIZE + 1; 3671573Srgrimes nsegs = 1 << __log2(nsegs); 3681573Srgrimes 3691573Srgrimes if (nsegs > hashp->DSIZE) 3701573Srgrimes hashp->DSIZE = nsegs; 3711573Srgrimes return (alloc_segs(hashp, nsegs)); 3721573Srgrimes} 3731573Srgrimes 3741573Srgrimes/********************** DESTROY/CLOSE ROUTINES ************************/ 3751573Srgrimes 3761573Srgrimes/* 3771573Srgrimes * Flushes any changes to the file if necessary and destroys the hashp 3781573Srgrimes * structure, freeing all allocated space. 3791573Srgrimes */ 3801573Srgrimesstatic int 381189291Sdelphijhdestroy(HTAB *hashp) 3821573Srgrimes{ 3831573Srgrimes int i, save_errno; 3841573Srgrimes 3851573Srgrimes save_errno = 0; 3861573Srgrimes 3871573Srgrimes#ifdef HASH_STATISTICS 3881573Srgrimes (void)fprintf(stderr, "hdestroy: accesses %ld collisions %ld\n", 3891573Srgrimes hash_accesses, hash_collisions); 3901573Srgrimes (void)fprintf(stderr, "hdestroy: expansions %ld\n", 3911573Srgrimes hash_expansions); 3921573Srgrimes (void)fprintf(stderr, "hdestroy: overflows %ld\n", 3931573Srgrimes hash_overflows); 3941573Srgrimes (void)fprintf(stderr, "keys %ld maxp %d segmentcount %d\n", 3951573Srgrimes hashp->NKEYS, hashp->MAX_BUCKET, hashp->nsegs); 3961573Srgrimes 3971573Srgrimes for (i = 0; i < NCACHED; i++) 3981573Srgrimes (void)fprintf(stderr, 3991573Srgrimes "spares[%d] = %d\n", i, hashp->SPARES[i]); 4001573Srgrimes#endif 4011573Srgrimes /* 4021573Srgrimes * Call on buffer manager to free buffers, and if required, 4031573Srgrimes * write them to disk. 4041573Srgrimes */ 4051573Srgrimes if (__buf_free(hashp, 1, hashp->save_file)) 4061573Srgrimes save_errno = errno; 4071573Srgrimes if (hashp->dir) { 4081573Srgrimes free(*hashp->dir); /* Free initial segments */ 4091573Srgrimes /* Free extra segments */ 4101573Srgrimes while (hashp->exsegs--) 4111573Srgrimes free(hashp->dir[--hashp->nsegs]); 4121573Srgrimes free(hashp->dir); 4131573Srgrimes } 4141573Srgrimes if (flush_meta(hashp) && !save_errno) 4151573Srgrimes save_errno = errno; 4161573Srgrimes /* Free Bigmaps */ 4171573Srgrimes for (i = 0; i < hashp->nmaps; i++) 4181573Srgrimes if (hashp->mapp[i]) 4191573Srgrimes free(hashp->mapp[i]); 420190496Sdelphij if (hashp->tmp_key) 421190496Sdelphij free(hashp->tmp_key); 422190496Sdelphij if (hashp->tmp_buf) 423190496Sdelphij free(hashp->tmp_buf); 4241573Srgrimes 4251573Srgrimes if (hashp->fp != -1) 42656698Sjasone (void)_close(hashp->fp); 4271573Srgrimes 4281573Srgrimes free(hashp); 4291573Srgrimes 4301573Srgrimes if (save_errno) { 4311573Srgrimes errno = save_errno; 4321573Srgrimes return (ERROR); 4331573Srgrimes } 4341573Srgrimes return (SUCCESS); 4351573Srgrimes} 4361573Srgrimes/* 4371573Srgrimes * Write modified pages to disk 4381573Srgrimes * 4391573Srgrimes * Returns: 4401573Srgrimes * 0 == OK 4411573Srgrimes * -1 ERROR 4421573Srgrimes */ 4431573Srgrimesstatic int 444189291Sdelphijhash_sync(const DB *dbp, u_int32_t flags) 4451573Srgrimes{ 4461573Srgrimes HTAB *hashp; 4471573Srgrimes 4481573Srgrimes if (flags != 0) { 4491573Srgrimes errno = EINVAL; 4501573Srgrimes return (ERROR); 4511573Srgrimes } 4521573Srgrimes 4531573Srgrimes if (!dbp) 4541573Srgrimes return (ERROR); 4551573Srgrimes 4561573Srgrimes hashp = (HTAB *)dbp->internal; 4571573Srgrimes if (!hashp->save_file) 4581573Srgrimes return (0); 4591573Srgrimes if (__buf_free(hashp, 0, 1) || flush_meta(hashp)) 4601573Srgrimes return (ERROR); 4611573Srgrimes hashp->new_file = 0; 4621573Srgrimes return (0); 4631573Srgrimes} 4641573Srgrimes 4651573Srgrimes/* 4661573Srgrimes * Returns: 4671573Srgrimes * 0 == OK 4681573Srgrimes * -1 indicates that errno should be set 4691573Srgrimes */ 4701573Srgrimesstatic int 471189291Sdelphijflush_meta(HTAB *hashp) 4721573Srgrimes{ 4731573Srgrimes HASHHDR *whdrp; 4741573Srgrimes#if BYTE_ORDER == LITTLE_ENDIAN 4751573Srgrimes HASHHDR whdr; 4761573Srgrimes#endif 4771573Srgrimes int fp, i, wsize; 4781573Srgrimes 4791573Srgrimes if (!hashp->save_file) 4801573Srgrimes return (0); 4811573Srgrimes hashp->MAGIC = HASHMAGIC; 4821573Srgrimes hashp->VERSION = HASHVERSION; 4831573Srgrimes hashp->H_CHARKEY = hashp->hash(CHARKEY, sizeof(CHARKEY)); 4841573Srgrimes 4851573Srgrimes fp = hashp->fp; 4861573Srgrimes whdrp = &hashp->hdr; 4871573Srgrimes#if BYTE_ORDER == LITTLE_ENDIAN 4881573Srgrimes whdrp = &whdr; 4891573Srgrimes swap_header_copy(&hashp->hdr, whdrp); 4901573Srgrimes#endif 491190486Sdelphij if ((wsize = pwrite(fp, whdrp, sizeof(HASHHDR), (off_t)0)) == -1) 4921573Srgrimes return (-1); 4931573Srgrimes else 4941573Srgrimes if (wsize != sizeof(HASHHDR)) { 4951573Srgrimes errno = EFTYPE; 49613545Sjulian hashp->error = errno; 4971573Srgrimes return (-1); 4981573Srgrimes } 4991573Srgrimes for (i = 0; i < NCACHED; i++) 5001573Srgrimes if (hashp->mapp[i]) 5011573Srgrimes if (__put_page(hashp, (char *)hashp->mapp[i], 5021573Srgrimes hashp->BITMAPS[i], 0, 1)) 5031573Srgrimes return (-1); 5041573Srgrimes return (0); 5051573Srgrimes} 5061573Srgrimes 5071573Srgrimes/*******************************SEARCH ROUTINES *****************************/ 5081573Srgrimes/* 5091573Srgrimes * All the access routines return 5101573Srgrimes * 5111573Srgrimes * Returns: 5121573Srgrimes * 0 on SUCCESS 5131573Srgrimes * 1 to indicate an external ERROR (i.e. key not found, etc) 5141573Srgrimes * -1 to indicate an internal ERROR (i.e. out of memory, etc) 5151573Srgrimes */ 5161573Srgrimesstatic int 517189291Sdelphijhash_get(const DB *dbp, const DBT *key, DBT *data, u_int32_t flag) 5181573Srgrimes{ 5191573Srgrimes HTAB *hashp; 5201573Srgrimes 5211573Srgrimes hashp = (HTAB *)dbp->internal; 5221573Srgrimes if (flag) { 52313545Sjulian hashp->error = errno = EINVAL; 5241573Srgrimes return (ERROR); 5251573Srgrimes } 5261573Srgrimes return (hash_access(hashp, HASH_GET, (DBT *)key, data)); 5271573Srgrimes} 5281573Srgrimes 5291573Srgrimesstatic int 530189291Sdelphijhash_put(const DB *dbp, DBT *key, const DBT *data, u_int32_t flag) 5311573Srgrimes{ 5321573Srgrimes HTAB *hashp; 5331573Srgrimes 5341573Srgrimes hashp = (HTAB *)dbp->internal; 5351573Srgrimes if (flag && flag != R_NOOVERWRITE) { 536190491Sdelphij hashp->error = errno = EINVAL; 5371573Srgrimes return (ERROR); 5381573Srgrimes } 5391573Srgrimes if ((hashp->flags & O_ACCMODE) == O_RDONLY) { 54013545Sjulian hashp->error = errno = EPERM; 5411573Srgrimes return (ERROR); 5421573Srgrimes } 5431573Srgrimes return (hash_access(hashp, flag == R_NOOVERWRITE ? 5441573Srgrimes HASH_PUTNEW : HASH_PUT, (DBT *)key, (DBT *)data)); 5451573Srgrimes} 5461573Srgrimes 5471573Srgrimesstatic int 548189291Sdelphijhash_delete(const DB *dbp, const DBT *key, 549189291Sdelphij u_int32_t flag) /* Ignored */ 5501573Srgrimes{ 5511573Srgrimes HTAB *hashp; 5521573Srgrimes 5531573Srgrimes hashp = (HTAB *)dbp->internal; 5541573Srgrimes if (flag && flag != R_CURSOR) { 55513545Sjulian hashp->error = errno = EINVAL; 5561573Srgrimes return (ERROR); 5571573Srgrimes } 5581573Srgrimes if ((hashp->flags & O_ACCMODE) == O_RDONLY) { 55913545Sjulian hashp->error = errno = EPERM; 5601573Srgrimes return (ERROR); 5611573Srgrimes } 5621573Srgrimes return (hash_access(hashp, HASH_DELETE, (DBT *)key, NULL)); 5631573Srgrimes} 5641573Srgrimes 5651573Srgrimes/* 5661573Srgrimes * Assume that hashp has been set in wrapper routine. 5671573Srgrimes */ 5681573Srgrimesstatic int 569189291Sdelphijhash_access(HTAB *hashp, ACTION action, DBT *key, DBT *val) 5701573Srgrimes{ 57192889Sobrien BUFHEAD *rbufp; 5721573Srgrimes BUFHEAD *bufp, *save_bufp; 57392889Sobrien u_int16_t *bp; 57492889Sobrien int n, ndx, off, size; 57592889Sobrien char *kp; 57614287Spst u_int16_t pageno; 5771573Srgrimes 5781573Srgrimes#ifdef HASH_STATISTICS 5791573Srgrimes hash_accesses++; 5801573Srgrimes#endif 5811573Srgrimes 5821573Srgrimes off = hashp->BSIZE; 5831573Srgrimes size = key->size; 5841573Srgrimes kp = (char *)key->data; 5851573Srgrimes rbufp = __get_buf(hashp, __call_hash(hashp, kp, size), NULL, 0); 5861573Srgrimes if (!rbufp) 5871573Srgrimes return (ERROR); 5881573Srgrimes save_bufp = rbufp; 5891573Srgrimes 5901573Srgrimes /* Pin the bucket chain */ 5911573Srgrimes rbufp->flags |= BUF_PIN; 59214287Spst for (bp = (u_int16_t *)rbufp->page, n = *bp++, ndx = 1; ndx < n;) 5931573Srgrimes if (bp[1] >= REAL_KEY) { 5941573Srgrimes /* Real key/data pair */ 5951573Srgrimes if (size == off - *bp && 5961573Srgrimes memcmp(kp, rbufp->page + *bp, size) == 0) 5971573Srgrimes goto found; 5981573Srgrimes off = bp[1]; 5991573Srgrimes#ifdef HASH_STATISTICS 6001573Srgrimes hash_collisions++; 6011573Srgrimes#endif 6021573Srgrimes bp += 2; 6031573Srgrimes ndx += 2; 6041573Srgrimes } else if (bp[1] == OVFLPAGE) { 6051573Srgrimes rbufp = __get_buf(hashp, *bp, rbufp, 0); 6061573Srgrimes if (!rbufp) { 6071573Srgrimes save_bufp->flags &= ~BUF_PIN; 6081573Srgrimes return (ERROR); 6091573Srgrimes } 6101573Srgrimes /* FOR LOOP INIT */ 61114287Spst bp = (u_int16_t *)rbufp->page; 6121573Srgrimes n = *bp++; 6131573Srgrimes ndx = 1; 6141573Srgrimes off = hashp->BSIZE; 6151573Srgrimes } else if (bp[1] < REAL_KEY) { 6161573Srgrimes if ((ndx = 6171573Srgrimes __find_bigpair(hashp, rbufp, ndx, kp, size)) > 0) 6181573Srgrimes goto found; 6191573Srgrimes if (ndx == -2) { 6201573Srgrimes bufp = rbufp; 6211573Srgrimes if (!(pageno = 6221573Srgrimes __find_last_page(hashp, &bufp))) { 6231573Srgrimes ndx = 0; 6241573Srgrimes rbufp = bufp; 6251573Srgrimes break; /* FOR */ 6261573Srgrimes } 6271573Srgrimes rbufp = __get_buf(hashp, pageno, bufp, 0); 6281573Srgrimes if (!rbufp) { 6291573Srgrimes save_bufp->flags &= ~BUF_PIN; 6301573Srgrimes return (ERROR); 6311573Srgrimes } 6321573Srgrimes /* FOR LOOP INIT */ 63314287Spst bp = (u_int16_t *)rbufp->page; 6341573Srgrimes n = *bp++; 6351573Srgrimes ndx = 1; 6361573Srgrimes off = hashp->BSIZE; 6371573Srgrimes } else { 6381573Srgrimes save_bufp->flags &= ~BUF_PIN; 6391573Srgrimes return (ERROR); 6401573Srgrimes } 6411573Srgrimes } 6421573Srgrimes 6431573Srgrimes /* Not found */ 6441573Srgrimes switch (action) { 6451573Srgrimes case HASH_PUT: 6461573Srgrimes case HASH_PUTNEW: 6471573Srgrimes if (__addel(hashp, rbufp, key, val)) { 6481573Srgrimes save_bufp->flags &= ~BUF_PIN; 6491573Srgrimes return (ERROR); 6501573Srgrimes } else { 6511573Srgrimes save_bufp->flags &= ~BUF_PIN; 6521573Srgrimes return (SUCCESS); 6531573Srgrimes } 6541573Srgrimes case HASH_GET: 6551573Srgrimes case HASH_DELETE: 6561573Srgrimes default: 6571573Srgrimes save_bufp->flags &= ~BUF_PIN; 6581573Srgrimes return (ABNORMAL); 6591573Srgrimes } 6601573Srgrimes 6611573Srgrimesfound: 6621573Srgrimes switch (action) { 6631573Srgrimes case HASH_PUTNEW: 6641573Srgrimes save_bufp->flags &= ~BUF_PIN; 6651573Srgrimes return (ABNORMAL); 6661573Srgrimes case HASH_GET: 66714287Spst bp = (u_int16_t *)rbufp->page; 6681573Srgrimes if (bp[ndx + 1] < REAL_KEY) { 6691573Srgrimes if (__big_return(hashp, rbufp, ndx, val, 0)) 6701573Srgrimes return (ERROR); 6711573Srgrimes } else { 6721573Srgrimes val->data = (u_char *)rbufp->page + (int)bp[ndx + 1]; 6731573Srgrimes val->size = bp[ndx] - bp[ndx + 1]; 6741573Srgrimes } 6751573Srgrimes break; 6761573Srgrimes case HASH_PUT: 6771573Srgrimes if ((__delpair(hashp, rbufp, ndx)) || 6781573Srgrimes (__addel(hashp, rbufp, key, val))) { 6791573Srgrimes save_bufp->flags &= ~BUF_PIN; 6801573Srgrimes return (ERROR); 6811573Srgrimes } 6821573Srgrimes break; 6831573Srgrimes case HASH_DELETE: 6841573Srgrimes if (__delpair(hashp, rbufp, ndx)) 6851573Srgrimes return (ERROR); 6861573Srgrimes break; 6871573Srgrimes default: 6881573Srgrimes abort(); 6891573Srgrimes } 6901573Srgrimes save_bufp->flags &= ~BUF_PIN; 6911573Srgrimes return (SUCCESS); 6921573Srgrimes} 6931573Srgrimes 6941573Srgrimesstatic int 695189291Sdelphijhash_seq(const DB *dbp, DBT *key, DBT *data, u_int32_t flag) 6961573Srgrimes{ 69792889Sobrien u_int32_t bucket; 69892889Sobrien BUFHEAD *bufp; 6991573Srgrimes HTAB *hashp; 70014287Spst u_int16_t *bp, ndx; 7011573Srgrimes 7021573Srgrimes hashp = (HTAB *)dbp->internal; 7031573Srgrimes if (flag && flag != R_FIRST && flag != R_NEXT) { 70413545Sjulian hashp->error = errno = EINVAL; 7051573Srgrimes return (ERROR); 7061573Srgrimes } 7071573Srgrimes#ifdef HASH_STATISTICS 7081573Srgrimes hash_accesses++; 7091573Srgrimes#endif 7101573Srgrimes if ((hashp->cbucket < 0) || (flag == R_FIRST)) { 7111573Srgrimes hashp->cbucket = 0; 7121573Srgrimes hashp->cndx = 1; 7131573Srgrimes hashp->cpage = NULL; 7141573Srgrimes } 715196525Sdelphijnext_bucket: 7161573Srgrimes for (bp = NULL; !bp || !bp[0]; ) { 7171573Srgrimes if (!(bufp = hashp->cpage)) { 7181573Srgrimes for (bucket = hashp->cbucket; 7191573Srgrimes bucket <= hashp->MAX_BUCKET; 7201573Srgrimes bucket++, hashp->cndx = 1) { 7211573Srgrimes bufp = __get_buf(hashp, bucket, NULL, 0); 7221573Srgrimes if (!bufp) 7231573Srgrimes return (ERROR); 7241573Srgrimes hashp->cpage = bufp; 72514287Spst bp = (u_int16_t *)bufp->page; 7261573Srgrimes if (bp[0]) 7271573Srgrimes break; 7281573Srgrimes } 7291573Srgrimes hashp->cbucket = bucket; 730190484Sdelphij if ((u_int32_t)hashp->cbucket > hashp->MAX_BUCKET) { 7311573Srgrimes hashp->cbucket = -1; 7321573Srgrimes return (ABNORMAL); 7331573Srgrimes } 734190491Sdelphij } else { 73514287Spst bp = (u_int16_t *)hashp->cpage->page; 736196525Sdelphij if (flag == R_NEXT || flag == 0) { 737190491Sdelphij hashp->cndx += 2; 738190491Sdelphij if (hashp->cndx > bp[0]) { 739190491Sdelphij hashp->cpage = NULL; 740190491Sdelphij hashp->cbucket++; 741190491Sdelphij hashp->cndx = 1; 742190491Sdelphij goto next_bucket; 743190491Sdelphij } 744190491Sdelphij } 745190491Sdelphij } 7461573Srgrimes 7471573Srgrimes#ifdef DEBUG 7481573Srgrimes assert(bp); 7491573Srgrimes assert(bufp); 7501573Srgrimes#endif 7511573Srgrimes while (bp[hashp->cndx + 1] == OVFLPAGE) { 7521573Srgrimes bufp = hashp->cpage = 7531573Srgrimes __get_buf(hashp, bp[hashp->cndx], bufp, 0); 7541573Srgrimes if (!bufp) 7551573Srgrimes return (ERROR); 75614287Spst bp = (u_int16_t *)(bufp->page); 7571573Srgrimes hashp->cndx = 1; 7581573Srgrimes } 7591573Srgrimes if (!bp[0]) { 7601573Srgrimes hashp->cpage = NULL; 7611573Srgrimes ++hashp->cbucket; 7621573Srgrimes } 7631573Srgrimes } 7641573Srgrimes ndx = hashp->cndx; 7651573Srgrimes if (bp[ndx + 1] < REAL_KEY) { 7661573Srgrimes if (__big_keydata(hashp, bufp, key, data, 1)) 7671573Srgrimes return (ERROR); 7681573Srgrimes } else { 769190496Sdelphij if (hashp->cpage == 0) 770190496Sdelphij return (ERROR); 7711573Srgrimes key->data = (u_char *)hashp->cpage->page + bp[ndx]; 7721573Srgrimes key->size = (ndx > 1 ? bp[ndx - 1] : hashp->BSIZE) - bp[ndx]; 7731573Srgrimes data->data = (u_char *)hashp->cpage->page + bp[ndx + 1]; 7741573Srgrimes data->size = bp[ndx] - bp[ndx + 1]; 7751573Srgrimes } 7761573Srgrimes return (SUCCESS); 7771573Srgrimes} 7781573Srgrimes 7791573Srgrimes/********************************* UTILITIES ************************/ 7801573Srgrimes 7811573Srgrimes/* 7821573Srgrimes * Returns: 7831573Srgrimes * 0 ==> OK 7841573Srgrimes * -1 ==> Error 7851573Srgrimes */ 786189291Sdelphijint 787189291Sdelphij__expand_table(HTAB *hashp) 7881573Srgrimes{ 78914287Spst u_int32_t old_bucket, new_bucket; 7901573Srgrimes int dirsize, new_segnum, spare_ndx; 7911573Srgrimes 7921573Srgrimes#ifdef HASH_STATISTICS 7931573Srgrimes hash_expansions++; 7941573Srgrimes#endif 7951573Srgrimes new_bucket = ++hashp->MAX_BUCKET; 7961573Srgrimes old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK); 7971573Srgrimes 7981573Srgrimes new_segnum = new_bucket >> hashp->SSHIFT; 7991573Srgrimes 8001573Srgrimes /* Check if we need a new segment */ 8011573Srgrimes if (new_segnum >= hashp->nsegs) { 8021573Srgrimes /* Check if we need to expand directory */ 8031573Srgrimes if (new_segnum >= hashp->DSIZE) { 8041573Srgrimes /* Reallocate directory */ 8051573Srgrimes dirsize = hashp->DSIZE * sizeof(SEGMENT *); 8061573Srgrimes if (!hash_realloc(&hashp->dir, dirsize, dirsize << 1)) 8071573Srgrimes return (-1); 8081573Srgrimes hashp->DSIZE = dirsize << 1; 8091573Srgrimes } 8101573Srgrimes if ((hashp->dir[new_segnum] = 8111573Srgrimes (SEGMENT)calloc(hashp->SGSIZE, sizeof(SEGMENT))) == NULL) 8121573Srgrimes return (-1); 8131573Srgrimes hashp->exsegs++; 8141573Srgrimes hashp->nsegs++; 8151573Srgrimes } 8161573Srgrimes /* 8171573Srgrimes * If the split point is increasing (MAX_BUCKET's log base 2 8181573Srgrimes * * increases), we need to copy the current contents of the spare 8191573Srgrimes * split bucket to the next bucket. 8201573Srgrimes */ 8211573Srgrimes spare_ndx = __log2(hashp->MAX_BUCKET + 1); 8221573Srgrimes if (spare_ndx > hashp->OVFL_POINT) { 8231573Srgrimes hashp->SPARES[spare_ndx] = hashp->SPARES[hashp->OVFL_POINT]; 8241573Srgrimes hashp->OVFL_POINT = spare_ndx; 8251573Srgrimes } 8261573Srgrimes 8271573Srgrimes if (new_bucket > hashp->HIGH_MASK) { 8281573Srgrimes /* Starting a new doubling */ 8291573Srgrimes hashp->LOW_MASK = hashp->HIGH_MASK; 8301573Srgrimes hashp->HIGH_MASK = new_bucket | hashp->LOW_MASK; 8311573Srgrimes } 8321573Srgrimes /* Relocate records to the new bucket */ 8331573Srgrimes return (__split_page(hashp, old_bucket, new_bucket)); 8341573Srgrimes} 8351573Srgrimes 8361573Srgrimes/* 8371573Srgrimes * If realloc guarantees that the pointer is not destroyed if the realloc 8381573Srgrimes * fails, then this routine can go away. 8391573Srgrimes */ 8401573Srgrimesstatic void * 841189291Sdelphijhash_realloc(SEGMENT **p_ptr, int oldsize, int newsize) 8421573Srgrimes{ 84392889Sobrien void *p; 8441573Srgrimes 84517141Sjkh if ( (p = malloc(newsize)) ) { 8461573Srgrimes memmove(p, *p_ptr, oldsize); 8471573Srgrimes memset((char *)p + oldsize, 0, newsize - oldsize); 8481573Srgrimes free(*p_ptr); 8491573Srgrimes *p_ptr = p; 8501573Srgrimes } 8511573Srgrimes return (p); 8521573Srgrimes} 8531573Srgrimes 854189291Sdelphiju_int32_t 855189291Sdelphij__call_hash(HTAB *hashp, char *k, int len) 8561573Srgrimes{ 857190484Sdelphij unsigned int n, bucket; 8581573Srgrimes 8591573Srgrimes n = hashp->hash(k, len); 8601573Srgrimes bucket = n & hashp->HIGH_MASK; 8611573Srgrimes if (bucket > hashp->MAX_BUCKET) 8621573Srgrimes bucket = bucket & hashp->LOW_MASK; 8631573Srgrimes return (bucket); 8641573Srgrimes} 8651573Srgrimes 8661573Srgrimes/* 8671573Srgrimes * Allocate segment table. On error, destroy the table and set errno. 8681573Srgrimes * 8691573Srgrimes * Returns 0 on success 8701573Srgrimes */ 8711573Srgrimesstatic int 872189291Sdelphijalloc_segs(HTAB *hashp, int nsegs) 8731573Srgrimes{ 87492889Sobrien int i; 87592889Sobrien SEGMENT store; 8761573Srgrimes 8771573Srgrimes int save_errno; 8781573Srgrimes 8791573Srgrimes if ((hashp->dir = 8801573Srgrimes (SEGMENT *)calloc(hashp->DSIZE, sizeof(SEGMENT *))) == NULL) { 8811573Srgrimes save_errno = errno; 8821573Srgrimes (void)hdestroy(hashp); 8831573Srgrimes errno = save_errno; 8841573Srgrimes return (-1); 8851573Srgrimes } 886190496Sdelphij hashp->nsegs = nsegs; 887190496Sdelphij if (nsegs == 0) 888190496Sdelphij return (0); 8891573Srgrimes /* Allocate segments */ 890190496Sdelphij if ((store = (SEGMENT)calloc(nsegs << hashp->SSHIFT, 891190496Sdelphij sizeof(SEGMENT))) == NULL) { 8921573Srgrimes save_errno = errno; 8931573Srgrimes (void)hdestroy(hashp); 8941573Srgrimes errno = save_errno; 8951573Srgrimes return (-1); 8961573Srgrimes } 897190496Sdelphij for (i = 0; i < nsegs; i++) 8981573Srgrimes hashp->dir[i] = &store[i << hashp->SSHIFT]; 8991573Srgrimes return (0); 9001573Srgrimes} 9011573Srgrimes 9021573Srgrimes#if BYTE_ORDER == LITTLE_ENDIAN 9031573Srgrimes/* 9041573Srgrimes * Hashp->hdr needs to be byteswapped. 9051573Srgrimes */ 9061573Srgrimesstatic void 907189291Sdelphijswap_header_copy(HASHHDR *srcp, HASHHDR *destp) 9081573Srgrimes{ 9091573Srgrimes int i; 9101573Srgrimes 9111573Srgrimes P_32_COPY(srcp->magic, destp->magic); 9121573Srgrimes P_32_COPY(srcp->version, destp->version); 9131573Srgrimes P_32_COPY(srcp->lorder, destp->lorder); 9141573Srgrimes P_32_COPY(srcp->bsize, destp->bsize); 9151573Srgrimes P_32_COPY(srcp->bshift, destp->bshift); 9161573Srgrimes P_32_COPY(srcp->dsize, destp->dsize); 9171573Srgrimes P_32_COPY(srcp->ssize, destp->ssize); 9181573Srgrimes P_32_COPY(srcp->sshift, destp->sshift); 9191573Srgrimes P_32_COPY(srcp->ovfl_point, destp->ovfl_point); 9201573Srgrimes P_32_COPY(srcp->last_freed, destp->last_freed); 9211573Srgrimes P_32_COPY(srcp->max_bucket, destp->max_bucket); 9221573Srgrimes P_32_COPY(srcp->high_mask, destp->high_mask); 9231573Srgrimes P_32_COPY(srcp->low_mask, destp->low_mask); 9241573Srgrimes P_32_COPY(srcp->ffactor, destp->ffactor); 9251573Srgrimes P_32_COPY(srcp->nkeys, destp->nkeys); 9261573Srgrimes P_32_COPY(srcp->hdrpages, destp->hdrpages); 9271573Srgrimes P_32_COPY(srcp->h_charkey, destp->h_charkey); 9281573Srgrimes for (i = 0; i < NCACHED; i++) { 9291573Srgrimes P_32_COPY(srcp->spares[i], destp->spares[i]); 9301573Srgrimes P_16_COPY(srcp->bitmaps[i], destp->bitmaps[i]); 9311573Srgrimes } 9321573Srgrimes} 9331573Srgrimes 9341573Srgrimesstatic void 935189291Sdelphijswap_header(HTAB *hashp) 9361573Srgrimes{ 9371573Srgrimes HASHHDR *hdrp; 9381573Srgrimes int i; 9391573Srgrimes 9401573Srgrimes hdrp = &hashp->hdr; 9411573Srgrimes 9421573Srgrimes M_32_SWAP(hdrp->magic); 9431573Srgrimes M_32_SWAP(hdrp->version); 9441573Srgrimes M_32_SWAP(hdrp->lorder); 9451573Srgrimes M_32_SWAP(hdrp->bsize); 9461573Srgrimes M_32_SWAP(hdrp->bshift); 9471573Srgrimes M_32_SWAP(hdrp->dsize); 9481573Srgrimes M_32_SWAP(hdrp->ssize); 9491573Srgrimes M_32_SWAP(hdrp->sshift); 9501573Srgrimes M_32_SWAP(hdrp->ovfl_point); 9511573Srgrimes M_32_SWAP(hdrp->last_freed); 9521573Srgrimes M_32_SWAP(hdrp->max_bucket); 9531573Srgrimes M_32_SWAP(hdrp->high_mask); 9541573Srgrimes M_32_SWAP(hdrp->low_mask); 9551573Srgrimes M_32_SWAP(hdrp->ffactor); 9561573Srgrimes M_32_SWAP(hdrp->nkeys); 9571573Srgrimes M_32_SWAP(hdrp->hdrpages); 9581573Srgrimes M_32_SWAP(hdrp->h_charkey); 9591573Srgrimes for (i = 0; i < NCACHED; i++) { 9601573Srgrimes M_32_SWAP(hdrp->spares[i]); 9611573Srgrimes M_16_SWAP(hdrp->bitmaps[i]); 9621573Srgrimes } 9631573Srgrimes} 9641573Srgrimes#endif 965