Asterisk - The Open Source Telephony Project
21.4.1
Main Page
Related Pages
Modules
Namespaces
Data Structures
Files
Examples
File List
Globals
utils
db1-ast
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
* 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
hashhdr
Definition:
hash.h:65
htab
Definition:
hash.h:92
_bufhead
Definition:
hash.h:47
Generated on Tue Jul 15 2025 11:50:40 for Asterisk - The Open Source Telephony Project by
1.8.10