allbery@uunet.UU.NET (Brandon S. Allbery - comp.sources.misc) (12/13/89)
Posting-number: Volume 9, Issue 63
Submitted-by: wht%n4hgf@gatech.edu (Warren Tucker)
Archive-name: umdb/part01
This gaggle of programs uses a btree database to play around with masses
of UUCP maps. The stuff is not so much a finished product as a toolbox
for development of map-grokking tools. They are not efficient, but
might be useful. For more details, see the README
UMDBUILD builds the database.
UMDBDUP prints duplicate system names.
UMDBPATH prints expanded path information. IT CURRENTLY WORKS ONLY IF
YOU HAVE SMAIL (by 'smail -A').
---- Cut Here and unpack ----
#!/bin/sh
# This is umdb, a shell archive (shar 3.04)
# made 12/11/1989 01:41 UTC by gatech!kd4nc!n4hgf!wht (wht%n4hgf@gatech.edu)
# Source directory /u4/src/umdb
#
# existing files WILL be overwritten
#
# This is part 1 of a multipart archive
# do not concatenate these parts, unpack them in order with /bin/sh
#
# This shar contains:
# README
# Makefile
# btree.h
# funcdefs.h
# umdb.h
# btree.c
# diagnose.c
# umdbdup.c
# umdbpath.c
# umdbuild.c
# umdbutil.c
#
touch 2>&1 | fgrep '[-amc]' > /tmp/s3_touch$$
if [ -s /tmp/s3_touch$$ ]
then
TOUCH=can
else
TOUCH=cannot
fi
rm -f /tmp/s3_touch$$
if test -r s3_seq_.tmp
then echo "Must unpack archives in sequence!"
next=`cat s3_seq_.tmp`; echo "Please unpack part $next next"
exit 1; fi
echo "x - extracting README (Text)"
sed 's/^X//' << 'SHAR_EOF' > README &&
XUMDB Release x1.00 - Sun Dec 10 20:37:46 EST 1989
X
XThis gaggle of programs uses a btree database to play around with masses
Xof UUCP maps. The stuff is not so much a finished product as a toolbox
Xfor development of map-grokking tools. They are not efficient, but
Xmight be useful.
X
XTO MAKE:
X---------------------------------------------------------------------
XEdit the Makefile if you are not running on SCO UNIX or XENIX 386 or
Xa Pyramid in the BSD universe. Note that I have only tested the
Xprograms on SCO UNIX/XENIX and a Pyramid. It hasn't been tested, but
Xsome #defines are in the code for Sun.
X
XAdd to CFLAGS:
X-DBSD4 for a BSD or Sun system.
X-M2l for a XENIX 286 system. M_SYS5 provided by the compiler will do
Xthe rest.
XPyramid from the att universe, 'ucb make' :-).
X
XUMDBUILD
X---------------------------------------------------------------------
XUMDBUILD builds the database. To do it:
Xsu root
Xcd /.../.../map_directory
Xumdbbuild /.../.../map_directory/[du].*
XThis places the output database into /usr/lib/uucp/umdb.
XA name index is placed in /usr/lib/uucp/umdb.in.
XCode is present in the program to build a location index in
X/usr/lib/uucp/umdb.il, but since no programs use it, production
Xis turned off (to turn on, use -DBUILD_LOC_INDEX).
X
XUMDBDUP
X---------------------------------------------------------------------
XUMDBDUP prints duplicate system names. Example output:
Xpei (pei) in /u3/lib/pathalias/u.usa.ca.5
Xpei (pei) in /u3/lib/pathalias/u.usa.ca.8
Xpepper (pepper) in /u3/lib/pathalias/u.fin.1
Xpepper (pepper) in /u3/lib/pathalias/u.usa.co.1
Xpporta (pporta) in /u3/lib/pathalias/u.usa.az.1
Xpporta (pporta) in /u3/lib/pathalias/u.usa.ok.1
Xsoft (softcon) in /u3/lib/pathalias/u.deu.2
Xsoft (intra) in /u3/lib/pathalias/u.grc.1
Xsssphx (sssphx) in /u3/lib/pathalias/u.usa.az.1
Xsssphx (sssphx) in /u3/lib/pathalias/u.usa.ca.5
X
XUMDBPATH
X---------------------------------------------------------------------
XUMDBPATH prints expanded path information. IT CURRENTLY WORKS ONLY IF
XYOU HAVE SMAIL (by 'smail -A'). I would love to receive patches
Xfrom folks who get it working with other path generators.
XExample output (from n4hgf perspective):
X
X% umdbpath sco
Xpath: kd4nc!gatech!ames!sun!sco
Xkd4nc 33.7500 N 82.3833 W city (u.usa.ga.1)
X.gatech.edu 33.7753 N 84.3947 W (u.usa.ga.1)
Xames 37.4172 N 122.0575 W (u.usa.ca.2)
Xsun 37.4289 N 122.0969 W (u.usa.ca.8)
Xsco 36.9667 N 122.0500 W city (u.usa.ca.8)
X
X% umdbpath proxima
Xpath: kd4nc!gatech!ames!lll-winken!ddsw1!olsa99!tabbs!proxima
Xkd4nc 33.7500 N 82.3833 W city (u.usa.ga.1)
X.gatech.edu 33.7753 N 84.3947 W (u.usa.ga.1)
Xames 37.4172 N 122.0575 W (u.usa.ca.2)
Xlll-winken 37.6839 N 121.7106 W (u.usa.ca.6)
Xddsw1 42.2833 N 87.9667 W city (u.usa.il.1)
Xolsa99 26.0000 S 27.0000 E (u.zaf.1)
Xtabbs 26.0000 S 27.0000 E (u.zaf.1)
Xproxima 0.0000 N 0.0000 W ?? (u.zaf.1)
X
X% umdbpath oz
Xpath: kd4nc!gatech!mailrus!uunet!munnari
Xkd4nc 33.7500 N 82.3833 W city (u.usa.ga.1)
X.gatech.edu 33.7753 N 84.3947 W (u.usa.ga.1)
Xmailrus 42.2889 N 83.7144 W (u.usa.mi.2)
X.uu.net 38.8833 N 77.0667 W (u.usa.va.2)
Xmunnari not found: munnari.oz.au seems to match
Xmunnari.oz.au 37.8086 S 144.9617 E (u.aus.vic.1)
X
X^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^
X1st name on #N line latitude, latitude basename of map
X
X-N SWITCH
X---------------------------------------------------------------------
XAll of the above programs accept an optional -n <umdb> to specify
Xa database other than /u3/lib/uucp/umdb.
X
Xumdbbuild -n foo u.*
X
Xbuilds the databse in ./foo and the index in ./foo.in.
X
XDIAGNOSE
X---------------------------------------------------------------------
XDIAGNOSE is not made by default, but is included for those who want
Xto hack on or debug the btree. Thanks for the btree source to Marcus
XJ. Ranum, William Welch Medical Library (mjr@jhuigf.BITNET). Much
Xhacking was done on btree.c and btree.h to improve efficiency and to
Xtune it for this "large" an application. It also seemed not to work
Xreal great when I first got it, and I'm still not sure it won't
Xbreak, but it works fine on an SCO UNIX or XENIX 386 box and on a
XPyramid.
X
X---------------------------------------------------------------------
XWarren Tucker, Mountain Park, Georgia ...!gatech!kd4nc!n4hgf!wht
SHAR_EOF
chmod 0644 README || echo "restore of README fails"
if [ $TOUCH = can ]
then
touch -m 1210204189 README
fi
echo "x - extracting Makefile (Text)"
sed 's/^X//' << 'SHAR_EOF' > Makefile &&
X#------------------------------------------------------------------
X# Makefile for umdb - UUCP Map Database programs
X# ...!gatech!emory!tridom!wht
X#------------------------------------------------------------------
X#+:EDITS:
X#:12-09-1989-20:30-wht-creation
X
XSHELL = /bin/sh
XCFLAGS = -Ox -DLINT_ARGS
XLIB=
X
XSRC = \
X btree.c \
X umdbuild.c \
X umdbdup.c \
X umdbutil.c
X
XUMDBUILD_OBJ = \
X btree.o \
X umdbuild.o \
X umdbutil.o
X
XUMDBDUP_OBJ = \
X btree.o \
X umdbdup.o \
X umdbutil.o
X
XUMDBPATH_OBJ = \
X btree.o \
X umdbpath.o \
X umdbutil.o
X
XDIAGNOSE_OBJ = \
X btree.o \
X diagnose.o
X
Xall: umdbuild umdbdup umdbpath
X
Xumdbuild: $(UMDBUILD_OBJ)
X cc -o $@ $(UMDBUILD_OBJ) $(LIB)
X
Xumdbdup: $(UMDBDUP_OBJ)
X cc -o $@ $(UMDBDUP_OBJ) $(LIB)
X
Xumdbpath: $(UMDBPATH_OBJ)
X cc -o $@ $(UMDBPATH_OBJ) $(LIB)
X
Xdiagnose: $(DIAGNOSE_OBJ)
X cc -o $@ $(DIAGNOSE_OBJ) $(LIB)
X
X# using this method, can only build with MSC compiler
Xlint:
X ls $(SRC) > src.fls
X echo ' '> funcdefs.h
X csh ./zgcc src.fls funcdefs.h
X
Xshar:
X shar -c -numdb -o/tmp/umdb. -l36 README Makefile *.h *.c
SHAR_EOF
chmod 0644 Makefile || echo "restore of Makefile fails"
if [ $TOUCH = can ]
then
touch -m 1210202889 Makefile
fi
echo "x - extracting btree.h (Text)"
sed 's/^X//' << 'SHAR_EOF' > btree.h &&
X/*+-------------------------------------------------------------------------
X btree.h
X hacked by ...!gatech!kd4nc!n4hgf!wht
X
XCopyright (C) 1988, Marcus J. Ranum, William Welch Medical Library
X$Author: mjr $ $Log: btree.c,v $ Revision 1.1 88/06/01 21:35:07 mjr
XInitial revision
XThe original code was placed in the public domain. This is not, since I
Xwish to retain some control over it. No restrictions are placed on
Xmodification, or use of this code, as long as the copyrights are not
Xremoved. There are some areas that really could use improving (like
Xhandling free nodes better) and I hope that if someone makes
Ximprovements they will keep me up to date on them (e-mail please, I am
Xnot on usenet).
XMarcus J. Ranum, William Welch Medical Library, 1988
Xmjr@jhuigf.BITNET || uunet!mimsy!aplcen!osiris!welchvax!mjr
X--------------------------------------------------------------------------*/
X/*+:EDITS:*/
X/*:12-10-1989-18:03-wht-make cache much larger */
X/*:12-17-1988-19:52-wht-released 1.20 */
X/*:12-16-1988-20:38-wht-variable max key length */
X/*:12-16-1988-18:22-afterlint-creation */
X
X#ifndef _INCL_BTREE_H
X#define _INCL_BTREE_H 1
X
X#define BT_NREC 1 /* no such record */
X#define BT_EOF 2 /* end of the tree (either end) */
X#define BT_ERR -1 /* something went wrong */
X
X#define BT_KSIZ 60 /* size of keys to store (or trunc) */
X#define BT_CSIZ 4096 /* # of nodes to cache (power of two) */
X
X/* this indicates a node deleted */
X#define BT_DELETED 1
X#define BT_ACTIVE 0
X
X#define BT_MAGIC 0x0BB1
X
X/* btree stack */
X#define STACK_LENGTH 30 /* length of history stacks */
X
Xstruct btstack {
X short ele[STACK_LENGTH]; /* stack elements */
X short lev[STACK_LENGTH]; /* stack levels */
X short sptr; /* stack pointer */
X};
X
X/* a disk resident btree super block */
Xstruct btsuper {
X short magic; /* magic number */
X short keysize; /* maximum length of key */
X short root; /* pointer to root node */
X short free; /* pointer to next free (basically, EOF) */
X short list; /* number of active records */
X};
X
Xstruct btnode {
X long recno; /* index to external file, or whatever */
X short lptr; /* left-pointer */
X short rptr; /* right-pointer */
X char deleted; /* deleted flag */
X char balance; /* balance flag */
X};
X#define BTNODE struct btnode
X
Xstruct btnode_m
X{
X struct btnode n; /* keep these two ... */
X char key[BT_KSIZ]; /* ... fields FIRST !!! */
X short node_num; /* disk node number */
X short dirty; /* if true, cache item needs writing to disk */
X};
X
X/* a memory resident btree super block */
X/* including room to hold a disk super block */
Xstruct btree
X{
X int fd; /* file descriptor */
X struct btsuper sblk; /* copy of superblock */
X struct btstack rstak; /* history stack */
X struct btstack lstak; /* history stack */
X struct btnode_m *cache[BT_CSIZ]; /* read-only cache */
X short rdonly; /* true if file opened read-only */
X short slev; /* history stack level */
X};
X#define BTREE struct btree
X
XBTREE *btopen();
Xvoid btperror();
X
Xextern int bterrno; /* btree error number/flag */
Xextern char *bterrs[]; /* error message list */
X/* error codes - match bterrs */
X#define BT_BAD_MAGIC 1 /* bad index file magic number */
X#define BT_BAD_STACK 2 /* history stack overflow */
X#define BT_BAD_ROOT 3 /* failed attempt to delete node 0 */
X#define BT_BAD_KSIZ 4 /* keysize at open does not match index keysize */
X#define BT_BAD_MEMORY 5 /* memory allocation failed */
X#define BT_BAD_SBLK 6 /* bad superblock */
X#define BT_BAD_WSUPER 7 /* error writing superblock */
X#define BT_BAD_WNODE 8 /* error writing node */
X#define BT_BAD_RNODE 9 /* error reading node */
X#define BT_BAD_FLUSH 10 /* error flushing node */
X
X#endif /*_INCL_BTREE_H */
X/* vi: set tabstop=4 shiftwidth=4: */
X/* end of btree.h */
SHAR_EOF
chmod 0644 btree.h || echo "restore of btree.h fails"
if [ $TOUCH = can ]
then
touch -m 1210180489 btree.h
fi
echo "x - extracting funcdefs.h (Text)"
sed 's/^X//' << 'SHAR_EOF' > funcdefs.h &&
X/*+-----------------------------------------------------------------------
X funcdefs.h
X------------------------------------------------------------------------*/
X/*+:EDITS:*/
X/*:12-10-1989-15:27-afterlint-creation */
X
X#ifndef BUILDING_LINT_ARGS
X#ifdef LINT_ARGS
X
X/* btree.c */
Xint _bthead(short *,struct btnode_m *,struct btree *);
Xint _btnext(short *,struct btnode_m *,struct btree *);
Xint _btprevious(short *,struct btnode_m *,struct btree *);
Xint _bttail(short *,struct btnode_m *,struct btree *);
Xint _flush_cache_node(struct btree *,struct btnode_m *);
Xint _pushl(struct btree *,short );
Xint _pushr(struct btree *,short );
Xint _rnode(short ,struct btnode_m *,struct btree *);
Xint _wnode(short ,struct btnode_m *,struct btree *);
Xint _wsuper(struct btree *);
Xint btclose(struct btree *);
Xint btdelete(short ,struct btree *);
Xint btfind(char *,short *,char **,long *,struct btree *);
Xint btflush(struct btree *);
Xint bthead(short *,char **,long *,struct btree *);
Xint btinsert(char *,long ,struct btree *);
Xint btnext(short *,char **,long *,struct btree *);
Xint btprevious(short *,char **,long *,struct btree *);
Xint btsetrec(short ,long ,struct btree *);
Xint bttail(short *,char **,long *,struct btree *);
Xshort _popl(struct btree *);
Xshort _popr(struct btree *);
Xstruct btree *btopen(char *,int ,int ,int );
Xvoid _btlink(int ,struct btnode *,int ,struct btnode *);
Xvoid _linknbr(int ,struct btnode *,short );
Xvoid _nbrlink(short *,int ,struct btnode *);
Xvoid _nodebal(int ,struct btnode *,struct btnode *,struct btnode *);
Xvoid btperror(char *);
X/* umdbdup.c */
Xint main(int ,char **,char **);
Xvoid print_dup_umdb_rec(long );
X/* umdbuild.c */
Xint main(int ,char **,char **);
Xvoid mapfile_to_mapdb(char *);
X/* umdbutil.c */
Xchar *arg_token(char *,char *);
Xchar *normalize_location(char *);
Xchar *normalized_loc_to_str(char *);
Xint array_to_angle(char **,int ,double *);
Xvoid build_arg_array(char *,char **,int ,int *,char *);
Xvoid build_dbfld_array(char *,char **,int ,int *);
Xvoid build_normalized_locfld(char *,double ,double ,int );
Xvoid build_sitename_array(char *,char **,int ,int *);
X
X#else /* compiler doesn't know about prototyping */
X
X/* btree.c */
Xshort _popl();
Xshort _popr();
Xstruct btree *btopen();
Xvoid _btlink();
Xvoid _linknbr();
Xvoid _nbrlink();
Xvoid _nodebal();
Xvoid btperror();
X/* umdbdup.c */
Xvoid print_dup_umdb_rec();
X/* umdbuild.c */
Xvoid mapfile_to_mapdb();
X/* umdbutil.c */
Xchar *arg_token();
Xchar *normalize_location();
Xchar *normalized_loc_to_str();
Xvoid build_arg_array();
Xvoid build_dbfld_array();
Xvoid build_normalized_locfld();
Xvoid build_sitename_array();
X
X#endif /* LINT_ARGS */
X#endif /* BUILDING_LINT_ARGS */
X
X/* end of funcdefs.h */
SHAR_EOF
chmod 0644 funcdefs.h || echo "restore of funcdefs.h fails"
if [ $TOUCH = can ]
then
touch -m 1210180489 funcdefs.h
fi
echo "x - extracting umdb.h (Text)"
sed 's/^X//' << 'SHAR_EOF' > umdb.h &&
X/*+-------------------------------------------------------------------------
X umdb.h - uucp map database definitions
X ...!gatech!emory!tridom!wht
X--------------------------------------------------------------------------*/
X/*+:EDITS:*/
X/*:12-09-1989-18:18-wht-creation */
X
X#include "funcdefs.h"
X
X/* maximum length of system name (remember .dom.dom.ad.nauseam) */
X#define SYSNAME_MAXLEN 40
X
X/* length of normailed location (latitude/logitude) field */
X#define LOC_LEN 24 /* don't change w/o studying code */
X
X/* max sitenames per #N or other text line */
X#define MAX_SITENAMES_PER_LINE 20 /* plenty! - avoid overflow tomorrow */
X
X/* max systems in a path */
X#define MAX_SYSTEMS_PER_PATH 50 /* plenty! - avoid overflow tomorrow */
X
X/* count of fields in umdb main db record */
X#define DBFLD_NLOC 0 /* normalized location */
X#define DBFLD_SNAME 1 /* site name */
X#define DBFLD_MNAME 2 /* map file name */
X#define DBFLD_MPOS 3 /* map file position of #N line */
X#define DBFLD_COUNT 4
X
X/* angle type definitions */
X#define ANGLE_LATITUDE 1
X#define ANGLE_LONGITUDE 2
X#define ANGLE_BAD -1
X
X/* vi: set tabstop=4 shiftwidth=4: */
X/* end of umdb.h */
SHAR_EOF
chmod 0644 umdb.h || echo "restore of umdb.h fails"
if [ $TOUCH = can ]
then
touch -m 1210180489 umdb.h
fi
echo "x - extracting btree.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > btree.c &&
X/*#define DEBUG*/
X/*+-------------------------------------------------------------------------
X btree.c
X hacked by ...!gatech!kd4nc!n4hgf!wht
X
XCopyright (C) 1988, Marcus J. Ranum, William Welch Medical Library
X$Author: mjr $ $Log: btree.c,v $ Revision 1.1 88/06/01 21:35:07 mjr
XInitial revision
XThe original code was placed in the public domain. This is not, since I
Xwish to retain some control over it. No restrictions are placed on
Xmodification, or use of this code, as long as the copyrights are not
Xremoved. There are some areas that really could use improving (like
Xhandling free nodes better) and I hope that if someone makes
Ximprovements they will keep me up to date on them (e-mail please, I am
Xnot on usenet).
XMarcus J. Ranum, William Welch Medical Library, 1988
Xmjr@jhuigf.BITNET || uunet!mimsy!aplcen!osiris!welchvax!mjr
X
X Defined functions:
X _bthead(node_num,node,bt)
X _btlink(alpha1,node1,alpha2,node2)
X _btnext(node_num,node,bt)
X _btprevious(node_num,node,bt)
X _bttail(node_num,node,bt)
X _flush_cache_node(bt,cache_node)
X _linknbr(alpha,node1,node_num)
X _nbrlink(node_num,alpha,node1)
X _nodebal(alpha,node1,node2,node3)
X _popl(bt)
X _popr(bt)
X _pushl(bt,node_num)
X _pushr(bt,node_num)
X _rnode(node_num,npt,bt)
X _wnode(node_num,npt,bt)
X _wsuper(bt)
X btclose(bt)
X btdelete(node_num,bt)
X btfind(key,node_num,reckey,recno,bt)
X btflush(bt)
X bthead(node_num,key,recno,bt)
X btinsert(argkey,recno,bt)
X btnext(node_num,key,recno,bt)
X btopen(path,flags,mode,keysize)
X btperror(str)
X btprevious(node_num,key,recno,bt)
X btsetrec(node_num,newrec,bt)
X bttail(node_num,key,recno,bt)
X
X--------------------------------------------------------------------------*/
X/*+:EDITS:*/
X/*:12-09-1989-17:29-wht-get working on SCO UNIX -- just #defines */
X/*:12-17-1988-17:51-wht-write sblk only at close-writes were inefficient */
X/*:12-17-1988-17:51-wht-cache now read-write... writes were inefficient */
X/*:12-17-1988-12:09-wht-allow open of existing index to specify zero keysize */
X/*:12-16-1988-20:38-wht-variable max key length */
X/*:12-16-1988-17:15-wht-static procs no longer static, but with '_' prefix */
X
X
X#include <stdio.h>
X#include <errno.h>
X#include "funcdefs.h"
X
X#define ff fprintf
X#define se stderr
X
X#if defined(pyr) || defined(sun) || defined(BSD4)
X#include <sys/file.h>
X#endif
X
X#if defined(M_SYS5) || defined(SYS5)
X#include <sys/fcntl.h>
X#define bcopy(dest,src,len) memcpy(src,dest,len)
X#define bzero(dest,len) memset(dest,0,len)
X#endif
X
X#include "btree.h"
X
Xlong cache_hits = 0;
Xlong cache_no_hits = 0;
X
X#define BT_NSIZ (sizeof(struct btnode) + bt->sblk.keysize)
X#define BT_SSIZ (sizeof(struct btsuper))
Xlong lseek();
X
X/* the errno for btree problems. we use negative # - */
X/* so btperror can use the real UNIX errno */
Xint bterrno = 0;
Xchar *bterrs[] =
X{
X "No btree error",
X "Bad index magic number (is this an index file?)",
X "History stack overflow",
X "Cannot delete node zero",
X "Open keysize does not match index keysize",
X "Memory allocation failure",
X "Bad superblock (is this an index file?)",
X "error writing superblock",
X "error writing node",
X "error reading node",
X "error flushing node",
X 0
X};
X
X/* write the btree superblock to disk */
Xint
X_wsuper(bt)
Xstruct btree *bt;
X{
Xregister int save_bterrno = bterrno;
X
X if(bt->rdonly)
X return(0);
X
X#ifdef DEBUG
X ff(se,"-------> write superblock fd=%d\n",bt->fd);
X#endif
X
X bterrno = BT_BAD_WSUPER;
X if(lseek(bt->fd,0L,0) < 0)
X return(BT_ERR);
X
X if(write(bt->fd,(char *)&bt->sblk,BT_SSIZ) != BT_SSIZ)
X return(BT_ERR);
X
X bterrno = save_bterrno;
X return(0);
X}
X
X
X
X/* dynamically allocate a control structure for an open btree */
Xstruct btree *
Xbtopen(path,flags,mode,keysize)
Xchar *path;
Xregister int flags;
Xregister int mode;
Xregister int keysize;
X{
X struct btree *bt;
X register int r;
X extern char *malloc();
X
X if(keysize)
X {
X keysize++; /* allow for null at end of record */
X if(keysize & 1)
X keysize++; /* keep even */
X }
X if(keysize > BT_KSIZ)
X {
X fprintf(stderr,"key size specified for %s (%d) exceeds max of %d\n",
X path,keysize,BT_KSIZ);
X exit(1);
X }
X
X
X /* lets be dynamic, shall we ? */
X if((bt = (struct btree *) malloc(sizeof(struct btree))) == (BTREE *)0)
X {
X bterrno = BT_BAD_MEMORY;
X return((BTREE *)0);
X }
X
X if((bt->fd = open(path,flags,mode)) > -1)
X {
X#ifdef DEBUG
X ff(se,"----------> open '%s' fd=%d\n",path,bt->fd);
X#endif
X r = read(bt->fd,(char *) &bt->sblk,BT_SSIZ);
X
X /* if read nothing, must be a new guy, right ? */
X if(r == 0)
X {
X bt->sblk.magic = BT_MAGIC;
X bt->sblk.free = 1;
X bt->sblk.root = 0;
X bt->sblk.list = 0;
X if(keysize)
X bt->sblk.keysize = keysize;
X else
X {
X printf("cannot create new index with max keysize == 0\n");
X exit(1);
X }
X
X if(_wsuper(bt) == 0)
X r = BT_SSIZ;
X }
X else if(r == BT_SSIZ)
X {
X bterrno = 0;
X if(bt->sblk.magic != BT_MAGIC)
X bterrno = BT_BAD_MAGIC;
X else if(keysize && (keysize != bt->sblk.keysize))
X bterrno = BT_BAD_KSIZ;
X if(bterrno)
X {
X close(bt->fd);
X free((char *) bt);
X return((BTREE *)0);
X }
X }
X
X /* cleverly check ret value from either read or write */
X if(r != BT_SSIZ)
X {
X bterrno = BT_BAD_SBLK;
X close(bt->fd);
X free((char *) bt);
X return((BTREE *)0);
X }
X }
X else
X {
X /* couldnt even open the bloody file */
X free((char *) bt);
X return((BTREE *)0);
X }
X
X /* zero the cache -- will fail at 65535 records :-) */
X for(r = 0; r < BT_CSIZ; r++)
X {
X if((bt->cache[r] = (struct btnode_m *)malloc(sizeof(struct btnode_m)))
X == (struct btnode_m *)0)
X {
X ff(se,"no memory for cache\n");
X exit(1);
X }
X bt->cache[r]->node_num = -1;
X bt->cache[r]->dirty = 0;
X }
X bt->rdonly = ((flags & (O_WRONLY | O_RDWR)) == O_RDONLY);
X
X return(bt);
X}
X
X/* close and deallocate the control structure */
Xbtclose(bt)
Xstruct btree *bt;
X{
X register int err = 0;
X register int icache;
X
X if(!bt->rdonly)
X {
X if(err = btflush(bt))
X printf("======== ERROR WRITING TO DISK ON CLOSE ==========\n");
X }
X close(bt->fd);
X for(icache = 0; icache < BT_CSIZ; icache++)
X free((char *)bt->cache[icache]);
X free((char *) bt);
X return(err);
X}
X
Xint
X_flush_cache_node(bt,cache_node)
Xstruct btree *bt;
Xregister struct btnode_m *cache_node;
X{
Xregister int save_bterrno = bterrno;
X
X if((cache_node->node_num == -1) || (!cache_node->dirty))
X return(0);
X bterrno = BT_BAD_FLUSH;
X if(lseek(bt->fd,(((long)cache_node->node_num * BT_NSIZ) + BT_SSIZ),0) < 0)
X return(BT_ERR);
X if(write(bt->fd,(char *)&cache_node->n,BT_NSIZ) != BT_NSIZ)
X return(BT_ERR);
X cache_node->dirty = 0;
X bterrno = save_bterrno;
X return(0);
X}
X
Xint
Xbtflush(bt)
Xstruct btree *bt;
X{
X register int icache;
X register struct btnode_m *cache_node;
X
X for(icache = 0; icache < BT_CSIZ; icache++)
X {
X cache_node = bt->cache[icache];
X if(_flush_cache_node(bt,cache_node))
X return(BT_ERR);
X }
X if(_wsuper(bt))
X return(BT_ERR);
X return(0);
X}
X
X/* write a node to cache */
Xint
X_wnode(node_num,npt,bt)
Xregister short node_num;
Xstruct btnode_m *npt;
Xregister struct btree *bt;
X{
X unsigned int hash = (unsigned int)node_num & (BT_CSIZ - 1);
X register struct btnode_m *cache_node = bt->cache[hash];
X extern int errno;
X
X#ifdef DEBUG
X ff(se,"_wnode(node_num=%d,fd=%d)\n",node_num,bt->fd);
X ff(se," cache node_num=%d\n",cache_node->node_num);
X#endif
X
X if(!node_num)
X return(0);
X
X errno = 0;
X if(bt->rdonly)
X {
X errno = EPERM; /* would be reported later */
X return(BT_ERR);
X }
X bterrno = BT_BAD_WNODE;
X if(cache_node->node_num != node_num)
X {
X if(_flush_cache_node(bt,cache_node))
X return(BT_ERR);
X }
X
X /* update cache - if the write succeeded */
X (void)bcopy((char *)npt,(char *)cache_node,sizeof(struct btnode_m));
X cache_node->node_num = node_num;
X cache_node->dirty = 1;
X bterrno = 0;
X return(0);
X}
X
X/* read a node from disk */
Xint
X_rnode(node_num,npt,bt)
Xregister short node_num;
Xregister struct btnode_m *npt;
Xregister struct btree *bt;
X{
X register rdcount;
X register long readpos;
X unsigned int hash = (unsigned int)node_num & (BT_CSIZ - 1);
X register struct btnode_m *cache_node = bt->cache[hash];
X extern int errno;
X
X#ifdef DEBUG
X ff(se,"_rnode(node_num=%d,fd=%d)\n",node_num,bt->fd);
X ff(se," cache node_num=%d\n",cache_node->node_num);
X#endif
X
X if(!node_num)
X {
X (void)bzero((char *)npt,sizeof(struct btnode_m));
X return(0);
X }
X
X errno = 0;
X bterrno = BT_BAD_RNODE;
X if(cache_node->node_num != node_num)
X {
X /* if no cache hit, load from disk */
X cache_no_hits++;
X if(!bt->rdonly)
X {
X if(_flush_cache_node(bt,cache_node))
X return(BT_ERR);
X }
X if(lseek(bt->fd,(readpos = ((long)node_num * BT_NSIZ) + BT_SSIZ),0) < 0)
X return(BT_ERR);
X if((rdcount = read(bt->fd,(char *)&cache_node->n,BT_NSIZ)) != BT_NSIZ)
X {
X#ifdef DEBUG
X if(rdcount >= 0)
X ff(se,"rdcount for node %u was % (should be %d) @ %ld\n",
X node_num,rdcount,BT_NSIZ,readpos);
X#endif
X return(BT_ERR);
X }
X cache_node->node_num = node_num;
X cache_node->dirty = 0;
X }
X else
X cache_hits++;
X
X (void)bcopy((char *)cache_node,(char *)npt,sizeof(struct btnode_m));
X
X bterrno = 0;
X return(0);
X}
X
Xint
X_pushl(bt,node_num)
Xstruct btree *bt;
Xregister short node_num;
X{
X if(++ (bt->lstak.sptr) >= STACK_LENGTH)
X {
X bterrno = BT_BAD_STACK;
X exit(0);
X }
X bt->lstak.ele[bt->lstak.sptr] = node_num;
X bt->lstak.lev[bt->lstak.sptr] = ++bt->slev;
X return;
X}
X
X
Xint
X_pushr(bt,node_num)
Xstruct btree *bt;
Xregister short node_num;
X{
X if(++ (bt->rstak.sptr) >= STACK_LENGTH)
X {
X bterrno = BT_BAD_STACK;
X exit(0);
X }
X bt->rstak.ele[bt->rstak.sptr] = node_num;
X bt->rstak.lev[bt->rstak.sptr] = ++bt->slev;
X return;
X}
X
X
X
Xshort
X_popr(bt)
Xstruct btree *bt;
X{
X
X bt->slev = bt->rstak.lev[bt->rstak.sptr];
X
X while(bt->lstak.lev[bt->lstak.sptr] > bt->slev)
X (bt->lstak.sptr)--;
X
X if(bt->rstak.sptr == 0)
X return(0);
X
X bt->slev--;
X return(bt->rstak.ele[(bt->rstak.sptr)--]);
X}
X
X
X
Xshort
X_popl(bt)
Xstruct btree *bt;
X{
X
X bt->slev = bt->lstak.lev[bt->lstak.sptr];
X
X while(bt->rstak.lev[bt->rstak.sptr] > bt->slev)
X (bt->rstak.sptr)--;
X
X if(bt->lstak.sptr == 0)
X return(0);
X
X bt->slev--;
X return(bt->lstak.ele[(bt->lstak.sptr)--]);
X}
X
Xvoid
X_btlink(alpha1,node1,alpha2,node2)
Xregister int alpha1;
Xregister int alpha2;
Xstruct btnode *node1;
Xstruct btnode *node2;
X{
X if(alpha1 == -1 && alpha2 == -1)
X node1->lptr = node2->lptr;
X else if(alpha1 == -1 && alpha2 == 1)
X node1->lptr = node2->rptr;
X else if(alpha1 == 1 && alpha2 == -1)
X node1->rptr = node2->lptr;
X else
X node1->rptr = node2->rptr;
X}
X
X
X
X/* number a link according to alpha */
Xvoid
X_nbrlink(node_num,alpha,node1)
Xshort *node_num;
Xregister int alpha;
Xstruct btnode *node1;
X{
X *node_num = (alpha == 1) ? node1->rptr : node1->lptr;
X}
X
X
X
X/* set a link according to alpha */
Xvoid
X_linknbr(alpha,node1,node_num)
Xregister int alpha;
Xstruct btnode *node1;
Xregister short node_num;
X{
X
X if(alpha == 1)
X node1->rptr = node_num;
X else
X node1->lptr = node_num;
X}
X
X
X
Xvoid
X_nodebal(alpha,node1,node2,node3)
Xregister int alpha;
Xstruct btnode *node1;
Xstruct btnode *node2;
Xstruct btnode *node3;
X{
X
X if(node1->balance == alpha)
X {
X node2->balance = -alpha;
X node3->balance = 0;
X }
X else if(node1->balance == 0)
X node2->balance = node3->balance = 0;
X else
X {
X node2->balance = 0;
X node3->balance = alpha;
X }
X}
X
X
X
X/* change the record number in a node */
Xbtsetrec(node_num,newrec,bt)
Xregister short node_num;
Xlong newrec;
Xstruct btree *bt;
X{
X struct btnode_m tnode;
X
X if(_rnode(node_num,&tnode,bt))
X return(BT_ERR);
X
X tnode.n.recno = newrec;
X
X if(_wnode(node_num,&tnode,bt))
X return(BT_ERR);
X
X return(0);
X}
X
X/* insert the node into the tree */
Xbtinsert(argkey,recno,bt)
Xchar *argkey;
Xlong recno;
Xstruct btree *bt;
X{
X register int compare;
X short trec1;
X short trec2;
X short trec3;
X short trec4;
X short top;
X struct btnode_m tnode1;
X struct btnode_m tnode2;
X struct btnode_m tnode3;
X struct btnode_m tnode4;
X
X
X /* the very first node gets inserted specially */
X if(bt->sblk.root == 0)
X {
X bt->sblk.root = 1;
X tnode1.n.balance = tnode1.n.rptr = tnode1.n.lptr = 0;
X tnode1.n.deleted = BT_ACTIVE;
X tnode1.n.recno = recno;
X
X strncpy(tnode1.key,argkey,bt->sblk.keysize - 1);
X tnode1.key[bt->sblk.keysize - 1] = '\0';
X if(_wnode(1,&tnode1,bt) < 0)
X return(BT_ERR);
X
X bt->sblk.free++;
X bt->sblk.list++;
X return(0);
X }
X top = -1;
X trec1 = bt->sblk.root;
X trec4 = bt->sblk.root;
X while(1)
X {
X if(_rnode(trec1,&tnode1,bt))
X {
X#ifdef DEBUG
X ff(se,"btinsert: trec1(1) read error\n");
X#endif
X return(BT_ERR);
X }
X if((compare = strcmp(argkey,tnode1.key)) < 0)
X {
X /* (move left) */
X trec2 = tnode1.n.lptr;
X
X if(trec2 == 0)
X {
X /* insert here */
X trec2 = bt->sblk.free++;
X tnode1.n.lptr = trec2;
X break; /* loop exit */
X }
X else
X {
X /* look again from this node */
X if(_rnode(trec2,&tnode2,bt))
X {
X#ifdef DEBUG
X ff(se,"btinsert: trec2(1) read error\n");
X#endif
X return(BT_ERR);
X }
X if(tnode2.n.balance != 0)
X {
X top = trec1;
X trec4 = trec2;
X }
X }
X trec1 = trec2;
X }
X else
X {
X /* (move right) */
X trec2 = tnode1.n.rptr;
X
X if(trec2 == 0)
X {
X /* insert here */
X trec2 = bt->sblk.free++;
X tnode1.n.rptr = trec2;
X break; /* loop exit */
X }
X else
X {
X /* look again from this node */
X if(_rnode(trec2,&tnode2,bt))
X {
X#ifdef DEBUG
X ff(se,"btinsert: trec2(2) read error\n");
X#endif
X return(BT_ERR);
X }
X if(tnode2.n.balance != 0)
X {
X top = trec1;
X trec4 = trec2;
X }
X trec1 = trec2;
X }
X }
X }
X
X /* Step 5 (insert key at tnode2) */
X tnode2.n.lptr = tnode2.n.rptr = 0;
X tnode2.n.balance = 0;
X tnode2.n.deleted = BT_ACTIVE;
X tnode2.n.recno = recno;
X strncpy(tnode2.key,argkey,bt->sblk.keysize - 1);
X tnode2.key[bt->sblk.keysize - 1] = '\0';
X
X if(_wnode(trec2,&tnode2,bt))
X return(BT_ERR);
X if(_wnode(trec1,&tnode1,bt))
X return(BT_ERR);
X if(_rnode(trec4,&tnode4,bt))
X {
X#ifdef DEBUG
X ff(se,"btinsert: trec4(1) read error\n");
X#endif
X return(BT_ERR);
X }
X
X /* (adjust balance factors) */
X if(strcmp(argkey,tnode4.key) < 0)
X trec3 = trec1 = tnode4.n.lptr;
X else
X trec3 = trec1 = tnode4.n.rptr;
X
X while(trec1 != trec2)
X {
X if(_rnode(trec1,&tnode1,bt))
X {
X#ifdef DEBUG
X ff(se,"btinsert: trec1(2) read error\n");
X#endif
X return(BT_ERR);
X }
X if(strcmp(argkey,tnode1.key) < 0)
X {
X tnode1.n.balance = -1;
X if(_wnode(trec1,&tnode1,bt) < 0)
X return(BT_ERR);
X trec1 = tnode1.n.lptr;
X }
X else
X {
X tnode1.n.balance = 1;
X if(_wnode(trec1,&tnode1,bt) < 0)
X return(BT_ERR);
X trec1 = tnode1.n.rptr;
X }
X }
X
X compare = (strcmp(argkey,tnode4.key) < 0) ? -1 : 1;
X if(tnode4.n.balance == 0)
X {
X bt->sblk.list++;
X tnode4.n.balance = compare;
X if(_wnode(trec4,&tnode4,bt) < 0)
X return(BT_ERR);
X return(0);
X }
X else if(tnode4.n.balance == -compare)
X {
X bt->sblk.list++;
X tnode4.n.balance = 0;
X if(_wnode(trec4,&tnode4,bt) < 0)
X return(BT_ERR);
X return(0);
X }
X else
X {
X /* (tree out of balance) */
X bt->sblk.list++;
X if(_rnode(trec4,&tnode4,bt))
X {
X#ifdef DEBUG
X ff(se,"btinsert: trec4(2) read error\n");
X#endif
X return(BT_ERR);
X }
X if(_rnode(trec3,&tnode3,bt))
X {
X#ifdef DEBUG
X ff(se,"btinsert: trec3(1) read error\n");
X#endif
X return(BT_ERR);
X }
X if(tnode3.n.balance == compare)
X {
X /* (single rotate) */
X trec1 = trec3;
X _btlink(compare,(BTNODE *) &tnode4,-compare,(BTNODE *) &tnode3);
X _linknbr(-compare,(BTNODE *) &tnode3,trec4);
X tnode4.n.balance = tnode3.n.balance = 0;
X }
X else
X {
X /* (double rotate) */
X _nbrlink(&trec1,-compare,(BTNODE *) &tnode3);
X if(_rnode(trec1,&tnode1,bt))
X {
X#ifdef DEBUG
X ff(se,"btinsert: trec1(3) read error\n");
X#endif
X return(BT_ERR);
X }
X _btlink(-compare,(BTNODE *) &tnode3,compare,(BTNODE *) &tnode1);
X _linknbr(compare,(BTNODE *) &tnode1,trec3);
X _btlink(compare,(BTNODE *) &tnode4,-compare,(BTNODE *) &tnode1);
X _linknbr(-compare,(BTNODE *) &tnode1,trec4);
X _nodebal(compare,(BTNODE *) &tnode1,(BTNODE *) &tnode4,(BTNODE *) &tnode3);
X tnode1.n.balance = 0;
X if(_wnode(trec1,&tnode1,bt))
X return(BT_ERR);
X }
X
X if(top == -1)
X bt->sblk.root = trec1;
X else
X {
X /* balanced at top of a sub-tree */
X if(_rnode(top,&tnode2,bt) < 0)
X {
X#ifdef DEBUG
X ff(se,"btinsert: top(1) read error\n");
X#endif
X return(BT_ERR);
X }
X if(trec4 == tnode2.n.rptr)
X tnode2.n.rptr = trec1;
X else
X tnode2.n.lptr = trec1;
X if(_wnode(top,&tnode2,bt))
X return(BT_ERR);
X }
X if(_wnode(trec4,&tnode4,bt))
X return(BT_ERR);
X if(_wnode(trec3,&tnode3,bt))
X return(BT_ERR);
X return(0);
X }
X}
X
X/* drop a node */
Xbtdelete(node_num,bt)
Xregister short node_num;
Xstruct btree *bt;
X{
X struct btnode_m node;
X
X if(node_num == 0)
X {
X bterrno = BT_BAD_ROOT;
X return(BT_ERR);
X }
X else
X {
X if(_rnode(node_num,&node,bt))
X return(BT_ERR);
X node.n.deleted = BT_DELETED;
X if(_wnode(node_num,&node,bt))
X return(BT_ERR);
X else
X bt->sblk.list--;
X }
X return(0);
X}
X
X/* find the next node */
Xbtnext(node_num,key,recno,bt)
Xshort *node_num;
Xchar **key;
Xlong *recno;
Xstruct btree *bt;
X{
X static struct btnode_m node;
X register int retn;
X if(_rnode(*node_num,&node,bt))
X return(BT_ERR);
X retn = _btnext(node_num,&node,bt);
X *key = node.key;
X *recno = node.n.recno;
X return(retn);
X}
X
X
X/* find the next node */
X_btnext(node_num,node,bt)
Xshort *node_num;
Xregister struct btnode_m *node;
Xstruct btree *bt;
X{
X short _popl();
X short _popr();
X short s_nod;
X
X s_nod = *node_num;
X
X if(*node_num == 0)
X {
X /* undefined current node - wind to beginning of file */
X return(_bthead(node_num,node,bt));
X }
X do
X {
X if(node->n.rptr == 0)
X {
X /* can't move right */
X if(bt->lstak.sptr == 0)
X {
X /* none in stack */
X if(_rnode(*node_num,node,bt))
X return(BT_ERR);
X return(BT_EOF);
X }
X else
X {
X /* can't go right & stack full (pop stack) */
X s_nod = _popl(bt);
X if(_rnode(s_nod,node,bt) < 0)
X return(BT_ERR);
X }
X }
X else
X {
X /* move right */
X _pushr(bt,s_nod);
X s_nod = node->n.rptr;
X if(_rnode(s_nod,node,bt) )
X return(BT_ERR);
X
X while(node->n.lptr != 0)
X {
X /* bottom left */
X _pushl(bt,s_nod);
X /* of this sub-tree */
X s_nod = node->n.lptr;
X if(_rnode(s_nod,node,bt))
X return(BT_ERR);
X }
X }
X } while(node->n.deleted == BT_DELETED);
X
X *node_num = s_nod;
X return(0);
X}
X
X/* go to the tail of the file */
Xbttail(node_num,key,recno,bt)
Xshort *node_num;
Xchar **key;
Xlong *recno;
Xstruct btree *bt;
X{
X static struct btnode_m node;
X register int retn = _bttail(node_num,&node,bt);
X *key = node.key;
X *recno = node.n.recno;
X return(retn);
X}
X
X/* go to the tail of the file */
X_bttail(node_num,node,bt)
Xshort *node_num;
Xregister struct btnode_m *node;
Xstruct btree *bt;
X{
X short s_nod;
X
X bt->rstak.sptr = 0;
SHAR_EOF
echo "End of umdb part 1"
echo "File btree.c is continued in part 2"
echo "2" > s3_seq_.tmp
exit 0