Xref: utzoo unix-pc.general:819 comp.sys.att:3486 Path: utzoo!attcan!uunet!lll-winken!lll-tis!ames!ucsd!rutgers!mtunx!att!ihnp4!chinet!randy From: randy@chinet.UUCP (Randy Suess) Newsgroups: unix-pc.general,comp.sys.att Subject: Re: BSD stuff --> libndir and libdbm Summary: mdbm part 2 Message-ID: <5828@chinet.UUCP> Date: 14 Jun 88 13:00:40 GMT Reply-To: randy@chinet.UUCP (Randy Suess) Organization: Chinet - Public Access Unix Lines: 639 Part 2 of the mdbm shar #! /bin/sh # This is a shell archive. Remove anything before this line, then unpack # it by saving it into a file and typing "sh file". To overwrite existing # files, type "sh file -c". You can also feed this as standard input via # unshar, or by typing "sh ./mdbm/mdbm.3x <<'END_OF_./mdbm/mdbm.3x' X.TH MDBM 3X X.UC 4 \" well not really but . . . X.SH NAME Xmdbm_open, mdbm_fetch, mdbm_store, mdbm_delete, mdbm_firstkey, ... \- multiple key hashed data base subroutines X.SH SYNOPSIS X.nf X.PP X.B #include X.B "\fP/* \fBtypedef struct {" X.B " char *dptr;" X.B " int dsize;" X.BR "} datum; " "*/ /* in */" X.PP X.B struct mdbm * X.B mdbm_open(file, flags, mode, adsize, amsize, comment) X.B char *file; X.B int flags, mode; X.B int *adsize, *amsize; X.B char *comment; X.PP X.B datum mdbm_fetch(d, key) X.B struct mdbm *d; X.B datum key; X.PP X.B mdbm_store(d, key, content, replace) X.B struct mdbm *d; X.B datum key, content; X.B int replace; X.PP X.B mdbm_delete(d, key) X.B struct mdbm *d; X.B datum key; X.PP X.B datum mdbm_firstkey(d) X.B struct mdbm *d; X.PP X.B datum mdbm_nextkey(d, key) X.B struct mdbm *d; X.B datum key; X.PP X.B mdbm_sync(d) X.B struct mdbm *d; X.PP X.B mdbm_close(d) X.B struct mdbm *d; X.PP X.B mdbm_getflags(d, flags) X.B struct mdbm *d; X.B int flags; X.PP X.B mdbm_setflags(d, flags) X.B struct mdbm *d; X.B int flags; X.PP X.B mdbm_bisflags(d, flags) X.B struct mdbm *d; X.B int flags; X.PP X.B mdbm_bicflags(d, flags) X.B struct mdbm *d; X.B int flags; X.SH DESCRIPTION XThese functions maintain key/content pairs in a database. XThe functions will handle very large (a billion blocks) Xdatabases and will usually access a keyed item in one or two file Xsystem accesses. The functions are obtained with the loader option X.BR \-lmdbm . X.PP X.IR Key s Xand X.IR content s Xare described by the X.I datum Xtypedef, which is defined in the include file X.IR mdbm.h . XA X.I datum Xspecifies a string of X.I dsize Xbytes pointed to by X.I dptr. XArbitrary binary data, as well as normal ASCII strings, are allowed. XThe database is stored in two files. One file is a directory Xcontaining a bit map and has ``.map'' as its suffix. The second Xfile contains all data and has ``.dat'' as its suffix. X.PP XBefore a database can be accessed, it must be opened by X.I mdbm_open. XThe X.I flags Xare simply passed to the open system call (see X.IR open(2) ). X(This is not strictly true: if the read/write mode is O_WRONLY, it Xis converted internally to O_RDWR.) X.PP XThe X.I mode Xparameter is only used with X.B O_CREAT Xwhen creating a new database. XThe value is merely passed to the X.I open Xsystem call. XIf X.B O_CREAT Xis not specified, the ``.map'' and ``.dat'' files must exist. X.I mdbm_open Xreturns a pointer to the database for use by the other mdbm routines. XIf the database cannot be opened, X.I mdbm_open Xreturns NULL. X.PP XThe X.I adsize Xand X.I amsize Xparameters, if non-null, should point to integers containing the Xdesired data and map block sizes of the database. On return, these Xvariables will have been filled in with the actual sizes in use. X(The values are only used when creating a database, but are always Xmodified on return.) If the default sizes are acceptable, these Xtwo parameters may be given as null pointers. X.PP XThe X.I comment Xparameter, like the X.I adsize Xand X.I amsize Xparameters, is ``value-result''. When a new database is created Xa comment of up to MDBM_CSIZ characters is stored along with it. X.I Comment Xshould be a pointer to an array of at least MDBM_CSIZ characters. XIt will be used to initialize the comment for a new database and Xwill be filled in with a null terminated string when opening an Xexisting datbase. If the comment information Xis not desired, the parameter may be given as zero; in this case Xthe file name will be used to initialize the comment field of a Xnew database. X.PP XOnce open, the data stored under a key is accessed by X.I mdbm_fetch Xand data is placed under a key by X.IR mdbm_store . XA key (and its associated contents) is deleted by X.IR mdbm_delete . XA linear pass through all keys in a database Xmay be made, in an (apparently) random order, by use of X.I mdbm_firstkey Xand X.IR mdbm_nextkey . X.I Mdbm_firstkey Xwill return the first key in the database. With any key X.I mdbm_nextkey Xwill return the next key in the database. XThis code will traverse the database d: X.IP X.B for X(key = mdbm_firstkey(d); key.dptr != NULL; key = mdbm_nextkey(d, key)) X.PP X.I mdbm_sync Xwill complete any pending writes on the database. (If the X.B MDBM_ISAUTOW Xflag has been set \- see X.I mdbm_setflags Xbelow \- then no writes will be pending). In any case X.I mdbm_sync Xcalls X.I fsync Xon the map and data file descriptors. X.PP XA database may be closed (and the associated storage and file Xdescriptors released) with X.IR mdbm_close . X.PP XWritable databases X.I must Xbe closed before exiting to ensure that all data are written. X(To be precise, this is only necessary if the X.B MDBM_ISAUTOW Xflag was not on, and no X.I mdbm_sync Xhas been done since the last X.IR mdbm_store ). X.PP XThe fourth parameter to store (``replace'') specifies what to Xdo in the event of a key collision. The value X.B MDBM_INSERT X(0) makes X.I mdbm_store Xreturn the error value 1 in the event that the given key already Xpoints to a particular datum. The value X.B MDBM_REPLACE X(actually your favorite nonzero value will do) tells Xstore to go ahead and replace the old datum. X.PP XVarious flags may be examined and set with the X.I mdbm_getflags Xand X.I mdbm_setflags Xmacros. Currently there are only four flags, and only one of these Xis user settable. They are: X.TP X.B MDBM_ISRONLY XIndicates that a database was opened with O_RDONLY and cannot be written. X.I (Store Xand friends return an error indication and set X.B errno X(see X.IR intro(2) ) Xto X.B EPERM Xif they are asked to operate on a read-only database.) X.TP X.B MDBM_ISAUTOW XSpecifies that all modifications to the database be written to the system Ximmediately (note that X.IR fsync s Xare X.I not Xdone in this case). This might be useful for an interactive program, Xto reduce the chances of loss of data in the event of a system crash. XThis is currently the only user settable flag. X.TP X.B MDBM_DDIRTY XIndicates that the data buffer is out of sync with its disk file. X.TP X.B MDBM_MDIRTY XIndicates that the bitmap buffer is out of sync with its disk file. X.PP XThe X.I mdbm_setflags Xroutine will set the user-settable flags to the values in its second Xargument. The X.I mdbm_getflags Xroutine returns all the flags in the database. The X.I mdbm_bisflags Xturns on the indicated user-settable flags, and the X.I mdbm_bicflags Xturns off the indicated flags. E.g., The C statement X.I mdbm_bisflags(d, \fP\fBMDBM_ISAUTOW\fP\fI) Xwould turn on the auto-write flag. X.SH "But what about multiple keys?" X.PP XThe database routines invisibly keep track of how many keys are pointing Xto a particular datum, and ensure that the datum itself is not removed Xuntil it is no longer in use. In fact, a datum may also be used as a key. XThus there is no storage penalty for having many keys that point to one Xdatum or even to themselves. X.PP XThe implementation of this involved changing the underlying structure Xof the database. Keys and data are no longer stored in pairs; instead, Xeach data block contains an arbitrary number of items each with Xincoming and outgoing link indicies. In addition to breaking anything Xthat depended on the old implementation, this means that in most cases Xtwo file system accesses are required to fetch a particular datum given Xa key (one to find the key and another to find its datum). However, Xthis is offset by the new 4.2BSD file system, which will probably Ximprove access times for all but the largest databases. X.SH DIAGNOSTICS XAll functions that return an X.I int Xindicate errors with negative values. A zero return indicates OK. XRoutines that return a X.I datum Xindicate errors with a NULL (0) X.IR dptr . X.I mdbm_open Xreturns NULL on error. X.SH AUTHORS XI don't know who wrote the original dbm code, but Chris Torek Xmodified it to handle multiple databases, changed the internal Xformat to support multiple keys, and added anything Xthat you see here and not in dbm (see X.IR dbm(3) ). X.SH "SEE ALSO" X.I dbm(3) X.SH BUGS XThe ``.dat'' file will contain holes so that its apparent size is X(usually) two to four times its actual content. Older UNIX systems Xmay create real file blocks for these holes when touched. These files Xcannot be copied by normal means (cp, cat, tp, tar, ar) without filling Xin the holes. X.PP X.I Dptr Xpointers returned by these subroutines Xpoint into static storage that is changed by subsequent calls. X.PP XThe previously undocumented X.I forder Xfunction is defunct. (It used to return the block number given a key.) X.PP XThe size of a key or content string must not exceed the data block size Xused when creating the database. Moreover, all strings that hash Xtogether must fit on a single block. X.I Mdbm_store Xwill return an error in the event that a block fills with Xinseparable data. X.PP X.I Mdbm_delete Xdoes not physically reclaim file space, Xalthough it does make it available for reuse. X.PP XDisk errors are not handled at all. No warning is given when a Xdisk read or write fails, and data may be lost or destroyed afterwards. X.PP XThe order of keys presented by X.I mdbm_firstkey Xand X.I mdbm_nextkey Xdepends on a hashing function, not on anything interesting. END_OF_./mdbm/mdbm.3x if test 9018 -ne `wc -c <./mdbm/mdbm.3x`; then echo shar: \"./mdbm/mdbm.3x\" unpacked with wrong size! fi # end of overwriting check fi if test -f ./mdbm/store.c -a "${1}" != "-c" ; then echo shar: Will not over-write existing file \"./mdbm/store.c\" else echo shar: Extracting \"./mdbm/store.c\" \(7864 characters\) sed "s/^X//" >./mdbm/store.c <<'END_OF_./mdbm/store.c' X#ifndef lint Xstatic char rcsid[] = "$Header: /ful/chris/dist/mdbm/store.c,v 1.1 84/08/12 10:03:37 chris Rel $"; X#endif X X#include X#include X#include "mdbm.h" X#include "mdbm_local.h" X X/* X * Exhaustively search for a valid inx index number for the new entry X * in d. We "guarantee" that one such will be available. (Used by X * mdbm_dostore) X */ Xstatic unsigned short mdbm_inx (d) Xregister struct mdbm *d; X{ X#define db ((struct mdbm_dblock *) d -> mdbm_d) X register struct mdbm_dentry *de; X register int i, X n = db -> db_n - 1; X register unsigned short inx = 1; X X for (;;) { X de = db -> db_e; X i = n; X while (--i >= 0) { X if (de -> de_inx == inx) X goto nope; X de++; X } X return inx; Xnope: X if (inx == MAXUSHORT) X break; X inx++; X } X printf ("mdbm bug: no inx's available (can't happen)\n"); X fflush(stdout); X abort (); X return 1; X#undef db X} X X/* X * Add an item to a data block, returning a pointer to the dentry X * descriptor (or 0 if it doesn't fit). The caller will fill in all X * fields except the offset, and will fill in the text of the item. X */ Xstatic struct mdbm_dentry *mdbm_additem (buf, dsize, len) Xregister char *buf; Xint dsize, len; X{ X#define db ((struct mdbm_dblock *) buf) X register struct mdbm_dentry *de; X register int i = db -> db_n; X X /* Figure out where the text should go. If there are no entries in this X block, it will go at the end of the block; otherwise, it will go right X before the last entry. It must not cross over the entry descriptor X area, which will be one larger than it is now. */ X de = &db -> db_e[i]; X i = (i ? de[-1].de_off : dsize) - len; X if (buf + i < (char *) &de[1]) X return 0; X X db -> db_n++; X de -> de_off = i; X return de; X#undef db X} X X/* X * Actually store the text of an item in a dblock. Fill in the supplied X * pointer (if any) with the hash number of the item. Also, if a split X * occurs, check *asplit, and if the block numbers match, set *asplit, X * otherwise clear it. (Used by mdbm_store) X */ Xstatic struct mdbm_dentry *mdbm_dostore (d, s, len, ahash, asplit) Xregister struct mdbm *d; Xchar *s; Xint len; Xlong *ahash; Xlong *asplit; X{ X#define db ((struct mdbm_dblock *) d -> mdbm_d) X register struct mdbm_dentry *de; X register int i; X long hash; X long hmask; X long IfSplit; X unsigned int minx = MAXUSHORT, X maxx = 0; X X hash = mdbm_calchash (s, len); X if (ahash) X *ahash = hash; X if (asplit) { X IfSplit = *asplit; X *asplit = 0; X } Xloop: X { X register int rlen = len; X X hmask = mdbm_access (d, hash); X for (i = 0, de = db -> db_e; i < db -> db_n; i++, de++) { X if (rlen == (i ? de[-1].de_off : d -> mdbm_dsize) - de -> de_off) X if (bcmp (s, d -> mdbm_d + de -> de_off, rlen) == 0) { X de -> de_links++; X goto returnit; X } X if (de -> de_inx < minx) X minx = de -> de_inx; X if (de -> de_inx > maxx) X maxx = de -> de_inx; X } X de = mdbm_additem (d -> mdbm_d, d -> mdbm_dsize, rlen); X } X if (de) { X de -> de_links = 1; /* will be either a key or a datum */ X de -> de_outx = 0; /* not a key (at least, not yet) */ X /* inx will be one less than min inx (if possible), or one more than X max inx (if possible), that occur in the block. If none of those X yeild results, we perform an exhaustive search. Hopefully the X searches are rare. */ X if (i == 0) X de -> de_inx = 1; /* first one, special case */ X else if (minx < MAXUSHORT && minx > 1) X de -> de_inx = minx - 1; X else if (maxx && maxx < MAXUSHORT) X de -> de_inx = maxx + 1; X else X de -> de_inx = mdbm_inx (d); X bcopy (s, d -> mdbm_d + de -> de_off, len); Xreturnit: X d -> mdbm_flags |= MDBM_DDIRTY; X return de; X } X /* Didn't fit; split the block to make room. Presumably about half of the X existing entries will move to the new block. */ X if (len + sizeof *db > d -> mdbm_dsize) X return 0; /* hopeless! */ X /* If we are splitting the "interesting" block, make a note of that fact */ X if (asplit && IfSplit == d -> mdbm_dblock) X *asplit = 1; X bzero (d -> mdbm_s, d -> mdbm_dsize); X hmask++; X for (i = 0, de = db -> db_e; i < db -> db_n;) { X register int l; X register char *p = d -> mdbm_d + de -> de_off; X X l = (i ? de[-1].de_off : d -> mdbm_dsize) - de -> de_off; X if (mdbm_calchash (p, l) & hmask) { X register struct mdbm_dentry *nde; X X nde = mdbm_additem (d -> mdbm_s, d -> mdbm_dsize, l); X bcopy (p, d -> mdbm_s + nde -> de_off, l); X nde -> de_links = de -> de_links; X nde -> de_inx = de -> de_inx; X nde -> de_outx = de -> de_outx; X nde -> de_outh = de -> de_outh; X de -> de_links = 1; /* force mdbm_delitem to remove it */ X mdbm_delitem (d, de - db -> db_e); X } X else X i++, de++; X } X MDBM_WBLK (d -> mdbm_datafd, d -> mdbm_dblock + hmask, d -> mdbm_s, X d -> mdbm_dsize, 0); X d -> mdbm_flags |= MDBM_DDIRTY; X hmask--; X /* Now mark the block as having been split by setting the appropriate bit in X the map. */ X { X register long bit = (hash & hmask) + hmask; X register int n; X register long bn; X X n = bit % BYTESIZ; /* bit index */ X bn = bit / BYTESIZ; /* byte index */ X i = bn % d -> mdbm_msize;/* byte offset in block */ X if (bit >= d -> mdbm_maxbit) { X d -> mdbm_maxbit = bit + 1; X bn /= d -> mdbm_msize;/* map block number */ X MDBM_MREAD (d, bn); /* read will probably fail, but this fills X in the block numbers and so forth */ X } X d -> mdbm_m[i] |= 1 << n;/* set the bit */ X d -> mdbm_flags |= MDBM_MDIRTY; X } X goto loop; X#undef db X} X X/* X * Store dat as datum of key key in dbm d X */ Xmdbm_store (d, key, dat, replace) Xregister struct mdbm *d; Xdatum key, dat; Xint replace; /* true => overwrite if exists */ X{ X#define db ((struct mdbm_dblock *) d -> mdbm_d) X register struct mdbm_dentry *de; X long keyblock; X int keyindex; X long didsplit; X long outh; X unsigned short outx; X extern int errno; X X if (d -> mdbm_flags & MDBM_ISRONLY) { X errno = EPERM; X return (-1); X } X /* Search for the key's datum. If it is found, then delete the datum X (unless we are told not to) and store a new one, then modify the key's X description parameters to point to the new datum. If it is not found, X then presumably there is no such key, so make a new one, then precede X as before. */ X de = mdbm_search (d, key.dptr, key.dsize, &keyblock, &keyindex, 0); X if (de) { X if (!replace) X return 1; X mdbm_delitem (d, de - db -> db_e); X /* now committed - if new datum doesn't fit, old pairing is gone! */ X } X else { /* create new key */ X de = mdbm_dostore (d, key.dptr, key.dsize, (long *) 0, (long *) 0); X if (de == 0) { X MDBM_AUTO (d); X errno = ENOSPC; /* presumably */ X return (-1); X } X de -> de_outx = 1; /* force it to look like a key */ X keyblock = d -> mdbm_dblock; X keyindex = de - db -> db_e; X } X didsplit = keyblock; X de = mdbm_dostore (d, dat.dptr, dat.dsize, &outh, &didsplit); X if (de) X outx = de -> de_inx; X /* if the data store split the key's block, have to find the key again */ X if (didsplit) X if (mdbm_search (d, key.dptr, key.dsize, &keyblock, X &keyindex, 1) == 0) { X printf ("mdbm bug: post-split keysearch failed!\n"); X fflush(stdout); X abort (); X } X if (!de) { /* oops, go delete the key */ X MDBM_DREAD (d, keyblock); X de = &db -> db_e[keyindex]; X de -> de_outx = 0; /* not a key anymore */ X mdbm_delitem (d, keyindex); X MDBM_AUTO (d); X errno = ENOSPC; X return (-1); X } X /* Replace the outx and outh numbers in the old (or new) key so that it X points to the new datum */ X MDBM_DREAD (d, keyblock); X de = &db -> db_e[keyindex]; X de -> de_outh = outh; X de -> de_outx = outx; X d -> mdbm_flags |= MDBM_DDIRTY; X MDBM_AUTO (d); X return 0; X#undef db X} END_OF_./mdbm/store.c if test 7864 -ne `wc -c <./mdbm/store.c`; then echo shar: \"./mdbm/store.c\" unpacked with wrong size! fi # end of overwriting check fi echo shar: End of archive 2 \(of 2\). cp /dev/null ark2isdone MISSING="" for I in 1 2 ; do if test ! -f ark${I}isdone ; then MISSING="${MISSING} ${I}" fi done if test "${MISSING}" = "" ; then echo You have unpacked both archives. rm -f ark[1-9]isdone else echo You still need to unpack the following archives: echo " " ${MISSING} fi ## End of shell archive. exit 0 -- But don't underestimate raw, frothing, manic hardware. (barry shein) Randy Suess ..!att!chinet!randy