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