mdbm library source
chris at umcp-cs.UUCP
chris at umcp-cs.UUCP
Mon Aug 13 02:18:14 AEST 1984
: Run this shell script with "sh" not "csh"
PATH=:/bin:/usr/bin:/usr/ucb
export PATH
all=FALSE
if [ $1x = -ax ]; then
all=TRUE
fi
cat << '--End Of Notice--' >/dev/null
Well, here it is: the threatened -- I mean promised! -- source to the
``mdbm'' Multiple Key dbm library. It comes complete with some
debugging code and a test routine (and documentation, now *that's* rare
-- of course it's just a man page). 'Ware 4.2BSDisms, if porting.
As usual, no warranties are expressed or implied, et cetera et cereal
[[it's breakfast time]] and so forth. And don't forget the .signature
at the end.
Enjoy ...
--End Of Notice--
/bin/echo 'Making directory "mdbm"'
mkdir mdbm
/bin/echo 'Extracting mdbm/Makefile'
sed 's/^X//' <<'//go.sysin dd *' >mdbm/Makefile
# $Header$
#
# The -R flag compiles initialized data into the text area. Not really
# necessary, but nice.
CFLAGS= -O -R
OBJS= access.o checkblock.o close.o compare.o delete.o delitem.o\
fetch.o firsthash.o firstkey.o hash.o hashinc.o nextkey.o\
open.o search.o store.o sync.o
SRCS= access.c checkblock.c close.c compare.c delete.c delitem.c\
fetch.c firsthash.c firstkey.c hash.c hashinc.c nextkey.c\
open.c search.c store.c sync.c
HDRS= mdbm.h mdbm_local.h
X.c.o:
$(CC) $(CFLAGS) -c $<
@ld -r -x $@
@mv a.out $@
all: libmdbm.a testdbm dumpdbm
libmdbm.a: $(OBJS)
ar cr libmdbm.a $(OBJS)
ranlib libmdbm.a
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
testdbm: testdbm.o libmdbm.a
cc $(CFLAGS) -o testdbm testdbm.o libmdbm.a
dumpdbm: dumpdbm.o libmdbm.a
cc $(CFLAGS) -o dumpdbm dumpdbm.o libmdbm.a
clean:
rm -f libmdbm.a *.o a.out testdbm dumpdbm core
lint: $(SRCS) $(HDRS)
lint -h $(SRCS) | egrep -v 'possible pointer alignment problem'
access.o: mdbm.h mdbm_local.h
additem.o: mdbm.h mdbm_local.h
checkblock.o: mdbm.h mdbm_local.h
close.o: mdbm.h mdbm_local.h
delete.o: mdbm.h mdbm_local.h
delitem.o: mdbm.h mdbm_local.h
fetch.o: mdbm.h mdbm_local.h
firsthash.o: mdbm.h mdbm_local.h
firstkey.o: mdbm.h mdbm_local.h
hash.o: mdbm.h mdbm_local.h
nextkey.o: mdbm.h mdbm_local.h
open.o: mdbm.h mdbm_local.h
search.o: mdbm_local.h
store.o: mdbm.h mdbm_local.h
sync.o: mdbm.h mdbm_local.h
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
/bin/chmod 644 mdbm/Makefile
/bin/echo -n ' '; /bin/ls -ld mdbm/Makefile
fi
/bin/echo 'Extracting mdbm/access.c'
sed 's/^X//' <<'//go.sysin dd *' >mdbm/access.c
#ifndef lint
static char rcsid[] = "$Header: /ful/chris/dist/mdbm/access.c,v 1.1 84/08/12 09:54:48 chris Rel $";
#endif
#include <stdio.h>
#include "mdbm.h"
#include "mdbm_local.h"
X/*
* 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 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.
*/
int mdbm_access (d, hash)
register struct mdbm *d;
register long hash;
{
register long hmask,
b;
for (hmask = 0;; hmask = (hmask << 1) + 1) {
b = (hash & hmask) + hmask;/* map bit number */
if (b < d -> mdbm_maxbit) {
register int i,
n;
n = b % BYTESIZ; /* bit index */
b /= BYTESIZ; /* byte index */
i = b % d -> mdbm_msize;/* byte offset in map */
b /= d -> mdbm_msize;/* map block number */
MDBM_MREAD (d, b);
if (d -> mdbm_m[i] & (1 << n))
continue;
}
b = hash & hmask;
MDBM_DREAD (d, b);
return hmask;
}
}
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
/bin/chmod 644 mdbm/access.c
/bin/echo -n ' '; /bin/ls -ld mdbm/access.c
fi
/bin/echo 'Extracting mdbm/checkblock.c'
sed 's/^X//' <<'//go.sysin dd *' >mdbm/checkblock.c
#ifndef lint
static char rcsid[] = "$Header: /ful/chris/dist/mdbm/checkblock.c,v 1.1 84/08/12 09:56:16 chris Rel $";
#endif
#include <stdio.h>
#include "mdbm.h"
#include "mdbm_local.h"
X/*
* Perform some sanity checks on a data block
*/
mdbm_checkblock (buf, size)
char *buf;
int size;
{
register struct mdbm_dblock *db = (struct mdbm_dblock *) buf;
register struct mdbm_dentry *de;
register int i,
t = size;
de = &db -> db_e[1];
for (i = 1; i < db -> db_n; i++) {
if (de -> de_off > t)
goto bad;
t = de -> de_off;
de++;
}
if (&buf[t] < (char *) de)
goto bad;
return;
bad:
printf ("mdbm: bad block\n");
abort ();
bzero (buf, size);
}
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
/bin/chmod 644 mdbm/checkblock.c
/bin/echo -n ' '; /bin/ls -ld mdbm/checkblock.c
fi
/bin/echo 'Extracting mdbm/close.c'
sed 's/^X//' <<'//go.sysin dd *' >mdbm/close.c
#ifndef lint
static char rcsid[] = "$Header: /ful/chris/dist/mdbm/close.c,v 1.1 84/08/12 09:57:45 chris Rel $";
#endif
#include <stdio.h>
#include "mdbm.h"
#include "mdbm_local.h"
X/*
* Close a database
*/
mdbm_close (d)
register struct mdbm *d;
{
MDBM_SYNC (d);
(void) close (d -> mdbm_datafd);
(void) close (d -> mdbm_mapfd);
free (d -> mdbm_d);
free (d -> mdbm_s);
free (d -> mdbm_m);
free ((char *) d);
return 0;
}
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
/bin/chmod 644 mdbm/close.c
/bin/echo -n ' '; /bin/ls -ld mdbm/close.c
fi
/bin/echo 'Extracting mdbm/compare.c'
sed 's/^X//' <<'//go.sysin dd *' >mdbm/compare.c
#ifndef lint
static char rcsid[] = "$Header: /ful/chris/dist/mdbm/compare.c,v 1.1 84/08/12 09:57:59 chris Rel $";
#endif
X/*
* Compare strings s1 and s2 for len bytes; return the difference
* between the first differing characters. Could probably use strncmp
* but I don't trust it to work the same way when encountering \0s.
*/
mdbm_compare (s1, s2, len)
register char *s1, *s2;
register int len;
{
while (--len >= 0)
if (*s1++ != *s2++)
return *--s1 - *--s2;
return 0;
}
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
/bin/chmod 644 mdbm/compare.c
/bin/echo -n ' '; /bin/ls -ld mdbm/compare.c
fi
/bin/echo 'Extracting mdbm/delete.c'
sed 's/^X//' <<'//go.sysin dd *' >mdbm/delete.c
#ifndef lint
static char rcsid[] = "$Header: /ful/chris/dist/mdbm/delete.c,v 1.1 84/08/12 09:58:22 chris Rel $";
#endif
#include <stdio.h>
#include <errno.h>
#include "mdbm.h"
#include "mdbm_local.h"
X/*
* Delete datum under key in dbm d
*/
mdbm_delete (d, key)
register struct mdbm *d;
datum key;
{
#define db ((struct mdbm_dblock *) d -> mdbm_d)
register struct mdbm_dentry *de;
long keyblock;
int keyindex;
extern int errno;
de = mdbm_search (d, key.dptr, key.dsize, &keyblock, &keyindex, 0);
if (de == 0) {
errno = ENOENT;
return (-1);
}
if (d -> mdbm_flags & MDBM_ISRONLY) {
errno = EPERM;
return (-1);
}
/* delete the datum */
mdbm_delitem (d, de - db -> db_e);
/* delete the key */
MDBM_DREAD (d, keyblock);
de = &db -> db_e[keyindex];
de -> de_outx = 0; /* not in use as a key anymore */
mdbm_delitem (d, keyindex);
MDBM_AUTO (d);
return 0;
}
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
/bin/chmod 644 mdbm/delete.c
/bin/echo -n ' '; /bin/ls -ld mdbm/delete.c
fi
/bin/echo 'Extracting mdbm/delitem.c'
sed 's/^X//' <<'//go.sysin dd *' >mdbm/delitem.c
#ifndef lint
static char rcsid[] = "$Header: /ful/chris/dist/mdbm/delitem.c,v 1.1 84/08/12 09:58:37 chris Rel $";
#endif lint
#include <stdio.h>
#include "mdbm.h"
#include "mdbm_local.h"
X/*
* Delete item 'n' from current data buffer of dbm d
*/
mdbm_delitem (d, n)
register struct mdbm *d;
register int n;
{
register int i;
#define db ((struct mdbm_dblock *) d -> mdbm_d)
register struct mdbm_dentry *de;
if (n < 0 || n >= db -> db_n)
goto bad;
de = &db -> db_e[n];
if (de -> de_links > 1) {
de -> de_links--;
goto done;
}
db -> db_n--;
i = (n ? de[-1].de_off : d -> mdbm_dsize) - de -> de_off;
if (i) { /* delete i bytes of text */
if (n < db -> db_n) {
register char *to,
*from;
register int bytes;
to = d -> mdbm_d + (n ? de[-1].de_off : d -> mdbm_dsize);
from = to - i;
bytes = de -> de_off - db -> db_e[db -> db_n].de_off;
while (--bytes >= 0)
*--to = *--from;
}
bzero (d -> mdbm_d + db -> db_e[db -> db_n].de_off, i);
}
{
register struct mdbm_dentry *e;
e = &db -> db_e[db -> db_n];
while (de < e) {
*de = de[1];
de -> de_off += i;
de++;
}
bzero ((char *) e, sizeof e);
}
done:
d -> mdbm_flags |= MDBM_DDIRTY;
return;
bad:
printf ("mdbm bug: bad delitem\n");
abort ();
}
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
/bin/chmod 644 mdbm/delitem.c
/bin/echo -n ' '; /bin/ls -ld mdbm/delitem.c
fi
/bin/echo 'Extracting mdbm/dumpdbm.c'
sed 's/^X//' <<'//go.sysin dd *' >mdbm/dumpdbm.c
#include <stdio.h>
#include <sys/types.h>
#include <sys/file.h>
#include <sys/stat.h>
#include <signal.h>
#include "mdbm.h"
#include "mdbm_local.h"
abort () { kill (getpid (), SIGILL); }
main (argc, argv)
int argc;
char **argv;
{
register struct mdbm *mp;
register struct mdbm_dblock *db;
register struct mdbm_dentry *de;
int dsize, msize, blocks;
register int i, j, len;
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, (char *) 0);
if (!mp) {
perror (argv[1]);
exit (1);
}
printf ("dbm %s: dsize = %d, msize = %d\n", argv[1], dsize, msize);
(void) fstat (mp -> mdbm_datafd, &sb);
blocks = sb.st_size / dsize;
printf ("(%d data blocks)\n", blocks);
db = (struct mdbm_dblock *) mp -> mdbm_d;
for (i = 0; i < blocks; i++) {
MDBM_DREAD (mp, i);
printf ("block %d: %d entries\n", i, db -> db_n);
for (j = 0, de = db -> db_e; j < db -> db_n; j++, de++) {
printf ("\t%2d: @%4d links=%2d inx=%4d outx=%4d outh=%08x ",
j, de -> de_off, de -> de_links, de -> de_inx,
de -> de_outx, de -> de_outh);
len = (j ? de[-1].de_off : dsize) - de -> de_off;
pr_entry (mp -> mdbm_d + de -> de_off, len);
}
}
(void) mdbm_close (mp);
exit (0);
}
pr_entry (s, len)
register char *s;
register int len;
{
register int c;
putchar ('"');
while (--len >= 0) {
c = *s++ & 0377;
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');
}
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
/bin/chmod 644 mdbm/dumpdbm.c
/bin/echo -n ' '; /bin/ls -ld mdbm/dumpdbm.c
fi
/bin/echo 'Extracting mdbm/fetch.c'
sed 's/^X//' <<'//go.sysin dd *' >mdbm/fetch.c
#ifndef lint
static char rcsid[] = "$Header: /ful/chris/dist/mdbm/fetch.c,v 1.1 84/08/12 09:59:20 chris Rel $";
#endif
#include <stdio.h>
#include "mdbm.h"
#include "mdbm_local.h"
X/*
* Find datum in dbm d, given key
*/
datum mdbm_fetch (d, key)
register struct mdbm *d;
datum key;
{
#define db ((struct mdbm_dblock *) d -> mdbm_d)
register struct mdbm_dentry *de;
datum item;
de = mdbm_search (d, key.dptr, key.dsize, (long *) 0, (int *) 0, 0);
if (de) {
item.dptr = d -> mdbm_d + de -> de_off;
item.dsize = (de > db -> db_e ? de[-1].de_off : d -> mdbm_dsize) -
de -> de_off;
}
else
item.dptr = 0, item.dsize = 0;
return item;
}
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
/bin/chmod 644 mdbm/fetch.c
/bin/echo -n ' '; /bin/ls -ld mdbm/fetch.c
fi
/bin/echo 'Extracting mdbm/firsthash.c'
sed 's/^X//' <<'//go.sysin dd *' >mdbm/firsthash.c
#ifndef lint
static char rcsid[] = "$Header: /ful/chris/dist/mdbm/firsthash.c,v 1.1 84/08/12 09:59:59 chris Rel $";
#endif
#include <stdio.h>
#include "mdbm.h"
#include "mdbm_local.h"
X/*
* Return the first datum in dbm d with hash value hash
*/
datum mdbm_firsthash (d, hash)
register struct mdbm *d;
long hash;
{
#define db ((struct mdbm_dblock *) d -> mdbm_d)
register struct mdbm_dentry *de;
register int i;
char *bp;
int bl;
char *ip;
int il,
found;
long hmask;
datum rval;
loop:
/* Suck in the block for the given hash, then find the "first" key. */
hmask = mdbm_access (d, hash);
found = 0;
#ifdef lint /* lint doesn't realize that 'found'
overrides the tests on bl and bp */
bl = 0;
bp = 0;
#endif lint
for (i = 0, de = db -> db_e; i < db -> db_n; i++, de++) {
if (de -> de_outx == 0) /* not a key */
continue;
il = (i ? de[-1].de_off : d -> mdbm_dsize) - de -> de_off;
ip = d -> mdbm_d + de -> de_off;
if (!found || il < bl || (il == bl && mdbm_compare (ip, bp, il) < 0)) {
bl = il;
bp = ip;
found++;
}
}
if (found) {
bcopy (bp, rval.dptr = d -> mdbm_s, rval.dsize = bl);
return rval;
}
/* No item with this hash, so get next hash and try again */
hash = mdbm_hashinc (hash, hmask);
if (hash == 0) { /* no more */
rval.dsize = 0;
rval.dptr = 0;
return rval;
}
goto loop;
}
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
/bin/chmod 644 mdbm/firsthash.c
/bin/echo -n ' '; /bin/ls -ld mdbm/firsthash.c
fi
/bin/echo 'Extracting mdbm/firstkey.c'
sed 's/^X//' <<'//go.sysin dd *' >mdbm/firstkey.c
#ifndef lint
static char rcsid[] = "$Header: /ful/chris/dist/mdbm/firstkey.c,v 1.1 84/08/12 10:00:27 chris Rel $";
#endif
#include <stdio.h>
#include "mdbm.h"
#include "mdbm_local.h"
X/*
* Return the "first" key in dbm d
*/
datum mdbm_firstkey (d)
struct mdbm *d;
{
return mdbm_firsthash (d, 0L);
}
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
/bin/chmod 644 mdbm/firstkey.c
/bin/echo -n ' '; /bin/ls -ld mdbm/firstkey.c
fi
/bin/echo 'Extracting mdbm/hash.c'
sed 's/^X//' <<'//go.sysin dd *' >mdbm/hash.c
#include <stdio.h>
#include "mdbm.h"
#include "mdbm_local.h"
int hitab[16] = {
X/* 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,
};
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,
};
X/*
* Calculate the hash val for the given item.
*/
long mdbm_calchash (s, len)
register char *s;
register int len;
{
register int hashi = 0;
register long hashl = 0L;
while (--len >= 0) {
register int f = *s++;
#if BYTESIZ > 4 && BYTESIZ <= 8 /* an easy optimization */
hashi += hitab[f & 15];
hashl += hltab[hashi & 63];
f >>= 4;
hashi += hitab[f & 15];
hashl += hltab[hashi & 63];
#else
register int j;
for (j = 0; j < BYTESIZ; j += 4) {
hashi += hitab[f & 15];
hashl += hltab[hashi & 63];
f >>= 4;
}
#endif
}
return hashl;
}
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
/bin/chmod 644 mdbm/hash.c
/bin/echo -n ' '; /bin/ls -ld mdbm/hash.c
fi
/bin/echo 'Extracting mdbm/hashinc.c'
sed 's/^X//' <<'//go.sysin dd *' >mdbm/hashinc.c
#ifndef lint
static char rcsid[] = "$Header: /ful/chris/dist/mdbm/hashinc.c,v 1.1 84/08/12 10:01:19 chris Rel $";
#endif
X/*
* Return the next hash number for this dbm, or 0 for no more
*/
long mdbm_hashinc (hash, hmask)
register long hash, hmask;
{
register long bit;
hash &= hmask;
bit = hmask + 1;
for (;;) {
bit >>= 1;
if (bit == 0)
return 0L;
if ((hash & bit) == 0)
return hash | bit;
hash &= ~bit;
}
}
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
/bin/chmod 644 mdbm/hashinc.c
/bin/echo -n ' '; /bin/ls -ld mdbm/hashinc.c
fi
/bin/echo 'Extracting mdbm/mdbm.3x'
sed 's/^X//' <<'//go.sysin dd *' >mdbm/mdbm.3x
X.TH MDBM 3X
X.UC 4 \" well not really but . . .
X.SH NAME
mdbm_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
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. The functions are obtained with the loader option
X.BR \-lmdbm .
X.PP
X.IR Key s
and
X.IR content s
are described by the
X.I datum
typedef, which is defined in the include file
X.IR mdbm.h .
A
X.I datum
specifies a string of
X.I dsize
bytes pointed to by
X.I dptr.
Arbitrary binary data, as well as normal ASCII strings, are allowed.
The database is stored in two files. One file is a directory
containing a bit map and has ``.map'' as its suffix. The second
file contains all data and has ``.dat'' as its suffix.
X.PP
Before a database can be accessed, it must be opened by
X.I mdbm_open.
The
X.I flags
are simply passed to the open system call (see
X.IR open(2) ).
(This is not strictly true: if the read/write mode is O_WRONLY, it
is converted internally to O_RDWR.)
X.PP
The
X.I mode
parameter is only used with
X.B O_CREAT
when creating a new database.
The value is merely passed to the
X.I open
system call.
If
X.B O_CREAT
is not specified, the ``.map'' and ``.dat'' files must exist.
X.I mdbm_open
returns a pointer to the database for use by the other mdbm routines.
If the database cannot be opened,
X.I mdbm_open
returns NULL.
X.PP
The
X.I adsize
and
X.I amsize
parameters, if non-null, should point to integers containing the
desired data and map 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, these
two parameters may be given as null pointers.
X.PP
The
X.I comment
parameter, like the
X.I adsize
and
X.I amsize
parameters, is ``value-result''. When a new database is created
a comment of up to MDBM_CSIZ characters is stored along with it.
X.I Comment
should be a pointer to an array of at least MDBM_CSIZ characters.
It will be used to initialize the comment for a new database and
will be filled in with a null terminated string when opening an
existing datbase. If the comment information
is not desired, the parameter may be given as zero; in this case
the file name will be used to initialize the comment field of a
new database.
X.PP
Once open, the data stored under a key is accessed by
X.I mdbm_fetch
and data is placed under a key by
X.IR mdbm_store .
A key (and its associated contents) is deleted by
X.IR mdbm_delete .
A linear pass through all keys in a database
may be made, in an (apparently) random order, by use of
X.I mdbm_firstkey
and
X.IR mdbm_nextkey .
X.I Mdbm_firstkey
will return the first key in the database. With any key
X.I mdbm_nextkey
will return the next key in the database.
This code will traverse the database d:
X.IP
X.B for
(key = mdbm_firstkey(d); key.dptr != NULL; key = mdbm_nextkey(d, key))
X.PP
X.I mdbm_sync
will complete any pending writes on the database. (If the
X.B MDBM_ISAUTOW
flag has been set \- see
X.I mdbm_setflags
below \- then no writes will be pending). In any case
X.I mdbm_sync
calls
X.I fsync
on the map and data file descriptors.
X.PP
A database may be closed (and the associated storage and file
descriptors released) with
X.IR mdbm_close .
X.PP
Writable databases
X.I must
be closed before exiting to ensure that all data are written.
(To be precise, this is only necessary if the
X.B MDBM_ISAUTOW
flag was not on, and no
X.I mdbm_sync
has been done since the last
X.IR mdbm_store ).
X.PP
The fourth parameter to store (``replace'') specifies what to
do in the event of a key collision. The value
X.B MDBM_INSERT
(0) makes
X.I mdbm_store
return the error value 1 in the event that the given key already
points to a particular datum. The value
X.B MDBM_REPLACE
(actually your favorite nonzero value will do) tells
store to go ahead and replace the old datum.
X.PP
Various flags may be examined and set with the
X.I mdbm_getflags
and
X.I mdbm_setflags
macros. Currently there are only four flags, and only one of these
is user settable. They are:
X.TP
X.B MDBM_ISRONLY
Indicates that a database was opened with O_RDONLY and cannot be written.
X.I (Store
and friends return an error indication and set
X.B errno
(see
X.IR intro(2) )
to
X.B EPERM
if they are asked to operate on a read-only database.)
X.TP
X.B MDBM_ISAUTOW
Specifies that all modifications to the database be written to the system
immediately (note that
X.IR fsync s
are
X.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.
X.TP
X.B MDBM_DDIRTY
Indicates that the data buffer is out of sync with its disk file.
X.TP
X.B MDBM_MDIRTY
Indicates that the bitmap buffer is out of sync with its disk file.
X.PP
The
X.I mdbm_setflags
routine will set the user-settable flags to the values in its second
argument. The
X.I mdbm_getflags
routine returns all the flags in the database. The
X.I mdbm_bisflags
turns on the indicated user-settable flags, and the
X.I mdbm_bicflags
turns off the indicated flags. E.g., The C statement
X.I mdbm_bisflags(d, \fP\fBMDBM_ISAUTOW\fP\fI)
would turn on the auto-write flag.
X.SH "But what about multiple keys?"
X.PP
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.
X.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). However,
this is offset by the new 4.2BSD file system, which will probably
improve access times for all but the largest databases.
X.SH DIAGNOSTICS
All functions that return an
X.I int
indicate errors with negative values. A zero return indicates OK.
Routines that return a
X.I datum
indicate errors with a NULL (0)
X.IR dptr .
X.I mdbm_open
returns NULL on error.
X.SH AUTHORS
I don't know who wrote the original dbm code, but 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 dbm (see
X.IR dbm(3) ).
X.SH "SEE ALSO"
X.I dbm(3)
X.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.
X.PP
X.I Dptr
pointers returned by these subroutines
point into static storage that is changed by subsequent calls.
X.PP
The previously undocumented
X.I forder
function is defunct. (It used to return the block number given a key.)
X.PP
The size of a key or content string must not exceed the data block size
used when creating the database. Moreover, all strings that hash
together must fit on a single block.
X.I Mdbm_store
will return an error in the event that a block fills with
inseparable data.
X.PP
X.I Mdbm_delete
does not physically reclaim file space,
although it does make it available for reuse.
X.PP
Disk errors are not handled at all. No warning is given when a
disk read or write fails, and data may be lost or destroyed afterwards.
X.PP
The order of keys presented by
X.I mdbm_firstkey
and
X.I mdbm_nextkey
depends on a hashing function, not on anything interesting.
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
/bin/chmod 644 mdbm/mdbm.3x
/bin/echo -n ' '; /bin/ls -ld mdbm/mdbm.3x
fi
/bin/echo 'Extracting mdbm/mdbm.h'
sed 's/^X//' <<'//go.sysin dd *' >mdbm/mdbm.h
X/* $Header: /ful/chris/dist/mdbm/mdbm.h,v 1.1 84/08/12 10:05:08 chris Rel $ */
X/*
* Multiple key database library (-lmdbm)
*/
X/* structure describing an open mdbm file */
struct mdbm {
int mdbm_flags; /* flags (see below) */
int mdbm_datafd; /* data area file descriptor */
int mdbm_mapfd; /* bitmap file descriptor */
int mdbm_dsize; /* data buffer size */
int mdbm_msize; /* bitmap buffer size */
long mdbm_maxbit; /* max possible set bit in map + 1 */
long mdbm_dblock; /* index of current data block */
long mdbm_mblock; /* index of current map block */
char *mdbm_d; /* current data block */
char *mdbm_s; /* secondary data block */
char *mdbm_m; /* current map block */
};
X/* structure giving (external) description of data and keys */
typedef struct {
char *dptr;
int dsize;
} datum;
X/*
* mdbm_flags
*/
#define MDBM_ISRONLY 0x01 /* true => db is readonly */
#define MDBM_ISAUTOW 0x02 /* true => do all writes immediately */
#define MDBM_DDIRTY 0x04 /* true => data buffer out of sync */
#define MDBM_MDIRTY 0x08 /* true => map buffer out of sync */
#define MDBM_UF 0x02 /* user allowed to modify only these flags */
X/*
* flags to mdbm_store()
*/
#define MDBM_INSERT 0 /* insert only; abort if key found */
#define MDBM_REPLACE 1 /* replace (or insert if not found) */
datum mdbm_fetch ();
datum mdbm_firstkey ();
datum mdbm_nextkey ();
long mdbm_forder ();
int mdbm_delete ();
int mdbm_store ();
struct mdbm *mdbm_open ();
int mdbm_close ();
X/*
* open flags the same as those for the open() system call
* with the exception that we force O_RDWR for O_WRONLY opens.
*/
X/*
* mdbm files contain a descriptive comment whose length is not
* longer than this, and is (supposed to be) null terminated.
*/
#define MDBM_CSIZ 248
X/*
* ``routines'' to examine and alter flags
*/
#define mdbm_getflags(m) \
((m) -> mdbm_flags)
#define mdbm_setflags(m,f) \
((m) -> mdbm_flags &= ~MDBM_UF, (m) -> mdbm_flags |= (f) & MDBM_UF)
#define mdbm_bisflags(m,f) \
((m) -> mdbm_flags |= (f) & MDBM_UF)
#define mdbm_bicflags(m,f) \
((m) -> mdbm_flags &= ~((f) & MDBM_UF))
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
/bin/chmod 644 mdbm/mdbm.h
/bin/echo -n ' '; /bin/ls -ld mdbm/mdbm.h
fi
/bin/echo 'Extracting mdbm/mdbm_local.h'
sed 's/^X//' <<'//go.sysin dd *' >mdbm/mdbm_local.h
X/* $Header: /ful/chris/dist/mdbm/mdbm_local.h,v 1.1 84/08/12 10:05:28 chris Rel $ */
X/*
* Definitions local to the various mdbm source files
*/
#define BYTESIZ 8 /* size of a byte */
#define MAXUSHORT 65535 /* largest legal value for unsigned short */
X/* Default database sizes for new databases */
#define MDBM_DefaultDataSize 1024 /* data buffer block size */
#define MDBM_DefaultMapSize 4096 /* bitmap buffer block size */
X/* Minimum sizes. Requests for anything smaller will be brought up
to these values. */
#define MDBM_MinDataSize 128 /* minimum data buffer size */
#define MDBM_MinMapSize 128 /* minimum map buffer size */
X/*
* This structure goes in at the front of the map file. It describes
* the per-database info. Typically the "comment" field contains the
* name of the database.
*/
struct mdbm_h {
int mh_dsize; /* size of data file blocks */
int mh_msize; /* size of map file blocks */
char mh_comment[MDBM_CSIZ];/* whatever you like */
};
X/*
* Within the map file, we simply have bits set whenever a data block
* was split. The data file is more complex. It contains the following
* info in each block:
* # entries in block
* entries
* free space
* text
*
* where the format of an entry is (as given by struct mdbm_dentry)
* <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 contain a nonzero
* number which is repeated in the inx field of its datum. The hash value
* in 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 contain a nonzero number that is unique
* to the block in which the item resides.
*/
struct mdbm_dblock {
int db_n; /* number of entries */
struct mdbm_dentry {
unsigned short de_off; /* offset to beginning of text */
unsigned short de_links;/* number of links */
unsigned short de_inx; /* in index */
unsigned short de_outx; /* out index */
unsigned long de_outh; /* out hash */
} db_e[1]; /* actually db_e[db_n], but can't say that */
};
X/* Some macros to simplify(?) things a bit */
X/* Read block blk (size sz offset off) from file f into buffer buf */
#define MDBM_RBLK(f,blk,buf,sz,off) \
((void) lseek (f, (blk)*(sz)+(off), 0), (void) read (f, buf, sz))
X/* Write block blk (size sz offset off) to file f from buffer buf */
#define MDBM_WBLK(f,blk,buf,sz,off) \
((void) lseek (f, (blk)*(sz)+(off), 0), (void) write (f, buf, sz))
X/* Write (if needed) */
#define MDBM_DSYNC(d) \
if ((d) -> mdbm_flags & MDBM_DDIRTY) { \
MDBM_WBLK ((d) -> mdbm_datafd, (d) -> mdbm_dblock, (d) -> mdbm_d, \
(d) -> mdbm_dsize, 0); \
(d) -> mdbm_flags &= ~MDBM_DDIRTY; \
}
#define MDBM_MSYNC(d) \
if ((d) -> mdbm_flags & MDBM_MDIRTY) { \
MDBM_WBLK ((d) -> mdbm_mapfd, (d) -> mdbm_mblock, (d) -> mdbm_m, \
(d) -> mdbm_msize, sizeof (struct mdbm_h)); \
(d) -> mdbm_flags &= ~MDBM_MDIRTY; \
}
#define MDBM_SYNC(d) { MDBM_DSYNC(d); MDBM_MSYNC(d); }
X/* Do autowrites */
#define MDBM_AUTO(d) if ((d) -> mdbm_flags & MDBM_ISAUTOW) MDBM_SYNC (d)
X/* Read data block b */
#define MDBM_DREAD(d,b) \
if ((d) -> mdbm_dblock != (b)) { \
MDBM_DSYNC (d); \
bzero ((d) -> mdbm_d, (d) -> mdbm_dsize); \
MDBM_RBLK ((d) -> mdbm_datafd, (d) -> mdbm_dblock = (b), \
(d) -> mdbm_d, (d) -> mdbm_dsize, 0); \
mdbm_checkblock ((d) -> mdbm_d, (d) -> mdbm_dsize); \
}
X/* Read map block b */
#define MDBM_MREAD(d,b) \
if ((d) -> mdbm_mblock != (b)) { \
MDBM_MSYNC (d); \
bzero ((d) -> mdbm_m, (d) -> mdbm_msize); \
MDBM_RBLK ((d) -> mdbm_mapfd, (d) -> mdbm_mblock = (b), \
(d) -> mdbm_m, (d) -> mdbm_msize, sizeof (struct mdbm_h)); \
}
X/*
* function types
*/
long mdbm_calchash ();
long mdbm_hashinc ();
struct mdbm_dentry *mdbm_search ();
datum mdbm_firsthash ();
long lseek ();
char *malloc ();
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
/bin/chmod 644 mdbm/mdbm_local.h
/bin/echo -n ' '; /bin/ls -ld mdbm/mdbm_local.h
fi
/bin/echo 'Extracting mdbm/nextkey.c'
sed 's/^X//' <<'//go.sysin dd *' >mdbm/nextkey.c
#ifndef lint
static char rcsid[] = "$Header: /ful/chris/dist/mdbm/nextkey.c,v 1.1 84/08/12 10:01:55 chris Rel $";
#endif
#include <stdio.h>
#include "mdbm.h"
#include "mdbm_local.h"
X/*
* Return the "next" key in dbm d
*/
datum mdbm_nextkey (d, key)
register struct mdbm *d;
datum key;
{
#define db ((struct mdbm_dblock *) d -> mdbm_d)
register struct mdbm_dentry *de;
register int i;
char *bp;
int bl;
char *ip;
int il,
found;
long hash,
hmask;
datum rval;
/* Suck in the block for the given hash, then find the key that follows
the one given */
hash = mdbm_calchash (key.dptr, key.dsize);
hmask = mdbm_access (d, hash);
found = 0;
#ifdef lint /* lint doesn't realize that 'found'
overrides the tests on bl and bp */
bl = 0;
bp = 0;
#endif lint
for (i = 0, de = db -> db_e; i < db -> db_n; i++, de++) {
if (de -> de_outx == 0) /* not a key */
continue;
il = (i ? de[-1].de_off : d -> mdbm_dsize) - de -> de_off;
ip = d -> mdbm_d + de -> de_off;
if (il < key.dsize ||
(il == key.dsize && mdbm_compare (ip, key.dptr, il) <= 0))
continue;
if (!found || il < bl || (il == bl && mdbm_compare (ip, bp, il) < 0)) {
bl = il;
bp = ip;
found++;
}
}
if (found) {
bcopy (bp, rval.dptr = d -> mdbm_s, rval.dsize = bl);
return rval;
}
/* No item with this hash, so get next hash and return its first item */
hash = mdbm_hashinc (hash, hmask);
if (hash == 0) { /* no more */
rval.dsize = 0;
rval.dptr = 0;
return rval;
}
return mdbm_firsthash (d, hash);
}
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
/bin/chmod 644 mdbm/nextkey.c
/bin/echo -n ' '; /bin/ls -ld mdbm/nextkey.c
fi
/bin/echo 'Extracting mdbm/open.c'
sed 's/^X//' <<'//go.sysin dd *' >mdbm/open.c
#ifndef lint
static char rcsid[] = "$Header: /ful/chris/dist/mdbm/open.c,v 1.1 84/08/12 10:02:40 chris Rel $";
#endif
#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/file.h>
#include <errno.h>
#include "mdbm.h"
#include "mdbm_local.h"
X/*
* Open or create a database
*/
struct mdbm *mdbm_open (file, flags, mode, adsize, amsize, comment)
char *file;
int flags, mode;
int *adsize, *amsize;
char *comment;
{
register struct mdbm *d;
struct stat stat;
struct mdbm_h mdbm_h;
int dsize,
msize,
l;
char *namebuf,
*p;
char *strcpy ();
char *strncpy ();
extern int errno;
/* get a descriptor */
if ((d = (struct mdbm *) malloc (sizeof *d)) == 0) {
errno = ENOMEM;
return 0;
}
/* get enough room for the file names */
l = strlen (file);
if ((namebuf = malloc ((unsigned) (l + 5))) == 0) {
l = ENOMEM;
goto out;
}
/* find out how big the buffers should be, if this is a new db */
dsize = adsize == 0 || *adsize == 0 ? MDBM_DefaultDataSize : *adsize;
msize = amsize == 0 || *amsize == 0 ? MDBM_DefaultMapSize : *amsize;
if (dsize < MDBM_MinDataSize)
dsize = MDBM_MinDataSize;
if (msize < MDBM_MinMapSize)
msize = MDBM_MinMapSize;
/* fix up the mode, then open them files */
if ((flags & 3) == O_WRONLY)
flags = (flags & ~3) | O_RDWR;
(void) strcpy (namebuf, file);
p = &namebuf[l];
(void) strcpy (p, ".dat");
if ((d -> mdbm_datafd = open (namebuf, flags, mode)) < 0) {
l = errno;
goto out;
}
(void) strcpy (p, ".map");
if ((d -> mdbm_mapfd = open (namebuf, flags, mode)) < 0) {
l = errno;
goto out1;
}
free (namebuf);
/* initialize the dbm descriptor */
d -> mdbm_flags = (flags & 3) == O_RDONLY ? MDBM_ISRONLY : 0;
(void) fstat (d -> mdbm_mapfd, &stat);
if (stat.st_size == 0) {
mdbm_h.mh_dsize = dsize;
mdbm_h.mh_msize = msize;
bzero (mdbm_h.mh_comment, MDBM_CSIZ);
(void) strncpy (mdbm_h.mh_comment,
comment && *comment ? comment : file, MDBM_CSIZ);
mdbm_h.mh_comment[MDBM_CSIZ - 1] = 0;
if ((d -> mdbm_flags & MDBM_ISRONLY) == 0)
if (write (d -> mdbm_mapfd, (char *) & mdbm_h, sizeof mdbm_h) !=
sizeof mdbm_h)
goto out2;
}
else {
if (read (d -> mdbm_mapfd, (char *) & mdbm_h, sizeof mdbm_h) !=
sizeof mdbm_h) {
l = EINVAL;
goto out2;
}
dsize = mdbm_h.mh_dsize;
msize = mdbm_h.mh_msize;
}
if (adsize)
*adsize = dsize;
if (amsize)
*amsize = msize;
if (comment)
(void) strncpy (comment, mdbm_h.mh_comment, MDBM_CSIZ);
if ((d -> mdbm_d = malloc ((unsigned) dsize)) == 0) {
l = ENOMEM;
goto out2;
}
if ((d -> mdbm_s = malloc ((unsigned) dsize)) == 0) {
free (d -> mdbm_d);
l = ENOMEM;
goto out2;
}
if ((d -> mdbm_m = malloc ((unsigned) msize)) == 0) {
free (d -> mdbm_s);
free (d -> mdbm_d);
l = ENOMEM;
goto out2;
}
d -> mdbm_dsize = dsize;
d -> mdbm_msize = msize;
d -> mdbm_maxbit = (stat.st_size - sizeof mdbm_h) * BYTESIZ;
d -> mdbm_dblock = -1;
d -> mdbm_mblock = -1;
return d;
out2:
(void) close (d -> mdbm_datafd);
out1:
(void) close (d -> mdbm_mapfd);
out:
free ((char *) d);
errno = l;
return 0;
}
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
/bin/chmod 644 mdbm/open.c
/bin/echo -n ' '; /bin/ls -ld mdbm/open.c
fi
/bin/echo 'Extracting mdbm/search.c'
sed 's/^X//' <<'//go.sysin dd *' >mdbm/search.c
#ifndef lint
static char rcsid[] = "$Header: /ful/chris/dist/mdbm/search.c,v 1.1 84/08/12 10:03:12 chris Rel $";
#endif
#include <stdio.h>
#include "mdbm.h"
#include "mdbm_local.h"
X/*
* 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.)
*/
struct mdbm_dentry *mdbm_search (d, s, len, ablock, aindex, justkey)
register struct mdbm *d;
char *s;
register int len;
long *ablock;
int *aindex;
int justkey;
{
#define db ((struct mdbm_dblock *) d -> mdbm_d)
register struct mdbm_dentry *de;
register int i;
register unsigned short outx;
long outh;
(void) mdbm_access (d, mdbm_calchash (s, len));
for (i = 0, de = db -> db_e; i < db -> db_n; i++, de++) {
if (de -> de_outx == 0) /* not a key */
continue;
if (len == (i ? de[-1].de_off : d -> mdbm_dsize) - de -> de_off)
if (bcmp (s, d -> mdbm_d + de -> de_off, len) == 0)
goto found;
}
return 0;
found:
if (ablock)
*ablock = d -> mdbm_dblock;
if (aindex)
*aindex = i;
if (justkey)
return de;
outx = de -> de_outx;
(void) mdbm_access (d, outh = de -> de_outh);
for (i = 0, de = db -> db_e; i < db -> db_n; i++, de++)
if (de -> de_inx == outx)
return de;
printf ("mdbm bug: no datum for key (%d, %d)\n", outh, outx);
return 0;
}
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
/bin/chmod 644 mdbm/search.c
/bin/echo -n ' '; /bin/ls -ld mdbm/search.c
fi
/bin/echo 'Extracting mdbm/store.c'
sed 's/^X//' <<'//go.sysin dd *' >mdbm/store.c
#ifndef lint
static char rcsid[] = "$Header: /ful/chris/dist/mdbm/store.c,v 1.1 84/08/12 10:03:37 chris Rel $";
#endif
#include <stdio.h>
#include <errno.h>
#include "mdbm.h"
#include "mdbm_local.h"
X/*
* Exhaustively search for a valid inx index number for the new entry
* in d. We "guarantee" that one such will be available. (Used by
* mdbm_dostore)
*/
static unsigned short mdbm_inx (d)
register struct mdbm *d;
{
#define db ((struct mdbm_dblock *) d -> mdbm_d)
register struct mdbm_dentry *de;
register int i,
n = db -> db_n - 1;
register unsigned short inx = 1;
for (;;) {
de = db -> db_e;
i = n;
while (--i >= 0) {
if (de -> de_inx == inx)
goto nope;
de++;
}
return inx;
nope:
if (inx == MAXUSHORT)
break;
inx++;
}
printf ("mdbm bug: no inx's available (can't happen)\n");
abort ();
return 1;
#undef db
}
X/*
* 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 struct mdbm_dentry *mdbm_additem (buf, dsize, len)
register char *buf;
int dsize, len;
{
#define db ((struct mdbm_dblock *) buf)
register struct mdbm_dentry *de;
register int i = db -> db_n;
/* 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. */
de = &db -> db_e[i];
i = (i ? de[-1].de_off : dsize) - len;
if (buf + i < (char *) &de[1])
return 0;
db -> db_n++;
de -> de_off = i;
return de;
#undef db
}
X/*
* 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 mdbm_store)
*/
static struct mdbm_dentry *mdbm_dostore (d, s, len, ahash, asplit)
register struct mdbm *d;
char *s;
int len;
long *ahash;
long *asplit;
{
#define db ((struct mdbm_dblock *) d -> mdbm_d)
register struct mdbm_dentry *de;
register int i;
long hash;
long hmask;
long IfSplit;
unsigned int minx = MAXUSHORT,
maxx = 0;
hash = mdbm_calchash (s, len);
if (ahash)
*ahash = hash;
if (asplit) {
IfSplit = *asplit;
*asplit = 0;
}
loop:
{
register int rlen = len;
hmask = mdbm_access (d, hash);
for (i = 0, de = db -> db_e; i < db -> db_n; i++, de++) {
if (rlen == (i ? de[-1].de_off : d -> mdbm_dsize) - de -> de_off)
if (bcmp (s, d -> mdbm_d + de -> de_off, rlen) == 0) {
de -> de_links++;
goto returnit;
}
if (de -> de_inx < minx)
minx = de -> de_inx;
if (de -> de_inx > maxx)
maxx = de -> de_inx;
}
de = mdbm_additem (d -> mdbm_d, d -> mdbm_dsize, rlen);
}
if (de) {
de -> de_links = 1; /* will be either a key or a datum */
de -> de_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
yeild results, we perform an exhaustive search. Hopefully the
searches are rare. */
if (i == 0)
de -> de_inx = 1; /* first one, special case */
else if (minx < MAXUSHORT && minx > 1)
de -> de_inx = minx - 1;
else if (maxx && maxx < MAXUSHORT)
de -> de_inx = maxx + 1;
else
de -> de_inx = mdbm_inx (d);
bcopy (s, d -> mdbm_d + de -> de_off, len);
returnit:
d -> mdbm_flags |= MDBM_DDIRTY;
return de;
}
/* 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 *db > d -> mdbm_dsize)
return 0; /* hopeless! */
/* If we are splitting the "interesting" block, make a note of that fact */
if (asplit && IfSplit == d -> mdbm_dblock)
*asplit = 1;
bzero (d -> mdbm_s, d -> mdbm_dsize);
hmask++;
for (i = 0, de = db -> db_e; i < db -> db_n;) {
register int l;
register char *p = d -> mdbm_d + de -> de_off;
l = (i ? de[-1].de_off : d -> mdbm_dsize) - de -> de_off;
if (mdbm_calchash (p, l) & hmask) {
register struct mdbm_dentry *nde;
nde = mdbm_additem (d -> mdbm_s, d -> mdbm_dsize, l);
bcopy (p, d -> mdbm_s + nde -> de_off, l);
nde -> de_links = de -> de_links;
nde -> de_inx = de -> de_inx;
nde -> de_outx = de -> de_outx;
nde -> de_outh = de -> de_outh;
de -> de_links = 1; /* force mdbm_delitem to remove it */
mdbm_delitem (d, de - db -> db_e);
}
else
i++, de++;
}
MDBM_WBLK (d -> mdbm_datafd, d -> mdbm_dblock + hmask, d -> mdbm_s,
d -> mdbm_dsize, 0);
d -> mdbm_flags |= MDBM_DDIRTY;
hmask--;
/* Now mark the block as having been split by setting the appropriate bit in
the map. */
{
register long bit = (hash & hmask) + hmask;
register int n;
register long bn;
n = bit % BYTESIZ; /* bit index */
bn = bit / BYTESIZ; /* byte index */
i = bn % d -> mdbm_msize;/* byte offset in block */
if (bit >= d -> mdbm_maxbit) {
d -> mdbm_maxbit = bit + 1;
bn /= d -> mdbm_msize;/* map block number */
MDBM_MREAD (d, bn); /* read will probably fail, but this fills
in the block numbers and so forth */
}
d -> mdbm_m[i] |= 1 << n;/* set the bit */
d -> mdbm_flags |= MDBM_MDIRTY;
}
goto loop;
#undef db
}
X/*
* Store dat as datum of key key in dbm d
*/
mdbm_store (d, key, dat, replace)
register struct mdbm *d;
datum key, dat;
int replace; /* true => overwrite if exists */
{
#define db ((struct mdbm_dblock *) d -> mdbm_d)
register struct mdbm_dentry *de;
long keyblock;
int keyindex;
long didsplit;
long outh;
unsigned short outx;
extern int errno;
if (d -> mdbm_flags & MDBM_ISRONLY) {
errno = EPERM;
return (-1);
}
/* 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 precede
as before. */
de = mdbm_search (d, key.dptr, key.dsize, &keyblock, &keyindex, 0);
if (de) {
if (!replace)
return 1;
mdbm_delitem (d, de - db -> db_e);
/* now committed - if new datum doesn't fit, old pairing is gone! */
}
else { /* create new key */
de = mdbm_dostore (d, key.dptr, key.dsize, (long *) 0, (long *) 0);
if (de == 0) {
MDBM_AUTO (d);
errno = ENOSPC; /* presumably */
return (-1);
}
de -> de_outx = 1; /* force it to look like a key */
keyblock = d -> mdbm_dblock;
keyindex = de - db -> db_e;
}
didsplit = keyblock;
de = mdbm_dostore (d, dat.dptr, dat.dsize, &outh, &didsplit);
if (de)
outx = de -> de_inx;
/* if the data store split the key's block, have to find the key again */
if (didsplit)
if (mdbm_search (d, key.dptr, key.dsize, &keyblock,
&keyindex, 1) == 0) {
printf ("mdbm bug: post-split keysearch failed!\n");
abort ();
}
if (!de) { /* oops, go delete the key */
MDBM_DREAD (d, keyblock);
de = &db -> db_e[keyindex];
de -> de_outx = 0; /* not a key anymore */
mdbm_delitem (d, keyindex);
MDBM_AUTO (d);
errno = ENOSPC;
return (-1);
}
/* Replace the outx and outh numbers in the old (or new) key so that it
points to the new datum */
MDBM_DREAD (d, keyblock);
de = &db -> db_e[keyindex];
de -> de_outh = outh;
de -> de_outx = outx;
d -> mdbm_flags |= MDBM_DDIRTY;
MDBM_AUTO (d);
return 0;
#undef db
}
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
/bin/chmod 644 mdbm/store.c
/bin/echo -n ' '; /bin/ls -ld mdbm/store.c
fi
/bin/echo 'Extracting mdbm/sync.c'
sed 's/^X//' <<'//go.sysin dd *' >mdbm/sync.c
#ifndef lint
static char rcsid[] = "$Header: /ful/chris/dist/mdbm/sync.c,v 1.1 84/08/12 10:04:03 chris Rel $";
#endif
#include <stdio.h>
#include "mdbm.h"
#include "mdbm_local.h"
X/*
* Sync the file attached to dbm d
*/
mdbm_sync (d)
register struct mdbm *d;
{
MDBM_SYNC (d);
(void) fsync (d -> mdbm_datafd);
(void) fsync (d -> mdbm_mapfd);
}
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
/bin/chmod 644 mdbm/sync.c
/bin/echo -n ' '; /bin/ls -ld mdbm/sync.c
fi
/bin/echo 'Extracting mdbm/testdbm.c'
sed 's/^X//' <<'//go.sysin dd *' >mdbm/testdbm.c
#ifndef lint
static char rcsid[] = "$Header: /ful/chris/dist/mdbm/testdbm.c,v 1.1 84/08/12 10:04:23 chris Rel $";
#endif lint
X/*
* testdbm - test the new multiple key database library
*/
#include <stdio.h>
#include <sys/types.h>
#include <sys/file.h>
#include <ctype.h>
#include "mdbm.h"
struct mdbm *mp;
#define NAV 10
struct stringarg {
int s_len;
char *s_str;
} av[NAV];
int c_open (), c_close (), c_fetch (), c_insert (), c_replace ();
int c_delete (), c_list (), c_quit (), c_sync ();
struct cmd {
char *c_name;
int (*c_func)();
int c_args;
} cmds[] = {
"open", c_open, 2,
"open", c_open, 4,
"open", c_open, 5,
"close", c_close, 1,
"fetch", c_fetch, 2,
"get", c_fetch, 2,
"insert", c_insert, 3,
"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
};
char serrbuf[BUFSIZ];
#define checkdb() \
if (!mp) { \
fprintf (stderr, "no database active\n"); \
return; \
} \
else
main () {
char cmdbuf[BUFSIZ];
setbuf (stderr, serrbuf);
for (;;) {
fflush (stderr);
printf ("testdbm> ");
fflush (stdout);
if (fgets (cmdbuf, sizeof cmdbuf, stdin) == NULL) {
putchar ('\n');
c_quit (0);
}
if (doit (cmdbuf))
printf ("Eh?\n");
}
}
doit (s)
char *s;
{
register int argc = parse (s);
register 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;
if (strncmp (cp -> c_name, av[0].s_str, av[0].s_len) == 0) {
(*cp -> c_func) (argc);
return 0;
}
}
return 1;
}
c_open (argc) {
int dsize, msize;
static char comment[MDBM_CSIZ];
if (mp)
(void) mdbm_close (mp);
if (argc == 5)
strncpy (comment, av[4].s_str, sizeof comment);
else
*comment = 0;
if (argc >= 4) {
dsize = atoi (av[2].s_str);
msize = atoi (av[3].s_str);
}
else
dsize = msize = 0;
mp = mdbm_open (av[1].s_str, O_RDWR|O_CREAT, 0666, &dsize, &msize, comment);
if (mp == 0) {
fprintf (stderr, "can't open ");
perror (av[1].s_str);
return;
}
comment[sizeof comment - 1] = 0;
printf ("opened %s - dsize %d, msize %d, comment %s\n",
av[1].s_str, dsize, msize, comment);
}
c_close (argc) {
if (mp)
(void) mdbm_close (mp);
mp = 0;
}
c_fetch (argc) {
datum key, dat;
checkdb ();
key.dptr = av[1].s_str;
key.dsize = av[1].s_len;
dat = mdbm_fetch (mp, key);
prdatum (key);
printf (": ");
if (dat.dptr == 0)
printf ("not found");
else
prdatum (dat);
putchar ('\n');
}
prdatum (d)
datum d;
{
register char *p;
register int c;
register int i;
i = d.dsize;
p = d.dptr;
while (--i >= 0) {
c = *p++ & 0377;
if (c & 0200) {
putchar ('M'), putchar ('-');
c &= 0177;
}
if (c == 0177 || c < ' ') {
putchar ('^');
if (c == 0177)
putchar ('?');
else
putchar (c + '@');
}
else
putchar (c);
}
}
c_insert (argc) {
datum key, dat;
int e;
checkdb ();
key.dptr = av[1].s_str;
key.dsize = av[1].s_len;
dat.dptr = av[2].s_str;
dat.dsize = av[2].s_len;
e = mdbm_store (mp, key, dat, MDBM_INSERT);
if (e == 0)
return;
if (e < 0)
perror ("store failed");
else
fprintf (stderr, "insert failed, key in use\n");
}
c_replace (argc) {
datum key, dat;
int e;
checkdb ();
key.dptr = av[1].s_str;
key.dsize = av[1].s_len;
dat.dptr = av[2].s_str;
dat.dsize = av[2].s_len;
if (mdbm_store (mp, key, dat, MDBM_REPLACE))
perror ("store failed");
}
c_delete (argc) {
datum key;
checkdb ();
key.dptr = av[1].s_str;
key.dsize = av[1].s_len;
if (mdbm_delete (mp, key))
perror ("delete failed");
}
c_list () {
datum key, dat;
checkdb ();
for (key = mdbm_firstkey (mp); key.dptr; key = mdbm_nextkey (mp, key)) {
dat = mdbm_fetch (mp, key);
prdatum (key);
printf (": ");
if (dat.dptr == 0)
printf ("datum not found!");
else
prdatum (dat);
putchar ('\n');
}
}
c_quit () {
if (mp)
(void) mdbm_close (mp);
exit (0);
}
c_sync () {
checkdb ();
mdbm_sync (mp);
}
parse (s)
register char *s;
{
register struct stringarg *ap;
register int aleft;
register int qu = 0;
register char *cp;
register int c;
static char xbuf[BUFSIZ];
char *malloc ();
for (ap = av, aleft = NAV; --aleft >= 0; ap++)
if (ap -> s_str) {
free (ap -> s_str);
ap -> s_str = 0;
}
ap = av;
aleft = NAV;
while (*s) {
while (isspace (*s))
s++;
if (!*s)
break;
qu = 0;
cp = xbuf;
while (((c = *s) != 0) && (qu || !isspace (c))) {
s++;
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;
}
*cp++ = 0;
if (--aleft < 0) {
fprintf (stderr, "too many argv's\n");
return 0;
}
ap -> s_str = malloc (cp - xbuf);
ap -> s_len = cp - xbuf;
bcopy (xbuf, ap -> s_str, ap -> s_len);
ap -> s_len--; /* stop counting trailing \0 */
ap++;
}
return NAV - aleft;
}
//go.sysin dd *
made=TRUE
if [ $made = TRUE ]; then
/bin/chmod 644 mdbm/testdbm.c
/bin/echo -n ' '; /bin/ls -ld mdbm/testdbm.c
fi
made=TRUE
if [ $made = TRUE ]; then
/bin/chmod 755 mdbm
/bin/echo -n ' '; /bin/ls -ld mdbm
fi
More information about the Comp.sources.unix
mailing list