1/*- 2 * See the file LICENSE for redistribution information. 3 * 4 * Copyright (c) 1996,2008 Oracle. All rights reserved. 5 */ 6/* 7 * Copyright (c) 1990, 1993, 1994 8 * Margo Seltzer. All rights reserved. 9 */ 10/* 11 * Copyright (c) 1990, 1993, 1994 12 * The Regents of the University of California. All rights reserved. 13 * 14 * This code is derived from software contributed to Berkeley by 15 * Margo Seltzer. 16 * 17 * Redistribution and use in source and binary forms, with or without 18 * modification, are permitted provided that the following conditions 19 * are met: 20 * 1. Redistributions of source code must retain the above copyright 21 * notice, this list of conditions and the following disclaimer. 22 * 2. Redistributions in binary form must reproduce the above copyright 23 * notice, this list of conditions and the following disclaimer in the 24 * documentation and/or other materials provided with the distribution. 25 * 3. Neither the name of the University nor the names of its contributors 26 * may be used to endorse or promote products derived from this software 27 * without specific prior written permission. 28 * 29 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 30 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 31 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 32 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 33 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 34 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 35 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 36 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 37 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 38 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 39 * SUCH DAMAGE. 40 * 41 * $Id: hash.h,v 12.12 2008/01/08 20:58:18 bostic Exp $ 42 */ 43 44#ifndef _DB_HASH_H_ 45#define _DB_HASH_H_ 46 47#if defined(__cplusplus) 48extern "C" { 49#endif 50 51/* Hash internal structure. */ 52typedef struct hash_t { 53 db_pgno_t meta_pgno; /* Page number of the meta data page. */ 54 u_int32_t h_ffactor; /* Fill factor. */ 55 u_int32_t h_nelem; /* Number of elements. */ 56 /* Hash and compare functions. */ 57 u_int32_t (*h_hash) __P((DB *, const void *, u_int32_t)); 58 int (*h_compare) __P((DB *, const DBT *, const DBT *)); 59} HASH; 60 61/* Cursor structure definitions. */ 62typedef struct cursor_t { 63 /* struct __dbc_internal */ 64 __DBC_INTERNAL 65 66 /* Hash private part */ 67 68 /* Per-thread information */ 69 DB_LOCK hlock; /* Metadata page lock. */ 70 HMETA *hdr; /* Pointer to meta-data page. */ 71 PAGE *split_buf; /* Temporary buffer for splits. */ 72 73 /* Hash cursor information */ 74 db_pgno_t bucket; /* Bucket we are traversing. */ 75 db_pgno_t lbucket; /* Bucket for which we are locked. */ 76 db_indx_t dup_off; /* Offset within a duplicate set. */ 77 db_indx_t dup_len; /* Length of current duplicate. */ 78 db_indx_t dup_tlen; /* Total length of duplicate entry. */ 79 u_int32_t seek_size; /* Number of bytes we need for add. */ 80 db_pgno_t seek_found_page;/* Page on which we can insert. */ 81 db_indx_t seek_found_indx;/* Insert position for item. */ 82 u_int32_t order; /* Relative order among deleted curs. */ 83 84#define H_CONTINUE 0x0001 /* Join--search strictly fwd for data */ 85#define H_DELETED 0x0002 /* Cursor item is deleted. */ 86#define H_DUPONLY 0x0004 /* Dups only; do not change key. */ 87#define H_EXPAND 0x0008 /* Table expanded. */ 88#define H_ISDUP 0x0010 /* Cursor is within duplicate set. */ 89#define H_NEXT_NODUP 0x0020 /* Get next non-dup entry. */ 90#define H_NOMORE 0x0040 /* No more entries in bucket. */ 91#define H_OK 0x0080 /* Request succeeded. */ 92 u_int32_t flags; 93} HASH_CURSOR; 94 95/* Test string. */ 96#define CHARKEY "%$sniglet^&" 97 98/* Overflow management */ 99/* 100 * The spares table indicates the page number at which each doubling begins. 101 * From this page number we subtract the number of buckets already allocated 102 * so that we can do a simple addition to calculate the page number here. 103 */ 104#define BS_TO_PAGE(bucket, spares) \ 105 ((bucket) + (spares)[__db_log2((bucket) + 1)]) 106#define BUCKET_TO_PAGE(I, B) (BS_TO_PAGE((B), (I)->hdr->spares)) 107 108/* Constraints about much data goes on a page. */ 109 110#define MINFILL 4 111#define ISBIG(I, N) (((N) > ((I)->hdr->dbmeta.pagesize / MINFILL)) ? 1 : 0) 112 113/* Shorthands for accessing structure */ 114#define NDX_INVALID 0xFFFF 115#define BUCKET_INVALID 0xFFFFFFFF 116 117/* On page duplicates are stored as a string of size-data-size triples. */ 118#define DUP_SIZE(len) ((len) + 2 * sizeof(db_indx_t)) 119 120/* Log messages types (these are subtypes within a record type) */ 121#define PAIR_KEYMASK 0x1 122#define PAIR_DATAMASK 0x2 123#define PAIR_DUPMASK 0x4 124#define PAIR_MASK 0xf 125#define PAIR_ISKEYBIG(N) (N & PAIR_KEYMASK) 126#define PAIR_ISDATABIG(N) (N & PAIR_DATAMASK) 127#define PAIR_ISDATADUP(N) (N & PAIR_DUPMASK) 128#define OPCODE_OF(N) (N & ~PAIR_MASK) 129 130#define PUTPAIR 0x20 131#define DELPAIR 0x30 132#define PUTOVFL 0x40 133#define DELOVFL 0x50 134#define HASH_UNUSED1 0x60 135#define HASH_UNUSED2 0x70 136#define SPLITOLD 0x80 137#define SPLITNEW 0x90 138#define SORTPAGE 0x100 139 140/* Flags to control behavior of __ham_del_pair */ 141#define HAM_DEL_NO_CURSOR 0x01 /* Don't do any cursor adjustment */ 142#define HAM_DEL_NO_RECLAIM 0x02 /* Don't reclaim empty pages */ 143 144typedef enum { 145 DB_HAM_CURADJ_DEL = 1, 146 DB_HAM_CURADJ_ADD = 2, 147 DB_HAM_CURADJ_ADDMOD = 3, 148 DB_HAM_CURADJ_DELMOD = 4 149} db_ham_curadj; 150 151typedef enum { 152 DB_HAM_CHGPG = 1, 153 DB_HAM_DELFIRSTPG = 2, 154 DB_HAM_DELMIDPG = 3, 155 DB_HAM_DELLASTPG = 4, 156 DB_HAM_DUP = 5, 157 DB_HAM_SPLIT = 6 158} db_ham_mode; 159 160#if defined(__cplusplus) 161} 162#endif 163 164#include "dbinc_auto/hash_auto.h" 165#include "dbinc_auto/hash_ext.h" 166#include "dbinc/db_am.h" 167#endif /* !_DB_HASH_H_ */ 168