allbery@uunet.UU.NET (Brandon S. Allbery - comp.sources.misc) (06/12/89)
Posting-number: Volume 7, Issue 30
Submitted-by: fox@marlow.UUCP (Paul Fox)
Archive-name: crisp1.9/part10
#!/bin/sh
# this is part 2 of a multipart archive
# do not concatenate these parts, unpack them in order with /bin/sh
# file dirlib/vmsdir.c continued
#
CurArch=2
if test ! -r s2_seq_.tmp
then echo "Please unpack part 1 first!"
exit 1; fi
( read Scheck
if test "$Scheck" != $CurArch
then echo "Please unpack part $Scheck next!"
exit 1;
else exit 0; fi
) < s2_seq_.tmp || exit 1
echo "x - Continuing file dirlib/vmsdir.c"
sed 's/^X//' << 'SHAR_EOF' >> dirlib/vmsdir.c
X Copyright (C) 1985, 1986, 1987, 1988 Free Software Foundation, Inc.
X
XThis file is part of GNU Emacs.
X
XGNU Emacs is distributed in the hope that it will be useful,
Xbut WITHOUT ANY WARRANTY. No author or distributor
Xaccepts responsibility to anyone for the consequences of using it
Xor for whether it serves any particular purpose or works at all,
Xunless he says so in writing. Refer to the GNU Emacs General Public
XLicense for full details.
X
XEveryone is granted permission to copy, modify and redistribute
XGNU Emacs, but only under the conditions described in the
XGNU Emacs General Public License. A copy of this license is
Xsupposed to have been given to you along with GNU Emacs so you
Xcan know your rights and responsibilities. It should be in a
Xfile named COPYING. Among other things, the copyright notice
Xand this notice must be preserved on all copies. */
X
X/* This file has been hacked by P. Fox on 2 Jan 1989 to allow
X/* GRIEF to work under VMS. Unfortunately this file has not
X/* been merged with the dirlib files. */
X
X#include <rms.h>
X#include <ttdef.h>
X#include <tt2def.h>
X#include <iodef.h>
X#include <ssdef.h>
X#include <descrip.h>
X#include <ctype.h>
X#include <file.h>
X#include <stat.h>
X#ifndef RAB$C_BID
X#include <rab.h>
X#endif
X
X#include "vmsdir.h"
X
XDIR *
Xopendir (filename)
X char *filename; /* name of directory */
X{
X register DIR *dirp; /* -> malloc'ed storage */
X register int fd; /* file descriptor for read */
X struct stat sbuf; /* result of fstat() */
X
X fd = open (filename, O_RDONLY);
X if (fd < 0)
X return 0;
X
X if (fstat (fd, &sbuf) < 0
X || (sbuf.st_mode & S_IFMT) != S_IFDIR
X || (dirp = (DIR *) malloc (sizeof (DIR))) == 0)
X {
X close (fd);
X return 0; /* bad luck today */
X }
X
X dirp->dd_fd = fd;
X dirp->dd_loc = dirp->dd_size = 0; /* refill needed */
X
X return dirp;
X}
X
Xvoid
Xclosedir (dirp)
X register DIR *dirp; /* stream from opendir() */
X{
X close (dirp->dd_fd);
X free ((char *) dirp);
X}
X
X
Xstruct direct dir_static; /* simulated directory contents */
X
X/* ARGUSED */
Xstruct direct *
Xreaddir (dirp)
X register DIR *dirp; /* stream from opendir() */
X{
X register struct dir$_name *dp; /* -> directory data */
X register struct dir$_version *dv; /* -> version data */
X
X for (; ;)
X {
X if (dirp->dd_loc >= dirp->dd_size)
X dirp->dd_loc = dirp->dd_size = 0;
X
X if (dirp->dd_size == 0 /* refill buffer */
X && (dirp->dd_size = sys_read (dirp->dd_fd, dirp->dd_buf, DIRBLKSIZ)) <= 0)
X return 0;
X
X dp = (struct dir$_name *) dirp->dd_buf;
X if (dirp->dd_loc == 0)
X dirp->dd_loc = (dp->dir$b_namecount&1) ? dp->dir$b_namecount + 1
X : dp->dir$b_namecount;
X dv = (struct dir$_version *)&dp->dir$t_name[dirp->dd_loc];
X dir_static.d_ino = dv->dir$w_fid_num;
X dir_static.d_namlen = dp->dir$b_namecount;
X dir_static.d_reclen = sizeof (struct direct)
X - MAXNAMLEN + 3
X + dir_static.d_namlen - dir_static.d_namlen % 4;
X strncpy (dir_static.d_name, dp->dir$t_name, dp->dir$b_namecount);
X dir_static.d_name[dir_static.d_namlen] = '\0';
X dirp->dd_loc = dirp->dd_size; /* only one record at a time */
X return &dir_static;
X }
X}
X
X/* readdirver is just like readdir except it returns all versions of a file
X as separate entries. */
X
X/* ARGUSED */
Xstruct direct *
Xreaddirver (dirp)
X register DIR *dirp; /* stream from opendir() */
X{
X register struct dir$_name *dp; /* -> directory data */
X register struct dir$_version *dv; /* -> version data */
X
X if (dirp->dd_loc >= dirp->dd_size - sizeof (struct dir$_name))
X dirp->dd_loc = dirp->dd_size = 0;
X
X if (dirp->dd_size == 0 /* refill buffer */
X && (dirp->dd_size = sys_read (dirp->dd_fd, dirp->dd_buf, DIRBLKSIZ)) <= 0)
X return 0;
X
X dp = (struct dir$_name *) dirp->dd_buf;
X if (dirp->dd_loc == 0)
X dirp->dd_loc = (dp->dir$b_namecount & 1) ? dp->dir$b_namecount + 1
X : dp->dir$b_namecount;
X dv = (struct dir$_version *) &dp->dir$t_name[dirp->dd_loc];
X strncpy (dir_static.d_name, dp->dir$t_name, dp->dir$b_namecount);
X sprintf (&dir_static.d_name[dp->dir$b_namecount], ";%d", dv->dir$w_version);
X dir_static.d_namlen = strlen (dir_static.d_name);
X dir_static.d_ino = dv->dir$w_fid_num;
X dir_static.d_reclen = sizeof (struct direct) - MAXNAMLEN + 3
X + dir_static.d_namlen - dir_static.d_namlen % 4;
X dirp->dd_loc = ((char *) (++dv) - dp->dir$t_name);
X return &dir_static;
X}
SHAR_EOF
echo "File dirlib/vmsdir.c is complete"
chmod 0644 dirlib/vmsdir.c || echo "restore of dirlib/vmsdir.c fails"
mkdir foxlib >/dev/null 2>&1
echo "x - extracting foxlib/Makefile (Text)"
sed 's/^X//' << 'SHAR_EOF' > foxlib/Makefile &&
XL = lib
XARC = ../$(L)/foxlib.a
XSRC = Makefile *.h *.c
X
XOBJ = \
X $(ARC)(ansi.o) \
X $(ARC)(atol.o) \
X $(ARC)(chk_alloc.o) \
X $(ARC)(dname.o) \
X $(ARC)(expand.o) \
X $(ARC)(instr.o) \
X $(ARC)(rename.o) \
X $(ARC)(sname.o) \
X $(ARC)(strdup.o) \
X $(ARC)(tell.o)
X
X$(ARC): $(OBJ)
X -test -f /bin/ranlib && ranlib $(ARC)
X
Xdist:
X sccs update < /dev/null
Xdist-list:
X @echo $(SRC)
X
Xxenix.386:
X $(MAKE) XFLAGS="-M3" RANLIB=ranlib
Xxenix.286:
X $(MAKE) XFLAGS="-M2l -K" RANLIB=ranlib
Xrtpc:
X $(MAKE)
Xuport.286:
X $(MAKE)
Xuport.386:
X $(MAKE)
Xsun:
X $(MAKE) RANLIB=ranlib
X
SHAR_EOF
chmod 0644 foxlib/Makefile || echo "restore of foxlib/Makefile fails"
mkdir foxlib >/dev/null 2>&1
echo "x - extracting foxlib/chk_alloc.h (Text)"
sed 's/^X//' << 'SHAR_EOF' > foxlib/chk_alloc.h &&
X# if !defined(_CHK_ALLOC_H)
X# define _CHK_ALLOC_H
Xextern char *check_alloc(), *chk_alloc();
Xextern char *check_realloc(), *chk_realloc();
Xextern void chk_free();
Xextern void *vm_alloc();
X
X/*# define WHERE /* Define this if you want to trace where the */
X /* malloc()'s are being called from. */
X/*# define TAIL /* Define this if you want to check that the end*/
X /* of a malloc-ed area is being overwritten. */
X# define VM_ALLOC /* If not defined, then vm_alloc's turn into */
X /* normal alloc's for better error checking. */
X
X# define chk_alloc(size) check_alloc(size, __FILE__, __LINE__)
X# define chk_realloc(ptr, size) check_realloc(ptr, size)
X# define chk_free(ptr) check_free(ptr)
X# if !defined(VM_ALLOC)
X# define vm_alloc(size, ptr) chk_alloc(size)
X# define vm_free(ptr, chain) chk_free(ptr)
X# endif
X# endif /* _CHK_ALLOC_H */
SHAR_EOF
chmod 0666 foxlib/chk_alloc.h || echo "restore of foxlib/chk_alloc.h fails"
mkdir foxlib >/dev/null 2>&1
echo "x - extracting foxlib/ansi.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > foxlib/ansi.c &&
X# include <stdio.h>
X
Xstatic enum {e_normal, e_bold, e_init} mode = e_init;
X
Xstatic char *text[] = {
X "\033[30m",
X "\033[31m",
X "\033[32m",
X "\033[33m",
X "\033[34m",
X "\033[35m",
X "\033[36m",
X "\033[37m",
X "\033[1m\033[30m",
X "\033[1m\033[31m",
X "\033[1m\033[32m",
X "\033[1m\033[33m",
X "\033[1m\033[34m",
X "\033[1m\033[35m",
X "\033[1m\033[36m",
X "\033[1m\033[37m",
X };
X
Xesc(str)
Xchar *str;
X{
X printf("\033%s", str);
X fflush(stdout);
X}
Xcls() { esc("[H"); esc("[2J"); }
Xchar *t_cls() { return "\033[H\033[2J"; }
Xbold()
X{
X if (mode != e_bold)
X esc("[1m");
X mode = e_bold;
X}
Xchar *
Xt_bold()
X{
X if (mode != e_bold)
X return "\033[1m";
X return "";
X}
Xchar *
Xt_normal()
X{
X if (mode != e_normal)
X return "\033[0m";
X return "";
X}
Xnormal()
X{
X if (mode != e_normal)
X esc("[0m");
X mode = e_normal;
X}
Xmove(x,y)
X{
X printf("\033[%d;%dH", x, y);
X fflush(stdout);
X}
Xblink()
X{
X esc("[5m");
X}
Xsteady()
X{
X esc("[0m");
X}
Xstatic char *s = "%s";
X
X# define FN(n1, n2, n3, n4, n) \
X n1() { printf(s, text[n]); fflush(stdout); } \
X n2() { printf(s, text[8+n]); fflush(stdout); } \
X char *n3() { return text[n]; } \
X char *n4() { return text[8+n]; }
X
XFN(black, lt_black, t_black, t_lt_black, 0)
XFN(red, lt_red, t_red, t_lt_red, 1)
XFN(green, lt_green, t_green, t_lt_green, 2)
XFN(yellow, lt_yellow, t_yellow, t_lt_yellow, 3)
XFN(blue, lt_blue, t_blue, t_lt_blue, 4)
XFN(magnenta, lt_magenta, t_magenta, t_lt_magenta, 5)
XFN(cyan, lt_cyan, t_cyan, t_lt_cyan, 6)
XFN(white, lt_white, t_white, t_lt_white, 7)
SHAR_EOF
chmod 0644 foxlib/ansi.c || echo "restore of foxlib/ansi.c fails"
mkdir foxlib >/dev/null 2>&1
echo "x - extracting foxlib/atol.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > foxlib/atol.c &&
Xlong
Xatol(str)
Xregister char *str;
X{ int positive = 1;
X register int d;
X long n = 0;
X
X while (*str == ' ' || *str == '\t')
X str++;
X if (*str == '+')
X str++;
X else if (*str == '-')
X positive = 0, str++;
X
X while ((d = *str++ - '0') >= 0 && d <= 9)
X n = 10 * n + d;
X return positive ? n : -n;
X}
X
X
X
SHAR_EOF
chmod 0644 foxlib/atol.c || echo "restore of foxlib/atol.c fails"
mkdir foxlib >/dev/null 2>&1
echo "x - extracting foxlib/bsearch.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > foxlib/bsearch.c &&
Xchar *
Xbsearch(name, tbl, size, sizeof_one, compare)
Xchar *name;
Xchar *tbl;
Xint (*compare)();
X{ int l = 0;
X int u = size-1;
X int res, m;
X char *p;
X
X while (1) {
X if (l > u)
X return (char *) 0;
X m = (l + u) / 2;
X p = tbl + (sizeof_one * m);
X res = (*compare)(name, p);
X if (res > 0)
X l = m + 1;
X else if (res == 0)
X return p;
X else
X u = m - 1;
X }
X
X}
X
SHAR_EOF
chmod 0644 foxlib/bsearch.c || echo "restore of foxlib/bsearch.c fails"
mkdir foxlib >/dev/null 2>&1
echo "x - extracting foxlib/chk_alloc.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > foxlib/chk_alloc.c &&
X/* Routine sitting on top of malloc() to aid in debugging. */
X
X# include <stdio.h>
X# include "chk_alloc.h"
Xextern char *malloc();
X
X# define TAIL_MAGIC 0x5441494c /* TAIL */
X# define MAGIC 0x464f5859L /* FOXY */
X# define FREED 0x46524545L /* FREE */
X
X# define MAX_FILE 80
X
Xint cnt_alloc = 0;
Xstruct tail {
X long magic;
X struct info *next;
X };
X
Xstruct info {
X long magic;
X# if defined(TAIL)
X struct tail *tail;
X# endif
X# if defined(WHERE)
X char file[MAX_FILE];
X# endif
X };
Xstatic struct info *alloc_chain = NULL;
X# if defined(TAIL)
Xvoid check_tail();
Xstatic void tail_remove();
Xstatic void tail_add();
X# endif
X
Xchar *
Xcheck_alloc(n, file, line)
Xchar *file;
X{ register char *cp;
X register struct info *ip;
X
X# if defined(TAIL)
X check_tail();
X n += sizeof (struct tail);
X# endif
X n += sizeof(struct info);
X cp = malloc(n);
X ip = (struct info *) cp;
X
X if (ip) {
X ip->magic = MAGIC;
X# if defined(TAIL)
X tail_add(ip, n);
X# endif
X# if defined(WHERE)
X sprintf(ip->file, "FILE: %s LINE: %d", file, line);
X# endif
X cp = (char *) (ip + 1);
X cnt_alloc++;
X }
X
X return cp;
X}
Xchar *
Xcheck_realloc(ptr, n)
Xchar *ptr;
X{ char *realloc();
X struct info *ip = (struct info *) ptr;
X struct info *new_ip;
X
X ip--;
X if (ip->magic != MAGIC)
X check_failed("Realloc non-alloced memory.");
X n += sizeof(struct info);
X# if defined(TAIL)
X n += sizeof(struct tail);
X# endif
X new_ip = (struct info *) realloc((char *) ip, n);
X# if defined(TAIL)
X check_tail();
X tail_remove(ip);
X tail_add(new_ip, n);
X# endif
X return (char *) (new_ip + 1);
X}
Xvoid
Xcheck_free(ptr)
Xchar *ptr;
X{ struct info *ip = (struct info *) ptr;
X
X ip--;
X if (ip->magic == FREED)
X check_failed("Trying to free already freed memory.");
X if (ip->magic != MAGIC)
X check_failed("Freeing non-alloced memory.");
X cnt_alloc--;
X# if defined(TAIL)
X tail_remove(ip);
X# endif
X ip->magic = FREED;
X free((char *) ip);
X}
Xcheck_failed(str)
Xchar *str;
X{
X fprintf(stderr, "CHK_ALLOC: %s\r\n", str);
X abort();
X}
X# if defined(TAIL)
Xvoid
Xcheck_tail()
X{ register struct info *ip;
X int i;
X for (ip = alloc_chain, i = 0; ip; ip = ip->tail->next, i++)
X if (ip->tail->magic != TAIL_MAGIC)
X check_failed("Overwritten past end of malloc() area.", i);
X}
Xstatic void
Xtail_add(ip, n)
Xstruct info *ip;
X{
X ip->tail = (struct tail *) ((char *) ip + n - sizeof(struct tail));
X ip->tail->magic = TAIL_MAGIC;
X ip->tail->next = alloc_chain;
X alloc_chain = ip;
X}
Xstatic void
Xtail_remove(ip)
Xstruct info *ip;
X{ register struct info *ip1;
X
X if (ip == alloc_chain)
X alloc_chain = ip->tail->next;
X else
X for (ip1 = alloc_chain; ip1->tail->next; ip1 = ip1->tail->next)
X if (ip1->tail->next == ip) {
X ip1->tail->next = ip->tail->next;
X break;
X }
X}
X# endif
X/* Following handles code compiled without including the
X/* chk_alloc.h file. */
X# if defined(chk_alloc)
X# undef chk_alloc
X# endif
X# if defined(chk_realloc)
X# undef chk_realloc
X# endif
X# if defined(chk_free)
X# undef chk_free
X# endif
X
Xchar *
Xchk_alloc(size)
X{
X return check_alloc(size, "DON'T KNOW", 1962);
X}
Xchar *
Xchk_realloc(ptr, size)
Xchar *ptr;
X{
X return check_realloc(ptr, size);
X}
Xvoid
Xchk_free(ptr)
Xchar *ptr;
X{
X check_free(ptr);
X}
X/* Following code can be used to find out how slow malloc really is !!.
XOn V.3 Unix running Microport I got a 6 minutes elapsed time
Xversus 4 seconds for this test !!.
XOn a Sun 3/260 + 8MB of memory I got a 5x improvement.
X*/
X# if 0
X# include <stdio.h>
Xchar *malloc();
Xextern void free();
Xchar *(*fn_malloc)() = malloc;
Xvoid (*fn_free)() = free;
X
X# define chk_alloc malloc
Xint mem_count = 0;
Xchar *freelist;
Xmain(argc, argv)
Xchar **argv;
X{
X int i;
X char *ptrs[100000];
X if (argc > 1) {
X char *vm_alloc();
X void vm_free();
X fn_malloc = vm_alloc;
X fn_free = vm_free;
X }
X# define SIZE (sizeof ptrs / sizeof ptrs[0])
X# define MALLOC(a,b) (*fn_malloc)(a, b)
X# define FREE(a, b) (*fn_free)(a, b)
X
X for (i = 0; i < SIZE; i++)
X ptrs[i] = MALLOC(16, &freelist);
X printf("Freeing %d bytes\n", mem_count); fflush(stdout);
X for (i = 0; i < SIZE; i++)
X FREE(ptrs[i], &freelist);
X printf("Finished...\n");
X}
X# endif
X/************************************************************************
X * Set of routines to improve virtual memory characteristics of *
X * certain data structures. This is done by allocating a large *
X * number of the things such that they'll all fit in at least *
X * one MMU page of memory and when the things are freed, just *
X * put them on a free list. We assume the things we are *
X * allocating are at least large enough to contain a pointer. *
X * *
X * We never actually free the memory but that shouldn't be a *
X * concern. Also we can't ever use realloc on these things. *
X * These routines are ideal for smallish data structures like *
X * linked list headers, etc. *
X ************************************************************************/
X
X# define MMU_PAGESIZE (3 * 8192)/* Must be at least as big as */
X /* real MMU page size. */
X# define NEXT(vp) ((VM *) ((char *) vp + size))
X# define NULL 0
X
Xtypedef struct VM {
X struct VM *next;
X } VM;
X# if defined(vm_alloc)
X# undef vm_alloc
X# endif
X# if defined(vm_free)
X# undef vm_free
X# endif
Xvoid *
Xvm_alloc(size, freeptr)
XVM **freeptr;
X{ register VM *vp1, *vp;
X register int i;
X int entries;
X
X if (*freeptr) {
X vp = *freeptr;
X *freeptr = vp->next;
X return (void *) vp;
X }
X entries = MMU_PAGESIZE / size;
X vp = (VM *) chk_alloc(entries * size);
X vp1 = *freeptr = NEXT(vp);
X for (i = 1; i++ < entries - 1; ) {
X vp1->next = NEXT(vp1);
X vp1 = vp1->next;
X }
X vp1->next = NULL;
X return (void *) vp;
X}
Xvoid
Xvm_free(vp, freeptr)
XVM *vp;
XVM **freeptr;
X{
X
X vp->next = *freeptr;
X *freeptr = vp;
X}
SHAR_EOF
chmod 0666 foxlib/chk_alloc.c || echo "restore of foxlib/chk_alloc.c fails"
mkdir foxlib >/dev/null 2>&1
echo "x - extracting foxlib/dname.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > foxlib/dname.c &&
Xchar *
Xdname(file)
Xregister char *file;
X{
X static char buf[64];
X register char *cp;
X strcpy(buf, file);
X
X cp = buf+strlen(buf)-1;
X for (; cp > buf; cp--)
X if (*cp == '/') {
X *cp = 0;
X break;
X }
X return buf;
X}
SHAR_EOF
chmod 0644 foxlib/dname.c || echo "restore of foxlib/dname.c fails"
mkdir foxlib >/dev/null 2>&1
echo "x - extracting foxlib/expand.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > foxlib/expand.c &&
X# include <stdio.h>
X
Xchar *
Xexpand(str)
Xchar *str;
X{
X FILE *fp;
X static char buf[BUFSIZ];
X
X sprintf(buf, "echo %s", str);
X fp = popen(buf, "r");
X fgets(buf, BUFSIZ, fp);
X if (buf[strlen(buf)-1] == '\n')
X buf[strlen(buf)-1] = NULL;
X pclose(fp);
X return buf;
X}
SHAR_EOF
chmod 0644 foxlib/expand.c || echo "restore of foxlib/expand.c fails"
mkdir foxlib >/dev/null 2>&1
echo "x - extracting foxlib/instr.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > foxlib/instr.c &&
Xchar *
Xinstr(str1, str2)
Xchar *str1, *str2;
X
X{ int len2 = strlen(str2);
X
X while (*str1) {
X if (strncmp(str1, str2, len2) == 0)
X return str1;
X str1++;
X }
X return (char *) 0;
X}
SHAR_EOF
chmod 0644 foxlib/instr.c || echo "restore of foxlib/instr.c fails"
mkdir foxlib >/dev/null 2>&1
echo "x - extracting foxlib/memcpy.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > foxlib/memcpy.c &&
Xchar *
Xmemcpy(dst, src, cnt)
Xregister char *dst;
Xregister char *src;
Xregister int cnt;
X{ register char *cp = dst;
X register int lcnt = cnt >> 2;
X
X cnt &= 3;
X while (lcnt-- > 0)
X *((long *) dst)++ = *((long *)src)++;
X while (cnt-- > 0)
X *dst++ = *src++;
X return cp;
X}
X
SHAR_EOF
chmod 0644 foxlib/memcpy.c || echo "restore of foxlib/memcpy.c fails"
mkdir foxlib >/dev/null 2>&1
echo "x - extracting foxlib/putenv.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > foxlib/putenv.c &&
X/* putenv.c - yet another implementation of the System V library routine.
X This code is in the public domain and may be freely changed and distributed.
X Written March, 1989 by Michael J. Haertel */
X
Xextern char *malloc(), *realloc();
Xextern char **environ;
X
Xstatic unsigned int envsize, envalloc, init;
X
Xstatic int
Xinitialize()
X{
X char **p;
X int i;
X
X for (p = environ, i = 0; *p; ++i, ++p)
X ;
X envsize = i;
X
X envalloc = 1;
X while (envalloc <= i)
X envalloc *= 2;
X
X p = (char **) malloc(envalloc * sizeof (char *));
X if (! p)
X return 0;
X
X for (i = 0; i <= envsize; ++i)
X p[i] = environ[i];
X
X environ = p;
X init = 1;
X return 1;
X}
X
Xstatic int
Xmatch(s, t)
X register char *s, *t;
X{
X while (*s && *s != '=' && *s == *t)
X ++s, ++t;
X if (*s == '=' && *s == *t)
X return 1;
X return 0;
X}
X
Xint
Xputenv(s)
X char *s;
X{
X int i;
X char **p;
X
X if (!init && !initialize())
X return 0;
X
X for (i = 0; i < envsize; ++i)
X if (match(s, environ[i])) {
X environ[i] = s;
X return 1;
X }
X
X if (i >= envalloc) {
X p = (char **) realloc((char *) environ,
X envalloc * 2 * sizeof (char **));
X if (!p)
X return 0;
X environ = p;
X envalloc *= 2;
X }
X
X environ[i] = s;
X ++envsize;
X return 1;
X}
SHAR_EOF
chmod 0644 foxlib/putenv.c || echo "restore of foxlib/putenv.c fails"
mkdir foxlib >/dev/null 2>&1
echo "x - extracting foxlib/rename.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > foxlib/rename.c &&
Xrename(old, new)
Xchar *new,
X *old;
X{ int i;
X
X if (link(old, new) < 0) {
X return -1;
X }
X return unlink(old);
X}
SHAR_EOF
chmod 0644 foxlib/rename.c || echo "restore of foxlib/rename.c fails"
mkdir foxlib >/dev/null 2>&1
echo "x - extracting foxlib/sname.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > foxlib/sname.c &&
Xchar *
Xsname(file)
Xregister char *file;
X{ char *strrchr();
X
X return strrchr(file, '/');
X}
SHAR_EOF
chmod 0644 foxlib/sname.c || echo "restore of foxlib/sname.c fails"
mkdir foxlib >/dev/null 2>&1
echo "x - extracting foxlib/strdup.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > foxlib/strdup.c &&
Xchar *
Xstrdup(str)
Xchar *str;
X{
X extern char *chk_alloc();
X extern char *memcpy();
X register char *cp = str;
X register int l = 0;
X
X while (*cp++)
X l++;
X l++;
X cp = chk_alloc(l);
X
X if (cp)
X return memcpy(cp, str, l);
X return 0;
X}
X
SHAR_EOF
chmod 0644 foxlib/strdup.c || echo "restore of foxlib/strdup.c fails"
mkdir foxlib >/dev/null 2>&1
echo "x - extracting foxlib/strtok.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > foxlib/strtok.c &&
X
X/*--------------------------------------------------------
X * Compilation instructions:
X * $COMPILE:$ cc -c strtok.c ; lib foxlib-+strtok,,
X *--------------------------------------------------------*/
X
Xchar *
Xstrtok(str, delims)
X
Xchar *str,
X *delims;
X{ static char *last_str;
X char *cp = str ? str : last_str;
X
X if (cp == (char *) 0)
X return (char *) 0;
X
X while (*cp && strchr(delims, *cp))
X cp++;
X if (last_str = strpbrk(cp, delims))
X *last_str++ = (char *) 0;
X
X return *cp == (char *) 0 ? (char *) 0 : cp;
X}
SHAR_EOF
chmod 0644 foxlib/strtok.c || echo "restore of foxlib/strtok.c fails"
mkdir foxlib >/dev/null 2>&1
echo "x - extracting foxlib/tell.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > foxlib/tell.c &&
Xlong
Xtell(fd)
Xint fd;
X{
X extern long lseek();
X return lseek(fd, 0l, 1);
X}
SHAR_EOF
chmod 0644 foxlib/tell.c || echo "restore of foxlib/tell.c fails"
mkdir foxlib >/dev/null 2>&1
echo "x - extracting foxlib/vmslib.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > foxlib/vmslib.c &&
X/* Standard Unix library routines not available under the Vax. */
X
X_assert(str, file, line)
Xchar *str;
Xchar *file;
X{
X printf("Assertion failed '%s', in %s at line %d\n",
X str, file, line);
X exit(1);
X}
Xgetcwd(buf, size)
Xchar *buf;
X{ char *getenv();
X char *cp = getenv("PATH");
X
X strcpy(buf, cp);
X}
Xqsort()
X{
X}
X_cleanup()
X{
X}
X/* Force GRIEF to think link failed so we do a normal copy. */
Xlink(f1, f2)
Xchar *f1, *f2;
X{
X return -1;
X}
X/* Version of unlink for VMS */
Xunlink(filename)
Xchar *filename;
X{
X return delete(filename);
X}
SHAR_EOF
chmod 0644 foxlib/vmslib.c || echo "restore of foxlib/vmslib.c fails"
mkdir llist >/dev/null 2>&1
echo "x - extracting llist/Makefile (Text)"
sed 's/^X//' << 'SHAR_EOF' > llist/Makefile &&
XRANLIB = echo
XLIBDIR = ../lib
XARC = $(LIBDIR)/llist.a
XSRC = Makefile *.h *.c
XOBJ = $(ARC)(ll_alloc.o) \
X $(ARC)(ll_append.o) \
X $(ARC)(ll_clear.o) \
X $(ARC)(ll_delete.o) \
X $(ARC)(ll_elem.o) \
X $(ARC)(ll_first.o) \
X $(ARC)(ll_free.o) \
X $(ARC)(ll_hook.o) \
X $(ARC)(ll_init.o) \
X $(ARC)(ll_insert.o) \
X $(ARC)(ll_lookup.o) \
X $(ARC)(ll_magic.o) \
X $(ARC)(ll_next.o) \
X $(ARC)(ll_prev.o) \
X $(ARC)(ll_push.o) \
X $(ARC)(ll_remove.o) \
X $(ARC)(ll_unhook.o)
X
XH = llist.h
X
X$(ARC): $(OBJ)
X -test -f /bin/ranlib && ranlib $(ARC)
X
X$(OBJ): $(H)
X
Xdist:
X sccs update < /dev/null
Xdist-list:
X @echo $(SRC)
Xdecls:
X echo '/* Blank Line */' > x
X $(CC) $(CFLAGS) -Zg $(OBJ:.o=.c) >> x
X mv x decls.h
X
SHAR_EOF
chmod 0644 llist/Makefile || echo "restore of llist/Makefile fails"
mkdir llist >/dev/null 2>&1
echo "x - extracting llist/llist.h (Text)"
sed 's/^X//' << 'SHAR_EOF' > llist/llist.h &&
X# define _LIB
X# define DEBUG
X
Xtypedef struct llist {
X# if defined(_LIB)
X struct llist *ll_next;
X struct llist *ll_prev;
X char *ll_elem;
X short ll_magic;
X# else
X short nothing;
X# endif
X }
X List,
X Head;
X
Xtypedef List *List_p;
Xtypedef Head *Head_p;
X
X# define LL_HEAD 0x4c48
X# define LL_LIST 0x4c4c
X
X#ifndef NULL
X# define NULL 0
X#endif
X/* Blank Line */
X# ifndef PROTO
X/*global*/ struct llist *ll_alloc();
X/*global*/ struct llist *ll_append();
X/*global*/ void ll_clear();
X/*global*/ void ll_delete();
X/*global*/ char *ll_elem();
X/*global*/ struct llist *ll_first();
X/*global*/ void ll_free();
X/*global*/ struct llist *ll_hook();
X/*global*/ struct llist *ll_init();
X/*global*/ struct llist *ll_insert();
X/*global*/ struct llist *ll_lookup();
X/*global*/ void ll_hmagic();
X/*global*/ void ll_magic();
X/*global*/ struct llist *ll_next();
X/*global*/ struct llist *ll_prev();
X/*global*/ char *ll_push();
X/*global*/ struct llist *ll_pop();
X/*global*/ int ll_remove();
X/*global*/ struct llist *ll_unhook();
X# else
X/*global*/ struct llist *ll_alloc(void );
X/*global*/ struct llist *ll_append(struct llist *,char *);
X/*global*/ void ll_clear(struct llist *);
X/*global*/ void ll_delete(struct llist *);
X/*global*/ char *ll_elem(struct llist *);
X/*global*/ struct llist *ll_first(struct llist *);
X/*global*/ void ll_free(struct llist *);
X/*global*/ struct llist *ll_hook(struct llist *,struct llist *);
X/*global*/ struct llist *ll_init(void );
X/*global*/ struct llist *ll_insert(struct llist *,char *,int );
X/*global*/ struct llist *ll_lookup(struct llist *,char *,int ( *)());
X/*global*/ void ll_hmagic(struct llist *);
X/*global*/ void ll_magic(struct llist *);
X/*global*/ struct llist *ll_next(struct llist *);
X/*global*/ struct llist *ll_prev(struct llist *);
X/*global*/ char *ll_push(struct llist *,char *);
X/*global*/ struct llist *ll_pop(struct llist *);
X/*global*/ int ll_remove(struct llist *);
X/*global*/ struct llist *ll_unhook(struct llist *);
X#endif
X
SHAR_EOF
chmod 0644 llist/llist.h || echo "restore of llist/llist.h fails"
mkdir llist >/dev/null 2>&1
echo "x - extracting llist/ll_alloc.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > llist/ll_alloc.c &&
X# include "llist.h"
X
Xstatic char err_msg[] = "ll_alloc: failed\n";
Xchar *ll_freelist = NULL;
Xextern void *vm_alloc();
X
XList_p
Xll_alloc()
X
X{ register List_p lp;
X
X if ((lp = (List_p) vm_alloc(sizeof (List), &ll_freelist)) == NULL) {
X write(2, err_msg, strlen(err_msg));
X abort();
X }
X
X lp->ll_magic = LL_LIST;
X lp->ll_next = lp->ll_prev = NULL;
X return lp;
X}
SHAR_EOF
chmod 0644 llist/ll_alloc.c || echo "restore of llist/ll_alloc.c fails"
mkdir llist >/dev/null 2>&1
echo "x - extracting llist/ll_append.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > llist/ll_append.c &&
X
X# include "llist.h"
X
XList_p
Xll_append(hp, atom)
XHead_p hp;
Xchar *atom;
X{
X return ll_insert(hp, atom, 32767);
X}
SHAR_EOF
chmod 0644 llist/ll_append.c || echo "restore of llist/ll_append.c fails"
mkdir llist >/dev/null 2>&1
echo "x - extracting llist/ll_clear.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > llist/ll_clear.c &&
X
X# include "llist.h"
X
Xvoid
Xll_clear(hp)
XHead_p hp;
X{ extern char *ll_freelist;
X register List_p lp;
X register List_p lp1;
X
X ll_hmagic(hp);
X
X for (lp = hp->ll_next; lp; lp = lp1) {
X lp1 = lp->ll_next;
X if (lp->ll_elem)
X chk_free(lp->ll_elem);
X vm_free(lp, &ll_freelist);
X }
X
X hp->ll_next = hp->ll_prev = NULL;
X}
SHAR_EOF
chmod 0644 llist/ll_clear.c || echo "restore of llist/ll_clear.c fails"
mkdir llist >/dev/null 2>&1
echo "x - extracting llist/ll_delete.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > llist/ll_delete.c &&
X# include "llist.h"
X
Xvoid
Xll_delete(lp)
XList_p lp;
X{ extern char *ll_freelist;
X
X ll_magic(lp);
X
X lp->ll_prev->ll_next = lp->ll_next;
X if (lp->ll_next)
X lp->ll_next->ll_prev = lp->ll_prev;
X vm_free(lp, &ll_freelist);
X}
SHAR_EOF
chmod 0644 llist/ll_delete.c || echo "restore of llist/ll_delete.c fails"
mkdir llist >/dev/null 2>&1
echo "x - extracting llist/ll_elem.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > llist/ll_elem.c &&
X# include "llist.h"
Xchar *
Xll_elem(lp)
XList_p lp;
X{
X ll_magic(lp);
X return lp->ll_elem;
X
X}
SHAR_EOF
chmod 0644 llist/ll_elem.c || echo "restore of llist/ll_elem.c fails"
mkdir llist >/dev/null 2>&1
echo "x - extracting llist/ll_first.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > llist/ll_first.c &&
X# include "llist.h"
X
XList_p
Xll_first(hp)
XHead_p hp;
X{
X ll_hmagic(hp);
X return hp->ll_next;
X}
SHAR_EOF
chmod 0644 llist/ll_first.c || echo "restore of llist/ll_first.c fails"
mkdir llist >/dev/null 2>&1
echo "x - extracting llist/ll_free.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > llist/ll_free.c &&
X# include "llist.h"
X
Xvoid
Xll_free(hp)
Xregister Head_p hp;
X{ extern char *ll_freelist;
X
X ll_hmagic(hp);
X vm_free(hp, &ll_freelist);
X}
SHAR_EOF
chmod 0644 llist/ll_free.c || echo "restore of llist/ll_free.c fails"
mkdir llist >/dev/null 2>&1
echo "x - extracting llist/ll_hook.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > llist/ll_hook.c &&
X# include "llist.h"
X
XList_p
Xll_hook(hp, lp)
XHead_p hp;
XList_p lp;
X{ register List_p lp1;
X
X ll_hmagic(hp);
X ll_magic(lp);
X
X if (hp->ll_next == NULL) {
X hp->ll_next = lp;
X return lp;
X }
X
X for (lp1 = hp->ll_next; lp1->ll_next; )
X lp1 = lp1->ll_next;
X
X lp1->ll_next = lp;
X lp->ll_prev = lp1;
X
X return lp;
X}
SHAR_EOF
chmod 0644 llist/ll_hook.c || echo "restore of llist/ll_hook.c fails"
mkdir llist >/dev/null 2>&1
echo "x - extracting llist/ll_init.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > llist/ll_init.c &&
X# include "llist.h"
X
XHead_p
Xll_init()
X
X{ register Head_p hp;
X
X hp = (Head_p) ll_alloc();
X hp->ll_magic = LL_HEAD;
X return hp;
X}
SHAR_EOF
chmod 0644 llist/ll_init.c || echo "restore of llist/ll_init.c fails"
mkdir llist >/dev/null 2>&1
echo "x - extracting llist/ll_insert.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > llist/ll_insert.c &&
X
X# include "llist.h"
X
XList_p
Xll_insert(hp, atom, pos)
XHead_p hp;
Xchar *atom;
X{ register List_p lp;
X register List_p lp1;
X
X ll_hmagic(hp);
X lp = ll_alloc();
X lp->ll_elem = atom;
X
X if (pos == 0 || hp->ll_next == NULL) {
X lp->ll_next = hp->ll_next;
X lp->ll_prev = hp;
X hp->ll_next = lp;
X if (lp->ll_next)
X lp->ll_next->ll_prev = lp;
X return lp;
X }
X
X for (lp1 = hp->ll_next; pos-- > 0 && lp1->ll_next; )
X lp1 = lp1->ll_next;
X
X lp->ll_next = lp1->ll_next;
X lp->ll_prev = lp1;
X
X lp1->ll_next = lp;
X if (lp->ll_next)
X lp->ll_next->ll_prev = lp;
X
X return lp;
X}
SHAR_EOF
chmod 0644 llist/ll_insert.c || echo "restore of llist/ll_insert.c fails"
mkdir llist >/dev/null 2>&1
echo "x - extracting llist/ll_lookup.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > llist/ll_lookup.c &&
X# include "llist.h"
X
XList_p
Xll_lookup(hp, str, func)
XHead_p hp;
Xchar *str;
Xint (*func)();
X{ register List_p lp;
X
X for (lp = hp->ll_next; lp; lp = lp->ll_next)
X if ((*func)(str, lp->ll_elem) == 0)
X return lp;
X return NULL;
X}
SHAR_EOF
chmod 0644 llist/ll_lookup.c || echo "restore of llist/ll_lookup.c fails"
mkdir llist >/dev/null 2>&1
echo "x - extracting llist/ll_magic.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > llist/ll_magic.c &&
X# include "llist.h"
X
Xstatic char err_msg1[] = "\nll_magic: null pointer\n";
Xstatic char err_msg2[] = "\nll_magic: bad magic number\n";
X
Xvoid
Xll_hmagic(hp)
XHead_p hp;
X{
X if (hp == 0) {
X write(2, err_msg1, strlen(err_msg1));
X abort();
X }
X if (hp->ll_magic != LL_HEAD) {
X write(2, err_msg2, strlen(err_msg2));
X abort();
X }
X}
Xvoid
Xll_magic(lp)
XList_p lp;
X{
X if (lp == 0) {
X write(2, err_msg1, strlen(err_msg1));
X abort();
X }
X if (lp->ll_magic != LL_LIST) {
X write(2, err_msg2, strlen(err_msg2));
X abort();
X }
X}
SHAR_EOF
chmod 0644 llist/ll_magic.c || echo "restore of llist/ll_magic.c fails"
mkdir llist >/dev/null 2>&1
echo "x - extracting llist/ll_next.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > llist/ll_next.c &&
X# include "llist.h"
X
XList_p
Xll_next(lp)
XList_p lp;
X{
X ll_magic(lp);
X return lp->ll_next;
X}
SHAR_EOF
chmod 0644 llist/ll_next.c || echo "restore of llist/ll_next.c fails"
mkdir llist >/dev/null 2>&1
echo "x - extracting llist/ll_prev.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > llist/ll_prev.c &&
X# include "llist.h"
X
XList_p
Xll_prev(lp)
XList_p lp;
X{
X ll_magic(lp);
X return lp->ll_prev;
X}
SHAR_EOF
chmod 0644 llist/ll_prev.c || echo "restore of llist/ll_prev.c fails"
mkdir llist >/dev/null 2>&1
echo "x - extracting llist/ll_push.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > llist/ll_push.c &&
X# include "llist.h"
X
Xchar *
Xll_push(hp, atom)
XHead_p hp;
Xchar *atom;
X{
X ll_insert(hp, atom, 0);
X return atom;
X}
XList_p
Xll_pop(hp)
XHead_p hp;
X{ List_p lp = ll_first(hp);
X char *atom;
X
X if (lp) {
X atom = ll_elem(lp);
X ll_delete(lp);
X }
X
X return ll_first(hp);
X
X}
SHAR_EOF
chmod 0644 llist/ll_push.c || echo "restore of llist/ll_push.c fails"
mkdir llist >/dev/null 2>&1
echo "x - extracting llist/ll_remove.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > llist/ll_remove.c &&
X# include "llist.h"
X
Xll_remove(lp)
XList_p lp;
X{ extern char *ll_freelist;
X lp = ll_unhook(lp);
X vm_free(lp, &ll_freelist);
X}
SHAR_EOF
chmod 0644 llist/ll_remove.c || echo "restore of llist/ll_remove.c fails"
mkdir llist >/dev/null 2>&1
echo "x - extracting llist/ll_unhook.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > llist/ll_unhook.c &&
X# include "llist.h"
X
XList_p
Xll_unhook(lp)
Xregister List_p lp;
X{
X ll_magic(lp);
X
X if (lp->ll_prev)
X lp->ll_prev->ll_next = lp->ll_next;
X if (lp->ll_next)
X lp->ll_next->ll_prev = lp->ll_prev;
X
X lp->ll_prev = lp->ll_next = NULL;
X
X return lp;
X}
SHAR_EOF
chmod 0644 llist/ll_unhook.c || echo "restore of llist/ll_unhook.c fails"
mkdir splay >/dev/null 2>&1
echo "x - extracting splay/Makefile (Text)"
sed 's/^X//' << 'SHAR_EOF' > splay/Makefile &&
X#
X# makefile for splay tree library
XL = lib
XARC = ../$(L)/libsptree.a
XOBJ = $(ARC)(splay.o) $(ARC)(spstats.o) $(ARC)(sptree.o)
XSRC = Makefile *.h *.c
XSHELL = /bin/sh
X
X$(ARC): $(OBJ)
X -test -f /bin/ranlib && ranlib $(ARC)
X
Xdist:
X sccs update < /dev/null
Xdist-list:
X @echo $(SRC)
Xtest: splay.o test.o spstats.o sptree.o
X cc $(CFLAGS) -o test test.o splay.o spstats.o sptree.o
Xxenix.386:
X $(MAKE) XFLAGS="-M3" RANLIB=ranlib
Xxenix.286:
X $(MAKE) XFLAGS="-M2l -K" RANLIB=ranlib
Xrtpc:
X $(MAKE)
Xuport.286:
X $(MAKE)
Xuport.386:
X $(MAKE)
Xsun:
X $(MAKE) RANLIB=ranlib
X
SHAR_EOF
chmod 0644 splay/Makefile || echo "restore of splay/Makefile fails"
mkdir splay >/dev/null 2>&1
echo "x - extracting splay/sptree.h (Text)"
sed 's/^X//' << 'SHAR_EOF' > splay/sptree.h &&
X/*
X** sptree.h: The following type declarations provide the binary tree
X** representation of event-sets or priority queues needed by splay trees
X**
X** assumes that data and datb will be provided by the application
X** to hold all application specific information
X**
X** assumes that key will be provided by the application, comparable
X** with the compare function applied to the addresses of two keys.
X*/
X
X# ifndef SPTREE_H
X# define SPTREE_H
X
X# ifndef NULL
X# define NULL 0
X# endif
X
X# define STRCMP( a, b ) ( (Sct = *(a) - *(b)) ? Sct : strcmp( (a), (b) ) )
X
Xtypedef struct _spblk SPBLK;
X
Xtypedef struct _spblk
X{
X SPBLK * leftlink;
X SPBLK * rightlink;
X SPBLK * uplink;
X
X char * key; /* formerly time/timetyp */
X char * data; /* formerly aux/auxtype */
X char * datb;
X};
X
X# define SPF_WALK 0x0001 /* If set, we cannot splay tree */
X /* because we are walking down the tree*/
Xtypedef struct
X{
X SPBLK * root; /* root node */
X int flags;
X
X /* Statistics, not strictly necessary, but handy for tuning */
X
X long lookups; /* number of splookup()s */
X long lkpcmps; /* number of lookup comparisons */
X
X long enqs; /* number of spenq()s */
X long enqcmps; /* compares in spenq */
X
X long splays;
X long splayloops;
X
X} SPTREE;
X
X
X/* sptree.c */
Xextern SPTREE * spinit(); /* init tree */
Xextern int spempty(); /* is tree empty? */
Xextern spenq(); /* insert item into the tree */
Xextern spdeq(); /* return and remove lowest item in subtree */
Xextern splay(); /* reorganize tree */
Xextern SPBLK *sprotate();
Xextern SPBLK * splookup(); /* find key in a tree */
Xextern SPBLK *sphead();
Xextern char *spstats();
X# endif
SHAR_EOF
chmod 0644 splay/sptree.h || echo "restore of splay/sptree.h fails"
mkdir splay >/dev/null 2>&1
echo "x - extracting splay/splay.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > splay/splay.c &&
X/*
X *
X * sptree.c: The following code implements the basic operations on
X * an event-set or priority-queue implemented using splay trees:
X *
X * spdeq( q ) Return first key in q, removing it.
X * int spempty(); Is tree empty?
X * spenq( n, q ) Insert n in q after all equal keys.
X * SPTREE *spinit( ) Make a new tree
X * splay( n, q ) n (already in q) becomes the root.
X * sprotate( n ) Perform rotation.
X * In the above, n points to an SPBLK type, while q points to an
X * SPTREE.
X *
X * The implementation used here is based on the implementation
X * which was used in the tests of splay trees reported in:
X *
X * An Empirical Comparison of Priority-Queue and Event-Set Implementations,
X * by Douglas W. Jones, Comm. ACM 29, 4 (Apr. 1986) 300-311.
X *
X * The basic splay tree algorithms were originally
X * presented in:
X *
X * Self Adjusting Binary Trees,
X * by D. D. Sleator and R. E. Tarjan,
X * Proc. ACM SIGACT Symposium on Theory
X * of Computing (Boston, Apr 1983) 235-245.
X *
X */
X
X# include "sptree.h"
X
X/* USER SUPPLIED! */
X
Xextern char *chk_alloc();
X
X
X/*----------------
X *
X * spinit() -- initialize an empty splay tree
X *
X */
XSPTREE *
Xspinit()
X{
X register SPTREE * q;
X static SPTREE null_sptree = {0};
X
X q = (SPTREE *) chk_alloc( sizeof( *q ) );
X *q = null_sptree;
X return q;
X}
X
X/*----------------
X *
X * spempty() -- is an event-set represented as a splay tree empty?
X */
Xint
Xspempty(q)
XSPTREE *q;
X
X{
X return q == NULL || q->root == NULL;
X}
XSPBLK *
Xsphead(tree)
XSPTREE *tree;
X{
X return tree->root;
X}
X
Xspenq(q, tree)
XSPBLK *q;
XSPTREE *tree;
X{ SPBLK *x = tree->root;
X char *key = q->key;
X
X tree->enqs++;
X
X q->leftlink = q->rightlink = NULL;
X if (x == NULL) {
X tree->root = q;
X q->uplink = NULL;
X return;
X }
X while (1) {
X int Sct;
X int cmp = STRCMP(key, x->key);
X tree->enqcmps++;
X if (cmp < 0) {
X if (x->leftlink == NULL) {
X x->leftlink = q;
X break;
X }
X x = x->leftlink;
X }
X else if (cmp > 0) {
X if (x->rightlink == NULL) {
X x->rightlink = q;
X break;
X }
X x = x->rightlink;
X }
X else {
X printf("Duplicate entry in splay tree\n");
X exit(1);
X }
X }
X q->uplink = x;
X/*ptree(tree);*/
X}
Xspdeq(q, tree)
XSPBLK *q;
XSPTREE *tree;
X{ register SPBLK *r, *s, *t;
X /* Knuth, Vol. 3, Algorithm D, page 420. */
XD1:
X t = q;
X if (t->rightlink == NULL) {
X q = t->leftlink;
X goto D4;
X }
XD2:
X r = t->rightlink;
X if (r->leftlink == NULL) {
X if (r->leftlink = t->leftlink)
X t->leftlink->uplink = r;
X q = r;
X goto D4;
X }
XD3:
X do {
X s = r->leftlink;
X if (s->leftlink == NULL)
X break;
X r = s;
X }
X while (1);
X if (s->leftlink = t->leftlink)
X t->leftlink->uplink = s;
X if (r->leftlink = s->rightlink)
X s->rightlink->uplink = r;
X s->rightlink = t->rightlink;
X t->rightlink->uplink = s;
X q = s;
XD4:
X if (tree->root == t)
X tree->root = q;
X if (q)
X q->uplink = t->uplink;
X if (t->uplink && t->uplink->leftlink == t)
X t->uplink->leftlink = q;
X else if (t->uplink && t->uplink->rightlink == t)
X t->uplink->rightlink = q;
X}
X/*----------------
X *
X * splay() -- reorganize the tree.
X *
X * the tree is reorganized so that x is the root of the
X * splay tree representing tree; x must be in the tree, otherwise
X * infinite looping will result; the left branch of
X * the right subtree and the right branch of the left subtree are
X * shortened in the process
X *
X */
X
Xsplay(x, tree)
XSPBLK *x;
XSPTREE *tree;
X{ register SPBLK *root = tree->root;
X register SPBLK *up;
X
X if (tree->flags & SPF_WALK)
X return;
X tree->splays++;
X if (root == x || root->leftlink == x || root->rightlink == x)
X return;
X while (1) {
X if (x->uplink == NULL) {
X tree->root = x;
X return;
X }
X /* ZIG */
X if (root->leftlink == x || root->rightlink == x) {
X sprotate(x);
X x->uplink = NULL;
X tree->root = x;
X return;
X }
X /* ZIG-ZIG */
X up = x->uplink;
X if (up->leftlink == x &&
X up->uplink &&
X up->uplink->leftlink == up) {
X sprotate(up);
X sprotate(x);
X }
X else if (up->rightlink == x &&
X up->uplink &&
X up->uplink->rightlink == up) {
X sprotate(up);
X sprotate(x);
X }
X /* ZIG-ZAG */
X else {
X sprotate(x);
X sprotate(x);
X }
X tree->splayloops++;
X }
X}
XSPBLK *
Xsprotate(x)
Xregister SPBLK *x;
X{ register SPBLK *y;
X SPBLK *B;
X SPBLK *up = x->uplink;
X SPBLK *yup;
X
X y = up;
X if (up->leftlink == x) {
X /*--------------------------------------------------*/
X /* Right rotate at x.
X /* y x
X /* / \ / \
X /* x C ==> A y
X /* / \ / \
X /* A B B C
X /*--------------------------------------------------*/
X B = x->rightlink;
X
X if (yup = x->uplink = y->uplink) {
X if (yup->leftlink == y)
X yup->leftlink = x;
X else
X yup->rightlink = x;
X }
X y->uplink = x;
X y->leftlink = B;
X x->rightlink = y;
X }
X else {
X /*--------------------------------------------------*/
X /* x y
X /* / \ / \
X /* y C <== A x
X /* / \ / \
X /* A B B C
X /*--------------------------------------------------*/
X B = x->leftlink;
X if (yup = x->uplink = y->uplink) {
X if (yup->leftlink == y)
X yup->leftlink = x;
X else
X yup->rightlink = x;
X }
X y->uplink = x;
X x->leftlink = y;
X y->rightlink = B;
X }
X if (B)
X B->uplink = y;
X}
X/*----------------
X *
X * splookup() -- given key, find a node in a tree.
X *
X * Splays the found node to the root.
X */
XSPBLK *
Xsplookup( key, q )
Xregister char * key;
Xregister SPTREE * q;
X
X{ register SPBLK * n;
X register int Sct;
X
X /* find node in the tree */
X n = q->root;
X q->lookups++;
X while (n) {
X q->lkpcmps++;
X if ((Sct = STRCMP(key, n->key)) == 0) {
X splay(n, q);
X return n;
X }
X n = (Sct < 0) ? n->leftlink : n->rightlink;
X }
X
X /* reorganize tree around this node */
X return NULL;
X}
Xspapply(tree, func, arg2)
XSPTREE *tree;
Xint (*func)();
X{
X tree->flags |= SPF_WALK;
X spwalk(tree->root, func, arg2);
X tree->flags &= ~SPF_WALK;
X}
Xspwalk(node, func, arg2)
XSPBLK *node;
Xint (*func)();
X{
X if (node == NULL)
X return;
X (*func)(node, arg2);
X spwalk(node->leftlink, func, arg2);
X spwalk(node->rightlink, func, arg2);
X}
X
SHAR_EOF
chmod 0644 splay/splay.c || echo "restore of splay/splay.c fails"
mkdir splay >/dev/null 2>&1
echo "x - extracting splay/spstats.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > splay/spstats.c &&
X# include "sptree.h"
X
Xchar *
Xspstats(q)
XSPTREE *q;
X{ static char buf[128];
X long llen;
X long elen;
X long sloops;
X
X if (q == NULL)
X return "";
X
X llen = q->lookups ? (100 * q->lkpcmps) / q->lookups : 0;
X elen = q->enqs ? (100 * q->enqcmps)/q->enqs : 0;
X sloops = q->splays ? (100 * q->splayloops)/q->splays : 0;
X
X sprintf(buf,
X"Lookups(%ld %ld.%02ld) Insertions(%ld %ld.%02ld) Splays(%ld %ld.%02ld)",
X q->lookups, llen / 100, llen % 100,
X q->enqs, elen / 100, elen % 100,
X q->splays, sloops / 100, sloops % 100);
X
X return buf;
X}
X
SHAR_EOF
chmod 0644 splay/spstats.c || echo "restore of splay/spstats.c fails"
mkdir splay >/dev/null 2>&1
echo "x - extracting splay/sptree.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > splay/sptree.c &&
X
X# include "sptree.h"
X
X# define MAX_DEPTH 128
Xtypedef char STRING[400];
XSTRING pe[MAX_DEPTH];
Xint pecnt = 0;
Xint max_level = 0;
Xptree(tree)
XSPTREE *tree;
X{ int i, j;
X
X if (tree->root == NULL) {
X printf("NULL TREE\n");
X return;
X }
X pecnt = 0;
X max_level = 0;
X for (i = 0; i < MAX_DEPTH; i++)
X pe[i][0] = NULL;
X print_tree(0, tree->root);
X printf("Tree:\n");
X
X for (i = 0; i <= max_level; i++) {
X int spc = (max_level - i) / 2;
X printf("%2d: ", i);
X while (spc-- > 0)
X printf(" ");
X printf("%s\n", pe[i]);
X }
X printf("Statistics: %s\n", spstats(tree));
X
X}
Xprint_tree(level, x)
XSPBLK *x;
X{ int i;
X char *str;
X if (level > MAX_DEPTH) {
X printf("Maximum nesting level exceeded in print_tree\n");
X abort();
X }
X if (level > max_level) {
X char buf[120];
X max_level = level;
X/* for (i = 0; i < max_level; i++) {
X strcpy(buf, pe[i]);
X sprintf(pe[i], " %s", buf);
X }*/
X }
X str = pe[level];
X str += strlen(str);
X sprintf(str, " %s(%s:%s,%s)", x->key,
X x->uplink ? x->uplink->key : "-",
X x->leftlink ? x->leftlink->key : "-",
X x->rightlink ? x->rightlink->key : "-");
X if (x->leftlink)
X print_tree(level+1, x->leftlink);
X if (x->rightlink)
X print_tree(level+1,x->rightlink);
X}
SHAR_EOF
chmod 0644 splay/sptree.c || echo "restore of splay/sptree.c fails"
mkdir splay >/dev/null 2>&1
echo "x - extracting splay/test.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > splay/test.c &&
X# include <stdio.h>
X# include "sptree.h"
XSPTREE *tree;
Xchar lbuf[132];
X# define TRUE 1
X# define FALSE 0
Xmain(argc, argv)
Xchar **argv;
X{ extern char *chk_alloc();
X int i = 1;
X SPBLK *q;
X int lookup = FALSE;
X
X tree = spinit();
X if (argv[1][0] == '-') {
X if (argv[1][1] == 'l') {
X lookup = TRUE;
X i++;
X }
X }
X for (; i < argc; i++)
X new(argv[i]);
X while (1) {
X ptree(tree);
X printf(lookup ? "Lookup ? " : "Delete ? ");
X fflush(stdout);
X gets(lbuf);
X if (lbuf[strlen(lbuf)-1] == '\n')
X lbuf[strlen(lbuf)-1] = NULL;
X if (lbuf[0] == NULL)
X exit(1);
X q = splookup(lbuf, tree);
X if (q == NULL) {
X printf("Entry not found.\n");
X continue;
X }
X if (!lookup) {
X printf("Before deletion\n");
X ptree(tree);
X fflush(stdout);
X spdeq(q, tree);
X }
X }
X}
Xchar *chk_alloc(n)
X{ extern char *malloc();
X return malloc(n);
X}
Xnew(str)
Xchar *str;
X{
X SPBLK *q = (SPBLK *) chk_alloc(sizeof (SPBLK) + 32);
X char *s = (char *) (q + 1);
X strcpy(s, str);
X q->key = s;
X
X spenq(q, tree);
X}
SHAR_EOF
chmod 0644 splay/test.c || echo "restore of splay/test.c fails"
mkdir utils >/dev/null 2>&1
echo "x - extracting utils/kbd.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > utils/kbd.c &&
X/************************************************************************
X * This is a utility for remapping the keyboard under Unix V.3.2 *
X * (only tested on 386/ix). It allows me to map the switch *
X * screen characters to things like ALT-F1, ALT-F2 rather than *
X * the brain damaged way Interactive did the keyboard layout. *
X * *
X * This code is modelled after the Xenix 386/2.2 mapkey program. *
X * For some reason Interactive left this program out of the *
X * supplied software. *
X * *
X * This program replaces the previous mapstr.c file in the utils *
X * directory. *
X ************************************************************************/
X
X# include <stdio.h>
X# include <ctype.h>
X# include <sys/types.h>
X# include <sys/at_ansi.h>
X# include <sys/kd.h>
X
X# define FALSE 0
X# define TRUE 1
X# define MAYBE 2
X
X# define XDIGIT(x) (isdigit(x) ? x - '0' : (x >= 'A' && x <= 'F') ? x - 'A' + 10 : (x - 'a' + 10))
X
Xstrmap_t strmap;
Xchar *fkeys[NSTRKEYS];
Xkeymap_t kdkeymap;
Xsrqtab_t sreq;
Xstruct kbentry kbentry;
Xint f_flag = MAYBE;
Xint k_flag = MAYBE;
X
Xstruct map {
X char *name;
X int value;
X };
Xchar *msg2[] = { "O", "C", "N", "B" };
Xstruct map ascii_msg[] = {
X "nul", 0,
X "soh", 1,
X "stx", 2,
X "etx", 3,
X "eot", 4,
X "enq", 5,
X "ack", 6,
X "bel", 7,
X "bs", 8,
X "ht", 9,
X "nl", 10,
X "vt", 11,
X "np", 12,
X "cr", 13,
X "so", 14,
X "si", 15,
X "dle", 16,
X "dc1", 17,
X "dc2", 18,
X "dc3", 19,
X "dc4", 20,
X "nak", 21,
X "syn", 22,
X "etb", 23,
X "can", 24,
X "em", 25,
X "sub", 26,
X "esc", 27,
X "fs", 28,
X "gs", 29,
X "rs", 30,
X "us", 31,
X "del", 127,
X NULL
X };
Xstruct map msg1[] = {
X "nop", K_NOP,
X "lshft", K_LSH,
X "rshft", K_RSH,
X "cplck", K_CLK,
X "nmlck", K_NLK,
X "sclck", K_SLK,
X "alt", K_ALT,
X "bktab", K_BTAB,
X "ctrl", K_CTL,
X "lalt", K_LAL,
X "ralt", K_RAL,
X "lctrl", K_LCT,
X "rctrl", K_RCT,
X "SYSREQ", K_SRQ,
X "brk", K_BRK,
X "escN", K_ESN,
X "escO", K_ESO,
X "escL", K_ESL,
X "REBOOT", K_RBT,
X "DEBUG", K_DBG,
X "NEXT", K_NEXT,
X "PREV", K_PREV,
X "FRCNXT", K_FRCNEXT,
X "FRCPRV", K_FRCPREV,
X "vt01", K_VTF-1+1,
X "vt02", K_VTF-1+2,
X "vt03", K_VTF-1+3,
X "vt04", K_VTF-1+4,
X "vt05", K_VTF-1+5,
X "vt06", K_VTF-1+6,
X "vt07", K_VTF-1+7,
X "vt08", K_VTF-1+8,
X "vt09", K_VTF-1+9,
X "vt10", K_VTF-1+10,
X "vt11", K_VTF-1+11,
X "vt12", K_VTF-1+12,
X "vt13", K_VTF-1+13,
X "vt14", K_VTF-1+14,
X "MGRF", K_MGRF,
X "fkey1", K_FUNF-1+1,
X "fkey2", K_FUNF-1+2,
X "fkey3", K_FUNF-1+3,
X "fkey4", K_FUNF-1+4,
X "fkey5", K_FUNF-1+5,
X "fkey6", K_FUNF-1+6,
X "fkey7", K_FUNF-1+7,
X "fkey8", K_FUNF-1+8,
X "fkey9", K_FUNF-1+9,
X "fkey10", K_FUNF-1+10,
X "fkey11", K_FUNF-1+11,
X "fkey12", K_FUNF-1+12,
X "fkey13", K_FUNF-1+13,
X "fkey14", K_FUNF-1+14,
X "fkey15", K_FUNF-1+15,
X "fkey16", K_FUNF-1+16,
X "fkey17", K_FUNF-1+17,
X "fkey18", K_FUNF-1+18,
X "fkey19", K_FUNF-1+19,
X "fkey20", K_FUNF-1+20,
X "fkey21", K_FUNF-1+21,
X "fkey22", K_FUNF-1+22,
X "fkey23", K_FUNF-1+23,
X "fkey24", K_FUNF-1+24,
X "fkey25", K_FUNF-1+25,
X "fkey26", K_FUNF-1+26,
X "fkey27", K_FUNF-1+27,
X "fkey28", K_FUNF-1+28,
X "fkey29", K_FUNF-1+29,
X "fkey30", K_FUNF-1+30,
X "fkey31", K_FUNF-1+31,
X "fkey32", K_FUNF-1+32,
X "fkey33", K_FUNF-1+33,
X "fkey34", K_FUNF-1+34,
X "fkey35", K_FUNF-1+35,
X "fkey36", K_FUNF-1+36,
X "fkey37", K_FUNF-1+37,
X "fkey38", K_FUNF-1+38,
X "fkey39", K_FUNF-1+39,
X "fkey40", K_FUNF-1+40,
X "fkey41", K_FUNF-1+41,
X "fkey42", K_FUNF-1+42,
X "fkey43", K_FUNF-1+43,
X "fkey44", K_FUNF-1+44,
X "fkey45", K_FUNF-1+45,
X "fkey46", K_FUNF-1+46,
X "fkey47", K_FUNF-1+47,
X "fkey48", K_FUNF-1+48,
X "fkey49", K_FUNF-1+49,
X "fkey50", K_FUNF-1+50,
X "fkey51", K_FUNF-1+51,
X "fkey52", K_FUNF-1+52,
X "fkey53", K_FUNF-1+53,
X "fkey54", K_FUNF-1+54,
X "fkey55", K_FUNF-1+55,
X "fkey56", K_FUNF-1+56,
X "fkey57", K_FUNF-1+57,
X "fkey58", K_FUNF-1+58,
X "fkey59", K_FUNF-1+59,
X "fkey60", K_FUNF-1+60,
X "fkey61", K_FUNF-1+61,
X "fkey62", K_FUNF-1+62,
X "fkey63", K_FUNF-1+63,
X "fkey64", K_FUNF-1+64,
X "fkey65", K_FUNF-1+65,
SHAR_EOF
echo "End of part 2"
echo "File utils/kbd.c is continued in part 3"
echo "3" > s2_seq_.tmp
exit 0
--
===================== Reuters Ltd PLC,
Tel: +44 628 891313 x. 212 Westthorpe House,
UUCP: fox%marlow.uucp@idec.stc.co.uk Little Marlow,
Bucks, England SL7 3RQ