home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / id-utils-3.2-src.tgz / tar.out / fsf / id-utils / src / mkid.c < prev    next >
C/C++ Source or Header  |  1996-09-28  |  22KB  |  840 lines
  1. /* mkid.c -- build an identifer database
  2.    Copyright (C) 1986, 1995, 1996 Free Software Foundation, Inc.
  3.    Written by Greg McGary <gkm@gnu.ai.mit.edu>
  4.  
  5.    This program is free software; you can redistribute it and/or modify
  6.    it under the terms of the GNU General Public License as published by
  7.    the Free Software Foundation; either version 2, or (at your option)
  8.    any later version.
  9.  
  10.    This program is distributed in the hope that it will be useful,
  11.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.    GNU General Public License for more details.
  14.  
  15.    You should have received a copy of the GNU General Public License
  16.    along with this program; if not, write to the Free Software
  17.    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
  18.  
  19. #include <config.h>
  20. #include "xstdlib.h"
  21. #include <assert.h>
  22. #include <stdio.h>
  23. #include <errno.h>
  24. #include <getopt.h>
  25. #include "xsysstat.h"
  26. #include "xstddef.h"
  27. #include "xunistd.h"
  28. #include "xnls.h"
  29. #include "pathmax.h"
  30. #include "xstring.h"
  31. #include "idfile.h"
  32. #include "xmalloc.h"
  33. #include "hash.h"
  34. #include "scanners.h"
  35. #include "error.h"
  36. #include "xalloca.h"
  37. #if HAVE_LIMITS_H
  38. # include <limits.h>
  39. #endif
  40.  
  41. struct summary
  42. {
  43.   struct token **sum_tokens;
  44.   unsigned char const *sum_hits;
  45.   struct summary *sum_parent;
  46.   union {
  47.     struct summary *u_kids[8];    /* when sum_level > 0 */
  48. #define sum_kids sum_u.u_kids
  49.     struct member_file *u_files[8];    /* when sum_level == 0 */
  50. #define sum_files sum_u.u_files
  51.   } sum_u;
  52.   unsigned long sum_tokens_size;
  53.   unsigned long sum_hits_count;
  54.   int sum_free_index;
  55.   int sum_level;
  56. };
  57.  
  58. void usage __P((void));
  59. static void help_me __P((void));
  60. int main __P((int argc, char **argv));
  61. void assert_writeable __P((char const *file_name));
  62. void scan_files __P((struct idhead *idhp));
  63. void scan_member_file __P((struct member_file const *member));
  64. void scan_member_file_1 __P((get_token_func_t get_token, void const *args, FILE *source_FILE));
  65. void report_statistics __P((void));
  66. void write_id_file __P((struct idhead *idhp));
  67. unsigned long token_hash_1 __P((void const *key));
  68. unsigned long token_hash_2 __P((void const *key));
  69. int token_hash_cmp __P((void const *x, void const *y));
  70. int token_qsort_cmp __P((void const *x, void const *y));
  71. void bump_current_hits_signature __P((void));
  72. void init_hits_signature __P((int i));
  73. void free_summary_tokens __P((void));
  74. void summarize __P((void));
  75. void init_summary __P((void));
  76. struct summary *make_sibling_summary __P((struct summary *summary));
  77. int count_vec_size __P((struct summary *summary, unsigned char const *tail_hits));
  78. int count_buf_size __P((struct summary *summary, unsigned char const *tail_hits));
  79. void assert_hits __P((struct summary* summary));
  80. void write_hits __P((FILE *fp, struct summary *summary, unsigned char const *tail_hits));
  81. void sign_token __P((struct token *token));
  82. void add_token_to_summary __P((struct summary *summary, struct token *token));
  83.  
  84. struct hash_table token_table;
  85.  
  86. /* Miscellaneous statistics */
  87. size_t input_chars;
  88. size_t name_tokens;
  89. size_t number_tokens;
  90. size_t string_tokens;
  91. size_t literal_tokens;
  92. size_t comment_tokens;
  93. size_t occurrences;
  94. size_t hits_length = 0;
  95. size_t tokens_length = 0;
  96. size_t output_length = 0;
  97.  
  98. int verbose_flag = 0;
  99. int statistics_flag = 0;
  100.  
  101. int file_name_count = 0;    /* # of files in database */
  102. int levels = 0;            /* ceil(log(8)) of file_name_count */
  103.  
  104. unsigned char current_hits_signature[MAX_LEVELS];
  105. #define INIT_TOKENS_SIZE(level) (1 << ((level) + 13))
  106. struct summary *summary_root;
  107. struct summary *summary_leaf;
  108.  
  109. char const *program_name;
  110.  
  111. char *lang_map_file_name = 0;
  112. int show_version = 0;
  113. int show_help = 0;
  114. struct idhead idh;
  115. struct file_link *cw_dlink;
  116.  
  117. void
  118. usage (void)
  119. {
  120.   fprintf (stderr, _("Try `%s --help' for more information.\n"),
  121.        program_name);
  122.   exit (1);
  123. }
  124.  
  125. static struct option const long_options[] =
  126. {
  127.   { "file", required_argument, 0, 'f' },
  128.   { "output", required_argument, 0, 'o' },
  129.   { "include", required_argument, 0, 'i' },
  130.   { "exclude", required_argument, 0, 'x' },
  131.   { "lang-option", required_argument, 0, 'l' },
  132.   { "lang-map", required_argument, 0, 'm' },
  133.   { "default-lang", required_argument, 0, 'd' },
  134.   { "prune", required_argument, 0, 'p' },
  135.   { "verbose", no_argument, 0, 'v' },
  136.   { "statistics", no_argument, 0, 's' },
  137.   { "help", no_argument, &show_help, 1 },
  138.   { "version", no_argument, &show_version, 1 },
  139.   { 0 }
  140. };
  141.  
  142. static void
  143. help_me (void)
  144. {
  145.   printf (_("\
  146. Usage: %s [OPTION]... [FILE]...\n\
  147. "), program_name);
  148.  
  149.   printf (_("\
  150. Build an identifier database.\n\
  151.   -o, --output=OUTFILE    file name of ID database output\n\
  152.   -f, --file=OUTFILE      synonym for --output\n\
  153.   -i, --include=LANGS     include languages in LANGS (default: \"C C++ asm\")\n\
  154.   -x, --exclude=LANGS     exclude languages in LANGS\n\
  155.   -l, --lang-option=L:OPT pass OPT as a default for language L (see below)\n\
  156.   -m, --lang-map=MAPFILE  use MAPFILE to map file names onto source language\n\
  157.   -d, --default-lang=LANG make LANG the default source language\n\
  158.   -p, --prune=NAMES       exclude the named files and/or directories\n\
  159.   -v, --verbose           report per file statistics\n\
  160.   -s, --statistics        report statistics at end of run\n\
  161. \n\
  162.       --help              display this help and exit\n\
  163.       --version           output version information and exit\n\
  164. \n\
  165. FILE may be a file name, or a directory name to recursively search.\n\
  166. If no FILE is given, the current directory is searched by default.\n\
  167. Note that the `--include' and `--exclude' options are mutually-exclusive.\n\
  168. \n\
  169. The following arguments apply to the language-specific scanners:\n\
  170. "));
  171.   language_help_me ();
  172.   exit (0);
  173. }
  174.  
  175. #ifdef HAVE_SBRK
  176. char const *heap_initial;
  177. char const *heap_after_walk;
  178. char const *heap_after_scan;
  179. #endif
  180.  
  181. int
  182. main (int argc, char **argv)
  183. {
  184.   program_name = argv[0];
  185. #ifdef HAVE_SBRK
  186.   heap_initial = (char const *) sbrk (0);
  187. #endif
  188.   idh.idh_file_name = DEFAULT_ID_FILE_NAME;
  189.  
  190.   /* Set locale according to user's wishes.  */
  191.   setlocale (LC_ALL, "");
  192.  
  193.   /* Tell program which translations to use and where to find.  */
  194.   bindtextdomain (PACKAGE, LOCALEDIR);
  195.   textdomain (PACKAGE);
  196.  
  197.   for (;;)
  198.     {
  199.       int optc = getopt_long (argc, argv, "o:f:i:x:l:m:d:p:vs",
  200.                   long_options, (int *) 0);
  201.       if (optc < 0)
  202.     break;
  203.       switch (optc)
  204.     {
  205.     case 0:
  206.       break;
  207.  
  208.     case 'o':
  209.     case 'f':
  210.       idh.idh_file_name = optarg;
  211.       break;
  212.  
  213.     case 'i':
  214.       include_languages (optarg);
  215.       break;
  216.  
  217.     case 'x':
  218.       exclude_languages (optarg);
  219.       break;
  220.  
  221.     case 'l':
  222.       language_save_arg (optarg);
  223.       break;
  224.  
  225.     case 'm':
  226.       lang_map_file_name = optarg;
  227.       break;
  228.  
  229.     case 'd':
  230.       set_default_language (optarg);
  231.       break;
  232.  
  233.     case 'p':
  234.       if (cw_dlink == 0)
  235.         cw_dlink = init_walker (&idh);
  236.       prune_file_names (optarg, cw_dlink);
  237.       break;
  238.  
  239.     case 'v':
  240.       verbose_flag = 1;
  241.       statistics_flag = 1;
  242.       break;
  243.  
  244.     case 's':
  245.       statistics_flag = 1;
  246.       break;
  247.  
  248.     default:
  249.       usage ();
  250.     }
  251.     }
  252.  
  253.   if (show_version)
  254.     {
  255.       printf ("%s - %s\n", program_name, PACKAGE_VERSION);
  256.       exit (0);
  257.     }
  258.  
  259.   if (show_help)
  260.     help_me ();
  261.  
  262.   argc -= optind;
  263.   argv += optind;
  264.   if (argc == 0)
  265.     {
  266.       static char *dot = (char *) ".";
  267.       argc = 1;
  268.       argv = ˙
  269.     }
  270.  
  271.   language_getopt ();
  272.   assert_writeable (idh.idh_file_name);
  273.   if (cw_dlink == 0)
  274.     cw_dlink = init_walker (&idh);
  275.   parse_language_map (lang_map_file_name);
  276.  
  277.   while (argc--)
  278.     {
  279.       struct file_link *flink = parse_file_name (*argv++, cw_dlink);
  280.       if (flink)
  281.     walk_flink (flink, 0);
  282.     }
  283. #ifdef HAVE_SBRK
  284.   heap_after_walk = (char const *) sbrk (0);
  285. #endif
  286.  
  287.   mark_member_file_links (&idh);
  288.   if (idh.idh_member_file_table.ht_fill)
  289.     {
  290.       scan_files (&idh);
  291. #ifdef HAVE_SBRK
  292.       heap_after_scan = sbrk (0);
  293. #endif
  294.  
  295.       free_summary_tokens ();
  296.       free (token_table.ht_vec);
  297.       chdir_to_link (cw_dlink);
  298.       write_id_file (&idh);
  299.  
  300.       if (statistics_flag)
  301.     report_statistics ();
  302.     }
  303.   else
  304.     error (0, 0, "nothing to do");
  305.   exit (0);
  306. }
  307.  
  308. void
  309. assert_writeable (char const *file_name)
  310. {
  311.   if (access (file_name, 06) < 0)
  312.     {
  313.       if (errno == ENOENT)
  314.     {
  315.       char const *dir_name = dirname (file_name);
  316.       if (!dir_name || !*dir_name)
  317.         dir_name = ".";
  318.       if (access (dir_name, 06) < 0)
  319.         error (1, errno, _("can't create `%s' in `%s'"),
  320.            basename (file_name), dir_name);
  321.     }
  322.       else
  323.     error (1, errno, _("can't modify `%s'"), file_name);
  324.     }
  325. }
  326.  
  327. void
  328. scan_files (struct idhead *idhp)
  329. {
  330.   struct member_file **members_0
  331.     = (struct member_file **) hash_dump (&idhp->idh_member_file_table,
  332.                      0, member_file_qsort_compare);
  333.   struct member_file **end = &members_0[idhp->idh_member_file_table.ht_fill];
  334.   struct member_file **members = members_0;
  335.  
  336.   hash_init (&token_table, idhp->idh_member_file_table.ht_fill * 64,
  337.          token_hash_1, token_hash_2, token_hash_cmp);
  338.   init_hits_signature (0);
  339.   init_summary ();
  340.   obstack_init (&tokens_obstack);
  341.  
  342.   for (;;)
  343.     {
  344.       struct member_file *member = *members++;
  345.       scan_member_file (member);
  346.       if (members == end)
  347.     break;
  348.       if (current_hits_signature[0] & 0x80)
  349.     summarize ();
  350.       bump_current_hits_signature ();
  351.     }
  352.  
  353.   free (members_0);
  354. }
  355.  
  356. void
  357. scan_member_file (struct member_file const *member)
  358. {
  359.   struct lang_args const *lang_args = member->mf_lang_args;
  360.   struct language const *lang = lang_args->la_language;
  361.   get_token_func_t get_token = lang->lg_get_token;
  362.   struct file_link *flink = member->mf_link;
  363.   struct stat st;
  364.   FILE *source_FILE;
  365.  
  366.   chdir_to_link (flink->fl_parent);
  367.   source_FILE = fopen (flink->fl_name, "r");
  368.   if (source_FILE)
  369.     {
  370.       if (statistics_flag)
  371.     {
  372.       if (fstat (fileno (source_FILE), &st) < 0)
  373.         {
  374.           char *file_name = ALLOCA (char, PATH_MAX);
  375.           maybe_relative_file_name (file_name, flink, cw_dlink);
  376.           error (0, errno, _("can't stat `%s'"), file_name);
  377.         }
  378.       else
  379.         input_chars += st.st_size;
  380.     }
  381.       if (verbose_flag)
  382.     {
  383.       char *file_name = ALLOCA (char, PATH_MAX);
  384.       maybe_relative_file_name (file_name, flink, cw_dlink);
  385.       printf ("%d: %s: %s", member->mf_index, lang->lg_name, file_name);
  386.       fflush (stdout);
  387.     }
  388.       scan_member_file_1 (get_token, lang_args->la_args_digested, source_FILE);
  389.       if (verbose_flag)
  390.     putchar ('\n');
  391.       fclose (source_FILE);
  392.     }
  393.   else
  394.     error (0, errno, _("can't open `%s'"), flink->fl_name);
  395. }
  396.  
  397. void
  398. scan_member_file_1 (get_token_func_t get_token, void const *args, FILE *source_FILE)
  399. {
  400.   struct token **slot;
  401.   struct token *token;
  402.   int flags;
  403.   int new_tokens = 0;
  404.   int distinct_tokens = 0;
  405.  
  406.   while ((token = (*get_token) (source_FILE, args, &flags)) != NULL)
  407.     {
  408.       if (*token->tok_name == '\0') {
  409.     obstack_free (&tokens_obstack, token);
  410.     continue;
  411.       }
  412.       slot = (struct token **) hash_find_slot (&token_table, token);
  413.       if (HASH_VACANT (*slot))
  414.     {
  415.       token->tok_flags = flags;
  416.       token->tok_count = 1;
  417.       memset (token->tok_hits, 0, sizeof (token->tok_hits));
  418.       sign_token (token);
  419.       if (verbose_flag)
  420.         {
  421.           distinct_tokens++;
  422.           new_tokens++;
  423.         }
  424.       hash_insert_at (&token_table, token, slot);
  425.     }
  426.       else
  427.     {
  428.       obstack_free (&tokens_obstack, token);
  429.       token = *slot;
  430.       token->tok_flags |= flags;
  431.       if (token->tok_count < USHRT_MAX)
  432.         token->tok_count++;
  433.       if (!(token->tok_hits[0] & current_hits_signature[0]))
  434.         {
  435.           sign_token (token);
  436.           if (verbose_flag)
  437.         distinct_tokens++;
  438.         }
  439.     }
  440.     }
  441.   if (verbose_flag)
  442.     {
  443.       printf (_("  new = %d/%d"), new_tokens, distinct_tokens);
  444.       if (distinct_tokens != 0)
  445.     printf (" = %.0f%%", 100.0 * (double) new_tokens / (double) distinct_tokens);
  446.     }
  447. }
  448.  
  449. void
  450. report_statistics (void)
  451. {
  452.   printf (_("Name=%ld, "), name_tokens);
  453.   printf (_("Number=%ld, "), number_tokens);
  454.   printf (_("String=%ld, "), string_tokens);
  455.   printf (_("Literal=%ld, "), literal_tokens);
  456.   printf (_("Comment=%ld\n"), comment_tokens);
  457.  
  458.   printf (_("Files=%d, "), idh.idh_files);
  459.   printf (_("Tokens=%ld, "), occurrences);
  460.   printf (_("Bytes=%ld Kb, "), input_chars / 1024);
  461. #ifdef HAVE_SBRK
  462.   printf (_("Heap=%ld+%ld Kb, "), (heap_after_scan - heap_after_walk) / 1024,
  463.       (heap_after_walk - heap_initial) / 1024);
  464. #endif
  465.   printf (_("Output=%ld (%ld tok, %ld hit)\n"), output_length, tokens_length, hits_length);
  466.  
  467.   hash_print_stats (&token_table, stdout);
  468.   printf (_(", Freq=%ld/%ld=%.2f\n"), occurrences, token_table.ht_fill,
  469.       (double) occurrences / (double) token_table.ht_fill);
  470. }
  471.  
  472. /* As the database is written, may need to adjust the file names.  If
  473.    we are generating the ID file in a remote directory, then adjust
  474.    the file names to be relative to the location of the ID database.
  475.  
  476.    (This would be a common useage if you want to make a database for a
  477.    directory which you have no write access to, so you cannot create
  478.    the ID file.)  */
  479. void
  480. write_id_file (struct idhead *idhp)
  481. {
  482.   struct token **tokens;
  483.   int i;
  484.   int buf_size;
  485.   int vec_size;
  486.   int tok_size;
  487.   int max_buf_size = 0;
  488.   int max_vec_size = 0;
  489.  
  490.   if (verbose_flag)
  491.     printf (_("Sorting tokens...\n"));
  492.   assert (summary_root->sum_hits_count == token_table.ht_fill);
  493.   tokens = REALLOC (summary_root->sum_tokens, struct token *, token_table.ht_fill);
  494.   qsort (tokens, token_table.ht_fill, sizeof (struct token *), token_qsort_cmp);
  495.  
  496.   if (verbose_flag)
  497.     printf (_("Writing `%s'...\n"), idhp->idh_file_name);
  498.   idhp->idh_FILE = fopen (idhp->idh_file_name, "w+b");
  499.   if (idhp->idh_FILE == NULL)
  500.     error (1, errno, _("can't create `%s'"), idhp->idh_file_name);
  501.  
  502.   idhp->idh_magic[0] = IDH_MAGIC_0;
  503.   idhp->idh_magic[1] = IDH_MAGIC_1;
  504.   idhp->idh_version = IDH_VERSION;
  505.   idhp->idh_flags = IDH_COUNTS;
  506.  
  507.   /* write out the list of pathnames */
  508.  
  509.   fseek (idhp->idh_FILE, sizeof_idhead (), 0);
  510.   idhp->idh_flinks_offset = ftell (idhp->idh_FILE);
  511.   serialize_file_links (idhp);
  512.  
  513.   /* write out the list of identifiers */
  514.  
  515.   putc ('\0', idhp->idh_FILE);
  516.   putc ('\0', idhp->idh_FILE);
  517.   idhp->idh_tokens_offset = ftell (idhp->idh_FILE);
  518.  
  519.   for (i = 0; i < token_table.ht_fill; i++, tokens++)
  520.     {
  521.       struct token *token = *tokens;
  522.       occurrences += token->tok_count;
  523.       if (token->tok_flags & TOK_NUMBER)
  524.     number_tokens++;
  525.       if (token->tok_flags & TOK_NAME)
  526.     name_tokens++;
  527.       if (token->tok_flags & TOK_STRING)
  528.     string_tokens++;
  529.       if (token->tok_flags & TOK_LITERAL)
  530.     literal_tokens++;
  531.       if (token->tok_flags & TOK_COMMENT)
  532.     comment_tokens++;
  533.  
  534.       fputs (token->tok_name, idhp->idh_FILE);
  535.       putc ('\0', idhp->idh_FILE);
  536.       if (token->tok_count > 0xff)
  537.     token->tok_flags |= TOK_SHORT_COUNT;
  538.       putc (token->tok_flags, idhp->idh_FILE);
  539.       putc (token->tok_count & 0xff, idhp->idh_FILE);
  540.       if (token->tok_flags & TOK_SHORT_COUNT)
  541.     putc (token->tok_count >> 8, idhp->idh_FILE);
  542.  
  543.       vec_size = count_vec_size (summary_root, token->tok_hits + levels);
  544.       buf_size = count_buf_size (summary_root, token->tok_hits + levels);
  545.       hits_length += buf_size;
  546.       tok_size = strlen (token->tok_name) + 1;
  547.       tokens_length += tok_size;
  548.       buf_size += tok_size + sizeof (token->tok_flags) + sizeof (token->tok_count) + 2;
  549.       if (buf_size > max_buf_size)
  550.     max_buf_size = buf_size;
  551.       if (vec_size > max_vec_size)
  552.     max_vec_size = vec_size;
  553.  
  554.       write_hits (idhp->idh_FILE, summary_root, token->tok_hits + levels);
  555.       putc ('\0', idhp->idh_FILE);
  556.       putc ('\0', idhp->idh_FILE);
  557.     }
  558.   assert_hits (summary_root);
  559.   idhp->idh_tokens = token_table.ht_fill;
  560.   output_length = ftell (idhp->idh_FILE);
  561.   idhp->idh_end_offset = output_length - 2;
  562.   idhp->idh_buf_size = max_buf_size;
  563.   idhp->idh_vec_size = max_vec_size;
  564.  
  565.   write_idhead (&idh);
  566.   fclose (idhp->idh_FILE);
  567. }
  568.  
  569. unsigned long
  570. token_hash_1 (void const *key)
  571. {
  572.   return_STRING_HASH_1 (((struct token const *) key)->tok_name);
  573. }
  574.  
  575. unsigned long
  576. token_hash_2 (void const *key)
  577. {
  578.   return_STRING_HASH_2 (((struct token const *) key)->tok_name);
  579. }
  580.  
  581. int
  582. token_hash_cmp (void const *x, void const *y)
  583. {
  584.   return_STRING_COMPARE (((struct token const *) x)->tok_name,
  585.              ((struct token const *) y)->tok_name);
  586. }
  587.  
  588. int
  589. token_qsort_cmp (void const *x, void const *y)
  590. {
  591.   return_STRING_COMPARE ((*(struct token const *const *) x)->tok_name,
  592.              (*(struct token const *const *) y)->tok_name);
  593. }
  594.  
  595.  
  596. /****************************************************************************/
  597.  
  598. void
  599. bump_current_hits_signature (void)
  600. {
  601.   unsigned char *hits = current_hits_signature;
  602.   while (*hits & 0x80)
  603.     *hits++ = 1;
  604.   *hits <<= 1;
  605. }
  606.  
  607. void
  608. init_hits_signature (int i)
  609. {
  610.   unsigned char *hits = current_hits_signature;
  611.   unsigned char const *end = ¤t_hits_signature[MAX_LEVELS];
  612.   while (hits < end)
  613.     {
  614.       *hits = 1 << (i & 7);
  615.       i >>= 3;
  616.       hits++;
  617.     }
  618. }
  619.  
  620. void
  621. free_summary_tokens (void)
  622. {
  623.   struct summary *summary = summary_leaf;
  624.   while (summary != summary_root)
  625.     {
  626.       free (summary->sum_tokens);
  627.       summary = summary->sum_parent;
  628.     }
  629. }
  630.  
  631. void
  632. summarize (void)
  633. {
  634.   unsigned char const *hits_sig = current_hits_signature;
  635.   struct summary *summary = summary_leaf;
  636.  
  637.   do
  638.     {
  639.       unsigned long count = summary->sum_hits_count;
  640.       unsigned char *hits = MALLOC (unsigned char, count + 1);
  641.       unsigned int level = summary->sum_level;
  642.       struct token **tokens = summary->sum_tokens;
  643.       unsigned long init_size = INIT_TOKENS_SIZE (summary->sum_level);
  644.  
  645.       if (verbose_flag)
  646.     printf (_("level %d: %ld/%ld = %.0f%%\n"),
  647.         summary->sum_level, count, init_size,
  648.         100.0 * (double) count / (double) init_size);
  649.  
  650.       qsort (tokens, count, sizeof (struct token *), token_qsort_cmp);
  651.       summary->sum_hits = hits;
  652.       while (count--)
  653.     {
  654.       unsigned char *hit = &(*tokens++)->tok_hits[level];
  655.       *hits++ = *hit;
  656.       *hit = 0;
  657.     }
  658.       *hits++ = 0;
  659.       if (summary->sum_parent)
  660.     {
  661.       free (summary->sum_tokens);
  662.       summary->sum_tokens = 0;
  663.     }
  664.       summary = summary->sum_parent;
  665.     }
  666.   while (*++hits_sig & 0x80);
  667.   summary_leaf = make_sibling_summary (summary_leaf);
  668. }
  669.  
  670. void
  671. init_summary (void)
  672. {
  673.   unsigned long size = INIT_TOKENS_SIZE (0);
  674.   summary_root = summary_leaf = CALLOC (struct summary, 1);
  675.   summary_root->sum_tokens_size = size;
  676.   summary_root->sum_tokens = MALLOC (struct token *, size);
  677. }
  678.  
  679. struct summary *
  680. make_sibling_summary (struct summary *summary)
  681. {
  682.   struct summary *parent = summary->sum_parent;
  683.   unsigned long size;
  684.  
  685.   if (parent == NULL)
  686.     {
  687.       levels++;
  688.       summary_root = summary->sum_parent = parent = CALLOC (struct summary, 1);
  689.       parent->sum_level = levels;
  690.       parent->sum_kids[0] = summary;
  691.       parent->sum_hits_count = summary->sum_hits_count;
  692.       parent->sum_free_index = 1;
  693.       size = INIT_TOKENS_SIZE (levels);
  694.       if (summary->sum_tokens_size >= size)
  695.     {
  696.       parent->sum_tokens_size = summary->sum_tokens_size;
  697.       parent->sum_tokens = summary->sum_tokens;
  698.     }
  699.       else
  700.     {
  701.       parent->sum_tokens_size = size;
  702.       parent->sum_tokens = REALLOC (summary->sum_tokens, struct token *, size);
  703.     }
  704.       summary->sum_tokens = 0;
  705.     }
  706.   if (parent->sum_free_index == 8)
  707.     parent = make_sibling_summary (parent);
  708.   summary = CALLOC (struct summary, 1);
  709.   summary->sum_level = parent->sum_level - 1;
  710.   parent->sum_kids[parent->sum_free_index++] = summary;
  711.   summary->sum_parent = parent;
  712.   size = INIT_TOKENS_SIZE (summary->sum_level);
  713.   summary->sum_tokens_size = size;
  714.   summary->sum_tokens = MALLOC (struct token *, size);
  715.   return summary;
  716. }
  717.  
  718. int
  719. count_vec_size (struct summary *summary, unsigned char const *tail_hits)
  720. {
  721.   struct summary **kids;
  722.   unsigned int hits = (summary->sum_hits ? *summary->sum_hits : *tail_hits);
  723.  
  724.   kids = summary->sum_kids;
  725.   if (*kids == NULL)
  726.     {
  727.       static char bits_per_nybble[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 };
  728.       return bits_per_nybble[hits & 0xf] + bits_per_nybble[hits >> 4];
  729.     }
  730.   else
  731.     {
  732.       int bit;
  733.       int count = 0;
  734.       --tail_hits;
  735.       for (bit = 1; bit & 0xff; bit <<= 1, ++kids)
  736.     if (bit & hits)
  737.       count += count_vec_size (*kids, tail_hits);
  738.       return count;
  739.     }
  740. }
  741.  
  742. int
  743. count_buf_size (struct summary *summary, unsigned char const *tail_hits)
  744. {
  745.   struct summary **kids;
  746.   unsigned int hits = (summary->sum_hits ? *summary->sum_hits : *tail_hits);
  747.  
  748.   kids = summary->sum_kids;
  749.   if (*kids == NULL)
  750.     return 1;
  751.   else
  752.     {
  753.       int bit;
  754.       int count = 1;
  755.       --tail_hits;
  756.       for (bit = 1; bit & 0xff; bit <<= 1, ++kids)
  757.     if (bit & hits)
  758.       count += count_buf_size (*kids, tail_hits);
  759.       return count;
  760.     }
  761. }
  762.  
  763. void
  764. assert_hits (struct summary* summary)
  765. {
  766.   struct summary **kids = summary->sum_kids;
  767.   struct summary **end = &kids[8];
  768.  
  769.   assert (summary->sum_hits == NULL || *summary->sum_hits == 0);
  770.  
  771.   if (end[-1] == 0)
  772.     while (*--end == 0)
  773.       ;
  774.   while (kids < end)
  775.     assert_hits (*kids++);
  776. }
  777.  
  778. void
  779. write_hits (FILE *fp, struct summary *summary, unsigned char const *tail_hits)
  780. {
  781.   struct summary **kids;
  782.   unsigned int hits = (summary->sum_hits ? *summary->sum_hits++ : *tail_hits);
  783.  
  784.   assert (hits);
  785.   putc (hits, fp);
  786.  
  787.   kids = summary->sum_kids;
  788.   if (*kids)
  789.     {
  790.       int bit;
  791.       --tail_hits;
  792.       for (bit = 1; (bit & 0xff) && *kids; bit <<= 1, ++kids)
  793.     if (bit & hits)
  794.       write_hits (fp, *kids, tail_hits);
  795.     }
  796. }
  797.  
  798. void
  799. sign_token (struct token *token)
  800. {
  801.   unsigned char *tok_hits = token->tok_hits;
  802.   unsigned char *hits_sig = current_hits_signature;
  803.   unsigned char *end = ¤t_hits_signature[MAX_LEVELS];
  804.   struct summary *summary = summary_leaf;
  805.  
  806.   while (summary)
  807.     {
  808.       if (*tok_hits == 0)
  809.     add_token_to_summary (summary, token);
  810.       if (*tok_hits & *hits_sig)
  811.     break;
  812.       *tok_hits |= *hits_sig;
  813.       summary = summary->sum_parent;
  814.       tok_hits++;
  815.       hits_sig++;
  816.     }
  817.   while (hits_sig < end)
  818.     {
  819.       if (*tok_hits & *hits_sig)
  820.     break;
  821.       *tok_hits |= *hits_sig;
  822.       tok_hits++;
  823.       hits_sig++;
  824.     }
  825. }
  826.  
  827. void
  828. add_token_to_summary (struct summary *summary, struct token *token)
  829. {
  830.   unsigned long size = summary->sum_tokens_size;
  831.  
  832.   if (summary->sum_hits_count >= size)
  833.     {
  834.       size *= 2;
  835.       summary->sum_tokens = REALLOC (summary->sum_tokens, struct token *, size);
  836.       summary->sum_tokens_size = size;
  837.     }
  838.   summary->sum_tokens[summary->sum_hits_count++] = token;
  839. }
  840.