#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create the files:
#	dbu.c
#	hash.c
#	makefile
#	sdbm.3
#	sdbm.c
#	sdbm.h
#	tune.h
#	util.c
# This archive created: Wed Jul 31 16:22:49 1991
export PATH; PATH=/bin:$PATH
if test -f 'dbu.c'
then
	echo shar: will not over-write existing file "'dbu.c'"
else
cat << \SHAR_EOF > 'dbu.c'
/*
 * dbu - ndbm/sdbm database utility
 *
 * Copyright (c) 1991 by Ozan S. Yigit (oz@nexus.yorku.ca)
 *
 * Permission to use, copy, modify, and distribute this software and its
 * documentation for any purpose and without fee is hereby granted,
 * provided that the above copyright notice appear in all copies and that
 * both that copyright notice and this permission notice appear in
 * supporting documentation.
 *
 * This file is provided AS IS with no warranties of any kind.  The author
 * shall have no liability with respect to the infringement of copyrights,
 * trade secrets or any patents by this file or any part thereof.  In no
 * event will the author be liable for any lost revenue or profits or
 * other special, indirect and consequential damages.
 */

#include <stdio.h>
#include <sys/file.h>
#ifdef SDBM
#include "sdbm.h"
#else
#include <ndbm.h>
#endif
#include <string.h>

#ifdef BSD42
#define strchr	index
#endif

extern int	getopt();
extern char	*strchr();
extern void	oops();

char *progname;

static int rflag;
static char *usage = "%s [-R] cat | look |... dbmname";

#define DERROR	0
#define DLOOK	1
#define DINSERT	2
#define DDELETE 3
#define	DCAT	4
#define DBUILD	5
#define DPRESS	6
#define DCREAT	7

#define LINEMAX	8192

typedef struct {
	char *sname;
	int scode;
	int flags;
} cmd;

static cmd cmds[] = {

	"fetch", DLOOK, 	O_RDONLY,
	"get", DLOOK,		O_RDONLY,
	"look", DLOOK,		O_RDONLY,
	"add", DINSERT,		O_RDWR,
	"insert", DINSERT,	O_RDWR,
	"store", DINSERT,	O_RDWR,
	"delete", DDELETE,	O_RDWR,
	"remove", DDELETE,	O_RDWR,
	"dump", DCAT,		O_RDONLY,
	"list", DCAT, 		O_RDONLY,
	"cat", DCAT,		O_RDONLY,
	"creat", DCREAT,	O_RDWR | O_CREAT | O_TRUNC,
	"new", DCREAT,		O_RDWR | O_CREAT | O_TRUNC,
	"build", DBUILD,	O_RDWR | O_CREAT,
	"squash", DPRESS,	O_RDWR,
	"compact", DPRESS,	O_RDWR,
	"compress", DPRESS,	O_RDWR
};

#define CTABSIZ (sizeof (cmds)/sizeof (cmd))

static cmd *parse();
static void badk(), doit(), prdatum();

int
main(argc, argv)
int	argc;
char *argv[];
{
	int c;
	register cmd *act;
	extern int optind;
	extern char *optarg;

	progname = argv[0];

	while ((c = getopt(argc, argv, "R")) != EOF)
		switch (c) {
		case 'R':	       /* raw processing  */
			rflag++;
			break;

		default:
			oops("usage: %s", usage);
			break;
		}

	if ((argc -= optind) < 2)
		oops("usage: %s", usage);

	if ((act = parse(argv[optind])) == NULL)
		badk(argv[optind]);
	optind++;
	doit(act, argv[optind]);
	return 0;
}

static void
doit(act, file)
register cmd *act;
char *file;
{
	datum key;
	datum val;
	register DBM *db;
	register char *op;
	register int n;
	char *line;
#ifdef TIME
	long start;
	extern long time();
#endif

	if ((db = dbm_open(file, act->flags, 0644)) == NULL)
		oops("cannot open: %s", file);

	if ((line = (char *) malloc(LINEMAX)) == NULL)
		oops("%s: cannot get memory", "line alloc");

	switch (act->scode) {

	case DLOOK:
		while (fgets(line, LINEMAX, stdin) != NULL) {
			n = strlen(line) - 1;
			line[n] = 0;
			key.dptr = line;
			key.dsize = n;
			val = dbm_fetch(db, key);
			if (val.dptr != NULL) {
				prdatum(stdout, val);
				putchar('\n');
				continue;
			}
			prdatum(stderr, key);
			fprintf(stderr, ": not found.\n");
		}
		break;
	case DINSERT:
		break;
	case DDELETE:
		while (fgets(line, LINEMAX, stdin) != NULL) {
			n = strlen(line) - 1;
			line[n] = 0;
			key.dptr = line;
			key.dsize = n;
			if (dbm_delete(db, key) == -1) {
				prdatum(stderr, key);
				fprintf(stderr, ": not found.\n");
			}
		}
		break;
	case DCAT:
		for (key = dbm_firstkey(db); key.dptr != 0; 
		     key = dbm_nextkey(db)) {
			prdatum(stdout, key);
			putchar('\t');
			prdatum(stdout, dbm_fetch(db, key));
			putchar('\n');
		}
		break;
	case DBUILD:
#ifdef TIME
		start = time(0);
#endif
		while (fgets(line, LINEMAX, stdin) != NULL) {
			n = strlen(line) - 1;
			line[n] = 0;
			key.dptr = line;
			if ((op = strchr(line, '\t')) != 0) {
				key.dsize = op - line;
				*op++ = 0;
				val.dptr = op;
				val.dsize = line + n - op;
			}
			else
				oops("bad input; %s", line);
	
			if (dbm_store(db, key, val, DBM_REPLACE) < 0) {
				prdatum(stderr, key);
				fprintf(stderr, ": ");
				oops("store: %s", "failed");
			}
		}
#ifdef TIME
		printf("done: %d seconds.\n", time(0) - start);
#endif
		break;
	case DPRESS:
		break;
	case DCREAT:
		break;
	}

	dbm_close(db);
}

static void
badk(word)
char *word;
{
	register int i;

	if (progname)
		fprintf(stderr, "%s: ", progname);
	fprintf(stderr, "bad keywd %s. use one of\n", word);
	for (i = 0; i < (int)CTABSIZ; i++)
		fprintf(stderr, "%-8s%c", cmds[i].sname,
			((i + 1) % 6 == 0) ? '\n' : ' ');
	fprintf(stderr, "\n");
	exit(1);
	/*NOTREACHED*/
}

static cmd *
parse(str)
register char *str;
{
	register int i = CTABSIZ;
	register cmd *p;
	
	for (p = cmds; i--; p++)
		if (strcmp(p->sname, str) == 0)
			return p;
	return NULL;
}

static void
prdatum(stream, d)
FILE *stream;
datum d;
{
	register int c;
	register char *p = d.dptr;
	register int n = d.dsize;

	while (n--) {
		c = *p++ & 0377;
		if (c & 0200) {
			fprintf(stream, "M-");
			c &= 0177;
		}
		if (c == 0177 || c < ' ') 
			fprintf(stream, "^%c", (c == 0177) ? '?' : c + '@');
		else
			putc(c, stream);
	}
}


SHAR_EOF
fi # end of overwriting check
if test -f 'hash.c'
then
	echo shar: will not over-write existing file "'hash.c'"
else
cat << \SHAR_EOF > 'hash.c'
/*
 * sdbm - ndbm work-alike hashed database library
 * based on Per-Aake Larson's Dynamic Hashing algorithms.
 * BIT 18 (1978).
 *
 * Copyright (c) 1991 by Ozan S. Yigit (oz@nexus.yorku.ca)
 *
 * Permission to use, copy, modify, and distribute this software and its
 * documentation for any purpose and without fee is hereby granted,
 * provided that the above copyright notice appear in all copies and that
 * both that copyright notice and this permission notice appear in
 * supporting documentation.
 *
 * This file is provided AS IS with no warranties of any kind.  The author
 * shall have no liability with respect to the infringement of copyrights,
 * trade secrets or any patents by this file or any part thereof.  In no
 * event will the author be liable for any lost revenue or profits or
 * other special, indirect and consequential damages.
 *
 * string hashing routine
 */

#include "sdbm.h"

/*
 * polynomial conversion ignoring overflows
 * [this seems to work remarkably well, in fact better
 * then the ndbm hash function. Replace at your own risk]
 */

#define CONST 65599

long
dbm_hash(str, len)
register char *str;
register int len;
{
	register unsigned long n = 0;

#ifdef DUFF
#define HASHC	n = *str++ + CONST * n

	if (len > 0) {
		register int loop = (len + 8 - 1) >> 3;

		switch(len & (8 - 1)) {
		case 0:	do {
			HASHC;	case 7:	HASHC;
		case 6:	HASHC;	case 5:	HASHC;
		case 4:	HASHC;	case 3:	HASHC;
		case 2:	HASHC;	case 1:	HASHC;
			} while (--loop);
		}
	}
#else
	while (len--)
		n = *str++ + CONST * n;
#endif
	return n;
}
SHAR_EOF
fi # end of overwriting check
if test -f 'makefile'
then
	echo shar: will not over-write existing file "'makefile'"
else
cat << \SHAR_EOF > 'makefile'
#
# makefile for public domain ndbm-clone: sdbm
# DUFF: use duff's device (loop unroll) in parts of the code
#
CFLAGS = -O -DSDBM -DDUFF -DBSD42 -DNULLKEY

LFLAGS = -p

OBJS = sdbm.o hash.o
SRCS = sdbm.c hash.c dbu.c util.c
HDRS = tune.h sdbm.h 

sdbm: $(OBJS)
	ar cr libsdbm.a $(OBJS)
	ranlib libsdbm.a
###	cp libsdbm.a /usr/lib/libsdbm.a

all: dbu

dbu: dbu.o sdbm util.o
	cc $(LFLAGS) -o dbu dbu.o util.o libsdbm.a

dba.o: sdbm.h
dbu.o: sdbm.h
util.o:sdbm.h

$(OBJS): $(HDRS)

lint:
	lint -abchx $(SRCS)

clean:
	rm -f *.o mon.out core

purge: 	clean
	rm -f dbu libsdbm.a  *.dir *.pag
SHAR_EOF
fi # end of overwriting check
if test -f 'sdbm.3'
then
	echo shar: will not over-write existing file "'sdbm.3'"
else
cat << \SHAR_EOF > 'sdbm.3'
.\" sdbm - ndbm work-alike hashed database library
.\" based on Per-Aake Larson's Dynamic Hashing algorithms.
.\" BIT 18 (1978).
.\"
.\" Copyright (c) 1991 by Ozan S. Yigit (oz@nexus.yorku.ca)
.\"
.\" Permission to use, copy, modify, and distribute this software and its
.\" documentation for any purpose and without fee is hereby granted,
.\" provided that the above copyright notice appear in all copies and that
.\" both that copyright notice and this permission notice appear in
.\" supporting documentation.
.\"
.\" This file is provided AS IS with no warranties of any kind.  The author
.\" shall have no liability with respect to the infringement of copyrights,
.\" trade secrets or any patents by this file or any part thereof.  In no
.\" event will the author be liable for any lost revenue or profits or
.\" other special, indirect and consequential damages.
.\"
.TH SDBM 3 "1 March 1990"
.SH NAME
sdbm, 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
.SH SYNOPSIS
.nf
.ft B
#include <sdbm.h>
.sp
typedef struct {
	char *dptr;
	int dsize;
} datum;
.sp
datum nullitem = { NULL, 0 };
.sp
\s-1DBM\s0 *dbm_open(char *file, int flags, int mode)
.sp
\s-1DBM\s0 *dbm_prep(char *dirname, char *pagname, int flags, int mode)
.sp
void dbm_close(\s-1DBM\s0 *db)
.sp
datum dbm_fetch(\s-1DBM\s0 *db, key)
.sp
int dbm_store(\s-1DBM\s0 *db, datum key, datum val, int flags)
.sp
int dbm_delete(\s-1DBM\s0 *db, datum key)
.sp
datum dbm_firstkey(\s-1DBM\s0 *db)
.sp
datum dbm_nextkey(\s-1DBM\s0 *db)
.sp
long dbm_hash(char *string, int len)
.sp
int dbm_rdonly(\s-1DBM\s0 *db)
int dbm_error(\s-1DBM\s0 *db)
dbm_clearerr(\s-1DBM\s0 *db)
int dbm_dirfno(\s-1DBM\s0 *db)
int dbm_pagfno(\s-1DBM\s0 *db)
.ft R
.fi
.SH DESCRIPTION
.IX "database library" sdbm "" "\fLsdbm\fR"
.IX dbm_open "" "\fLdbm_open\fR \(em open \fLsdbm\fR database"
.IX dbm_prep "" "\fLdbm_prep\fR \(em prepare \fLsdbm\fR database"
.IX dbm_close "" "\fLdbm_close\fR \(em close \fLsdbm\fR routine"
.IX dbm_fetch "" "\fLdbm_fetch\fR \(em fetch \fLsdbm\fR database data"
.IX dbm_store "" "\fLdbm_store\fR \(em add data to \fLsdbm\fR database"
.IX dbm_delete "" "\fLdbm_delete\fR \(em remove data from \fLsdbm\fR database"
.IX dbm_firstkey "" "\fLdbm_firstkey\fR \(em access \fLsdbm\fR database"
.IX dbm_nextkey "" "\fLdbm_nextkey\fR \(em access \fLsdbm\fR database"
.IX dbm_hash "" "\fLdbm_hash\fR \(em string hash for \fLsdbm\fR database"
.IX dbm_rdonly "" "\fLdbm_rdonly\fR \(em return \fLsdbm\fR database read-only mode"
.IX dbm_error "" "\fLdbm_error\fR \(em return \fLsdbm\fR database error condition"
.IX dbm_clearerr "" "\fLdbm_clearerr\fR \(em clear \fLsdbm\fR database error condition"
.IX dbm_dirfno "" "\fLdbm_dirfno\fR \(em return \fLsdbm\fR database bitmap file descriptor"
.IX dbm_pagfno "" "\fLdbm_pagfno\fR \(em return \fLsdbm\fR database data file descriptor"
.IX "database functions \(em \fLsdbm\fR"  dbm_open  ""  \fLdbm_open\fP
.IX "database functions \(em \fLsdbm\fR"  dbm_prep  ""  \fLdbm_prep\fP
.IX "database functions \(em \fLsdbm\fR"  dbm_close  ""  \fLdbm_close\fP
.IX "database functions \(em \fLsdbm\fR"  dbm_fetch  ""  \fLdbm_fetch\fP
.IX "database functions \(em \fLsdbm\fR"  dbm_store  ""  \fLdbm_store\fP
.IX "database functions \(em \fLsdbm\fR"  dbm_delete  ""  \fLdbm_delete\fP
.IX "database functions \(em \fLsdbm\fR"  dbm_firstkey  ""  \fLdbm_firstkey\fP
.IX "database functions \(em \fLsdbm\fR"  dbm_nextkey  ""  \fLdbm_nextkey\fP
.IX "database functions \(em \fLsdbm\fR"  dbm_rdonly  ""  \fLdbm_rdonly\fP
.IX "database functions \(em \fLsdbm\fR"  dbm_error  ""  \fLdbm_error\fP
.IX "database functions \(em \fLsdbm\fR"  dbm_clearerr  ""  \fLdbm_clearerr\fP
.IX "database functions \(em \fLsdbm\fR"  dbm_dirfno  ""  \fLdbm_dirfno\fP
.IX "database functions \(em \fLsdbm\fR"  dbm_pagfno  ""  \fLdbm_pagfno\fP
.LP
This package allows an application to maintain a mapping of <key,value> pairs
in disk files.  This is not to be considered a real database system, but is
still useful in many simple applications built around fast retrieval of a data
value from a key.  This implementation uses an external hashing scheme,
called Dynamic Hashing, as described by Per-Aake Larson in BIT 18 (1978) pp.
184-201.  Retrieval of any item usually requires a single disk access.
The application interface is compatible with the
.IR ndbm (3)
library.
.LP
An
.B sdbm
database is kept in two files usually given the extensions
.B \.dir
and
.BR \.pag .
The
.B \.dir
file contains a bitmap representing a forest of binary hash trees, the leaves
of which indicate data pages in the
.B \.pag
file.
.LP
The application interface uses the
.B datum
structure to describe both
.I keys
and
.IR value s.
A
.B datum
specifies a byte sequence of
.I dsize
size pointed to by
.IR dptr .
If you use
.SM ASCII
strings as
.IR key s
or
.IR value s,
then you must decide whether or not to include the terminating
.SM NUL
byte which sometimes defines strings.  Including it will require larger
database files, but it will be possible to get sensible output from a
.IR strings (1)
command applied to the data file.
.LP
In order to allow a process using this package to manipulate multiple
databases, the applications interface always requires a
.IR handle ,
a
.BR "DBM *" ,
to identify the database to be manipulated.  Such a handle can be obtained
from the only routines that do not require it, namely
.BR dbm_open (\|)
or
.BR dbm_prep (\|).
Either of these will open or create the two necessary files.  The
difference is that the latter allows explicitly naming the bitmap and data
files whereas
.BR dbm_open (\|)
will take a base file name and call
.BR dbm_prep (\|)
with the default extensions.
The
.I flags
and
.I mode
parameters are the same as for
.BR open (2).
.LP
To free the resources occupied while a database handle is active, call
.BR dbm_close (\|).
.LP
Given a handle, one can retrieve data associated with a key by using the
.BR dbm_fetch (\|)
routine, and associate data with a key by using the
.BR dbm_store (\|)
routine.
.LP
The values of the
.I flags
parameter for
.BR dbm_store (\|)
can be either
.BR \s-1DBM_INSERT\s0 ,
which will not change an existing entry with the same key, or
.BR \s-1DBM_REPLACE\s0 ,
which will replace an existing entry with the same key.
Keys are unique within the database.
.LP
To delete a key and its associated value use the
.BR dbm_delete (\|)
routine.
.LP
To retrieve every key in the database, use a loop like:
.sp
.nf
.ft B
for (key = dbm_firstkey(db); key.dptr != NULL; key = dbm_nextkey(db))
        ;
.ft R
.fi
.LP
The order of retrieval is unspecified.
.LP
If you determine that the performance of the database is inadequate or
you notice clustering or other effects that may be due to the hashing
algorithm used by this package, you can override it by supplying your
own
.BR dbm_hash (\|)
routine.  Doing so will make the database unintelligable to any other
applications that do not use your specialized hash function.
.sp
.LP
The following macros are defined in the header file:
.IP
.BR dbm_rdonly (\|)
returns true if the database has been opened read\-only.
.IP
.BR dbm_error (\|)
returns true if an I/O error has occurred.
.IP
.BR dbm_clearerr (\|)
allows you to clear the error flag if you think you know what the error
was and insist on ignoring it.
.IP
.BR dbm_dirfno (\|)
returns the file descriptor associated with the bitmap file.
.IP
.BR dbm_pagfno (\|)
returns the file descriptor associated with the data file.
.SH SEE ALSO
.IR open (2).
.SH DIAGNOSTICS
Functions that return a
.B "DBM *"
handle will use
.SM NULL
to indicate an error.
Functions that return an
.B int
will use \-1 to indicate an error.  The normal return value in that case is 0.
Functions that return a
.B datum
will return
.B nullitem
to indicate an error.
.LP
As a special case of
.BR dbm_store (\|),
if it is called with the
.B \s-1DBM_INSERT\s0
flag and the key already exists in the database, the return value will be 1.
.LP
In general, if a function parameter is invalid,
.B errno
will be set to
.BR \s-1EINVAL\s0 .
If a write operation is requested on a read-only database,
.B errno
will be set to
.BR \s-1ENOPERM\s0 .
If a memory allocation (using
.IR malloc (3))
failed,
.B errno
will be set to
.BR \s-1ENOMEM\s0 .
For I/O operation failures
.B errno
will contain the value set by the relevant failed system call, either
.IR read (2),
.IR write (2),
or
.IR lseek (2).
.SH AUTHOR
.IP "Ozan S. Yigit" (oz@nexus.yorku.ca)
.SH BUGS
The sum of key and value data sizes must not exceed
.B \s-1PAIRMAX\s0
(1008 bytes).
.LP
The sum of the key and value data sizes where several keys hash to the
same value must fit within one bitmap page.
.LP
The
.B \.pag
file will contain holes, so its apparent size is larger than its contents.
When copied through the filesystem the holes will be filled.
.LP
The contents of
.B datum
values returned are in volatile storage.  If you want to retain the values
pointed to, you must copy them immediately before another call to this package.
.LP
The only safe way for multiple processes to (read and) update a database at
the same time, is to implement a private locking scheme outside this package
and open and close the database between lock acquisitions.  It is safe for
multiple processes to concurrently access a database read-only.
.SH APPLICATIONS PORTABILITY
For complete source code compatibility with the Berkeley Unix
.IR ndbm (3)
library, the 
.B sdbm.h
header file should be installed in
.BR /usr/include/ndbm.h .
.LP
The
.B nullitem
data item, and the
.BR dbm_prep (\|),
.BR dbm_hash (\|),
.BR dbm_rdonly (\|),
.BR dbm_dirfno (\|),
and
.BR dbm_pagfno (\|)
functions are unique to this package.
SHAR_EOF
fi # end of overwriting check
if test -f 'sdbm.c'
then
	echo shar: will not over-write existing file "'sdbm.c'"
else
cat << \SHAR_EOF > 'sdbm.c'
/*
 * sdbm - ndbm work-alike hashed database library
 * based on Per-Aake Larson's Dynamic Hashing algorithms.
 * BIT 18 (1978).
 *
 * Copyright (c) 1991 by Ozan S. Yigit
 *
 * Permission to use, copy, modify, and distribute this software and its
 * documentation for any purpose and without fee is hereby granted,
 * provided that the above copyright notice appear in all copies and that
 * both that copyright notice and this permission notice appear in
 * supporting documentation.
 *
 * This file is provided AS IS with no warranties of any kind.  The author
 * shall have no liability with respect to the infringement of copyrights,
 * trade secrets or any patents by this file or any part thereof.  In no
 * event will the author be liable for any lost revenue or profits or
 * other special, indirect and consequential damages.
 *
 *			oz@nexus.yorku.ca
 *
 *			Ozan S. Yigit
 *			Dept. of Computing and Communication Svcs.
 *			Steacie Science Library. T103
 *			York University
 *			4700 Keele Street, North York
 *			Ontario M3J 1P3
 *			Canada
 */

#include "sdbm.h"
#include "tune.h"

#include <sys/types.h>
#include <sys/stat.h>
#ifdef BSD42
#include <sys/file.h>
#else
#include <fcntl.h>
#include <memory.h>
#endif
#include <errno.h>
#include <string.h>

#ifdef __STDC__
#include <stddef.h>
#endif

#ifndef NULL
#define NULL	0
#endif

/*
 * externals
 */
#ifndef sun
extern int errno;
#endif

extern char *malloc proto((unsigned int));
extern void free proto((void *));
extern long lseek();

/*
 * forward
 */
static int getdbit proto((DBM *, long));
static int setdbit proto((DBM *, long));
static int getpage proto((DBM *, long));
static datum getnext proto((DBM *));
static int makroom proto((DBM *, long, int));

static int fitpair proto((char *, int));
static void  putpair proto((char *, datum, datum));
static datum	getpair proto((char *, datum));
static int  delpair proto((char *, datum));
static int  chkpage proto((char *));
static datum getnkey proto((char *, int));
static void splpage proto((char *, char *, long));
#ifdef SEEDUPS
static int duppair proto((char *, datum));
#endif

/*
 * useful macros
 */
#ifdef NULLKEY
#define bad(x)		((x).dsize < 0)
#else
#define bad(x)		((x).dptr == NULL || (x).dsize <= 0)
#endif
#define exhash(item)	dbm_hash((item).dptr, (item).dsize)
#define ioerr(db)	((db)->flags |= DBM_IOERR)

#define OFF_PAG(off)	(long) (off) * PBLKSIZ
#define OFF_DIR(off)	(long) (off) * DBLKSIZ

static long masks[] = {
	000000000000, 000000000001, 000000000003, 000000000007,
	000000000017, 000000000037, 000000000077, 000000000177,
	000000000377, 000000000777, 000000001777, 000000003777,
	000000007777, 000000017777, 000000037777, 000000077777,
	000000177777, 000000377777, 000000777777, 000001777777,
	000003777777, 000007777777, 000017777777, 000037777777,
	000077777777, 000177777777, 000377777777, 000777777777,
	001777777777, 003777777777, 007777777777, 017777777777
};

datum nullitem = {NULL, 0};

DBM *
dbm_open(file, flags, mode)
register char *file;
register int flags;
register int mode;
{
	register DBM *db;
	register char *dirname;
	register char *pagname;
	register int n;

	if (file == NULL || !*file)
		return errno = EINVAL, (DBM *) NULL;
/*
 * need space for two seperate filenames
 */
	n = strlen(file) * 2 + strlen(DIRFEXT) + strlen(PAGFEXT) + 2;

	if ((dirname = malloc((unsigned) n)) == NULL)
		return errno = ENOMEM, (DBM *) NULL;
/*
 * build the file names
 */
	dirname = strcat(strcpy(dirname, file), DIRFEXT);
	pagname = strcpy(dirname + strlen(dirname) + 1, file);
	pagname = strcat(pagname, PAGFEXT);

	db = dbm_prep(dirname, pagname, flags, mode);
	free((char *) dirname);
	return db;
}

DBM *
dbm_prep(dirname, pagname, flags, mode)
char *dirname;
char *pagname;
int flags;
int mode;
{
	register DBM *db;
	struct stat dstat;

	if ((db = (DBM *) malloc(sizeof(DBM))) == NULL)
		return errno = ENOMEM, (DBM *) NULL;

        db->flags = 0;
        db->hmask = 0;
        db->blkptr = 0;
        db->keyptr = 0;
/*
 * adjust user flags so that WRONLY becomes RDWR, 
 * as required by this package. Also set our internal
 * flag for RDONLY if needed.
 */
	if (flags & O_WRONLY)
		flags = (flags & ~O_WRONLY) | O_RDWR;

	else if ((flags & 03) == O_RDONLY)
		db->flags = DBM_RDONLY;
/*
 * open the files in sequence, and stat the dirfile.
 * If we fail anywhere, undo everything, return NULL.
 */
	if ((db->pagf = open(pagname, flags, mode)) > -1) {
		if ((db->dirf = open(dirname, flags, mode)) > -1) {
/*
 * need the dirfile size to establish max bit number.
 */
			if (fstat(db->dirf, &dstat) == 0) {
/*
 * zero size: either a fresh database, or one with a single,
 * unsplit data page: dirpage is all zeros.
 */
				db->dirbno = (!dstat.st_size) ? 0 : -1;
				db->pagbno = -1;
				db->maxbno = dstat.st_size * BYTESIZ;

				(void) memset(db->pagbuf, 0, PBLKSIZ);
				(void) memset(db->dirbuf, 0, DBLKSIZ);
			/*
			 * success
			 */
				return db;
			}
			(void) close(db->dirf);
		}
		(void) close(db->pagf);
	}
	free((char *) db);
	return (DBM *) NULL;
}

void
dbm_close(db)
register DBM *db;
{
	if (db == NULL)
		errno = EINVAL;
	else {
		(void) close(db->dirf);
		(void) close(db->pagf);
		free((char *) db);
	}
}

datum
dbm_fetch(db, key)
register DBM *db;
datum key;
{
	if (db == NULL || bad(key))
		return errno = EINVAL, nullitem;

	if (getpage(db, exhash(key)))
		return getpair(db->pagbuf, key);

	return ioerr(db), nullitem;
}

int
dbm_delete(db, key)
register DBM *db;
datum key;
{
	if (db == NULL || bad(key))
		return errno = EINVAL, -1;
	if (dbm_rdonly(db))
		return errno = EPERM, -1;

	if (getpage(db, exhash(key))) {
		if (!delpair(db->pagbuf, key))
			return -1;
/*
 * update the page file
 */
		if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
		    || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
			return ioerr(db), -1;

		return 0;
	}

	return ioerr(db), -1;
}

int
dbm_store(db, key, val, flags)
register DBM *db;
datum key;
datum val;
int flags;
{
	int need;
	register long hash;

	if (db == NULL || bad(key))
		return errno = EINVAL, -1;
	if (dbm_rdonly(db))
		return errno = EPERM, -1;

	need = key.dsize + val.dsize;
/*
 * is the pair too big (or too small) for this database ??
 */
	if (need < 0 || need > PAIRMAX)
		return errno = EINVAL, -1;

	if (getpage(db, (hash = exhash(key)))) {
/*
 * if we need to replace, delete the key/data pair
 * first. If it is not there, ignore.
 */
		if (flags == DBM_REPLACE)
			(void) delpair(db->pagbuf, key);
#ifdef SEEDUPS
		else if (duppair(db->pagbuf, key))
			return 1;
#endif
/*
 * if we do not have enough room, we have to split.
 */
		if (!fitpair(db->pagbuf, need))
			if (!makroom(db, hash, need))
				return ioerr(db), -1;
/*
 * we have enough room or split is successful. insert the key,
 * and update the page file.
 */
		(void) putpair(db->pagbuf, key, val);

		if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
		    || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
			return ioerr(db), -1;
	/*
	 * success
	 */
		return 0;
	}

	return ioerr(db), -1;
}

/*
 * makroom - make room by splitting the overfull page
 * this routine will attempt to make room for SPLTMAX times before
 * giving up.
 */
static int
makroom(db, hash, need)
register DBM *db;
long hash;
int need;
{
	long newp;
	char twin[PBLKSIZ];
	char *pag = db->pagbuf;
	char *new = twin;
	register int smax = SPLTMAX;

	do {
/*
 * split the current page
 */
		(void) splpage(pag, new, db->hmask + 1);
/*
 * address of the new page
 */
		newp = (hash & db->hmask) | (db->hmask + 1);

/*
 * write delay, read avoidence/cache shuffle:
 * select the page for incoming pair: if key is to go to the new page,
 * write out the previous one, and copy the new one over, thus making
 * it the current page. If not, simply write the new page, and we are
 * still looking at the page of interest. current page is not updated
 * here, as dbm_store will do so, after it inserts the incoming pair.
 */
		if (hash & (db->hmask + 1)) {
			if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
			    || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
				return 0;
			db->pagbno = newp;
			(void) memcpy(pag, new, PBLKSIZ);
		}
		else if (lseek(db->pagf, OFF_PAG(newp), SEEK_SET) < 0
			 || write(db->pagf, new, PBLKSIZ) < 0)
			return 0;

		if (!setdbit(db, db->curbit))
			return 0;
/*
 * see if we have enough room now
 */
		if (fitpair(pag, need))
			return 1;
/*
 * try again... update curbit and hmask as getpage would have
 * done. because of our update of the current page, we do not
 * need to read in anything. BUT we have to write the current
 * [deferred] page out, as the window of failure is too great.
 */
		db->curbit = 2 * db->curbit +
			((hash & (db->hmask + 1)) ? 2 : 1);
		db->hmask |= db->hmask + 1;

		if (lseek(db->pagf, OFF_PAG(db->pagbno), SEEK_SET) < 0
		    || write(db->pagf, db->pagbuf, PBLKSIZ) < 0)
			return 0;

	} while (--smax);
/*
 * if we are here, this is real bad news. After SPLTMAX splits,
 * we still cannot fit the key. say goodnight.
 */
#ifdef BADMESS
	(void) write(2, "sdbm: cannot insert after SPLTMAX attempts.\n", 44);
#endif
	return 0;

}

/*
 * the following two routines will break if
 * deletions aren't taken into account. (ndbm bug)
 */
datum
dbm_firstkey(db)
register DBM *db;
{
	if (db == NULL)
		return errno = EINVAL, nullitem;
/*
 * start at page 0
 */
	if (lseek(db->pagf, OFF_PAG(0), SEEK_SET) < 0
	    || read(db->pagf, db->pagbuf, PBLKSIZ) < 0)
		return ioerr(db), nullitem;
	db->pagbno = 0;
	db->blkptr = 0;
	db->keyptr = 0;

	return getnext(db);
}

datum
dbm_nextkey(db)
register DBM *db;
{
	if (db == NULL)
		return errno = EINVAL, nullitem;
	return getnext(db);
}

/*
 * all important binary trie traversal
 */
static int
getpage(db, hash)
register DBM *db;
register long hash;
{
	register int hbit;
	register long dbit;
	register long pagb;

	dbit = 0;
	hbit = 0;
	while (dbit < db->maxbno && getdbit(db, dbit))
		dbit = 2 * dbit + ((hash & (1 << hbit++)) ? 2 : 1);

	debug(("dbit: %d...", dbit));

	db->curbit = dbit;
	db->hmask = masks[hbit];

	pagb = hash & db->hmask;
/*
 * see if the block we need is already in memory.
 * note: this lookaside cache has about 10% hit rate.
 */
	if (pagb != db->pagbno) { 
/*
 * note: here, we assume a "hole" is read as 0s.
 * if not, must zero pagbuf first.
 */
		if (lseek(db->pagf, OFF_PAG(pagb), SEEK_SET) < 0
		    || read(db->pagf, db->pagbuf, PBLKSIZ) < 0)
			return 0;
		if (!chkpage(db->pagbuf))
			return 0;
		db->pagbno = pagb;

		debug(("pag read: %d\n", pagb));
	}
	return 1;
}

static int
getdbit(db, dbit)
register DBM *db;
register long dbit;
{
	register long c;
	register long dirb;

	c = dbit / BYTESIZ;
	dirb = c / DBLKSIZ;

	if (dirb != db->dirbno) {
		if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0
		    || read(db->dirf, db->dirbuf, DBLKSIZ) < 0)
			return 0;
		db->dirbno = dirb;

		debug(("dir read: %d\n", dirb));
	}

	return db->dirbuf[c % DBLKSIZ] & (1 << dbit % BYTESIZ);
}

static int
setdbit(db, dbit)
register DBM *db;
register long dbit;
{
	register long c;
	register long dirb;

	c = dbit / BYTESIZ;
	dirb = c / DBLKSIZ;

	if (dirb != db->dirbno) {
		if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0
		    || read(db->dirf, db->dirbuf, DBLKSIZ) < 0)
			return 0;
		db->dirbno = dirb;

		debug(("dir read: %d\n", dirb));
	}

	db->dirbuf[c % DBLKSIZ] |= (1 << dbit % BYTESIZ);

	if (dbit >= db->maxbno)
		db->maxbno += DBLKSIZ * BYTESIZ;

	if (lseek(db->dirf, OFF_DIR(dirb), SEEK_SET) < 0
	    || write(db->dirf, db->dirbuf, DBLKSIZ) < 0)
		return 0;

	return 1;
}

/*
 * getnext - get the next key in the page, and if done with
 * the page, try the next page in sequence
 */
static datum
getnext(db)
register DBM *db;
{
	datum key;

	for (;;) {
		db->keyptr++;
		key = getnkey(db->pagbuf, db->keyptr);
		if (key.dptr != NULL)
			return key;
/*
 * we either run out, or there is nothing on this page..
 * try the next one... If we lost our position on the
 * file, we will have to seek.
 */
		db->keyptr = 0;
		if (db->pagbno != db->blkptr++)
			if (lseek(db->pagf, OFF_PAG(db->blkptr), SEEK_SET) < 0)
				break;
		db->pagbno = db->blkptr;
		if (read(db->pagf, db->pagbuf, PBLKSIZ) <= 0)
			break;
		if (!chkpage(db->pagbuf))
			break;
	}

	return ioerr(db), nullitem;
}

/*
 * page-level routines
 */

static int seepair proto((char *, int, char *, int));

/*
 * page format:
 *	+------------------------------+
 * ino	| n | keyoff | datoff | keyoff |
 * 	+------------+--------+--------+
 *	| datoff | - - - ---->	       |
 *	+--------+---------------------+
 *	|	 F R E E A R E A       |
 *	+--------------+---------------+
 *	|  <---- - - - | data          |
 *	+--------+-----+----+----------+
 *	|  key   | data     | key      |
 *	+--------+----------+----------+
 *
 * calculating the offsets for free area:  if the number
 * of entries (ino[0]) is zero, the offset to the END of
 * the free area is the block size. Otherwise, it is the
 * nth (ino[ino[0]]) entry's offset.
 */

static int
fitpair(pag, need)
char *pag;
int need;
{
	register int n;
	register int off;
	register int free;
	register short *ino = (short *) pag;

	off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
	free = off - (n + 1) * sizeof(short);
	need += 2 * sizeof(short);

	debug(("free %d need %d\n", free, need));

	return need <= free;
}

static void
putpair(pag, key, val)
char *pag;
datum key;
datum val;
{
	register int n;
	register int off;
	register short *ino = (short *) pag;

	off = ((n = ino[0]) > 0) ? ino[n] : PBLKSIZ;
/*
 * enter the key first
 */
	off -= key.dsize;
	(void) memcpy(pag + off, key.dptr, key.dsize);
	ino[n + 1] = off;
/*
 * now the data
 */
	off -= val.dsize;
	(void) memcpy(pag + off, val.dptr, val.dsize);
	ino[n + 2] = off;
/*
 * adjust item count
 */
	ino[0] += 2;
}

static datum
getpair(pag, key)
char *pag;
datum key;
{
	register int i;
	register int n;
	datum val;
	register short *ino = (short *) pag;

	if ((n = ino[0]) == 0)
		return nullitem;

	if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
		return nullitem;

	val.dptr = pag + ino[i + 1];
	val.dsize = ino[i] - ino[i + 1];
	return val;
}

#ifdef SEEDUPS
static int
duppair(pag, key)
char *pag;
datum key;
{
	register short *ino = (short *) pag;
	return ino[0] > 0 && seepair(pag, ino[0], key.dptr, key.dsize) > 0;
}
#endif

static datum
getnkey(pag, num)
char *pag;
int num;
{
	datum key;
	register int off;
	register short *ino = (short *) pag;

	num = num * 2 - 1;
	if (ino[0] == 0 || num > ino[0])
		return nullitem;

	off = (num > 1) ? ino[num - 1] : PBLKSIZ;

	key.dptr = pag + ino[num];
	key.dsize = off - ino[num];

	return key;
}

static int
delpair(pag, key)
char *pag;
datum key;
{
	register int n;
	register int i;
	register short *ino = (short *) pag;

	if ((n = ino[0]) == 0)
		return 0;

	if ((i = seepair(pag, n, key.dptr, key.dsize)) == 0)
		return 0;
/*
 * found the key. if it is the last entry
 * [i.e. i == n - 1] we just adjust the entry count.
 * hard case: move all data down onto the deleted pair,
 * shift offsets onto deleted offsets, and adjust them.
 * [note: 0 < i < n]
 */
	if (i < n - 1) {
		register int m;
		register char *dst = pag + (i == 1 ? PBLKSIZ : ino[i - 1]);
		register char *src = pag + ino[i + 1];
		register int   zoo = dst - src;

		debug(("free-up %d ", zoo));
/*
 * shift data/keys down
 */
		m = ino[i + 1] - ino[n];
#ifdef DUFF
#define MOVB 	*--dst = *--src

		if (m > 0) {
			register int loop = (m + 8 - 1) >> 3;

			switch (m & (8 - 1)) {
			case 0:	do {
				MOVB;	case 7:	MOVB;
			case 6:	MOVB;	case 5:	MOVB;
			case 4:	MOVB;	case 3:	MOVB;
			case 2:	MOVB;	case 1:	MOVB;
				} while (--loop);
			}
		}
#else
#ifdef MEMMOVE
		memmove(dst, src, m);
#else
		while (m--)
			*--dst = *--src;
#endif
#endif
/*
 * adjust offset index up
 */
		while (i < n - 1) {
			ino[i] = ino[i + 2] + zoo;
			i++;
		}
	}
	ino[0] -= 2;
	return 1;
}

/*
 * search for the key in the page.
 * return offset index in the range 0 < i < n.
 * return 0 if not found.
 */
static int
seepair(pag, n, key, siz)
char *pag;
register int n;
register char *key;
register int siz;
{
	register int i;
	register int off = PBLKSIZ;
	register short *ino = (short *) pag;

	for (i = 1; i < n; i += 2) {
		if (siz == off - ino[i] &&
		    memcmp(key, pag + ino[i], siz) == 0)
			return i;
		off = ino[i + 1];
	}
	return 0;
}

static void
splpage(pag, new, sbit)
char *pag;
char *new;
long sbit;
{
	datum key;
	datum val;

	register int n;
	register int off = PBLKSIZ;
	char cur[PBLKSIZ];
	register short *ino = (short *) cur;

	(void) memcpy(cur, pag, PBLKSIZ);
	(void) memset(pag, 0, PBLKSIZ);
	(void) memset(new, 0, PBLKSIZ);

	n = ino[0];
	for (ino++; n > 0; ino += 2) {
		key.dptr = cur + ino[0]; 
		key.dsize = off - ino[0];
		val.dptr = cur + ino[1];
		val.dsize = ino[0] - ino[1];
/*
 * select the page pointer (by looking at sbit) and insert
 */
		(void) putpair((exhash(key) & sbit) ? new : pag, key, val);

		off = ino[1];
		n -= 2;
	}

	debug(("%d split %d/%d\n", ((short *) cur)[0] / 2, 
	       ((short *) new)[0] / 2,
	       ((short *) pag)[0] / 2));
}

/*
 * check page sanity: 
 * number of entries should be something
 * reasonable, and all offsets in the index should be in order.
 * this could be made more rigorous.
 */
static int
chkpage(pag)
char *pag;
{
	register int n;
	register int off;
	register short *ino = (short *) pag;

	if ((n = ino[0]) < 0 || n > PBLKSIZ / sizeof(short))
		return 0;

	if (n > 0) {
		off = PBLKSIZ;
		for (ino++; n > 0; ino += 2) {
			if (ino[0] > off || ino[1] > off ||
			    ino[1] > ino[0])
				return 0;
			off = ino[1];
			n -= 2;
		}
	}
	return 1;
}

SHAR_EOF
fi # end of overwriting check
if test -f 'sdbm.h'
then
	echo shar: will not over-write existing file "'sdbm.h'"
else
cat << \SHAR_EOF > 'sdbm.h'
/*
 * sdbm - ndbm work-alike hashed database library
 * based on Per-Aake Larson's Dynamic Hashing algorithms.
 * BIT 18 (1978).
 *
 * Copyright (c) 1991 by Ozan S. Yigit (oz@nexus.yorku.ca)
 *
 * Permission to use, copy, modify, and distribute this software and its
 * documentation for any purpose and without fee is hereby granted,
 * provided that the above copyright notice appear in all copies and that
 * both that copyright notice and this permission notice appear in
 * supporting documentation.
 *
 * This file is provided AS IS with no warranties of any kind.  The author
 * shall have no liability with respect to the infringement of copyrights,
 * trade secrets or any patents by this file or any part thereof.  In no
 * event will the author be liable for any lost revenue or profits or
 * other special, indirect and consequential damages.
 */

#define DBLKSIZ 4096
#define PBLKSIZ 1024
#define PAIRMAX 1008			/* arbitrary on PBLKSIZ-N */
#define SPLTMAX	10			/* maximum allowed splits */
					/* for a single insertion */
#define DIRFEXT	".dir"
#define PAGFEXT	".pag"

typedef struct {
	int dirf;		       /* directory file descriptor */
	int pagf;		       /* page file descriptor */
	int flags;		       /* status/error flags, see below */
	long maxbno;		       /* size of dirfile in bits */
	long curbit;		       /* current bit number */
	long hmask;		       /* current hash mask */
	long blkptr;		       /* current block for nextkey */
	int keyptr;		       /* current key for nextkey */
	long blkno;		       /* current page to read/write */
	long pagbno;		       /* current page in pagbuf */
	char pagbuf[PBLKSIZ];	       /* page file block buffer */
	long dirbno;		       /* current block in dirbuf */
	char dirbuf[DBLKSIZ];	       /* directory file block buffer */
} DBM;

#define DBM_RDONLY	0x1	       /* data base open read-only */
#define DBM_IOERR	0x2	       /* data base I/O error */

/*
 * utility macros
 */
#define dbm_rdonly(db)		((db)->flags & DBM_RDONLY)
#define dbm_error(db)		((db)->flags & DBM_IOERR)

#define dbm_clearerr(db)	((db)->flags &= ~DBM_IOERR)  /* ouch */

#define dbm_dirfno(db)	((db)->dirf)
#define dbm_pagfno(db)	((db)->pagf)

typedef struct {
	char *dptr;
	int dsize;
} datum;

extern datum nullitem;

#ifdef __STDC__
#define proto(p) p
#else
#define proto(p) ()
#endif

/*
 * flags to dbm_store
 */
#define DBM_INSERT	0
#define DBM_REPLACE	1

/*
 * ndbm interface
 */
extern DBM *dbm_open proto((char *, int, int));
extern void dbm_close proto((DBM *));
extern datum dbm_fetch proto((DBM *, datum));
extern int dbm_delete proto((DBM *, datum));
extern int dbm_store proto((DBM *, datum, datum, int));
extern datum dbm_firstkey proto((DBM *));
extern datum dbm_nextkey proto((DBM *));

/*
 * other
 */
extern DBM *dbm_prep proto((char *, char *, int, int));
extern long dbm_hash proto((char *, int));
SHAR_EOF
fi # end of overwriting check
if test -f 'tune.h'
then
	echo shar: will not over-write existing file "'tune.h'"
else
cat << \SHAR_EOF > 'tune.h'
/*
 * sdbm - ndbm work-alike hashed database library
 * tuning and portability constructs [not nearly enough]
 * author: oz@nexus.yorku.ca
 */

#define BYTESIZ		8

#ifdef SVID
#include <unistd.h>
#endif

#ifdef BSD42
#define SEEK_SET	L_SET
#define	memset(s,c,n)	bzero(s, n)		/* only when c is zero */
#define	memcpy(s1,s2,n)	bcopy(s2, s1, n)
#define	memcmp(s1,s2,n)	bcmp(s1,s2,n)
#endif

/*
 * important tuning parms (hah)
 */

#define SEEDUPS			/* always detect duplicates */
#define BADMESS			/* generate a message for worst case:
				   cannot make room after SPLTMAX splits */
/*
 * misc
 */
#ifdef DEBUG
#define debug(x)	printf x
#else
#define debug(x)
#endif
SHAR_EOF
fi # end of overwriting check
if test -f 'util.c'
then
	echo shar: will not over-write existing file "'util.c'"
else
cat << \SHAR_EOF > 'util.c'
#include <stdio.h>
#ifdef SDBM
#include "sdbm.h"
#else
#include "ndbm.h"
#endif

void
oops(s1, s2)
register char *s1;
register char *s2;
{
	extern int errno, sys_nerr;
	extern char *sys_errlist[];
	extern char *progname;

	if (progname)
		fprintf(stderr, "%s: ", progname);
	fprintf(stderr, s1, s2);
	if (errno > 0 && errno < sys_nerr)
		fprintf(stderr, " (%s)", sys_errlist[errno]);
	fprintf(stderr, "\n");
	exit(1);
}

int
okpage(pag)
char *pag;
{
	register unsigned n;
	register off;
	register short *ino = (short *) pag;

	if ((n = ino[0]) > PBLKSIZ / sizeof(short))
		return 0;

	if (!n)
		return 1;

	off = PBLKSIZ;
	for (ino++; n; ino += 2) {
		if (ino[0] > off || ino[1] > off ||
		    ino[1] > ino[0])
			return 0;
		off = ino[1];
		n -= 2;
	}

	return 1;
}
SHAR_EOF
fi # end of overwriting check
#	End of shell archive
exit 0
