Re: [PATCH 4/9] Add treap implementation

Ramkumar Ramachandra wrote:

David is currently working on
a Java implementation of a immutable ternary treap and will
re-implement it as C macros. See the ternary-treap branch.

I assume his blog post from a week or so ago[1] is relevant.

The trie-based version should be interesting but less generic (which
is fine, since we only have two users and both use string keys).

quoted

 $(VCSSVN_OBJS): \
-       vcs-svn/obj_pool.h
+       vcs-svn/obj_pool.h vcs-svn/trp.h

Interesting how you've shown this in every patch :)

It would have been less messy to use

 $(VCSSVN_OBJS): \
	vcs-svn/obj_pool.h \
	vcs-svn/trp.h \
	... \

or

 $(VCSSVN_OBJS): vcs-svn/obj_pool.h
 $(VCSSVN_OBJS): vcs-svn/trp.h
 ...

I just can’t bring myself to care much. :)

quoted

+/*
+ * Fibonacci hash function.
+ * The multiplier is the nearest prime to (2^32 times (√5 - 1)/2).
+ * See Knuth §6.4: volume 3, 3rd ed, p518.
+ */

Um, is it alright to put non-ascii characters in a file containing
code?

Yes, UTF-8 is sometimes used in comments for people’s names.  See
builtin/branch.c, for example.

The documentation is good, but I don't see it merged into the tree.
Perhaps send a patch to David?

Yes.  I should send some other patches, too, to minimize the delta.

Also, you might want to include the
technical explanation for using treaps from the commit message here?

Good idea, thanks!

Jonathan

[1] http://barrbrain.github.com/2010/06/19/relocatable-immutable-randomised-ternary-search-tree-part-2.html