Asterisk - The Open Source Telephony Project  GIT-master-a24979a
hash.h
Go to the documentation of this file.
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 {
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  * numbered 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[__hash_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
#define NCACHED
Definition: hash.h:85
struct hashhdr HASHHDR
BUFHEAD ** SEGMENT
Definition: hash.h:62
ACTION
Definition: hash.h:40
@ HASH_DELETE
Definition: hash.h:41
@ HASH_PUT
Definition: hash.h:41
@ HASH_PUTNEW
Definition: hash.h:41
@ HASH_GET
Definition: hash.h:41
@ HASH_NEXT
Definition: hash.h:41
@ HASH_FIRST
Definition: hash.h:41
struct htab HTAB
unsigned int u_int32_t
unsigned short u_int16_t
Definition: hash.h:47
char * page
Definition: hash.h:52
BUFHEAD * ovfl
Definition: hash.h:50
char flags
Definition: hash.h:53
u_int32_t addr
Definition: hash.h:51
BUFHEAD * prev
Definition: hash.h:48
BUFHEAD * next
Definition: hash.h:49
Definition: hash.h:65
int spares[NCACHED]
Definition: hash.h:86
int bsize
Definition: hash.h:69
int high_mask
Definition: hash.h:78
int hdrpages
Definition: hash.h:83
int h_charkey
Definition: hash.h:84
int bshift
Definition: hash.h:70
int ovfl_point
Definition: hash.h:74
int magic
Definition: hash.h:66
int ffactor
Definition: hash.h:81
int nkeys
Definition: hash.h:82
u_int32_t lorder
Definition: hash.h:68
int low_mask
Definition: hash.h:79
int max_bucket
Definition: hash.h:77
int version
Definition: hash.h:67
int dsize
Definition: hash.h:71
int sshift
Definition: hash.h:73
int ssize
Definition: hash.h:72
int last_freed
Definition: hash.h:76
u_int16_t bitmaps[NCACHED]
Definition: hash.h:87
Definition: hash.h:91
BUFHEAD bufhead
Definition: hash.h:116
int cbucket
Definition: hash.h:103
char * tmp_buf
Definition: hash.h:100
int save_file
Definition: hash.h:109
char * tmp_key
Definition: hash.h:101
int new_file
Definition: hash.h:107
u_int32_t hash __P((const void *, size_t))
int fp
Definition: hash.h:99
int exsegs
Definition: hash.h:94
SEGMENT * dir
Definition: hash.h:117
u_int32_t * mapp[NCACHED]
Definition: hash.h:112
int nbufs
Definition: hash.h:114
int nsegs
Definition: hash.h:93
HASHHDR hdr
Definition: hash.h:92
int errnum
Definition: hash.h:105
int nmaps
Definition: hash.h:113
BUFHEAD * cpage
Definition: hash.h:102
int cndx
Definition: hash.h:104
int flags
Definition: hash.h:98