Merge branch 'ew/many-alternate-optim'

Optimization for repositories with many alternate object store.

* ew/many-alternate-optim:
  oidtree: a crit-bit tree for odb_loose_cache
  oidcpy_with_padding: constify `src' arg
  make object_directory.loose_objects_subdir_seen a bitmap
  avoid strlen via strbuf_addstr in link_alt_odb_entry
  speed up alt_odb_usable() with many alternates

4 files changed, 100 insertions, 0 deletions

diff --git a/t/helper/test-oidtree.c b/t/helper/test-oidtree.c
new file mode 100644
index 0000000000..180ee28dd9
--- /dev/null
+++ b/t/helper/test-oidtree.c
@@ -0,0 +1,49 @@
+#include "test-tool.h"
+#include "cache.h"
+#include "oidtree.h"
+
+static enum cb_next print_oid(const struct object_id *oid, void *data)
+{
+	puts(oid_to_hex(oid));
+	return CB_CONTINUE;
+}
+
+int cmd__oidtree(int argc, const char **argv)
+{
+	struct oidtree ot;
+	struct strbuf line = STRBUF_INIT;
+	int nongit_ok;
+	int algo = GIT_HASH_UNKNOWN;
+
+	oidtree_init(&ot);
+	setup_git_directory_gently(&nongit_ok);
+
+	while (strbuf_getline(&line, stdin) != EOF) {
+		const char *arg;
+		struct object_id oid;
+
+		if (skip_prefix(line.buf, "insert ", &arg)) {
+			if (get_oid_hex_any(arg, &oid) == GIT_HASH_UNKNOWN)
+				die("insert not a hexadecimal oid: %s", arg);
+			algo = oid.algo;
+			oidtree_insert(&ot, &oid);
+		} else if (skip_prefix(line.buf, "contains ", &arg)) {
+			if (get_oid_hex(arg, &oid))
+				die("contains not a hexadecimal oid: %s", arg);
+			printf("%d\n", oidtree_contains(&ot, &oid));
+		} else if (skip_prefix(line.buf, "each ", &arg)) {
+			char buf[GIT_MAX_HEXSZ + 1] = { '0' };
+			memset(&oid, 0, sizeof(oid));
+			memcpy(buf, arg, strlen(arg));
+			buf[hash_algos[algo].hexsz] = '\0';
+			get_oid_hex_any(buf, &oid);
+			oid.algo = algo;
+			oidtree_each(&ot, &oid, strlen(arg), print_oid, NULL);
+		} else if (!strcmp(line.buf, "clear")) {
+			oidtree_clear(&ot);
+		} else {
+			die("unknown command: %s", line.buf);
+		}
+	}
+	return 0;
+}
diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c
index b21e8f1519..490ac026c5 100644
--- a/t/helper/test-tool.c
+++ b/t/helper/test-tool.c
@@ -43,6 +43,7 @@ static struct test_cmd cmds[] = {
 	{ "mktemp", cmd__mktemp },
 	{ "oid-array", cmd__oid_array },
 	{ "oidmap", cmd__oidmap },
+	{ "oidtree", cmd__oidtree },
 	{ "online-cpus", cmd__online_cpus },
 	{ "parse-options", cmd__parse_options },
 	{ "parse-pathspec-file", cmd__parse_pathspec_file },
diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h
index f845ced4b3..f8dc266721 100644
--- a/t/helper/test-tool.h
+++ b/t/helper/test-tool.h
@@ -32,6 +32,7 @@ int cmd__match_trees(int argc, const char **argv);
 int cmd__mergesort(int argc, const char **argv);
 int cmd__mktemp(int argc, const char **argv);
 int cmd__oidmap(int argc, const char **argv);
+int cmd__oidtree(int argc, const char **argv);
 int cmd__online_cpus(int argc, const char **argv);
 int cmd__parse_options(int argc, const char **argv);
 int cmd__parse_pathspec_file(int argc, const char** argv);
diff --git a/t/t0069-oidtree.sh b/t/t0069-oidtree.sh
new file mode 100755
index 0000000000..bfb1397d7b
--- /dev/null
+++ b/t/t0069-oidtree.sh
@@ -0,0 +1,49 @@
+#!/bin/sh
+
+test_description='basic tests for the oidtree implementation'
+. ./test-lib.sh
+
+maxhexsz=$(test_oid hexsz)
+echoid () {
+	prefix="${1:+$1 }"
+	shift
+	while test $# -gt 0
+	do
+		shortoid="$1"
+		shift
+		difference=$(($maxhexsz - ${#shortoid}))
+		printf "%s%s%0${difference}d\\n" "$prefix" "$shortoid" "0"
+	done
+}
+
+test_expect_success 'oidtree insert and contains' '
+	cat >expect <<-\EOF &&
+		0
+		0
+		0
+		1
+		1
+		0
+	EOF
+	{
+		echoid insert 444 1 2 3 4 5 a b c d e &&
+		echoid contains 44 441 440 444 4440 4444
+		echo clear
+	} | test-tool oidtree >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'oidtree each' '
+	echoid "" 123 321 321 >expect &&
+	{
+		echoid insert f 9 8 123 321 a b c d e
+		echo each 12300
+		echo each 3211
+		echo each 3210
+		echo each 32100
+		echo clear
+	} | test-tool oidtree >actual &&
+	test_cmp expect actual
+'
+
+test_done