gonzui


Format: Advanced Search

t2ex/bsd_source/lib/libc/src_bsd/search/hash.hbare sourcepermlink (0.03 seconds)

Search this content:

    1: /*      $OpenBSD: hash.h,v 1.9 2004/06/21 23:13:22 marc Exp $        */
    2: 
    3: /*-
    4:  * Copyright (c) 1990, 1993, 1994
    5:  *      The Regents of the University of California.  All rights reserved.
    6:  *
    7:  * This code is derived from software contributed to Berkeley by
    8:  * Margo Seltzer.
    9:  *
   10:  * Redistribution and use in source and binary forms, with or without
   11:  * modification, are permitted provided that the following conditions
   12:  * are met:
   13:  * 1. Redistributions of source code must retain the above copyright
   14:  *    notice, this list of conditions and the following disclaimer.
   15:  * 2. Redistributions in binary form must reproduce the above copyright
   16:  *    notice, this list of conditions and the following disclaimer in the
   17:  *    documentation and/or other materials provided with the distribution.
   18:  * 3. Neither the name of the University nor the names of its contributors
   19:  *    may be used to endorse or promote products derived from this software
   20:  *    without specific prior written permission.
   21:  *
   22:  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
   23:  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   24:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   25:  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
   26:  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   27:  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   28:  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   29:  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   30:  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   31:  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   32:  * SUCH DAMAGE.
   33:  *
   34:  *      @(#)hash.h   8.3 (Berkeley) 5/31/94
   35:  */
   36: 
   37: /* Operations */
   38: typedef enum {
   39:         HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, HASH_FIRST, HASH_NEXT
   40: } ACTION;
   41: 
   42: /* Buffer Management structures */
   43: typedef struct _bufhead BUFHEAD;
   44: 
   45: struct _bufhead {
   46:         BUFHEAD                *prev;                /* LRU links */
   47:         BUFHEAD                *next;                /* LRU links */
   48:         BUFHEAD                *ovfl;                /* Overflow page buffer header */
   49:         u_int32_t       addr;               /* Address of this page */
   50:         char           *page;           /* Actual page data */
   51:         char     flags;
   52: #define BUF_MOD         0x0001
   53: #define BUF_DISK        0x0002
   54: #define BUF_BUCKET      0x0004
   55: #define BUF_PIN         0x0008
   56: };
   57: 
   58: #define IS_BUCKET(X)    ((X) & BUF_BUCKET)
   59: 
   60: typedef BUFHEAD **SEGMENT;
   61: 
   62: /* Hash Table Information */
   63: typedef struct hashhdr {                /* Disk resident portion */
   64:         int32_t                magic;                /* Magic NO for hash tables */
   65:         int32_t                version;      /* Version ID */
   66:         u_int32_t      lorder;              /* Byte Order */
   67:         int32_t                bsize;                /* Bucket/Page Size */
   68:         int32_t                bshift;               /* Bucket shift */
   69:         int32_t                dsize;                /* Directory Size */
   70:         int32_t                ssize;                /* Segment Size */
   71:         int32_t                sshift;               /* Segment shift */
   72:         int32_t                ovfl_point;   /* Where overflow pages are being 
   73:                                          * allocated */
   74:         int32_t                last_freed;   /* Last overflow page freed */
   75:         int32_t                max_bucket;   /* ID of Maximum bucket in use */
   76:         int32_t                high_mask;    /* Mask to modulo into entire table */
   77:         int32_t                low_mask;     /* Mask to modulo into lower half of 
   78:                                          * table */
   79:         int32_t                ffactor;      /* Fill factor */
   80:         int32_t                nkeys;                /* Number of keys in hash table */
   81:         int32_t                hdrpages;     /* Size of table header */
   82:         int32_t                h_charkey;    /* value of hash(CHARKEY) */
   83: #define NCACHED 32                      /* number of bit maps and spare 
   84:                                          * points */
   85:         int32_t                spares[NCACHED];/* spare pages for overflow */
   86:         u_int16_t      bitmaps[NCACHED];    /* address of overflow page 
   87:                                                  * bitmaps */
   88: } HASHHDR;
   89: 
   90: typedef struct htab      {          /* Memory resident data structure */
   91:         HASHHDR        hdr;          /* Header */
   92:         int            nsegs;            /* Number of allocated segments */
   93:         int            exsegs;           /* Number of extra allocated 
   94:                                          * segments */
   95:         u_int32_t                      /* Hash function */
   96:             (*hash)(const void *, size_t);
   97:         int            flags;            /* Flag values */
   98:         int            fp;               /* File pointer */
   99:         char           *tmp_buf;        /* Temporary Buffer for BIG data */
  100:         char           *tmp_key;        /* Temporary Buffer for BIG keys */
  101:         BUFHEAD        *cpage;               /* Current page */
  102:         int            cbucket;  /* Current bucket */
  103:         int            cndx;             /* Index of next item on cpage */
  104:         int            err;              /* Error Number -- for DBM 
  105:                                          * compatibility */
  106:         int            new_file; /* Indicates if fd is backing store 
  107:                                          * or no */
  108:         int            save_file;        /* Indicates whether we need to flush 
  109:                                          * file at
  110:                                          * exit */
  111:         u_int32_t      *mapp[NCACHED];      /* Pointers to page maps */
  112:         int            nmaps;            /* Initial number of bitmaps */
  113:         int            nbufs;            /* Number of buffers left to 
  114:                                          * allocate */
  115:         BUFHEAD        bufhead;      /* Header of buffer lru list */
  116:         SEGMENT        *dir;         /* Hash Bucket directory */
  117: } HTAB;
  118: 
  119: /*
  120:  * Constants
  121:  */
  122: #define MAX_BSIZE               65536                /* 2^16 */
  123: #define MIN_BUFFERS             6
  124: #define MINHDRSIZE              512
  125: #define DEF_BUFSIZE             65536              /* 64 K */
  126: #define DEF_BUCKET_SIZE         4096
  127: #define DEF_BUCKET_SHIFT        12             /* log2(BUCKET) */
  128: #define DEF_SEGSIZE             256
  129: #define DEF_SEGSIZE_SHIFT       8             /* log2(SEGSIZE)    */
  130: #define DEF_DIRSIZE             256
  131: #define DEF_FFACTOR             65536
  132: #define MIN_FFACTOR             4
  133: #define SPLTMAX                 8
  134: #define CHARKEY                 "%$sniglet^&"
  135: #define NUMKEY                  1038583
  136: #define BYTE_SHIFT              3
  137: #define INT_TO_BYTE             2
  138: #define INT_BYTE_SHIFT          5
  139: #define ALL_SET                 ((u_int32_t)0xFFFFFFFF)
  140: #define ALL_CLEAR               0
  141: 
  142: #define PTROF(X)        ((BUFHEAD *)((ptrdiff_t)(X)&~0x3))
  143: #define ISMOD(X)        ((u_int32_t)(ptrdiff_t)(X)&0x1)
  144: #define DOMOD(X)        ((X) = (char *)((ptrdiff_t)(X)|0x1))
  145: #define ISDISK(X)       ((u_int32_t)(ptrdiff_t)(X)&0x2)
  146: #define DODISK(X)       ((X) = (char *)((ptrdiff_t)(X)|0x2))
  147: 
  148: #define BITS_PER_MAP    32
  149: 
  150: /* Given the address of the beginning of a big map, clear/set the nth bit */
  151: #define CLRBIT(A, N)    ((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP)))
  152: #define SETBIT(A, N)    ((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP)))
  153: #define ISSET(A, N)     ((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP)))
  154: 
  155: /* Overflow management */
  156: /*
  157:  * Overflow page numbers are allocated per split point.  At each doubling of
  158:  * the table, we can allocate extra pages.  So, an overflow page number has
  159:  * the top 5 bits indicate which split point and the lower 11 bits indicate
  160:  * which page at that split point is indicated (pages within split points are
  161:  * numberered starting with 1).
  162:  */
  163: 
  164: #define SPLITSHIFT      11
  165: #define SPLITMASK       0x7FF
  166: #define SPLITNUM(N)     (((u_int32_t)(N)) >> SPLITSHIFT)
  167: #define OPAGENUM(N)     ((N) & SPLITMASK)
  168: #define OADDR_OF(S,O)   ((u_int32_t)((u_int32_t)(S) << SPLITSHIFT) + (O))
  169: 
  170: #define BUCKET_TO_PAGE(B) \
  171:         (B) + hashp->HDRPAGES + ((B) ? hashp->SPARES[__log2((B)+1)-1] : 0)
  172: #define OADDR_TO_PAGE(B)        \
  173:         BUCKET_TO_PAGE ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B));
  174: 
  175: /*
  176:  * page.h contains a detailed description of the page format.
  177:  *
  178:  * Normally, keys and data are accessed from offset tables in the top of
  179:  * each page which point to the beginning of the key and data.  There are
  180:  * four flag values which may be stored in these offset tables which indicate
  181:  * the following:
  182:  *
  183:  *
  184:  * OVFLPAGE     Rather than a key data pair, this pair contains
  185:  *              the address of an overflow page.  The format of
  186:  *              the pair is:
  187:  *                  OVERFLOW_PAGE_NUMBER OVFLPAGE
  188:  *
  189:  * PARTIAL_KEY  This must be the first key/data pair on a page
  190:  *              and implies that page contains only a partial key.
  191:  *              That is, the key is too big to fit on a single page
  192:  *              so it starts on this page and continues on the next.
  193:  *              The format of the page is:
  194:  *                  KEY_OFF PARTIAL_KEY OVFL_PAGENO OVFLPAGE
  195:  *              
  196:  *                  KEY_OFF -- offset of the beginning of the key
  197:  *                  PARTIAL_KEY -- 1
  198:  *                  OVFL_PAGENO - page number of the next overflow page
  199:  *                  OVFLPAGE -- 0
  200:  *
  201:  * FULL_KEY     This must be the first key/data pair on the page.  It
  202:  *              is used in two cases.
  203:  *
  204:  *              Case 1:
  205:  *                  There is a complete key on the page but no data
  206:  *                  (because it wouldn't fit).  The next page contains
  207:  *                  the data.
  208:  *
  209:  *                  Page format it:
  210:  *                  KEY_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
  211:  *
  212:  *                  KEY_OFF -- offset of the beginning of the key
  213:  *                  FULL_KEY -- 2
  214:  *                  OVFL_PAGENO - page number of the next overflow page
  215:  *                  OVFLPAGE -- 0
  216:  *
  217:  *              Case 2:
  218:  *                  This page contains no key, but part of a large
  219:  *                  data field, which is continued on the next page.
  220:  *
  221:  *                  Page format it:
  222:  *                  DATA_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
  223:  *
  224:  *                  KEY_OFF -- offset of the beginning of the data on
  225:  *                              this page
  226:  *                  FULL_KEY -- 2
  227:  *                  OVFL_PAGENO - page number of the next overflow page
  228:  *                  OVFLPAGE -- 0
  229:  *
  230:  * FULL_KEY_DATA 
  231:  *              This must be the first key/data pair on the page.
  232:  *              There are two cases:
  233:  *
  234:  *              Case 1:
  235:  *                  This page contains a key and the beginning of the
  236:  *                  data field, but the data field is continued on the
  237:  *                  next page.
  238:  *
  239:  *                  Page format is:
  240:  *                  KEY_OFF FULL_KEY_DATA OVFL_PAGENO DATA_OFF
  241:  *
  242:  *                  KEY_OFF -- offset of the beginning of the key
  243:  *                  FULL_KEY_DATA -- 3
  244:  *                  OVFL_PAGENO - page number of the next overflow page
  245:  *                  DATA_OFF -- offset of the beginning of the data
  246:  *
  247:  *              Case 2:
  248:  *                  This page contains the last page of a big data pair.
  249:  *                  There is no key, only the  tail end of the data
  250:  *                  on this page.
  251:  *
  252:  *                  Page format is:
  253:  *                  DATA_OFF FULL_KEY_DATA <OVFL_PAGENO> <OVFLPAGE>
  254:  *
  255:  *                  DATA_OFF -- offset of the beginning of the data on
  256:  *                              this page
  257:  *                  FULL_KEY_DATA -- 3
  258:  *                  OVFL_PAGENO - page number of the next overflow page
  259:  *                  OVFLPAGE -- 0
  260:  *
  261:  *                  OVFL_PAGENO and OVFLPAGE are optional (they are
  262:  *                  not present if there is no next page).
  263:  */
  264: 
  265: #define OVFLPAGE        0
  266: #define PARTIAL_KEY     1
  267: #define FULL_KEY        2
  268: #define FULL_KEY_DATA   3
  269: #define REAL_KEY        4
  270: 
  271: /* Short hands for accessing structure */
  272: #define BSIZE           hdr.bsize
  273: #define BSHIFT          hdr.bshift
  274: #define DSIZE           hdr.dsize
  275: #define SGSIZE          hdr.ssize
  276: #define SSHIFT          hdr.sshift
  277: #define LORDER          hdr.lorder
  278: #define OVFL_POINT      hdr.ovfl_point
  279: #define LAST_FREED      hdr.last_freed
  280: #define MAX_BUCKET      hdr.max_bucket
  281: #define FFACTOR         hdr.ffactor
  282: #define HIGH_MASK       hdr.high_mask
  283: #define LOW_MASK        hdr.low_mask
  284: #define NKEYS           hdr.nkeys
  285: #define HDRPAGES        hdr.hdrpages
  286: #define SPARES          hdr.spares
  287: #define BITMAPS         hdr.bitmaps
  288: #define VERSION         hdr.version
  289: #define MAGIC           hdr.magic
  290: #define NEXT_FREE       hdr.next_free
  291: #define H_CHARKEY       hdr.h_charkey