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