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