215 lines
7.2 KiB
C
215 lines
7.2 KiB
C
/*-
|
|
* Copyright (c) 1990, 1993, 1994
|
|
* The Regents of the University of California. All rights reserved.
|
|
*
|
|
* This code is derived from software contributed to Berkeley by
|
|
* Margo Seltzer.
|
|
*
|
|
* Redistribution and use in source and binary forms, with or without
|
|
* modification, are permitted provided that the following conditions
|
|
* are met:
|
|
* 1. Redistributions of source code must retain the above copyright
|
|
* notice, this list of conditions and the following disclaimer.
|
|
* 2. Redistributions in binary form must reproduce the above copyright
|
|
* notice, this list of conditions and the following disclaimer in the
|
|
* documentation and/or other materials provided with the distribution.
|
|
* 3. All advertising materials mentioning features or use of this software
|
|
* must display the following acknowledgement:
|
|
* This product includes software developed by the University of
|
|
* California, Berkeley and its contributors.
|
|
* 4. Neither the name of the University nor the names of its contributors
|
|
* may be used to endorse or promote products derived from this software
|
|
* without specific prior written permission.
|
|
*
|
|
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
|
|
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
|
|
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
|
|
* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
|
|
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
|
|
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
|
|
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
|
|
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
|
|
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
|
|
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
|
|
* SUCH DAMAGE.
|
|
*
|
|
* @(#)hash.h 8.4 (Berkeley) 11/2/95
|
|
*/
|
|
|
|
#include <sys/queue.h>
|
|
|
|
#include <mpool.h>
|
|
#include "compat.h"
|
|
|
|
/* Operations */
|
|
typedef enum {
|
|
HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, HASH_FIRST, HASH_NEXT
|
|
} ACTION;
|
|
|
|
/* cursor structure */
|
|
typedef struct cursor_t {
|
|
TAILQ_ENTRY(cursor_t) queue;
|
|
int (*get) __P((const DB *, struct cursor_t *, DBT *, DBT *, \
|
|
u_int32_t));
|
|
int (*delete) __P((const DB *, struct cursor_t *, u_int32_t));
|
|
pgno_t bucket;
|
|
pgno_t pgno;
|
|
indx_t ndx;
|
|
indx_t pgndx;
|
|
u_int16_t *pagep;
|
|
void *internal;
|
|
} CURSOR;
|
|
|
|
|
|
#define IS_BUCKET(X) ((X) & BUF_BUCKET)
|
|
#define IS_VALID(X) (!((X) & BUF_INVALID))
|
|
|
|
/* Hash Table Information */
|
|
typedef struct hashhdr { /* Disk resident portion */
|
|
int32_t magic; /* Magic NO for hash tables */
|
|
int32_t version; /* Version ID */
|
|
int32_t lorder; /* Byte Order */
|
|
int32_t bsize; /* Bucket/Page Size */
|
|
int32_t bshift; /* Bucket shift */
|
|
int32_t ovfl_point; /* Where overflow pages are being allocated */
|
|
int32_t last_freed; /* Last overflow page freed */
|
|
int32_t max_bucket; /* ID of Maximum bucket in use */
|
|
int32_t high_mask; /* Mask to modulo into entire table */
|
|
int32_t low_mask; /* Mask to modulo into lower half of table */
|
|
int32_t ffactor; /* Fill factor */
|
|
int32_t nkeys; /* Number of keys in hash table */
|
|
int32_t hdrpages; /* Size of table header */
|
|
int32_t h_charkey; /* value of hash(CHARKEY) */
|
|
#define NCACHED 32 /* number of bit maps and spare points */
|
|
int32_t spares[NCACHED];/* spare pages for overflow */
|
|
u_int16_t bitmaps[NCACHED]; /* address of overflow page bitmaps */
|
|
} HASHHDR;
|
|
|
|
typedef struct htab { /* Memory resident data structure */
|
|
TAILQ_HEAD(_cursor_queue, cursor_t) curs_queue;
|
|
HASHHDR hdr; /* Header */
|
|
u_int32_t (*hash) __P((const void *, size_t)); /* Hash Function */
|
|
int32_t flags; /* Flag values */
|
|
int32_t fp; /* File pointer */
|
|
char *fname; /* File path */
|
|
char *bigdata_buf; /* Temporary Buffer for BIG data */
|
|
int32_t bigdata_len; /* Length of bigdata_buf */
|
|
char *bigkey_buf; /* Temporary Buffer for BIG keys */
|
|
int32_t bigkey_len; /* Length of bigkey_buf */
|
|
u_int16_t *split_buf; /* Temporary buffer for splits */
|
|
CURSOR *seq_cursor; /* Cursor used for hash_seq */
|
|
int32_t errno; /* Error Number -- for DBM compatability */
|
|
int32_t new_file; /* Indicates if fd is backing store or no */
|
|
int32_t save_file; /* Indicates whether we need to flush file at
|
|
* exit */
|
|
u_int32_t *mapp[NCACHED];/* Pointers to page maps */
|
|
int32_t nmaps; /* Initial number of bitmaps */
|
|
MPOOL *mp; /* mpool for buffer management */
|
|
} HTAB;
|
|
|
|
/*
|
|
* Constants
|
|
*/
|
|
#define MAX_BSIZE 65536 /* 2^16 */
|
|
#define MIN_BUFFERS 6
|
|
#define MINHDRSIZE 512
|
|
#define DEF_CACHESIZE 65536
|
|
#define DEF_BUCKET_SIZE 4096
|
|
#define DEF_BUCKET_SHIFT 12 /* log2(BUCKET) */
|
|
#define DEF_SEGSIZE 256
|
|
#define DEF_SEGSIZE_SHIFT 8 /* log2(SEGSIZE) */
|
|
#define DEF_DIRSIZE 256
|
|
#define DEF_FFACTOR 65536
|
|
#define MIN_FFACTOR 4
|
|
#define SPLTMAX 8
|
|
#define CHARKEY "%$sniglet^&"
|
|
#define NUMKEY 1038583
|
|
#define BYTE_SHIFT 3
|
|
#define INT32_T_TO_BYTE 2
|
|
#define INT32_T_BYTE_SHIFT 5
|
|
#define ALL_SET ((u_int32_t)0xFFFFFFFF)
|
|
#define ALL_CLEAR 0
|
|
|
|
#define PTROF(X) ((BUFHEAD *)((ptr_t)(X)&~0x3))
|
|
#define ISMOD(X) ((ptr_t)(X)&0x1)
|
|
#define DOMOD(X) ((X) = (int8_t *)((ptr_t)(X)|0x1))
|
|
#define ISDISK(X) ((ptr_t)(X)&0x2)
|
|
#define DODISK(X) ((X) = (int8_t *)((ptr_t)(X)|0x2))
|
|
|
|
#define BITS_PER_MAP 32
|
|
|
|
/* Given the address of the beginning of a big map, clear/set the nth bit */
|
|
#define CLRBIT(A, N) ((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP)))
|
|
#define SETBIT(A, N) ((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP)))
|
|
#define ISSET(A, N) ((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP)))
|
|
|
|
/* Overflow management */
|
|
/*
|
|
* Overflow page numbers are allocated per split point. At each doubling of
|
|
* the table, we can allocate extra pages. So, an overflow page number has
|
|
* the top 5 bits indicate which split point and the lower 11 bits indicate
|
|
* which page at that split point is indicated (pages within split points are
|
|
* numberered starting with 1).
|
|
*/
|
|
|
|
#define SPLITSHIFT 11
|
|
#define SPLITMASK 0x7FF
|
|
#define SPLITNUM(N) (((u_int32_t)(N)) >> SPLITSHIFT)
|
|
#define OPAGENUM(N) ((N) & SPLITMASK)
|
|
#define OADDR_OF(S,O) ((u_int32_t)((u_int32_t)(S) << SPLITSHIFT) + (O))
|
|
|
|
#define BUCKET_TO_PAGE(B) \
|
|
((B) + hashp->hdr.hdrpages + ((B) \
|
|
? hashp->hdr.spares[__log2((B)+1)-1] : 0))
|
|
#define OADDR_TO_PAGE(B) \
|
|
(BUCKET_TO_PAGE ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B)))
|
|
|
|
#define POW2(N) (1 << (N))
|
|
|
|
/*
|
|
* There is no portable way to figure out the maximum value of a file
|
|
* offset, so we put it here.
|
|
*/
|
|
#ifdef OFF_T_MAX
|
|
#define DB_OFF_T_MAX OFF_T_MAX
|
|
#else
|
|
#ifdef LONG_MAX
|
|
#define DB_OFF_T_MAX LONG_MAX
|
|
#else
|
|
#define DB_OFF_T_MAX 0xffffffff
|
|
#endif
|
|
#endif
|
|
|
|
#define MAX_PAGES(H) (DB_OFF_T_MAX / (H)->hdr.bsize)
|
|
|
|
/* Shorthands for accessing structure */
|
|
#define METADATA_PGNO 0
|
|
#define SPLIT_PGNO 0xFFFF
|
|
|
|
typedef struct item_info {
|
|
pgno_t pgno;
|
|
pgno_t bucket;
|
|
indx_t ndx;
|
|
indx_t pgndx;
|
|
u_int8_t status;
|
|
int32_t seek_size;
|
|
pgno_t seek_found_page;
|
|
indx_t key_off;
|
|
indx_t data_off;
|
|
u_int8_t caused_expand;
|
|
} ITEM_INFO;
|
|
|
|
|
|
#define ITEM_ERROR 0
|
|
#define ITEM_OK 1
|
|
#define ITEM_NO_MORE 2
|
|
|
|
#define ITEM_GET_FIRST 0
|
|
#define ITEM_GET_NEXT 1
|
|
#define ITEM_GET_RESET 2
|
|
#define ITEM_GET_DONE 3
|
|
#define ITEM_GET_N 4
|
|
|
|
#define UNKNOWN 0xffffffff /* for num_items */
|
|
#define NO_EXPAND 0xfffffffe
|