Merge commit 'v1.7.6' into jc/checkout-reflog-fix

* commit 'v1.7.6': (3211 commits)
  Git 1.7.6
  completion: replace core.abbrevguard to core.abbrev
  Git 1.7.6-rc3
  Documentation: git diff --check respects core.whitespace
  gitweb: 'pickaxe' and 'grep' features requires 'search' to be enabled
  t7810: avoid unportable use of "echo"
  plug a few coverity-spotted leaks
  builtin/gc.c: add missing newline in message
  tests: link shell libraries into valgrind directory
  t/Makefile: pass test opts to valgrind target properly
  sh-i18n--envsubst.c: do not #include getopt.h
  Fix typo: existant->existent
  Git 1.7.6-rc2
  gitweb: do not misparse nonnumeric content tag files that contain a digit
  Git 1.7.6-rc1
  fetch: do not leak a refspec
  t3703: skip more tests using colons in file names on Windows
  gitweb: Fix usability of $prevent_xss
  gitweb: Move "Requirements" up in gitweb/INSTALL
  gitweb: Describe CSSMIN and JSMIN in gitweb/INSTALL
  ...

1 files changed, 70 insertions, 0 deletions

diff --git a/test-treap.c b/test-treap.c
new file mode 100644
index 0000000000..ab8c951c6e
--- /dev/null
+++ b/test-treap.c
@@ -0,0 +1,70 @@
+/*
+ * test-treap.c: code to exercise the svn importer's treap structure
+ */
+
+#include "cache.h"
+#include "vcs-svn/obj_pool.h"
+#include "vcs-svn/trp.h"
+
+struct int_node {
+	uintmax_t n;
+	struct trp_node children;
+};
+
+obj_pool_gen(node, struct int_node, 3)
+
+static int node_cmp(struct int_node *a, struct int_node *b)
+{
+	return (a->n > b->n) - (a->n < b->n);
+}
+
+trp_gen(static, treap_, struct int_node, children, node, node_cmp)
+
+static void strtonode(struct int_node *item, const char *s)
+{
+	char *end;
+	item->n = strtoumax(s, &end, 10);
+	if (*s == '\0' || (*end != '\n' && *end != '\0'))
+		die("invalid integer: %s", s);
+}
+
+int main(int argc, char *argv[])
+{
+	struct strbuf sb = STRBUF_INIT;
+	struct trp_root root = { ~0 };
+	uint32_t item;
+
+	if (argc != 1)
+		usage("test-treap < ints");
+
+	while (strbuf_getline(&sb, stdin, '\n') != EOF) {
+		struct int_node *node = node_pointer(node_alloc(1));
+
+		item = node_offset(node);
+		strtonode(node, sb.buf);
+		node = treap_insert(&root, node_pointer(item));
+		if (node_offset(node) != item)
+			die("inserted %"PRIu32" in place of %"PRIu32"",
+				node_offset(node), item);
+	}
+
+	item = node_offset(treap_first(&root));
+	while (~item) {
+		uint32_t next;
+		struct int_node *tmp = node_pointer(node_alloc(1));
+
+		tmp->n = node_pointer(item)->n;
+		next = node_offset(treap_next(&root, node_pointer(item)));
+
+		treap_remove(&root, node_pointer(item));
+		item = node_offset(treap_nsearch(&root, tmp));
+
+		if (item != next && (!~item || node_pointer(item)->n != tmp->n))
+			die("found %"PRIuMAX" in place of %"PRIuMAX"",
+				~item ? node_pointer(item)->n : ~(uintmax_t) 0,
+				~next ? node_pointer(next)->n : ~(uintmax_t) 0);
+		printf("%"PRIuMAX"\n", tmp->n);
+	}
+	node_reset();
+	return 0;
+}