🚀 go-pugleaf

Okay, I've taken people's suggestions into account, and now have an updated
implementation of my in-memory B-tree.  The documentation and some
miscellaneous stuff follow in "shar" format, and the actual implementation
will appear in a subsequent posting.

The changes I've made are the following:
- Added first/next/last/prev browsing capability
- Added "big-O" performance figures to the documentation
- Split the implementation into several files that a linker can mix and
  match as needed to save space
- Ported to VMS
- Included troff source for documentation

My questions now are:

- Is this still a reusable component?
- Is it an improvement over the previous attempt?
- How can it be improved still further?
- If you were building a system in C, would _you_, personally, use it?  Why,
  or why not?
- If this were installed in a much larger component library, would you use it?
  Why, or why not?

Paul Sander
paul@Atherton.COM
(408) 734-9822
--------------------------------
#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create:
#	README
#	btree.doc
#	Makefile
#	Makefile.vms
#	btree.man
# This archive created: Fri Aug 17 20:48:29 1990
export PATH; PATH=/bin:/usr/bin:$PATH
if test -f 'README'
then
	echo shar: "will not over-write existing file 'README'"
else
cat << \SHAR_EOF > 'README'
This directory contains source code to an in-memory B-tree implementation.
The tree can hold arbitrary keys, but duplicate keys cannot be inserted.
Also, this was written in K&R C, so please handle accordingly.

This implementation has been placed in the public domain by its author,
Paul Sander, to be used as you wish.  However, if you add neat new features,
I'd appreciate having a copy sent to me at paul.Atherton.COM, or
sun!athertn!paul .

Following are the files included, and create a library called libbtree.a on
Unix, and LIBBTREE.OLB on VMS.

Makefile	Rules for building library and test case (SunOS)
Makefile.vms	Rules for building library and test case (VMS MMS)
README		This file
bt_last.c	Implementation of bt_last function
bt_next.c	Implementation of bt_next function
bt_prev.c	Implementation of bt_prev function
btdelete.c	Implementation of bt_delete function
btdestroy.c	Implementation of bt_destroy function
btdump.c	Implementation of bt_dump function (non-portable)
btfirst.c	Implementation of bt_first function
btinsert.c	Implementation of bt_insert function
btmalloc.c	Heap utilities used for debugging
btnew.c		Implementation of bt_new function
btpriv.h	Private header file used by B-tree source files
btree.doc	Formatted man page, this is ASCII text
btree.h		Public include file, to be used by B-tree clients
btree.man	Man page source -- format with "[tn]roff -man"
btsearch.c	Implementation of bt_search function
bttraverse.c	Implementation of bt_traverse function
btutil.c	Utility functions
test.c		Test case, links with library to make executable
SHAR_EOF
fi
if test -f 'btree.doc'
then
	echo shar: "will not over-write existing file 'btree.doc'"
else
cat << \SHAR_EOF > 'btree.doc'



BTREE()           MISC. REFERENCE MANUAL PAGES            BTREE()



NAME
     bt_dump,   bt_search,   bt_new,    bt_destroy,    bt_insert,
     bt_traverse, bt_delete - In-memory B-tree manipulation

SYNOPSIS
     #include <btree.h>

     BTREE     bt_new(order,comp)
     int  order;
     int  (*comp)();

     void bt_destroy(tree,free_key)
     BTREE     tree;
     void (*free_key)();

     int bt_insert(tree,key)
     BTREE     tree;
     char *key;

     char *bt_delete(tree,key)
     BTREE     tree;
     char *key;

     char *bt_search(tree,target)
     BTREE     tree;
     char *target;

     void bt_traverse(tree,fn,parms)
     BTREE     tree;
     void (*fn)();
     char *parms;

     void bt_dump(tree,key_dump)
     BTREE     tree;
     void (*key_dump)();

     char *bt_first(tree)
     BTREE     tree;

     char *bt_last(tree)
     BTREE     tree;

     char *bt_next(tree)
     BTREE     tree;

     char *bt_prev(tree)
     BTREE     tree;

DESCRIPTION
     These functions implement an in-memory  B-tree  data  struc-
     ture.   The tree itself stores only pointers to the client's
     data,  and  relies  on  client-provided  functions  for  any



Sun Release 4.0           Last change:                          1






BTREE()           MISC. REFERENCE MANUAL PAGES            BTREE()



     comparisons and storage deallocation.

     bt_new creates a  new  B-tree.   The  client  specifies  the
     desired  order  (the maximum number of children allowed each
     node) of the tree (for performance trade-offs based  on  the
     efficiency  of  comparisons  of client-provided data), and a
     pointer to a function that compares two client-provided data
     structures.   The comparison function, comp, has the follow-
     ing interface:
          int comp(k1,k2)
          char *k1,*k2;
     The result of this function is -1 if the object  pointed  to
     by  k1 is "less than" the object pointed to by k2, 0 if they
     are "equal", and 1 otherwise.  Client-provided  data  struc-
     tures  that  compare  greater  by  this function will appear
     later in the lexical order of the data stored in  the  tree.
     bt_new returns a pointer to a handle for the B-tree, or NULL
     if an error occurs.

     bt_destroy deallocates all storage allocated  to  a  B-tree.
     The  client provides a pointer to a visitation function that
     is called once for each item stored in the tree.  The  items
     are  visited  in arbitrary order.  If NULL is passed instead
     of a pointer to a function,  no  action  is  taken  for  the
     client-provided  data,  but  the  tree  structure  itself is
     freed.

     bt_insert inserts a new item into the tree.  1  is  returned
     if  the  insertion was successful, -1 is returned if the new
     item matches another item that  has  already  been  inserted
     into the tree, and 0 is returned in the event of an error.

     bt_delete deletes an item from a tree.  The  value  returned
     is  the  same  as that passed to bt_insert when the item was
     inserted, or NULL if the item is not found.

     bt_search searches  for  an  item  in  a  tree.   The  value
     returned  is  the  same as that passed to bt_insert when the
     item was inserted, or NULL if the item is not found.

     bt_traverse traverses the tree,  calling  a  client-provided
     visitation  function fn once for each item stored there.  fn
     has the following interface:
          void fn(item,parms)
          char *item;
          char *parms;
     item is the pointer stored when the item was  inserted  into
     the  tree.   parms  is  an arbitrary pointer that the client
     wishes to pass to the visitation function, but is  otherwise
     unused  by  the B-tree implementation.  Items are visited in
     their lexical order.




Sun Release 4.0           Last change:                          2






BTREE()           MISC. REFERENCE MANUAL PAGES            BTREE()



     bt_dump displays the contents of the tree to  stdout,  along
     with  some  diagnostic  and  statistical  information.   The
     key_dump function is called once for each item in the  tree,
     in arbitrary order.  It may be NULL if no action is desired.
     Its interface follows:
          void key_dump(item)
          char *item;

     bt_first returns the item that falls earliest in the lexical
     order  of  the items stored in the tree, or NULL if the tree
     is empty.

     bt_last returns the item that falls latest  in  the  lexical
     order  of  the items stored in the tree, or NULL if the tree
     is empty.

     bt_next returns the next item higher in  the  lexical  order
     after  the  last  key  returned  by  bt_first,  bt_next,  or
     bt_search.  If bt_search failed to  find  an  item,  bt_next
     returns  the  next item higher in the lexical order that was
     stored in the tree.  NULL is returned if the  last  call  to
     bt_next  returned  the  item  falling highest in the lexical
     order of the items stored in the tree, or if  the  tree  was
     modified since the last call to bt_next or bt_prev.

     bt_prev returns the next item lower  in  the  lexical  order
     after   the  last  key  returned  by  bt_last,  bt_next,  or
     bt_search.  If bt_search failed to  find  an  item,  bt_prev
     returns  the  next  item lower in the lexical order that was
     stored in the tree.  NULL is returned if the  last  call  to
     bt_prev  returned  the  item  falling  lowest in the lexical
     order of the items stored in the tree, or if  the  tree  was
     modified since the last call to bt_next or bt_prev.

     Worst case performance  characteristics  are  listed  below.
     Here,  "m"  is  number  passed  as  the "order" parameter to
     bt_new, and "n" is the number of items stored in the tree.
          bt_search:     O(m * log n)
          bt_new:        O(1)
          bt_destroy:    O(log n) + O(n)  when  free_key  is  not
                         NULL
                         O(log n) otherwise
          bt_insert:     O(m * log n)
          bt_delete:     O(m * log n)
          bt_traverse:   O(n)
          bt_next:       O(log n)
          bt_prev:       O(log n)
          bt_first:      O(log n)
          bt_last:       O(log n)

BUGS
     This implementation is written in K&R C, and tested only  on



Sun Release 4.0           Last change:                          3






BTREE()           MISC. REFERENCE MANUAL PAGES            BTREE()



     a Sun 3 running SunOS 4.0.3 and on VMS V5.3.

     This implementation assumes "char*" is the generic  pointer.
     This  goes against practice used by most "modern" compilers,
     but aids portability to older  compilers.   Note  also  that
     this will probably generate lots of complaints from Lint.

     bt_dump assumes that pointers are the same size as integers,
     and that they can be displayed in total in eight hexidecimal
     digits.













































Sun Release 4.0           Last change:                          4



SHAR_EOF
fi
if test -f 'Makefile'
then
	echo shar: "will not over-write existing file 'Makefile'"
else
cat << \SHAR_EOF > 'Makefile'
TARGET = libbtree.a

OBJECTS = btmalloc.o btutil.o bt_last.o bt_next.o bt_prev.o \
	btdelete.o btdestroy.o btdump.o btfirst.o btinsert.o btnew.o \
	btsearch.o bttraverse.o

$(TARGET): $(OBJECTS)
	ar r $@ $?
	ranlib $@

$(OBJECTS): btpriv.h

test:	test.o $(TARGET)
	cc -o test test.o $(TARGET) /usr/lib/debug/malloc.o

btree.doc: btree.man
	nroff -man btree.man > btree.doc

clean:
	rm *.o *.a *.doc test
SHAR_EOF
fi
if test -f 'Makefile.vms'
then
	echo shar: "will not over-write existing file 'Makefile.vms'"
else
cat << \SHAR_EOF > 'Makefile.vms'
TARGET = libbtree.olb

OBJECTS = btmalloc.obj btutil.obj bt_last.obj bt_next.obj \
	bt_prev.obj btdelete.obj btdestroy.obj btdump.obj btfirst.obj \
	btinsert.obj btnew.obj btsearch.obj bttraverse.obj

$(TARGET) : $(OBJECTS)
	if f$search("$(TARGET)") .eqs. "" then $library/create/object $@
	library/replace $@ $?

$(OBJECTS) : btpriv.h

test :	test.obj $(TARGET)
	link/exe=$@.exe test.obj,$(TARGET)/lib,sys$library:vaxcrtl.olb/lib

clean :
	delete *.obj;*,*.lib;*,test.exe
SHAR_EOF
fi
if test -f 'btree.man'
then
	echo shar: "will not over-write existing file 'btree.man'"
else
cat << \SHAR_EOF > 'btree.man'
.TH BTREE
.SH NAME
bt_dump, bt_search, bt_new, bt_destroy, bt_insert, bt_traverse, bt_delete -
In-memory B-tree manipulation
.SH SYNOPSIS
#include <btree.h>
.sp
BTREE	bt_new(order,comp)
.br
int	order;
.br
int	(*comp)();
.sp
void bt_destroy(tree,free_key)
.br
BTREE	tree;
.br
void	(*free_key)();
.sp
int bt_insert(tree,key)
.br
BTREE	tree;
.br
char	*key;
.sp
char	*bt_delete(tree,key)
.br
BTREE	tree;
.br
char	*key;
.sp
char *bt_search(tree,target)
.br
BTREE	tree;
.br
char	*target;
.sp
void bt_traverse(tree,fn,parms)
.br
BTREE	tree;
.br
void	(*fn)();
.br
char	*parms;
.sp
void bt_dump(tree,key_dump)
.br
BTREE	tree;
.br
void	(*key_dump)();
.sp
char *bt_first(tree)
.br
BTREE	tree;
.sp
char *bt_last(tree)
.br
BTREE	tree;
.sp
char *bt_next(tree)
.br
BTREE	tree;
.sp
char *bt_prev(tree)
.br
BTREE	tree;
.SH DESCRIPTION
These functions implement an in-memory B-tree data structure.  The tree
itself stores only pointers to the client's data, and relies on
client-provided functions for any comparisons and storage deallocation.
.sp
.B bt_new
creates a new B-tree.  The client specifies the desired order (the maximum
number of children allowed each node) of the tree
(for performance trade-offs based on the efficiency of comparisons of
client-provided data), and a pointer to a function that compares two
client-provided data structures.  The comparison function, 
.BR comp ,
has the following interface:
.RS
.B
int comp(k1,k2)
.br
.B
char *k1,*k2;
.RE
The result of this function is -1 if the object pointed to by k1 is "less than"
the object pointed to by k2, 0 if they are "equal", and 1 otherwise.
Client-provided data structures that
compare greater by this function will appear later in the lexical order
of the data stored in the tree.
.B bt_new
returns a pointer to a handle for the B-tree, or NULL if an error occurs.
.sp
.B bt_destroy
deallocates all storage allocated to a B-tree.  The client provides a pointer
to a visitation function that is called once for each item stored in the
tree.  The items are visited in arbitrary order.  If
NULL is passed instead of a pointer to a function, no action is taken for
the client-provided data, but the tree structure itself is freed.
.sp
.B bt_insert
inserts a new item into the tree.  1 is returned if the insertion was
successful, -1 is returned if the new item matches another item that has
already been inserted into the tree, and 0 is returned in the event of an
error.
.sp
.B bt_delete
deletes an item from a tree.  The value returned is the same as that passed
to
.B bt_insert
when the item was inserted, or NULL if the item is not found.
.sp
.B bt_search
searches for an item in a tree.  The value returned is the same as that passed
to
.B bt_insert
when the item was inserted, or NULL if the item is not found.
.sp
.B bt_traverse
traverses the tree, calling a client-provided visitation function
.B fn
once for each item stored there.
.B fn
has the following interface:
.RS
.B
void fn(item,parms)
.br
.B
char *item;
.B
.br
char *parms;
.RE
.B item
is the pointer stored when the item was inserted into the tree.
.B parms
is an arbitrary pointer that the client wishes to pass to the visitation
function, but is otherwise unused by the B-tree implementation.  Items
are visited in their lexical order.
.sp
.B bt_dump
displays the contents of the tree to stdout, along with some diagnostic and
statistical information.  The
.B key_dump
function is called once for each item in the tree, in arbitrary order.  It
may be NULL if no action is desired.  Its interface follows:
.RS
.B
void key_dump(item)
.br
.B
char *item;
.RE
.sp
.B bt_first
returns the item that falls earliest in the lexical order of the items
stored in the tree, or NULL if the tree is empty.
.sp
.B bt_last
returns the item that falls latest in the lexical order of the items
stored in the tree, or NULL if the tree is empty.
.sp
.B bt_next
returns the next item higher in the lexical order after the last key
returned by
.BR bt_first ,
.BR bt_next ,
.b bt_prev ,
or
.BR bt_search .
If
.B bt_search
failed to find an item,
.B bt_next
returns the next item higher in the
lexical order that was stored in the tree.  NULL is returned if
the last call to
.B bt_next
returned the item falling highest in the
lexical order of the items stored in the tree, or if the tree was
modified since the last call to
.B bt_next
or
.BR bt_prev .
.sp
.B bt_prev
returns the next item lower in the lexical order after the last key
returned by
.BR bt_last ,
.BR bt_next ,
.b bt_prev ,
or
.BR bt_search .
If
.B bt_search
failed to find an item,
.B bt_prev
returns the next item lower in the
lexical order that was stored in the tree.  NULL is returned if
the last call to
.B bt_prev
returned the item falling lowest in the
lexical order of the items stored in the tree, or if the tree was
modified since the last call to
.B bt_next
or
.BR bt_prev .
.sp
Worst case performance characteristics are listed below.  Here, "m" is number
passed as the "order" parameter to bt_new, and "n" is the number of items
stored in the tree.
.RS
bt_search:	O(m * log n)
.br
bt_new:		O(1)
.br
bt_destroy:	O(log n) + O(n) when free_key is not NULL
.br
		O(log n) otherwise
.br
bt_insert:	O(m * log n)
.br
bt_delete:	O(m * log n)
.br
bt_traverse:	O(n)
.br
bt_next:		O(log n)
.br
bt_prev:		O(log n)
.br
bt_first:		O(log n)
.br
bt_last:		O(log n)
.RE
.SH BUGS
This implementation is written in K&R C, and tested only on a Sun 3 running
SunOS 4.0.3 and on VMS V5.3.
.sp
This implementation assumes "char*" is the generic pointer.  This goes
against practice used by most "modern" compilers, but aids portability to
older compilers.  Note also that this will probably generate lots of
complaints from Lint.
.sp
.B bt_dump
assumes that pointers are the same size as integers, and that they can be
displayed in total in eight hexidecimal digits.
SHAR_EOF
fi
exit 0
#	End of shell archive
-- 
Paul Sander        (408) 734-9822  | "Passwords are like underwear," she said,
paul@Atherton.COM                  | "Both should be changed often."
{decwrl,pyramid,sun}!athertn!paul  | -- Bennett Falk in "Mom Meets Unix"