je**********@gmail.com wrote:
I have spent the last week or more looking for an implementation (open
source) for a deterministic skip lists. I am currently approaching the
completion of a data structure library I am implementing.
I have a randomized skip list completed; however, I require a
deterministic skip list. No matter how hard I look I can't seem to
find an implementation, or even the details to make my own.
In addition, there is a data structure called a forward-balancing B-
Tree that lets implementors lock sub-trees instead of the entire tree
itself. It does this by ensuring the tree is balanced ahead of time so
it can lock as little as possible.
Any ideas?
Google?
I admit, I had not heard of either. Google provides nothing relevant
when using "forward-balancing b-tree" as the search time, so I'm
wondering if you got the term right. You say one exists; why do you
think it does? Why does it appear that there's no one else on the
Internet who's ever heard of it?
As far as the skip-list goes, as near as I can tell from the
descriptions of the algorithm (including Pugh's own paper where he
published it), randomization is a key element of the data structure.
When you write "deterministic", what exactly is it that you want to be
deterministic about the skip-list? And what sort of trouble are you
having in applying that goal to your current implementation?
For both of your questions above, it's almost as if you are asking for
help implementing something that doesn't (or can't) exist. If that's
actually what's going on, then obviously you won't get an answer. If
it's not what's going on, then at the very least there seems to be some
ambiguities and/or inaccuracies in your question that you might want to
explore, to see if you can rephrase the question in a way more likely to
get the help you need.
Pete