00001 /*- 00002 * See the file LICENSE for redistribution information. 00003 * 00004 * Copyright (c) 1996, 1997, 1998, 1999, 2000 00005 * Sleepycat Software. All rights reserved. 00006 */ 00007 /* 00008 * Copyright (c) 1990, 1993, 1994 00009 * Margo Seltzer. All rights reserved. 00010 */ 00011 /* 00012 * Copyright (c) 1990, 1993, 1994 00013 * The Regents of the University of California. All rights reserved. 00014 * 00015 * This code is derived from software contributed to Berkeley by 00016 * Margo Seltzer. 00017 * 00018 * Redistribution and use in source and binary forms, with or without 00019 * modification, are permitted provided that the following conditions 00020 * are met: 00021 * 1. Redistributions of source code must retain the above copyright 00022 * notice, this list of conditions and the following disclaimer. 00023 * 2. Redistributions in binary form must reproduce the above copyright 00024 * notice, this list of conditions and the following disclaimer in the 00025 * documentation and/or other materials provided with the distribution. 00026 * 3. Neither the name of the University nor the names of its contributors 00027 * may be used to endorse or promote products derived from this software 00028 * without specific prior written permission. 00029 * 00030 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 00031 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 00032 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 00033 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 00034 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 00035 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 00036 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 00037 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 00038 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 00039 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 00040 * SUCH DAMAGE. 00041 * 00042 * $Id: hash_8h-source.html,v 1.1 2008年06月08日 10:19:12 sebdiaz Exp $ 00043 */ 00044 00045 /* Hash internal structure. */ 00046 typedef struct hash_t { 00047 db_pgno_t meta_pgno; /* Page number of the meta data page. */ 00048 u_int32_t h_ffactor; /* Fill factor. */ 00049 u_int32_t h_nelem; /* Number of elements. */ 00050 /* Hash function. */ 00051 u_int32_t (*h_hash) __P((const void *, u_int32_t)); 00052 } HASH; 00053 00054 /* Cursor structure definitions. */ 00055 typedef struct cursor_t { 00056 /* struct __dbc_internal */ 00057 __DBC_INTERNAL 00058 00059 /* Hash private part */ 00060 00061 /* Per-thread information */ 00062 DB_LOCK hlock; /* Metadata page lock. */ 00063 HMETA *hdr; /* Pointer to meta-data page. */ 00064 PAGE *split_buf; /* Temporary buffer for splits. */ 00065 00066 /* Hash cursor information */ 00067 db_pgno_t bucket; /* Bucket we are traversing. */ 00068 db_pgno_t lbucket; /* Bucket for which we are locked. */ 00069 db_indx_t dup_off; /* Offset within a duplicate set. */ 00070 db_indx_t dup_len; /* Length of current duplicate. */ 00071 db_indx_t dup_tlen; /* Total length of duplicate entry. */ 00072 u_int32_t seek_size; /* Number of bytes we need for add. */ 00073 db_pgno_t seek_found_page;/* Page on which we can insert. */ 00074 00075 #define H_CONTINUE 0x0001 /* Join--search strictly fwd for data */ 00076 #define H_DELETED 0x0002 /* Cursor item is deleted. */ 00077 #define H_DIRTY 0x0004 /* Meta-data page needs to be written */ 00078 #define H_DUPONLY 0x0008 /* Dups only; do not change key. */ 00079 #define H_EXPAND 0x0010 /* Table expanded. */ 00080 #define H_ISDUP 0x0020 /* Cursor is within duplicate set. */ 00081 #define H_NEXT_NODUP 0x0040 /* Get next non-dup entry. */ 00082 #define H_NOMORE 0x0080 /* No more entries in bucket. */ 00083 #define H_OK 0x0100 /* Request succeeded. */ 00084 u_int32_t flags; 00085 } HASH_CURSOR; 00086 00087 #define IS_VALID(C) ((C)->bucket != BUCKET_INVALID) 00088 00089 /* Test string. */ 00090 #define CHARKEY "%$sniglet^&" 00091 00092 /* Overflow management */ 00093 /* 00094 * The spares table indicates the page number at which each doubling begins. 00095 * From this page number we subtract the number of buckets already allocated 00096 * so that we can do a simple addition to calculate the page number here. 00097 */ 00098 #define BUCKET_TO_PAGE(I, B) ((B) + (I)->hdr->spares[CDB___db_log2((B)+1)]) 00099 00100 /* Constraints about number of pages and how much data goes on a page. */ 00101 00102 #define MAX_PAGES(H) UINT32_T_MAX 00103 #define MINFILL 4 00104 #define ISBIG(I, N) (((N) > ((I)->hdr->dbmeta.pagesize / MINFILL)) ? 1 : 0) 00105 00106 /* Shorthands for accessing structure */ 00107 #define NDX_INVALID 0xFFFF 00108 #define BUCKET_INVALID 0xFFFFFFFF 00109 00110 /* On page duplicates are stored as a string of size-data-size triples. */ 00111 #define DUP_SIZE(len) ((len) + 2 * sizeof(db_indx_t)) 00112 00113 /* Log messages types (these are subtypes within a record type) */ 00114 #define PAIR_KEYMASK 0x1 00115 #define PAIR_DATAMASK 0x2 00116 #define PAIR_DUPMASK 0x4 00117 #define PAIR_MASK 0xf 00118 #define PAIR_ISKEYBIG(N) (N & PAIR_KEYMASK) 00119 #define PAIR_ISDATABIG(N) (N & PAIR_DATAMASK) 00120 #define PAIR_ISDATADUP(N) (N & PAIR_DUPMASK) 00121 #define OPCODE_OF(N) (N & ~PAIR_MASK) 00122 00123 #define PUTPAIR 0x20 00124 #define DELPAIR 0x30 00125 #define PUTOVFL 0x40 00126 #define DELOVFL 0x50 00127 #define ALLOCPGNO 0x60 00128 #define DELPGNO 0x70 00129 #define SPLITOLD 0x80 00130 #define SPLITNEW 0x90 00131 00132 #include "hash_auto.h" 00133 #include "hash_ext.h" 00134 #include "db_am.h"