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

From: Jonathan Nieder <jrnieder@gmail.com>
Date: May 29, 2010, 07:18 UTC
Message-ID: <20100529071811.GA6648@progeny.tock>
In-Reply-To: <1274650832-7411-3-git-send-email-artagnon@gmail.com>

Hi Ram,

Ramkumar Ramachandra wrote:

> Taken directly
> from David Michael Barr's svn-dump-fast-export repository.

More details:

  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>

I stole most of the description from [1].

Show 15 quoted lines

> --- /dev/null
> +++ b/vcs-svn/trp.h
> @@ -0,0 +1,221 @@
> +/******************************************************************************
> + *
> + * cpp macro implementation of treaps.
> + *
> + * Usage:
> + *
> + *   #include <trp.h>
> + *   trp(...)
> + *   trp_gen(...)
> + *   ...
> + *
> + ******************************************************************************/

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?

If style nitpicking were appropriate, I would say that comments in C code written specifically for git should look like this:

   /*
    * cpp macro implementation of treaps.
   [...]
    */

Okay. :)

Show 5 quoted lines

> +
> +#ifndef TRP_H_
> +#define	TRP_H_
> +
> +#include <stdint.h>

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

Show 5 quoted lines

> +/* Pointer/Offset conversion */
> +#define trpn_pointer(a_base, a_offset)					\
> +    (a_base##_pointer(a_offset))
> +#define trpn_offset(a_base, a_pointer)				        \
> +    (a_base##_offset(a_pointer))

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.

> +/* Priority accessors. */
> +#define	trp_prio_get(a_type, a_field, a_node)				\
> +    (2654435761*(uint32_t)(uintptr_t)(a_node))

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

> +/*
> + * The trp_gen() macro generates a type-specific treap implementation,
> + * based on the above cpp macros.

[...]

Show 28 quoted lines

> + * Assuming the following setup:
> + *
> + *   typedef struct ex_node_s ex_node_t;
> + *   struct ex_node_s {
> + *       trp_node(ex_node_t) ex_link;
> + *   };
> + *   typedef trp(ex_node_t) ex_t;
> + *   static ex_node_t ex_base[MAX_NODES];
> + *   trp_gen(static, ex_, ex_t, ex_node_t, ex_link, ex_base, ex_cmp)
> + *
> + * The following API is generated:
> + *
> + *   static void
> + *   ex_new(ex_t *treap);
> + *       Description: Initialize a treap structure.
> + *       Args:
> + *         treap: Pointer to an uninitialized treap object.
> + *
> + *   static ex_node_t *
> + *   ex_psearch(ex_t *treap, ex_node_t *key);
> + *       Description: Search for node that matches key.  If no match is found,
> + *                    return what would be key's successor/predecessor, were
> + *                    key in treap.
> + *       Args:
> + *         treap: Pointer to a initialized treap object.
> + *         key  : Search key.
> + *       Ret: Node in treap that matches key, or if no match, hypothetical
> + *            node's successor/predecessor (NULL if no successor/predecessor).

[...]

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

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

Thanks, Jonathan

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