Possible Glib BTree substitute



> 	I am preparing some source code for submittal to Glib.  It'll be a
> while before I actually submit it [...]

	There's been some discussion about a Glib Tree recently, so I've
decided to go ahead and submit this now.  I will be working on a sample
application over the next several days, so hopefully I can show its
viability through example in the near future.

	I have implemented a skip list/balanced tree hybrid structure (in
the Glib style) that may be preferable to a tree implementation.  It
should be much faster than a BTree, and I believe the code is simpler.  
It allows the user to do (average: log n) searches on either the data,
using a GCompareFunc, or on the index number of the element.  It's
probability-based, so it the search time doesn't depend on the type of
data being stored.  I wrote it for a project I'm working on, but I
designed it to be of general-purpose use.

	A complete overview with source code can be found at:

http://www.kd-dev.com/~dereks/skip/

	(I would post the overview here, but there are a couple of
pictures in the HTML).

	I believe this can be used as (a) a substitute for a balanced
tree, and (b) as a very fast linked list (see the URL for more
explanation).  The API is very, very similar to the GList API.  If this
turns out to be generally useful, it is my hope that it can be included
into Glib.

	There is still a little bit of work to be done, so I encourage
comments and criticism.


Thank You,
Derek Simkowiak
dereks@kd-dev.com



[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]