Re: [PATCH 4/9] Add treap implementation

From: Ramkumar Ramachandra <artagnon@gmail.com>
Date: Jun 24, 2010, 19:08 UTC
Message-ID: <AANLkTinYmKl4M10l3u5V7deleqSzr7iJDqf7X6ghtwRM@mail.gmail.com>
In-Reply-To: <20100624105706.GD12376@burratino>

Hi again,

Jonathan Nieder wrote:

Show 7 quoted lines

> From: Jason Evans <jasone@canonware.com>
>
> Provide macros to generate a type-specific treap implementation and
> various functions to operate on it. It uses obj_pool.h to store memory
> nodes in a treap.  Previously committed nodes are never removed from
> the pool; after any *_commit operation, it is assumed (correctly, in
> the case of svn-fast-export) that someone else must care about them.

This is likely to change in a few days. 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.

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

Show 5 quoted lines

> +/*
> + * 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? I haven't seen such a thing in any of the other files. Will some old compilers complain while parsing?

> --- /dev/null
> +++ b/vcs-svn/trp.txt
> @@ -0,0 +1,90 @@
> +treap API

The documentation is good, but I don't see it merged into the tree. Perhaps send a patch to David? Also, you might want to include the technical explanation for using treaps from the commit message here?

-- Ram