Annotation of parser3/src/lib/sdbm/sdbm.c, revision 1.4
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() */
1.4 ! misha 74: // #include <stdlib.h> /* for malloc() and free() */
1.1 paf 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);
1.4 ! misha 123: // free(db); // libcg will do it
1.1 paf 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:
1.4 ! misha 136: // db = malloc(sizeof(*db));
! 137: // memset(db, 0, sizeof(*db));
! 138: db = apr_malloc(sizeof(*db));
1.1 paf 139:
140: db->pool = p;
141:
142: /*
143: * adjust user flags so that WRONLY becomes RDWR,
144: * as required by this package. Also set our internal
145: * flag for RDONLY if needed.
146: */
147: if (!(flags & APR_WRITE)) {
148: db->flags |= SDBM_RDONLY;
149: }
150:
151: /*
152: * adjust the file open flags so that we handle locking
153: * on our own (don't rely on any locking behavior within
154: * an apr_file_t, in case it's ever introduced, and set
155: * our own flag.
156: */
157: if (flags & APR_SHARELOCK) {
158: db->flags |= SDBM_SHARED;
159: flags &= ~APR_SHARELOCK;
160: }
161:
162: flags |= APR_BINARY | APR_READ;
163:
164: /*
165: * open the files in sequence, and stat the dirfile.
166: * If we fail anywhere, undo everything, return NULL.
167: */
168:
169: if ((status = apr_file_open(&db->dirf, dirname, flags, perms, p))
170: != APR_SUCCESS)
171: goto error;
172:
173: if ((status = apr_file_open(&db->pagf, pagname, flags, perms, p))
174: != APR_SUCCESS)
175: goto error;
176:
177: if ((status = apr_sdbm_lock(db, (db->flags & SDBM_RDONLY)
178: ? APR_FLOCK_SHARED
179: : APR_FLOCK_EXCLUSIVE))
180: != APR_SUCCESS)
181: goto error;
182:
183: /* apr_pcalloc zeroed the buffers
184: * apr_sdbm_lock stated the dirf->size and invalidated the cache
185: */
186:
187: /*
188: * if we are opened in SHARED mode, unlock ourself
189: */
190: if (db->flags & SDBM_SHARED)
191: if ((status = apr_sdbm_unlock(db)) != APR_SUCCESS)
192: goto error;
193:
194: /* make sure that we close the database at some point */
1.2 paf 195: //apr_pool_cleanup_register(p, db, database_cleanup, apr_pool_cleanup_null);
1.1 paf 196:
197: /* Done! */
198: *pdb = db;
199: return APR_SUCCESS;
200:
201: error:
202: if (db->dirf && db->pagf)
203: (void) apr_sdbm_unlock(db);
204: if (db->dirf != NULL)
205: (void) apr_file_close(db->dirf);
206: if (db->pagf != NULL) {
207: (void) apr_file_close(db->pagf);
208: }
1.4 ! misha 209: // free(db); // libcg will do it
1.1 paf 210: return status;
211: }
212:
213: APU_DECLARE(apr_status_t) apr_sdbm_open(apr_sdbm_t **db, const char *file,
214: apr_int32_t flags,
215: apr_fileperms_t perms, apr_pool_t *p)
216: {
217: char *dirname = apr_pstrcat(p, file, APR_SDBM_DIRFEXT, NULL);
218: char *pagname = apr_pstrcat(p, file, APR_SDBM_PAGFEXT, NULL);
219:
220: return prep(db, dirname, pagname, flags, perms, p);
221: }
222:
223: APU_DECLARE(apr_status_t) apr_sdbm_close(apr_sdbm_t *db)
224: {
1.2 paf 225: database_cleanup(db); return APR_SUCCESS;
226: //return apr_pool_cleanup_run(db->pool, db, database_cleanup);
1.1 paf 227: }
228:
229: APU_DECLARE(apr_status_t) apr_sdbm_fetch(apr_sdbm_t *db, apr_sdbm_datum_t *val,
230: apr_sdbm_datum_t key)
231: {
232: apr_status_t status;
233:
234: if (db == NULL || bad(key))
235: return APR_EINVAL;
236:
237: if ((status = apr_sdbm_lock(db, APR_FLOCK_SHARED)) != APR_SUCCESS)
238: return status;
239:
240: if ((status = getpage(db, exhash(key))) == APR_SUCCESS) {
241: *val = getpair(db->pagbuf, key);
242: /* ### do we want a not-found result? */
243: }
244:
245: (void) apr_sdbm_unlock(db);
246:
247: return status;
248: }
249:
250: static apr_status_t write_page(apr_sdbm_t *db, const char *buf, long pagno)
251: {
252: apr_status_t status;
253: apr_off_t off = OFF_PAG(pagno);
254:
255: if ((status = apr_file_seek(db->pagf, APR_SET, &off)) == APR_SUCCESS)
256: status = apr_file_write_full(db->pagf, buf, PBLKSIZ, NULL);
257:
258: return status;
259: }
260:
261: APU_DECLARE(apr_status_t) apr_sdbm_delete(apr_sdbm_t *db,
262: const apr_sdbm_datum_t key)
263: {
264: apr_status_t status;
265:
266: if (db == NULL || bad(key))
267: return APR_EINVAL;
268: if (apr_sdbm_rdonly(db))
269: return APR_EINVAL;
270:
271: if ((status = apr_sdbm_lock(db, APR_FLOCK_EXCLUSIVE)) != APR_SUCCESS)
272: return status;
273:
274: if ((status = getpage(db, exhash(key))) == APR_SUCCESS) {
275: if (!delpair(db->pagbuf, key))
276: /* ### should we define some APRUTIL codes? */
1.3 paf 277: status = APR_SUCCESS; /* PAF: were APR_EGENERAL, contradicting comment in .h file :( */
1.1 paf 278: else
279: status = write_page(db, db->pagbuf, db->pagbno);
280: }
281:
282: (void) apr_sdbm_unlock(db);
283:
284: return status;
285: }
286:
287: APU_DECLARE(apr_status_t) apr_sdbm_store(apr_sdbm_t *db, apr_sdbm_datum_t key,
288: apr_sdbm_datum_t val, int flags)
289: {
290: int need;
291: register long hash;
292: apr_status_t status;
293:
294: if (db == NULL || bad(key))
295: return APR_EINVAL;
296: if (apr_sdbm_rdonly(db))
297: return APR_EINVAL;
298: need = key.dsize + val.dsize;
299: /*
300: * is the pair too big (or too small) for this database ??
301: */
302: if (need < 0 || need > PAIRMAX)
303: return APR_EINVAL;
304:
305: if ((status = apr_sdbm_lock(db, APR_FLOCK_EXCLUSIVE)) != APR_SUCCESS)
306: return status;
307:
308: if ((status = getpage(db, (hash = exhash(key)))) == APR_SUCCESS) {
309:
310: /*
311: * if we need to replace, delete the key/data pair
312: * first. If it is not there, ignore.
313: */
314: if (flags == APR_SDBM_REPLACE)
315: (void) delpair(db->pagbuf, key);
316: else if (!(flags & APR_SDBM_INSERTDUP) && duppair(db->pagbuf, key)) {
317: status = APR_EEXIST;
318: goto error;
319: }
320: /*
321: * if we do not have enough room, we have to split.
322: */
323: if (!fitpair(db->pagbuf, need))
324: if ((status = makroom(db, hash, need)) != APR_SUCCESS)
325: goto error;
326: /*
327: * we have enough room or split is successful. insert the key,
328: * and update the page file.
329: */
330: (void) putpair(db->pagbuf, key, val);
331:
332: status = write_page(db, db->pagbuf, db->pagbno);
333: }
334:
335: error:
336: (void) apr_sdbm_unlock(db);
337:
338: return status;
339: }
340:
341: /*
342: * makroom - make room by splitting the overfull page
343: * this routine will attempt to make room for SPLTMAX times before
344: * giving up.
345: */
346: static apr_status_t makroom(apr_sdbm_t *db, long hash, int need)
347: {
348: long newp;
349: char twin[PBLKSIZ];
350: char *pag = db->pagbuf;
351: char *new = twin;
352: register int smax = SPLTMAX;
353: apr_status_t status;
354:
355: do {
356: /*
357: * split the current page
358: */
359: (void) splpage(pag, new, db->hmask + 1);
360: /*
361: * address of the new page
362: */
363: newp = (hash & db->hmask) | (db->hmask + 1);
364:
365: /*
366: * write delay, read avoidence/cache shuffle:
367: * select the page for incoming pair: if key is to go to the new page,
368: * write out the previous one, and copy the new one over, thus making
369: * it the current page. If not, simply write the new page, and we are
370: * still looking at the page of interest. current page is not updated
371: * here, as sdbm_store will do so, after it inserts the incoming pair.
372: */
373: if (hash & (db->hmask + 1)) {
374: if ((status = write_page(db, db->pagbuf, db->pagbno))
375: != APR_SUCCESS)
376: return status;
377:
378: db->pagbno = newp;
379: (void) memcpy(pag, new, PBLKSIZ);
380: }
381: else {
382: if ((status = write_page(db, new, newp)) != APR_SUCCESS)
383: return status;
384: }
385:
386: if ((status = setdbit(db, db->curbit)) != APR_SUCCESS)
387: return status;
388: /*
389: * see if we have enough room now
390: */
391: if (fitpair(pag, need))
392: return APR_SUCCESS;
393: /*
394: * try again... update curbit and hmask as getpage would have
395: * done. because of our update of the current page, we do not
396: * need to read in anything. BUT we have to write the current
397: * [deferred] page out, as the window of failure is too great.
398: */
399: db->curbit = 2 * db->curbit
400: + ((hash & (db->hmask + 1)) ? 2 : 1);
401: db->hmask |= db->hmask + 1;
402:
403: if ((status = write_page(db, db->pagbuf, db->pagbno))
404: != APR_SUCCESS)
405: return status;
406:
407: } while (--smax);
408:
409: /*
410: * if we are here, this is real bad news. After SPLTMAX splits,
411: * we still cannot fit the key. say goodnight.
412: */
413: #if 0
414: (void) write(2, "sdbm: cannot insert after SPLTMAX attempts.\n", 44);
415: #endif
416: /* ### ENOSPC not really appropriate but better than nothing */
417: return APR_ENOSPC;
418:
419: }
420:
421: /* Reads 'len' bytes from file 'f' at offset 'off' into buf.
422: * 'off' is given relative to the start of the file.
423: * If EOF is returned while reading, this is taken as success.
424: */
425: static apr_status_t read_from(apr_file_t *f, void *buf,
426: apr_off_t off, apr_size_t len)
427: {
428: apr_status_t status;
429:
430: if ((status = apr_file_seek(f, APR_SET, &off)) != APR_SUCCESS ||
431: ((status = apr_file_read_full(f, buf, len, NULL)) != APR_SUCCESS)) {
432: /* if EOF is reached, pretend we read all zero's */
433: if (status == APR_EOF) {
434: memset(buf, 0, len);
435: status = APR_SUCCESS;
436: }
437: }
438:
439: return status;
440: }
441:
442: /*
443: * the following two routines will break if
444: * deletions aren't taken into account. (ndbm bug)
445: */
446: APU_DECLARE(apr_status_t) apr_sdbm_firstkey(apr_sdbm_t *db,
447: apr_sdbm_datum_t *key)
448: {
449: apr_status_t status;
450:
451: if ((status = apr_sdbm_lock(db, APR_FLOCK_SHARED)) != APR_SUCCESS)
452: return status;
453:
454: /*
455: * start at page 0
456: */
457: if ((status = read_from(db->pagf, db->pagbuf, OFF_PAG(0), PBLKSIZ))
458: == APR_SUCCESS) {
459: db->pagbno = 0;
460: db->blkptr = 0;
461: db->keyptr = 0;
462: status = getnext(key, db);
463: }
464:
465: (void) apr_sdbm_unlock(db);
466:
467: return status;
468: }
469:
470: APU_DECLARE(apr_status_t) apr_sdbm_nextkey(apr_sdbm_t *db,
471: apr_sdbm_datum_t *key)
472: {
473: apr_status_t status;
474:
475: if ((status = apr_sdbm_lock(db, APR_FLOCK_SHARED)) != APR_SUCCESS)
476: return status;
477:
478: status = getnext(key, db);
479:
480: (void) apr_sdbm_unlock(db);
481:
482: return status;
483: }
484:
485: /*
486: * all important binary tree traversal
487: */
488: static apr_status_t getpage(apr_sdbm_t *db, long hash)
489: {
490: register int hbit;
491: register long dbit;
492: register long pagb;
493: apr_status_t status;
494:
495: dbit = 0;
496: hbit = 0;
497: while (dbit < db->maxbno && getdbit(db, dbit))
498: dbit = 2 * dbit + ((hash & (1 << hbit++)) ? 2 : 1);
499:
500: debug(("dbit: %d...", dbit));
501:
502: db->curbit = dbit;
503: db->hmask = masks[hbit];
504:
505: pagb = hash & db->hmask;
506: /*
507: * see if the block we need is already in memory.
508: * note: this lookaside cache has about 10% hit rate.
509: */
510: if (pagb != db->pagbno) {
511: /*
512: * note: here, we assume a "hole" is read as 0s.
513: * if not, must zero pagbuf first.
514: * ### joe: this assumption was surely never correct? but
515: * ### we make it so in read_from anyway.
516: */
517: if ((status = read_from(db->pagf, db->pagbuf, OFF_PAG(pagb), PBLKSIZ))
518: != APR_SUCCESS)
519: return status;
520:
521: if (!chkpage(db->pagbuf))
522: return APR_ENOSPC; /* ### better error? */
523: db->pagbno = pagb;
524:
525: debug(("pag read: %d\n", pagb));
526: }
527: return APR_SUCCESS;
528: }
529:
530: static int getdbit(apr_sdbm_t *db, long dbit)
531: {
532: register long c;
533: register long dirb;
534:
535: c = dbit / BYTESIZ;
536: dirb = c / DBLKSIZ;
537:
538: if (dirb != db->dirbno) {
539: if (read_from(db->dirf, db->dirbuf, OFF_DIR(dirb), DBLKSIZ)
540: != APR_SUCCESS)
541: return 0;
542:
543: db->dirbno = dirb;
544:
545: debug(("dir read: %d\n", dirb));
546: }
547:
548: return db->dirbuf[c % DBLKSIZ] & (1 << dbit % BYTESIZ);
549: }
550:
551: static apr_status_t setdbit(apr_sdbm_t *db, long dbit)
552: {
553: register long c;
554: register long dirb;
555: apr_status_t status;
556: apr_off_t off;
557:
558: c = dbit / BYTESIZ;
559: dirb = c / DBLKSIZ;
560:
561: if (dirb != db->dirbno) {
562: if ((status = read_from(db->dirf, db->dirbuf, OFF_DIR(dirb), DBLKSIZ))
563: != APR_SUCCESS)
564: return status;
565:
566: db->dirbno = dirb;
567:
568: debug(("dir read: %d\n", dirb));
569: }
570:
571: db->dirbuf[c % DBLKSIZ] |= (1 << dbit % BYTESIZ);
572:
573: if (dbit >= db->maxbno)
574: db->maxbno += DBLKSIZ * BYTESIZ;
575:
576: off = OFF_DIR(dirb);
577: if ((status = apr_file_seek(db->dirf, APR_SET, &off)) == APR_SUCCESS)
578: status = apr_file_write_full(db->dirf, db->dirbuf, DBLKSIZ, NULL);
579:
580: return status;
581: }
582:
583: /*
584: * getnext - get the next key in the page, and if done with
585: * the page, try the next page in sequence
586: */
587: static apr_status_t getnext(apr_sdbm_datum_t *key, apr_sdbm_t *db)
588: {
589: apr_status_t status;
590: for (;;) {
591: db->keyptr++;
592: *key = getnkey(db->pagbuf, db->keyptr);
593: if (key->dptr != NULL)
594: return APR_SUCCESS;
595: /*
596: * we either run out, or there is nothing on this page..
597: * try the next one... If we lost our position on the
598: * file, we will have to seek.
599: */
600: db->keyptr = 0;
601: if (db->pagbno != db->blkptr++) {
602: apr_off_t off = OFF_PAG(db->blkptr);
603: if ((status = apr_file_seek(db->pagf, APR_SET, &off)
604: != APR_SUCCESS))
605: return status;
606: }
607:
608: db->pagbno = db->blkptr;
609: /* ### EOF acceptable here too? */
610: if ((status = apr_file_read_full(db->pagf, db->pagbuf, PBLKSIZ, NULL))
611: != APR_SUCCESS)
612: return status;
613: if (!chkpage(db->pagbuf))
614: return APR_EGENERAL; /* ### need better error */
615: }
616:
617: /* NOTREACHED */
618: }
619:
620:
621: APU_DECLARE(int) apr_sdbm_rdonly(apr_sdbm_t *db)
622: {
623: /* ### Should we return true if the first lock is a share lock,
624: * to reflect that apr_sdbm_store and apr_sdbm_delete will fail?
625: */
626: return (db->flags & SDBM_RDONLY) != 0;
627: }
628:
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