xref: /original-bsd/old/libdbm/dbm.c (revision e59fb703) 
1 #ifndef lint
2 static char sccsid[] = "@(#)dbm.c	4.5 (Berkeley) 06/19/85";
3 #endif
4 
5 #include	"dbm.h"
6 #undef		NULL
7 #include	<sys/types.h>
8 #undef		setbit
9 #include	<sys/stat.h>
10 
11 dbminit(file)
12 char *file;
13 {
14 	struct stat statb;
15 
16 	dbrdonly = 0;
17 	strcpy(pagbuf, file);
18 	strcat(pagbuf, ".pag");
19 	pagf = open(pagbuf, 2);
20 	if (pagf < 0) {
21 		pagf = open(pagbuf, 0);
22 		dbrdonly = 1;
23 	}
24 
25 	strcpy(pagbuf, file);
26 	strcat(pagbuf, ".dir");
27 	dirf = open(pagbuf, 2);
28 	if (dirf < 0) {
29 		dirf = open(pagbuf, 0);
30 		dbrdonly = 1;
31 	}
32 	if(pagf < 0 || dirf < 0) {
33 		printf("dbm: %s: cannot open database\n", file);
34 		return(-1);
35 	}
36 	fstat(dirf, &statb);
37 	maxbno = statb.st_size*BYTESIZ-1;
38 	return(0);
39 }
40 
41 long
42 forder(key)
43 datum key;
44 {
45 	long hash;
46 
47 	hash = calchash(key);
48 	for(hmask=0;; hmask=(hmask<<1)+1) {
49 		blkno = hash & hmask;
50 		bitno = blkno + hmask;
51 		if(getbit() == 0)
52 			break;
53 	}
54 	return(blkno);
55 }
56 
57 datum
58 fetch(key)
59 datum key;
60 {
61 	register i;
62 	datum item;
63 
64 	dbm_access(calchash(key));
65 	for(i=0;; i+=2) {
66 		item = makdatum(pagbuf, i);
67 		if(item.dptr == NULL)
68 			return(item);
69 		if(cmpdatum(key, item) == 0) {
70 			item = makdatum(pagbuf, i+1);
71 			if(item.dptr == NULL)
72 				printf("dbm: items not in pairs\n");
73 			return(item);
74 		}
75 	}
76 }
77 
78 delete(key)
79 datum key;
80 {
81 	register i;
82 	datum item;
83 
84 	if (dbrdonly)
85 		return -1;
86 	dbm_access(calchash(key));
87 	for(i=0;; i+=2) {
88 		item = makdatum(pagbuf, i);
89 		if(item.dptr == NULL)
90 			return(-1);
91 		if(cmpdatum(key, item) == 0) {
92 			delitem(pagbuf, i);
93 			delitem(pagbuf, i);
94 			break;
95 		}
96 	}
97 	lseek(pagf, blkno*PBLKSIZ, 0);
98 	write(pagf, pagbuf, PBLKSIZ);
99 	return(0);
100 }
101 
102 store(key, dat)
103 datum key, dat;
104 {
105 	register i;
106 	datum item;
107 	char ovfbuf[PBLKSIZ];
108 
109 	if (dbrdonly)
110 		return -1;
111 loop:
112 	dbm_access(calchash(key));
113 	for(i=0;; i+=2) {
114 		item = makdatum(pagbuf, i);
115 		if(item.dptr == NULL)
116 			break;
117 		if(cmpdatum(key, item) == 0) {
118 			delitem(pagbuf, i);
119 			delitem(pagbuf, i);
120 			break;
121 		}
122 	}
123 	i = additem(pagbuf, key);
124 	if(i < 0)
125 		goto split;
126 	if(additem(pagbuf, dat) < 0) {
127 		delitem(pagbuf, i);
128 		goto split;
129 	}
130 	lseek(pagf, blkno*PBLKSIZ, 0);
131 	write(pagf, pagbuf, PBLKSIZ);
132 	return (0);
133 
134 split:
135 	if(key.dsize+dat.dsize+3*sizeof(short) >= PBLKSIZ) {
136 		printf("dbm: entry too big\n");
137 		return (-1);
138 	}
139 	clrbuf(ovfbuf, PBLKSIZ);
140 	for(i=0;;) {
141 		item = makdatum(pagbuf, i);
142 		if(item.dptr == NULL)
143 			break;
144 		if(calchash(item) & (hmask+1)) {
145 			additem(ovfbuf, item);
146 			delitem(pagbuf, i);
147 			item = makdatum(pagbuf, i);
148 			if(item.dptr == NULL) {
149 				printf("dbm: split not paired\n");
150 				break;
151 			}
152 			additem(ovfbuf, item);
153 			delitem(pagbuf, i);
154 			continue;
155 		}
156 		i += 2;
157 	}
158 	lseek(pagf, blkno*PBLKSIZ, 0);
159 	write(pagf, pagbuf, PBLKSIZ);
160 	lseek(pagf, (blkno+hmask+1)*PBLKSIZ, 0);
161 	write(pagf, ovfbuf, PBLKSIZ);
162 	setbit();
163 	goto loop;
164 }
165 
166 datum
167 firstkey()
168 {
169 	return(firsthash(0L));
170 }
171 
172 datum
173 nextkey(key)
174 datum key;
175 {
176 	register i;
177 	datum item, bitem;
178 	long hash;
179 	int f;
180 
181 	hash = calchash(key);
182 	dbm_access(hash);
183 	f = 1;
184 	for(i=0;; i+=2) {
185 		item = makdatum(pagbuf, i);
186 		if(item.dptr == NULL)
187 			break;
188 		if(cmpdatum(key, item) <= 0)
189 			continue;
190 		if(f || cmpdatum(bitem, item) < 0) {
191 			bitem = item;
192 			f = 0;
193 		}
194 	}
195 	if(f == 0)
196 		return(bitem);
197 	hash = hashinc(hash);
198 	if(hash == 0)
199 		return(item);
200 	return(firsthash(hash));
201 }
202 
203 datum
204 firsthash(hash)
205 long hash;
206 {
207 	register i;
208 	datum item, bitem;
209 
210 loop:
211 	dbm_access(hash);
212 	bitem = makdatum(pagbuf, 0);
213 	for(i=2;; i+=2) {
214 		item = makdatum(pagbuf, i);
215 		if(item.dptr == NULL)
216 			break;
217 		if(cmpdatum(bitem, item) < 0)
218 			bitem = item;
219 	}
220 	if(bitem.dptr != NULL)
221 		return(bitem);
222 	hash = hashinc(hash);
223 	if(hash == 0)
224 		return(item);
225 	goto loop;
226 }
227 
228 dbm_access(hash)
229 long hash;
230 {
231 	static long oldb = -1;
232 
233 	for(hmask=0;; hmask=(hmask<<1)+1) {
234 		blkno = hash & hmask;
235 		bitno = blkno + hmask;
236 		if(getbit() == 0)
237 			break;
238 	}
239 	if(blkno != oldb) {
240 		clrbuf(pagbuf, PBLKSIZ);
241 		lseek(pagf, blkno*PBLKSIZ, 0);
242 		read(pagf, pagbuf, PBLKSIZ);
243 		chkblk(pagbuf);
244 		oldb = blkno;
245 	}
246 }
247 
248 getbit()
249 {
250 	long bn;
251 	register b, i, n;
252 	static oldb = -1;
253 
254 	if(bitno > maxbno)
255 		return(0);
256 	n = bitno % BYTESIZ;
257 	bn = bitno / BYTESIZ;
258 	i = bn % DBLKSIZ;
259 	b = bn / DBLKSIZ;
260 	if(b != oldb) {
261 		clrbuf(dirbuf, DBLKSIZ);
262 		lseek(dirf, (long)b*DBLKSIZ, 0);
263 		read(dirf, dirbuf, DBLKSIZ);
264 		oldb = b;
265 	}
266 	if(dirbuf[i] & (1<<n))
267 		return(1);
268 	return(0);
269 }
270 
271 setbit()
272 {
273 	long bn;
274 	register i, n, b;
275 
276 	if (dbrdonly)
277 		return -1;
278 	if(bitno > maxbno) {
279 		maxbno = bitno;
280 		getbit();
281 	}
282 	n = bitno % BYTESIZ;
283 	bn = bitno / BYTESIZ;
284 	i = bn % DBLKSIZ;
285 	b = bn / DBLKSIZ;
286 	dirbuf[i] |= 1<<n;
287 	lseek(dirf, (long)b*DBLKSIZ, 0);
288 	write(dirf, dirbuf, DBLKSIZ);
289 }
290 
291 clrbuf(cp, n)
292 register char *cp;
293 register n;
294 {
295 
296 	do
297 		*cp++ = 0;
298 	while(--n);
299 }
300 
301 datum
302 makdatum(buf, n)
303 char buf[PBLKSIZ];
304 {
305 	register short *sp;
306 	register t;
307 	datum item;
308 
309 	sp = (short *)buf;
310 	if(n < 0 || n >= sp[0])
311 		goto null;
312 	t = PBLKSIZ;
313 	if(n > 0)
314 		t = sp[n+1-1];
315 	item.dptr = buf+sp[n+1];
316 	item.dsize = t - sp[n+1];
317 	return(item);
318 
319 null:
320 	item.dptr = NULL;
321 	item.dsize = 0;
322 	return(item);
323 }
324 
325 cmpdatum(d1, d2)
326 datum d1, d2;
327 {
328 	register n;
329 	register char *p1, *p2;
330 
331 	n = d1.dsize;
332 	if(n != d2.dsize)
333 		return(n - d2.dsize);
334 	if(n == 0)
335 		return(0);
336 	p1 = d1.dptr;
337 	p2 = d2.dptr;
338 	do
339 		if(*p1++ != *p2++)
340 			return(*--p1 - *--p2);
341 	while(--n);
342 	return(0);
343 }
344 
345 int	hitab[16]
346 /* ken's
347 {
348 	055,043,036,054,063,014,004,005,
349 	010,064,077,000,035,027,025,071,
350 };
351 */
352  = {	61, 57, 53, 49, 45, 41, 37, 33,
353 	29, 25, 21, 17, 13,  9,  5,  1,
354 };
355 long	hltab[64]
356  = {
357 	06100151277L,06106161736L,06452611562L,05001724107L,
358 	02614772546L,04120731531L,04665262210L,07347467531L,
359 	06735253126L,06042345173L,03072226605L,01464164730L,
360 	03247435524L,07652510057L,01546775256L,05714532133L,
361 	06173260402L,07517101630L,02431460343L,01743245566L,
362 	00261675137L,02433103631L,03421772437L,04447707466L,
363 	04435620103L,03757017115L,03641531772L,06767633246L,
364 	02673230344L,00260612216L,04133454451L,00615531516L,
365 	06137717526L,02574116560L,02304023373L,07061702261L,
366 	05153031405L,05322056705L,07401116734L,06552375715L,
367 	06165233473L,05311063631L,01212221723L,01052267235L,
368 	06000615237L,01075222665L,06330216006L,04402355630L,
369 	01451177262L,02000133436L,06025467062L,07121076461L,
370 	03123433522L,01010635225L,01716177066L,05161746527L,
371 	01736635071L,06243505026L,03637211610L,01756474365L,
372 	04723077174L,03642763134L,05750130273L,03655541561L,
373 };
374 
375 long
376 hashinc(hash)
377 long hash;
378 {
379 	long bit;
380 
381 	hash &= hmask;
382 	bit = hmask+1;
383 	for(;;) {
384 		bit >>= 1;
385 		if(bit == 0)
386 			return(0L);
387 		if((hash&bit) == 0)
388 			return(hash|bit);
389 		hash &= ~bit;
390 	}
391 }
392 
393 long
394 calchash(item)
395 datum item;
396 {
397 	register i, j, f;
398 	long hashl;
399 	int hashi;
400 
401 	hashl = 0;
402 	hashi = 0;
403 	for(i=0; i<item.dsize; i++) {
404 		f = item.dptr[i];
405 		for(j=0; j<BYTESIZ; j+=4) {
406 			hashi += hitab[f&017];
407 			hashl += hltab[hashi&63];
408 			f >>= 4;
409 		}
410 	}
411 	return(hashl);
412 }
413 
414 delitem(buf, n)
415 char buf[PBLKSIZ];
416 {
417 	register short *sp;
418 	register i1, i2, i3;
419 
420 	sp = (short *)buf;
421 	if(n < 0 || n >= sp[0])
422 		goto bad;
423 	i1 = sp[n+1];
424 	i2 = PBLKSIZ;
425 	if(n > 0)
426 		i2 = sp[n+1-1];
427 	i3 = sp[sp[0]+1-1];
428 	if(i2 > i1)
429 	while(i1 > i3) {
430 		i1--;
431 		i2--;
432 		buf[i2] = buf[i1];
433 		buf[i1] = 0;
434 	}
435 	i2 -= i1;
436 	for(i1=n+1; i1<sp[0]; i1++)
437 		sp[i1+1-1] = sp[i1+1] + i2;
438 	sp[0]--;
439 	sp[sp[0]+1] = 0;
440 	return;
441 
442 bad:
443 	printf("dbm: bad delitem\n");
444 	abort();
445 }
446 
447 additem(buf, item)
448 char buf[PBLKSIZ];
449 datum item;
450 {
451 	register short *sp;
452 	register i1, i2;
453 
454 	sp = (short *)buf;
455 	i1 = PBLKSIZ;
456 	if(sp[0] > 0)
457 		i1 = sp[sp[0]+1-1];
458 	i1 -= item.dsize;
459 	i2 = (sp[0]+2) * sizeof(short);
460 	if(i1 <= i2)
461 		return(-1);
462 	sp[sp[0]+1] = i1;
463 	for(i2=0; i2<item.dsize; i2++) {
464 		buf[i1] = item.dptr[i2];
465 		i1++;
466 	}
467 	sp[0]++;
468 	return(sp[0]-1);
469 }
470 
471 chkblk(buf)
472 char buf[PBLKSIZ];
473 {
474 	register short *sp;
475 	register t, i;
476 
477 	sp = (short *)buf;
478 	t = PBLKSIZ;
479 	for(i=0; i<sp[0]; i++) {
480 		if(sp[i+1] > t)
481 			goto bad;
482 		t = sp[i+1];
483 	}
484 	if(t < (sp[0]+1)*sizeof(short))
485 		goto bad;
486 	return;
487 
488 bad:
489 	printf("dbm: bad block\n");
490 	abort();
491 	clrbuf(buf, PBLKSIZ);
492 }
493