1 /*-
2 * Copyright (c) 1983 The Regents of the University of California.
3 * All rights reserved.
4 *
5 * %sccs.include.proprietary.c%
6 */
7
8 #if defined(LIBC_SCCS) && !defined(lint)
9 static char sccsid[] = "@(#)ndbm.c 5.7 (Berkeley) 04/22/91";
10 #endif /* LIBC_SCCS and not lint */
11
12 #include <sys/types.h>
13 #include <sys/stat.h>
14 #include <sys/file.h>
15 #include <stdio.h>
16 #include <errno.h>
17 #include "ndbm.h"
18
19 #define BYTESIZ 8
20 #undef setbit
21
22 static datum makdatum();
23 static long hashinc();
24 static long dcalchash();
25 static int additem(), delitem(), finddatum(), getbit();
26 static void dbm_access(), setbit();
27 extern int errno;
28
29 DBM *
dbm_open(file,flags,mode)30 dbm_open(file, flags, mode)
31 const char *file;
32 int flags, mode;
33 {
34 struct stat statb;
35 register DBM *db;
36
37 if ((db = (DBM *)malloc(sizeof *db)) == 0) {
38 errno = ENOMEM;
39 return ((DBM *)0);
40 }
41 db->dbm_flags = (flags & 03) == O_RDONLY ? _DBM_RDONLY : 0;
42 if ((flags & 03) == O_WRONLY)
43 flags = (flags & ~03) | O_RDWR;
44 strcpy(db->dbm_pagbuf, file);
45 strcat(db->dbm_pagbuf, ".pag");
46 db->dbm_pagf = open(db->dbm_pagbuf, flags, mode);
47 if (db->dbm_pagf < 0)
48 goto bad;
49 strcpy(db->dbm_pagbuf, file);
50 strcat(db->dbm_pagbuf, ".dir");
51 db->dbm_dirf = open(db->dbm_pagbuf, flags, mode);
52 if (db->dbm_dirf < 0)
53 goto bad1;
54 fstat(db->dbm_dirf, &statb);
55 db->dbm_maxbno = statb.st_size*BYTESIZ-1;
56 db->dbm_pagbno = db->dbm_dirbno = -1;
57 return (db);
58 bad1:
59 (void) close(db->dbm_pagf);
60 bad:
61 free((char *)db);
62 return ((DBM *)0);
63 }
64
65 void
dbm_close(db)66 dbm_close(db)
67 DBM *db;
68 {
69
70 (void) close(db->dbm_dirf);
71 (void) close(db->dbm_pagf);
72 free((char *)db);
73 }
74
75 long
dbm_forder(db,key)76 dbm_forder(db, key)
77 register DBM *db;
78 datum key;
79 {
80 long hash;
81
82 hash = dcalchash(key);
83 for (db->dbm_hmask=0;; db->dbm_hmask=(db->dbm_hmask<<1)+1) {
84 db->dbm_blkno = hash & db->dbm_hmask;
85 db->dbm_bitno = db->dbm_blkno + db->dbm_hmask;
86 if (getbit(db) == 0)
87 break;
88 }
89 return (db->dbm_blkno);
90 }
91
92 datum
dbm_fetch(db,key)93 dbm_fetch(db, key)
94 register DBM *db;
95 datum key;
96 {
97 register i;
98 datum item;
99
100 if (dbm_error(db))
101 goto err;
102 dbm_access(db, dcalchash(key));
103 if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) {
104 item = makdatum(db->dbm_pagbuf, i+1);
105 if (item.dptr != NULL)
106 return (item);
107 }
108 err:
109 item.dptr = NULL;
110 item.dsize = 0;
111 return (item);
112 }
113
dbm_delete(db,key)114 dbm_delete(db, key)
115 register DBM *db;
116 datum key;
117 {
118 register i;
119 datum item;
120
121 if (dbm_error(db))
122 return (-1);
123 if (dbm_rdonly(db)) {
124 errno = EPERM;
125 return (-1);
126 }
127 dbm_access(db, dcalchash(key));
128 if ((i = finddatum(db->dbm_pagbuf, key)) < 0)
129 return (-1);
130 if (!delitem(db->dbm_pagbuf, i))
131 goto err;
132 db->dbm_pagbno = db->dbm_blkno;
133 (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
134 if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
135 err:
136 db->dbm_flags |= _DBM_IOERR;
137 return (-1);
138 }
139 return (0);
140 }
141
dbm_store(db,key,dat,replace)142 dbm_store(db, key, dat, replace)
143 register DBM *db;
144 datum key, dat;
145 int replace;
146 {
147 register i;
148 datum item, item1;
149 char ovfbuf[PBLKSIZ];
150
151 if (dbm_error(db))
152 return (-1);
153 if (dbm_rdonly(db)) {
154 errno = EPERM;
155 return (-1);
156 }
157 loop:
158 dbm_access(db, dcalchash(key));
159 if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) {
160 if (!replace)
161 return (1);
162 if (!delitem(db->dbm_pagbuf, i)) {
163 db->dbm_flags |= _DBM_IOERR;
164 return (-1);
165 }
166 }
167 if (!additem(db->dbm_pagbuf, key, dat))
168 goto split;
169 db->dbm_pagbno = db->dbm_blkno;
170 (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
171 if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
172 db->dbm_flags |= _DBM_IOERR;
173 return (-1);
174 }
175 return (0);
176
177 split:
178 if (key.dsize+dat.dsize+3*sizeof(short) >= PBLKSIZ) {
179 db->dbm_flags |= _DBM_IOERR;
180 errno = ENOSPC;
181 return (-1);
182 }
183 bzero(ovfbuf, PBLKSIZ);
184 for (i=0;;) {
185 item = makdatum(db->dbm_pagbuf, i);
186 if (item.dptr == NULL)
187 break;
188 if (dcalchash(item) & (db->dbm_hmask+1)) {
189 item1 = makdatum(db->dbm_pagbuf, i+1);
190 if (item1.dptr == NULL) {
191 fprintf(stderr, "ndbm: split not paired\n");
192 db->dbm_flags |= _DBM_IOERR;
193 break;
194 }
195 if (!additem(ovfbuf, item, item1) ||
196 !delitem(db->dbm_pagbuf, i)) {
197 db->dbm_flags |= _DBM_IOERR;
198 return (-1);
199 }
200 continue;
201 }
202 i += 2;
203 }
204 db->dbm_pagbno = db->dbm_blkno;
205 (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
206 if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
207 db->dbm_flags |= _DBM_IOERR;
208 return (-1);
209 }
210 (void) lseek(db->dbm_pagf, (db->dbm_blkno+db->dbm_hmask+1)*PBLKSIZ, L_SET);
211 if (write(db->dbm_pagf, ovfbuf, PBLKSIZ) != PBLKSIZ) {
212 db->dbm_flags |= _DBM_IOERR;
213 return (-1);
214 }
215 setbit(db);
216 goto loop;
217 }
218
219 datum
dbm_firstkey(db)220 dbm_firstkey(db)
221 DBM *db;
222 {
223
224 db->dbm_blkptr = 0L;
225 db->dbm_keyptr = 0;
226 return (dbm_nextkey(db));
227 }
228
229 datum
dbm_nextkey(db)230 dbm_nextkey(db)
231 register DBM *db;
232 {
233 struct stat statb;
234 datum item;
235
236 if (dbm_error(db) || fstat(db->dbm_pagf, &statb) < 0)
237 goto err;
238 statb.st_size /= PBLKSIZ;
239 for (;;) {
240 if (db->dbm_blkptr != db->dbm_pagbno) {
241 db->dbm_pagbno = db->dbm_blkptr;
242 (void) lseek(db->dbm_pagf, db->dbm_blkptr*PBLKSIZ, L_SET);
243 if (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)
244 bzero(db->dbm_pagbuf, PBLKSIZ);
245 #ifdef DEBUG
246 else if (chkblk(db->dbm_pagbuf) < 0)
247 db->dbm_flags |= _DBM_IOERR;
248 #endif
249 }
250 if (((short *)db->dbm_pagbuf)[0] != 0) {
251 item = makdatum(db->dbm_pagbuf, db->dbm_keyptr);
252 if (item.dptr != NULL) {
253 db->dbm_keyptr += 2;
254 return (item);
255 }
256 db->dbm_keyptr = 0;
257 }
258 if (++db->dbm_blkptr >= statb.st_size)
259 break;
260 }
261 err:
262 item.dptr = NULL;
263 item.dsize = 0;
264 return (item);
265 }
266
267 static void
dbm_access(db,hash)268 dbm_access(db, hash)
269 register DBM *db;
270 long hash;
271 {
272
273 for (db->dbm_hmask=0;; db->dbm_hmask=(db->dbm_hmask<<1)+1) {
274 db->dbm_blkno = hash & db->dbm_hmask;
275 db->dbm_bitno = db->dbm_blkno + db->dbm_hmask;
276 if (getbit(db) == 0)
277 break;
278 }
279 if (db->dbm_blkno != db->dbm_pagbno) {
280 db->dbm_pagbno = db->dbm_blkno;
281 (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
282 if (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)
283 bzero(db->dbm_pagbuf, PBLKSIZ);
284 #ifdef DEBUG
285 else if (chkblk(db->dbm_pagbuf) < 0)
286 db->dbm_flags |= _DBM_IOERR;
287 #endif
288 }
289 }
290
291 static
getbit(db)292 getbit(db)
293 register DBM *db;
294 {
295 long bn;
296 register b, i, n;
297
298
299 if (db->dbm_bitno > db->dbm_maxbno)
300 return (0);
301 n = db->dbm_bitno % BYTESIZ;
302 bn = db->dbm_bitno / BYTESIZ;
303 i = bn % DBLKSIZ;
304 b = bn / DBLKSIZ;
305 if (b != db->dbm_dirbno) {
306 db->dbm_dirbno = b;
307 (void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET);
308 if (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
309 bzero(db->dbm_dirbuf, DBLKSIZ);
310 }
311 return (db->dbm_dirbuf[i] & (1<<n));
312 }
313
314 static void
setbit(db)315 setbit(db)
316 register DBM *db;
317 {
318 long bn;
319 register i, n, b;
320
321 if (db->dbm_bitno > db->dbm_maxbno)
322 db->dbm_maxbno = db->dbm_bitno;
323 n = db->dbm_bitno % BYTESIZ;
324 bn = db->dbm_bitno / BYTESIZ;
325 i = bn % DBLKSIZ;
326 b = bn / DBLKSIZ;
327 if (b != db->dbm_dirbno) {
328 db->dbm_dirbno = b;
329 (void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET);
330 if (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
331 bzero(db->dbm_dirbuf, DBLKSIZ);
332 }
333 db->dbm_dirbuf[i] |= 1<<n;
334 db->dbm_dirbno = b;
335 (void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET);
336 if (write(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
337 db->dbm_flags |= _DBM_IOERR;
338 }
339
340 static datum
makdatum(buf,n)341 makdatum(buf, n)
342 char buf[PBLKSIZ];
343 {
344 register short *sp;
345 register t;
346 datum item;
347
348 sp = (short *)buf;
349 if ((unsigned)n >= sp[0]) {
350 item.dptr = NULL;
351 item.dsize = 0;
352 return (item);
353 }
354 t = PBLKSIZ;
355 if (n > 0)
356 t = sp[n];
357 item.dptr = buf+sp[n+1];
358 item.dsize = t - sp[n+1];
359 return (item);
360 }
361
362 static
finddatum(buf,item)363 finddatum(buf, item)
364 char buf[PBLKSIZ];
365 datum item;
366 {
367 register short *sp;
368 register int i, n, j;
369
370 sp = (short *)buf;
371 n = PBLKSIZ;
372 for (i=0, j=sp[0]; i<j; i+=2, n = sp[i]) {
373 n -= sp[i+1];
374 if (n != item.dsize)
375 continue;
376 if (n == 0 || bcmp(&buf[sp[i+1]], item.dptr, n) == 0)
377 return (i);
378 }
379 return (-1);
380 }
381
382 static int hitab[16]
383 /* ken's
384 {
385 055,043,036,054,063,014,004,005,
386 010,064,077,000,035,027,025,071,
387 };
388 */
389 = { 61, 57, 53, 49, 45, 41, 37, 33,
390 29, 25, 21, 17, 13, 9, 5, 1,
391 };
392 static long hltab[64]
393 = {
394 06100151277L,06106161736L,06452611562L,05001724107L,
395 02614772546L,04120731531L,04665262210L,07347467531L,
396 06735253126L,06042345173L,03072226605L,01464164730L,
397 03247435524L,07652510057L,01546775256L,05714532133L,
398 06173260402L,07517101630L,02431460343L,01743245566L,
399 00261675137L,02433103631L,03421772437L,04447707466L,
400 04435620103L,03757017115L,03641531772L,06767633246L,
401 02673230344L,00260612216L,04133454451L,00615531516L,
402 06137717526L,02574116560L,02304023373L,07061702261L,
403 05153031405L,05322056705L,07401116734L,06552375715L,
404 06165233473L,05311063631L,01212221723L,01052267235L,
405 06000615237L,01075222665L,06330216006L,04402355630L,
406 01451177262L,02000133436L,06025467062L,07121076461L,
407 03123433522L,01010635225L,01716177066L,05161746527L,
408 01736635071L,06243505026L,03637211610L,01756474365L,
409 04723077174L,03642763134L,05750130273L,03655541561L,
410 };
411
412 static long
hashinc(db,hash)413 hashinc(db, hash)
414 register DBM *db;
415 long hash;
416 {
417 long bit;
418
419 hash &= db->dbm_hmask;
420 bit = db->dbm_hmask+1;
421 for (;;) {
422 bit >>= 1;
423 if (bit == 0)
424 return (0L);
425 if ((hash & bit) == 0)
426 return (hash | bit);
427 hash &= ~bit;
428 }
429 }
430
431 static long
dcalchash(item)432 dcalchash(item)
433 datum item;
434 {
435 register int s, c, j;
436 register char *cp;
437 register long hashl;
438 register int hashi;
439
440 hashl = 0;
441 hashi = 0;
442 for (cp = item.dptr, s=item.dsize; --s >= 0; ) {
443 c = *cp++;
444 for (j=0; j<BYTESIZ; j+=4) {
445 hashi += hitab[c&017];
446 hashl += hltab[hashi&63];
447 c >>= 4;
448 }
449 }
450 return (hashl);
451 }
452
453 /*
454 * Delete pairs of items (n & n+1).
455 */
456 static
delitem(buf,n)457 delitem(buf, n)
458 char buf[PBLKSIZ];
459 {
460 register short *sp, *sp1;
461 register i1, i2;
462
463 sp = (short *)buf;
464 i2 = sp[0];
465 if ((unsigned)n >= i2 || (n & 1))
466 return (0);
467 if (n == i2-2) {
468 sp[0] -= 2;
469 return (1);
470 }
471 i1 = PBLKSIZ;
472 if (n > 0)
473 i1 = sp[n];
474 i1 -= sp[n+2];
475 if (i1 > 0) {
476 i2 = sp[i2];
477 bcopy(&buf[i2], &buf[i2 + i1], sp[n+2] - i2);
478 }
479 sp[0] -= 2;
480 for (sp1 = sp + sp[0], sp += n+1; sp <= sp1; sp++)
481 sp[0] = sp[2] + i1;
482 return (1);
483 }
484
485 /*
486 * Add pairs of items (item & item1).
487 */
488 static
additem(buf,item,item1)489 additem(buf, item, item1)
490 char buf[PBLKSIZ];
491 datum item, item1;
492 {
493 register short *sp;
494 register i1, i2;
495
496 sp = (short *)buf;
497 i1 = PBLKSIZ;
498 i2 = sp[0];
499 if (i2 > 0)
500 i1 = sp[i2];
501 i1 -= item.dsize + item1.dsize;
502 if (i1 <= (i2+3) * (int)sizeof(short))
503 return (0);
504 sp[0] += 2;
505 sp[++i2] = i1 + item1.dsize;
506 bcopy(item.dptr, &buf[i1 + item1.dsize], item.dsize);
507 sp[++i2] = i1;
508 bcopy(item1.dptr, &buf[i1], item1.dsize);
509 return (1);
510 }
511
512 #ifdef DEBUG
513 static
chkblk(buf)514 chkblk(buf)
515 char buf[PBLKSIZ];
516 {
517 register short *sp;
518 register t, i;
519
520 sp = (short *)buf;
521 t = PBLKSIZ;
522 for (i=0; i<sp[0]; i++) {
523 if (sp[i+1] > t)
524 return (-1);
525 t = sp[i+1];
526 }
527 if (t < (sp[0]+1)*sizeof(short))
528 return (-1);
529 return (0);
530 }
531 #endif
532