git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
Ramkumar Ramachandra <artagnon@gmail.com>
Date
May 23, 2010, 21:40 UTC
Message-ID
<1274650832-7411-3-git-send-email-artagnon@gmail.com>
In-Reply-To
<1274650832-7411-1-git-send-email-artagnon@gmail.com>

The implementation exposes an API to generate type-specific treap implmentation and various functions to operate on it. Taken directly from David Michael Barr's svn-dump-fast-export repository.

Signed-off-by: Ramkumar Ramachandra <artagnon@gmail.com>
---
 vcs-svn/trp.h |  221 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 221 insertions(+), 0 deletions(-)
 create mode 100644 vcs-svn/trp.h
diff --git a/vcs-svn/trp.h b/vcs-svn/trp.h
new file mode 100644
index 0000000..d40f9d3
--- /dev/null
+++ b/vcs-svn/trp.h
@@ -0,0 +1,221 @@
+/******************************************************************************
+ *
+ * cpp macro implementation of treaps.
+ *
+ * Usage:
+ *
+ *   #include <trp.h>
+ *   trp(...)
+ *   trp_gen(...)
+ *   ...
+ *
+ ******************************************************************************/
+
+#ifndef TRP_H_
+#define	TRP_H_
+
+#include <stdint.h>
+
+/* Node structure. */
+#define	trp_node(a_type)						\
+struct {								\
+    uint32_t trpn_left;							\
+    uint32_t trpn_right;						\
+}
+
+/* Root structure. */
+#define	trp(a_type)							\
+struct {								\
+    uint32_t trp_root;							\
+}
+
+/* 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))
+
+/* Left accessors. */
+#define	trp_left_get(a_base, a_type, a_field, a_node)			\
+    trpn_pointer(a_base, (a_node)->a_field.trpn_left)
+#define	trp_left_set(a_base, a_type, a_field, a_node, a_left) do {	\
+    (a_node)->a_field.trpn_left = trpn_offset(a_base, a_left);	        \
+} while (0)
+
+/* Right accessors. */
+#define	trp_right_get(a_base, a_type, a_field, a_node)			\
+    trpn_pointer(a_base, (a_node)->a_field.trpn_right)
+#define	trp_right_set(a_base, a_type, a_field, a_node, a_right) do {	\
+    (a_node)->a_field.trpn_right = trpn_offset(a_base, a_right);        \
+} while (0)
+
+/* Priority accessors. */
+#define	trp_prio_get(a_type, a_field, a_node)				\
+    (2654435761*(uint32_t)(uintptr_t)(a_node))
+
+/* Node initializer. */
+#define	trp_node_new(a_base, a_type, a_field, a_trp, a_node) do {	\
+    trp_left_set(a_base, a_type, a_field, (a_node), NULL);		\
+    trp_right_set(a_base, a_type, a_field, (a_node), NULL);		\
+} while (0)
+
+/* Tree initializer. */
+#define	trp_new(a_type, a_base, a_trp) do {		        	\
+    (a_trp)->trp_root = trpn_offset(a_base, NULL);			\
+} while (0)
+
+/* Internal utility macros. */
+#define	trpn_rotate_left(a_base, a_type, a_field, a_node, r_node) do {	\
+    (r_node) = trp_right_get(a_base, a_type, a_field, (a_node));	\
+    trp_right_set(a_base, a_type, a_field, (a_node),			\
+      trp_left_get(a_base, a_type, a_field, (r_node)));			\
+    trp_left_set(a_base, a_type, a_field, (r_node), (a_node));		\
+} while (0)
+
+#define	trpn_rotate_right(a_base, a_type, a_field, a_node, r_node) do {	\
+    (r_node) = trp_left_get(a_base, a_type, a_field, (a_node));		\
+    trp_left_set(a_base, a_type, a_field, (a_node),			\
+      trp_right_get(a_base, a_type, a_field, (r_node)));		\
+    trp_right_set(a_base, a_type, a_field, (r_node), (a_node));		\
+} while (0)
+
+/*
+ * The trp_gen() macro generates a type-specific treap implementation,
+ * based on the above cpp macros.
+ *
+ * Arguments:
+ *
+ *   a_attr     : Function attribute for generated functions (ex: static).
+ *   a_pre      : Prefix for generated functions (ex: treap_).
+ *   a_t_type   : Type for treap data structure (ex: treap_t).
+ *   a_type     : Type for treap node data structure (ex: treap_node_t).
+ *   a_field    : Name of treap node linkage (ex: treap_link).
+ *   a_base     : Expression for the base pointer from which nodes are offset.
+ *   a_cmp      : Node comparison function name, with the following prototype:
+ *                  int (a_cmp *)(a_type *a_node, a_type *a_other);
+ *                                        ^^^^^^
+ *                                     or a_key
+ *                Interpretation of comparision function return values:
+ *                  -1 : a_node <  a_other
+ *                   0 : a_node == a_other
+ *                   1 : a_node >  a_other
+ *                In all cases, the a_node or a_key macro argument is the first
+ *                argument to the comparison function, which makes it possible
+ *                to write comparison functions that treat the first argument
+ *                specially.
+ *
+ * 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).
+ *
+ *   static void
+ *   ex_insert(ex_t *treap, ex_node_t *node);
+ *       Description: Insert node into treap.
+ *       Args:
+ *         treap: Pointer to a initialized treap object.
+ *         node : Node to be inserted into treap.
+ */
+#define	trp_gen(a_attr, a_pre, a_t_type, a_type, a_field, a_base, a_cmp)\
+a_attr void								\
+a_pre##new(a_t_type *treap) {           				\
+    trp_new(a_type, a_base, treap);			        	\
+}									\
+a_attr a_type *								\
+a_pre##search(a_t_type *treap, a_type *key) {				\
+    a_type *ret;							\
+    int cmp;								\
+    ret = trpn_pointer(a_base, treap->trp_root);			\
+    while (ret != NULL							\
+      && (cmp = (a_cmp)(key, ret)) != 0) {				\
+	if (cmp < 0) {							\
+	    ret = trp_left_get(a_base, a_type, a_field, ret);		\
+	} else {							\
+	    ret = trp_right_get(a_base, a_type, a_field, ret);		\
+	}								\
+    }									\
+    return (ret);							\
+}									\
+a_attr a_type *								\
+a_pre##psearch(a_t_type *treap, a_type *key) {				\
+    a_type *ret;							\
+    a_type *tnode = trpn_pointer(a_base, treap->trp_root);		\
+    ret = NULL;								\
+    while (tnode != NULL) {						\
+	int cmp = (a_cmp)(key, tnode);					\
+	if (cmp < 0) {							\
+	    tnode = trp_left_get(a_base, a_type, a_field, tnode);	\
+	} else if (cmp > 0) {						\
+	    ret = tnode;						\
+	    tnode = trp_right_get(a_base, a_type, a_field, tnode);	\
+	} else {							\
+	    ret = tnode;						\
+	    break;							\
+	}								\
+    }									\
+    return (ret);							\
+}									\
+a_attr a_type *								\
+a_pre##insert_recurse(a_type *cur_node, a_type *ins_node) {		\
+    if (cur_node == NULL) {						\
+	return (ins_node);						\
+    } else {								\
+	a_type *ret;							\
+	int cmp = a_cmp(ins_node, cur_node);				\
+	if (cmp < 0) {							\
+	    a_type *left = a_pre##insert_recurse(trp_left_get(a_base,	\
+              a_type, a_field, cur_node), ins_node);			\
+	    trp_left_set(a_base, a_type, a_field, cur_node, left);	\
+	    if (trp_prio_get(a_type, a_field, left) <			\
+	      trp_prio_get(a_type, a_field, cur_node)) {		\
+		trpn_rotate_right(a_base, a_type, a_field, cur_node,	\
+                  ret);							\
+	    } else {							\
+		ret = cur_node;						\
+	    }								\
+	} else {							\
+	    a_type *right = a_pre##insert_recurse(trp_right_get(a_base, \
+	      a_type, a_field, cur_node), ins_node);			\
+	    trp_right_set(a_base, a_type, a_field, cur_node, right);	\
+	    if (trp_prio_get(a_type, a_field, right) <			\
+	      trp_prio_get(a_type, a_field, cur_node)) {		\
+		trpn_rotate_left(a_base, a_type, a_field, cur_node,	\
+                  ret);							\
+	    } else {							\
+		ret = cur_node;						\
+	    }								\
+	}								\
+	return (ret);							\
+    }									\
+}									\
+a_attr void								\
+a_pre##insert(a_t_type *treap, a_type *node) {				\
+    trp_node_new(a_base, a_type, a_field, treap, node);			\
+    treap->trp_root = trpn_offset(a_base, a_pre##insert_recurse(        \
+        trpn_pointer(a_base, treap->trp_root), node));	                \
+}
+#endif                          /* TRP_H_ */

-- 
1.7.1
Previous: Ramkumar RamachandraNext: Jonathan Nieder
Message 3 of 29 in “Import David's SVN exporter”
  1. 0/7 Import David's SVN exporterRamkumar Ramachandra, May 23, 2010
  2. 1/7 Add skeleton remote helper for SVNRamkumar Ramachandra, May 23, 2010
  3. 2/7 Add cpp macro implementation of treapsRamkumar Ramachandra, May 23, 2010
  4. Jonathan NiederMay 29, 2010
  5. Ramkumar RamachandraMay 30, 2010
  6. Jonathan NiederMay 30, 2010
  7. Ramkumar RamachandraMay 30, 2010
  8. 3/7 Add buffer pool libraryRamkumar Ramachandra, May 23, 2010
  9. Peter BaumannMay 24, 2010
  10. Ramkumar RamachandraMay 24, 2010
  11. David Michael BarrMay 24, 2010
  12. Jonathan NiederMay 29, 2010
  13. David Michael BarrMay 29, 2010
  14. 4/7 Add a memory pool libraryRamkumar Ramachandra, May 23, 2010
  15. Jonathan NiederMay 29, 2010
  16. Ramkumar RamachandraMay 30, 2010
  17. Jonathan NiederMay 30, 2010
  18. Ramkumar RamachandraMay 30, 2010
  19. 5/7 Add API for string-specific memory poolRamkumar Ramachandra, May 23, 2010
  20. Jonathan NiederMay 29, 2010
  21. Ramkumar RamachandraMay 30, 2010
  22. Jonathan NiederMay 30, 2010
  23. Ramkumar RamachandraMay 30, 2010
  24. 6/7 Add SVN revision parser and exporterRamkumar Ramachandra, May 23, 2010
  25. Jonathan NiederMay 29, 2010
  26. Ramkumar RamachandraMay 30, 2010
  27. 7/7 Add handler for SVN dumpRamkumar Ramachandra, May 23, 2010
  28. Jonathan NiederMay 30, 2010
  29. Ramkumar RamachandraMay 30, 2010

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.