line |
stmt |
bran |
cond |
sub |
time |
code |
1
|
|
|
|
|
|
/* |
2
|
|
|
|
|
|
* sdbm - ndbm work-alike hashed database library |
3
|
|
|
|
|
|
* based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978). |
4
|
|
|
|
|
|
* author: oz@nexus.yorku.ca |
5
|
|
|
|
|
|
* status: public domain. |
6
|
|
|
|
|
|
* |
7
|
|
|
|
|
|
* core routines |
8
|
|
|
|
|
|
*/ |
9
|
|
|
|
|
|
|
10
|
|
|
|
|
|
#include "INTERN.h" |
11
|
|
|
|
|
|
#include "config.h" |
12
|
|
|
|
|
|
#ifdef WIN32 |
13
|
|
|
|
|
|
#include "io.h" |
14
|
|
|
|
|
|
#endif |
15
|
|
|
|
|
|
#include "sdbm.h" |
16
|
|
|
|
|
|
#include "tune.h" |
17
|
|
|
|
|
|
#include "pair.h" |
18
|
|
|
|
|
|
|
19
|
|
|
|
|
|
#ifdef I_FCNTL |
20
|
|
|
|
|
|
# include |
21
|
|
|
|
|
|
#endif |
22
|
|
|
|
|
|
#ifdef I_SYS_FILE |
23
|
|
|
|
|
|
# include |
24
|
|
|
|
|
|
#endif |
25
|
|
|
|
|
|
|
26
|
|
|
|
|
|
#ifdef I_STRING |
27
|
|
|
|
|
|
# ifndef __ultrix__ |
28
|
|
|
|
|
|
# include |
29
|
|
|
|
|
|
# endif |
30
|
|
|
|
|
|
#else |
31
|
|
|
|
|
|
# include |
32
|
|
|
|
|
|
#endif |
33
|
|
|
|
|
|
|
34
|
|
|
|
|
|
/* |
35
|
|
|
|
|
|
* externals |
36
|
|
|
|
|
|
*/ |
37
|
|
|
|
|
|
|
38
|
|
|
|
|
|
#include /* See notes in perl.h about avoiding |
39
|
|
|
|
|
|
extern int errno; */ |
40
|
|
|
|
|
|
#ifdef __cplusplus |
41
|
|
|
|
|
|
extern "C" { |
42
|
|
|
|
|
|
#endif |
43
|
|
|
|
|
|
|
44
|
|
|
|
|
|
extern Malloc_t malloc proto((MEM_SIZE)); |
45
|
|
|
|
|
|
extern Free_t free proto((Malloc_t)); |
46
|
|
|
|
|
|
|
47
|
|
|
|
|
|
#ifdef __cplusplus |
48
|
|
|
|
|
|
} |
49
|
|
|
|
|
|
#endif |
50
|
|
|
|
|
|
|
51
|
|
|
|
|
|
/* |
52
|
|
|
|
|
|
* forward |
53
|
|
|
|
|
|
*/ |
54
|
|
|
|
|
|
static int getdbit proto((DBM *, long)); |
55
|
|
|
|
|
|
static int setdbit proto((DBM *, long)); |
56
|
|
|
|
|
|
static int getpage proto((DBM *, long)); |
57
|
|
|
|
|
|
static datum getnext proto((DBM *)); |
58
|
|
|
|
|
|
static int makroom proto((DBM *, long, int)); |
59
|
|
|
|
|
|
|
60
|
|
|
|
|
|
/* |
61
|
|
|
|
|
|
* useful macros |
62
|
|
|
|
|
|
*/ |
63
|
|
|
|
|
|
#define bad(x) ((x).dptr == NULL || (x).dsize < 0) |
64
|
|
|
|
|
|
#define exhash(item) sdbm_hash((item).dptr, (item).dsize) |
65
|
|
|
|
|
|
#define ioerr(db) ((db)->flags |= DBM_IOERR) |
66
|
|
|
|
|
|
|
67
|
|
|
|
|
|
#define OFF_PAG(off) (long) (off) * PBLKSIZ |
68
|
|
|
|
|
|
#define OFF_DIR(off) (long) (off) * DBLKSIZ |
69
|
|
|
|
|
|
|
70
|
|
|
|
|
|
static const long masks[] = { |
71
|
|
|
|
|
|
000000000000, 000000000001, 000000000003, 000000000007, |
72
|
|
|
|
|
|
000000000017, 000000000037, 000000000077, 000000000177, |
73
|
|
|
|
|
|
000000000377, 000000000777, 000000001777, 000000003777, |
74
|
|
|
|
|
|
000000007777, 000000017777, 000000037777, 000000077777, |
75
|
|
|
|
|
|
000000177777, 000000377777, 000000777777, 000001777777, |
76
|
|
|
|
|
|
000003777777, 000007777777, 000017777777, 000037777777, |
77
|
|
|
|
|
|
000077777777, 000177777777, 000377777777, 000777777777, |
78
|
|
|
|
|
|
001777777777, 003777777777, 007777777777, 017777777777 |
79
|
|
|
|
|
|
}; |
80
|
|
|
|
|
|
|
81
|
|
|
|
|
|
DBM * |
82
|
128
|
|
|
|
|
sdbm_open(char *file, int flags, int mode) |
83
|
|
|
|
|
|
{ |
84
|
|
|
|
|
|
DBM *db; |
85
|
|
|
|
|
|
char *dirname; |
86
|
|
|
|
|
|
char *pagname; |
87
|
|
|
|
|
|
size_t filelen; |
88
|
|
|
|
|
|
const size_t dirfext_size = sizeof(DIRFEXT ""); |
89
|
|
|
|
|
|
const size_t pagfext_size = sizeof(PAGFEXT ""); |
90
|
|
|
|
|
|
|
91
|
128
|
|
|
|
|
if (file == NULL || !*file) |
92
|
0
|
|
|
|
|
return errno = EINVAL, (DBM *) NULL; |
93
|
|
|
|
|
|
/* |
94
|
|
|
|
|
|
* need space for two separate filenames |
95
|
|
|
|
|
|
*/ |
96
|
128
|
|
|
|
|
filelen = strlen(file); |
97
|
|
|
|
|
|
|
98
|
128
|
|
|
|
|
if ((dirname = (char *) malloc(filelen + dirfext_size |
99
|
128
|
|
|
|
|
+ filelen + pagfext_size)) == NULL) |
100
|
0
|
|
|
|
|
return errno = ENOMEM, (DBM *) NULL; |
101
|
|
|
|
|
|
/* |
102
|
|
|
|
|
|
* build the file names |
103
|
|
|
|
|
|
*/ |
104
|
128
|
|
|
|
|
memcpy(dirname, file, filelen); |
105
|
128
|
|
|
|
|
memcpy(dirname + filelen, DIRFEXT, dirfext_size); |
106
|
128
|
|
|
|
|
pagname = dirname + filelen + dirfext_size; |
107
|
128
|
|
|
|
|
memcpy(pagname, file, filelen); |
108
|
128
|
|
|
|
|
memcpy(pagname + filelen, PAGFEXT, pagfext_size); |
109
|
|
|
|
|
|
|
110
|
128
|
|
|
|
|
db = sdbm_prep(dirname, pagname, flags, mode); |
111
|
128
|
|
|
|
|
free((char *) dirname); |
112
|
128
|
|
|
|
|
return db; |
113
|
|
|
|
|
|
} |
114
|
|
|
|
|
|
|
115
|
|
|
|
|
|
DBM * |
116
|
128
|
|
|
|
|
sdbm_prep(char *dirname, char *pagname, int flags, int mode) |
117
|
|
|
|
|
|
{ |
118
|
|
|
|
|
|
DBM *db; |
119
|
|
|
|
|
|
struct stat dstat; |
120
|
|
|
|
|
|
|
121
|
128
|
|
|
|
|
if ((db = (DBM *) malloc(sizeof(DBM))) == NULL) |
122
|
0
|
|
|
|
|
return errno = ENOMEM, (DBM *) NULL; |
123
|
|
|
|
|
|
|
124
|
128
|
|
|
|
|
db->flags = 0; |
125
|
128
|
|
|
|
|
db->hmask = 0; |
126
|
128
|
|
|
|
|
db->blkptr = 0; |
127
|
128
|
|
|
|
|
db->keyptr = 0; |
128
|
|
|
|
|
|
/* |
129
|
|
|
|
|
|
* adjust user flags so that WRONLY becomes RDWR, |
130
|
|
|
|
|
|
* as required by this package. Also set our internal |
131
|
|
|
|
|
|
* flag for RDONLY if needed. |
132
|
|
|
|
|
|
*/ |
133
|
128
|
|
|
|
|
if (flags & O_WRONLY) |
134
|
0
|
|
|
|
|
flags = (flags & ~O_WRONLY) | O_RDWR; |
135
|
|
|
|
|
|
|
136
|
128
|
|
|
|
|
else if ((flags & 03) == O_RDONLY) |
137
|
8
|
|
|
|
|
db->flags = DBM_RDONLY; |
138
|
|
|
|
|
|
/* |
139
|
|
|
|
|
|
* open the files in sequence, and stat the dirfile. |
140
|
|
|
|
|
|
* If we fail anywhere, undo everything, return NULL. |
141
|
|
|
|
|
|
*/ |
142
|
|
|
|
|
|
#if defined(OS2) || defined(MSDOS) || defined(WIN32) || defined(__CYGWIN__) |
143
|
|
|
|
|
|
flags |= O_BINARY; |
144
|
|
|
|
|
|
# endif |
145
|
128
|
|
|
|
|
if ((db->pagf = open(pagname, flags, mode)) > -1) { |
146
|
112
|
|
|
|
|
if ((db->dirf = open(dirname, flags, mode)) > -1) { |
147
|
|
|
|
|
|
/* |
148
|
|
|
|
|
|
* need the dirfile size to establish max bit number. |
149
|
|
|
|
|
|
*/ |
150
|
224
|
|
|
|
|
if (fstat(db->dirf, &dstat) == 0) { |
151
|
|
|
|
|
|
/* |
152
|
|
|
|
|
|
* zero size: either a fresh database, or one with a single, |
153
|
|
|
|
|
|
* unsplit data page: dirpage is all zeros. |
154
|
|
|
|
|
|
*/ |
155
|
112
|
|
|
|
|
db->dirbno = (!dstat.st_size) ? 0 : -1; |
156
|
112
|
|
|
|
|
db->pagbno = -1; |
157
|
112
|
|
|
|
|
db->maxbno = dstat.st_size * BYTESIZ; |
158
|
|
|
|
|
|
|
159
|
112
|
|
|
|
|
(void) memset(db->pagbuf, 0, PBLKSIZ); |
160
|
112
|
|
|
|
|
(void) memset(db->dirbuf, 0, DBLKSIZ); |
161
|
|
|
|
|
|
/* |
162
|
|
|
|
|
|
* success |
163
|
|
|
|
|
|
*/ |
164
|
112
|
|
|
|
|
return db; |
165
|
|
|
|
|
|
} |
166
|
0
|
|
|
|
|
(void) close(db->dirf); |
167
|
|
|
|
|
|
} |
168
|
0
|
|
|
|
|
(void) close(db->pagf); |
169
|
|
|
|
|
|
} |
170
|
16
|
|
|
|
|
free((char *) db); |
171
|
16
|
|
|
|
|
return (DBM *) NULL; |
172
|
|
|
|
|
|
} |
173
|
|
|
|
|
|
|
174
|
|
|
|
|
|
void |
175
|
112
|
|
|
|
|
sdbm_close(DBM *db) |
176
|
|
|
|
|
|
{ |
177
|
112
|
|
|
|
|
if (db == NULL) |
178
|
0
|
|
|
|
|
errno = EINVAL; |
179
|
|
|
|
|
|
else { |
180
|
112
|
|
|
|
|
(void) close(db->dirf); |
181
|
112
|
|
|
|
|
(void) close(db->pagf); |
182
|
112
|
|
|
|
|
free((char *) db); |
183
|
|
|
|
|
|
} |
184
|
112
|
|
|
|
|
} |
185
|
|
|
|
|
|
|
186
|
|
|
|
|
|
datum |
187
|
2308
|
|
|
|
|
sdbm_fetch(DBM *db, datum key) |
188
|
|
|
|
|
|
{ |
189
|
2308
|
|
|
|
|
if (db == NULL || bad(key)) |
190
|
0
|
|
|
|
|
return errno = EINVAL, nullitem; |
191
|
|
|
|
|
|
|
192
|
2308
|
|
|
|
|
if (getpage(db, exhash(key))) |
193
|
2308
|
|
|
|
|
return getpair(db->pagbuf, key); |
194
|
|
|
|
|
|
|
195
|
0
|
|
|
|
|
return ioerr(db), nullitem; |
196
|
|
|
|
|
|
} |
197
|
|
|
|
|
|
|
198
|
|
|
|
|
|
int |
199
|
4
|
|
|
|
|
sdbm_exists(DBM *db, datum key) |
200
|
|
|
|
|
|
{ |
201
|
4
|
|
|
|
|
if (db == NULL || bad(key)) |
202
|
0
|
|
|
|
|
return errno = EINVAL, -1; |
203
|
|
|
|
|
|
|
204
|
4
|
|
|
|
|
if (getpage(db, exhash(key))) |
205
|
4
|
|
|
|
|
return exipair(db->pagbuf, key); |
206
|
|
|
|
|
|
|
207
|
0
|
|
|
|
|
return ioerr(db), -1; |
208
|
|
|
|
|
|
} |
209
|
|
|
|
|
|
|
210
|
|
|
|
|
|
int |
211
|
12
|
|
|
|
|
sdbm_delete(DBM *db, datum key) |
212
|
|
|
|
|
|
{ |
213
|
12
|
|
|
|
|
if (db == NULL || bad(key)) |
214
|
0
|
|
|
|
|
return errno = EINVAL, -1; |
215
|
12
|
|
|
|
|
if (sdbm_rdonly(db)) |
216
|
0
|
|
|
|
|
return errno = EPERM, -1; |
217
|
|
|
|
|
|
|
218
|
12
|
|
|
|
|
if (getpage(db, exhash(key))) { |
219
|
12
|
|
|
|
|
if (!delpair(db->pagbuf, key)) |
220
|
|
|
|
|
|
return -1; |
221
|
|
|
|
|
|
/* |
222
|
|
|
|
|
|
* update the page file |
223
|
|
|
|
|
|
*/ |
224
|
12
|
|
|
|
|
if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0 |
225
|
12
|
|
|
|
|
|| write(db->pagf, db->pagbuf, PBLKSIZ) < 0) |
226
|
0
|
|
|
|
|
return ioerr(db), -1; |
227
|
|
|
|
|
|
|
228
|
|
|
|
|
|
return 0; |
229
|
|
|
|
|
|
} |
230
|
|
|
|
|
|
|
231
|
0
|
|
|
|
|
return ioerr(db), -1; |
232
|
|
|
|
|
|
} |
233
|
|
|
|
|
|
|
234
|
|
|
|
|
|
int |
235
|
1984
|
|
|
|
|
sdbm_store(DBM *db, datum key, datum val, int flags) |
236
|
|
|
|
|
|
{ |
237
|
|
|
|
|
|
int need; |
238
|
|
|
|
|
|
long hash; |
239
|
|
|
|
|
|
|
240
|
1984
|
|
|
|
|
if (db == NULL || bad(key)) |
241
|
0
|
|
|
|
|
return errno = EINVAL, -1; |
242
|
1984
|
|
|
|
|
if (sdbm_rdonly(db)) |
243
|
0
|
|
|
|
|
return errno = EPERM, -1; |
244
|
|
|
|
|
|
|
245
|
1984
|
|
|
|
|
need = key.dsize + val.dsize; |
246
|
|
|
|
|
|
/* |
247
|
|
|
|
|
|
* is the pair too big (or too small) for this database ?? |
248
|
|
|
|
|
|
*/ |
249
|
1984
|
|
|
|
|
if (need < 0 || need > PAIRMAX) |
250
|
0
|
|
|
|
|
return errno = EINVAL, -1; |
251
|
|
|
|
|
|
|
252
|
1984
|
|
|
|
|
if (getpage(db, (hash = exhash(key)))) { |
253
|
|
|
|
|
|
/* |
254
|
|
|
|
|
|
* if we need to replace, delete the key/data pair |
255
|
|
|
|
|
|
* first. If it is not there, ignore. |
256
|
|
|
|
|
|
*/ |
257
|
1984
|
|
|
|
|
if (flags == DBM_REPLACE) |
258
|
1984
|
|
|
|
|
(void) delpair(db->pagbuf, key); |
259
|
|
|
|
|
|
#ifdef SEEDUPS |
260
|
0
|
|
|
|
|
else if (duppair(db->pagbuf, key)) |
261
|
|
|
|
|
|
return 1; |
262
|
|
|
|
|
|
#endif |
263
|
|
|
|
|
|
/* |
264
|
|
|
|
|
|
* if we do not have enough room, we have to split. |
265
|
|
|
|
|
|
*/ |
266
|
1984
|
|
|
|
|
if (!fitpair(db->pagbuf, need)) |
267
|
12
|
|
|
|
|
if (!makroom(db, hash, need)) |
268
|
0
|
|
|
|
|
return ioerr(db), -1; |
269
|
|
|
|
|
|
/* |
270
|
|
|
|
|
|
* we have enough room or split is successful. insert the key, |
271
|
|
|
|
|
|
* and update the page file. |
272
|
|
|
|
|
|
*/ |
273
|
1984
|
|
|
|
|
(void) putpair(db->pagbuf, key, val); |
274
|
|
|
|
|
|
|
275
|
1984
|
|
|
|
|
if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0 |
276
|
1984
|
|
|
|
|
|| write(db->pagf, db->pagbuf, PBLKSIZ) < 0) |
277
|
0
|
|
|
|
|
return ioerr(db), -1; |
278
|
|
|
|
|
|
/* |
279
|
|
|
|
|
|
* success |
280
|
|
|
|
|
|
*/ |
281
|
|
|
|
|
|
return 0; |
282
|
|
|
|
|
|
} |
283
|
|
|
|
|
|
|
284
|
0
|
|
|
|
|
return ioerr(db), -1; |
285
|
|
|
|
|
|
} |
286
|
|
|
|
|
|
|
287
|
|
|
|
|
|
/* |
288
|
|
|
|
|
|
* makroom - make room by splitting the overfull page |
289
|
|
|
|
|
|
* this routine will attempt to make room for SPLTMAX times before |
290
|
|
|
|
|
|
* giving up. |
291
|
|
|
|
|
|
*/ |
292
|
|
|
|
|
|
static int |
293
|
12
|
|
|
|
|
makroom(DBM *db, long int hash, int need) |
294
|
|
|
|
|
|
{ |
295
|
|
|
|
|
|
long newp; |
296
|
|
|
|
|
|
char twin[PBLKSIZ]; |
297
|
|
|
|
|
|
#if defined(DOSISH) || defined(WIN32) |
298
|
|
|
|
|
|
char zer[PBLKSIZ]; |
299
|
|
|
|
|
|
long oldtail; |
300
|
|
|
|
|
|
#endif |
301
|
12
|
|
|
|
|
char *pag = db->pagbuf; |
302
|
|
|
|
|
|
char *New = twin; |
303
|
|
|
|
|
|
int smax = SPLTMAX; |
304
|
|
|
|
|
|
|
305
|
|
|
|
|
|
do { |
306
|
|
|
|
|
|
/* |
307
|
|
|
|
|
|
* split the current page |
308
|
|
|
|
|
|
*/ |
309
|
12
|
|
|
|
|
(void) splpage(pag, New, db->hmask + 1); |
310
|
|
|
|
|
|
/* |
311
|
|
|
|
|
|
* address of the new page |
312
|
|
|
|
|
|
*/ |
313
|
12
|
|
|
|
|
newp = (hash & db->hmask) | (db->hmask + 1); |
314
|
|
|
|
|
|
|
315
|
|
|
|
|
|
/* |
316
|
|
|
|
|
|
* write delay, read avoidance/cache shuffle: |
317
|
|
|
|
|
|
* select the page for incoming pair: if key is to go to the new page, |
318
|
|
|
|
|
|
* write out the previous one, and copy the new one over, thus making |
319
|
|
|
|
|
|
* it the current page. If not, simply write the new page, and we are |
320
|
|
|
|
|
|
* still looking at the page of interest. current page is not updated |
321
|
|
|
|
|
|
* here, as sdbm_store will do so, after it inserts the incoming pair. |
322
|
|
|
|
|
|
*/ |
323
|
|
|
|
|
|
|
324
|
|
|
|
|
|
#if defined(DOSISH) || defined(WIN32) |
325
|
|
|
|
|
|
/* |
326
|
|
|
|
|
|
* Fill hole with 0 if made it. |
327
|
|
|
|
|
|
* (hole is NOT read as 0) |
328
|
|
|
|
|
|
*/ |
329
|
|
|
|
|
|
oldtail = lseek(db->pagf, 0L, SEEK_END); |
330
|
|
|
|
|
|
memset(zer, 0, PBLKSIZ); |
331
|
|
|
|
|
|
while (OFF_PAG(newp) > oldtail) { |
332
|
|
|
|
|
|
if (lseek(db->pagf, 0L, SEEK_END) < 0 || |
333
|
|
|
|
|
|
write(db->pagf, zer, PBLKSIZ) < 0) { |
334
|
|
|
|
|
|
|
335
|
|
|
|
|
|
return 0; |
336
|
|
|
|
|
|
} |
337
|
|
|
|
|
|
oldtail += PBLKSIZ; |
338
|
|
|
|
|
|
} |
339
|
|
|
|
|
|
#endif |
340
|
12
|
|
|
|
|
if (hash & (db->hmask + 1)) { |
341
|
0
|
|
|
|
|
if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0 |
342
|
0
|
|
|
|
|
|| write(db->pagf, db->pagbuf, PBLKSIZ) < 0) |
343
|
|
|
|
|
|
return 0; |
344
|
0
|
|
|
|
|
db->pagbno = newp; |
345
|
0
|
|
|
|
|
(void) memcpy(pag, New, PBLKSIZ); |
346
|
|
|
|
|
|
} |
347
|
12
|
|
|
|
|
else if (lseek(db->pagf, OFF_PAG(newp), SEEK_SET) < 0 |
348
|
12
|
|
|
|
|
|| write(db->pagf, New, PBLKSIZ) < 0) |
349
|
|
|
|
|
|
return 0; |
350
|
|
|
|
|
|
|
351
|
12
|
|
|
|
|
if (!setdbit(db, db->curbit)) |
352
|
|
|
|
|
|
return 0; |
353
|
|
|
|
|
|
/* |
354
|
|
|
|
|
|
* see if we have enough room now |
355
|
|
|
|
|
|
*/ |
356
|
12
|
|
|
|
|
if (fitpair(pag, need)) |
357
|
|
|
|
|
|
return 1; |
358
|
|
|
|
|
|
/* |
359
|
|
|
|
|
|
* try again... update curbit and hmask as getpage would have |
360
|
|
|
|
|
|
* done. because of our update of the current page, we do not |
361
|
|
|
|
|
|
* need to read in anything. BUT we have to write the current |
362
|
|
|
|
|
|
* [deferred] page out, as the window of failure is too great. |
363
|
|
|
|
|
|
*/ |
364
|
0
|
|
|
|
|
db->curbit = 2 * db->curbit + |
365
|
0
|
|
|
|
|
((hash & (db->hmask + 1)) ? 2 : 1); |
366
|
0
|
|
|
|
|
db->hmask |= db->hmask + 1; |
367
|
|
|
|
|
|
|
368
|
0
|
|
|
|
|
if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0 |
369
|
0
|
|
|
|
|
|| write(db->pagf, db->pagbuf, PBLKSIZ) < 0) |
370
|
|
|
|
|
|
return 0; |
371
|
|
|
|
|
|
|
372
|
0
|
|
|
|
|
} while (--smax); |
373
|
|
|
|
|
|
/* |
374
|
|
|
|
|
|
* if we are here, this is real bad news. After SPLTMAX splits, |
375
|
|
|
|
|
|
* we still cannot fit the key. say goodnight. |
376
|
|
|
|
|
|
*/ |
377
|
|
|
|
|
|
#ifdef BADMESS |
378
|
0
|
|
|
|
|
(void) write(2, "sdbm: cannot insert after SPLTMAX attempts.\n", 44); |
379
|
|
|
|
|
|
#endif |
380
|
0
|
|
|
|
|
return 0; |
381
|
|
|
|
|
|
|
382
|
|
|
|
|
|
} |
383
|
|
|
|
|
|
|
384
|
|
|
|
|
|
/* |
385
|
|
|
|
|
|
* the following two routines will break if |
386
|
|
|
|
|
|
* deletions aren't taken into account. (ndbm bug) |
387
|
|
|
|
|
|
*/ |
388
|
|
|
|
|
|
datum |
389
|
94
|
|
|
|
|
sdbm_firstkey(DBM *db) |
390
|
|
|
|
|
|
{ |
391
|
94
|
|
|
|
|
if (db == NULL) |
392
|
0
|
|
|
|
|
return errno = EINVAL, nullitem; |
393
|
|
|
|
|
|
/* |
394
|
|
|
|
|
|
* start at page 0 |
395
|
|
|
|
|
|
*/ |
396
|
94
|
|
|
|
|
if (lseek(db->pagf, OFF_PAG(0), SEEK_SET) < 0 |
397
|
188
|
|
|
|
|
|| read(db->pagf, db->pagbuf, PBLKSIZ) < 0) |
398
|
0
|
|
|
|
|
return ioerr(db), nullitem; |
399
|
94
|
|
|
|
|
db->pagbno = 0; |
400
|
94
|
|
|
|
|
db->blkptr = 0; |
401
|
94
|
|
|
|
|
db->keyptr = 0; |
402
|
|
|
|
|
|
|
403
|
94
|
|
|
|
|
return getnext(db); |
404
|
|
|
|
|
|
} |
405
|
|
|
|
|
|
|
406
|
|
|
|
|
|
datum |
407
|
756
|
|
|
|
|
sdbm_nextkey(DBM *db) |
408
|
|
|
|
|
|
{ |
409
|
756
|
|
|
|
|
if (db == NULL) |
410
|
0
|
|
|
|
|
return errno = EINVAL, nullitem; |
411
|
756
|
|
|
|
|
return getnext(db); |
412
|
|
|
|
|
|
} |
413
|
|
|
|
|
|
|
414
|
|
|
|
|
|
/* |
415
|
|
|
|
|
|
* all important binary trie traversal |
416
|
|
|
|
|
|
*/ |
417
|
|
|
|
|
|
static int |
418
|
4308
|
|
|
|
|
getpage(DBM *db, long int hash) |
419
|
|
|
|
|
|
{ |
420
|
|
|
|
|
|
int hbit; |
421
|
|
|
|
|
|
long dbit; |
422
|
|
|
|
|
|
long pagb; |
423
|
|
|
|
|
|
|
424
|
|
|
|
|
|
dbit = 0; |
425
|
|
|
|
|
|
hbit = 0; |
426
|
12928
|
|
|
|
|
while (dbit < db->maxbno && getdbit(db, dbit)) |
427
|
4312
|
|
|
|
|
dbit = 2 * dbit + ((hash & (1 << hbit++)) ? 2 : 1); |
428
|
|
|
|
|
|
|
429
|
|
|
|
|
|
debug(("dbit: %d...", dbit)); |
430
|
|
|
|
|
|
|
431
|
4308
|
|
|
|
|
db->curbit = dbit; |
432
|
4308
|
|
|
|
|
db->hmask = masks[hbit]; |
433
|
|
|
|
|
|
|
434
|
4308
|
|
|
|
|
pagb = hash & db->hmask; |
435
|
|
|
|
|
|
/* |
436
|
|
|
|
|
|
* see if the block we need is already in memory. |
437
|
|
|
|
|
|
* note: this lookaside cache has about 10% hit rate. |
438
|
|
|
|
|
|
*/ |
439
|
4308
|
|
|
|
|
if (pagb != db->pagbno) { |
440
|
|
|
|
|
|
/* |
441
|
|
|
|
|
|
* note: here, we assume a "hole" is read as 0s. |
442
|
|
|
|
|
|
* if not, must zero pagbuf first. |
443
|
|
|
|
|
|
*/ |
444
|
2762
|
|
|
|
|
if (lseek(db->pagf, OFF_PAG(pagb), SEEK_SET) < 0 |
445
|
5524
|
|
|
|
|
|| read(db->pagf, db->pagbuf, PBLKSIZ) < 0) |
446
|
|
|
|
|
|
return 0; |
447
|
2762
|
|
|
|
|
if (!chkpage(db->pagbuf)) |
448
|
|
|
|
|
|
return 0; |
449
|
2762
|
|
|
|
|
db->pagbno = pagb; |
450
|
|
|
|
|
|
|
451
|
|
|
|
|
|
debug(("pag read: %d\n", pagb)); |
452
|
|
|
|
|
|
} |
453
|
|
|
|
|
|
return 1; |
454
|
|
|
|
|
|
} |
455
|
|
|
|
|
|
|
456
|
|
|
|
|
|
static int |
457
|
7120
|
|
|
|
|
getdbit(DBM *db, long int dbit) |
458
|
|
|
|
|
|
{ |
459
|
|
|
|
|
|
long c; |
460
|
|
|
|
|
|
long dirb; |
461
|
|
|
|
|
|
|
462
|
7120
|
|
|
|
|
c = dbit / BYTESIZ; |
463
|
7120
|
|
|
|
|
dirb = c / DBLKSIZ; |
464
|
|
|
|
|
|
|
465
|
7120
|
|
|
|
|
if (dirb != db->dirbno) { |
466
|
|
|
|
|
|
int got; |
467
|
0
|
|
|
|
|
if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0 |
468
|
0
|
|
|
|
|
|| (got=read(db->dirf, db->dirbuf, DBLKSIZ)) < 0) |
469
|
|
|
|
|
|
return 0; |
470
|
0
|
|
|
|
|
if (got==0) |
471
|
0
|
|
|
|
|
memset(db->dirbuf,0,DBLKSIZ); |
472
|
0
|
|
|
|
|
db->dirbno = dirb; |
473
|
|
|
|
|
|
|
474
|
|
|
|
|
|
debug(("dir read: %d\n", dirb)); |
475
|
|
|
|
|
|
} |
476
|
|
|
|
|
|
|
477
|
7120
|
|
|
|
|
return db->dirbuf[c % DBLKSIZ] & (1 << dbit % BYTESIZ); |
478
|
|
|
|
|
|
} |
479
|
|
|
|
|
|
|
480
|
|
|
|
|
|
static int |
481
|
12
|
|
|
|
|
setdbit(DBM *db, long int dbit) |
482
|
|
|
|
|
|
{ |
483
|
|
|
|
|
|
long c; |
484
|
|
|
|
|
|
long dirb; |
485
|
|
|
|
|
|
|
486
|
12
|
|
|
|
|
c = dbit / BYTESIZ; |
487
|
12
|
|
|
|
|
dirb = c / DBLKSIZ; |
488
|
|
|
|
|
|
|
489
|
12
|
|
|
|
|
if (dirb != db->dirbno) { |
490
|
|
|
|
|
|
int got; |
491
|
0
|
|
|
|
|
if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0 |
492
|
0
|
|
|
|
|
|| (got=read(db->dirf, db->dirbuf, DBLKSIZ)) < 0) |
493
|
|
|
|
|
|
return 0; |
494
|
0
|
|
|
|
|
if (got==0) |
495
|
0
|
|
|
|
|
memset(db->dirbuf,0,DBLKSIZ); |
496
|
0
|
|
|
|
|
db->dirbno = dirb; |
497
|
|
|
|
|
|
|
498
|
|
|
|
|
|
debug(("dir read: %d\n", dirb)); |
499
|
|
|
|
|
|
} |
500
|
|
|
|
|
|
|
501
|
12
|
|
|
|
|
db->dirbuf[c % DBLKSIZ] |= (1 << dbit % BYTESIZ); |
502
|
|
|
|
|
|
|
503
|
|
|
|
|
|
#if 0 |
504
|
|
|
|
|
|
if (dbit >= db->maxbno) |
505
|
|
|
|
|
|
db->maxbno += DBLKSIZ * BYTESIZ; |
506
|
|
|
|
|
|
#else |
507
|
12
|
|
|
|
|
if (OFF_DIR((dirb+1))*BYTESIZ > db->maxbno) |
508
|
4
|
|
|
|
|
db->maxbno=OFF_DIR((dirb+1))*BYTESIZ; |
509
|
|
|
|
|
|
#endif |
510
|
|
|
|
|
|
|
511
|
12
|
|
|
|
|
if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0 |
512
|
12
|
|
|
|
|
|| write(db->dirf, db->dirbuf, DBLKSIZ) < 0) |
513
|
|
|
|
|
|
return 0; |
514
|
|
|
|
|
|
|
515
|
12
|
|
|
|
|
return 1; |
516
|
|
|
|
|
|
} |
517
|
|
|
|
|
|
|
518
|
|
|
|
|
|
/* |
519
|
|
|
|
|
|
* getnext - get the next key in the page, and if done with |
520
|
|
|
|
|
|
* the page, try the next page in sequence |
521
|
|
|
|
|
|
*/ |
522
|
|
|
|
|
|
static datum |
523
|
850
|
|
|
|
|
getnext(DBM *db) |
524
|
|
|
|
|
|
{ |
525
|
|
|
|
|
|
datum key; |
526
|
|
|
|
|
|
|
527
|
|
|
|
|
|
for (;;) { |
528
|
850
|
|
|
|
|
db->keyptr++; |
529
|
850
|
|
|
|
|
key = getnkey(db->pagbuf, db->keyptr); |
530
|
850
|
|
|
|
|
if (key.dptr != NULL) |
531
|
768
|
|
|
|
|
return key; |
532
|
|
|
|
|
|
/* |
533
|
|
|
|
|
|
* we either run out, or there is nothing on this page.. |
534
|
|
|
|
|
|
* try the next one... If we lost our position on the |
535
|
|
|
|
|
|
* file, we will have to seek. |
536
|
|
|
|
|
|
*/ |
537
|
82
|
|
|
|
|
db->keyptr = 0; |
538
|
82
|
|
|
|
|
if (db->pagbno != db->blkptr++) |
539
|
0
|
|
|
|
|
if (lseek(db->pagf, OFF_PAG(db->blkptr), SEEK_SET) < 0) |
540
|
|
|
|
|
|
break; |
541
|
82
|
|
|
|
|
db->pagbno = db->blkptr; |
542
|
164
|
|
|
|
|
if (read(db->pagf, db->pagbuf, PBLKSIZ) <= 0) |
543
|
|
|
|
|
|
break; |
544
|
0
|
|
|
|
|
if (!chkpage(db->pagbuf)) |
545
|
|
|
|
|
|
break; |
546
|
|
|
|
|
|
} |
547
|
|
|
|
|
|
|
548
|
82
|
|
|
|
|
return ioerr(db), nullitem; |
549
|
|
|
|
|
|
} |
550
|
|
|
|
|
|
|