1139743Simp/* $NetBSD: hash.c,v 1.38 2015/11/18 18:22:42 christos Exp $ */ 242650Sgibbs 342650Sgibbs/*- 442650Sgibbs * Copyright (c) 1990, 1993, 1994 542650Sgibbs * The Regents of the University of California. All rights reserved. 642650Sgibbs * 742650Sgibbs * This code is derived from software contributed to Berkeley by 842650Sgibbs * Margo Seltzer. 942650Sgibbs * 1042650Sgibbs * Redistribution and use in source and binary forms, with or without 1142650Sgibbs * modification, are permitted provided that the following conditions 1242650Sgibbs * are met: 1342650Sgibbs * 1. Redistributions of source code must retain the above copyright 1442650Sgibbs * notice, this list of conditions and the following disclaimer. 1542650Sgibbs * 2. Redistributions in binary form must reproduce the above copyright 1642650Sgibbs * notice, this list of conditions and the following disclaimer in the 1742650Sgibbs * documentation and/or other materials provided with the distribution. 1842650Sgibbs * 3. Neither the name of the University nor the names of its contributors 1942650Sgibbs * may be used to endorse or promote products derived from this software 2042650Sgibbs * without specific prior written permission. 2142650Sgibbs * 2242650Sgibbs * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 2342650Sgibbs * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2442650Sgibbs * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2542650Sgibbs * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 2642650Sgibbs * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2742650Sgibbs * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2842650Sgibbs * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29116162Sobrien * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30116162Sobrien * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31116162Sobrien * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 3242650Sgibbs * SUCH DAMAGE. 3342650Sgibbs */ 3442650Sgibbs 3542650Sgibbs#if HAVE_NBTOOL_CONFIG_H 3642650Sgibbs#include "nbtool_config.h" 3760041Sphk#endif 3842650Sgibbs 3942650Sgibbs#include <sys/cdefs.h> 4042650Sgibbs__RCSID("$NetBSD: hash.c,v 1.38 2015/11/18 18:22:42 christos Exp $"); 4142650Sgibbs 4242650Sgibbs#include "namespace.h" 4342650Sgibbs#include <sys/param.h> 4442650Sgibbs#include <sys/stat.h> 4542650Sgibbs 4642650Sgibbs#include <errno.h> 4742650Sgibbs#include <fcntl.h> 4842650Sgibbs#include <stdio.h> 49168752Sscottl#include <stdlib.h> 5042650Sgibbs#include <string.h> 5142650Sgibbs#include <unistd.h> 5242650Sgibbs#include <assert.h> 5342650Sgibbs 54147723Savatar#include <db.h> 55147723Savatar#include "hash.h" 5642650Sgibbs#include "page.h" 5742650Sgibbs#include "extern.h" 5842650Sgibbs 5942650Sgibbsstatic int alloc_segs(HTAB *, int); 6042650Sgibbsstatic int flush_meta(HTAB *); 6142650Sgibbsstatic int hash_access(HTAB *, ACTION, DBT *, DBT *); 6242650Sgibbsstatic int hash_close(DB *); 6342650Sgibbsstatic int hash_delete(const DB *, const DBT *, uint32_t); 6442650Sgibbsstatic int hash_fd(const DB *); 6542650Sgibbsstatic int hash_get(const DB *, const DBT *, DBT *, uint32_t); 6642650Sgibbsstatic int hash_put(const DB *, DBT *, const DBT *, uint32_t); 6742650Sgibbsstatic void *hash_realloc(SEGMENT **, size_t, size_t); 6842650Sgibbsstatic int hash_seq(const DB *, DBT *, DBT *, uint32_t); 6942650Sgibbsstatic int hash_sync(const DB *, uint32_t); 7042650Sgibbsstatic int hdestroy(HTAB *); 7142650Sgibbsstatic HTAB *init_hash(HTAB *, const char *, const HASHINFO *); 7244503Sgibbsstatic int init_htab(HTAB *, size_t); 7342650Sgibbs#if BYTE_ORDER == LITTLE_ENDIAN 7442650Sgibbsstatic void swap_header(HTAB *); 7542650Sgibbsstatic void swap_header_copy(HASHHDR *, HASHHDR *); 7642650Sgibbs#endif 7742650Sgibbs 7842650Sgibbs/* Fast arithmetic, relying on powers of 2, */ 7942650Sgibbs#define MOD(x, y) ((x) & ((y) - 1)) 8042650Sgibbs 8142650Sgibbs#define RETURN_ERROR(ERR, LOC) { save_errno = ERR; goto LOC; } 8242650Sgibbs 8360938Sjake/* Return values */ 8442650Sgibbs#define SUCCESS (0) 8542650Sgibbs#define ERROR (-1) 8642650Sgibbs#define ABNORMAL (1) 8742650Sgibbs 8842650Sgibbs#ifdef HASH_STATISTICS 8942650Sgibbsint hash_accesses, hash_collisions, hash_expansions, hash_overflows; 9042650Sgibbs#endif 9142650Sgibbs 9242650Sgibbs/************************** INTERFACE ROUTINES ***************************/ 9342650Sgibbs/* OPEN/CLOSE */ 9442650Sgibbs 9542650Sgibbs/* ARGSUSED */ 9642650SgibbsDB * 9742650Sgibbs__hash_open(const char *file, int flags, mode_t mode, const HASHINFO *info, 9842650Sgibbs int dflags) 9942650Sgibbs{ 10042650Sgibbs HTAB *hashp; 10142650Sgibbs struct stat statbuf; 10242650Sgibbs DB *dbp; 10342650Sgibbs int bpages, new_table, nsegs, save_errno; 10442650Sgibbs ssize_t hdrsize; 10542650Sgibbs 10642650Sgibbs if ((flags & O_ACCMODE) == O_WRONLY) { 10742650Sgibbs errno = EINVAL; 10842650Sgibbs return (NULL); 10942650Sgibbs } 11042650Sgibbs 11142650Sgibbs if (!(hashp = calloc(1, sizeof(HTAB)))) 11242650Sgibbs return (NULL); 11342650Sgibbs hashp->fp = -1; 11442650Sgibbs 11542650Sgibbs /* 11642650Sgibbs * Even if user wants write only, we need to be able to read 11742650Sgibbs * the actual file, so we need to open it read/write. But, the 11842650Sgibbs * field in the hashp structure needs to be accurate so that 11942650Sgibbs * we can check accesses. 12044503Sgibbs */ 12142650Sgibbs hashp->flags = flags; 12242650Sgibbs 12344503Sgibbs new_table = 0; 12442650Sgibbs if (!file || (flags & O_TRUNC) || 12542650Sgibbs (stat(file, &statbuf) && (errno == ENOENT))) { 12642650Sgibbs if (errno == ENOENT) 12742650Sgibbs errno = 0; /* Just in case someone looks at errno */ 12842650Sgibbs new_table = 1; 12942650Sgibbs } 13042650Sgibbs if (file) { 13142650Sgibbs if ((hashp->fp = __dbopen(file, flags, mode, &statbuf)) == -1) 13242650Sgibbs RETURN_ERROR(errno, error0); 13342650Sgibbs new_table |= statbuf.st_size == 0; 13442650Sgibbs } 13542650Sgibbs if (new_table) { 13642650Sgibbs if (!(hashp = init_hash(hashp, file, info))) 13742650Sgibbs RETURN_ERROR(errno, error1); 13842650Sgibbs } else { 13942650Sgibbs /* Table already exists */ 14044503Sgibbs if (info && info->hash) 14142650Sgibbs hashp->hash = info->hash; 14242650Sgibbs else 14344503Sgibbs hashp->hash = __default_hash; 14442650Sgibbs 14542650Sgibbs hdrsize = read(hashp->fp, &hashp->hdr, sizeof(HASHHDR)); 14642650Sgibbs#if BYTE_ORDER == LITTLE_ENDIAN 14742650Sgibbs swap_header(hashp); 14842650Sgibbs#endif 14942650Sgibbs if (hdrsize == -1) 15042650Sgibbs RETURN_ERROR(errno, error1); 15142650Sgibbs if (hdrsize != sizeof(HASHHDR)) 15242650Sgibbs RETURN_ERROR(EFTYPE, error1); 15372119Speter /* Verify file type, versions and hash function */ 15442650Sgibbs if (hashp->MAGIC != HASHMAGIC) 15542650Sgibbs RETURN_ERROR(EFTYPE, error1); 15642650Sgibbs#define OLDHASHVERSION 1 15742650Sgibbs if (hashp->VERSION != HASHVERSION && 15842650Sgibbs hashp->VERSION != OLDHASHVERSION) 15942650Sgibbs RETURN_ERROR(EFTYPE, error1); 16042650Sgibbs if (hashp->hash(CHARKEY, sizeof(CHARKEY)) != 16142650Sgibbs (uint32_t)hashp->H_CHARKEY) 16242650Sgibbs RETURN_ERROR(EFTYPE, error1); 16342650Sgibbs /* 164169605Sscottl * Figure out how many segments we need. Max_Bucket is the 165169605Sscottl * maximum bucket number, so the number of buckets is 16642650Sgibbs * max_bucket + 1. 16742650Sgibbs */ 16842650Sgibbs nsegs = (hashp->MAX_BUCKET + 1 + hashp->SGSIZE - 1) / 16942650Sgibbs hashp->SGSIZE; 17042650Sgibbs hashp->nsegs = 0; 17142650Sgibbs if (alloc_segs(hashp, nsegs)) 17242650Sgibbs /* 17342650Sgibbs * If alloc_segs fails, table will have been destroyed 17442650Sgibbs * and errno will have been set. 17542650Sgibbs */ 17642650Sgibbs return (NULL); 177120426Ssimokawa /* Read in bitmaps */ 178120601Ssimokawa bpages = (hashp->SPARES[hashp->OVFL_POINT] + 179120601Ssimokawa (unsigned int)(hashp->BSIZE << BYTE_SHIFT) - 1) >> 180120426Ssimokawa (hashp->BSHIFT + BYTE_SHIFT); 18142650Sgibbs 182120601Ssimokawa hashp->nmaps = bpages; 183120601Ssimokawa (void)memset(&hashp->mapp[0], 0, bpages * sizeof(uint32_t *)); 184120601Ssimokawa } 185120601Ssimokawa 186120601Ssimokawa /* Initialize Buffer Manager */ 187120426Ssimokawa if (info && info->cachesize) 188120426Ssimokawa __buf_init(hashp, info->cachesize); 189120426Ssimokawa else 190120426Ssimokawa __buf_init(hashp, DEF_BUFSIZE); 191120426Ssimokawa 192120601Ssimokawa hashp->new_file = new_table; 193120426Ssimokawa hashp->save_file = file && (hashp->flags & O_RDWR); 194120426Ssimokawa hashp->cbucket = -1; 195120426Ssimokawa if (!(dbp = malloc(sizeof(*dbp)))) { 196120426Ssimokawa save_errno = errno; 197120426Ssimokawa hdestroy(hashp); 198120426Ssimokawa errno = save_errno; 199120426Ssimokawa return (NULL); 20042650Sgibbs } 20142650Sgibbs dbp->internal = hashp; 20242650Sgibbs dbp->close = hash_close; 20342650Sgibbs dbp->del = hash_delete; 20442650Sgibbs dbp->fd = hash_fd; 20542650Sgibbs dbp->get = hash_get; 20642650Sgibbs dbp->put = hash_put; 20742650Sgibbs dbp->seq = hash_seq; 20842650Sgibbs dbp->sync = hash_sync; 20942650Sgibbs dbp->type = DB_HASH; 21042650Sgibbs 21142650Sgibbs#ifdef DEBUG1 21242650Sgibbs (void)fprintf(stderr, 21342650Sgibbs"%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", 21442650Sgibbs "init_htab:", 21542650Sgibbs "TABLE POINTER ", hashp, 21642650Sgibbs "BUCKET SIZE ", hashp->BSIZE, 217120601Ssimokawa "BUCKET SHIFT ", hashp->BSHIFT, 218120601Ssimokawa "DIRECTORY SIZE ", hashp->DSIZE, 219120601Ssimokawa "SEGMENT SIZE ", hashp->SGSIZE, 220120601Ssimokawa "SEGMENT SHIFT ", hashp->SSHIFT, 22142650Sgibbs "FILL FACTOR ", hashp->FFACTOR, 22242650Sgibbs "MAX BUCKET ", hashp->MAX_BUCKET, 22342650Sgibbs "OVFL POINT ", hashp->OVFL_POINT, 22442650Sgibbs "LAST FREED ", hashp->LAST_FREED, 22542650Sgibbs "HIGH MASK ", hashp->HIGH_MASK, 226120426Ssimokawa "LOW MASK ", hashp->LOW_MASK, 22742650Sgibbs "NSEGS ", hashp->nsegs, 22842650Sgibbs "NKEYS ", hashp->NKEYS); 22942650Sgibbs#endif 23042650Sgibbs#ifdef HASH_STATISTICS 23142650Sgibbs hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0; 23242650Sgibbs#endif 23342650Sgibbs return (dbp); 23442650Sgibbs 23542650Sgibbserror1: 23642650Sgibbs if (hashp != NULL) 23742650Sgibbs (void)close(hashp->fp); 23842650Sgibbs 23942650Sgibbserror0: 24042650Sgibbs free(hashp); 24142650Sgibbs errno = save_errno; 24242650Sgibbs return (NULL); 243198382Smav} 24442650Sgibbs 24542650Sgibbsstatic int 24642650Sgibbshash_close(DB *dbp) 24742650Sgibbs{ 24842650Sgibbs HTAB *hashp; 24942650Sgibbs int retval; 25042650Sgibbs 25142650Sgibbs if (!dbp) 25242650Sgibbs return (ERROR); 253164906Smjacob 254164906Smjacob hashp = dbp->internal; 255164906Smjacob retval = hdestroy(hashp); 25642650Sgibbs free(dbp); 25742650Sgibbs return (retval); 25842650Sgibbs} 25942650Sgibbs 26042650Sgibbsstatic int 26142650Sgibbshash_fd(const DB *dbp) 26242650Sgibbs{ 26342650Sgibbs HTAB *hashp; 26442650Sgibbs 26542650Sgibbs if (!dbp) 26642650Sgibbs return (ERROR); 26742650Sgibbs 268147723Savatar hashp = dbp->internal; 26942650Sgibbs if (hashp->fp == -1) { 27042650Sgibbs errno = ENOENT; 27142650Sgibbs return (-1); 27242650Sgibbs } 27342650Sgibbs return (hashp->fp); 27442650Sgibbs} 27542650Sgibbs 27642650Sgibbs/************************** LOCAL CREATION ROUTINES **********************/ 27742650Sgibbsstatic HTAB * 278147723Savatarinit_hash(HTAB *hashp, const char *file, const HASHINFO *info) 27942650Sgibbs{ 28042650Sgibbs struct stat statbuf; 28142650Sgibbs int nelem; 28242650Sgibbs 283198382Smav nelem = 1; 28442650Sgibbs hashp->NKEYS = 0; 28542650Sgibbs hashp->LORDER = BYTE_ORDER; 28642650Sgibbs hashp->BSIZE = DEF_BUCKET_SIZE; 28742650Sgibbs hashp->BSHIFT = DEF_BUCKET_SHIFT; 28842650Sgibbs hashp->SGSIZE = DEF_SEGSIZE; 28942650Sgibbs hashp->SSHIFT = DEF_SEGSIZE_SHIFT; 290147723Savatar hashp->DSIZE = DEF_DIRSIZE; 29142650Sgibbs hashp->FFACTOR = DEF_FFACTOR; 29242650Sgibbs hashp->hash = __default_hash; 29342650Sgibbs memset(hashp->SPARES, 0, sizeof(hashp->SPARES)); 29442650Sgibbs memset(hashp->BITMAPS, 0, sizeof (hashp->BITMAPS)); 29542650Sgibbs 29642650Sgibbs /* Fix bucket size to be optimal for file system */ 29742650Sgibbs if (file != NULL) { 29842650Sgibbs if (stat(file, &statbuf)) 299164906Smjacob return (NULL); 300164906Smjacob hashp->BSIZE = MIN(statbuf.st_blksize, MAX_BSIZE); 301164906Smjacob hashp->BSHIFT = __log2((uint32_t)hashp->BSIZE); 30242650Sgibbs } 30342650Sgibbs 30442650Sgibbs if (info) { 30542650Sgibbs if (info->bsize) { 30642650Sgibbs /* Round pagesize up to power of 2 */ 30742650Sgibbs hashp->BSHIFT = __log2(info->bsize); 30842650Sgibbs hashp->BSIZE = 1 << hashp->BSHIFT; 30942650Sgibbs if (hashp->BSIZE > MAX_BSIZE) { 31042650Sgibbs errno = EINVAL; 31142650Sgibbs return (NULL); 31242650Sgibbs } 313147723Savatar } 31442650Sgibbs if (info->ffactor) 31542650Sgibbs hashp->FFACTOR = info->ffactor; 31642650Sgibbs if (info->hash) 31742650Sgibbs hashp->hash = info->hash; 31842650Sgibbs if (info->nelem) 31942650Sgibbs nelem = info->nelem; 32042650Sgibbs if (info->lorder) { 321198382Smav if (info->lorder != BIG_ENDIAN && 32242650Sgibbs info->lorder != LITTLE_ENDIAN) { 32342650Sgibbs errno = EINVAL; 32442650Sgibbs return (NULL); 32542650Sgibbs } 32642650Sgibbs hashp->LORDER = info->lorder; 327147723Savatar } 32842650Sgibbs } 32942650Sgibbs /* init_htab should destroy the table and set errno if it fails */ 33042650Sgibbs if (init_htab(hashp, (size_t)nelem)) 33142650Sgibbs return (NULL); 33242650Sgibbs else 33342650Sgibbs return (hashp); 33442650Sgibbs} 335164906Smjacob/* 336164906Smjacob * This calls alloc_segs which may run out of memory. Alloc_segs will destroy 337164906Smjacob * the table and set errno, so we just pass the error information along. 33842650Sgibbs * 33942650Sgibbs * Returns 0 on No Error 34042650Sgibbs */ 34142650Sgibbsstatic int 34242650Sgibbsinit_htab(HTAB *hashp, size_t nelem) 34342650Sgibbs{ 34442650Sgibbs int nbuckets; 34542650Sgibbs uint32_t nsegs; 34642650Sgibbs int l2; 34742650Sgibbs 34842650Sgibbs /* 34942650Sgibbs * Divide number of elements by the fill factor and determine a 35042650Sgibbs * desired number of buckets. Allocate space for the next greater 35142650Sgibbs * power of two number of buckets. 35242650Sgibbs */ 35342650Sgibbs nelem = (nelem - 1) / hashp->FFACTOR + 1; 35442650Sgibbs 35542650Sgibbs _DBFIT(nelem, uint32_t); 35642650Sgibbs l2 = __log2(MAX((uint32_t)nelem, 2)); 35742650Sgibbs nbuckets = 1 << l2; 35842650Sgibbs 35942650Sgibbs hashp->SPARES[l2] = l2 + 1; 36042650Sgibbs hashp->SPARES[l2 + 1] = l2 + 1; 36142650Sgibbs hashp->OVFL_POINT = l2; 36242650Sgibbs hashp->LAST_FREED = 2; 36342650Sgibbs 364198382Smav /* First bitmap page is at: splitpoint l2 page offset 1 */ 36542650Sgibbs if (__ibitmap(hashp, (int)OADDR_OF(l2, 1), l2 + 1, 0)) 36642650Sgibbs return (-1); 36742650Sgibbs 36842650Sgibbs hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1; 36942650Sgibbs hashp->HIGH_MASK = (nbuckets << 1) - 1; 37042650Sgibbs /* LINTED constant in conditional context */ 37142650Sgibbs hashp->HDRPAGES = ((MAX(sizeof(HASHHDR), MINHDRSIZE) - 1) >> 372198382Smav hashp->BSHIFT) + 1; 37342650Sgibbs 37442650Sgibbs nsegs = (nbuckets - 1) / hashp->SGSIZE + 1; 37542650Sgibbs nsegs = 1 << __log2(nsegs); 37642650Sgibbs 37742650Sgibbs if (nsegs > (uint32_t)hashp->DSIZE) 37842650Sgibbs hashp->DSIZE = nsegs; 37942650Sgibbs return (alloc_segs(hashp, (int)nsegs)); 38042650Sgibbs} 381198382Smav 38242650Sgibbs/********************** DESTROY/CLOSE ROUTINES ************************/ 38342650Sgibbs 38442650Sgibbs/* 38542650Sgibbs * Flushes any changes to the file if necessary and destroys the hashp 38642650Sgibbs * structure, freeing all allocated space. 38742650Sgibbs */ 38842650Sgibbsstatic int 38942650Sgibbshdestroy(HTAB *hashp) 39042650Sgibbs{ 39142650Sgibbs int i, save_errno; 39242650Sgibbs 39342650Sgibbs save_errno = 0; 39442650Sgibbs 39542650Sgibbs#ifdef HASH_STATISTICS 39642650Sgibbs (void)fprintf(stderr, "hdestroy: accesses %d collisions %d\n", 39742650Sgibbs hash_accesses, hash_collisions); 39842650Sgibbs (void)fprintf(stderr, "hdestroy: expansions %d\n", 39942650Sgibbs hash_expansions); 40042650Sgibbs (void)fprintf(stderr, "hdestroy: overflows %d\n", 401147723Savatar hash_overflows); 40242650Sgibbs (void)fprintf(stderr, "keys %d maxp %d segmentcount %d\n", 40342650Sgibbs hashp->NKEYS, hashp->MAX_BUCKET, hashp->nsegs); 40442650Sgibbs 40542650Sgibbs for (i = 0; i < NCACHED; i++) 40642650Sgibbs (void)fprintf(stderr, 40763172Smjacob "spares[%d] = %d\n", i, hashp->SPARES[i]); 40842650Sgibbs#endif 40942650Sgibbs /* 41042650Sgibbs * Call on buffer manager to free buffers, and if required, 41142650Sgibbs * write them to disk. 41242650Sgibbs */ 41342650Sgibbs if (__buf_free(hashp, 1, hashp->save_file)) 41442650Sgibbs save_errno = errno; 41542650Sgibbs if (hashp->dir) { 41642650Sgibbs free(*hashp->dir); /* Free initial segments */ 41742650Sgibbs /* Free extra segments */ 41842650Sgibbs while (hashp->exsegs--) 41942650Sgibbs free(hashp->dir[--hashp->nsegs]); 42042650Sgibbs free(hashp->dir); 42142650Sgibbs } 42242650Sgibbs if (flush_meta(hashp) && !save_errno) 42342650Sgibbs save_errno = errno; 42442650Sgibbs /* Free Bigmaps */ 42542650Sgibbs for (i = 0; i < hashp->nmaps; i++) 42642650Sgibbs if (hashp->mapp[i]) 42742650Sgibbs free(hashp->mapp[i]); 42842650Sgibbs 42942650Sgibbs if (hashp->fp != -1) 43042650Sgibbs (void)close(hashp->fp); 431115561Sphk 432201758Smbr free(hashp); 433115561Sphk 434115561Sphk if (save_errno) { 43542650Sgibbs errno = save_errno; 436120426Ssimokawa return (ERROR); 437168752Sscottl } 438147723Savatar return (SUCCESS); 43942650Sgibbs} 44042650Sgibbs/* 44142650Sgibbs * Write modified pages to disk 44242650Sgibbs * 44342650Sgibbs * Returns: 44442650Sgibbs * 0 == OK 44542650Sgibbs * -1 ERROR 44642650Sgibbs */ 44742650Sgibbsstatic int 44842650Sgibbshash_sync(const DB *dbp, uint32_t flags) 44942650Sgibbs{ 45042650Sgibbs HTAB *hashp; 45142650Sgibbs 45242650Sgibbs if (flags != 0) { 45342650Sgibbs errno = EINVAL; 45442650Sgibbs return (ERROR); 45542650Sgibbs } 45642650Sgibbs 45742650Sgibbs if (!dbp) 45842650Sgibbs return (ERROR); 45942650Sgibbs 46042650Sgibbs hashp = dbp->internal; 46142650Sgibbs if (!hashp->save_file) 46242650Sgibbs return (0); 46342650Sgibbs if (__buf_free(hashp, 0, 1) || flush_meta(hashp)) 46442650Sgibbs return (ERROR); 46542650Sgibbs hashp->new_file = 0; 46642650Sgibbs return (0); 46742650Sgibbs} 46842650Sgibbs 46942650Sgibbs/* 47042650Sgibbs * Returns: 47142650Sgibbs * 0 == OK 47280573Smjacob * -1 indicates that errno should be set 47380573Smjacob */ 47442650Sgibbsstatic int 47556594Smjacobflush_meta(HTAB *hashp) 47642650Sgibbs{ 47742650Sgibbs HASHHDR *whdrp; 47842650Sgibbs#if BYTE_ORDER == LITTLE_ENDIAN 47956594Smjacob HASHHDR whdr; 48056594Smjacob#endif 48142650Sgibbs int fp, i; 48256594Smjacob ssize_t wsize; 48342650Sgibbs 48456594Smjacob if (!hashp->save_file) 48556594Smjacob return (0); 48656594Smjacob hashp->MAGIC = HASHMAGIC; 48756594Smjacob hashp->VERSION = HASHVERSION; 48856594Smjacob hashp->H_CHARKEY = hashp->hash(CHARKEY, sizeof(CHARKEY)); 48942650Sgibbs 49056594Smjacob fp = hashp->fp; 49156594Smjacob whdrp = &hashp->hdr; 49242650Sgibbs#if BYTE_ORDER == LITTLE_ENDIAN 49342650Sgibbs whdrp = &whdr; 49442650Sgibbs swap_header_copy(&hashp->hdr, whdrp); 49542650Sgibbs#endif 49663190Smjacob if ((wsize = pwrite(fp, whdrp, sizeof(HASHHDR), (off_t)0)) == -1) 49763190Smjacob return (-1); 49842650Sgibbs else 49942650Sgibbs if (wsize != sizeof(HASHHDR)) { 50042650Sgibbs errno = EFTYPE; 50142650Sgibbs hashp->err = errno; 50242650Sgibbs return (-1); 50342650Sgibbs } 50442650Sgibbs for (i = 0; i < NCACHED; i++) 50542650Sgibbs if (hashp->mapp[i]) 50642650Sgibbs if (__put_page(hashp, (char *)(void *)hashp->mapp[i], 50742650Sgibbs (u_int)hashp->BITMAPS[i], 0, 1)) 50842650Sgibbs return (-1); 50942650Sgibbs return (0); 51042650Sgibbs} 51142650Sgibbs 51242650Sgibbs/*******************************SEARCH ROUTINES *****************************/ 51342650Sgibbs/* 51442650Sgibbs * All the access routines return 51580573Smjacob * 51680573Smjacob * Returns: 51780573Smjacob * 0 on SUCCESS 51880573Smjacob * 1 to indicate an external ERROR (i.e. key not found, etc) 51980573Smjacob * -1 to indicate an internal ERROR (i.e. out of memory, etc) 52080573Smjacob */ 52180573Smjacobstatic int 52280573Smjacobhash_get(const DB *dbp, const DBT *key, DBT *data, uint32_t flag) 52380573Smjacob{ 52480573Smjacob HTAB *hashp; 52580573Smjacob 52680573Smjacob hashp = dbp->internal; 52780573Smjacob if (flag) { 52842650Sgibbs hashp->err = errno = EINVAL; 52942650Sgibbs return (ERROR); 53042650Sgibbs } 531198382Smav return (hash_access(hashp, HASH_GET, __UNCONST(key), data)); 53242650Sgibbs} 53342650Sgibbs 53442650Sgibbsstatic int 53542650Sgibbshash_put(const DB *dbp, DBT *key, const DBT *data, uint32_t flag) 53642650Sgibbs{ 53742650Sgibbs HTAB *hashp; 53842650Sgibbs 53942650Sgibbs hashp = dbp->internal; 54042650Sgibbs if (flag && flag != R_NOOVERWRITE) { 54142650Sgibbs hashp->err = errno = EINVAL; 54242650Sgibbs return (ERROR); 54342650Sgibbs } 54442650Sgibbs if ((hashp->flags & O_ACCMODE) == O_RDONLY) { 54542650Sgibbs hashp->err = errno = EPERM; 54642650Sgibbs return (ERROR); 54742650Sgibbs } 54842650Sgibbs /* LINTED const castaway */ 54942650Sgibbs return (hash_access(hashp, flag == R_NOOVERWRITE ? 55042650Sgibbs HASH_PUTNEW : HASH_PUT, __UNCONST(key), __UNCONST(data))); 55142650Sgibbs} 55242650Sgibbs 55380573Smjacobstatic int 55442650Sgibbshash_delete(const DB *dbp, const DBT *key, uint32_t flag) 55542650Sgibbs{ 55642650Sgibbs HTAB *hashp; 55742650Sgibbs 55842650Sgibbs hashp = dbp->internal; 55942650Sgibbs if (flag && flag != R_CURSOR) { 56042650Sgibbs hashp->err = errno = EINVAL; 561147723Savatar return (ERROR); 56242650Sgibbs } 56342650Sgibbs if ((hashp->flags & O_ACCMODE) == O_RDONLY) { 56442650Sgibbs hashp->err = errno = EPERM; 56542650Sgibbs return (ERROR); 56642650Sgibbs } 56742650Sgibbs return hash_access(hashp, HASH_DELETE, __UNCONST(key), NULL); 56842650Sgibbs} 56942650Sgibbs 57042650Sgibbs/* 57142650Sgibbs * Assume that hashp has been set in wrapper routine. 57242650Sgibbs */ 57342650Sgibbsstatic int 57442650Sgibbshash_access(HTAB *hashp, ACTION action, DBT *key, DBT *val) 57542650Sgibbs{ 57642650Sgibbs BUFHEAD *rbufp; 57742650Sgibbs BUFHEAD *bufp, *save_bufp; 57842650Sgibbs uint16_t *bp; 57942650Sgibbs int n, ndx, off; 58042650Sgibbs size_t size; 58142650Sgibbs char *kp; 58242650Sgibbs uint16_t pageno; 58342650Sgibbs 58442650Sgibbs#ifdef HASH_STATISTICS 58542650Sgibbs hash_accesses++; 58656594Smjacob#endif 58756594Smjacob 58856594Smjacob off = HASH_BSIZE(hashp); 58956594Smjacob size = key->size; 59056594Smjacob kp = (char *)key->data; 59163172Smjacob rbufp = __get_buf(hashp, __call_hash(hashp, kp, (int)size), NULL, 0); 59242650Sgibbs if (!rbufp) 59342650Sgibbs return (ERROR); 59442650Sgibbs save_bufp = rbufp; 59542650Sgibbs 59642650Sgibbs /* Pin the bucket chain */ 59742650Sgibbs rbufp->flags |= BUF_PIN; 59842650Sgibbs for (bp = (uint16_t *)(void *)rbufp->page, n = *bp++, ndx = 1; ndx < n;) 59942650Sgibbs if (bp[1] >= REAL_KEY) { 60042650Sgibbs /* Real key/data pair */ 60142650Sgibbs if (size == (size_t)(off - *bp) && 60242650Sgibbs memcmp(kp, rbufp->page + *bp, size) == 0) 60342650Sgibbs goto found; 60442650Sgibbs off = bp[1]; 60563172Smjacob#ifdef HASH_STATISTICS 60642650Sgibbs hash_collisions++; 60742650Sgibbs#endif 60842650Sgibbs bp += 2; 60942650Sgibbs ndx += 2; 61042650Sgibbs } else if (bp[1] == OVFLPAGE) { 61142650Sgibbs rbufp = __get_buf(hashp, (uint32_t)*bp, rbufp, 0); 61242650Sgibbs if (!rbufp) { 61342650Sgibbs save_bufp->flags &= ~BUF_PIN; 61442650Sgibbs return (ERROR); 61542650Sgibbs } 61642650Sgibbs /* FOR LOOP INIT */ 61742650Sgibbs bp = (uint16_t *)(void *)rbufp->page; 61842650Sgibbs n = *bp++; 61942650Sgibbs ndx = 1; 62042650Sgibbs off = HASH_BSIZE(hashp); 62142650Sgibbs } else if (bp[1] < REAL_KEY) { 62263172Smjacob if ((ndx = 62342650Sgibbs __find_bigpair(hashp, rbufp, ndx, kp, (int)size)) > 0) 62442650Sgibbs goto found; 62542650Sgibbs if (ndx == -2) { 62642650Sgibbs bufp = rbufp; 62742650Sgibbs if (!(pageno = 62842650Sgibbs __find_last_page(hashp, &bufp))) { 62942650Sgibbs ndx = 0; 63042650Sgibbs rbufp = bufp; 63142650Sgibbs break; /* FOR */ 63242650Sgibbs } 63356594Smjacob rbufp = __get_buf(hashp, (uint32_t)pageno, 63456594Smjacob bufp, 0); 63542650Sgibbs if (!rbufp) { 63642650Sgibbs save_bufp->flags &= ~BUF_PIN; 63742650Sgibbs return (ERROR); 63842650Sgibbs } 63942650Sgibbs /* FOR LOOP INIT */ 64042650Sgibbs bp = (uint16_t *)(void *)rbufp->page; 64142650Sgibbs n = *bp++; 64242650Sgibbs ndx = 1; 64380573Smjacob off = HASH_BSIZE(hashp); 64480573Smjacob } else { 64580573Smjacob save_bufp->flags &= ~BUF_PIN; 64680573Smjacob return (ERROR); 64780573Smjacob } 64880573Smjacob } 64980573Smjacob 650198382Smav /* Not found */ 65180573Smjacob switch (action) { 65280573Smjacob case HASH_PUT: 65342650Sgibbs case HASH_PUTNEW: 65442650Sgibbs if (__addel(hashp, rbufp, key, val)) { 65542650Sgibbs save_bufp->flags &= ~BUF_PIN; 65642650Sgibbs return (ERROR); 65742650Sgibbs } else { 65842650Sgibbs save_bufp->flags &= ~BUF_PIN; 65942650Sgibbs return (SUCCESS); 66042650Sgibbs } 66142650Sgibbs case HASH_GET: 66242650Sgibbs case HASH_DELETE: 66342650Sgibbs default: 66442650Sgibbs save_bufp->flags &= ~BUF_PIN; 66542650Sgibbs return (ABNORMAL); 66642650Sgibbs } 66742650Sgibbs 66856594Smjacobfound: 66956594Smjacob switch (action) { 67056594Smjacob case HASH_PUTNEW: 67156594Smjacob save_bufp->flags &= ~BUF_PIN; 67256594Smjacob return (ABNORMAL); 67356594Smjacob case HASH_GET: 67456594Smjacob bp = (uint16_t *)(void *)rbufp->page; 67556594Smjacob if (bp[ndx + 1] < REAL_KEY) { 67656594Smjacob if (__big_return(hashp, rbufp, ndx, val, 0)) 67780573Smjacob return (ERROR); 67880573Smjacob } else { 67980573Smjacob val->data = (uint8_t *)rbufp->page + (int)bp[ndx + 1]; 68080573Smjacob val->size = bp[ndx] - bp[ndx + 1]; 68180573Smjacob } 68280573Smjacob break; 68380573Smjacob case HASH_PUT: 68480573Smjacob if ((__delpair(hashp, rbufp, ndx)) || 68580573Smjacob (__addel(hashp, rbufp, key, val))) { 68680573Smjacob save_bufp->flags &= ~BUF_PIN; 68780573Smjacob return (ERROR); 68880573Smjacob } 68980573Smjacob break; 69080573Smjacob case HASH_DELETE: 69180573Smjacob if (__delpair(hashp, rbufp, ndx)) 69280573Smjacob return (ERROR); 69342650Sgibbs /* 69442650Sgibbs * Our index lags 2 behind on the same page when we are 69542650Sgibbs * deleting the element pointed to by the index; otherwise 69642650Sgibbs * deleting randomly from an iterated hash produces undefined 69742650Sgibbs * results. 69842650Sgibbs */ 69942650Sgibbs if (ndx != hashp->cndx - 2 || rbufp != hashp->cpage) 70042650Sgibbs break; 70142650Sgibbs 70242650Sgibbs if (hashp->cndx > 1) { 70342650Sgibbs /* Move back one element */ 70442650Sgibbs hashp->cndx -= 2; 70542650Sgibbs } else { 70642650Sgibbs /* 70742650Sgibbs * Move back one page, and indicate to go to the last 70842650Sgibbs * element of the previous page by setting cndx to -1 70942650Sgibbs */ 710147723Savatar hashp->cbucket--; 71142650Sgibbs hashp->cpage = NULL; 71242650Sgibbs hashp->cndx = -1; 71342650Sgibbs } 71442650Sgibbs break; 71542650Sgibbs default: 71680573Smjacob abort(); 71780573Smjacob } 71880573Smjacob save_bufp->flags &= ~BUF_PIN; 71942650Sgibbs return (SUCCESS); 72042650Sgibbs} 72142650Sgibbs 722147723Savatarstatic int 72380573Smjacobhash_seq(const DB *dbp, DBT *key, DBT *data, uint32_t flag) 72480573Smjacob{ 72580573Smjacob uint32_t bucket; 72642650Sgibbs BUFHEAD *bufp = NULL; /* XXX: gcc */ 72780573Smjacob HTAB *hashp; 72880573Smjacob uint16_t *bp, ndx; 72980573Smjacob 73080573Smjacob hashp = dbp->internal; 73180573Smjacob if (flag && flag != R_FIRST && flag != R_NEXT) { 73280573Smjacob hashp->err = errno = EINVAL; 73342650Sgibbs return (ERROR); 73442650Sgibbs } 73544503Sgibbs#ifdef HASH_STATISTICS 73644503Sgibbs hash_accesses++; 73744503Sgibbs#endif 73842650Sgibbs if ((hashp->cbucket < 0) || (flag == R_FIRST)) { 73942650Sgibbs hashp->cbucket = 0; 74042650Sgibbs hashp->cndx = 1; 74144503Sgibbs hashp->cpage = NULL; 74242650Sgibbs } 74342650Sgibbs 74442650Sgibbsnext_bucket: 74542650Sgibbs for (bp = NULL; !bp || !bp[0]; ) { 74642650Sgibbs if (!(bufp = hashp->cpage)) { 74744503Sgibbs for (bucket = hashp->cbucket; 74842650Sgibbs bucket <= (uint32_t)hashp->MAX_BUCKET; 74942650Sgibbs bucket++) { 75042650Sgibbs bufp = __get_buf(hashp, bucket, NULL, 0); 75142650Sgibbs if (!bufp) 75242650Sgibbs return (ERROR); 75342650Sgibbs hashp->cpage = bufp; 75442650Sgibbs bp = (uint16_t *)(void *)bufp->page; 75542650Sgibbs if (bp[0]) 756147723Savatar break; 75742650Sgibbs } 75842650Sgibbs hashp->cbucket = bucket; 75942650Sgibbs if (hashp->cbucket > hashp->MAX_BUCKET) { 76042650Sgibbs hashp->cbucket = -1; 76142650Sgibbs return (ABNORMAL); 76242650Sgibbs } 763147723Savatar if (hashp->cndx == -1) { 76442650Sgibbs /* move to the last element of the page */ 765147723Savatar hashp->cndx = 1; 76642650Sgibbs while (bp[hashp->cndx - 1] != 0) 76742650Sgibbs hashp->cndx += 2; 76842650Sgibbs } else { 76942650Sgibbs /* start on the first element */ 77042650Sgibbs hashp->cndx = 1; 77142650Sgibbs } 77242650Sgibbs } else { 77342650Sgibbs bp = (uint16_t *)(void *)bufp->page; 77442650Sgibbs if (flag == R_NEXT || flag == 0) { 775147723Savatar if (hashp->cndx > bp[0]) { 776147723Savatar hashp->cpage = NULL; 77742650Sgibbs hashp->cbucket++; 778 hashp->cndx = 1; 779 goto next_bucket; 780 } 781 } 782 } 783 784 785 _DIAGASSERT(bp != NULL); 786 _DIAGASSERT(bufp != NULL); 787 while (bp[hashp->cndx + 1] == OVFLPAGE) { 788 bufp = hashp->cpage = 789 __get_buf(hashp, (uint32_t)bp[hashp->cndx], bufp, 790 0); 791 if (!bufp) 792 return (ERROR); 793 bp = (uint16_t *)(void *)(bufp->page); 794 hashp->cndx = 1; 795 } 796 if (!bp[0]) { 797 hashp->cpage = NULL; 798 ++hashp->cbucket; 799 } 800 } 801 ndx = hashp->cndx; 802 if (bp[ndx + 1] < REAL_KEY) { 803 if (__big_keydata(hashp, bufp, key, data, 1)) 804 return (ERROR); 805 hashp->cndx = 1; 806 } else { 807 if (hashp->cpage == NULL) 808 return (ERROR); 809 key->data = (uint8_t *)hashp->cpage->page + bp[ndx]; 810 key->size = (ndx > 1 ? bp[ndx - 1] : HASH_BSIZE(hashp)) - bp[ndx]; 811 data->data = (uint8_t *)hashp->cpage->page + bp[ndx + 1]; 812 data->size = bp[ndx] - bp[ndx + 1]; 813 hashp->cndx += 2; 814 } 815 return (SUCCESS); 816} 817 818/********************************* UTILITIES ************************/ 819 820/* 821 * Returns: 822 * 0 ==> OK 823 * -1 ==> Error 824 */ 825int 826__expand_table(HTAB *hashp) 827{ 828 uint32_t old_bucket, new_bucket; 829 int new_segnum, spare_ndx; 830 size_t dirsize; 831 832#ifdef HASH_STATISTICS 833 hash_expansions++; 834#endif 835 new_bucket = ++hashp->MAX_BUCKET; 836 old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK); 837 838 new_segnum = new_bucket >> hashp->SSHIFT; 839 840 /* Check if we need a new segment */ 841 if (new_segnum >= hashp->nsegs) { 842 /* Check if we need to expand directory */ 843 if (new_segnum >= hashp->DSIZE) { 844 /* Reallocate directory */ 845 dirsize = hashp->DSIZE * sizeof(SEGMENT *); 846 if (!hash_realloc(&hashp->dir, dirsize, dirsize << 1)) 847 return (-1); 848 dirsize <<= 1; 849 _DBFIT(dirsize, uint32_t); 850 hashp->DSIZE = (uint32_t)dirsize; 851 } 852 if ((hashp->dir[new_segnum] = 853 calloc((size_t)hashp->SGSIZE, sizeof(SEGMENT))) == NULL) 854 return (-1); 855 hashp->exsegs++; 856 hashp->nsegs++; 857 } 858 /* 859 * If the split point is increasing (MAX_BUCKET's log base 2 860 * * increases), we need to copy the current contents of the spare 861 * split bucket to the next bucket. 862 */ 863 spare_ndx = __log2((uint32_t)(hashp->MAX_BUCKET + 1)); 864 if (spare_ndx > hashp->OVFL_POINT) { 865 hashp->SPARES[spare_ndx] = hashp->SPARES[hashp->OVFL_POINT]; 866 hashp->OVFL_POINT = spare_ndx; 867 } 868 869 if (new_bucket > (uint32_t)hashp->HIGH_MASK) { 870 /* Starting a new doubling */ 871 hashp->LOW_MASK = hashp->HIGH_MASK; 872 hashp->HIGH_MASK = new_bucket | hashp->LOW_MASK; 873 } 874 /* Relocate records to the new bucket */ 875 return (__split_page(hashp, old_bucket, new_bucket)); 876} 877 878/* 879 * If realloc guarantees that the pointer is not destroyed if the realloc 880 * fails, then this routine can go away. 881 */ 882static void * 883hash_realloc(SEGMENT **p_ptr, size_t oldsize, size_t newsize) 884{ 885 void *p; 886 887 if ((p = malloc(newsize)) != NULL) { 888 memmove(p, *p_ptr, oldsize); 889 memset((char *)p + oldsize, 0, newsize - oldsize); 890 free(*p_ptr); 891 *p_ptr = p; 892 } 893 return (p); 894} 895 896uint32_t 897__call_hash(HTAB *hashp, char *k, int len) 898{ 899 int n, bucket; 900 901 n = hashp->hash(k, (size_t)len); 902 bucket = n & hashp->HIGH_MASK; 903 if (bucket > hashp->MAX_BUCKET) 904 bucket = bucket & hashp->LOW_MASK; 905 return (bucket); 906} 907 908/* 909 * Allocate segment table. On error, destroy the table and set errno. 910 * 911 * Returns 0 on success 912 */ 913static int 914alloc_segs(HTAB *hashp, int nsegs) 915{ 916 int i; 917 SEGMENT store; 918 919 int save_errno; 920 921 hashp->dir = calloc((size_t)hashp->DSIZE, sizeof(SEGMENT *)); 922 if (hashp->dir == NULL) { 923 save_errno = errno; 924 (void)hdestroy(hashp); 925 errno = save_errno; 926 return (-1); 927 } 928 hashp->nsegs = nsegs; 929 if (nsegs == 0) 930 return 0; 931 /* Allocate segments */ 932 store = calloc((size_t)(nsegs << hashp->SSHIFT), sizeof(SEGMENT)); 933 if (store == NULL) { 934 save_errno = errno; 935 (void)hdestroy(hashp); 936 errno = save_errno; 937 return (-1); 938 } 939 for (i = 0; i < nsegs; i++) 940 hashp->dir[i] = &store[i << hashp->SSHIFT]; 941 return (0); 942} 943 944#if BYTE_ORDER == LITTLE_ENDIAN 945/* 946 * Hashp->hdr needs to be byteswapped. 947 */ 948static void 949swap_header_copy(HASHHDR *srcp, HASHHDR *destp) 950{ 951 size_t i; 952 953 P_32_COPY(srcp->magic, destp->magic); 954 P_32_COPY(srcp->version, destp->version); 955 P_32_COPY(srcp->lorder, destp->lorder); 956 P_32_COPY(srcp->bsize, destp->bsize); 957 P_32_COPY(srcp->bshift, destp->bshift); 958 P_32_COPY(srcp->dsize, destp->dsize); 959 P_32_COPY(srcp->ssize, destp->ssize); 960 P_32_COPY(srcp->sshift, destp->sshift); 961 P_32_COPY(srcp->ovfl_point, destp->ovfl_point); 962 P_32_COPY(srcp->last_freed, destp->last_freed); 963 P_32_COPY(srcp->max_bucket, destp->max_bucket); 964 P_32_COPY(srcp->high_mask, destp->high_mask); 965 P_32_COPY(srcp->low_mask, destp->low_mask); 966 P_32_COPY(srcp->ffactor, destp->ffactor); 967 P_32_COPY(srcp->nkeys, destp->nkeys); 968 P_32_COPY(srcp->hdrpages, destp->hdrpages); 969 P_32_COPY(srcp->h_charkey, destp->h_charkey); 970 for (i = 0; i < NCACHED; i++) { 971 P_32_COPY(srcp->spares[i], destp->spares[i]); 972 P_16_COPY(srcp->bitmaps[i], destp->bitmaps[i]); 973 } 974} 975 976static void 977swap_header(HTAB *hashp) 978{ 979 HASHHDR *hdrp; 980 size_t i; 981 982 hdrp = &hashp->hdr; 983 984 M_32_SWAP(hdrp->magic); 985 M_32_SWAP(hdrp->version); 986 M_32_SWAP(hdrp->lorder); 987 M_32_SWAP(hdrp->bsize); 988 M_32_SWAP(hdrp->bshift); 989 M_32_SWAP(hdrp->dsize); 990 M_32_SWAP(hdrp->ssize); 991 M_32_SWAP(hdrp->sshift); 992 M_32_SWAP(hdrp->ovfl_point); 993 M_32_SWAP(hdrp->last_freed); 994 M_32_SWAP(hdrp->max_bucket); 995 M_32_SWAP(hdrp->high_mask); 996 M_32_SWAP(hdrp->low_mask); 997 M_32_SWAP(hdrp->ffactor); 998 M_32_SWAP(hdrp->nkeys); 999 M_32_SWAP(hdrp->hdrpages); 1000 M_32_SWAP(hdrp->h_charkey); 1001 for (i = 0; i < NCACHED; i++) { 1002 M_32_SWAP(hdrp->spares[i]); 1003 M_16_SWAP(hdrp->bitmaps[i]); 1004 } 1005} 1006#endif 1007