diff options
Diffstat (limited to 'src/plugins/kdb/db2/libdb2/hash/hash.h')
-rw-r--r-- | src/plugins/kdb/db2/libdb2/hash/hash.h | 196 |
1 files changed, 196 insertions, 0 deletions
diff --git a/src/plugins/kdb/db2/libdb2/hash/hash.h b/src/plugins/kdb/db2/libdb2/hash/hash.h new file mode 100644 index 0000000..b202fc9 --- /dev/null +++ b/src/plugins/kdb/db2/libdb2/hash/hash.h @@ -0,0 +1,196 @@ +/*- + * 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 "mpool.h" +#include "db-queue.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)); + db_pgno_t bucket; + db_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 */ + const char *fname; /* File path */ + u_int8_t *bigdata_buf; /* Temporary Buffer for BIG data */ + u_int8_t *bigkey_buf; /* Temporary Buffer for BIG keys */ + u_int16_t *split_buf; /* Temporary buffer for splits */ + CURSOR *seq_cursor; /* Cursor used for hash_seq */ + int32_t local_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_SHIFT 12 /* log2(BUCKET) */ +#define DEF_BUCKET_SIZE (1<<DEF_BUCKET_SHIFT) +#define DEF_SEGSIZE_SHIFT 8 /* log2(SEGSIZE) */ +#define DEF_SEGSIZE (1<<DEF_SEGSIZE_SHIFT) +#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)) + +#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 { + db_pgno_t pgno; + db_pgno_t bucket; + indx_t ndx; + indx_t pgndx; + u_int8_t status; + int32_t seek_size; + db_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 |