Annotation of parser3/src/lib/sdbm/sdbm.c, revision 1.3
1.1 paf 1: /* ====================================================================
2: * The Apache Software License, Version 1.1
3: *
4: * Copyright (c) 2000-2002 The Apache Software Foundation. All rights
5: * reserved.
6: *
7: * Redistribution and use in source and binary forms, with or without
8: * modification, are permitted provided that the following conditions
9: * are met:
10: *
11: * 1. Redistributions of source code must retain the above copyright
12: * notice, this list of conditions and the following disclaimer.
13: *
14: * 2. Redistributions in binary form must reproduce the above copyright
15: * notice, this list of conditions and the following disclaimer in
16: * the documentation and/or other materials provided with the
17: * distribution.
18: *
19: * 3. The end-user documentation included with the redistribution,
20: * if any, must include the following acknowledgment:
21: * "This product includes software developed by the
22: * Apache Software Foundation (http://www.apache.org/)."
23: * Alternately, this acknowledgment may appear in the software itself,
24: * if and wherever such third-party acknowledgments normally appear.
25: *
26: * 4. The names "Apache" and "Apache Software Foundation" must
27: * not be used to endorse or promote products derived from this
28: * software without prior written permission. For written
29: * permission, please contact apache@apache.org.
30: *
31: * 5. Products derived from this software may not be called "Apache",
32: * nor may "Apache" appear in their name, without prior written
33: * permission of the Apache Software Foundation.
34: *
35: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
36: * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
37: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
38: * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
39: * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
40: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
41: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
42: * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
43: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
44: * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
45: * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
46: * SUCH DAMAGE.
47: * ====================================================================
48: *
49: * This software consists of voluntary contributions made by many
50: * individuals on behalf of the Apache Software Foundation. For more
51: * information on the Apache Software Foundation, please see
52: * <http://www.apache.org/>.
53: */
54:
55: /*
56: * sdbm - ndbm work-alike hashed database library
57: * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
58: * author: oz@nexus.yorku.ca
59: * ex-public domain, ported to APR for Apache 2
60: * core routines
61: */
62:
63: #include "apr.h"
64: #include "apr_file_io.h"
65: #include "apr_strings.h"
66: #include "apr_errno.h"
67: #include "apr_sdbm.h"
68:
69: #include "sdbm_tune.h"
70: #include "sdbm_pair.h"
71: #include "sdbm_private.h"
72:
73: #include <string.h> /* for memset() */
74: #include <stdlib.h> /* for malloc() and free() */
75:
76: /*
77: * forward
78: */
79: static int getdbit (apr_sdbm_t *, long);
80: static apr_status_t setdbit(apr_sdbm_t *, long);
81: static apr_status_t getpage(apr_sdbm_t *db, long);
82: static apr_status_t getnext(apr_sdbm_datum_t *key, apr_sdbm_t *db);
83: static apr_status_t makroom(apr_sdbm_t *, long, int);
84:
85: /*
86: * useful macros
87: */
88: #define bad(x) ((x).dptr == NULL || (x).dsize <= 0)
89: #define exhash(item) sdbm_hash((item).dptr, (item).dsize)
90:
91: /* ### Does anything need these externally? */
92: #define sdbm_dirfno(db) ((db)->dirf)
93: #define sdbm_pagfno(db) ((db)->pagf)
94:
95: #define OFF_PAG(off) (apr_off_t) (off) * PBLKSIZ
96: #define OFF_DIR(off) (apr_off_t) (off) * DBLKSIZ
97:
98: static long masks[] = {
99: 000000000000, 000000000001, 000000000003, 000000000007,
100: 000000000017, 000000000037, 000000000077, 000000000177,
101: 000000000377, 000000000777, 000000001777, 000000003777,
102: 000000007777, 000000017777, 000000037777, 000000077777,
103: 000000177777, 000000377777, 000000777777, 000001777777,
104: 000003777777, 000007777777, 000017777777, 000037777777,
105: 000077777777, 000177777777, 000377777777, 000777777777,
106: 001777777777, 003777777777, 007777777777, 017777777777
107: };
108:
109: const apr_sdbm_datum_t sdbm_nullitem = { NULL, 0 };
110:
111: static apr_status_t database_cleanup(void *data)
112: {
113: apr_sdbm_t *db = data;
114:
115: /*
116: * Can't rely on apr_sdbm_unlock, since it will merely
117: * decrement the refcnt if several locks are held.
118: */
119: if (db->flags & (SDBM_SHARED_LOCK | SDBM_EXCLUSIVE_LOCK))
120: (void) apr_file_unlock(db->dirf);
121: (void) apr_file_close(db->dirf);
122: (void) apr_file_close(db->pagf);
123: free(db);
124:
125: return APR_SUCCESS;
126: }
127:
128: static apr_status_t prep(apr_sdbm_t **pdb, const char *dirname, const char *pagname,
129: apr_int32_t flags, apr_fileperms_t perms, apr_pool_t *p)
130: {
131: apr_sdbm_t *db;
132: apr_status_t status;
133:
134: *pdb = NULL;
135:
136: db = malloc(sizeof(*db));
137: memset(db, 0, sizeof(*db));
138:
139: db->pool = p;
140:
141: /*
142: * adjust user flags so that WRONLY becomes RDWR,
143: * as required by this package. Also set our internal
144: * flag for RDONLY if needed.
145: */
146: if (!(flags & APR_WRITE)) {
147: db->flags |= SDBM_RDONLY;
148: }
149:
150: /*
151: * adjust the file open flags so that we handle locking
152: * on our own (don't rely on any locking behavior within
153: * an apr_file_t, in case it's ever introduced, and set
154: * our own flag.
155: */
156: if (flags & APR_SHARELOCK) {
157: db->flags |= SDBM_SHARED;
158: flags &= ~APR_SHARELOCK;
159: }
160:
161: flags |= APR_BINARY | APR_READ;
162:
163: /*
164: * open the files in sequence, and stat the dirfile.
165: * If we fail anywhere, undo everything, return NULL.
166: */
167:
168: if ((status = apr_file_open(&db->dirf, dirname, flags, perms, p))
169: != APR_SUCCESS)
170: goto error;
171:
172: if ((status = apr_file_open(&db->pagf, pagname, flags, perms, p))
173: != APR_SUCCESS)
174: goto error;
175:
176: if ((status = apr_sdbm_lock(db, (db->flags & SDBM_RDONLY)
177: ? APR_FLOCK_SHARED
178: : APR_FLOCK_EXCLUSIVE))
179: != APR_SUCCESS)
180: goto error;
181:
182: /* apr_pcalloc zeroed the buffers
183: * apr_sdbm_lock stated the dirf->size and invalidated the cache
184: */
185:
186: /*
187: * if we are opened in SHARED mode, unlock ourself
188: */
189: if (db->flags & SDBM_SHARED)
190: if ((status = apr_sdbm_unlock(db)) != APR_SUCCESS)
191: goto error;
192:
193: /* make sure that we close the database at some point */
1.2 paf 194: //apr_pool_cleanup_register(p, db, database_cleanup, apr_pool_cleanup_null);
1.1 paf 195:
196: /* Done! */
197: *pdb = db;
198: return APR_SUCCESS;
199:
200: error:
201: if (db->dirf && db->pagf)
202: (void) apr_sdbm_unlock(db);
203: if (db->dirf != NULL)
204: (void) apr_file_close(db->dirf);
205: if (db->pagf != NULL) {
206: (void) apr_file_close(db->pagf);
207: }
208: free(db);
209: return status;
210: }
211:
212: APU_DECLARE(apr_status_t) apr_sdbm_open(apr_sdbm_t **db, const char *file,
213: apr_int32_t flags,
214: apr_fileperms_t perms, apr_pool_t *p)
215: {
216: char *dirname = apr_pstrcat(p, file, APR_SDBM_DIRFEXT, NULL);
217: char *pagname = apr_pstrcat(p, file, APR_SDBM_PAGFEXT, NULL);
218:
219: return prep(db, dirname, pagname, flags, perms, p);
220: }
221:
222: APU_DECLARE(apr_status_t) apr_sdbm_close(apr_sdbm_t *db)
223: {
1.2 paf 224: database_cleanup(db); return APR_SUCCESS;
225: //return apr_pool_cleanup_run(db->pool, db, database_cleanup);
1.1 paf 226: }
227:
228: APU_DECLARE(apr_status_t) apr_sdbm_fetch(apr_sdbm_t *db, apr_sdbm_datum_t *val,
229: apr_sdbm_datum_t key)
230: {
231: apr_status_t status;
232:
233: if (db == NULL || bad(key))
234: return APR_EINVAL;
235:
236: if ((status = apr_sdbm_lock(db, APR_FLOCK_SHARED)) != APR_SUCCESS)
237: return status;
238:
239: if ((status = getpage(db, exhash(key))) == APR_SUCCESS) {
240: *val = getpair(db->pagbuf, key);
241: /* ### do we want a not-found result? */
242: }
243:
244: (void) apr_sdbm_unlock(db);
245:
246: return status;
247: }
248:
249: static apr_status_t write_page(apr_sdbm_t *db, const char *buf, long pagno)
250: {
251: apr_status_t status;
252: apr_off_t off = OFF_PAG(pagno);
253:
254: if ((status = apr_file_seek(db->pagf, APR_SET, &off)) == APR_SUCCESS)
255: status = apr_file_write_full(db->pagf, buf, PBLKSIZ, NULL);
256:
257: return status;
258: }
259:
260: APU_DECLARE(apr_status_t) apr_sdbm_delete(apr_sdbm_t *db,
261: const apr_sdbm_datum_t key)
262: {
263: apr_status_t status;
264:
265: if (db == NULL || bad(key))
266: return APR_EINVAL;
267: if (apr_sdbm_rdonly(db))
268: return APR_EINVAL;
269:
270: if ((status = apr_sdbm_lock(db, APR_FLOCK_EXCLUSIVE)) != APR_SUCCESS)
271: return status;
272:
273: if ((status = getpage(db, exhash(key))) == APR_SUCCESS) {
274: if (!delpair(db->pagbuf, key))
275: /* ### should we define some APRUTIL codes? */
1.3 ! paf 276: status = APR_SUCCESS; /* PAF: were APR_EGENERAL, contradicting comment in .h file :( */
1.1 paf 277: else
278: status = write_page(db, db->pagbuf, db->pagbno);
279: }
280:
281: (void) apr_sdbm_unlock(db);
282:
283: return status;
284: }
285:
286: APU_DECLARE(apr_status_t) apr_sdbm_store(apr_sdbm_t *db, apr_sdbm_datum_t key,
287: apr_sdbm_datum_t val, int flags)
288: {
289: int need;
290: register long hash;
291: apr_status_t status;
292:
293: if (db == NULL || bad(key))
294: return APR_EINVAL;
295: if (apr_sdbm_rdonly(db))
296: return APR_EINVAL;
297: need = key.dsize + val.dsize;
298: /*
299: * is the pair too big (or too small) for this database ??
300: */
301: if (need < 0 || need > PAIRMAX)
302: return APR_EINVAL;
303:
304: if ((status = apr_sdbm_lock(db, APR_FLOCK_EXCLUSIVE)) != APR_SUCCESS)
305: return status;
306:
307: if ((status = getpage(db, (hash = exhash(key)))) == APR_SUCCESS) {
308:
309: /*
310: * if we need to replace, delete the key/data pair
311: * first. If it is not there, ignore.
312: */
313: if (flags == APR_SDBM_REPLACE)
314: (void) delpair(db->pagbuf, key);
315: else if (!(flags & APR_SDBM_INSERTDUP) && duppair(db->pagbuf, key)) {
316: status = APR_EEXIST;
317: goto error;
318: }
319: /*
320: * if we do not have enough room, we have to split.
321: */
322: if (!fitpair(db->pagbuf, need))
323: if ((status = makroom(db, hash, need)) != APR_SUCCESS)
324: goto error;
325: /*
326: * we have enough room or split is successful. insert the key,
327: * and update the page file.
328: */
329: (void) putpair(db->pagbuf, key, val);
330:
331: status = write_page(db, db->pagbuf, db->pagbno);
332: }
333:
334: error:
335: (void) apr_sdbm_unlock(db);
336:
337: return status;
338: }
339:
340: /*
341: * makroom - make room by splitting the overfull page
342: * this routine will attempt to make room for SPLTMAX times before
343: * giving up.
344: */
345: static apr_status_t makroom(apr_sdbm_t *db, long hash, int need)
346: {
347: long newp;
348: char twin[PBLKSIZ];
349: char *pag = db->pagbuf;
350: char *new = twin;
351: register int smax = SPLTMAX;
352: apr_status_t status;
353:
354: do {
355: /*
356: * split the current page
357: */
358: (void) splpage(pag, new, db->hmask + 1);
359: /*
360: * address of the new page
361: */
362: newp = (hash & db->hmask) | (db->hmask + 1);
363:
364: /*
365: * write delay, read avoidence/cache shuffle:
366: * select the page for incoming pair: if key is to go to the new page,
367: * write out the previous one, and copy the new one over, thus making
368: * it the current page. If not, simply write the new page, and we are
369: * still looking at the page of interest. current page is not updated
370: * here, as sdbm_store will do so, after it inserts the incoming pair.
371: */
372: if (hash & (db->hmask + 1)) {
373: if ((status = write_page(db, db->pagbuf, db->pagbno))
374: != APR_SUCCESS)
375: return status;
376:
377: db->pagbno = newp;
378: (void) memcpy(pag, new, PBLKSIZ);
379: }
380: else {
381: if ((status = write_page(db, new, newp)) != APR_SUCCESS)
382: return status;
383: }
384:
385: if ((status = setdbit(db, db->curbit)) != APR_SUCCESS)
386: return status;
387: /*
388: * see if we have enough room now
389: */
390: if (fitpair(pag, need))
391: return APR_SUCCESS;
392: /*
393: * try again... update curbit and hmask as getpage would have
394: * done. because of our update of the current page, we do not
395: * need to read in anything. BUT we have to write the current
396: * [deferred] page out, as the window of failure is too great.
397: */
398: db->curbit = 2 * db->curbit
399: + ((hash & (db->hmask + 1)) ? 2 : 1);
400: db->hmask |= db->hmask + 1;
401:
402: if ((status = write_page(db, db->pagbuf, db->pagbno))
403: != APR_SUCCESS)
404: return status;
405:
406: } while (--smax);
407:
408: /*
409: * if we are here, this is real bad news. After SPLTMAX splits,
410: * we still cannot fit the key. say goodnight.
411: */
412: #if 0
413: (void) write(2, "sdbm: cannot insert after SPLTMAX attempts.\n", 44);
414: #endif
415: /* ### ENOSPC not really appropriate but better than nothing */
416: return APR_ENOSPC;
417:
418: }
419:
420: /* Reads 'len' bytes from file 'f' at offset 'off' into buf.
421: * 'off' is given relative to the start of the file.
422: * If EOF is returned while reading, this is taken as success.
423: */
424: static apr_status_t read_from(apr_file_t *f, void *buf,
425: apr_off_t off, apr_size_t len)
426: {
427: apr_status_t status;
428:
429: if ((status = apr_file_seek(f, APR_SET, &off)) != APR_SUCCESS ||
430: ((status = apr_file_read_full(f, buf, len, NULL)) != APR_SUCCESS)) {
431: /* if EOF is reached, pretend we read all zero's */
432: if (status == APR_EOF) {
433: memset(buf, 0, len);
434: status = APR_SUCCESS;
435: }
436: }
437:
438: return status;
439: }
440:
441: /*
442: * the following two routines will break if
443: * deletions aren't taken into account. (ndbm bug)
444: */
445: APU_DECLARE(apr_status_t) apr_sdbm_firstkey(apr_sdbm_t *db,
446: apr_sdbm_datum_t *key)
447: {
448: apr_status_t status;
449:
450: if ((status = apr_sdbm_lock(db, APR_FLOCK_SHARED)) != APR_SUCCESS)
451: return status;
452:
453: /*
454: * start at page 0
455: */
456: if ((status = read_from(db->pagf, db->pagbuf, OFF_PAG(0), PBLKSIZ))
457: == APR_SUCCESS) {
458: db->pagbno = 0;
459: db->blkptr = 0;
460: db->keyptr = 0;
461: status = getnext(key, db);
462: }
463:
464: (void) apr_sdbm_unlock(db);
465:
466: return status;
467: }
468:
469: APU_DECLARE(apr_status_t) apr_sdbm_nextkey(apr_sdbm_t *db,
470: apr_sdbm_datum_t *key)
471: {
472: apr_status_t status;
473:
474: if ((status = apr_sdbm_lock(db, APR_FLOCK_SHARED)) != APR_SUCCESS)
475: return status;
476:
477: status = getnext(key, db);
478:
479: (void) apr_sdbm_unlock(db);
480:
481: return status;
482: }
483:
484: /*
485: * all important binary tree traversal
486: */
487: static apr_status_t getpage(apr_sdbm_t *db, long hash)
488: {
489: register int hbit;
490: register long dbit;
491: register long pagb;
492: apr_status_t status;
493:
494: dbit = 0;
495: hbit = 0;
496: while (dbit < db->maxbno && getdbit(db, dbit))
497: dbit = 2 * dbit + ((hash & (1 << hbit++)) ? 2 : 1);
498:
499: debug(("dbit: %d...", dbit));
500:
501: db->curbit = dbit;
502: db->hmask = masks[hbit];
503:
504: pagb = hash & db->hmask;
505: /*
506: * see if the block we need is already in memory.
507: * note: this lookaside cache has about 10% hit rate.
508: */
509: if (pagb != db->pagbno) {
510: /*
511: * note: here, we assume a "hole" is read as 0s.
512: * if not, must zero pagbuf first.
513: * ### joe: this assumption was surely never correct? but
514: * ### we make it so in read_from anyway.
515: */
516: if ((status = read_from(db->pagf, db->pagbuf, OFF_PAG(pagb), PBLKSIZ))
517: != APR_SUCCESS)
518: return status;
519:
520: if (!chkpage(db->pagbuf))
521: return APR_ENOSPC; /* ### better error? */
522: db->pagbno = pagb;
523:
524: debug(("pag read: %d\n", pagb));
525: }
526: return APR_SUCCESS;
527: }
528:
529: static int getdbit(apr_sdbm_t *db, long dbit)
530: {
531: register long c;
532: register long dirb;
533:
534: c = dbit / BYTESIZ;
535: dirb = c / DBLKSIZ;
536:
537: if (dirb != db->dirbno) {
538: if (read_from(db->dirf, db->dirbuf, OFF_DIR(dirb), DBLKSIZ)
539: != APR_SUCCESS)
540: return 0;
541:
542: db->dirbno = dirb;
543:
544: debug(("dir read: %d\n", dirb));
545: }
546:
547: return db->dirbuf[c % DBLKSIZ] & (1 << dbit % BYTESIZ);
548: }
549:
550: static apr_status_t setdbit(apr_sdbm_t *db, long dbit)
551: {
552: register long c;
553: register long dirb;
554: apr_status_t status;
555: apr_off_t off;
556:
557: c = dbit / BYTESIZ;
558: dirb = c / DBLKSIZ;
559:
560: if (dirb != db->dirbno) {
561: if ((status = read_from(db->dirf, db->dirbuf, OFF_DIR(dirb), DBLKSIZ))
562: != APR_SUCCESS)
563: return status;
564:
565: db->dirbno = dirb;
566:
567: debug(("dir read: %d\n", dirb));
568: }
569:
570: db->dirbuf[c % DBLKSIZ] |= (1 << dbit % BYTESIZ);
571:
572: if (dbit >= db->maxbno)
573: db->maxbno += DBLKSIZ * BYTESIZ;
574:
575: off = OFF_DIR(dirb);
576: if ((status = apr_file_seek(db->dirf, APR_SET, &off)) == APR_SUCCESS)
577: status = apr_file_write_full(db->dirf, db->dirbuf, DBLKSIZ, NULL);
578:
579: return status;
580: }
581:
582: /*
583: * getnext - get the next key in the page, and if done with
584: * the page, try the next page in sequence
585: */
586: static apr_status_t getnext(apr_sdbm_datum_t *key, apr_sdbm_t *db)
587: {
588: apr_status_t status;
589: for (;;) {
590: db->keyptr++;
591: *key = getnkey(db->pagbuf, db->keyptr);
592: if (key->dptr != NULL)
593: return APR_SUCCESS;
594: /*
595: * we either run out, or there is nothing on this page..
596: * try the next one... If we lost our position on the
597: * file, we will have to seek.
598: */
599: db->keyptr = 0;
600: if (db->pagbno != db->blkptr++) {
601: apr_off_t off = OFF_PAG(db->blkptr);
602: if ((status = apr_file_seek(db->pagf, APR_SET, &off)
603: != APR_SUCCESS))
604: return status;
605: }
606:
607: db->pagbno = db->blkptr;
608: /* ### EOF acceptable here too? */
609: if ((status = apr_file_read_full(db->pagf, db->pagbuf, PBLKSIZ, NULL))
610: != APR_SUCCESS)
611: return status;
612: if (!chkpage(db->pagbuf))
613: return APR_EGENERAL; /* ### need better error */
614: }
615:
616: /* NOTREACHED */
617: }
618:
619:
620: APU_DECLARE(int) apr_sdbm_rdonly(apr_sdbm_t *db)
621: {
622: /* ### Should we return true if the first lock is a share lock,
623: * to reflect that apr_sdbm_store and apr_sdbm_delete will fail?
624: */
625: return (db->flags & SDBM_RDONLY) != 0;
626: }
627:
E-mail:
![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to sdbm.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [parser3project] / parser3 / src / lib / sdbm