Re: [PATCH 4/9] Add treap implementation

[Jonathan Nieder <jrnieder@gmail.com>]

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).

>>  $(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. :)

> > +/*
> > + * 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