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