From 398c7299d50aa64f5043c2f946779c985ba01897 Mon Sep 17 00:00:00 2001 From: "Richard W.M. Jones" Date: Wed, 3 Nov 2010 20:34:42 +0000 Subject: [PATCH] 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. (cherry picked from commit 58915725b1e464f7d447c0051ad916fbc1a82210) --- .gitignore | 2 + configure.ac | 5 ++ fish/Makefile.am | 19 ++++- fish/cmds_gperf.h | 46 +++++++++++ generator/generator_fish.ml | 192 ++++++++++++++++++++++++++++---------------- generator/generator_main.ml | 1 + po/POTFILES.in | 1 + 7 files changed, 196 insertions(+), 70 deletions(-) create mode 100644 fish/cmds_gperf.h diff --git a/.gitignore b/.gitignore index 7228828..0cd08f9 100644 --- a/.gitignore +++ b/.gitignore @@ -62,6 +62,8 @@ emptydisk examples/hello examples/to-xml fish/cmds.c +fish/cmds_gperf.c +fish/cmds_gperf.gperf fish/completion.c fish/guestfish fish/guestfish.static diff --git a/configure.ac b/configure.ac index 6c2e137..254d3dd 100644 --- a/configure.ac +++ b/configure.ac @@ -209,6 +209,11 @@ AC_CHECK_PROG([CPIO],[cpio],[cpio],[no]) test "x$CPIO" = "xno" && AC_MSG_ERROR([cpio must be installed]) +dnl Check for gperf. +AC_CHECK_PROG([GPERF],[gperf],[gperf],[no]) +test "x$GPERF" = "xno" && + AC_MSG_ERROR([gperf must be installed]) + dnl Check for pod2man and pod2text. AC_CHECK_PROG([POD2MAN],[pod2man],[pod2man],[no]) test "x$POD2MAN" = "xno" && diff --git a/fish/Makefile.am b/fish/Makefile.am index e3221ca..89cc4ec 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 0000000..92bd607 --- /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 */ diff --git a/generator/generator_fish.ml b/generator/generator_fish.ml index b0772fc..1341fa2 100644 --- a/generator/generator_fish.ml +++ b/generator/generator_fish.ml @@ -58,34 +58,28 @@ let generate_fish_cmds () = pr "#include \"full-write.h\"\n"; pr "#include \"xstrtol.h\"\n"; pr "#include \"fish.h\"\n"; + pr "#include \"cmds_gperf.h\"\n"; pr "\n"; pr "/* Valid suffixes allowed for numbers. See Gnulib xstrtol function. */\n"; pr "static const char *xstrtol_suffixes = \"0kKMGTPEZY\";\n"; pr "\n"; - (* list_commands function, which implements guestfish -h *) - pr "void list_commands (void)\n"; - pr "{\n"; - pr " printf (\" %%-16s %%s\\n\", _(\"Command\"), _(\"Description\"));\n"; - pr " list_builtin_commands ();\n"; List.iter ( - fun (name, _, _, flags, _, shortdesc, _) -> - let name = replace_char name '_' '-' in - pr " printf (\"%%-20s %%s\\n\", \"%s\", _(\"%s\"));\n" - name shortdesc - ) all_functions_and_fish_commands_sorted; - pr " printf (\" %%s\\n\","; - pr " _(\"Use -h / help to show detailed help for a command.\"));\n"; - pr "}\n"; - pr "\n"; + fun (name, _, _, _, _, _, _) -> + pr "static int run_%s (const char *cmd, size_t argc, char *argv[]);\n" + name + ) all_functions; - (* display_command function, which implements guestfish -h cmd *) - pr "int display_command (const char *cmd)\n"; - pr "{\n"; + pr "\n"; + (* List of command_entry structs. *) List.iter ( fun (name, _, _, flags, _, shortdesc, longdesc) -> + pr "struct command_entry %s_cmd_entry = {\n" name; + let name2 = replace_char name '_' '-' in + pr " .name = \"%s\",\n" name2; + let aliases = filter_map (function FishAlias n -> Some n | _ -> None) flags in let describe_alias = @@ -94,29 +88,25 @@ let generate_fish_cmds () = (String.concat " or " (List.map (fun s -> "'" ^ s ^ "'") aliases)) else "" in - pr " if ("; - pr "STRCASEEQ (cmd, \"%s\")" name; - if name <> name2 then - pr " || STRCASEEQ (cmd, \"%s\")" name2; - List.iter ( - fun alias -> - pr " || STRCASEEQ (cmd, \"%s\")" alias - ) aliases; - pr ") {\n"; - pr " pod2text (\"%s\", _(\"%s\"), %S);\n" - name2 shortdesc - ("=head1 DESCRIPTION\n\n" ^ - longdesc ^ describe_alias); - pr " return 0;\n"; - pr " }\n"; - pr " else\n" + pr " .shortdesc = \"%s\",\n" shortdesc; + pr " .podbody = %S,\n" + ("=head1 DESCRIPTION\n\n" ^ longdesc ^ describe_alias); + + pr " .run = run_%s\n" name; + pr "};\n"; + pr "\n"; ) fish_commands; List.iter ( fun (name, (_, args, optargs), _, flags, _, shortdesc, longdesc) -> + pr "struct command_entry %s_cmd_entry = {\n" name; + let name2 = replace_char name '_' '-' in + pr " .name = \"%s\",\n" name2; + let aliases = filter_map (function FishAlias n -> Some n | _ -> None) flags in + let longdesc = replace_str longdesc "C "'" ^ s ^ "'") aliases)) else "" in - pr " if ("; - pr "STRCASEEQ (cmd, \"%s\")" name; - if name <> name2 then - pr " || STRCASEEQ (cmd, \"%s\")" name2; - List.iter ( - fun alias -> - pr " || STRCASEEQ (cmd, \"%s\")" alias - ) aliases; - pr ") {\n"; - pr " pod2text (\"%s\", _(\"%s\"), %S);\n" - name2 shortdesc + pr " .shortdesc = \"%s\",\n" shortdesc; + pr " .podbody = %S,\n" ("=head1 SYNOPSIS\n\n " ^ synopsis ^ "\n\n" ^ "=head1 DESCRIPTION\n\n" ^ longdesc ^ warnings ^ describe_alias); - pr " return 0;\n"; - pr " }\n"; - pr " else\n" + + pr " .run = run_%s\n" name; + pr "};\n"; + pr "\n"; ) all_functions; + (* list_commands function, which implements guestfish -h *) + pr "void list_commands (void)\n"; + pr "{\n"; + pr " printf (\" %%-16s %%s\\n\", _(\"Command\"), _(\"Description\"));\n"; + pr " list_builtin_commands ();\n"; + List.iter ( + fun (name, _, _, flags, _, shortdesc, _) -> + let name = replace_char name '_' '-' in + pr " printf (\"%%-20s %%s\\n\", \"%s\", _(\"%s\"));\n" + name shortdesc + ) all_functions_and_fish_commands_sorted; + pr " printf (\" %%s\\n\","; + pr " _(\"Use -h / help to show detailed help for a command.\"));\n"; + pr "}\n"; + pr "\n"; + + (* display_command function, which implements guestfish -h cmd *) + pr "int display_command (const char *cmd)\n"; + pr "{\n"; + pr " const struct command_table *ct;\n"; + pr "\n"; + pr " ct = lookup_fish_command (cmd, strlen (cmd));\n"; + pr " if (ct) {\n"; + pr " pod2text (ct->entry->name, ct->entry->shortdesc, ct->entry->podbody);\n"; + pr " return 0;\n"; + pr " }\n"; + pr " else\n"; pr " return display_builtin_command (cmd);\n"; pr "}\n"; pr "\n"; @@ -279,7 +288,8 @@ Guestfish will prompt for these separately." (* run_ actions *) List.iter ( fun (name, (ret, args, optargs as style), _, flags, _, _, _) -> - pr "static int run_%s (const char *cmd, size_t argc, char *argv[])\n" name; + pr "static int\n"; + pr "run_%s (const char *cmd, size_t argc, char *argv[])\n" name; pr "{\n"; (match ret with | RErr @@ -582,36 +592,84 @@ Guestfish will prompt for these separately." ) all_functions; (* run_action function *) - pr "int run_action (const char *cmd, size_t argc, char *argv[])\n"; + pr "int\n"; + pr "run_action (const char *cmd, size_t argc, char *argv[])\n"; pr "{\n"; + pr " const struct command_table *ct;\n"; + pr "\n"; + pr " ct = lookup_fish_command (cmd, strlen (cmd));\n"; + pr " if (ct)\n"; + pr " return ct->entry->run (cmd, argc, argv);\n"; + pr " else {\n"; + pr " fprintf (stderr, _(\"%%s: unknown command\\n\"), cmd);\n"; + pr " if (command_num == 1)\n"; + pr " extended_help_message ();\n"; + pr " return -1;\n"; + pr " }\n"; + pr "}\n" + +(* gperf code to do fast lookups of commands. *) +and generate_fish_cmds_gperf () = + generate_header CStyle GPLv2plus; + + let all_functions_sorted = + List.filter ( + fun (_, _, _, flags, _, _, _) -> not (List.mem NotInFish flags) + ) all_functions_sorted in + + let all_functions_and_fish_commands_sorted = + List.sort action_compare (all_functions_sorted @ fish_commands) in + + pr "\ +%%language=ANSI-C +%%define lookup-function-name lookup_fish_command +%%ignore-case +%%readonly-tables +%%null-strings + +%%{ + +#include + +#include +#include + +#include \"cmds_gperf.h\" + +"; + + List.iter ( + fun (name, _, _, _, _, _, _) -> + pr "extern struct command_entry %s_cmd_entry;\n" name + ) all_functions_and_fish_commands_sorted; + + pr "\ +%%} + +struct command_table; + +%%%% +"; List.iter ( fun (name, _, _, flags, _, _, _) -> let name2 = replace_char name '_' '-' in let aliases = filter_map (function FishAlias n -> Some n | _ -> None) flags in - pr " if ("; - pr "STRCASEEQ (cmd, \"%s\")" name; + + (* The basic command. *) + pr "%s, &%s_cmd_entry\n" name name; + + (* Command with dashes instead of underscores. *) if name <> name2 then - pr " || STRCASEEQ (cmd, \"%s\")" name2; + pr "%s, &%s_cmd_entry\n" name2 name; + + (* Aliases for the command. *) List.iter ( fun alias -> - pr " || STRCASEEQ (cmd, \"%s\")" alias; + pr "%s, &%s_cmd_entry\n" alias name; ) aliases; - pr ")\n"; - pr " return run_%s (cmd, argc, argv);\n" name; - pr " else\n"; - ) all_functions_and_fish_commands_sorted; - - pr " {\n"; - pr " fprintf (stderr, _(\"%%s: unknown command\\n\"), cmd);\n"; - pr " if (command_num == 1)\n"; - pr " extended_help_message ();\n"; - pr " return -1;\n"; - pr " }\n"; - pr " return 0;\n"; - pr "}\n"; - pr "\n" + ) all_functions_and_fish_commands_sorted (* Readline completion for guestfish. *) and generate_fish_completion () = diff --git a/generator/generator_main.ml b/generator/generator_main.ml index 401ae60..6cc5f00 100644 --- a/generator/generator_main.ml +++ b/generator/generator_main.ml @@ -88,6 +88,7 @@ Run it from the top source directory using the command output_to "daemon/optgroups.c" generate_daemon_optgroups_c; output_to "daemon/optgroups.h" generate_daemon_optgroups_h; output_to "capitests/tests.c" generate_tests; + output_to "fish/cmds_gperf.gperf" generate_fish_cmds_gperf; output_to "fish/cmds.c" generate_fish_cmds; output_to "fish/completion.c" generate_fish_completion; output_to "fish/guestfish-commands.pod" generate_fish_commands_pod; diff --git a/po/POTFILES.in b/po/POTFILES.in index 699e90b..35643a2 100644 --- a/po/POTFILES.in +++ b/po/POTFILES.in @@ -71,6 +71,7 @@ daemon/zero.c daemon/zerofree.c fish/alloc.c fish/cmds.c +fish/cmds_gperf.c fish/completion.c fish/copy.c fish/destpaths.c -- 1.8.3.1