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