fish: Use a perfect hash for faster command lookups.

Existing command lookups are approx O(n^2).  Replace this
with a perfect hash implementation which should be a lot
faster.

2 files changed, 62 insertions, 3 deletions

diff --git a/fish/Makefile.am b/fish/Makefile.am
index e3221ca5..89cc4ecb 100644
--- a/fish/Makefile.am
+++ b/fish/Makefile.am
@@ -21,6 +21,7 @@ bin_PROGRAMS = guestfish
 
 generator_built = \
 	cmds.c \
+	cmds_gperf.gperf \
 	completion.c \
 	guestfish-actions.pod \
 	guestfish-commands.pod \
@@ -29,6 +30,7 @@ generator_built = \
 
 BUILT_SOURCES = \
 	$(generator_built) \
+	cmds_gperf.c \
 	rc_protocol.h \
 	rc_protocol.c
 
@@ -52,6 +54,7 @@ guestfish_SOURCES = \
 	$(generator_built) \
 	$(SHARED_SOURCE_FILES) \
 	alloc.c \
+	cmds_gperf.h \
 	copy.c \
 	destpaths.c \
 	echo.c \
@@ -82,6 +85,16 @@ guestfish_SOURCES = \
 librc_protocol_la_SOURCES = rc_protocol.c
 librc_protocol_la_CFLAGS = -Wall -Wno-unused
 
+# Build the command lookup perfect hash code.  The generated code has
+# lots of warnings so we must compile it in a separate mini-library.
+libcmds_la_SOURCES = cmds_gperf.c
+libcmds_la_CFLAGS =
+
+cmds_gperf.c: cmds_gperf.gperf
+	rm -f $@
+	$(GPERF) -t $< > $@-t
+	mv $@-t $@
+
 guestfish_CFLAGS = \
 	-I$(top_srcdir)/src -I$(top_builddir)/src \
 	-I$(top_srcdir)/fish -I$(top_builddir)/fish \
@@ -95,9 +108,9 @@ guestfish_LDADD = \
 	$(LIBVIRT_LIBS) $(LIBXML2_LIBS) \
 	$(top_builddir)/src/libguestfs.la $(LIBREADLINE) -lm
 
-# Make libguestfs use the convenience library.
-noinst_LTLIBRARIES = librc_protocol.la
-guestfish_LDADD += librc_protocol.la ../gnulib/lib/libgnu.la
+# Make guestfish use the convenience libraries.
+noinst_LTLIBRARIES = libcmds.la librc_protocol.la
+guestfish_LDADD += libcmds.la librc_protocol.la ../gnulib/lib/libgnu.la
 
 if HAVE_RPCGEN
 rc_protocol.c: rc_protocol.x
diff --git a/fish/cmds_gperf.h b/fish/cmds_gperf.h
new file mode 100644
index 00000000..92bd6070
--- /dev/null
+++ b/fish/cmds_gperf.h
@@ -0,0 +1,46 @@
+/* libguestfs - guestfish shell
+ * Copyright (C) 2010 Red Hat Inc.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+#ifndef FISH_CMDS_GPERF_H
+#define FISH_CMDS_GPERF_H
+
+/* There is one of these structures for each individual command that
+ * guestfish can execute.
+ */
+struct command_entry {
+  /* These fields are passed to pod2text to implement the online help. */
+  const char *name;
+  const char *shortdesc;
+  const char *podbody;
+
+  /* The run_* function. */
+  int (*run) (const char *cmd, size_t argc, char *argv[]);
+};
+
+/* Command table used by the gperf-generated lookup function.
+ * Multiple rows in this table can and do point to a single command
+ * entry.  This is used to implement aliases.
+ */
+struct command_table {
+  char *name;
+  struct command_entry *entry;
+};
+
+const struct command_table *lookup_fish_command (register const char *str, register unsigned int len);
+
+#endif /* FISH_CMDS_GPERF_H */