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 * 3214287Spst * @(#)hash.h 8.3 (Berkeley) 5/31/94 3372092Sasmodai * $FreeBSD$ 341573Srgrimes */ 351573Srgrimes 361573Srgrimes/* Operations */ 371573Srgrimestypedef enum { 381573Srgrimes HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, HASH_FIRST, HASH_NEXT 391573Srgrimes} ACTION; 401573Srgrimes 411573Srgrimes/* Buffer Management structures */ 421573Srgrimestypedef struct _bufhead BUFHEAD; 431573Srgrimes 441573Srgrimesstruct _bufhead { 4514287Spst BUFHEAD *prev; /* LRU links */ 4614287Spst BUFHEAD *next; /* LRU links */ 4714287Spst BUFHEAD *ovfl; /* Overflow page buffer header */ 4814287Spst u_int32_t addr; /* Address of this page */ 4914287Spst char *page; /* Actual page data */ 5014287Spst char flags; 511573Srgrimes#define BUF_MOD 0x0001 521573Srgrimes#define BUF_DISK 0x0002 531573Srgrimes#define BUF_BUCKET 0x0004 541573Srgrimes#define BUF_PIN 0x0008 551573Srgrimes}; 561573Srgrimes 571573Srgrimes#define IS_BUCKET(X) ((X) & BUF_BUCKET) 581573Srgrimes 591573Srgrimestypedef BUFHEAD **SEGMENT; 601573Srgrimes 611573Srgrimes/* Hash Table Information */ 6214287Spsttypedef struct hashhdr { /* Disk resident portion */ 63189330Sdelphij int32_t magic; /* Magic NO for hash tables */ 64189330Sdelphij int32_t version; /* Version ID */ 6514287Spst u_int32_t lorder; /* Byte Order */ 66189330Sdelphij int32_t bsize; /* Bucket/Page Size */ 67189330Sdelphij int32_t bshift; /* Bucket shift */ 68189330Sdelphij int32_t dsize; /* Directory Size */ 69189330Sdelphij int32_t ssize; /* Segment Size */ 70189330Sdelphij int32_t sshift; /* Segment shift */ 71189330Sdelphij int32_t ovfl_point; /* Where overflow pages are being 7214287Spst * allocated */ 73189330Sdelphij int32_t last_freed; /* Last overflow page freed */ 74190484Sdelphij u_int32_t max_bucket; /* ID of Maximum bucket in use */ 75190484Sdelphij u_int32_t high_mask; /* Mask to modulo into entire table */ 76190484Sdelphij u_int32_t low_mask; /* Mask to modulo into lower half of 7714287Spst * table */ 78190484Sdelphij u_int32_t ffactor; /* Fill factor */ 79189330Sdelphij int32_t nkeys; /* Number of keys in hash table */ 80189330Sdelphij int32_t hdrpages; /* Size of table header */ 81189330Sdelphij int32_t h_charkey; /* value of hash(CHARKEY) */ 8214287Spst#define NCACHED 32 /* number of bit maps and spare 8314287Spst * points */ 84189330Sdelphij int32_t spares[NCACHED];/* spare pages for overflow */ 8514287Spst u_int16_t bitmaps[NCACHED]; /* address of overflow page 8614287Spst * bitmaps */ 871573Srgrimes} HASHHDR; 881573Srgrimes 8914287Spsttypedef struct htab { /* Memory resident data structure */ 9014287Spst HASHHDR hdr; /* Header */ 9114287Spst int nsegs; /* Number of allocated segments */ 9214287Spst int exsegs; /* Number of extra allocated 9314287Spst * segments */ 9414287Spst u_int32_t /* Hash function */ 9592905Sobrien (*hash)(const void *, size_t); 9614287Spst int flags; /* Flag values */ 9714287Spst int fp; /* File pointer */ 9814287Spst char *tmp_buf; /* Temporary Buffer for BIG data */ 9914287Spst char *tmp_key; /* Temporary Buffer for BIG keys */ 10014287Spst BUFHEAD *cpage; /* Current page */ 10114287Spst int cbucket; /* Current bucket */ 10214287Spst int cndx; /* Index of next item on cpage */ 10314287Spst int error; /* Error Number -- for DBM 10472092Sasmodai * compatibility */ 10514287Spst int new_file; /* Indicates if fd is backing store 10614287Spst * or no */ 10714287Spst int save_file; /* Indicates whether we need to flush 10814287Spst * file at 10914287Spst * exit */ 11014287Spst u_int32_t *mapp[NCACHED]; /* Pointers to page maps */ 11114287Spst int nmaps; /* Initial number of bitmaps */ 11214287Spst int nbufs; /* Number of buffers left to 11314287Spst * allocate */ 11414287Spst BUFHEAD bufhead; /* Header of buffer lru list */ 11514287Spst SEGMENT *dir; /* Hash Bucket directory */ 1161573Srgrimes} HTAB; 1171573Srgrimes 1181573Srgrimes/* 1191573Srgrimes * Constants 1201573Srgrimes */ 121206178Savg#define MAX_BSIZE 32768 /* 2^15 but should be 65536 */ 1221573Srgrimes#define MIN_BUFFERS 6 1231573Srgrimes#define MINHDRSIZE 512 1241573Srgrimes#define DEF_BUFSIZE 65536 /* 64 K */ 1251573Srgrimes#define DEF_BUCKET_SIZE 4096 1261573Srgrimes#define DEF_BUCKET_SHIFT 12 /* log2(BUCKET) */ 1271573Srgrimes#define DEF_SEGSIZE 256 1281573Srgrimes#define DEF_SEGSIZE_SHIFT 8 /* log2(SEGSIZE) */ 1291573Srgrimes#define DEF_DIRSIZE 256 1301573Srgrimes#define DEF_FFACTOR 65536 1311573Srgrimes#define MIN_FFACTOR 4 1321573Srgrimes#define SPLTMAX 8 1331573Srgrimes#define CHARKEY "%$sniglet^&" 1341573Srgrimes#define NUMKEY 1038583 1351573Srgrimes#define BYTE_SHIFT 3 1361573Srgrimes#define INT_TO_BYTE 2 1371573Srgrimes#define INT_BYTE_SHIFT 5 13814287Spst#define ALL_SET ((u_int32_t)0xFFFFFFFF) 1391573Srgrimes#define ALL_CLEAR 0 1401573Srgrimes 14114287Spst#define PTROF(X) ((BUFHEAD *)((ptrdiff_t)(X)&~0x3)) 14214287Spst#define ISMOD(X) ((u_int32_t)(ptrdiff_t)(X)&0x1) 14314287Spst#define DOMOD(X) ((X) = (char *)((ptrdiff_t)(X)|0x1)) 14414287Spst#define ISDISK(X) ((u_int32_t)(ptrdiff_t)(X)&0x2) 14514287Spst#define DODISK(X) ((X) = (char *)((ptrdiff_t)(X)|0x2)) 1461573Srgrimes 1471573Srgrimes#define BITS_PER_MAP 32 1481573Srgrimes 1491573Srgrimes/* Given the address of the beginning of a big map, clear/set the nth bit */ 1501573Srgrimes#define CLRBIT(A, N) ((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP))) 1511573Srgrimes#define SETBIT(A, N) ((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP))) 1521573Srgrimes#define ISSET(A, N) ((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP))) 1531573Srgrimes 1541573Srgrimes/* Overflow management */ 1551573Srgrimes/* 1561573Srgrimes * Overflow page numbers are allocated per split point. At each doubling of 1571573Srgrimes * the table, we can allocate extra pages. So, an overflow page number has 1581573Srgrimes * the top 5 bits indicate which split point and the lower 11 bits indicate 1591573Srgrimes * which page at that split point is indicated (pages within split points are 1601573Srgrimes * numberered starting with 1). 1611573Srgrimes */ 1621573Srgrimes 1631573Srgrimes#define SPLITSHIFT 11 1641573Srgrimes#define SPLITMASK 0x7FF 16514287Spst#define SPLITNUM(N) (((u_int32_t)(N)) >> SPLITSHIFT) 1661573Srgrimes#define OPAGENUM(N) ((N) & SPLITMASK) 16714287Spst#define OADDR_OF(S,O) ((u_int32_t)((u_int32_t)(S) << SPLITSHIFT) + (O)) 1681573Srgrimes 1691573Srgrimes#define BUCKET_TO_PAGE(B) \ 1701573Srgrimes (B) + hashp->HDRPAGES + ((B) ? hashp->SPARES[__log2((B)+1)-1] : 0) 1711573Srgrimes#define OADDR_TO_PAGE(B) \ 1721573Srgrimes BUCKET_TO_PAGE ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B)); 1731573Srgrimes 1741573Srgrimes/* 1751573Srgrimes * page.h contains a detailed description of the page format. 1761573Srgrimes * 1771573Srgrimes * Normally, keys and data are accessed from offset tables in the top of 1781573Srgrimes * each page which point to the beginning of the key and data. There are 1791573Srgrimes * four flag values which may be stored in these offset tables which indicate 1801573Srgrimes * the following: 1811573Srgrimes * 1821573Srgrimes * 1831573Srgrimes * OVFLPAGE Rather than a key data pair, this pair contains 1841573Srgrimes * the address of an overflow page. The format of 1851573Srgrimes * the pair is: 1861573Srgrimes * OVERFLOW_PAGE_NUMBER OVFLPAGE 1871573Srgrimes * 1881573Srgrimes * PARTIAL_KEY This must be the first key/data pair on a page 1891573Srgrimes * and implies that page contains only a partial key. 1901573Srgrimes * That is, the key is too big to fit on a single page 1911573Srgrimes * so it starts on this page and continues on the next. 1921573Srgrimes * The format of the page is: 1931573Srgrimes * KEY_OFF PARTIAL_KEY OVFL_PAGENO OVFLPAGE 1948870Srgrimes * 1951573Srgrimes * KEY_OFF -- offset of the beginning of the key 1961573Srgrimes * PARTIAL_KEY -- 1 1971573Srgrimes * OVFL_PAGENO - page number of the next overflow page 1981573Srgrimes * OVFLPAGE -- 0 1991573Srgrimes * 2001573Srgrimes * FULL_KEY This must be the first key/data pair on the page. It 2011573Srgrimes * is used in two cases. 2021573Srgrimes * 2031573Srgrimes * Case 1: 2041573Srgrimes * There is a complete key on the page but no data 2051573Srgrimes * (because it wouldn't fit). The next page contains 2061573Srgrimes * the data. 2071573Srgrimes * 2081573Srgrimes * Page format it: 2091573Srgrimes * KEY_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE 2101573Srgrimes * 2111573Srgrimes * KEY_OFF -- offset of the beginning of the key 2121573Srgrimes * FULL_KEY -- 2 2131573Srgrimes * OVFL_PAGENO - page number of the next overflow page 2141573Srgrimes * OVFLPAGE -- 0 2151573Srgrimes * 2161573Srgrimes * Case 2: 2171573Srgrimes * This page contains no key, but part of a large 2181573Srgrimes * data field, which is continued on the next page. 2191573Srgrimes * 2201573Srgrimes * Page format it: 2211573Srgrimes * DATA_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE 2221573Srgrimes * 2231573Srgrimes * KEY_OFF -- offset of the beginning of the data on 2241573Srgrimes * this page 2251573Srgrimes * FULL_KEY -- 2 2261573Srgrimes * OVFL_PAGENO - page number of the next overflow page 2271573Srgrimes * OVFLPAGE -- 0 2281573Srgrimes * 2298870Srgrimes * FULL_KEY_DATA 2301573Srgrimes * This must be the first key/data pair on the page. 2311573Srgrimes * There are two cases: 2321573Srgrimes * 2331573Srgrimes * Case 1: 2341573Srgrimes * This page contains a key and the beginning of the 2351573Srgrimes * data field, but the data field is continued on the 2361573Srgrimes * next page. 2371573Srgrimes * 2381573Srgrimes * Page format is: 2391573Srgrimes * KEY_OFF FULL_KEY_DATA OVFL_PAGENO DATA_OFF 2401573Srgrimes * 2411573Srgrimes * KEY_OFF -- offset of the beginning of the key 2421573Srgrimes * FULL_KEY_DATA -- 3 2431573Srgrimes * OVFL_PAGENO - page number of the next overflow page 2441573Srgrimes * DATA_OFF -- offset of the beginning of the data 2451573Srgrimes * 2461573Srgrimes * Case 2: 2471573Srgrimes * This page contains the last page of a big data pair. 2481573Srgrimes * There is no key, only the tail end of the data 2491573Srgrimes * on this page. 2501573Srgrimes * 2511573Srgrimes * Page format is: 2521573Srgrimes * DATA_OFF FULL_KEY_DATA <OVFL_PAGENO> <OVFLPAGE> 2531573Srgrimes * 2541573Srgrimes * DATA_OFF -- offset of the beginning of the data on 2551573Srgrimes * this page 2561573Srgrimes * FULL_KEY_DATA -- 3 2571573Srgrimes * OVFL_PAGENO - page number of the next overflow page 2581573Srgrimes * OVFLPAGE -- 0 2591573Srgrimes * 2601573Srgrimes * OVFL_PAGENO and OVFLPAGE are optional (they are 2611573Srgrimes * not present if there is no next page). 2621573Srgrimes */ 2631573Srgrimes 2641573Srgrimes#define OVFLPAGE 0 2651573Srgrimes#define PARTIAL_KEY 1 2661573Srgrimes#define FULL_KEY 2 2671573Srgrimes#define FULL_KEY_DATA 3 2681573Srgrimes#define REAL_KEY 4 2691573Srgrimes 2701573Srgrimes/* Short hands for accessing structure */ 2711573Srgrimes#define BSIZE hdr.bsize 2721573Srgrimes#define BSHIFT hdr.bshift 2731573Srgrimes#define DSIZE hdr.dsize 2741573Srgrimes#define SGSIZE hdr.ssize 2751573Srgrimes#define SSHIFT hdr.sshift 2761573Srgrimes#define LORDER hdr.lorder 2771573Srgrimes#define OVFL_POINT hdr.ovfl_point 2781573Srgrimes#define LAST_FREED hdr.last_freed 2791573Srgrimes#define MAX_BUCKET hdr.max_bucket 2801573Srgrimes#define FFACTOR hdr.ffactor 2811573Srgrimes#define HIGH_MASK hdr.high_mask 2821573Srgrimes#define LOW_MASK hdr.low_mask 2831573Srgrimes#define NKEYS hdr.nkeys 2841573Srgrimes#define HDRPAGES hdr.hdrpages 2851573Srgrimes#define SPARES hdr.spares 2861573Srgrimes#define BITMAPS hdr.bitmaps 2871573Srgrimes#define VERSION hdr.version 2881573Srgrimes#define MAGIC hdr.magic 2891573Srgrimes#define NEXT_FREE hdr.next_free 2901573Srgrimes#define H_CHARKEY hdr.h_charkey 291