source: trunk/src/emx/bsd/db/hash/hash.h@ 277

Last change on this file since 277 was 277, checked in by bird, 23 years ago

#357: Initial adjustments.
  • Property cvs2svn:cvs-rev set to 1.2
  • Property svn:eol-style set to native
  • Property svn:executable set to *
File size: 10.2 KB
Line 
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 */
40typedef enum {
41 HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, HASH_FIRST, HASH_NEXT
42} ACTION;
43
44/* Buffer Management structures */
45typedef struct _bufhead BUFHEAD;
46
47struct _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
62typedef BUFHEAD **SEGMENT;
63
64/* Hash Table Information */
65typedef 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
92typedef 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 /* bird: this used to be errno but that crashes with the errno define in errno.h and stdlib.h. */
107 int dbmerrno; /* Error Number -- for DBM
108 * compatability */
109 int new_file; /* Indicates if fd is backing store
110 * or no */
111 int save_file; /* Indicates whether we need to flush
112 * file at
113 * exit */
114 u_int32_t *mapp[NCACHED]; /* Pointers to page maps */
115 int nmaps; /* Initial number of bitmaps */
116 int nbufs; /* Number of buffers left to
117 * allocate */
118 BUFHEAD bufhead; /* Header of buffer lru list */
119 SEGMENT *dir; /* Hash Bucket directory */
120#ifdef __EMX__
121 char *tempname; /* Name of temporary file */
122#endif /* __EMX__ */
123} HTAB;
124
125/*
126 * Constants
127 */
128#define MAX_BSIZE 65536 /* 2^16 */
129#define MIN_BUFFERS 6
130#define MINHDRSIZE 512
131#define DEF_BUFSIZE 65536 /* 64 K */
132#define DEF_BUCKET_SIZE 4096
133#define DEF_BUCKET_SHIFT 12 /* log2(BUCKET) */
134#define DEF_SEGSIZE 256
135#define DEF_SEGSIZE_SHIFT 8 /* log2(SEGSIZE) */
136#define DEF_DIRSIZE 256
137#define DEF_FFACTOR 65536
138#define MIN_FFACTOR 4
139#define SPLTMAX 8
140#define CHARKEY "%$sniglet^&"
141#define NUMKEY 1038583
142#define BYTE_SHIFT 3
143#define INT_TO_BYTE 2
144#define INT_BYTE_SHIFT 5
145#define ALL_SET ((u_int32_t)0xFFFFFFFF)
146#define ALL_CLEAR 0
147
148#define PTROF(X) ((BUFHEAD *)((ptrdiff_t)(X)&~0x3))
149#define ISMOD(X) ((u_int32_t)(ptrdiff_t)(X)&0x1)
150#define DOMOD(X) ((X) = (char *)((ptrdiff_t)(X)|0x1))
151#define ISDISK(X) ((u_int32_t)(ptrdiff_t)(X)&0x2)
152#define DODISK(X) ((X) = (char *)((ptrdiff_t)(X)|0x2))
153
154#define BITS_PER_MAP 32
155
156/* Given the address of the beginning of a big map, clear/set the nth bit */
157#define CLRBIT(A, N) ((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP)))
158#define SETBIT(A, N) ((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP)))
159#define ISSET(A, N) ((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP)))
160
161/* Overflow management */
162/*
163 * Overflow page numbers are allocated per split point. At each doubling of
164 * the table, we can allocate extra pages. So, an overflow page number has
165 * the top 5 bits indicate which split point and the lower 11 bits indicate
166 * which page at that split point is indicated (pages within split points are
167 * numberered starting with 1).
168 */
169
170#define SPLITSHIFT 11
171#define SPLITMASK 0x7FF
172#define SPLITNUM(N) (((u_int32_t)(N)) >> SPLITSHIFT)
173#define OPAGENUM(N) ((N) & SPLITMASK)
174#define OADDR_OF(S,O) ((u_int32_t)((u_int32_t)(S) << SPLITSHIFT) + (O))
175
176#define BUCKET_TO_PAGE(B) \
177 (B) + hashp->HDRPAGES + ((B) ? hashp->SPARES[__log2((B)+1)-1] : 0)
178#define OADDR_TO_PAGE(B) \
179 BUCKET_TO_PAGE ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B));
180
181/*
182 * page.h contains a detailed description of the page format.
183 *
184 * Normally, keys and data are accessed from offset tables in the top of
185 * each page which point to the beginning of the key and data. There are
186 * four flag values which may be stored in these offset tables which indicate
187 * the following:
188 *
189 *
190 * OVFLPAGE Rather than a key data pair, this pair contains
191 * the address of an overflow page. The format of
192 * the pair is:
193 * OVERFLOW_PAGE_NUMBER OVFLPAGE
194 *
195 * PARTIAL_KEY This must be the first key/data pair on a page
196 * and implies that page contains only a partial key.
197 * That is, the key is too big to fit on a single page
198 * so it starts on this page and continues on the next.
199 * The format of the page is:
200 * KEY_OFF PARTIAL_KEY OVFL_PAGENO OVFLPAGE
201 *
202 * KEY_OFF -- offset of the beginning of the key
203 * PARTIAL_KEY -- 1
204 * OVFL_PAGENO - page number of the next overflow page
205 * OVFLPAGE -- 0
206 *
207 * FULL_KEY This must be the first key/data pair on the page. It
208 * is used in two cases.
209 *
210 * Case 1:
211 * There is a complete key on the page but no data
212 * (because it wouldn't fit). The next page contains
213 * the data.
214 *
215 * Page format it:
216 * KEY_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
217 *
218 * KEY_OFF -- offset of the beginning of the key
219 * FULL_KEY -- 2
220 * OVFL_PAGENO - page number of the next overflow page
221 * OVFLPAGE -- 0
222 *
223 * Case 2:
224 * This page contains no key, but part of a large
225 * data field, which is continued on the next page.
226 *
227 * Page format it:
228 * DATA_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
229 *
230 * KEY_OFF -- offset of the beginning of the data on
231 * this page
232 * FULL_KEY -- 2
233 * OVFL_PAGENO - page number of the next overflow page
234 * OVFLPAGE -- 0
235 *
236 * FULL_KEY_DATA
237 * This must be the first key/data pair on the page.
238 * There are two cases:
239 *
240 * Case 1:
241 * This page contains a key and the beginning of the
242 * data field, but the data field is continued on the
243 * next page.
244 *
245 * Page format is:
246 * KEY_OFF FULL_KEY_DATA OVFL_PAGENO DATA_OFF
247 *
248 * KEY_OFF -- offset of the beginning of the key
249 * FULL_KEY_DATA -- 3
250 * OVFL_PAGENO - page number of the next overflow page
251 * DATA_OFF -- offset of the beginning of the data
252 *
253 * Case 2:
254 * This page contains the last page of a big data pair.
255 * There is no key, only the tail end of the data
256 * on this page.
257 *
258 * Page format is:
259 * DATA_OFF FULL_KEY_DATA <OVFL_PAGENO> <OVFLPAGE>
260 *
261 * DATA_OFF -- offset of the beginning of the data on
262 * this page
263 * FULL_KEY_DATA -- 3
264 * OVFL_PAGENO - page number of the next overflow page
265 * OVFLPAGE -- 0
266 *
267 * OVFL_PAGENO and OVFLPAGE are optional (they are
268 * not present if there is no next page).
269 */
270
271#define OVFLPAGE 0
272#define PARTIAL_KEY 1
273#define FULL_KEY 2
274#define FULL_KEY_DATA 3
275#define REAL_KEY 4
276
277/* Short hands for accessing structure */
278#define BSIZE hdr.bsize
279#define BSHIFT hdr.bshift
280#define DSIZE hdr.dsize
281#define SGSIZE hdr.ssize
282#define SSHIFT hdr.sshift
283#define LORDER hdr.lorder
284#define OVFL_POINT hdr.ovfl_point
285#define LAST_FREED hdr.last_freed
286#define MAX_BUCKET hdr.max_bucket
287#define FFACTOR hdr.ffactor
288#define HIGH_MASK hdr.high_mask
289#define LOW_MASK hdr.low_mask
290#define NKEYS hdr.nkeys
291#define HDRPAGES hdr.hdrpages
292#define SPARES hdr.spares
293#define BITMAPS hdr.bitmaps
294#define VERSION hdr.version
295#define MAGIC hdr.magic
296#define NEXT_FREE hdr.next_free
297#define H_CHARKEY hdr.h_charkey
Note: See TracBrowser for help on using the repository browser.