sdbm part 1
Ozan Yigit
oz at nexus.YorkU.CA
Sun Dec 16 02:37:53 AEST 1990
#! /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 1 (of 2)."
# Contents: dist dist/CHANGES dist/COMPARE dist/biblio dist/dba.c
# dist/dbd.c dist/dbe.1 dist/dbe.c dist/dbm.c dist/dbm.h dist/dbu.c
# dist/hash.c dist/makefile dist/pair.c dist/pair.h dist/sdbm.3
# dist/sdbm.h dist/tune.h dist/util.c
# Wrapped by oz at yunexus on Sat Dec 15 10:24:19 1990
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test ! -d 'dist' ; then
echo shar: Creating directory \"'dist'\"
mkdir 'dist'
fi
if test -f 'dist/CHANGES' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'dist/CHANGES'\"
else
echo shar: Extracting \"'dist/CHANGES'\" \(900 characters\)
sed "s/^X//" >'dist/CHANGES' <<'END_OF_FILE'
XChanges from the earlier BETA releases.
X
Xo dbm_prep does everything now, so dbm_open is just a simple
X wrapper that builds the default filenames. dbm_prep no longer
X requires a (DBM *) db parameter: it allocates one itself. It
X returns (DBM *) db or (DBM *) NULL.
X
Xo makroom is now reliable. In the common-case optimization of the page
X split, the page into which the incoming key/value pair is to be inserted
X is write-deferred (if the split is successful), thereby saving a cosly
X write. BUT, if the split does not make enough room (unsuccessful), the
X deferred page is written out, as the failure-window is now dependent on
X the number of split attempts.
X
Xo if -DDUFF is defined, hash function will also use the DUFF construct.
X This may look like a micro-performance tweak (maybe it is), but in fact,
X the hash function is the third most-heavily used function, after read
X and write.
END_OF_FILE
if test 900 -ne `wc -c <'dist/CHANGES'`; then
echo shar: \"'dist/CHANGES'\" unpacked with wrong size!
fi
# end of 'dist/CHANGES'
fi
if test -f 'dist/COMPARE' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'dist/COMPARE'\"
else
echo shar: Extracting \"'dist/COMPARE'\" \(2832 characters\)
sed "s/^X//" >'dist/COMPARE' <<'END_OF_FILE'
X
XScript started on Thu Sep 28 15:41:06 1989
X% uname -a
Xtitan titan 4_0 UMIPS mips
X% make all x-dbm
X cc -O -DSDBM -DDUFF -DDUPERROR -DSPLITFAIL -c dbm.c
X cc -O -DSDBM -DDUFF -DDUPERROR -DSPLITFAIL -c sdbm.c
X cc -O -DSDBM -DDUFF -DDUPERROR -DSPLITFAIL -c pair.c
X cc -O -DSDBM -DDUFF -DDUPERROR -DSPLITFAIL -c hash.c
X ar cr libsdbm.a sdbm.o pair.o hash.o
X ranlib libsdbm.a
X cc -o dbm dbm.o libsdbm.a
X cc -O -DSDBM -DDUFF -DDUPERROR -DSPLITFAIL -c dba.c
X cc -o dba dba.o
X cc -O -DSDBM -DDUFF -DDUPERROR -DSPLITFAIL -c dbd.c
X cc -o dbd dbd.o
X cc -O -DSDBM -DDUFF -DDUPERROR -DSPLITFAIL -o x-dbm dbm.o
X%
X%
X% wc history
X 65110 218344 3204883 history
X%
X% /bin/time dbm build foo <history
X
Xreal 5:56.9
Xuser 13.3
Xsys 26.3
X% ls -s
Xtotal 14251
X 5 README 2 dbd.c 1 hash.c 1 pair.h
X 0 SCRIPT 5 dbd.o 1 hash.o 5 pair.o
X 1 WISHLIST 62 dbm 3130 history 1 port.h
X 46 dba 5 dbm.c 11 howtodbm.txt 11 sdbm.c
X 3 dba.c 8 dbm.o 14 libsdbm.a 2 sdbm.h
X 6 dba.o 4 foo.dir 1 makefile 8 sdbm.o
X 46 dbd 10810 foo.pag 6 pair.c 60 x-dbm
X% ls -l foo.*
X-rw-r--r-- 1 oz 4096 Sep 28 15:48 foo.dir
X-rw-r--r-- 1 oz 11069440 Sep 28 15:48 foo.pag
X%
X% /bin/time x-dbm build bar <history
X
Xreal 5:59.4
Xuser 24.7
Xsys 29.1
X%
X% ls -s
Xtotal 27612
X 5 README 46 dbd 1 hash.c 5 pair.o
X 1 SCRIPT 2 dbd.c 1 hash.o 1 port.h
X 1 WISHLIST 5 dbd.o 3130 history 11 sdbm.c
X 4 bar.dir 62 dbm 11 howtodbm.txt 2 sdbm.h
X13356 bar.pag 5 dbm.c 14 libsdbm.a 8 sdbm.o
X 46 dba 8 dbm.o 1 makefile 60 x-dbm
X 3 dba.c 4 foo.dir 6 pair.c
X 6 dba.o 10810 foo.pag 1 pair.h
X%
X% ls -l bar.*
X-rw-r--r-- 1 oz 4096 Sep 28 15:54 bar.dir
X-rw-r--r-- 1 oz 13676544 Sep 28 15:54 bar.pag
X%
X% dba foo | tail
X#10801: ok. no entries.
X#10802: ok. no entries.
X#10803: ok. no entries.
X#10804: ok. no entries.
X#10805: ok. no entries.
X#10806: ok. no entries.
X#10807: ok. no entries.
X#10808: ok. no entries.
X#10809: ok. 11 entries 67% used free 337.
X10810 pages (6036 holes): 65073 entries
X%
X% dba bar | tail
X#13347: ok. no entries.
X#13348: ok. no entries.
X#13349: ok. no entries.
X#13350: ok. no entries.
X#13351: ok. no entries.
X#13352: ok. no entries.
X#13353: ok. no entries.
X#13354: ok. no entries.
X#13355: ok. 7 entries 33% used free 676.
X13356 pages (8643 holes): 65073 entries
X%
X% exit
Xscript done on Thu Sep 28 16:08:45 1989
X
END_OF_FILE
if test 2832 -ne `wc -c <'dist/COMPARE'`; then
echo shar: \"'dist/COMPARE'\" unpacked with wrong size!
fi
# end of 'dist/COMPARE'
fi
if test -f 'dist/biblio' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'dist/biblio'\"
else
echo shar: Extracting \"'dist/biblio'\" \(1012 characters\)
sed "s/^X//" >'dist/biblio' <<'END_OF_FILE'
X%A R. J. Enbody
X%A H. C. Du
X%T Dynamic Hashing Schemes
X%J ACM Computing Surveys
X%V 20
X%N 2
X%D June 1988
X%P 85-113
X%K surveys
X
X%A P.-A. Larson
X%T Dynamic Hashing
X%J BIT
X%V 18
X%P 184-201
X%D 1978
X%K dynamic
X
X%A W. Litwin
X%T Linear Hashing: A new tool for file and table addressing
X%J Proceedings of the 6th Conference on Very Large Dabatases (Montreal)
X%I Very Large Database Foundation
X%C Saratoga, Calif.
X%P 212-223
X%D 1980
X%K linear
X
X%A R. Fagin
X%A J. Nievergelt
X%A N. Pippinger
X%A H. R. Strong
X%T Extendible Hashing - A Fast Access Method for Dynamic Files
X%J ACM Trans. Database Syst.
X%V 4
X%N 3
X%D Sept. 1979
X%P 315-344
X%K extend
X
X%A G. N. Martin
X%T Spiral Storage: Incrementally Augmentable Hash Addressed Storage
X%J Technical Report #27
X%I University of Varwick
X%C Coventry, U.K.
X%D 1979
X%K spiral
X
X%A Chris Torek
X%T Re: dbm.a and ndbm.a archives
X%B USENET newsgroup comp.unix
X%D 1987
X%K torek
X
X%A Rich Wales
X%T Discusson of "dbm" data base system
X%B USENET newsgroup unix.wizards
X%D Jan. 1984
X%K rich
X
X
X
X
X
X
END_OF_FILE
if test 1012 -ne `wc -c <'dist/biblio'`; then
echo shar: \"'dist/biblio'\" unpacked with wrong size!
fi
# end of 'dist/biblio'
fi
if test -f 'dist/dba.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'dist/dba.c'\"
else
echo shar: Extracting \"'dist/dba.c'\" \(1273 characters\)
sed "s/^X//" >'dist/dba.c' <<'END_OF_FILE'
X/*
X * dba dbm analysis/recovery
X */
X
X#include <stdio.h>
X#include <sys/file.h>
X#include "sdbm.h"
X
Xchar *progname;
Xextern void oops();
X
Xint
Xmain(argc, argv)
Xchar **argv;
X{
X int n;
X char *p;
X char *name;
X int pagf;
X
X progname = argv[0];
X
X if (p = argv[1]) {
X name = (char *) malloc((n = strlen(p)) + 5);
X strcpy(name, p);
X strcpy(name + n, ".pag");
X
X if ((pagf = open(name, O_RDONLY)) < 0)
X oops("cannot open %s.", name);
X
X sdump(pagf);
X }
X else
X oops("usage: %s dbname", progname);
X
X return 0;
X}
X
Xsdump(pagf)
Xint pagf;
X{
X register b;
X register n = 0;
X register t = 0;
X register o = 0;
X register e;
X char pag[PBLKSIZ];
X
X while ((b = read(pagf, pag, PBLKSIZ)) > 0) {
X printf("#%d: ", n);
X if (!okpage(pag))
X printf("bad\n");
X else {
X printf("ok. ");
X if (!(e = pagestat(pag)))
X o++;
X else
X t += e;
X }
X n++;
X }
X
X if (b == 0)
X printf("%d pages (%d holes): %d entries\n", n, o, t);
X else
X oops("read failed: block %d", n);
X}
X
Xpagestat(pag)
Xchar *pag;
X{
X register n;
X register free;
X register short *ino = (short *) pag;
X
X if (!(n = ino[0]))
X printf("no entries.\n");
X else {
X free = ino[n] - (n + 1) * sizeof(short);
X printf("%3d entries %2d%% used free %d.\n",
X n / 2, ((PBLKSIZ - free) * 100) / PBLKSIZ, free);
X }
X return n / 2;
X}
END_OF_FILE
if test 1273 -ne `wc -c <'dist/dba.c'`; then
echo shar: \"'dist/dba.c'\" unpacked with wrong size!
fi
# end of 'dist/dba.c'
fi
if test -f 'dist/dbd.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'dist/dbd.c'\"
else
echo shar: Extracting \"'dist/dbd.c'\" \(1719 characters\)
sed "s/^X//" >'dist/dbd.c' <<'END_OF_FILE'
X/*
X * dbd - dump a dbm data file
X */
X
X#include <stdio.h>
X#include <sys/file.h>
X#include "sdbm.h"
X
Xchar *progname;
Xextern void oops();
X
X
X#define empty(page) (((short *) page)[0] == 0)
X
Xint
Xmain(argc, argv)
Xchar **argv;
X{
X int n;
X char *p;
X char *name;
X int pagf;
X
X progname = argv[0];
X
X if (p = argv[1]) {
X name = (char *) malloc((n = strlen(p)) + 5);
X strcpy(name, p);
X strcpy(name + n, ".pag");
X
X if ((pagf = open(name, O_RDONLY)) < 0)
X oops("cannot open %s.", name);
X
X sdump(pagf);
X }
X else
X oops("usage: %s dbname", progname);
X return 0;
X}
X
Xsdump(pagf)
Xint pagf;
X{
X register r;
X register n = 0;
X register o = 0;
X char pag[PBLKSIZ];
X
X while ((r = read(pagf, pag, PBLKSIZ)) > 0) {
X if (!okpage(pag))
X fprintf(stderr, "%d: bad page.\n", n);
X else if (empty(pag))
X o++;
X else
X dispage(pag);
X n++;
X }
X
X if (r == 0)
X fprintf(stderr, "%d pages (%d holes).\n", n, o);
X else
X oops("read failed: block %d", n);
X}
X
X
X#ifdef OLD
Xdispage(pag)
Xchar *pag;
X{
X register i, n;
X register off;
X register short *ino = (short *) pag;
X
X off = PBLKSIZ;
X for (i = 1; i < ino[0]; i += 2) {
X printf("\t[%d]: ", ino[i]);
X for (n = ino[i]; n < off; n++)
X putchar(pag[n]);
X putchar(' ');
X off = ino[i];
X printf("[%d]: ", ino[i + 1]);
X for (n = ino[i + 1]; n < off; n++)
X putchar(pag[n]);
X off = ino[i + 1];
X putchar('\n');
X }
X}
X#else
Xdispage(pag)
Xchar *pag;
X{
X register i, n;
X register off;
X register short *ino = (short *) pag;
X
X off = PBLKSIZ;
X for (i = 1; i < ino[0]; i += 2) {
X for (n = ino[i]; n < off; n++)
X if (pag[n] != 0)
X putchar(pag[n]);
X putchar('\t');
X off = ino[i];
X for (n = ino[i + 1]; n < off; n++)
X if (pag[n] != 0)
X putchar(pag[n]);
X putchar('\n');
X off = ino[i + 1];
X }
X}
X#endif
END_OF_FILE
if test 1719 -ne `wc -c <'dist/dbd.c'`; then
echo shar: \"'dist/dbd.c'\" unpacked with wrong size!
fi
# end of 'dist/dbd.c'
fi
if test -f 'dist/dbe.1' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'dist/dbe.1'\"
else
echo shar: Extracting \"'dist/dbe.1'\" \(1454 characters\)
sed "s/^X//" >'dist/dbe.1' <<'END_OF_FILE'
X.TH dbe 1 "ndbm(3) EDITOR"
X.SH NAME
Xdbe \- Edit a ndbm(3) database
X.SH USAGE
Xdbe <database> [-m r|w|rw] [-crtvx] -a|-d|-f|-F|-s [<key> [<content>]]
X.SH DESCRIPTION
X\fIdbme\fP operates on ndbm(3) databases.
XIt can be used to create them, look at them or change them.
XWhen specifying the value of a key or the content of its associated entry,
X\\nnn, \\0, \\n, \\t, \\f and \\r are interpreted as usual.
XWhen displaying key/content pairs, non-printable characters are displayed
Xusing the \\nnn notation.
X.SH OPTIONS
X.IP -a
XList all entries in the database.
X.IP -c
XCreate the database if it does not exist.
X.IP -d
XDelete the entry associated with the specified key.
X.IP -f
XFetch and display the entry associated with the specified key.
X.IP -F
XFetch and display all the entries whose key match the specified
Xregular-expression
X.IP "-m r|w|rw"
XOpen the database in read-only, write-only or read-write mode
X.IP -r
XReplace the entry associated with the specified key if it already exists.
XSee option -s.
X.IP -s
XStore an entry under a specific key.
XAn error occurs if the key already exists and the option -r was not specified.
X.IP -t
XRe-initialize the database before executing the command.
X.IP -v
XVerbose mode.
XConfirm stores and deletions.
X.IP -x
XIf option -x is used with option -c, then if the database already exists,
Xan error occurs.
XThis can be used to implement a simple exclusive access locking mechanism.
X.SH SEE ALSO
Xndbm(3)
X.SH AUTHOR
Xjanick at bnr.ca
X
END_OF_FILE
if test 1454 -ne `wc -c <'dist/dbe.1'`; then
echo shar: \"'dist/dbe.1'\" unpacked with wrong size!
fi
# end of 'dist/dbe.1'
fi
if test -f 'dist/dbe.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'dist/dbe.c'\"
else
echo shar: Extracting \"'dist/dbe.c'\" \(9799 characters\)
sed "s/^X//" >'dist/dbe.c' <<'END_OF_FILE'
X#include <stdio.h>
X#ifndef VMS
X#include <sys/file.h>
X#include <ndbm.h>
X#else
X#include "file.h"
X#include "ndbm.h"
X#endif
X#include <ctype.h>
X
X/***************************************************************************\
X** **
X** Function name: getopt() **
X** Author: Henry Spencer, UofT **
X** Coding date: 84/04/28 **
X** **
X** Description: **
X** **
X** Parses argv[] for arguments. **
X** Works with Whitesmith's C compiler. **
X** **
X** Inputs - The number of arguments **
X** - The base address of the array of arguments **
X** - A string listing the valid options (':' indicates an **
X** argument to the preceding option is required, a ';' **
X** indicates an argument to the preceding option is optional) **
X** **
X** Outputs - Returns the next option character, **
X** '?' for non '-' arguments **
X** or ':' when there is no more arguments. **
X** **
X** Side Effects + The argument to an option is pointed to by 'optarg' **
X** **
X*****************************************************************************
X** **
X** REVISION HISTORY: **
X** **
X** DATE NAME DESCRIPTION **
X** YY/MM/DD ------------------ ------------------------------------ **
X** 88/10/20 Janick Bergeron Returns '?' on unamed arguments **
X** returns '!' on unknown options **
X** and 'EOF' only when exhausted. **
X** 88/11/18 Janick Bergeron Return ':' when no more arguments **
X** 89/08/11 Janick Bergeron Optional optarg when ';' in optstring **
X** **
X\***************************************************************************/
X
Xchar *optarg; /* Global argument pointer. */
X
X#ifdef VMS
X#define index strchr
X#endif
X
Xchar
Xgetopt(argc, argv, optstring)
Xint argc;
Xchar **argv;
Xchar *optstring;
X{
X register int c;
X register char *place;
X extern char *index();
X static int optind = 0;
X static char *scan = NULL;
X
X optarg = NULL;
X
X if (scan == NULL || *scan == '\0') {
X
X if (optind == 0)
X optind++;
X if (optind >= argc)
X return ':';
X
X optarg = place = argv[optind++];
X if (place[0] != '-' || place[1] == '\0')
X return '?';
X if (place[1] == '-' && place[2] == '\0')
X return '?';
X scan = place + 1;
X }
X
X c = *scan++;
X place = index(optstring, c);
X if (place == NULL || c == ':' || c == ';') {
X
X (void) fprintf(stderr, "%s: unknown option %c\n", argv[0], c);
X scan = NULL;
X return '!';
X }
X if (*++place == ':') {
X
X if (*scan != '\0') {
X
X optarg = scan;
X scan = NULL;
X
X }
X else {
X
X if (optind >= argc) {
X
X (void) fprintf(stderr, "%s: %c requires an argument\n",
X argv[0], c);
X return '!';
X }
X optarg = argv[optind];
X optind++;
X }
X }
X else if (*place == ';') {
X
X if (*scan != '\0') {
X
X optarg = scan;
X scan = NULL;
X
X }
X else {
X
X if (optind >= argc || *argv[optind] == '-')
X optarg = NULL;
X else {
X optarg = argv[optind];
X optind++;
X }
X }
X }
X return c;
X}
X
X
Xvoid
Xprint_datum(db)
Xdatum db;
X{
X int i;
X
X putchar('"');
X for (i = 0; i < db.dsize; i++) {
X if (isprint(db.dptr[i]))
X putchar(db.dptr[i]);
X else {
X putchar('\\');
X putchar('0' + ((db.dptr[i] >> 6) & 0x07));
X putchar('0' + ((db.dptr[i] >> 3) & 0x07));
X putchar('0' + (db.dptr[i] & 0x07));
X }
X }
X putchar('"');
X}
X
X
Xdatum
Xread_datum(s)
Xchar *s;
X{
X datum db;
X char *p;
X int i;
X
X db.dsize = 0;
X db.dptr = (char *) malloc(strlen(s) * sizeof(char));
X for (p = db.dptr; *s != '\0'; p++, db.dsize++, s++) {
X if (*s == '\\') {
X if (*++s == 'n')
X *p = '\n';
X else if (*s == 'r')
X *p = '\r';
X else if (*s == 'f')
X *p = '\f';
X else if (*s == 't')
X *p = '\t';
X else if (isdigit(*s) && isdigit(*(s + 1)) && isdigit(*(s + 2))) {
X i = (*s++ - '0') << 6;
X i |= (*s++ - '0') << 3;
X i |= *s - '0';
X *p = i;
X }
X else if (*s == '0')
X *p = '\0';
X else
X *p = *s;
X }
X else
X *p = *s;
X }
X
X return db;
X}
X
X
Xchar *
Xkey2s(db)
Xdatum db;
X{
X char *buf;
X char *p1, *p2;
X
X buf = (char *) malloc((db.dsize + 1) * sizeof(char));
X for (p1 = buf, p2 = db.dptr; *p2 != '\0'; *p1++ = *p2++);
X *p1 = '\0';
X return buf;
X}
X
X
Xmain(argc, argv)
Xint argc;
Xchar **argv;
X{
X typedef enum {
X YOW, FETCH, STORE, DELETE, SCAN, REGEXP
X } commands;
X char opt;
X int flags;
X int giveusage = 0;
X int verbose = 0;
X commands what = YOW;
X char *comarg[3];
X int st_flag = DBM_INSERT;
X int argn;
X DBM *db;
X datum key;
X datum content;
X
X flags = O_RDWR;
X argn = 0;
X
X while ((opt = getopt(argc, argv, "acdfFm:rstvx")) != ':') {
X switch (opt) {
X case 'a':
X what = SCAN;
X break;
X case 'c':
X flags |= O_CREAT;
X break;
X case 'd':
X what = DELETE;
X break;
X case 'f':
X what = FETCH;
X break;
X case 'F':
X what = REGEXP;
X break;
X case 'm':
X flags &= ~(000007);
X if (strcmp(optarg, "r") == 0)
X flags |= O_RDONLY;
X else if (strcmp(optarg, "w") == 0)
X flags |= O_WRONLY;
X else if (strcmp(optarg, "rw") == 0)
X flags |= O_RDWR;
X else {
X fprintf(stderr, "Invalid mode: \"%s\"\n", optarg);
X giveusage = 1;
X }
X break;
X case 'r':
X st_flag = DBM_REPLACE;
X break;
X case 's':
X what = STORE;
X break;
X case 't':
X flags |= O_TRUNC;
X break;
X case 'v':
X verbose = 1;
X break;
X case 'x':
X flags |= O_EXCL;
X break;
X case '!':
X giveusage = 1;
X break;
X case '?':
X if (argn < 3)
X comarg[argn++] = optarg;
X else {
X fprintf(stderr, "Too many arguments.\n");
X giveusage = 1;
X }
X break;
X }
X }
X
X if (giveusage | what == YOW | argn < 1) {
X fprintf(stderr, "Usage: %s databse [-m r|w|rw] [-crtx] -a|-d|-f|-F|-s [key [content]]\n", argv[0]);
X exit(-1);
X }
X
X if ((db = dbm_open(comarg[0], flags, 0777)) == NULL) {
X fprintf(stderr, "Error opening database \"%s\"\n", comarg[0]);
X exit(-1);
X }
X
X if (argn > 1)
X key = read_datum(comarg[1]);
X if (argn > 2)
X content = read_datum(comarg[2]);
X
X switch (what) {
X
X case SCAN:
X key = dbm_firstkey(db);
X if (dbm_error(db)) {
X fprintf(stderr, "Error when fetching first key\n");
X goto db_exit;
X }
X while (key.dptr != NULL) {
X content = dbm_fetch(db, key);
X if (dbm_error(db)) {
X fprintf(stderr, "Error when fetching ");
X print_datum(key);
X printf("\n");
X goto db_exit;
X }
X print_datum(key);
X printf(": ");
X print_datum(content);
X printf("\n");
X if (dbm_error(db)) {
X fprintf(stderr, "Error when fetching next key\n");
X goto db_exit;
X }
X key = dbm_nextkey(db);
X }
X break;
X
X case REGEXP:
X if (argn < 2) {
X fprintf(stderr, "Missing regular expression.\n");
X goto db_exit;
X }
X if (re_comp(comarg[1])) {
X fprintf(stderr, "Invalid regular expression\n");
X goto db_exit;
X }
X key = dbm_firstkey(db);
X if (dbm_error(db)) {
X fprintf(stderr, "Error when fetching first key\n");
X goto db_exit;
X }
X while (key.dptr != NULL) {
X if (re_exec(key2s(key))) {
X content = dbm_fetch(db, key);
X if (dbm_error(db)) {
X fprintf(stderr, "Error when fetching ");
X print_datum(key);
X printf("\n");
X goto db_exit;
X }
X print_datum(key);
X printf(": ");
X print_datum(content);
X printf("\n");
X if (dbm_error(db)) {
X fprintf(stderr, "Error when fetching next key\n");
X goto db_exit;
X }
X }
X key = dbm_nextkey(db);
X }
X break;
X
X case FETCH:
X if (argn < 2) {
X fprintf(stderr, "Missing fetch key.\n");
X goto db_exit;
X }
X content = dbm_fetch(db, key);
X if (dbm_error(db)) {
X fprintf(stderr, "Error when fetching ");
X print_datum(key);
X printf("\n");
X goto db_exit;
X }
X if (content.dptr == NULL) {
X fprintf(stderr, "Cannot find ");
X print_datum(key);
X printf("\n");
X goto db_exit;
X }
X print_datum(key);
X printf(": ");
X print_datum(content);
X printf("\n");
X break;
X
X case DELETE:
X if (argn < 2) {
X fprintf(stderr, "Missing delete key.\n");
X goto db_exit;
X }
X if (dbm_delete(db, key) || dbm_error(db)) {
X fprintf(stderr, "Error when deleting ");
X print_datum(key);
X printf("\n");
X goto db_exit;
X }
X if (verbose) {
X print_datum(key);
X printf(": DELETED\n");
X }
X break;
X
X case STORE:
X if (argn < 3) {
X fprintf(stderr, "Missing key and/or content.\n");
X goto db_exit;
X }
X if (dbm_store(db, key, content, st_flag) || dbm_error(db)) {
X fprintf(stderr, "Error when storing ");
X print_datum(key);
X printf("\n");
X goto db_exit;
X }
X if (verbose) {
X print_datum(key);
X printf(": ");
X print_datum(content);
X printf(" STORED\n");
X }
X break;
X }
X
Xdb_exit:
X dbm_clearerr(db);
X dbm_close(db);
X if (dbm_error(db)) {
X fprintf(stderr, "Error closing database \"%s\"\n", comarg[0]);
X exit(-1);
X }
X}
END_OF_FILE
if test 9799 -ne `wc -c <'dist/dbe.c'`; then
echo shar: \"'dist/dbe.c'\" unpacked with wrong size!
fi
# end of 'dist/dbe.c'
fi
if test -f 'dist/dbm.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'dist/dbm.c'\"
else
echo shar: Extracting \"'dist/dbm.c'\" \(2426 characters\)
sed "s/^X//" >'dist/dbm.c' <<'END_OF_FILE'
X/*
X * Copyright (c) 1985 The Regents of the University of California.
X * All rights reserved.
X *
X * Redistribution and use in source and binary forms are permitted
X * provided that the above copyright notice and this paragraph are
X * duplicated in all such forms and that any documentation,
X * advertising materials, and other materials related to such
X * distribution and use acknowledge that the software was developed
X * by the University of California, Berkeley. The name of the
X * University may not be used to endorse or promote products derived
X * from this software without specific prior written permission.
X * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
X * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
X * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
X */
X
X#ifndef lint
Xstatic char sccsid[] = "@(#)dbm.c 5.4 (Berkeley) 5/24/89";
X#endif /* not lint */
X
X#include "dbm.h"
X
X#define NODB ((DBM *)0)
X
Xstatic DBM *cur_db = NODB;
X
Xstatic char no_db[] = "dbm: no open database\n";
X
Xdbminit(file)
X char *file;
X{
X if (cur_db != NODB)
X dbm_close(cur_db);
X
X cur_db = dbm_open(file, 2, 0);
X if (cur_db == NODB) {
X cur_db = dbm_open(file, 0, 0);
X if (cur_db == NODB)
X return (-1);
X }
X return (0);
X}
X
Xlong
Xforder(key)
Xdatum key;
X{
X if (cur_db == NODB) {
X printf(no_db);
X return (0L);
X }
X return (dbm_forder(cur_db, key));
X}
X
Xdatum
Xfetch(key)
Xdatum key;
X{
X datum item;
X
X if (cur_db == NODB) {
X printf(no_db);
X item.dptr = 0;
X return (item);
X }
X return (dbm_fetch(cur_db, key));
X}
X
Xdelete(key)
Xdatum key;
X{
X if (cur_db == NODB) {
X printf(no_db);
X return (-1);
X }
X if (dbm_rdonly(cur_db))
X return (-1);
X return (dbm_delete(cur_db, key));
X}
X
Xstore(key, dat)
Xdatum key, dat;
X{
X if (cur_db == NODB) {
X printf(no_db);
X return (-1);
X }
X if (dbm_rdonly(cur_db))
X return (-1);
X
X return (dbm_store(cur_db, key, dat, DBM_REPLACE));
X}
X
Xdatum
Xfirstkey()
X{
X datum item;
X
X if (cur_db == NODB) {
X printf(no_db);
X item.dptr = 0;
X return (item);
X }
X return (dbm_firstkey(cur_db));
X}
X
Xdatum
Xnextkey(key)
Xdatum key;
X{
X datum item;
X
X if (cur_db == NODB) {
X printf(no_db);
X item.dptr = 0;
X return (item);
X }
X return (dbm_nextkey(cur_db, key));
X}
END_OF_FILE
if test 2426 -ne `wc -c <'dist/dbm.c'`; then
echo shar: \"'dist/dbm.c'\" unpacked with wrong size!
fi
# end of 'dist/dbm.c'
fi
if test -f 'dist/dbm.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'dist/dbm.h'\"
else
echo shar: Extracting \"'dist/dbm.h'\" \(1186 characters\)
sed "s/^X//" >'dist/dbm.h' <<'END_OF_FILE'
X/*
X * Copyright (c) 1983 The Regents of the University of California.
X * All rights reserved.
X *
X * Redistribution and use in source and binary forms are permitted
X * provided that the above copyright notice and this paragraph are
X * duplicated in all such forms and that any documentation,
X * advertising materials, and other materials related to such
X * distribution and use acknowledge that the software was developed
X * by the University of California, Berkeley. The name of the
X * University may not be used to endorse or promote products derived
X * from this software without specific prior written permission.
X * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
X * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
X * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
X *
X * @(#)dbm.h 5.2 (Berkeley) 5/24/89
X */
X
X#ifndef NULL
X/*
X * this is lunacy, we no longer use it (and never should have
X * unconditionally defined it), but, this whole file is for
X * backwards compatability - someone may rely on this.
X */
X#define NULL ((char *) 0)
X#endif
X
X#include <ndbm.h>
X
Xdatum fetch();
Xdatum firstkey();
Xdatum nextkey();
END_OF_FILE
if test 1186 -ne `wc -c <'dist/dbm.h'`; then
echo shar: \"'dist/dbm.h'\" unpacked with wrong size!
fi
# end of 'dist/dbm.h'
fi
if test -f 'dist/dbu.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'dist/dbu.c'\"
else
echo shar: Extracting \"'dist/dbu.c'\" \(4408 characters\)
sed "s/^X//" >'dist/dbu.c' <<'END_OF_FILE'
X#include <stdio.h>
X#include <sys/file.h>
X#ifdef SDBM
X#include "sdbm.h"
X#else
X#include <ndbm.h>
X#endif
X#include <string.h>
X
X#ifdef BSD42
X#define strchr index
X#endif
X
Xextern int getopt();
Xextern char *strchr();
Xextern void oops();
X
Xchar *progname;
X
Xstatic int rflag;
Xstatic char *usage = "%s [-R] cat | look |... dbmname";
X
X#define DERROR 0
X#define DLOOK 1
X#define DINSERT 2
X#define DDELETE 3
X#define DCAT 4
X#define DBUILD 5
X#define DPRESS 6
X#define DCREAT 7
X
X#define LINEMAX 8192
X
Xtypedef struct {
X char *sname;
X int scode;
X int flags;
X} cmd;
X
Xstatic cmd cmds[] = {
X
X "fetch", DLOOK, O_RDONLY,
X "get", DLOOK, O_RDONLY,
X "look", DLOOK, O_RDONLY,
X "add", DINSERT, O_RDWR,
X "insert", DINSERT, O_RDWR,
X "store", DINSERT, O_RDWR,
X "delete", DDELETE, O_RDWR,
X "remove", DDELETE, O_RDWR,
X "dump", DCAT, O_RDONLY,
X "list", DCAT, O_RDONLY,
X "cat", DCAT, O_RDONLY,
X "creat", DCREAT, O_RDWR | O_CREAT | O_TRUNC,
X "new", DCREAT, O_RDWR | O_CREAT | O_TRUNC,
X "build", DBUILD, O_RDWR | O_CREAT,
X "squash", DPRESS, O_RDWR,
X "compact", DPRESS, O_RDWR,
X "compress", DPRESS, O_RDWR
X};
X
X#define CTABSIZ (sizeof (cmds)/sizeof (cmd))
X
Xstatic cmd *parse();
Xstatic void badk(), doit(), prdatum();
X
Xint
Xmain(argc, argv)
Xint argc;
Xchar *argv[];
X{
X int c;
X register cmd *act;
X extern int optind;
X extern char *optarg;
X
X progname = argv[0];
X
X while ((c = getopt(argc, argv, "R")) != EOF)
X switch (c) {
X case 'R': /* raw processing */
X rflag++;
X break;
X
X default:
X oops("usage: %s", usage);
X break;
X }
X
X if ((argc -= optind) < 2)
X oops("usage: %s", usage);
X
X if ((act = parse(argv[optind])) == NULL)
X badk(argv[optind]);
X optind++;
X doit(act, argv[optind]);
X return 0;
X}
X
Xstatic void
Xdoit(act, file)
Xregister cmd *act;
Xchar *file;
X{
X datum key;
X datum val;
X register DBM *db;
X register char *op;
X register int n;
X char *line;
X#ifdef TIME
X long start;
X extern long time();
X#endif
X
X if ((db = dbm_open(file, act->flags, 0644)) == NULL)
X oops("cannot open: %s", file);
X
X if ((line = (char *) malloc(LINEMAX)) == NULL)
X oops("%s: cannot get memory", "line alloc");
X
X switch (act->scode) {
X
X case DLOOK:
X while (fgets(line, LINEMAX, stdin) != NULL) {
X n = strlen(line) - 1;
X line[n] = 0;
X key.dptr = line;
X key.dsize = n;
X val = dbm_fetch(db, key);
X if (val.dptr != NULL) {
X prdatum(stdout, val);
X putchar('\n');
X continue;
X }
X prdatum(stderr, key);
X fprintf(stderr, ": not found.\n");
X }
X break;
X case DINSERT:
X break;
X case DDELETE:
X while (fgets(line, LINEMAX, stdin) != NULL) {
X n = strlen(line) - 1;
X line[n] = 0;
X key.dptr = line;
X key.dsize = n;
X if (dbm_delete(db, key) == -1) {
X prdatum(stderr, key);
X fprintf(stderr, ": not found.\n");
X }
X }
X break;
X case DCAT:
X for (key = dbm_firstkey(db); key.dptr != 0;
X key = dbm_nextkey(db)) {
X prdatum(stdout, key);
X putchar('\t');
X prdatum(stdout, dbm_fetch(db, key));
X putchar('\n');
X }
X break;
X case DBUILD:
X#ifdef TIME
X start = time(0);
X#endif
X while (fgets(line, LINEMAX, stdin) != NULL) {
X n = strlen(line) - 1;
X line[n] = 0;
X key.dptr = line;
X if ((op = strchr(line, '\t')) != 0) {
X key.dsize = op - line;
X *op++ = 0;
X val.dptr = op;
X val.dsize = line + n - op;
X }
X else
X oops("bad input; %s", line);
X
X if (dbm_store(db, key, val, DBM_REPLACE) < 0) {
X prdatum(stderr, key);
X fprintf(stderr, ": ");
X oops("store: %s", "failed");
X }
X }
X#ifdef TIME
X printf("done: %d seconds.\n", time(0) - start);
X#endif
X break;
X case DPRESS:
X break;
X case DCREAT:
X break;
X }
X
X dbm_close(db);
X}
X
Xstatic void
Xbadk(word)
Xchar *word;
X{
X register int i;
X
X if (progname)
X fprintf(stderr, "%s: ", progname);
X fprintf(stderr, "bad keywd %s. use one of\n", word);
X for (i = 0; i < (int)CTABSIZ; i++)
X fprintf(stderr, "%-8s%c", cmds[i].sname,
X ((i + 1) % 6 == 0) ? '\n' : ' ');
X fprintf(stderr, "\n");
X exit(1);
X /*NOTREACHED*/
X}
X
Xstatic cmd *
Xparse(str)
Xregister char *str;
X{
X register int i = CTABSIZ;
X register cmd *p;
X
X for (p = cmds; i--; p++)
X if (strcmp(p->sname, str) == 0)
X return p;
X return NULL;
X}
X
Xstatic void
Xprdatum(stream, d)
XFILE *stream;
Xdatum d;
X{
X register int c;
X register char *p = d.dptr;
X register int n = d.dsize;
X
X while (n--) {
X c = *p++ & 0377;
X if (c & 0200) {
X fprintf(stream, "M-");
X c &= 0177;
X }
X if (c == 0177 || c < ' ')
X fprintf(stream, "^%c", (c == 0177) ? '?' : c + '@');
X else
X putc(c, stream);
X }
X}
X
X
END_OF_FILE
if test 4408 -ne `wc -c <'dist/dbu.c'`; then
echo shar: \"'dist/dbu.c'\" unpacked with wrong size!
fi
# end of 'dist/dbu.c'
fi
if test -f 'dist/hash.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'dist/hash.c'\"
else
echo shar: Extracting \"'dist/hash.c'\" \(922 characters\)
sed "s/^X//" >'dist/hash.c' <<'END_OF_FILE'
X/*
X * sdbm - ndbm work-alike hashed database library
X * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
X * author: oz at nexus.yorku.ca
X * status: public domain. keep it that way.
X *
X * hashing routine
X */
X
X#include "sdbm.h"
X/*
X * polynomial conversion ignoring overflows
X * [this seems to work remarkably well, in fact better
X * then the ndbm hash function. Replace at your own risk]
X * use: 65599 nice.
X * 65587 even better.
X */
Xlong
Xdbm_hash(str, len)
Xregister char *str;
Xregister int len;
X{
X register unsigned long n = 0;
X
X#ifdef DUFF
X
X#define HASHC n = *str++ + 65599 * n
X
X if (len > 0) {
X register int loop = (len + 8 - 1) >> 3;
X
X switch(len & (8 - 1)) {
X case 0: do {
X HASHC; case 7: HASHC;
X case 6: HASHC; case 5: HASHC;
X case 4: HASHC; case 3: HASHC;
X case 2: HASHC; case 1: HASHC;
X } while (--loop);
X }
X
X }
X#else
X while (len--)
X n = *str++ + 65599 * n;
X#endif
X return n;
X}
END_OF_FILE
if test 922 -ne `wc -c <'dist/hash.c'`; then
echo shar: \"'dist/hash.c'\" unpacked with wrong size!
fi
# end of 'dist/hash.c'
fi
if test -f 'dist/makefile' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'dist/makefile'\"
else
echo shar: Extracting \"'dist/makefile'\" \(1147 characters\)
sed "s/^X//" >'dist/makefile' <<'END_OF_FILE'
X#
X# makefile for public domain ndbm-clone: sdbm
X# DUFF: use duff's device (loop unroll) in parts of the code
X#
XCFLAGS = -O -DSDBM -DDUFF -DBSD42
X#LDFLAGS = -p
X
XOBJS = sdbm.o pair.o hash.o
XSRCS = sdbm.c pair.c hash.c dbu.c dba.c dbd.c util.c
XHDRS = tune.h sdbm.h pair.h
XMISC = README CHANGES COMPARE sdbm.3 dbe.c dbe.1 dbm.c dbm.h biblio \
X readme.ms readme.ps
X
Xall: dbu dba dbd dbe
X
Xdbu: dbu.o sdbm util.o
X cc $(LDFLAGS) -o dbu dbu.o util.o libsdbm.a
X
Xdba: dba.o util.o
X cc $(LDFLAGS) -o dba dba.o util.o
Xdbd: dbd.o util.o
X cc $(LDFLAGS) -o dbd dbd.o util.o
Xdbe: dbe.o sdbm
X cc $(LDFLAGS) -o dbe dbe.o libsdbm.a
X
Xsdbm: $(OBJS)
X ar cr libsdbm.a $(OBJS)
X ranlib libsdbm.a
X### cp libsdbm.a /usr/lib/libsdbm.a
X
Xdba.o: sdbm.h
Xdbu.o: sdbm.h
Xutil.o:sdbm.h
X
X$(OBJS): sdbm.h tune.h pair.h
X
X#
X# dbu using berkelezoid ndbm routines [if you have them] for testing
X#
X#x-dbu: dbu.o util.o
X# cc $(CFLAGS) -o x-dbu dbu.o util.o
Xlint:
X lint -abchx $(SRCS)
X
Xclean:
X rm -f *.o mon.out core
X
Xpurge: clean
X rm -f dbu libsdbm.a dbd dba dbe x-dbu *.dir *.pag
X
Xshar:
X shar $(MISC) makefile $(SRCS) $(HDRS) >SDBM.SHAR
X
Xreadme:
X nroff -ms readme.ms | col -b >README
END_OF_FILE
if test 1147 -ne `wc -c <'dist/makefile'`; then
echo shar: \"'dist/makefile'\" unpacked with wrong size!
fi
# end of 'dist/makefile'
fi
if test -f 'dist/pair.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'dist/pair.c'\"
else
echo shar: Extracting \"'dist/pair.c'\" \(5720 characters\)
sed "s/^X//" >'dist/pair.c' <<'END_OF_FILE'
X/*
X * sdbm - ndbm work-alike hashed database library
X * based on Per-Aake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
X * author: oz at nexus.yorku.ca
X * status: public domain.
X *
X * page-level routines
X */
X
X#ifndef lint
Xstatic char rcsid[] = "$Id: pair.c,v 1.10 90/12/13 13:00:35 oz Exp $";
X#endif
X
X#include "sdbm.h"
X#include "tune.h"
X#include "pair.h"
X
X#ifndef BSD42
X#include <memory.h>
X#endif
X
X#define exhash(item) dbm_hash((item).dptr, (item).dsize)
X
X/*
X * forward
X */
Xstatic int seepair proto((char *, int, char *, int));
X
X/*
X * page format:
X * +------------------------------+
X * ino | n | keyoff | datoff | keyoff |
X * +------------+--------+--------+
X * | datoff | - - - ----> |
X * +--------+---------------------+
X * | F R E E A R E A |
X * +--------------+---------------+
X * | <---- - - - | data |
X * +--------+-----+----+----------+
X * | key | data | key |
X * +--------+----------+----------+
X *
X * calculating the offsets for free area: if the number
X * of entries (ino[0]) is zero, the offset to the END of
X * the free area is the block size. Otherwise, it is the
X * nth (ino[ino[0]]) entry's offset.
X */
X
Xint
Xfitpair(pag, need)
Xchar *pag;
Xint need;
X{
X register int n;
X register int off;
X register int free;
X register short *ino = (short *) pag;
X
X off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
X free = off - (n + 1) * sizeof(short);
X need += 2 * sizeof(short);
X
X debug(("free %d need %d\n", free, need));
X
X return need <= free;
X}
X
Xvoid
Xputpair(pag, key, val)
Xchar *pag;
Xdatum key;
Xdatum val;
X{
X register int n;
X register int off;
X register short *ino = (short *) pag;
X
X off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
X/*
X * enter the key first
X */
X off -= key.dsize;
X (void) memcpy(pag + off, key.dptr, key.dsize);
X ino[n + 1] = off;
X/*
X * now the data
X */
X off -= val.dsize;
X (void) memcpy(pag + off, val.dptr, val.dsize);
X ino[n + 2] = off;
X/*
X * adjust item count
X */
X ino[0] += 2;
X}
X
Xdatum
Xgetpair(pag, key)
Xchar *pag;
Xdatum key;
X{
X register int i;
X register int n;
X datum val;
X register short *ino = (short *) pag;
X
X if ((n = ino[0]) == 0)
X return nullitem;
X
X if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
X return nullitem;
X
X val.dptr = pag + ino[i + 1];
X val.dsize = ino[i] - ino[i + 1];
X return val;
X}
X
X#ifdef SEEDUPS
Xint
Xduppair(pag, key)
Xchar *pag;
Xdatum key;
X{
X register short *ino = (short *) pag;
X return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0;
X}
X#endif
X
Xdatum
Xgetnkey(pag, num)
Xchar *pag;
Xint num;
X{
X datum key;
X register int off;
X register short *ino = (short *) pag;
X
X num = num * 2 - 1;
X if (ino[0] == 0 || num > ino[0])
X return nullitem;
X
X off = (num > 1) ? ino[num - 1] : PBLKSIZ;
X
X key.dptr = pag + ino[num];
X key.dsize = off - ino[num];
X
X return key;
X}
X
Xint
Xdelpair(pag, key)
Xchar *pag;
Xdatum key;
X{
X register int n;
X register int i;
X register short *ino = (short *) pag;
X
X if ((n = ino[0]) == 0)
X return 0;
X
X if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
X return 0;
X/*
X * found the key. if it is the last entry
X * [i.e. i == n - 1] we just adjust the entry count.
X * hard case: move all data down onto the deleted pair,
X * shift offsets onto deleted offsets, and adjust them.
X * [note: 0 < i < n]
X */
X if (i < n - 1) {
X register int m;
X register char *dst = pag + (i == 1 ? PBLKSIZ : ino[i - 1]);
X register char *src = pag + ino[i + 1];
X register int zoo = dst - src;
X
X debug(("free-up %d ", zoo));
X/*
X * shift data/keys down
X */
X m = ino[i + 1] - ino[n];
X#ifdef DUFF
X#define MOVB *--dst = *--src
X
X if (m > 0) {
X register int loop = (m + 8 - 1) >> 3;
X
X switch (m & (8 - 1)) {
X case 0: do {
X MOVB; case 7: MOVB;
X case 6: MOVB; case 5: MOVB;
X case 4: MOVB; case 3: MOVB;
X case 2: MOVB; case 1: MOVB;
X } while (--loop);
X }
X }
X#else
X#ifdef MEMMOVE
X memmove(dst, src, m);
X#else
X while (m--)
X *--dst = *--src;
X#endif
X#endif
X/*
X * adjust offset index up
X */
X while (i < n - 1) {
X ino[i] = ino[i + 2] + zoo;
X i++;
X }
X }
X ino[0] -= 2;
X return 1;
X}
X
X/*
X * search for the key in the page.
X * return offset index in the range 0 < i < n.
X * return 0 if not found.
X */
Xstatic int
Xseepair(pag, n, key, siz)
Xchar *pag;
Xregister int n;
Xregister char *key;
Xregister int siz;
X{
X register int i;
X register int off = PBLKSIZ;
X register short *ino = (short *) pag;
X
X for (i = 1; i < n; i += 2) {
X if (siz == off - ino[i] &&
X memcmp(key, pag + ino[i], siz) == 0)
X return i;
X off = ino[i + 1];
X }
X return 0;
X}
X
Xvoid
Xsplpage(pag, new, sbit)
Xchar *pag;
Xchar *new;
Xlong sbit;
X{
X datum key;
X datum val;
X
X register int n;
X register int off = PBLKSIZ;
X char cur[PBLKSIZ];
X register short *ino = (short *) cur;
X
X (void) memcpy(cur, pag, PBLKSIZ);
X (void) memset(pag, 0, PBLKSIZ);
X (void) memset(new, 0, PBLKSIZ);
X
X n = ino[0];
X for (ino++; n > 0; ino += 2) {
X key.dptr = cur + ino[0];
X key.dsize = off - ino[0];
X val.dptr = cur + ino[1];
X val.dsize = ino[0] - ino[1];
X/*
X * select the page pointer (by looking at sbit) and insert
X */
X (void) putpair((exhash(key) & sbit) ? new : pag, key, val);
X
X off = ino[1];
X n -= 2;
X }
X
X debug(("%d split %d/%d\n", ((short *) cur)[0] / 2,
X ((short *) new)[0] / 2,
X ((short *) pag)[0] / 2));
X}
X
X/*
X * check page sanity:
X * number of entries should be something
X * reasonable, and all offsets in the index should be in order.
X * this could be made more rigorous.
X */
Xint
Xchkpage(pag)
Xchar *pag;
X{
X register int n;
X register int off;
X register short *ino = (short *) pag;
X
X if ((n = ino[0]) < 0 || n > PBLKSIZ / sizeof(short))
X return 0;
X
X if (n > 0) {
X off = PBLKSIZ;
X for (ino++; n > 0; ino += 2) {
X if (ino[0] > off || ino[1] > off ||
X ino[1] > ino[0])
X return 0;
X off = ino[1];
X n -= 2;
X }
X }
X return 1;
X}
END_OF_FILE
if test 5720 -ne `wc -c <'dist/pair.c'`; then
echo shar: \"'dist/pair.c'\" unpacked with wrong size!
fi
# end of 'dist/pair.c'
fi
if test -f 'dist/pair.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'dist/pair.h'\"
else
echo shar: Extracting \"'dist/pair.h'\" \(378 characters\)
sed "s/^X//" >'dist/pair.h' <<'END_OF_FILE'
Xextern int fitpair proto((char *, int));
Xextern void putpair proto((char *, datum, datum));
Xextern datum getpair proto((char *, datum));
Xextern int delpair proto((char *, datum));
Xextern int chkpage proto((char *));
Xextern datum getnkey proto((char *, int));
Xextern void splpage proto((char *, char *, long));
X#ifdef SEEDUPS
Xextern int duppair proto((char *, datum));
X#endif
END_OF_FILE
if test 378 -ne `wc -c <'dist/pair.h'`; then
echo shar: \"'dist/pair.h'\" unpacked with wrong size!
fi
# end of 'dist/pair.h'
fi
if test -f 'dist/sdbm.3' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'dist/sdbm.3'\"
else
echo shar: Extracting \"'dist/sdbm.3'\" \(8952 characters\)
sed "s/^X//" >'dist/sdbm.3' <<'END_OF_FILE'
X.\" $Id: sdbm.3,v 1.2 90/12/13 13:00:57 oz Exp $
X.TH SDBM 3 "1 March 1990"
X.SH NAME
Xsdbm, dbm_open, dbm_prep, dbm_close, dbm_fetch, dbm_store, dbm_delete, dbm_firstkey, dbm_nextkey, dbm_hash, dbm_rdonly, dbm_error, dbm_clearerr, dbm_dirfno, dbm_pagfno \- data base subroutines
X.SH SYNOPSIS
X.nf
X.ft B
X#include <sdbm.h>
X.sp
Xtypedef struct {
X char *dptr;
X int dsize;
X} datum;
X.sp
Xdatum nullitem = { NULL, 0 };
X.sp
X\s-1DBM\s0 *dbm_open(char *file, int flags, int mode)
X.sp
X\s-1DBM\s0 *dbm_prep(char *dirname, char *pagname, int flags, int mode)
X.sp
Xvoid dbm_close(\s-1DBM\s0 *db)
X.sp
Xdatum dbm_fetch(\s-1DBM\s0 *db, key)
X.sp
Xint dbm_store(\s-1DBM\s0 *db, datum key, datum val, int flags)
X.sp
Xint dbm_delete(\s-1DBM\s0 *db, datum key)
X.sp
Xdatum dbm_firstkey(\s-1DBM\s0 *db)
X.sp
Xdatum dbm_nextkey(\s-1DBM\s0 *db)
X.sp
Xlong dbm_hash(char *string, int len)
X.sp
Xint dbm_rdonly(\s-1DBM\s0 *db)
Xint dbm_error(\s-1DBM\s0 *db)
Xdbm_clearerr(\s-1DBM\s0 *db)
Xint dbm_dirfno(\s-1DBM\s0 *db)
Xint dbm_pagfno(\s-1DBM\s0 *db)
X.ft R
X.fi
X.SH DESCRIPTION
X.IX "database library" sdbm "" "\fLsdbm\fR"
X.IX dbm_open "" "\fLdbm_open\fR \(em open \fLsdbm\fR database"
X.IX dbm_prep "" "\fLdbm_prep\fR \(em prepare \fLsdbm\fR database"
X.IX dbm_close "" "\fLdbm_close\fR \(em close \fLsdbm\fR routine"
X.IX dbm_fetch "" "\fLdbm_fetch\fR \(em fetch \fLsdbm\fR database data"
X.IX dbm_store "" "\fLdbm_store\fR \(em add data to \fLsdbm\fR database"
X.IX dbm_delete "" "\fLdbm_delete\fR \(em remove data from \fLsdbm\fR database"
X.IX dbm_firstkey "" "\fLdbm_firstkey\fR \(em access \fLsdbm\fR database"
X.IX dbm_nextkey "" "\fLdbm_nextkey\fR \(em access \fLsdbm\fR database"
X.IX dbm_hash "" "\fLdbm_hash\fR \(em string hash for \fLsdbm\fR database"
X.IX dbm_rdonly "" "\fLdbm_rdonly\fR \(em return \fLsdbm\fR database read-only mode"
X.IX dbm_error "" "\fLdbm_error\fR \(em return \fLsdbm\fR database error condition"
X.IX dbm_clearerr "" "\fLdbm_clearerr\fR \(em clear \fLsdbm\fR database error condition"
X.IX dbm_dirfno "" "\fLdbm_dirfno\fR \(em return \fLsdbm\fR database bitmap file descriptor"
X.IX dbm_pagfno "" "\fLdbm_pagfno\fR \(em return \fLsdbm\fR database data file descriptor"
X.IX "database functions \(em \fLsdbm\fR" dbm_open "" \fLdbm_open\fP
X.IX "database functions \(em \fLsdbm\fR" dbm_prep "" \fLdbm_prep\fP
X.IX "database functions \(em \fLsdbm\fR" dbm_close "" \fLdbm_close\fP
X.IX "database functions \(em \fLsdbm\fR" dbm_fetch "" \fLdbm_fetch\fP
X.IX "database functions \(em \fLsdbm\fR" dbm_store "" \fLdbm_store\fP
X.IX "database functions \(em \fLsdbm\fR" dbm_delete "" \fLdbm_delete\fP
X.IX "database functions \(em \fLsdbm\fR" dbm_firstkey "" \fLdbm_firstkey\fP
X.IX "database functions \(em \fLsdbm\fR" dbm_nextkey "" \fLdbm_nextkey\fP
X.IX "database functions \(em \fLsdbm\fR" dbm_rdonly "" \fLdbm_rdonly\fP
X.IX "database functions \(em \fLsdbm\fR" dbm_error "" \fLdbm_error\fP
X.IX "database functions \(em \fLsdbm\fR" dbm_clearerr "" \fLdbm_clearerr\fP
X.IX "database functions \(em \fLsdbm\fR" dbm_dirfno "" \fLdbm_dirfno\fP
X.IX "database functions \(em \fLsdbm\fR" dbm_pagfno "" \fLdbm_pagfno\fP
X.LP
XThis package allows an application to maintain a mapping of <key,value> pairs
Xin disk files. This is not to be considered a real database system, but is
Xstill useful in many simple applications built around fast retrieval of a data
Xvalue from a key. This implementation uses an external hashing scheme,
Xcalled Dynamic Hashing, as described by Per-Aake Larson in BIT 18 (1978) pp.
X184-201. Retrieval of any item usually requires a single disk access.
XThe application interface is compatible with the
X.IR ndbm (3)
Xlibrary.
X.LP
XAn
X.B sdbm
Xdatabase is kept in two files usually given the extensions
X.B \.dir
Xand
X.BR \.pag .
XThe
X.B \.dir
Xfile contains a bitmap representing a forest of binary hash trees, the leaves
Xof which indicate data pages in the
X.B \.pag
Xfile.
X.LP
XThe application interface uses the
X.B datum
Xstructure to describe both
X.I keys
Xand
X.IR value s.
XA
X.B datum
Xspecifies a byte sequence of
X.I dsize
Xsize pointed to by
X.IR dptr .
XIf you use
X.SM ASCII
Xstrings as
X.IR key s
Xor
X.IR value s,
Xthen you must decide whether or not to include the terminating
X.SM NUL
Xbyte which sometimes defines strings. Including it will require larger
Xdatabase files, but it will be possible to get sensible output from a
X.IR strings (1)
Xcommand applied to the data file.
X.LP
XIn order to allow a process using this package to manipulate multiple
Xdatabases, the applications interface always requires a
X.IR handle ,
Xa
X.BR "DBM *" ,
Xto identify the database to be manipulated. Such a handle can be obtained
Xfrom the only routines that do not require it, namely
X.BR dbm_open (\|)
Xor
X.BR dbm_prep (\|).
XEither of these will open or create the two necessary files. The
Xdifference is that the latter allows explicitly naming the bitmap and data
Xfiles whereas
X.BR dbm_open (\|)
Xwill take a base file name and call
X.BR dbm_prep (\|)
Xwith the default extensions.
XThe
X.I flags
Xand
X.I mode
Xparameters are the same as for
X.BR open (2).
X.LP
XTo free the resources occupied while a database handle is active, call
X.BR dbm_close (\|).
X.LP
XGiven a handle, one can retrieve data associated with a key by using the
X.BR dbm_fetch (\|)
Xroutine, and associate data with a key by using the
X.BR dbm_store (\|)
Xroutine.
X.LP
XThe values of the
X.I flags
Xparameter for
X.BR dbm_store (\|)
Xcan be either
X.BR \s-1DBM_INSERT\s0 ,
Xwhich will not change an existing entry with the same key, or
X.BR \s-1DBM_REPLACE\s0 ,
Xwhich will replace an existing entry with the same key.
XKeys are unique within the database.
X.LP
XTo delete a key and its associated value use the
X.BR dbm_delete (\|)
Xroutine.
X.LP
XTo retrieve every key in the database, use a loop like:
X.sp
X.nf
X.ft B
Xfor (key = dbm_firstkey(db); key.dptr != NULL; key = dbm_nextkey(db))
X ;
X.ft R
X.fi
X.LP
XThe order of retrieval is unspecified.
X.LP
XIf you determine that the performance of the database is inadequate or
Xyou notice clustering or other effects that may be due to the hashing
Xalgorithm used by this package, you can override it by supplying your
Xown
X.BR dbm_hash (\|)
Xroutine. Doing so will make the database unintelligable to any other
Xapplications that do not use your specialized hash function.
X.sp
X.LP
XThe following macros are defined in the header file:
X.IP
X.BR dbm_rdonly (\|)
Xreturns true if the database has been opened read\-only.
X.IP
X.BR dbm_error (\|)
Xreturns true if an I/O error has occurred.
X.IP
X.BR dbm_clearerr (\|)
Xallows you to clear the error flag if you think you know what the error
Xwas and insist on ignoring it.
X.IP
X.BR dbm_dirfno (\|)
Xreturns the file descriptor associated with the bitmap file.
X.IP
X.BR dbm_pagfno (\|)
Xreturns the file descriptor associated with the data file.
X.SH SEE ALSO
X.IR open (2).
X.SH DIAGNOSTICS
XFunctions that return a
X.B "DBM *"
Xhandle will use
X.SM NULL
Xto indicate an error.
XFunctions that return an
X.B int
Xwill use \-1 to indicate an error. The normal return value in that case is 0.
XFunctions that return a
X.B datum
Xwill return
X.B nullitem
Xto indicate an error.
X.LP
XAs a special case of
X.BR dbm_store (\|),
Xif it is called with the
X.B \s-1DBM_INSERT\s0
Xflag and the key already exists in the database, the return value will be 1.
X.LP
XIn general, if a function parameter is invalid,
X.B errno
Xwill be set to
X.BR \s-1EINVAL\s0 .
XIf a write operation is requested on a read-only database,
X.B errno
Xwill be set to
X.BR \s-1ENOPERM\s0 .
XIf a memory allocation (using
X.IR malloc (3))
Xfailed,
X.B errno
Xwill be set to
X.BR \s-1ENOMEM\s0 .
XFor I/O operation failures
X.B errno
Xwill contain the value set by the relevant failed system call, either
X.IR read (2),
X.IR write (2),
Xor
X.IR lseek (2).
X.SH AUTHOR
X.IP "Ozan S. Yigit" (oz at nexus.yorku.ca)
X.SH BUGS
XThe sum of key and value data sizes must not exceed
X.B \s-1PAIRMAX\s0
X(1008 bytes).
X.LP
XThe sum of the key and value data sizes where several keys hash to the
Xsame value must fit within one bitmap page.
X.LP
XThe
X.B \.pag
Xfile will contain holes, so its apparent size is larger than its contents.
XWhen copied through the filesystem the holes will be filled.
X.LP
XThe contents of
X.B datum
Xvalues returned are in volatile storage. If you want to retain the values
Xpointed to, you must copy them immediately before another call to this package.
X.LP
XThe only safe way for multiple processes to (read and) update a database at
Xthe same time, is to implement a private locking scheme outside this package
Xand open and close the database between lock acquisitions. It is safe for
Xmultiple processes to concurrently access a database read-only.
X.SH APPLICATIONS PORTABILITY
XFor complete source code compatibility with the Berkeley Unix
X.IR ndbm (3)
Xlibrary, the
X.B sdbm.h
Xheader file should be installed in
X.BR /usr/include/ndbm.h .
X.LP
XThe
X.B nullitem
Xdata item, and the
X.BR dbm_prep (\|),
X.BR dbm_hash (\|),
X.BR dbm_rdonly (\|),
X.BR dbm_dirfno (\|),
Xand
X.BR dbm_pagfno (\|)
Xfunctions are unique to this package.
END_OF_FILE
if test 8952 -ne `wc -c <'dist/sdbm.3'`; then
echo shar: \"'dist/sdbm.3'\" unpacked with wrong size!
fi
# end of 'dist/sdbm.3'
fi
if test -f 'dist/sdbm.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'dist/sdbm.h'\"
else
echo shar: Extracting \"'dist/sdbm.h'\" \(2174 characters\)
sed "s/^X//" >'dist/sdbm.h' <<'END_OF_FILE'
X/*
X * sdbm - ndbm work-alike hashed database library
X * based on Per-Ake Larson's Dynamic Hashing algorithms. BIT 18 (1978).
X * author: oz at nexus.yorku.ca
X * status: public domain.
X */
X#define DBLKSIZ 4096
X#define PBLKSIZ 1024
X#define PAIRMAX 1008 /* arbitrary on PBLKSIZ-N */
X#define SPLTMAX 10 /* maximum allowed splits */
X /* for a single insertion */
X#define DIRFEXT ".dir"
X#define PAGFEXT ".pag"
X
Xtypedef struct {
X int dirf; /* directory file descriptor */
X int pagf; /* page file descriptor */
X int flags; /* status/error flags, see below */
X long maxbno; /* size of dirfile in bits */
X long curbit; /* current bit number */
X long hmask; /* current hash mask */
X long blkptr; /* current block for nextkey */
X int keyptr; /* current key for nextkey */
X long blkno; /* current page to read/write */
X long pagbno; /* current page in pagbuf */
X char pagbuf[PBLKSIZ]; /* page file block buffer */
X long dirbno; /* current block in dirbuf */
X char dirbuf[DBLKSIZ]; /* directory file block buffer */
X} DBM;
X
X#define DBM_RDONLY 0x1 /* data base open read-only */
X#define DBM_IOERR 0x2 /* data base I/O error */
X
X/*
X * utility macros
X */
X#define dbm_rdonly(db) ((db)->flags & DBM_RDONLY)
X#define dbm_error(db) ((db)->flags & DBM_IOERR)
X
X#define dbm_clearerr(db) ((db)->flags &= ~DBM_IOERR) /* ouch */
X
X#define dbm_dirfno(db) ((db)->dirf)
X#define dbm_pagfno(db) ((db)->pagf)
X
Xtypedef struct {
X char *dptr;
X int dsize;
X} datum;
X
Xextern datum nullitem;
X
X#ifdef __STDC__
X#define proto(p) p
X#else
X#define proto(p) ()
X#endif
X
X/*
X * flags to dbm_store
X */
X#define DBM_INSERT 0
X#define DBM_REPLACE 1
X
X/*
X * ndbm interface
X */
Xextern DBM *dbm_open proto((char *, int, int));
Xextern void dbm_close proto((DBM *));
Xextern datum dbm_fetch proto((DBM *, datum));
Xextern int dbm_delete proto((DBM *, datum));
Xextern int dbm_store proto((DBM *, datum, datum, int));
Xextern datum dbm_firstkey proto((DBM *));
Xextern datum dbm_nextkey proto((DBM *));
X
X/*
X * other
X */
Xextern DBM *dbm_prep proto((char *, char *, int, int));
Xextern long dbm_hash proto((char *, int));
END_OF_FILE
if test 2174 -ne `wc -c <'dist/sdbm.h'`; then
echo shar: \"'dist/sdbm.h'\" unpacked with wrong size!
fi
# end of 'dist/sdbm.h'
fi
if test -f 'dist/tune.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'dist/tune.h'\"
else
echo shar: Extracting \"'dist/tune.h'\" \(665 characters\)
sed "s/^X//" >'dist/tune.h' <<'END_OF_FILE'
X/*
X * sdbm - ndbm work-alike hashed database library
X * tuning and portability constructs [not nearly enough]
X * author: oz at nexus.yorku.ca
X */
X
X#define BYTESIZ 8
X
X#ifdef SVID
X#include <unistd.h>
X#endif
X
X#ifdef BSD42
X#define SEEK_SET L_SET
X#define memset(s,c,n) bzero(s, n) /* only when c is zero */
X#define memcpy(s1,s2,n) bcopy(s2, s1, n)
X#define memcmp(s1,s2,n) bcmp(s1,s2,n)
X#endif
X
X/*
X * important tuning parms (hah)
X */
X
X#define SEEDUPS /* always detect duplicates */
X#define BADMESS /* generate a message for worst case:
X cannot make room after SPLTMAX splits */
X/*
X * misc
X */
X#ifdef DEBUG
X#define debug(x) printf x
X#else
X#define debug(x)
X#endif
END_OF_FILE
if test 665 -ne `wc -c <'dist/tune.h'`; then
echo shar: \"'dist/tune.h'\" unpacked with wrong size!
fi
# end of 'dist/tune.h'
fi
if test -f 'dist/util.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'dist/util.c'\"
else
echo shar: Extracting \"'dist/util.c'\" \(767 characters\)
sed "s/^X//" >'dist/util.c' <<'END_OF_FILE'
X#include <stdio.h>
X#ifdef SDBM
X#include "sdbm.h"
X#else
X#include "ndbm.h"
X#endif
X
Xvoid
Xoops(s1, s2)
Xregister char *s1;
Xregister char *s2;
X{
X extern int errno, sys_nerr;
X extern char *sys_errlist[];
X extern char *progname;
X
X if (progname)
X fprintf(stderr, "%s: ", progname);
X fprintf(stderr, s1, s2);
X if (errno > 0 && errno < sys_nerr)
X fprintf(stderr, " (%s)", sys_errlist[errno]);
X fprintf(stderr, "\n");
X exit(1);
X}
X
Xint
Xokpage(pag)
Xchar *pag;
X{
X register unsigned n;
X register off;
X register short *ino = (short *) pag;
X
X if ((n = ino[0]) > PBLKSIZ / sizeof(short))
X return 0;
X
X if (!n)
X return 1;
X
X off = PBLKSIZ;
X for (ino++; n; ino += 2) {
X if (ino[0] > off || ino[1] > off ||
X ino[1] > ino[0])
X return 0;
X off = ino[1];
X n -= 2;
X }
X
X return 1;
X}
END_OF_FILE
if test 767 -ne `wc -c <'dist/util.c'`; then
echo shar: \"'dist/util.c'\" unpacked with wrong size!
fi
# end of 'dist/util.c'
fi
echo shar: End of archive 1 \(of 2\).
cp /dev/null ark1isdone
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
More information about the Alt.sources
mailing list