diff options
| author | Richard W.M. Jones <rjones@redhat.com> | 2010-11-03 20:34:42 +0000 |
|---|---|---|
| committer | Richard W.M. Jones <rjones@redhat.com> | 2010-11-03 20:34:42 +0000 |
| commit | 58915725b1e464f7d447c0051ad916fbc1a82210 (patch) | |
| tree | 2300ce670996e97809518ba2fa14109c5dcc4b08 | |
| parent | f661db2c393d1b7e4211c55682b7fac82a70e36d (diff) | |
| download | libguestfs-58915725b1e464f7d447c0051ad916fbc1a82210.tar.gz libguestfs-58915725b1e464f7d447c0051ad916fbc1a82210.tar.xz libguestfs-58915725b1e464f7d447c0051ad916fbc1a82210.zip | |
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.
| -rw-r--r-- | .gitignore | 2 | ||||
| -rw-r--r-- | fish/Makefile.am | 19 | ||||
| -rw-r--r-- | fish/cmds_gperf.h | 46 | ||||
| -rw-r--r-- | generator/generator_fish.ml | 192 | ||||
| -rw-r--r-- | generator/generator_main.ml | 1 | ||||
| -rw-r--r-- | po/POTFILES.in | 1 |
6 files changed, 191 insertions, 70 deletions
@@ -67,6 +67,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/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 */ diff --git a/generator/generator_fish.ml b/generator/generator_fish.ml index b0772fc0..1341fa26 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 <cmd> / help <cmd> 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<guestfs_" "C<" in let synopsis = match args with @@ -164,25 +154,44 @@ Guestfish will prompt for these separately." (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 + 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 <cmd> / help <cmd> 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_<action> 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 <config.h> + +#include <stdlib.h> +#include <string.h> + +#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 2d4b2412..41214130 100644 --- a/generator/generator_main.ml +++ b/generator/generator_main.ml @@ -92,6 +92,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 5d4bdf76..877db697 100644 --- a/po/POTFILES.in +++ b/po/POTFILES.in @@ -73,6 +73,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 |