This is a version of Henry Spencer's famous regexp implementation. I've
modified it to meet my needs, this is what I've done:

    2) added a new function regsublen(), this performs a dry run of the
       regsub() function returning the length of the string needed to hold
       the output from regsub().
    3) changed regexec(prog,str) to regexec2(prog,str,eflags) with macro for
       regexec(). This is so I can have the flag REG_NOTBOL which signifies
       that the string passed to regexec[2]() is not actually the start of a
       line.
    4) support for case-insignificant matching (with the flag REG_NOCASE)
    5) split the definition of a compiled regexp from regexp.c into
       a new file regprog.h
    6) created a new file regjade.c which uses the regexec() structure to
       match regexp against editor buffers in place.
    7) Altered the regexp structure to allow storing of subexpressions as
       positions in a Jade buffer. Also altered calling conventions of
       regsub() and regsublen() to support this.
    8) support \w, \W, \s, \S, \d, \D, \b, \B, *?, +?, ?? syntax (as in Perl)

And probably some other things as well. Obviously all errors are my
responsibility. The original README follows,

John

--

This is a nearly-public-domain reimplementation of the V8 regexp(3) package.
It gives C programs the ability to use egrep-style regular expressions, and
does it in a much cleaner fashion than the analogous routines in SysV.

	Copyright (c) 1986 by University of Toronto.
	Written by Henry Spencer.  Not derived from licensed software.

	Permission is granted to anyone to use this software for any
	purpose on any computer system, and to redistribute it freely,
	subject to the following restrictions:

	1. The author is not responsible for the consequences of use of
		this software, no matter how awful, even if they arise
		from defects in it.

	2. The origin of this software must not be misrepresented, either
		by explicit claim or by omission.

	3. Altered versions must be plainly marked as such, and must not
		be misrepresented as being the original software.

Barring a couple of small items in the BUGS list, this implementation is
believed 100% compatible with V8.  It should even be binary-compatible,
sort of, since the only fields in a "struct regexp" that other people have
any business touching are declared in exactly the same way at the same
location in the struct (the beginning).

This implementation is *NOT* AT&T/Bell code, and is not derived from licensed
software.  Even though U of T is a V8 licensee.  This software is based on
a V8 manual page sent to me by Dennis Ritchie (the manual page enclosed
here is a complete rewrite and hence is not covered by AT&T copyright).
The software was nearly complete at the time of arrival of our V8 tape.
I haven't even looked at V8 yet, although a friend elsewhere at U of T has
been kind enough to run a few test programs using the V8 regexp(3) to resolve
a few fine points.  I admit to some familiarity with regular-expression
implementations of the past, but the only one that this code traces any
ancestry to is the one published in Kernighan & Plauger (from which this
one draws ideas but not code).

Simplistically:  put this stuff into a source directory, copy regexp.h into
/usr/include, inspect Makefile for compilation options that need changing
to suit your local environment, and then do "make r".  This compiles the
regexp(3) functions, compiles a test program, and runs a large set of
regression tests.  If there are no complaints, then put regexp.o, regsub.o,
and regerror.o into your C library, and regexp.3 into your manual-pages
directory.

Note that if you don't put regexp.h into /usr/include *before* compiling,
you'll have to add "-I." to CFLAGS before compiling.

The files are:

Makefile	instructions to make everything
regexp.3	manual page
regexp.h	header file, for /usr/include
regexp.c	source for regcomp() and regexec()
regsub.c	source for regsub()
regerror.c	source for default regerror()
regmagic.h	internal header file
try.c		source for test program
timer.c		source for timing program
tests		test list for try and timer

This implementation uses nondeterministic automata rather than the
deterministic ones found in some other implementations, which makes it
simpler, smaller, and faster at compiling regular expressions, but slower
at executing them.  In theory, anyway.  This implementation does employ
some special-case optimizations to make the simpler cases (which do make
up the bulk of regular expressions actually used) run quickly.  In general,
if you want blazing speed you're in the wrong place.  Replacing the insides
of egrep with this stuff is probably a mistake; if you want your own egrep
you're going to have to do a lot more work.  But if you want to use regular
expressions a little bit in something else, you're in luck.  Note that many
existing text editors use nondeterministic regular-expression implementations,
so you're in good company.

This stuff should be pretty portable, given appropriate option settings.
If your chars have less than 8 bits, you're going to have to change the
internal representation of the automaton, although knowledge of the details
of this is fairly localized.  There are no "reserved" char values except for
NUL, and no special significance is attached to the top bit of chars.
The string(3) functions are used a fair bit, on the grounds that they are
probably faster than coding the operations in line.  Some attempts at code
tuning have been made, but this is invariably a bit machine-specific.

                   sdbm - Substitute DBM
                             or
        Berkeley ndbm for Every UN*X[1] Made Simple

                      Ozan (oz) Yigit

            The Guild of PD Software Toolmakers
                      Toronto - Canada

                     oz@nexus.yorku.ca



Implementation is the sincerest form of flattery. - L. Peter
Deutsch

A The Clone of the ndbm library

     The sources accompanying this notice - sdbm  -  consti-
tute  the  first  public  release  (Dec. 1990) of a complete
clone of the Berkeley UN*X ndbm library. The sdbm library is
meant  to  clone the proven functionality of ndbm as closely
as possible, including a few improvements. It is  practical,
easy to understand, and compatible.  The sdbm library is not
derived  from  any  licensed,  proprietary  or   copyrighted
software.

     The sdbm implementation is based on  a  1978  algorithm
[Lar78] by P.-A. (Paul) Larson known as ``Dynamic Hashing''.
In the course of searching for a substitute for ndbm, I pro-
totyped  three different external-hashing algorithms [Lar78,
Fag79, Lit80] and ultimately chose Larson's algorithm  as  a
basis  of  the  sdbm  implementation. The Bell Labs dbm (and
therefore ndbm) is based on an  algorithm  invented  by  Ken
Thompson, [Tho90, Tor87] and predates Larson's work.

     The sdbm programming interface  is  totally  compatible
with ndbm and includes a slight improvement in database ini-
tialization.  It is also expected  to  be  binary-compatible
under most UN*X versions that support the ndbm library.

     The sdbm implementation shares the shortcomings of  the
ndbm library, as a side effect of various simplifications to
the original Larson algorithm. It does produce holes in  the
page file as it writes pages past the end of file. (Larson's
paper include a clever solution to this problem  that  is  a
result of using the hash value directly as a block address.)
On the other hand, extensive tests  seem  to  indicate  that
sdbm creates fewer holes in general, and the resulting page-
files are smaller. The sdbm implementation  is  also  faster
than  ndbm  in database creation.  Unlike the ndbm, the sdbm
_________________________

  [1] UN*X is not a trademark of any (dis)organization.









                           - 2 -


store operation will not ``wander away'' trying to split its
data  pages  to insert a datum that cannot (due to elaborate
worst-case situations) be inserted. (It will  fail  after  a
pre-defined number of attempts.)

Important Compatibility Warning

     The sdbm and ndbm libraries cannot share databases: one
cannot  read  the  (dir/pag)  database created by the other.
This is due to the differences between  the  ndbm  and  sdbm
algorithms[2], and the hash functions used.  It is  easy  to
convert  between the dbm/ndbm databases and sdbm by ignoring
the index completely: see dbd, dbu etc.


Notice of Intellectual Property

The entire sdbm  library package, as authored by me, Ozan S.
Yigit,  is  hereby placed in the public domain. As such, the
author is not responsible for the  consequences  of  use  of
this  software, no matter how awful, even if they arise from
defects in it. There is no expressed or implied warranty for
the sdbm library.

     Since the sdbm library package is in the public domain,
this   original  release  or  any  additional  public-domain
releases of the modified original cannot possibly (by defin-
ition) be withheld from you. Also by definition, You (singu-
lar) have all the rights to this code (including  the  right
to sell without permission, the right to  hoard[3]  and  the
right  to  do  other  icky  things as you see fit) but those
rights are also granted to everyone else.

     Please note that all  previous  distributions  of  this
software  contained  a  copyright  (which is now dropped) to
protect its origins and its  current  public  domain  status
against any possible claims and/or challenges.

Acknowledgments

     Many people have been very helpful and  supportive.   A
partial  list  would  necessarily  include Rayan Zacherissen
(who contributed the  man  page,  and  also  hacked  a  MMAP
_________________________

  [2] Torek's   discussion   [Tor87]   indicates   that
dbm/ndbm implementations use the hash value to traverse
the radix trie differently than sdbm and as  a  result,
the page indexes are generated in different order.  For
more information, send e-mail to the author.
  [3] You  cannot really hoard something that is avail-
able to the public at large, but try if  it  makes  you
feel any better.










                           - 3 -


version of sdbm), Arnold Robbins, Chris Lewis,  Bill  David-
sen,  Henry  Spencer,  Geoff  Collyer, Rich Salz (who got me
started in the first place), Johannes Ruschein (who did  the
minix port) and David Tilbrook. I thank you all.

Distribution Manifest and Notes

This distribution of sdbm includes (at least) the following:

    CHANGES     change log
    README      this file.
    biblio      a small bibliography on external hashing
    dba.c       a crude (n/s)dbm page file analyzer
    dbd.c       a crude (n/s)dbm page file dumper (for conversion)
    dbe.1       man page for dbe.c
    dbe.c       Janick's database editor
    dbm.c       a dbm library emulation wrapper for ndbm/sdbm
    dbm.h       header file for the above
    dbu.c       a crude db management utility
    hash.c      hashing function
    makefile    guess.
    pair.c      page-level routines (posted earlier)
    pair.h      header file for the above
    readme.ms   troff source for the README file
    sdbm.3      man page
    sdbm.c      the real thing
    sdbm.h      header file for the above
    tune.h      place for tuning & portability thingies
    util.c      miscellaneous

     dbu is a simple database manipulation  program[4]  that
tries to look like Bell Labs' cbt utility. It  is  currently
incomplete in functionality.  I use dbu to test out the rou-
tines: it takes (from stdin) tab separated  key/value  pairs
for commands like build or insert or takes keys for commands
like delete or look.

    dbu <build|creat|look|insert|cat|delete> dbmfile

     dba is a crude analyzer of dbm/sdbm/ndbm page files. It
scans the entire page file, reporting page level statistics,
and totals at the end.

     dbd is a crude dump  program  for  dbm/ndbm/sdbm  data-
bases.  It  ignores  the bitmap, and dumps the data pages in
sequence. It can be used to create input for the  dbu  util-
ity.   Note that dbd will skip any NULLs in the key and data
fields,  thus  is  unsuitable  to  convert   some   peculiar
_________________________

  [4] The dbd, dba, dbu utilities are quick  hacks  and
are  not  fit  for  production use. They were developed
late one night, just to test out sdbm, and convert some
databases.









                           - 4 -


databases that insist in including the terminating null.

     I have also included a copy of the dbe  (ndbm  DataBase
Editor)  by  Janick Bergeron [janick@bnr.ca] for your pleas-
ure. You may find it more useful than the little  dbu  util-
ity.

     dbm.[ch] is a dbm library emulation on top of ndbm (and
hence suitable for sdbm). Written by Robert Elz.

     The sdbm library has been around in beta test for quite
a  long  time,  and from whatever little feedback I received
(maybe no news is good news), I believe it  has  been  func-
tioning  without  any  significant  problems.  I  would,  of
course, appreciate all fixes and/or improvements.  Portabil-
ity enhancements would especially be useful.

Implementation Issues

     Hash functions: The algorithm behind  sdbm  implementa-
tion  needs a good bit-scrambling hash function to be effec-
tive. I ran into a set of constants for a simple hash  func-
tion  that  seem  to  help sdbm perform better than ndbm for
various inputs:

    /*
     * polynomial conversion ignoring overflows
     * 65599 nice. 65587 even better.
     */
    long
    dbm_hash(char *str, int len) {
        register unsigned long n = 0;

        while (len--)
            n = n * 65599 + *str++;
        return n;
    }

     There may be better hash functions for the purposes  of
dynamic hashing.  Try your favorite, and check the pagefile.
If it contains too many pages with too many holes, (in rela-
tion  to this one for example) or if sdbm simply stops work-
ing (fails after SPLTMAX attempts to split)  when  you  feed
your  NEWS  history  file  to it, you probably do not have a
good hashing function.  If  you  do  better  (for  different
types of input), I would like to know about the function you
use.

     Block sizes: It seems (from  various  tests  on  a  few
machines)  that a page file block size PBLKSIZ of 1024 is by
far the best for performance, but this also happens to limit
the  size  of a key/value pair. Depending on your needs, you
may wish to increase the page size, and also adjust  PAIRMAX
(the maximum size of a key/value pair allowed: should always









                           - 5 -


be at least three words smaller than PBLKSIZ.)  accordingly.
The  system-wide  version  of the library should probably be
configured with 1024 (distribution default), as this appears
to be sufficient for most common uses of sdbm.

Portability

     This package has been tested in many  different  UN*Xes
even including minix, and appears to be reasonably portable.
This does not mean it will port easily to non-UN*X systems.

Notes and Miscellaneous

     The sdbm is not a very complicated  package,  at  least
not  after  you  familiarize yourself with the literature on
external hashing. There are other interesting algorithms  in
existence  that ensure (approximately) single-read access to
a data value associated with any key. These  are  directory-
less schemes such as linear hashing [Lit80] (+ Larson varia-
tions), spiral storage [Mar79] or directory schemes such  as
extensible  hashing  [Fag79] by Fagin et al. I do hope these
sources provide a reasonable playground for  experimentation
with  other algorithms.  See the June 1988 issue of ACM Com-
putting Surveys [Enb88] for  an  excellent  overview  of  the
field.

References


[Lar78]
    P.-A. Larson, ``Dynamic Hashing'', BIT, vol.   18,   pp.
    184-201, 1978.

[Tho90]
    Ken Thompson, private communication, Nov. 1990

[Lit80]
    W. Litwin, `` Linear Hashing: A new tool  for  file  and
    table addressing'', Proceedings of the 6th Conference on
    Very Large  Dabatases  (Montreal), pp.   212-223,   Very
    Large Database Foundation, Saratoga, Calif., 1980.

[Fag79]
    R. Fagin, J.  Nievergelt,  N.  Pippinger,  and   H.   R.
    Strong,  ``Extendible Hashing - A Fast Access Method for
    Dynamic Files'', ACM  Trans.  Database  Syst.,  vol.  4,
    no.3, pp. 315-344, Sept. 1979.

[Wal84]
    Rich Wales, ``Discussion of "dbm"  data  base  system'',
    USENET newsgroup unix.wizards, Jan. 1984.

[Tor87]
    Chris Torek,  ``Re:   dbm.a   and   ndbm.a   archives'',









                           - 6 -


    USENET newsgroup comp.unix, 1987.

[Mar79]
    G. N. Martin, ``Spiral Storage: Incrementally   Augment-
    able   Hash  Addressed  Storage'', Technical Report #27,
    University of Varwick, Coventry, U.K., 1979.

[Enb88]
    R.  J.  Enbody  and  H.   C.   Du,   ``Dynamic   Hashing
    Schemes'',ACM  Computting  Surveys,  vol.  20, no. 2, pp.
    85-113, June 1988.