Re: [PATCH 2/7] Add cpp macro implementation of treaps

From: Ramkumar Ramachandra <artagnon@gmail.com>
Date: May 30, 2010, 09:09 UTC
Message-ID: <AANLkTilHgXD1mzrTE0PQKeLWM7uheNmZ62ZJGGxuh-7E@mail.gmail.com>
In-Reply-To: <20100529071811.GA6648@progeny.tock>

Hi Jonathan,

Jonathan Nieder <jrnieder@gmail.com> wrote:

Show 14 quoted lines

>  From: Jason Evans <jasone@canonware.com>
>
>  Treaps provide a memory-efficient binary search tree structure.
>  Insertion/deletion/search are about as about as fast in the average
>  case as red-black trees and the chances of worst-case behavior are
>  vanishingly small, thanks to (pseudo-)randomness.  That is a small
>  price to pay, given that treaps are much simpler to implement.
>
>  [db: Altered to reference nodes by offset from a common base pointer]
>  [db: Bob Jenkins' hashing implementation dropped for Knuth's]
>  [db: Methods unnecessary for search and insert dropped]
>
>  Signed-off-by: David Barr <david.barr@cordelta.com>
>  Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com>

Thanks. This can go into the commit message when I re-send the series.

> I don’t know if style nitpicking is welcome here, given that the
> code comes from elsewhere.  Should we be trying to keep the code
> close to Jason’s version (and sending patches upstream as needed),
> or is that not worth the trouble?

In my opinion, style nitpicks are welcome: it should conform to the git.git style. I'm anyway maintaining a separate branch of master just for changes specific to the git.git merge- Jason and David are welcome to pull patches from there.

> #include "../git-compat-util.h" would be more portable.

Right, this should be one major change in all the files in the git-merge branch.

> These are defined in obj_pool.h?  Maybe this would be easier to
> understand if the patch to add that file came sooner in the series.

Okay. Note that in the revision history, trp.h was first imported, and then culled to use obj_pool.h by David.

> Where does this magic number come from?  (I assume Knuth, but it
> would be nice to include a reference or explanation.)

Indeed. 2654435761 is the golden ratio number corresponding with 2^32. See http://bit.ly/cwAfD4

> Neat.  Maybe this description should go in a file in
> Documentation/technical, to make trp.h itself a little less daunting.

Okay, I'll put it in a separate file then.

> Also: http://www.canonware.com/trp/ seems to provide a test program;
> do you think it would make sense to include it as well?

Probably in documentation/technical?

> [1] http://t-t-travails.blogspot.com/2008/07/treaps-versus-red-black-trees.html

This is a good read, thanks.

-- Ram