Annotation of parser3/src/lib/sdbm/sdbm.c, revision 1.8
1.8 ! moko 1: /* Copyright 2000-2005 The Apache Software Foundation or its licensors, as
! 2: * applicable.
1.1 paf 3: *
1.8 ! moko 4: * Licensed under the Apache License, Version 2.0 (the "License");
! 5: * you may not use this file except in compliance with the License.
! 6: * You may obtain a copy of the License at
1.1 paf 7: *
1.8 ! moko 8: * http://www.apache.org/licenses/LICENSE-2.0
1.1 paf 9: *
1.8 ! moko 10: * Unless required by applicable law or agreed to in writing, software
! 11: * distributed under the License is distributed on an "AS IS" BASIS,
! 12: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
! 13: * See the License for the specific language governing permissions and
! 14: * limitations under the License.
1.1 paf 15: */
16:
17: /*
18: * sdbm - ndbm work-alike hashed database library
19: * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
20: * author: oz@nexus.yorku.ca
21: * ex-public domain, ported to APR for Apache 2
22: * core routines
23: */
24:
1.5 moko 25: #include "pa_apr.h"
26: #include "pa_file_io.h"
27: #include "pa_strings.h"
28: #include "pa_errno.h"
29: #include "pa_sdbm.h"
1.1 paf 30:
31: #include "sdbm_tune.h"
32: #include "sdbm_pair.h"
33: #include "sdbm_private.h"
34:
35: /*
36: * forward
37: */
1.5 moko 38: static int getdbit (pa_sdbm_t *, long);
39: static pa_status_t setdbit(pa_sdbm_t *, long);
40: static pa_status_t getpage(pa_sdbm_t *db, long);
41: static pa_status_t getnext(pa_sdbm_datum_t *key, pa_sdbm_t *db);
42: static pa_status_t makroom(pa_sdbm_t *, long, int);
1.1 paf 43:
44: /*
45: * useful macros
46: */
47: #define bad(x) ((x).dptr == NULL || (x).dsize <= 0)
48: #define exhash(item) sdbm_hash((item).dptr, (item).dsize)
49:
50: /* ### Does anything need these externally? */
51: #define sdbm_dirfno(db) ((db)->dirf)
52: #define sdbm_pagfno(db) ((db)->pagf)
53:
1.5 moko 54: #define OFF_PAG(off) (pa_off_t) (off) * PBLKSIZ
55: #define OFF_DIR(off) (pa_off_t) (off) * DBLKSIZ
1.1 paf 56:
57: static long masks[] = {
58: 000000000000, 000000000001, 000000000003, 000000000007,
59: 000000000017, 000000000037, 000000000077, 000000000177,
60: 000000000377, 000000000777, 000000001777, 000000003777,
61: 000000007777, 000000017777, 000000037777, 000000077777,
62: 000000177777, 000000377777, 000000777777, 000001777777,
63: 000003777777, 000007777777, 000017777777, 000037777777,
64: 000077777777, 000177777777, 000377777777, 000777777777,
65: 001777777777, 003777777777, 007777777777, 017777777777
66: };
67:
1.5 moko 68: const pa_sdbm_datum_t sdbm_nullitem = { NULL, 0 };
1.1 paf 69:
1.5 moko 70: static pa_status_t database_cleanup(void *data)
1.1 paf 71: {
1.5 moko 72: pa_sdbm_t *db = data;
1.1 paf 73:
74: /*
1.5 moko 75: * Can't rely on pa_sdbm_unlock, since it will merely
1.1 paf 76: * decrement the refcnt if several locks are held.
77: */
78: if (db->flags & (SDBM_SHARED_LOCK | SDBM_EXCLUSIVE_LOCK))
1.5 moko 79: (void) pa_file_unlock(db->dirf);
80: (void) pa_file_close(db->dirf);
81: (void) pa_file_close(db->pagf);
1.4 misha 82: // free(db); // libcg will do it
1.1 paf 83:
1.5 moko 84: return PA_SUCCESS;
1.1 paf 85: }
86:
1.5 moko 87: static pa_status_t prep(pa_sdbm_t **pdb, const char *dirname, const char *pagname,
88: pa_int32_t flags, pa_fileperms_t perms, pa_pool_t *p)
1.1 paf 89: {
1.5 moko 90: pa_sdbm_t *db;
91: pa_status_t status;
1.1 paf 92:
93: *pdb = NULL;
94:
1.4 misha 95: // db = malloc(sizeof(*db));
96: // memset(db, 0, sizeof(*db));
1.6 moko 97: db = pa_sdbm_malloc(sizeof(*db));
1.1 paf 98:
99: db->pool = p;
100:
101: /*
102: * adjust user flags so that WRONLY becomes RDWR,
103: * as required by this package. Also set our internal
104: * flag for RDONLY if needed.
105: */
1.5 moko 106: if (!(flags & PA_WRITE)) {
1.1 paf 107: db->flags |= SDBM_RDONLY;
108: }
109:
110: /*
111: * adjust the file open flags so that we handle locking
112: * on our own (don't rely on any locking behavior within
1.5 moko 113: * an pa_file_t, in case it's ever introduced, and set
1.1 paf 114: * our own flag.
115: */
1.5 moko 116: if (flags & PA_SHARELOCK) {
1.1 paf 117: db->flags |= SDBM_SHARED;
1.5 moko 118: flags &= ~PA_SHARELOCK;
1.1 paf 119: }
120:
1.5 moko 121: flags |= PA_BINARY | PA_READ;
1.1 paf 122:
123: /*
124: * open the files in sequence, and stat the dirfile.
125: * If we fail anywhere, undo everything, return NULL.
126: */
127:
1.5 moko 128: if ((status = pa_file_open(&db->dirf, dirname, flags, perms, p))
129: != PA_SUCCESS)
1.1 paf 130: goto error;
131:
1.5 moko 132: if ((status = pa_file_open(&db->pagf, pagname, flags, perms, p))
133: != PA_SUCCESS)
1.1 paf 134: goto error;
135:
1.5 moko 136: if ((status = pa_sdbm_lock(db, (db->flags & SDBM_RDONLY)
137: ? PA_FLOCK_SHARED
138: : PA_FLOCK_EXCLUSIVE))
139: != PA_SUCCESS)
1.1 paf 140: goto error;
141:
1.5 moko 142: /* pa_pcalloc zeroed the buffers
143: * pa_sdbm_lock stated the dirf->size and invalidated the cache
1.1 paf 144: */
145:
146: /*
147: * if we are opened in SHARED mode, unlock ourself
148: */
149: if (db->flags & SDBM_SHARED)
1.5 moko 150: if ((status = pa_sdbm_unlock(db)) != PA_SUCCESS)
1.1 paf 151: goto error;
152:
153: /* make sure that we close the database at some point */
1.5 moko 154: //pa_pool_cleanup_register(p, db, database_cleanup, pa_pool_cleanup_null);
1.1 paf 155:
156: /* Done! */
157: *pdb = db;
1.5 moko 158: return PA_SUCCESS;
1.1 paf 159:
160: error:
161: if (db->dirf && db->pagf)
1.5 moko 162: (void) pa_sdbm_unlock(db);
1.1 paf 163: if (db->dirf != NULL)
1.5 moko 164: (void) pa_file_close(db->dirf);
1.1 paf 165: if (db->pagf != NULL) {
1.5 moko 166: (void) pa_file_close(db->pagf);
1.1 paf 167: }
1.4 misha 168: // free(db); // libcg will do it
1.1 paf 169: return status;
170: }
171:
1.5 moko 172: pa_status_t pa_sdbm_open(pa_sdbm_t **db, const char *file,
173: pa_int32_t flags,
174: pa_fileperms_t perms, pa_pool_t *p)
1.1 paf 175: {
1.5 moko 176: char *dirname = pa_pstrcat(p, file, PA_SDBM_DIRFEXT, NULL);
177: char *pagname = pa_pstrcat(p, file, PA_SDBM_PAGFEXT, NULL);
1.1 paf 178:
179: return prep(db, dirname, pagname, flags, perms, p);
180: }
181:
1.5 moko 182: pa_status_t pa_sdbm_close(pa_sdbm_t *db)
1.1 paf 183: {
1.5 moko 184: database_cleanup(db); return PA_SUCCESS;
185: //return pa_pool_cleanup_run(db->pool, db, database_cleanup);
1.1 paf 186: }
187:
1.5 moko 188: pa_status_t pa_sdbm_fetch(pa_sdbm_t *db, pa_sdbm_datum_t *val,
189: pa_sdbm_datum_t key)
1.1 paf 190: {
1.5 moko 191: pa_status_t status;
1.1 paf 192:
193: if (db == NULL || bad(key))
1.5 moko 194: return PA_EINVAL;
1.1 paf 195:
1.5 moko 196: if ((status = pa_sdbm_lock(db, PA_FLOCK_SHARED)) != PA_SUCCESS)
1.1 paf 197: return status;
198:
1.5 moko 199: if ((status = getpage(db, exhash(key))) == PA_SUCCESS) {
1.1 paf 200: *val = getpair(db->pagbuf, key);
201: /* ### do we want a not-found result? */
202: }
203:
1.5 moko 204: (void) pa_sdbm_unlock(db);
1.1 paf 205:
206: return status;
207: }
208:
1.5 moko 209: static pa_status_t write_page(pa_sdbm_t *db, const char *buf, long pagno)
1.1 paf 210: {
1.5 moko 211: pa_status_t status;
212: pa_off_t off = OFF_PAG(pagno);
1.1 paf 213:
1.5 moko 214: if ((status = pa_file_seek(db->pagf, PA_SET, &off)) == PA_SUCCESS)
215: status = pa_file_write_full(db->pagf, buf, PBLKSIZ, NULL);
1.1 paf 216:
217: return status;
218: }
219:
1.5 moko 220: pa_status_t pa_sdbm_delete(pa_sdbm_t *db,
221: const pa_sdbm_datum_t key)
1.1 paf 222: {
1.5 moko 223: pa_status_t status;
1.1 paf 224:
225: if (db == NULL || bad(key))
1.5 moko 226: return PA_EINVAL;
227: if (pa_sdbm_rdonly(db))
228: return PA_EINVAL;
1.1 paf 229:
1.5 moko 230: if ((status = pa_sdbm_lock(db, PA_FLOCK_EXCLUSIVE)) != PA_SUCCESS)
1.1 paf 231: return status;
232:
1.5 moko 233: if ((status = getpage(db, exhash(key))) == PA_SUCCESS) {
1.1 paf 234: if (!delpair(db->pagbuf, key))
235: /* ### should we define some APRUTIL codes? */
1.5 moko 236: status = PA_SUCCESS; /* PAF: were PA_EGENERAL, contradicting comment in .h file :( */
1.1 paf 237: else
238: status = write_page(db, db->pagbuf, db->pagbno);
239: }
240:
1.5 moko 241: (void) pa_sdbm_unlock(db);
1.1 paf 242:
243: return status;
244: }
245:
1.5 moko 246: pa_status_t pa_sdbm_store(pa_sdbm_t *db, pa_sdbm_datum_t key,
247: pa_sdbm_datum_t val, int flags)
1.1 paf 248: {
249: int need;
250: register long hash;
1.5 moko 251: pa_status_t status;
1.1 paf 252:
253: if (db == NULL || bad(key))
1.5 moko 254: return PA_EINVAL;
255: if (pa_sdbm_rdonly(db))
256: return PA_EINVAL;
1.1 paf 257: need = key.dsize + val.dsize;
258: /*
259: * is the pair too big (or too small) for this database ??
260: */
261: if (need < 0 || need > PAIRMAX)
1.5 moko 262: return PA_EINVAL;
1.1 paf 263:
1.5 moko 264: if ((status = pa_sdbm_lock(db, PA_FLOCK_EXCLUSIVE)) != PA_SUCCESS)
1.1 paf 265: return status;
266:
1.5 moko 267: if ((status = getpage(db, (hash = exhash(key)))) == PA_SUCCESS) {
1.1 paf 268:
269: /*
270: * if we need to replace, delete the key/data pair
271: * first. If it is not there, ignore.
272: */
1.5 moko 273: if (flags == PA_SDBM_REPLACE)
1.1 paf 274: (void) delpair(db->pagbuf, key);
1.5 moko 275: else if (!(flags & PA_SDBM_INSERTDUP) && duppair(db->pagbuf, key)) {
276: status = PA_EEXIST;
1.1 paf 277: goto error;
278: }
279: /*
280: * if we do not have enough room, we have to split.
281: */
282: if (!fitpair(db->pagbuf, need))
1.5 moko 283: if ((status = makroom(db, hash, need)) != PA_SUCCESS)
1.1 paf 284: goto error;
285: /*
286: * we have enough room or split is successful. insert the key,
287: * and update the page file.
288: */
289: (void) putpair(db->pagbuf, key, val);
290:
291: status = write_page(db, db->pagbuf, db->pagbno);
292: }
293:
294: error:
1.5 moko 295: (void) pa_sdbm_unlock(db);
1.1 paf 296:
297: return status;
298: }
299:
300: /*
301: * makroom - make room by splitting the overfull page
302: * this routine will attempt to make room for SPLTMAX times before
303: * giving up.
304: */
1.5 moko 305: static pa_status_t makroom(pa_sdbm_t *db, long hash, int need)
1.1 paf 306: {
307: long newp;
308: char twin[PBLKSIZ];
309: char *pag = db->pagbuf;
310: char *new = twin;
311: register int smax = SPLTMAX;
1.5 moko 312: pa_status_t status;
1.1 paf 313:
314: do {
315: /*
316: * split the current page
317: */
318: (void) splpage(pag, new, db->hmask + 1);
319: /*
320: * address of the new page
321: */
322: newp = (hash & db->hmask) | (db->hmask + 1);
323:
324: /*
325: * write delay, read avoidence/cache shuffle:
326: * select the page for incoming pair: if key is to go to the new page,
327: * write out the previous one, and copy the new one over, thus making
328: * it the current page. If not, simply write the new page, and we are
329: * still looking at the page of interest. current page is not updated
330: * here, as sdbm_store will do so, after it inserts the incoming pair.
331: */
332: if (hash & (db->hmask + 1)) {
333: if ((status = write_page(db, db->pagbuf, db->pagbno))
1.5 moko 334: != PA_SUCCESS)
1.1 paf 335: return status;
336:
337: db->pagbno = newp;
338: (void) memcpy(pag, new, PBLKSIZ);
339: }
340: else {
1.5 moko 341: if ((status = write_page(db, new, newp)) != PA_SUCCESS)
1.1 paf 342: return status;
343: }
344:
1.5 moko 345: if ((status = setdbit(db, db->curbit)) != PA_SUCCESS)
1.1 paf 346: return status;
347: /*
348: * see if we have enough room now
349: */
350: if (fitpair(pag, need))
1.5 moko 351: return PA_SUCCESS;
1.1 paf 352: /*
353: * try again... update curbit and hmask as getpage would have
354: * done. because of our update of the current page, we do not
355: * need to read in anything. BUT we have to write the current
356: * [deferred] page out, as the window of failure is too great.
357: */
358: db->curbit = 2 * db->curbit
359: + ((hash & (db->hmask + 1)) ? 2 : 1);
360: db->hmask |= db->hmask + 1;
361:
362: if ((status = write_page(db, db->pagbuf, db->pagbno))
1.5 moko 363: != PA_SUCCESS)
1.1 paf 364: return status;
365:
366: } while (--smax);
367:
368: /*
369: * if we are here, this is real bad news. After SPLTMAX splits,
370: * we still cannot fit the key. say goodnight.
371: */
372: #if 0
373: (void) write(2, "sdbm: cannot insert after SPLTMAX attempts.\n", 44);
374: #endif
375: /* ### ENOSPC not really appropriate but better than nothing */
1.5 moko 376: return PA_ENOSPC;
1.1 paf 377:
378: }
379:
380: /* Reads 'len' bytes from file 'f' at offset 'off' into buf.
381: * 'off' is given relative to the start of the file.
382: * If EOF is returned while reading, this is taken as success.
383: */
1.5 moko 384: static pa_status_t read_from(pa_file_t *f, void *buf,
385: pa_off_t off, pa_size_t len)
1.1 paf 386: {
1.5 moko 387: pa_status_t status;
1.1 paf 388:
1.5 moko 389: if ((status = pa_file_seek(f, PA_SET, &off)) != PA_SUCCESS ||
390: ((status = pa_file_read_full(f, buf, len, NULL)) != PA_SUCCESS)) {
1.1 paf 391: /* if EOF is reached, pretend we read all zero's */
1.5 moko 392: if (status == PA_EOF) {
1.1 paf 393: memset(buf, 0, len);
1.5 moko 394: status = PA_SUCCESS;
1.1 paf 395: }
396: }
397:
398: return status;
399: }
400:
401: /*
402: * the following two routines will break if
403: * deletions aren't taken into account. (ndbm bug)
404: */
1.5 moko 405: pa_status_t pa_sdbm_firstkey(pa_sdbm_t *db,
406: pa_sdbm_datum_t *key)
1.1 paf 407: {
1.5 moko 408: pa_status_t status;
1.1 paf 409:
1.5 moko 410: if ((status = pa_sdbm_lock(db, PA_FLOCK_SHARED)) != PA_SUCCESS)
1.1 paf 411: return status;
412:
413: /*
414: * start at page 0
415: */
416: if ((status = read_from(db->pagf, db->pagbuf, OFF_PAG(0), PBLKSIZ))
1.5 moko 417: == PA_SUCCESS) {
1.1 paf 418: db->pagbno = 0;
419: db->blkptr = 0;
420: db->keyptr = 0;
421: status = getnext(key, db);
422: }
423:
1.5 moko 424: (void) pa_sdbm_unlock(db);
1.1 paf 425:
426: return status;
427: }
428:
1.5 moko 429: pa_status_t pa_sdbm_nextkey(pa_sdbm_t *db,
430: pa_sdbm_datum_t *key)
1.1 paf 431: {
1.5 moko 432: pa_status_t status;
1.1 paf 433:
1.5 moko 434: if ((status = pa_sdbm_lock(db, PA_FLOCK_SHARED)) != PA_SUCCESS)
1.1 paf 435: return status;
436:
437: status = getnext(key, db);
438:
1.5 moko 439: (void) pa_sdbm_unlock(db);
1.1 paf 440:
441: return status;
442: }
443:
444: /*
445: * all important binary tree traversal
446: */
1.5 moko 447: static pa_status_t getpage(pa_sdbm_t *db, long hash)
1.1 paf 448: {
449: register int hbit;
450: register long dbit;
451: register long pagb;
1.5 moko 452: pa_status_t status;
1.1 paf 453:
454: dbit = 0;
455: hbit = 0;
456: while (dbit < db->maxbno && getdbit(db, dbit))
457: dbit = 2 * dbit + ((hash & (1 << hbit++)) ? 2 : 1);
458:
459: debug(("dbit: %d...", dbit));
460:
461: db->curbit = dbit;
462: db->hmask = masks[hbit];
463:
464: pagb = hash & db->hmask;
465: /*
466: * see if the block we need is already in memory.
467: * note: this lookaside cache has about 10% hit rate.
468: */
469: if (pagb != db->pagbno) {
470: /*
471: * note: here, we assume a "hole" is read as 0s.
472: * if not, must zero pagbuf first.
473: * ### joe: this assumption was surely never correct? but
474: * ### we make it so in read_from anyway.
475: */
476: if ((status = read_from(db->pagf, db->pagbuf, OFF_PAG(pagb), PBLKSIZ))
1.5 moko 477: != PA_SUCCESS)
1.1 paf 478: return status;
479:
480: if (!chkpage(db->pagbuf))
1.5 moko 481: return PA_ENOSPC; /* ### better error? */
1.1 paf 482: db->pagbno = pagb;
483:
484: debug(("pag read: %d\n", pagb));
485: }
1.5 moko 486: return PA_SUCCESS;
1.1 paf 487: }
488:
1.5 moko 489: static int getdbit(pa_sdbm_t *db, long dbit)
1.1 paf 490: {
491: register long c;
492: register long dirb;
493:
494: c = dbit / BYTESIZ;
495: dirb = c / DBLKSIZ;
496:
497: if (dirb != db->dirbno) {
498: if (read_from(db->dirf, db->dirbuf, OFF_DIR(dirb), DBLKSIZ)
1.5 moko 499: != PA_SUCCESS)
1.1 paf 500: return 0;
501:
502: db->dirbno = dirb;
503:
504: debug(("dir read: %d\n", dirb));
505: }
506:
507: return db->dirbuf[c % DBLKSIZ] & (1 << dbit % BYTESIZ);
508: }
509:
1.5 moko 510: static pa_status_t setdbit(pa_sdbm_t *db, long dbit)
1.1 paf 511: {
512: register long c;
513: register long dirb;
1.5 moko 514: pa_status_t status;
515: pa_off_t off;
1.1 paf 516:
517: c = dbit / BYTESIZ;
518: dirb = c / DBLKSIZ;
519:
520: if (dirb != db->dirbno) {
521: if ((status = read_from(db->dirf, db->dirbuf, OFF_DIR(dirb), DBLKSIZ))
1.5 moko 522: != PA_SUCCESS)
1.1 paf 523: return status;
524:
525: db->dirbno = dirb;
526:
527: debug(("dir read: %d\n", dirb));
528: }
529:
530: db->dirbuf[c % DBLKSIZ] |= (1 << dbit % BYTESIZ);
531:
532: if (dbit >= db->maxbno)
533: db->maxbno += DBLKSIZ * BYTESIZ;
534:
535: off = OFF_DIR(dirb);
1.5 moko 536: if ((status = pa_file_seek(db->dirf, PA_SET, &off)) == PA_SUCCESS)
537: status = pa_file_write_full(db->dirf, db->dirbuf, DBLKSIZ, NULL);
1.1 paf 538:
539: return status;
540: }
541:
542: /*
543: * getnext - get the next key in the page, and if done with
544: * the page, try the next page in sequence
545: */
1.5 moko 546: static pa_status_t getnext(pa_sdbm_datum_t *key, pa_sdbm_t *db)
1.1 paf 547: {
1.5 moko 548: pa_status_t status;
1.1 paf 549: for (;;) {
550: db->keyptr++;
551: *key = getnkey(db->pagbuf, db->keyptr);
552: if (key->dptr != NULL)
1.5 moko 553: return PA_SUCCESS;
1.1 paf 554: /*
555: * we either run out, or there is nothing on this page..
556: * try the next one... If we lost our position on the
557: * file, we will have to seek.
558: */
559: db->keyptr = 0;
560: if (db->pagbno != db->blkptr++) {
1.5 moko 561: pa_off_t off = OFF_PAG(db->blkptr);
562: if ((status = pa_file_seek(db->pagf, PA_SET, &off)
563: != PA_SUCCESS))
1.1 paf 564: return status;
565: }
566:
567: db->pagbno = db->blkptr;
568: /* ### EOF acceptable here too? */
1.5 moko 569: if ((status = pa_file_read_full(db->pagf, db->pagbuf, PBLKSIZ, NULL))
570: != PA_SUCCESS)
1.1 paf 571: return status;
572: if (!chkpage(db->pagbuf))
1.5 moko 573: return PA_EGENERAL; /* ### need better error */
1.1 paf 574: }
575:
576: /* NOTREACHED */
577: }
578:
579:
1.5 moko 580: int pa_sdbm_rdonly(pa_sdbm_t *db)
1.1 paf 581: {
582: /* ### Should we return true if the first lock is a share lock,
1.5 moko 583: * to reflect that pa_sdbm_store and pa_sdbm_delete will fail?
1.1 paf 584: */
585: return (db->flags & SDBM_RDONLY) != 0;
586: }
587:
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