Update from db-2.3.12.
[kopensolaris-gnu/glibc.git] / db2 / include / hash.h
1 /*-
2  * See the file LICENSE for redistribution information.
3  *
4  * Copyright (c) 1996, 1997
5  *      Sleepycat Software.  All rights reserved.
6  */
7 /*
8  * Copyright (c) 1990, 1993, 1994
9  *      Margo Seltzer.  All rights reserved.
10  */
11 /*
12  * Copyright (c) 1990, 1993, 1994
13  *      The Regents of the University of California.  All rights reserved.
14  *
15  * This code is derived from software contributed to Berkeley by
16  * Margo Seltzer.
17  *
18  * Redistribution and use in source and binary forms, with or without
19  * modification, are permitted provided that the following conditions
20  * are met:
21  * 1. Redistributions of source code must retain the above copyright
22  *    notice, this list of conditions and the following disclaimer.
23  * 2. Redistributions in binary form must reproduce the above copyright
24  *    notice, this list of conditions and the following disclaimer in the
25  *    documentation and/or other materials provided with the distribution.
26  * 3. All advertising materials mentioning features or use of this software
27  *    must display the following acknowledgement:
28  *      This product includes software developed by the University of
29  *      California, Berkeley and its contributors.
30  * 4. Neither the name of the University nor the names of its contributors
31  *    may be used to endorse or promote products derived from this software
32  *    without specific prior written permission.
33  *
34  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
35  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
36  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
37  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
38  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
39  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
40  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
41  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
42  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
43  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
44  * SUCH DAMAGE.
45  *
46  *      @(#)hash.h      10.7 (Sleepycat) 11/1/97
47  */
48
49 /* Cursor structure definitions. */
50 typedef struct cursor_t {
51         DBC             *db_cursor;
52         db_pgno_t       bucket;         /* Bucket we are traversing. */
53         DB_LOCK         lock;           /* Lock held on the current bucket. */
54         PAGE            *pagep;         /* The current page. */
55         db_pgno_t       pgno;           /* Current page number. */
56         db_indx_t       bndx;           /* Index within the current page. */
57         PAGE            *dpagep;        /* Duplicate page pointer. */
58         db_pgno_t       dpgno;          /* Duplicate page number. */
59         db_indx_t       dndx;           /* Index within a duplicate set. */
60         db_indx_t       dup_off;        /* Offset within a duplicate set. */
61         db_indx_t       dup_len;        /* Length of current duplicate. */
62         db_indx_t       dup_tlen;       /* Total length of duplicate entry. */
63         u_int32_t       seek_size;      /* Number of bytes we need for add. */
64         db_pgno_t       seek_found_page;/* Page on which we can insert. */
65         u_int32_t       big_keylen;     /* Length of big_key buffer. */
66         void            *big_key;       /* Temporary buffer for big keys. */
67         u_int32_t       big_datalen;    /* Length of big_data buffer. */
68         void            *big_data;      /* Temporary buffer for big data. */
69 #define H_OK            0x0001
70 #define H_NOMORE        0x0002
71 #define H_DELETED       0x0004
72 #define H_ISDUP         0x0008
73 #define H_EXPAND        0x0020
74         u_int32_t       flags;          /* Is cursor inside a dup set. */
75 } HASH_CURSOR;
76
77 #define IS_VALID(C) ((C)->bucket != BUCKET_INVALID)
78
79
80 typedef struct htab {           /* Memory resident data structure. */
81         DB *dbp;                /* Pointer to parent db structure. */
82         DB_LOCK hlock;          /* Metadata page lock. */
83         HASHHDR *hdr;           /* Pointer to meta-data page. */
84         u_int32_t (*hash) __P((const void *, u_int32_t)); /* Hash Function */
85         PAGE *split_buf;        /* Temporary buffer for splits. */
86         int local_errno;        /* Error Number -- for DBM compatability */
87         u_long hash_accesses;   /* Number of accesses to this table. */
88         u_long hash_collisions; /* Number of collisions on search. */
89         u_long hash_expansions; /* Number of times we added a bucket. */
90         u_long hash_overflows;  /* Number of overflow pages. */
91         u_long hash_bigpages;   /* Number of big key/data pages. */
92 } HTAB;
93
94 /*
95  * Macro used for interface functions to set the txnid in the DBP.
96  */
97 #define SET_LOCKER(D, T) ((D)->txn = (T))
98
99 /*
100  * More interface macros used to get/release the meta data page.
101  */
102 #define GET_META(D, H) {                                                \
103         int _r;                                                         \
104         if (F_ISSET(D, DB_AM_LOCKING) && !F_ISSET(D, DB_AM_RECOVER)) {  \
105                 (D)->lock.pgno = BUCKET_INVALID;                        \
106                 if ((_r = lock_get((D)->dbenv->lk_info,                 \
107                     (D)->txn == NULL ? (D)->locker : (D)->txn->txnid,   \
108                     0, &(D)->lock_dbt, DB_LOCK_READ,                    \
109                     &(H)->hlock)) != 0)                                 \
110                         return (_r < 0 ? EAGAIN : _r);                  \
111         }                                                               \
112         if ((_r = __ham_get_page(D, 0, (PAGE **)&((H)->hdr))) != 0) {   \
113                 if ((H)->hlock) {                                       \
114                         (void)lock_put((D)->dbenv->lk_info, (H)->hlock);\
115                         (H)->hlock = 0;                                 \
116                 }                                                       \
117                 return (_r);                                            \
118         }                                                               \
119 }
120
121 #define RELEASE_META(D, H) {                                            \
122         if (!F_ISSET(D, DB_AM_RECOVER) &&                               \
123             (D)->txn == NULL && (H)->hlock)                             \
124                 (void)lock_put((H)->dbp->dbenv->lk_info, (H)->hlock);   \
125         (H)->hlock = 0;                                                 \
126         if ((H)->hdr)                                                   \
127                 (void)__ham_put_page(D, (PAGE *)(H)->hdr,               \
128                     F_ISSET(D, DB_HS_DIRTYMETA) ? 1 : 0);               \
129         (H)->hdr = NULL;                                                \
130         F_CLR(D, DB_HS_DIRTYMETA);                                      \
131 }
132
133 #define DIRTY_META(H, R) {                                              \
134         if (F_ISSET((H)->dbp, DB_AM_LOCKING) &&                         \
135             !F_ISSET((H)->dbp, DB_AM_RECOVER)) {                        \
136                 DB_LOCK _tmp;                                           \
137                 (H)->dbp->lock.pgno = BUCKET_INVALID;                   \
138                 if (((R) = lock_get((H)->dbp->dbenv->lk_info,           \
139                     (H)->dbp->txn ? (H)->dbp->txn->txnid :              \
140                     (H)->dbp->locker, 0, &(H)->dbp->lock_dbt,           \
141                     DB_LOCK_WRITE, &_tmp)) == 0)                        \
142                         (R) = lock_put((H)->dbp->dbenv->lk_info,        \
143                             (H)->hlock);                                \
144                 else if ((R) < 0)                                       \
145                         (R) = EAGAIN;                                   \
146                 (H)->hlock = _tmp;                                      \
147         }                                                               \
148         F_SET((H)->dbp, DB_HS_DIRTYMETA);                               \
149 }
150
151 /* Allocate and discard thread structures. */
152 #define H_GETHANDLE(dbp, dbpp, ret)                                     \
153         if (F_ISSET(dbp, DB_AM_THREAD))                                 \
154                 ret = __db_gethandle(dbp, __ham_hdup, dbpp);            \
155         else {                                                          \
156                 ret = 0;                                                \
157                 *dbpp = dbp;                                            \
158         }
159
160 #define H_PUTHANDLE(dbp) {                                              \
161         if (F_ISSET(dbp, DB_AM_THREAD))                                 \
162                 __db_puthandle(dbp);                                    \
163 }
164
165 /* Test string. */
166 #define CHARKEY                 "%$sniglet^&"
167
168 /* Overflow management */
169 /*
170  * Overflow page numbers are allocated per split point.  At each doubling of
171  * the table, we can allocate extra pages.  We keep track of how many pages
172  * we've allocated at each point to calculate bucket to page number mapping.
173  */
174 #define BUCKET_TO_PAGE(H, B) \
175         ((B) + 1 + ((B) ? (H)->hdr->spares[__db_log2((B)+1)-1] : 0))
176
177 #define PGNO_OF(H, S, O) (BUCKET_TO_PAGE((H), (1 << (S)) - 1) + (O))
178
179 /* Constraints about number of pages and how much data goes on a page. */
180
181 #define MAX_PAGES(H)    UINT32_T_MAX
182 #define MINFILL         4
183 #define ISBIG(H, N)     (((N) > ((H)->hdr->pagesize / MINFILL)) ? 1 : 0)
184
185 /* Shorthands for accessing structure */
186 #define NDX_INVALID     0xFFFF
187 #define BUCKET_INVALID  0xFFFFFFFF
188
189 /* On page duplicates are stored as a string of size-data-size triples. */
190 #define DUP_SIZE(len)   ((len) + 2 * sizeof(db_indx_t))
191
192 /* Log messages types (these are subtypes within a record type) */
193 #define PAIR_KEYMASK            0x1
194 #define PAIR_DATAMASK           0x2
195 #define PAIR_ISKEYBIG(N)        (N & PAIR_KEYMASK)
196 #define PAIR_ISDATABIG(N)       (N & PAIR_DATAMASK)
197 #define OPCODE_OF(N)            (N & ~(PAIR_KEYMASK | PAIR_DATAMASK))
198
199 #define PUTPAIR         0x20
200 #define DELPAIR         0x30
201 #define PUTOVFL         0x40
202 #define DELOVFL         0x50
203 #define ALLOCPGNO       0x60
204 #define DELPGNO         0x70
205 #define SPLITOLD        0x80
206 #define SPLITNEW        0x90
207
208 #include "hash_auto.h"
209 #include "hash_ext.h"
210 #include "db_am.h"
211 #include "common_ext.h"