Re: [PATCH] builtins: search builtin commands via binary search.

From

Junio C Hamano <gitster@pobox.com>

Date

Jul 29, 2013, 16:18 UTC

Message-ID

<7v4nbd1grs.fsf@alter.siamese.dyndns.org>

In-Reply-To

<51F38997.9010507@googlemail.com>

Stefan Beller <stefanbeller@googlemail.com> writes:

> However I could not find a speedup.
> So if the patch is accepted, it would only be for readability.

--- a/git.c
+++ b/git.c
@@ -34,6 +34,150 @@ static void commit_pager_choice(void) {
 	}
 }
 
+struct cmd_struct {
+	const char *cmd;
+	int (*fn)(int, const char **, const char *);
+	int option;
+};
+
+#define RUN_SETUP		(1<<0)
+#define RUN_SETUP_GENTLY	(1<<1)
+#define USE_PAGER		(1<<2)
+/*
+ * require working tree to be present -- anything uses this needs
+ * RUN_SETUP for reading from the configuration file.
+ */
+#define NEED_WORK_TREE		(1<<3)
+
+static struct cmd_struct builtin_commands[] = {
+	{ "add", cmd_add, RUN_SETUP | NEED_WORK_TREE },
+	{ "annotate", cmd_annotate, RUN_SETUP },
+	...
+	{ "whatchanged", cmd_whatchanged, RUN_SETUP },
+	{ "write-tree", cmd_write_tree, RUN_SETUP },
+};
+
+static void make_sure_the_builtin_array_is_sorted(void)
+{
+	int i;
+	for (i = 0; i < ARRAY_SIZE(builtin_commands) - 1; i++) {
+		struct cmd_struct *it = &builtin_commands[i];
+		if (strcmp(it[0].cmd, it[1].cmd) >= 0)
+			die("BUG: builtin command list not sorted %s > %s",
+			    it[0].cmd, it[1].cmd);
+	}
+}
+
 static int handle_options(const char ***argv, int *argc, int *envchanged)
 {
 	const char **orig_argv = *argv;
@@ -62,6 +206,9 @@ static int handle_options(const char ***argv, int *argc, int *envchanged)
 				puts(git_exec_path());
 				exit(0);
 			}
+		} else if (!strcmp(cmd, "--check-builtins-sorted")) {
+			make_sure_the_builtin_array_is_sorted();
+			exit(0);
 		} else if (!strcmp(cmd, "--html-path")) {
 			puts(system_path(GIT_HTML_PATH));
 			exit(0);
@@ -241,21 +388,6 @@ static int handle_alias(int *argcp, const char ***argv)
 	return ret;
 }
 
-#define RUN_SETUP		(1<<0)
-#define RUN_SETUP_GENTLY	(1<<1)
-#define USE_PAGER		(1<<2)
-/*
- * require working tree to be present -- anything uses this needs
- * RUN_SETUP for reading from the configuration file.
- */
-#define NEED_WORK_TREE		(1<<3)
-
-struct cmd_struct {
-	const char *cmd;
-	int (*fn)(int, const char **, const char *);
-	int option;
-};
-
 static int run_builtin(struct cmd_struct *p, int argc, const char **argv)
 {
 	int status, help;
@@ -312,123 +444,6 @@ static int run_builtin(struct cmd_struct *p, int argc, const char **argv)
 static void handle_internal_command(int argc, const char **argv)
 {
 	const char *cmd = argv[0];
-	static struct cmd_struct commands[] = {
-		{ "add", cmd_add, RUN_SETUP | NEED_WORK_TREE },
-		{ "annotate", cmd_annotate, RUN_SETUP },
-		...
-		{ "whatchanged", cmd_whatchanged, RUN_SETUP },
-		{ "write-tree", cmd_write_tree, RUN_SETUP },
-	};
 	int i;
 	static const char ext[] = STRIP_EXTENSION;
 
@@ -447,8 +462,8 @@ static void handle_internal_command(int argc, const char **argv)
 		argv[0] = cmd = "help";
 	}
 
-	for (i = 0; i < ARRAY_SIZE(commands); i++) {
-		struct cmd_struct *p = commands+i;
+	for (i = 0; i < ARRAY_SIZE(builtin_commands); i++) {
+		struct cmd_struct *p = builtin_commands+i;
 		if (strcmp(p->cmd, cmd))
 			continue;
 		exit(run_builtin(p, argc, argv));