Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!decwrl!nsc!pyramid!athertn!paul From: paul@athertn.Atherton.COM (Paul Sander) Newsgroups: comp.sw.components Subject: Re: What is a reusable software component? Summary: Is this better? Message-ID: <28982@athertn.Atherton.COM> Date: 18 Aug 90 04:32:45 GMT References: <27705@athertn.Atherton.COM> <533@helios.prosys.se> <27914@athertn.Atherton.COM> Reply-To: paul@Atherton.COM (Paul Sander) Organization: Atherton Technology, Sunnyvale, CA Lines: 662 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 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 .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"