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