BSD stuff --> libndir and libdbm
Randy Suess
randy at chinet.UUCP
Tue Jun 14 23:00:40 AEST 1988
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 <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of archive 2 (of 2)."
# Contents: ./mdbm/mdbm.3x ./mdbm/store.c
# Wrapped by randy at chinet on Wed Jun 8 13:52:20 1988
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f ./mdbm/mdbm.3x -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"./mdbm/mdbm.3x\"
else
echo shar: Extracting \"./mdbm/mdbm.3x\" \(9018 characters\)
sed "s/^X//" >./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 <mdbm.h>
X.B "\fP/* \fBtypedef struct {"
X.B " char *dptr;"
X.B " int dsize;"
X.BR "} datum; " "*/ /* in <mdbm.h> */"
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 <stdio.h>
X#include <errno.h>
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
More information about the Unix-pc.general
mailing list