(libdb.so): Depend on libc.so for dynamic loading and for Linux ld.so.
[kopensolaris-gnu/glibc.git] / db / hash / hash.h
1 /*-
2  * Copyright (c) 1990, 1993, 1994
3  *      The Regents of the University of California.  All rights reserved.
4  *
5  * This code is derived from software contributed to Berkeley by
6  * Margo Seltzer.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  * 1. Redistributions of source code must retain the above copyright
12  *    notice, this list of conditions and the following disclaimer.
13  * 2. Redistributions in binary form must reproduce the above copyright
14  *    notice, this list of conditions and the following disclaimer in the
15  *    documentation and/or other materials provided with the distribution.
16  * 3. All advertising materials mentioning features or use of this software
17  *    must display the following acknowledgement:
18  *      This product includes software developed by the University of
19  *      California, Berkeley and its contributors.
20  * 4. Neither the name of the University nor the names of its contributors
21  *    may be used to endorse or promote products derived from this software
22  *    without specific prior written permission.
23  *
24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34  * SUCH DAMAGE.
35  *
36  *      @(#)hash.h      8.3 (Berkeley) 5/31/94
37  */
38
39 /* Operations */
40 typedef enum {
41         HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, HASH_FIRST, HASH_NEXT
42 } ACTION;
43
44 /* Buffer Management structures */
45 typedef struct _bufhead BUFHEAD;
46
47 struct _bufhead {
48         BUFHEAD         *prev;          /* LRU links */
49         BUFHEAD         *next;          /* LRU links */
50         BUFHEAD         *ovfl;          /* Overflow page buffer header */
51         u_int32_t        addr;          /* Address of this page */
52         char            *page;          /* Actual page data */
53         char            flags;
54 #define BUF_MOD         0x0001
55 #define BUF_DISK        0x0002
56 #define BUF_BUCKET      0x0004
57 #define BUF_PIN         0x0008
58 };
59
60 #define IS_BUCKET(X)    ((X) & BUF_BUCKET)
61
62 typedef BUFHEAD **SEGMENT;
63
64 /* Hash Table Information */
65 typedef struct hashhdr {                /* Disk resident portion */
66         int             magic;          /* Magic NO for hash tables */
67         int             version;        /* Version ID */
68         u_int32_t       lorder;         /* Byte Order */
69         int             bsize;          /* Bucket/Page Size */
70         int             bshift;         /* Bucket shift */
71         int             dsize;          /* Directory Size */
72         int             ssize;          /* Segment Size */
73         int             sshift;         /* Segment shift */
74         int             ovfl_point;     /* Where overflow pages are being
75                                          * allocated */
76         int             last_freed;     /* Last overflow page freed */
77         int             max_bucket;     /* ID of Maximum bucket in use */
78         int             high_mask;      /* Mask to modulo into entire table */
79         int             low_mask;       /* Mask to modulo into lower half of
80                                          * table */
81         int             ffactor;        /* Fill factor */
82         int             nkeys;          /* Number of keys in hash table */
83         int             hdrpages;       /* Size of table header */
84         int             h_charkey;      /* value of hash(CHARKEY) */
85 #define NCACHED 32                      /* number of bit maps and spare
86                                          * points */
87         int             spares[NCACHED];/* spare pages for overflow */
88         u_int16_t       bitmaps[NCACHED];       /* address of overflow page
89                                                  * bitmaps */
90 } HASHHDR;
91
92 typedef struct htab      {              /* Memory resident data structure */
93         HASHHDR         hdr;            /* Header */
94         int             nsegs;          /* Number of allocated segments */
95         int             exsegs;         /* Number of extra allocated
96                                          * segments */
97         u_int32_t                       /* Hash function */
98             (*hash)__P((const void *, size_t));
99         int             flags;          /* Flag values */
100         int             fp;             /* File pointer */
101         char            *tmp_buf;       /* Temporary Buffer for BIG data */
102         char            *tmp_key;       /* Temporary Buffer for BIG keys */
103         BUFHEAD         *cpage;         /* Current page */
104         int             cbucket;        /* Current bucket */
105         int             cndx;           /* Index of next item on cpage */
106         int             errnum;         /* Error Number -- for DBM
107                                          * compatibility */
108         int             new_file;       /* Indicates if fd is backing store
109                                          * or no */
110         int             save_file;      /* Indicates whether we need to flush
111                                          * file at
112                                          * exit */
113         u_int32_t       *mapp[NCACHED]; /* Pointers to page maps */
114         int             nmaps;          /* Initial number of bitmaps */
115         int             nbufs;          /* Number of buffers left to
116                                          * allocate */
117         BUFHEAD         bufhead;        /* Header of buffer lru list */
118         SEGMENT         *dir;           /* Hash Bucket directory */
119 } HTAB;
120
121 /*
122  * Constants
123  */
124 #define MAX_BSIZE               65536           /* 2^16 */
125 #define MIN_BUFFERS             6
126 #define MINHDRSIZE              512
127 #define DEF_BUFSIZE             65536           /* 64 K */
128 #define DEF_BUCKET_SIZE         4096
129 #define DEF_BUCKET_SHIFT        12              /* log2(BUCKET) */
130 #define DEF_SEGSIZE             256
131 #define DEF_SEGSIZE_SHIFT       8               /* log2(SEGSIZE)         */
132 #define DEF_DIRSIZE             256
133 #define DEF_FFACTOR             65536
134 #define MIN_FFACTOR             4
135 #define SPLTMAX                 8
136 #define CHARKEY                 "%$sniglet^&"
137 #define NUMKEY                  1038583
138 #define BYTE_SHIFT              3
139 #define INT_TO_BYTE             2
140 #define INT_BYTE_SHIFT          5
141 #define ALL_SET                 ((u_int32_t)0xFFFFFFFF)
142 #define ALL_CLEAR               0
143
144 #define PTROF(X)        ((BUFHEAD *)((ptrdiff_t)(X)&~0x3))
145 #define ISMOD(X)        ((u_int32_t)(ptrdiff_t)(X)&0x1)
146 #define DOMOD(X)        ((X) = (char *)((ptrdiff_t)(X)|0x1))
147 #define ISDISK(X)       ((u_int32_t)(ptrdiff_t)(X)&0x2)
148 #define DODISK(X)       ((X) = (char *)((ptrdiff_t)(X)|0x2))
149
150 #define BITS_PER_MAP    32
151
152 /* Given the address of the beginning of a big map, clear/set the nth bit */
153 #define CLRBIT(A, N)    ((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP)))
154 #define SETBIT(A, N)    ((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP)))
155 #define ISSET(A, N)     ((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP)))
156
157 /* Overflow management */
158 /*
159  * Overflow page numbers are allocated per split point.  At each doubling of
160  * the table, we can allocate extra pages.  So, an overflow page number has
161  * the top 5 bits indicate which split point and the lower 11 bits indicate
162  * which page at that split point is indicated (pages within split points are
163  * numberered starting with 1).
164  */
165
166 #define SPLITSHIFT      11
167 #define SPLITMASK       0x7FF
168 #define SPLITNUM(N)     (((u_int32_t)(N)) >> SPLITSHIFT)
169 #define OPAGENUM(N)     ((N) & SPLITMASK)
170 #define OADDR_OF(S,O)   ((u_int32_t)((u_int32_t)(S) << SPLITSHIFT) + (O))
171
172 #define BUCKET_TO_PAGE(B) \
173         (B) + hashp->HDRPAGES + ((B) ? hashp->SPARES[__log2((B)+1)-1] : 0)
174 #define OADDR_TO_PAGE(B)        \
175         BUCKET_TO_PAGE ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B));
176
177 /*
178  * page.h contains a detailed description of the page format.
179  *
180  * Normally, keys and data are accessed from offset tables in the top of
181  * each page which point to the beginning of the key and data.  There are
182  * four flag values which may be stored in these offset tables which indicate
183  * the following:
184  *
185  *
186  * OVFLPAGE     Rather than a key data pair, this pair contains
187  *              the address of an overflow page.  The format of
188  *              the pair is:
189  *                  OVERFLOW_PAGE_NUMBER OVFLPAGE
190  *
191  * PARTIAL_KEY  This must be the first key/data pair on a page
192  *              and implies that page contains only a partial key.
193  *              That is, the key is too big to fit on a single page
194  *              so it starts on this page and continues on the next.
195  *              The format of the page is:
196  *                  KEY_OFF PARTIAL_KEY OVFL_PAGENO OVFLPAGE
197  *
198  *                  KEY_OFF -- offset of the beginning of the key
199  *                  PARTIAL_KEY -- 1
200  *                  OVFL_PAGENO - page number of the next overflow page
201  *                  OVFLPAGE -- 0
202  *
203  * FULL_KEY     This must be the first key/data pair on the page.  It
204  *              is used in two cases.
205  *
206  *              Case 1:
207  *                  There is a complete key on the page but no data
208  *                  (because it wouldn't fit).  The next page contains
209  *                  the data.
210  *
211  *                  Page format it:
212  *                  KEY_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
213  *
214  *                  KEY_OFF -- offset of the beginning of the key
215  *                  FULL_KEY -- 2
216  *                  OVFL_PAGENO - page number of the next overflow page
217  *                  OVFLPAGE -- 0
218  *
219  *              Case 2:
220  *                  This page contains no key, but part of a large
221  *                  data field, which is continued on the next page.
222  *
223  *                  Page format it:
224  *                  DATA_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
225  *
226  *                  KEY_OFF -- offset of the beginning of the data on
227  *                              this page
228  *                  FULL_KEY -- 2
229  *                  OVFL_PAGENO - page number of the next overflow page
230  *                  OVFLPAGE -- 0
231  *
232  * FULL_KEY_DATA
233  *              This must be the first key/data pair on the page.
234  *              There are two cases:
235  *
236  *              Case 1:
237  *                  This page contains a key and the beginning of the
238  *                  data field, but the data field is continued on the
239  *                  next page.
240  *
241  *                  Page format is:
242  *                  KEY_OFF FULL_KEY_DATA OVFL_PAGENO DATA_OFF
243  *
244  *                  KEY_OFF -- offset of the beginning of the key
245  *                  FULL_KEY_DATA -- 3
246  *                  OVFL_PAGENO - page number of the next overflow page
247  *                  DATA_OFF -- offset of the beginning of the data
248  *
249  *              Case 2:
250  *                  This page contains the last page of a big data pair.
251  *                  There is no key, only the  tail end of the data
252  *                  on this page.
253  *
254  *                  Page format is:
255  *                  DATA_OFF FULL_KEY_DATA <OVFL_PAGENO> <OVFLPAGE>
256  *
257  *                  DATA_OFF -- offset of the beginning of the data on
258  *                              this page
259  *                  FULL_KEY_DATA -- 3
260  *                  OVFL_PAGENO - page number of the next overflow page
261  *                  OVFLPAGE -- 0
262  *
263  *                  OVFL_PAGENO and OVFLPAGE are optional (they are
264  *                  not present if there is no next page).
265  */
266
267 #define OVFLPAGE        0
268 #define PARTIAL_KEY     1
269 #define FULL_KEY        2
270 #define FULL_KEY_DATA   3
271 #define REAL_KEY        4
272
273 /* Short hands for accessing structure */
274 #define BSIZE           hdr.bsize
275 #define BSHIFT          hdr.bshift
276 #define DSIZE           hdr.dsize
277 #define SGSIZE          hdr.ssize
278 #define SSHIFT          hdr.sshift
279 #define LORDER          hdr.lorder
280 #define OVFL_POINT      hdr.ovfl_point
281 #define LAST_FREED      hdr.last_freed
282 #define MAX_BUCKET      hdr.max_bucket
283 #define FFACTOR         hdr.ffactor
284 #define HIGH_MASK       hdr.high_mask
285 #define LOW_MASK        hdr.low_mask
286 #define NKEYS           hdr.nkeys
287 #define HDRPAGES        hdr.hdrpages
288 #define SPARES          hdr.spares
289 #define BITMAPS         hdr.bitmaps
290 #define VERSION         hdr.version
291 #define MAGIC           hdr.magic
292 #define NEXT_FREE       hdr.next_free
293 #define H_CHARKEY       hdr.h_charkey