libmdbm/ 775 0 0 0 7765605211 5426 5libmdbm/plan9.h 664 0 0 364 7746126663 6615 /* plan 9 headers & defines */ #include #include #include typedef vlong off_t; #define lseek seek #define O_RDWR ORDWR #define O_RDONLY OREAD #define O_WRONLY OWRITE #define O_CREAT 128 /* fake, for openfile() */ _hvաzohvܢozHohvo` ǜC__'`#`tv___vvCu c_s_rB FG_Jvjv_fм\libmdbm/mdbm.3x 664 0 0 17032 7765605647 6661 .TH MDBM 3X .SH NAME mdbm: mdbmopen, mdbmfetch, mdbmstore, mdbmdelete, mdbmfirstkey, ... \- multiple-key, extensible-hashing data base subroutines .SH SYNOPSIS .nf .ft L #include typedef struct { char *dptr; int dsize; } datum; /* in */ typedef struct { unsigned short pagblksz, dirblksz; } Dbmparams; /* " */ .sp 0.3v Dbm *mdbmopen(char *file, int omode, int perm, Dbmparams *dpp) .sp 0.3v datum mdbmfetch(Dbm *d, datum key) .sp 0.3v mdbmstore(Dbm *d, datum key, datum content, int replace) .sp 0.3v mdbmdelete(Dbm *d, datum key) .sp 0.3v datum mdbmfirstkey(Dbm *d) .sp 0.3v datum mdbmnextkey(Dbm *d, datum key) .sp 0.3v mdbmsync(Dbm *d) .sp 0.3v mdbmclose(Dbm *d) .sp 0.3v mdbmgetflags(Dbm *d, int flags) .sp 0.3v mdbmsetflags(Dbm *d, int flags) .sp 0.3v mdbmbisflags(Dbm *d, int flags) .sp 0.3v mdbmbicflags(Dbm *d, int flags) .SH DESCRIPTION These functions maintain key/content pairs in a database. The functions will handle very large (a billion blocks) databases and will usually access a keyed item in one or two file system accesses. This implementation uses extensible hashing. The functions are obtained with the loader option .BR \-lmdbm . .PP .IR Key s and .IR content s are described by the .I datum typedef, which is defined in the include file .IR mdbm.h . A .I datum specifies a string of .I dsize bytes pointed to by .I dptr. Arbitrary binary data, as well as normal text strings, are allowed. The database is stored in two files. One file is a directory containing a bit map and has ``.dir'' as its suffix. The second file contains all data (pages) and has ``.pag'' as its suffix. .PP Before a database can be accessed, it must be opened by .IR mdbmopen . The .I flags are simply passed to the open system call (see .IR open (2)). (This is not strictly true: if the read/write mode is O_WRONLY, it is converted internally to O_RDWR.) .PP The .I mode parameter is only used with .B O_CREAT when creating a new database. The value is merely passed to the .I open system call. If .B O_CREAT is not specified, the ``.dir'' and ``.pag'' files must exist. .I mdbmopen returns a pointer to the database for use by the other mdbm routines. If the database cannot be opened, .I mdbmopen returns NULL. .PP If .I dpp is non-null, it points to desired .I pag and .I dir block sizes of the database. On return, these variables will have been filled in with the actual sizes in use. (The values are only used when creating a database, but are always modified on return.) If the default sizes are acceptable, .I dpp may be 0. .PP Once open, the data stored under a key is accessed by .I mdbmfetch and data is placed under a key by .IR mdbmstore . A key (and its associated contents) is deleted by .IR mdbmdelete . A linear pass through all keys in a database may be made, in an (apparently) random order, by use of .I mdbmfirstkey and .IR mdbmnextkey . .I Mdbm_firstkey will return the first key in the database. With any key .I mdbmnextkey will return the next key in the database. This code will traverse the database d: .IP .RS .ft L for (key = mdbmfirstkey(d); key.dptr != NULL; key = mdbmnextkey(d, key)) .ft .RE .PP .I mdbmsync will complete any pending writes on the database. (If the .B Mdbmimmwr flag has been set \- see .I mdbmsetflags below \- then no writes will be pending). In any case .I mdbmsync calls .I fsync on the .I dir and .I pag file descriptors. .PP A database may be closed (and the associated storage and file descriptors released) with .IR mdbmclose . .PP Writable databases .I must be closed before exiting to ensure that all data are written. (To be precise, this is only necessary if the .B Mdbmimmwr flag was not on, and no .I mdbmsync has been done since the last .IR mdbmstore ). .PP The fourth parameter to store (``replace'') specifies what to do in the event of a key collision. The value .B Mdbmnorepl (0) makes .I mdbmstore return the error value 1 in the event that the given key already points to a particular datum. The value .B Mdbmokrepl (actually your favorite nonzero value will do) tells store to go ahead and replace the old datum. .PP Various flags may be examined and set via .I mdbmgetflags and .IR mdbmsetflags . Currently they are: .TP .B Mdbmreadonly Indicates that a database was opened with O_RDONLY and cannot be written. .I (Store and friends return an error indication and set .B errno (see .IR intro(2) ) to .B EPERM if they are asked to operate on a read-only database.) .TP .B Mdbmimmwr Specifies that all modifications to the database be written to the file system immediately (note that .IR fsync s are .I not done in this case). This might be useful for an interactive program, to reduce the chances of loss of data in the event of a system crash. This is currently the only user-settable flag. .PP .I Mdbmsetflags sets the user-settable flags to its second argument. .I Mdbmgetflags returns all the flags in the database. .I Mdbm_bisflags turns on the indicated user-settable flags, and .I mdbmbicflags turns off the indicated user-settable flags. E.g., the C statement .IP .B mdbmbisflags(d, Mdbmimmwr); .PP would turn on the immediate-write flag. .SS "Multiple Keys" The database routines invisibly keep track of how many keys are pointing to a particular datum, and ensure that the datum itself is not removed until it is no longer in use. In fact, a datum may also be used as a key. Thus there is no storage penalty for having many keys that point to one datum or even to themselves. .PP The implementation of this involved changing the underlying structure of the database. Keys and data are no longer stored in pairs; instead, each data block contains an arbitrary number of items each with incoming and outgoing link indicies. In addition to breaking anything that depended on the old implementation, this means that in most cases two file system accesses are required to fetch a particular datum given a key (one to find the key and another to find its datum). .SH DIAGNOSTICS All functions that return an .I int indicate errors with negative values. A zero return indicates OK. Routines that return a .I datum indicate errors with a NULL (0) .IR dptr . .I mdbmopen returns NULL on error. .SH "SEE ALSO" .IR dbm (3) .SH HISTORY Ken Thompson wrote the original .I dbm code that appeared in Research UNIX, Seventh Edition. Chris Torek modified it to handle multiple databases, changed the internal format to support multiple keys, and added anything that you see here and not in .IR dbm (3). Geoff Collyer adapted .I mdbm to Plan 9 and arranged that binary integers are stored in big-endian byte order on disk, thus making the database files portable across architectures. .SH BUGS The ``.dat'' file will contain holes so that its apparent size is (usually) two to four times its actual content. Older UNIX systems may create real file blocks for these holes when touched. These files cannot be copied by normal means (cp, cat, tp, tar, ar) without filling in the holes. .PP .I Dptr pointers returned by these subroutines point into static storage that is changed by subsequent calls. .PP The previously undocumented .I forder function is defunct. (It used to return the block number given a key.) .PP The size of a key or content string must not exceed the .I pag block size set when creating the database. Moreover, all strings that hash together must fit on a single block. .I Mdbm_store will return an error in the event that a block fills with inseparable data. .PP .I Mdbm_delete does not physically reclaim file space, although it does make it available for reuse. .PP The order of keys presented by .I mdbmfirstkey and .I mdbmnextkey depends on a hashing function, not on anything interesting. a key.) .PP The size of a key or content string must not exceed the .I pag block size set when creating the database. Moreover, all strings that hash together must fit on a single block. .I Mdbm_store will return an error in the event that a block fills with inseparable data. .PP .I Mdbm_delete does not physically reclaim file space, although it does make it available for reuse. .PP The order of keys presented by .I mdbmfirstkey and .I mdbmnextkey depends on a hashing function, notlibmdbm/dumpdbm.obsolete.c 664 0 0 3021 7745606042 11032 #include #include #include #include #include #include #include #include "mdbm.h" #include "mdbm_local.h" void abort(void) { kill(getpid(), SIGILL); } main(int argc, char **argv) { int i, j, len, dsize, msize, blocks; Mdbm *mp; Pagblk *db; Pagent *de; struct stat sb; if (argc < 2) { fprintf(stderr, "Usage: dumpdbm dbname\n"); exit(1); } if (argc > 2) signal(SIGILL, SIG_IGN); dsize = msize = 0; mp = mdbm_open(argv[1], O_RDONLY, 0, &dsize, &msize); if (!mp) { perror(argv[1]); exit(1); } printf("dbm %s: dsize = %d, msize = %d\n", argv[1], dsize, msize); (void) fstat(mp->pag.fd, &sb); blocks = sb.st_size/dsize; printf("(%d data blocks)\n", blocks); db = (Pagblk *) mp->pag.buf; for (i = 0; i < blocks; i++) { dread(mp, i); /* internal routine! */ printf("block %d: %d entries\n", i, db->nent); for (j = 0, de = db->ents; j < db->nent; j++, de++) { printf("\t%2d: @%4d links=%2d inx=%4d outx=%4d outh=%08x ", j, de->txtoff, de->nlinks, de->inx, de->outx, de->outh); len = (j? de[-1].txtoff: dsize) - de->txtoff; pr_entry(mp->pag.buf+de->txtoff, len); } } (void) mdbm_close(mp); exit(0); } pr_entry(char *s, int len) { int c; putchar('"'); while (--len >= 0) { c = (unsigned char)*s++; if (c&0200) putchar('M'), putchar('-'), c &= 0177; if (c == 0177) putchar('^'), putchar('?'); else if (c < ' ') putchar('^'), putchar(c+'@'); else putchar(c); } putchar('"'); putchar('\n'); } , de->txtoff, de->nlinks, de->inx, de->outx, de->outh); len = (j? de[-1].txtoff: dsize) - de->txtoff; pr_entry(mp->pag.buf+de->txtoff, len); } } (void) mdbm_close(mp); exit(0); } pr_entry(char *s, int len) { int c; putchar('"'); while (--len >= 0) { c = (unsigned char)*s++; if (c&0200) putchar('M'), putchar('-'), c &= 0177; if (c == 0177) putchar('^'), putchar('?'); else if (c < ' ') putchar('^'), putchar(c+'@'); else putchar(c); } putchar('"'); libmdbm/plan9.c 664 0 0 1067 7746130776 6631 /* plan 9 primitives */ static char lasterr[ERRMAX]; static off_t size(int fd) { Dir *stp = dirfstat(fd); off_t size = -1; if (stp != nil) { size = stp->length; free(stp); } return size; } static void seterr(char *err) { werrstr("%s", err); } static void saverr(void) { rerrstr(lasterr, sizeof lasterr); } static void resterr(void) { seterr(lasterr); } static int openfile(char *name, int omode, int perm) { int rwmode = omode & 3; int fd = open(name, rwmode); if (fd < 0 && rwmode != O_RDONLY) fd = create(name, rwmode, perm); return fd; } static off_t size(int fd) { Dir *stp = dirfstat(fd); off_t size = -1; if (stp != nil) { size = stp->length; free(stp); } return size; } static void seterr(char *err) { werrstr("%s", err); } static void saverr(void) { rerrstr(lasterr, sizeof lasterr); } static void resterr(void) { seterr(lasterr); } static int openfile(char *name, int omode, int perm) { int rwmode = omode & 3; int fd = open(name, rwmode); if (fd < 0 && rwmode != O_RDlibmdbm/unix.h 664 0 0 374 7750156737 6556 /* unix headers & defines */ #include #include #include #include #include #include #include #include typedef unsigned char uchar; typedef unsigned short ushort; ); } static void saverr(void) { rerrstr(lasterr, sizeof lasterr); } static void resterr(void) { seterr(lasterr); } static int openfile(char *name, int omode, int perm) { int rwmode = omode & 3; int fd = open(name, rwmode); if (fd < 0 && rwmode != O_RDlibmdbm/unix.c 664 0 0 1471 7746067577 6600 /* unix headers & defines */ static int lasterr; static off_t size(int fd) { struct stat stat; if (fstat(fd, &stat) < 0) return -1; return stat.st_size; } static void seterr(char *err) { if (strcmp(err, "no mem") == 0) errno = ENOMEM; else if (strcmp(err, "invalid argument") == 0) errno = EINVAL; else if (strcmp(err, "permission denied") == 0) errno = EPERM; else if (strcmp(err, "out of space") == 0) errno = ENOSPC; else if (strcmp(err, "not found") == 0) errno = ENOENT; else errno = EINVAL; } static void saverr(void) { lasterr = errno; } static void resterr(void) { errno = lasterr; } static int openfile(char *name, int omode, int perm) { int fd = open(name, omode, perm); if (fd < 0 && (omode&3) != O_RDONLY) { close(creat(name, perm)); fd = open(name, omode); } return fd; } else if (strcmp(err, "permission denied") == 0) errno = EPERM; else if (strcmp(err, "out of space") == 0) errno = ENOSPC; else if (strcmp(err, "not found") == 0) errno = ENOENT; else errnolibmdbm/os.h 664 0 0 364 7746131002 6172 /* plan 9 headers & defines */ #include #include #include typedef vlong off_t; #define lseek seek #define O_RDWR ORDWR #define O_RDONLY OREAD #define O_WRONLY OWRITE #define O_CREAT 128 /* fake, for openfile() */ close(creat(name, perm)); fd = open(name, omode); } return fd; } else if (strcmp(err, "permission denied") == 0) errno = EPERM; else if (strcmp(err, "out of space") == 0) errno = ENOSPC; else if (strcmp(err, "not found") == 0) errno = ENOENT; else errnolibmdbm/os.c 664 0 0 1067 7746131014 6211 /* plan 9 primitives */ static char lasterr[ERRMAX]; static off_t size(int fd) { Dir *stp = dirfstat(fd); off_t size = -1; if (stp != nil) { size = stp->length; free(stp); } return size; } static void seterr(char *err) { werrstr("%s", err); } static void saverr(void) { rerrstr(lasterr, sizeof lasterr); } static void resterr(void) { seterr(lasterr); } static int openfile(char *name, int omode, int perm) { int rwmode = omode & 3; int fd = open(name, rwmode); if (fd < 0 && rwmode != O_RDONLY) fd = create(name, rwmode, perm); return fd; } static off_t size(int fd) { Dir *stp = dirfstat(fd); off_t size = -1; if (stp != nil) { size = stp->length; free(stp); } return size; } static void seterr(char *err) { werrstr("%s", err); } static void saverr(void) { rerrstr(lasterr, sizeof lasterr); } static void resterr(void) { seterr(lasterr); } static int openfile(char *name, int omode, int perm) { int rwmode = omode & 3; int fd = open(name, rwmode); if (fd < 0 && rwmode != O_RDlibmdbm/mkfile 664 0 0 460 7765604626 6611 #include "mdbm.h" #define exit(n) exits((n) == 0? NULL: "error") /* $Header: testdbm.c,v 1.3 84/09/10 01:57:33 geoff Exp $ */ enum { NAV = 10, }; static Dbm *mp; static int prompt = 1; static struct stringarg { int s_len; char *s_str; } av[NAV]; void c_open(int), c_close(int), c_fetch(int), c_insert(int), c_replace(int); void c_delete(int), c_list(int), c_quit(int), c_sync(int); static struct cmd { char *c_name; void (*c_func)(int); short c_args; } cmds[] = { "open", c_open, 2, "open", c_open, 4, "open", c_open, 5, "close", c_close, 1, "fetch", c_fetch, 2, "store", c_insert, 3, "replace", c_replace, 3, "delete", c_delete, 2, "list", c_list, 1, "quit", c_quit, 1, "sync", c_sync, 1, 0, 0, 0 }; #define checkdb() \ if (!mp) { \ fprintf(stderr, "no database active\n"); \ return; \ } static int parse(char *s) { int aleft, c, qu; char *cp; struct stringarg *ap; static char xbuf[BUFSIZ]; for (ap = av, aleft = NAV; --aleft >= 0; ap++) if (ap->s_str) { free(ap->s_str); ap->s_str = NULL; } aleft = NAV; for (ap = av; *s; ap++) { while (isspace(*s)) s++; if (!*s) break; qu = 0; cp = xbuf; while ((c = *s++) != 0 && (qu || !isspace(c))) if (qu == '\\') { switch (c) { case 'n': c = '\n'; break; case 'r': c = '\r'; break; case 't': c = '\t'; break; case 'b': c = '\b'; break; case 'f': c = '\f'; break; case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': c -= '0'; if (*s >= '0' && *s <= '7') { c = (c<<3) + *s++ -'0'; if (*s >= '0' && *s <= '7') c = (c<<3) + *s++ -'0'; } break; } *cp++ = c; qu = 0; } else if (c == qu) qu = 0; else if (qu == 0 && (c == '\'' || c == '"' || c == '\\')) qu = c; else *cp++ = c; --s; *cp++ = 0; if (--aleft < 0) { fprintf(stderr, "too many args's\n"); return 0; } ap->s_str = malloc(cp - xbuf); if (ap->s_str == NULL) { perror("malloc"); exit(1); } ap->s_len = cp - xbuf; memmove(ap->s_str, xbuf, ap->s_len); ap->s_len--; /* stop counting trailing \0 */ } return NAV - aleft; } static int doit(char *s) { int argc = parse(s); struct cmd *cp; if (argc < 1) return 0; if (av[0].s_len < 1) return 1; for (cp = cmds; cp->c_name; cp++) if (cp->c_args != argc) continue; else if (strncmp(cp->c_name, av[0].s_str, av[0].s_len) == 0) { (*cp->c_func)(argc); return 0; } return 1; } void c_quit(int) { if (mp) (void) mdbmclose(mp); exit(0); } void main(int argc, char **argv) { int errflg = 0; char cmdbuf[BUFSIZ]; ARGBEGIN { case 'p': prompt = 0; break; default: errflg++; break; } ARGEND if (errflg) { fprintf(stderr, "usage: %s [-p]\m", argv0); exit(0); } setbuf(stderr, NULL); setbuf(stdout, NULL); for (; ; ) { if (prompt) printf("> "); if (fgets(cmdbuf, sizeof cmdbuf, stdin) == NULL) break; if (doit(cmdbuf)) printf( "cmds: open close fetch store replace delete list sync quit\n"); } putchar('\n'); c_quit(0); } void c_open(int argc) { Dbmparams dp; memset(&dp, 0, sizeof dp); c_close(0); if (argc >= 4) { dp.pagblksz = atoi(av[2].s_str); dp.dirblksz = atoi(av[3].s_str); } mp = mdbmopen(av[1].s_str, O_RDWR|O_CREAT, 0666, &dp); if (mp == NULL) { perror(av[1].s_str); return; } printf("opened %s - pagblksz %d, dirblksz %d\n", av[1].s_str, dp.pagblksz, dp.dirblksz); } void c_close(int) { if (mp) (void) mdbmclose(mp); mp = NULL; } /* bug: won't cope with NULs in the datum */ void prdatum(datum d) { printf("%.*s", d.dsize, d.dptr); } static void getkey(datum *key) { key->dptr = av[1].s_str; key->dsize = av[1].s_len; } static void getkeydat(datum *key, datum *dat) { getkey(key); dat->dptr = av[2].s_str; dat->dsize = av[2].s_len; } void c_fetch(int) { datum key, dat; checkdb(); getkey(&key); dat = mdbmfetch(mp, key); if (dat.dptr == nil) fprintf(stderr, "%s: not found\n", key.dptr); else { prdatum(key); printf(": "); prdatum(dat); putchar('\n'); } } void c_insert(int) { int e; datum key, dat; checkdb(); getkeydat(&key, &dat); e = mdbmstore(mp, key, dat, Mdbmnorepl); if (e < 0) fprintf(stderr, "%s: store failed\n", key.dptr); else if (e > 0) fprintf(stderr, "%s: insert failed, key in use\n", key.dptr); } void c_replace(int) { datum key, dat; checkdb(); getkeydat(&key, &dat); if (mdbmstore(mp, key, dat, Mdbmokrepl)) fprintf(stderr, "%s: replace failed\n", key.dptr); } void c_delete(int) { datum key; checkdb(); getkey(&key); if (mdbmdelete(mp, key)) fprintf(stderr, "%s: delete failed\n", key.dptr); } void c_list(int) { datum key, dat; checkdb(); for (key = mdbmfirstkey(mp); key.dptr; key = mdbmnextkey(mp, key)) { dat = mdbmfetch(mp, key); if (dat.dptr == nil) fprintf(stderr, "%.*s: key not found\n", key.dsize, key.dptr); else { prdatum(key); printf(": "); prdatum(dat); putchar('\n'); } } } int mdbmsync(Dbm *d); void c_sync(int) { checkdb(); mdbmsync(mp); } ey; checkdb(); getkey(&key); if (mdbmdelete(mp, key)) fprintf(stderr, "%s: delete failed\n", key.dptr); } void c_list(int) { datum key, dat; checkdb(); for (key = mdbmfirstkey(mp); key.dptr; key = mdbmnextkey(mp, key)) { dat = mdbmfetch(mp, key); if (dat.dptr == nil) fprintf(stderr, "%.*s: key not found\n", key.dsize, key.dptr); else { prdatum(key); printf(": "); prdlibmdbm/makefile 664 0 0 716 7765605313 7115 # Makefile for libmdbm - multiple file dbm(3) CFLAGS= -O OBJS= mdbm.o HDRS= mdbm.h mdbm_local.h all: libmdbm.a dbm libmdbm.a: $(OBJS) ar cr $@ $(OBJS) ranlib $@ install: install -c libmdbm.a $(DESTDIR)/usr/lib ranlib $(DESTDIR)/usr/lib/libmdbm.a install -c mdbm.h $(DESTDIR)/usr/include install -c mdbm.3x $(DESTDIR)/usr/man/man3 dbm: dbm.o libmdbm.a $(CC) $(CFLAGS) -o $@ dbm.o libmdbm.a clean: rm -f libmdbm.a *.o a.out dbm core $(OBJS): $(HDRS) else { prdatum(key); printf(": "); prdlibmdbm/mdbm.c 664 0 0 63207 7750166761 6547 /* multi-key extensible hashing */ #include "os.h" #include "mdbm.h" #include "os.c" #define MAGIC "#mdbm\n" #define pagent(pb, n) ((Pagent *)((pb)->pagents + Pagsiz*(n))) enum { Magic = 'd'<<8 | 'b', BYTESIZ = 8, /* bits per byte */ MAXUSHORT = (ushort)~0, Pagsiz = 4*2 + 4, /* bytes per Pagent, excluding alignment padding */ /* Def database block sizes for new databases */ DefPagesiz = 1024, DefDirsiz = 4096, /* Minimum sizes; smaller requests will be brought up to these values */ MinPagesiz = 128, MinDirsiz = MinPagesiz, Fdirty = 1, /* fflag: buffer data is newer than file's */ Userflags = Mdbmimmwr, /* user allowed to modify only these flags */ }; /* an open mdbm file */ typedef struct { int fd; /* data area (page) file descriptor */ int size; /* data buffer size */ char *buf; /* current data block */ char *sec; /* secondary data block (if any) */ long block; /* index of current data block */ off_t dataoff; /* base offset of data after header */ char fflags; } Mdbmfile; /* an open database (two files) */ struct Dbm { ushort magic; char flags; /* flags (see below) */ long maxbit; /* (max possible set bit in dir map) + 1 */ Mdbmfile dir; /* bit-mapped directory */ Mdbmfile pag; /* data pages */ }; typedef struct { off_t block; short byteoff; /* bytes into current block */ char bitoff; /* # of bits to shift left */ } Bitoffs; /* * Header of the bit-mapped directory file; contains per-database info. * Is stored big-endian on disk. * Followed by bits set whenever a data block was split. */ typedef union { struct { char magic[8]; char pagblksz[2]; char dirblksz[2]; }; char pad[DefDirsiz]; } Dirhdr; /* * The pages (data) file contains the following in each block: # of * entries in block, those entries, free space, and text. * * A (Pagent) entry contains off, links, inx, outx, outh. * * off is the offset within the block of the text (and thus also specifies * the size of the text string); links is the number of links to this item; * inx is the ``in index'' number of this item; outx is the ``out index'' * number of this item; and outh is the out hash. * * If an item is in use as a key, its outx will be non-zero and repeated * in the inx field of its datum. outh will (by the usual extensible hashing * rules) determine a block number, and the item with the matching inx field * in that block is the datum under the key in question. * * An item's inx field will always be non-zero and unique to the block in * which the item resides. */ typedef struct { char txtoff[2]; /* offset to beginning of text */ char nlinks[2]; /* number of links */ char inx[2]; /* in index */ char outx[2]; /* out index */ char outh[4]; /* out hash */ } Pagent; typedef struct { char nent[2]; /* number of entries */ char pagents[1]; /* Pagent ents[1]; /* actually ents[nent] but can't say that */ } Pagblk; /* big-endian get and put for shorts & longs */ static ushort begets(void *p) { uchar *up = (uchar *)p; return up[0]<> BYTESIZ; *p++ = s; return p; } static unsigned long begetl(void *p) { uchar *up = (uchar *)p; return up[0]<<(3*BYTESIZ) | up[1]<<(2*BYTESIZ) | up[2]<> (3*BYTESIZ); *p++ = l >> (2*BYTESIZ); *p++ = l >> BYTESIZ; *p++ = l; return p; } static int notdbm(Dbm *d) { return d == nil || d->magic != Magic; } void mdbmbisflags(Dbm *m, int f) { m->flags |= f & Userflags; } void mdbmbicflags(Dbm *m, int f) { m->flags &= ~(f & Userflags); } int mdbmgetflags(Dbm *m) { return m->flags; } void mdbmsetflags(Dbm *m, int f) { mdbmbicflags(m, Userflags); mdbmbisflags(m, f); } static void badblk(char *buf, int size) { fprintf(stderr, "mdbm: bad block\n"); abort(); memset(buf, 0, size); } /* * Perform some sanity checks on a data (page) block */ static void chkblk(char *buf, int size) { int i, t = size, nent, toff; Pagblk *pb = (Pagblk *)buf; Pagent *pe; nent = begets(pb->nent); pe = pagent(pb, 0); for (i = 0; i < nent; i++) { pe = pagent(pb, i); toff = begets(pe->txtoff); if (toff > t) { badblk(buf, size); return; } t = toff; } if (&buf[t] < (char *)pe) badblk(buf, size); } /* Read block blk (size sz offset off) from file f into buffer buf */ static int rdblk(int f, off_t blk, char *buf, int sz, off_t off) { lseek(f, blk*sz + off, 0); if (blk < 0) fprintf(stderr, "mdbm: negative block # (%lld) in rdblk\n", blk); return read(f, buf, sz); } /* Write block blk (size sz offset off) to file f from buffer buf */ static int wrblk(int f, off_t blk, char *buf, int sz, off_t off) { lseek(f, blk*sz + off, 0); if (blk < 0) fprintf(stderr, "mdbm: negative block # (%lld) in wrblk\n", blk); return write(f, buf, sz); } /* Write (if needed) */ static int anysync(Mdbmfile *f) { if (f->fflags & Fdirty) if (wrblk(f->fd, f->block, f->buf, f->size, f->dataoff) != f->size) { fprintf(stderr, "mdbm: write error\n"); return -1; } else f->fflags &= ~Fdirty; return 0; } static int syncall(Dbm *d) { if ((anysync(&d->dir) < 0) | (anysync(&d->pag) < 0)) return -1; return 0; } /* Do autowrites */ static int autowrite(Dbm *d) { if (d->flags & Mdbmimmwr) return syncall(d); return 0; } static int readblock(Mdbmfile *mf, off_t b) { int bytes; anysync(mf); memset(mf->buf, 0, mf->size); mf->block = b; /* short reads are okay */ bytes = rdblk(mf->fd, b, mf->buf, mf->size, mf->dataoff); if (bytes < 0) fprintf(stderr, "mdbm: read error\n"); return bytes; } static int pagread(Dbm *d, off_t b) /* Read pag block b */ { int bytes = 0; if (d->pag.block != b) { bytes = readblock(&d->pag, b); chkblk(d->pag.buf, d->pag.size); } return bytes; } static int dirfread(Dbm *d, off_t b) /* Read dir block b */ { int bytes = 0; if (d->dir.block != b) bytes = readblock(&d->dir, b); return bytes; } static int ckhdr(Dirhdr *hp) { if (strcmp(hp->magic, MAGIC) != 0) { fprintf(stderr, "mdbm: bad magic\n"); return -1; } if (begets(hp->pagblksz) <= 0) { fprintf(stderr, "mdbm: bad pagblksz\n"); return -1; } if (begets(hp->dirblksz) <= 0) { fprintf(stderr, "mdbm: bad dirblksz\n"); return -1; } return 0; } static int inbounds(int val, int def, int low, int high) { if (val == 0) val = def; if (val < low) return low; if (val > high) return high; return val; } /* work out how big the buffers should be, if this is a new pb */ static void sizebufs(Dirhdr *hp, Dbmparams *dpp) { beputs(hp->pagblksz, inbounds(dpp->pagblksz, DefPagesiz, MinPagesiz, MAXUSHORT)); beputs(hp->dirblksz, inbounds(dpp->dirblksz, DefDirsiz, MinDirsiz, MAXUSHORT)); } static int popfile(Mdbmfile *mf, char *base, char *ext, int omode, int perm) { char *name = malloc(strlen(base) + strlen(ext) + 1); if (name == NULL) return mf->fd = -1; strcpy(name, base); strcat(name, ext); mf->dataoff = 0; mf->block = -1; mf->fd = openfile(name, omode, perm); free(name); return mf->fd; } /* internal version of mdbmopen */ static int opendb(Dbm *d, char *file, int omode, int perm, Dbmparams *dpp) { off_t fsize; Dirhdr hdr; Dbmparams dp; memset(d, 0, sizeof *d); d->dir.fd = d->pag.fd = -1; /* fix up the open mode, then open them files */ if ((omode&3) == O_WRONLY) omode = (omode & ~3) | O_RDWR; d->flags = (omode&3) == O_RDONLY? Mdbmreadonly: 0; if (popfile(&d->pag, file, ".pag", omode, perm) < 0 || popfile(&d->dir, file, ".dir", omode, perm) < 0) return -1; d->dir.dataoff = sizeof hdr; if (dpp == NULL) { dp.pagblksz = DefPagesiz; dp.dirblksz = DefDirsiz; dpp = &dp; } fsize = size(d->dir.fd); if (fsize <= 0) { /* empty dir file: populate header */ memset(&hdr, 0, sizeof hdr); strncpy(hdr.magic, MAGIC, sizeof hdr.magic); sizebufs(&hdr, dpp); if (!(d->flags&Mdbmreadonly) && write(d->dir.fd, (char *)&hdr, sizeof hdr) != sizeof hdr) return -1; lseek(d->dir.fd, 0, 0); /* back over header */ fsize = size(d->dir.fd); /* file has grown */ } d->maxbit = (fsize - sizeof hdr)*BYTESIZ; /* existing dir file: read header & validate */ if (read(d->dir.fd, (char *)&hdr, sizeof hdr) != sizeof hdr || ckhdr(&hdr) < 0) { seterr("invalid argument"); return -1; } /* allocate block buffers */ d->dir.size = dpp->dirblksz = begets(hdr.dirblksz); d->pag.size = dpp->pagblksz = begets(hdr.pagblksz); if ((d->pag.buf = malloc(d->pag.size)) == NULL || (d->pag.sec = malloc(d->pag.size)) == NULL || (d->dir.buf = malloc(d->dir.size)) == NULL) return -1; return 0; } /* close all file descriptors and free all memory associated with d */ int mdbmclose(Dbm *d) { int rv; if (notdbm(d)) return -1; rv = syncall(d); d->magic = 0; if (d->pag.fd >= 0 && close(d->pag.fd) < 0) rv = -1; if (d->dir.fd >= 0 && close(d->dir.fd) < 0) rv = -1; free(d->pag.buf); free(d->pag.sec); free(d->dir.buf); free(d); return rv; } /* Open or create a database */ Dbm * mdbmopen(char *file, int omode, int perm, Dbmparams *dpp) { Dbm *d = (Dbm *)malloc(sizeof *d); if (d == NULL) return NULL; if (opendb(d, file, omode, perm, dpp) < 0) { saverr(); mdbmclose(d); resterr(); return NULL; } d->magic = Magic; return d; } static Bitoffs getbitoffs(Dbm *d, unsigned long bitno) { off_t bn; Bitoffs bo; if (bitno >= d->maxbit) { memset(&bo, 0, sizeof bo); return bo; } bo.bitoff = bitno % BYTESIZ; bn = bitno / BYTESIZ; /* byte index */ bo.byteoff = bn % d->dir.size; bo.block = bn / d->dir.size; return bo; } /* returns -1 on I/O error, else the bit requested */ static int getbit(Dbm *d, unsigned long bitno) { if (bitno < d->maxbit) { Bitoffs bo = getbitoffs(d, bitno); if (dirfread(d, bo.block) < 0) return -1; return (d->dir.buf[bo.byteoff] >> bo.bitoff) & 1; } return 0; } /* * Mark the block as having been split by setting the appropriate bit * in the dir map. * * returns -1 on I/O error. */ static int setbit(Dbm *d, unsigned long bitno) { Bitoffs bo; if (bitno >= d->maxbit) { d->maxbit = bitno + 1; if (getbit(d, bitno) < 0) return -1; } bo = getbitoffs(d, bitno); d->dir.buf[bo.byteoff] |= 1 << bo.bitoff; d->dir.fflags |= Fdirty; return 0; } /* * Read in the appropriate data block for an item whose hash index is hash. * The hash index specifies the data block in an indirect way: * if the bit in the dir map is set, then more bits of the hash value should * be considered. If it is not set then we have the right hash bits * and the block number is just the low bits of the hash value. * * Return the hash mask that gets the right block number. */ static int mdbmaccess(Dbm *d, long hash) { int bit; long hmask; for (hmask = 0; ; hmask = (hmask<<1) + 1) { bit = getbit(d, (hash & hmask) + hmask); if (bit < 0) return -1; if (!bit) break; } if (pagread(d, hash & hmask) < 0) return -1; return hmask; } /* * Return the next hash number for this dbm, or 0 for no more */ static long mdbmhashinc(long hash, long hmask) { long bit; hash &= hmask; bit = hmask + 1; for (; ; ) { bit >>= 1; if (bit == 0) return 0; if ((hash&bit) == 0) return hash|bit; hash &= ~bit; } return 0; } static datum nildatum; /* * Return the first datum in dbm d with hash value hash */ static datum mdbmfirsthash(Dbm *d, long hash) { int bl = 0, i, il, found, nent, toff; long hmask; char *bp = NULL, *ip; datum rval; Pagent *pe; Pagblk *pb = (Pagblk *)d->pag.buf; for (; ; ) { /* * Suck in the block for the given hash, * then find the "first" key. */ hmask = mdbmaccess(d, hash); if (hmask == -1) return nildatum; found = 0; nent = begets(pb->nent); for (i = 0; i < nent; i++) { pe = pagent(pb, i); if (begets(pe->outx) == 0) /* not a key */ continue; toff = begets(pe->txtoff); il = (i? begets(pagent(pb, i-1)->txtoff): d->pag.size) - toff; ip = d->pag.buf + toff; if (!found || il < bl || (il == bl && memcmp(ip, bp, il) < 0)) { bl = il; bp = ip; found++; } } if (found) { memmove(rval.dptr = d->pag.sec, bp, rval.dsize = bl); return rval; } /* No item with this hash, so get next hash and try again */ hash = mdbmhashinc(hash, hmask); if (hash == 0) /* no more */ return nildatum; } } /* * Return the "first" key in dbm d */ datum mdbmfirstkey(Dbm *d) { if (notdbm(d)) return nildatum; return mdbmfirsthash(d, 0); } static int hitab[16] = { /* ken's 055,043,036,054,063,014,004,005, 010,064,077,000,035,027,025,071, */ 61, 57, 53, 49, 45, 41, 37, 33, 29, 25, 21, 17, 13, 9, 5, 1, }; static long hltab[64] = { 06100151277L,06106161736L,06452611562L,05001724107L, 02614772546L,04120731531L,04665262210L,07347467531L, 06735253126L,06042345173L,03072226605L,01464164730L, 03247435524L,07652510057L,01546775256L,05714532133L, 06173260402L,07517101630L,02431460343L,01743245566L, 00261675137L,02433103631L,03421772437L,04447707466L, 04435620103L,03757017115L,03641531772L,06767633246L, 02673230344L,00260612216L,04133454451L,00615531516L, 06137717526L,02574116560L,02304023373L,07061702261L, 05153031405L,05322056705L,07401116734L,06552375715L, 06165233473L,05311063631L,01212221723L,01052267235L, 06000615237L,01075222665L,06330216006L,04402355630L, 01451177262L,02000133436L,06025467062L,07121076461L, 03123433522L,01010635225L,01716177066L,05161746527L, 01736635071L,06243505026L,03637211610L,01756474365L, 04723077174L,03642763134L,05750130273L,03655541561L, }; /* * Calculate the hash val for the given item. */ static long mdbmcalchash(char *s, int len) { int j, hashi = 0; long hashl = 0; while (--len >= 0) { int f = *s++; for (j = 0; j < BYTESIZ; j += 4) { hashi += hitab[f&017]; hashl += hltab[hashi&077]; f >>= 4; } } return hashl; } /* * Return the "next" key in dbm d */ datum mdbmnextkey(Dbm *d, datum key) { int bl = 0, i, il, found, nent, toff; long hash, hmask; char *bp = NULL, *ip; Pagent *pe; Pagblk *pb; datum rval; if (notdbm(d)) return nildatum; pb = (Pagblk *)d->pag.buf; /* * Suck in the block for the given hash, * then find the key that follows the one given. */ hash = mdbmcalchash(key.dptr, key.dsize); hmask = mdbmaccess(d, hash); if (hmask == -1) return nildatum; found = 0; nent = begets(pb->nent); for (i = 0; i < nent; i++) { pe = pagent(pb, i); if (begets(pe->outx) == 0) /* not a key */ continue; toff = begets(pe->txtoff); il = (i? begets(pagent(pb, i-1)->txtoff): d->pag.size) - toff; ip = d->pag.buf + toff; if (il < key.dsize || (il == key.dsize && memcmp(ip, key.dptr, il) <= 0)) continue; if (!found || il < bl || (il == bl && memcmp(ip, bp, il) < 0)) { bl = il; bp = ip; found++; } } if (found) { memmove(rval.dptr = d->pag.sec, bp, rval.dsize = bl); return rval; } /* No item with this hash, so get next hash and return its first item */ hash = mdbmhashinc(hash, hmask); if (hash == 0) /* no more */ return nildatum; return mdbmfirsthash(d, hash); } /* * Search for the given key, and if found, return a pointer to the * datum under the key. If ablock and aindex are nonzero, fill in * the block and index numbers of the key. If justkey is true, * forget about the datum and stop when the key is found. * * (Workhorse for fetch, also used by delete & store.) */ static Pagent * mdbmsearch(Dbm *d, char *s, int len, long *ablock, int *aindex, int justkey) { int i, nent, toff; ushort outx; long outh; Pagent *pe; Pagblk *pb = (Pagblk *)d->pag.buf; if (mdbmaccess(d, mdbmcalchash(s, len)) == -1) return NULL; nent = begets(pb->nent); pe = pagent(pb, 0); for (i = 0; i < nent; i++) { pe = pagent(pb, i); if (begets(pe->outx) == 0) /* not a key */ continue; toff = begets(pe->txtoff); if ((i? begets(pagent(pb, i-1)->txtoff): d->pag.size) - toff == len && memcmp(s, d->pag.buf + toff, len) == 0) break; } if (i >= nent) return NULL; if (ablock) *ablock = d->pag.block; if (aindex) *aindex = i; if (justkey) return pe; outx = begets(pe->outx); outh = begetl(pe->outh); if (mdbmaccess(d, outh) == -1) return NULL; for (i = 0; i < nent; i++) { pe = pagent(pb, i); if (begets(pe->inx) == outx) return pe; } fprintf(stderr, "mdbm bug: no datum for key (%d, %d)\n", outh, outx); return NULL; } /* * Find datum in dbm d, given key */ datum mdbmfetch(Dbm *d, datum key) { int toff; Pagent *pe; Pagblk *pb; datum item; if (notdbm(d)) return nildatum; pb = (Pagblk *)d->pag.buf; memset(&item, 0, sizeof item); item.dptr = NULL; /* paranoia */ pe = mdbmsearch(d, key.dptr, key.dsize, (long *)0, (int *)0, 0); if (pe) { toff = begets(pe->txtoff); item.dptr = d->pag.buf + toff; item.dsize = (pe > (Pagent *)pb->pagents? begets(((Pagent *)((char *)pe - Pagsiz))->txtoff): d->pag.size) - toff; } return item; } /* * Exhaustively search for a valid inx index number for the new entry * in d. We "guarantee" that one such will be available. (Used by * dostore) */ static ushort mdbminx(Dbm *d) { Pagblk *pb = (Pagblk *)d->pag.buf; int i, n = begets(pb->nent) - 1, ent; ushort inx; for (inx = 1; ; inx++) { for (i = n, ent = 0; --i >= 0; ent++) if (begets(pagent(pb, ent)->inx) == inx) break; if (i < 0) return inx; if (inx == MAXUSHORT) break; } fprintf(stderr, "mdbm bug: no inx's available (can't happen)\n"); abort(); return 1; } /* * Add an item to a data block, returning a pointer to the dentry * descriptor (or 0 if it doesn't fit). The caller will fill in all * fields except the offset, and will fill in the text of the item. */ static Pagent * additem(char *buf, int dsize, int len) { Pagblk *pb = (Pagblk *)buf; int i = begets(pb->nent); Pagent *pe; /* * Figure out where the text should go. If there are no * entries in this block, it will go at the end of the block; * otherwise, it will go right before the last entry. * It must not cross over the entry descriptor area, * which will be one larger than it is now. */ pe = pagent(pb, i); i = (i? begets(pagent(pb, i-1)->txtoff): dsize) - len; if (buf+i < (char *)pe + Pagsiz) return 0; beputs(pb->nent, begets(pb->nent) + 1); beputs(pe->txtoff, i); return pe; } /* * Delete item 'n' from current data buffer of dbm d */ static int mdbmdelitem(Dbm *d, int n) { int i, nlinks, nent, toff, prevtoff = 0, nenttoff; Pagent *pe, *e; Pagblk *pb = (Pagblk *)d->pag.buf; nent = begets(pb->nent); if (n < 0 || n >= nent) { fprintf(stderr, "mdbm bug: bad delitem\n"); abort(); return -1; } pe = pagent(pb, n); nlinks = begets(pe->nlinks); if (nlinks > 1) { beputs(pe->nlinks, --nlinks); d->pag.fflags |= Fdirty; return 0; } beputs(pb->nent, --nent); toff = begets(pe->txtoff); if (n) prevtoff = begets(pagent(pb, n-1)->txtoff); i = (n? prevtoff: d->pag.size) - toff; if (i) { /* delete i bytes of text */ nenttoff = begets(pagent(pb, nent)->txtoff); if (n < nent) { char *to = d->pag.buf +(n? prevtoff: d->pag.size); int bytes = toff - nenttoff; if (bytes > 0) memmove(to, to - i, bytes); } nenttoff = begets(pagent(pb, nent)->txtoff); memset(d->pag.buf + nenttoff, 0, i); } for (e = pagent(pb, nent); pe < e; n++) { pe = pagent(pb, n); memmove(pe, pagent(pb, n+1), sizeof *pe); beputs(pe->txtoff, begets(pe->txtoff) + i); } memset(e, 0, sizeof *pe); return 0; } /* * Actually store the text of an item in a dblock. Fill in the supplied * pointer (if any) with the hash number of the item. Also, if a split * occurs, check *asplit, and if the block numbers match, set *asplit, * otherwise clear it. (Used by mdbmstore) */ static Pagent * dostore(Dbm *d, char *s, int len, long *ahash, long *asplit) { int i, l, rlen, nent, toff, inx; unsigned minx = MAXUSHORT, maxx = 0; long hash, hmask, IfSplit = 0; char *p; Pagent *pe; Pagblk *pb = (Pagblk *)d->pag.buf; hash = mdbmcalchash(s, len); if (ahash) *ahash = hash; if (asplit) { IfSplit = *asplit; *asplit = 0; } while ((hmask = mdbmaccess(d, hash)) != -1) { rlen = len; nent = begets(pb->nent); for (i = 0; i < nent; i++) { pe = pagent(pb, i); toff = begets(pe->txtoff); if ((i? begets(pagent(pb, i-1)->txtoff): d->pag.size) - toff == rlen && memcmp(s, d->pag.buf + toff, rlen) == 0) { beputs(pe->nlinks, begets(pe->nlinks) + 1); d->pag.fflags |= Fdirty; return pe; } inx = begets(pe->inx); if (inx < minx) minx = inx; if (inx > maxx) maxx = inx; } pe = additem(d->pag.buf, d->pag.size, rlen); if (pe) { beputs(pe->nlinks, 1); /* will be either key or datum */ beputs(pe->outx, 0); /* not a key (at least, not yet) */ /* * inx will be one less than min inx (if possible), * or one more than max inx (if possible), that occur * in the block. If none of those yield results, * we perform an exhaustive search. Hopefully the * searches are rare. */ if (i == 0) inx = 1; /* 1st one, special case */ else if (minx < MAXUSHORT && minx > 1) inx = minx-1; else if (maxx && maxx < MAXUSHORT) inx = maxx+1; else inx = mdbminx(d); beputs(pe->inx, inx); memmove(d->pag.buf + begets(pe->txtoff), s, len); d->pag.fflags |= Fdirty; return pe; } /* * Didn't fit; split the block to make room. * Presumably about half of the existing entries * will move to the new block. */ if (len + sizeof *pb > d->pag.size) return NULL; /* hopeless! */ /* * If we are splitting the "interesting" block, * make a note of that. */ if (asplit && IfSplit == d->pag.block) *asplit = 1; memset(d->pag.sec, 0, d->pag.size); hmask++; nent = begets(pb->nent); for (i = 0; i < nent; ) { pe = pagent(pb, i); toff = begets(pe->txtoff); l = (i? begets(pagent(pb, i-1)->txtoff): d->pag.size) - toff; p = d->pag.buf + toff; if (mdbmcalchash(p, l) & hmask) { Pagent *npe=additem(d->pag.sec, d->pag.size, l); memmove(d->pag.sec + begets(npe->txtoff), p, l); /* no need to byte-swap when just copying */ memmove(npe->nlinks, pe->nlinks, sizeof pe->nlinks); memmove(npe->inx, pe->inx, sizeof pe->inx); memmove(npe->outx, pe->outx, sizeof pe->outx); memmove(npe->outh, pe->outh, sizeof pe->outh); /* force mdbmdelitem to remove it */ beputs(pe->nlinks, 1); mdbmdelitem(d, pe - (Pagent *)pb->pagents); } else i++; } wrblk(d->pag.fd, d->pag.block+hmask, d->pag.sec, d->pag.size, 0); d->pag.fflags |= Fdirty; hmask--; /* * Now mark the block as having been split by setting the * appropriate bit in the dir map. */ if (setbit(d, (hash & hmask) + hmask) < 0) return NULL; } return NULL; } static int notwritable(Dbm *d) { if (d->flags&Mdbmreadonly) { seterr("permission denied"); return 1; } return 0; } static int delkey(Dbm *d, long keyblock, int keyindex) { Pagblk *pb; if (notdbm(d) || pagread(d, keyblock) < 0) return -1; pb = (Pagblk *)d->pag.buf; beputs(pagent(pb, keyindex)->outx, 0); /* not a key anymore */ mdbmdelitem(d, keyindex); autowrite(d); return 0; } /* * Store dat as datum of key key in dbm d. * replace: true → overwrite if exists. */ int mdbmstore(Dbm *d, datum key, datum dat, int replace) { int keyindex; ushort outx = 0; long didsplit, keyblock, outh; Pagent *pe; Pagblk *pb; if (notdbm(d) || notwritable(d)) return -1; pb = (Pagblk *)d->pag.buf; /* * Search for the key's datum. If it is found, then delete the datum * (unless we are told not to) and store a new one, then modify the * key's description parameters to point to the new datum. * If it is not found, then presumably there is no such key, * so make a new one, then proceed as before. */ pe = mdbmsearch(d, key.dptr, key.dsize, &keyblock, &keyindex, 0); if (pe) { if (!replace) return 1; mdbmdelitem(d, pe - (Pagent *)pb->pagents); /* now committed; if new datum doesn't fit, old pairing is gone! */ } else { /* create new key */ pe = dostore(d, key.dptr, key.dsize, (long *)0, (long *)0); if (pe == 0) { autowrite(d); seterr("out of space"); /* presumably */ return -1; } beputs(pe->outx, 1); /* force it to look like a key */ keyblock = d->pag.block; keyindex = pe - (Pagent *)pb->pagents; } didsplit = keyblock; pe = dostore(d, dat.dptr, dat.dsize, &outh, &didsplit); if (pe) outx = begets(pe->inx); /* if the data store split the key's block, must find the key again */ if (didsplit) if (mdbmsearch(d, key.dptr, key.dsize, &keyblock, &keyindex, 1) == 0) { fprintf(stderr, "mdbm bug: post-split keysearch failed!\n"); abort(); } if (!pe) { /* oops, go delete the key */ if (delkey(d, keyblock, keyindex) < 0) return -1; seterr("out of space"); return -1; } /* * Replace the outx and outh numbers in the old (or new) key * so that it points to the new datum. */ if (pagread(d, keyblock) < 0) return -1; pe = pagent(pb, keyindex); beputl(pe->outh, outh); beputs(pe->outx, outx); d->pag.fflags |= Fdirty; autowrite(d); return 0; } /* * Sync the file attached to dbm d */ int mdbmsync(Dbm *d) { int rv; if (notdbm(d)) return -1; rv = syncall(d); #ifdef unix (void) fsync(d->pag.fd); (void) fsync(d->dir.fd); #endif return rv; } /* * Delete datum under key in dbm d */ int mdbmdelete(Dbm *d, datum key) { int keyindex, datindex; long keyblock; Pagent *pe; Pagblk *pb; if (notdbm(d)) return -1; pe = mdbmsearch(d, key.dptr, key.dsize, &keyblock, &keyindex, 0); if (pe == 0) { seterr("not found"); return -1; } if (notwritable(d)) return -1; /* * Delete the datum. This might change the position of the key, so * check, and if so, fix up keyindex ahead of time. */ pb = (Pagblk *)d->pag.buf; datindex = pe - (Pagent *)pb->pagents; if (d->pag.block == keyblock && datindex < keyindex && begets(pe->nlinks) == 1) keyindex--; mdbmdelitem(d, datindex); /* delete the key */ if (delkey(d, keyindex, keyblock) < 0) return -1; return 0; } x, 0); if (pe == 0) { seterr("not found"); return -1; } if (notwritable(d)) return -1; /* * Delete the datum. This might change the position of the key, so * check, and if so, fix up keyindex ahead of time. */ pb = (Pagblk *)d->pag.buf; datindex = pe - (Pagent *)pb->pagents; if (d->pag.block == keyblock && datindex < keyindex && begets(pe->nlinks) =ent)->inx) == inx) break; if (i < 0) return inx; if (inx == MAXUSHORT) break; } fprintf(stderr, "mdbm bug: no inx's available (can't happen)\n"); abort(); return 1; } /* * Add an item to a data block, returning a pointer to the dentry * descriptor (or 0 if it doesn't fit). The caller will fill in all * fields except the offset, and will fill in the text of the item. */ static Pagent * additem(char *buf, int dsize, int len) { Pagblk *pb = (Pagblk *)buf; int i = begets(pb->nent); Pagent *pe; /* * Figure out where the text should go. If there are no * entries in this block, it will go at the end of the block; * otherwise, it will go right before the last entry. * It must not cross over the entry descriptor area, * which will be one larger than it is now. */ pe = pagent(pb, i); i = (i? begets(pagent(pb, i-1)->txtoff): dsize) - len; if (buf+i < (char *)pe + Pagsiz) return 0; beputs(pb->nent, begets(pb->nent) + 1); beputs(pe->txtoff, i); return pe; } /* * Delete item 'n' from current data buffer of dbm d */ static int mdbmdelitem(Dbm *d, int n) { int i, nlinks, nent, toff, prevtoff = 0, nenttoff; Pagent *pe, *e; Pagblk *pb = (Pagblk *)d->pag.buf; nent = begets(pb->nent); if (n < 0 || n >= nent) { fprintf(stderr, "mdbm bug: bad delitem\n"); abort(); return -1; } pe = pagent(pb, n); nlinks = begets(pe->nlinks); if (nlinks > 1) { beputs(pe->nlinks, --nlinks); d->pag.fflags |= Fdirty; return 0; } beputs(pb->nent, --nent); toff = begets(pe->txtoff); if (n) prevtoff = begets(pagent(pb, n-1)->txtoff); i = (n? prevtoff: d->pag.size) - toff; if (i) { /* delete i bytes of text */ nenttoff = begets(pagent(pb, nent)->txtoff); if (n < nent) { char *to = d->pag.buf +(n? prevtoff: d->pag.size); int bytes = toff - nenttoff; if (bytes > 0) memmove(to, to - i, bytes); } nenttoff = begets(pagent(pb, nent)->txtoff); memset(d->pag.buf + nenttoff, 0, i); } for (e = pagent(pb, nent); pe < e; n++) { pe = pagent(pb, n); memmove(pe, pagent(pb, n+1), sizeof *pe); beputs(pe->txtoff, begets(pe->txtoff) + i); } memset(e, 0, sizeof *pe); return 0; } /* * Actually store the text of an item in a dblock. Fill in the supplied * pointer (if any) with the hash number of the item. Also, if a split * occurs, check *asplit, and if the block numbers match, set *asplit, * otherwise clear it. (Used by mdbmstore) */ static Pagent * dostore(Dbm *d, char *s, int len, long *ahash, long *asplit) { int i, l, rlen, nent, toff, inx; unsigned minx = MAXUSHORT, maxx = 0; long hash, hmask, IfSplit = 0; char *p; Pagent *pe; Pagblk *pb = (Pagblk *)d->pag.buf; hash = mdbmcalchash(s, len); if (ahash) *ahash = hash; if (asplit) { IfSplit = *asplit; *asplit = 0; } while ((hmask = mdbmaccess(d, hash)) != -1) { rlen = len; nent = begets(pb->nent); for (i = 0; i < nent; i++) { pe = pagent(pb, i); toff = begets(pe->txtoff); if ((i? begets(pagent(pb, i-1)->txtoff): d->pag.size) - toff == rlen && memcmp(s, d->pag.buf + toff, rlen) == 0) { beputs(pe->nlinks, begets(pe->nlinks) + 1); d->pag.fflags |= Fdirty; return pe; } inx = begets(pe->inx); if (inx < minx) minx = inx; if (inx > maxx) maxx = inx; } pe = additem(d->pag.buf, d->pag.size, rlen); if (pe) { beputs(pe->nlinks, 1); /* will be either key or datum */ beputs(pe->outx, 0); /* not a key (at least, not yet) */ /* * inx will be one less than min inx (if possible), * or one more than max inx (if possible), th