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

[Jonathan Nieder <jrnieder@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].

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

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

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

> +/* 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.
[...]
> + * 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