home *** CD-ROM | disk | FTP | other *** search
/ Amiga ISO Collection / AmigaUtilCD2.iso / Programming / GCC / GERLIB_DEV08B.LHA / gerlib / libg++ / etc / trie-gen / trie.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-12  |  6.4 KB  |  198 lines
  1. /* Generates a minimal-prefix trie for a user-specified set of keywords.
  2.  
  3.    Copyright (C) 1989, 1993 Free Software Foundation, Inc.
  4.    written by Douglas C. Schmidt (schmidt@ics.uci.edu)
  5.    
  6.    This file is part of GNU TRIE-GEN.
  7.    
  8.    GNU TRIE-GEN is free software; you can redistribute it and/or modify
  9.    it under the terms of the GNU General Public License as published by
  10.    the Free Software Foundation; either version 1, or (at your option)
  11.    any later version.
  12.    
  13.    GNU TRIE-GEN is distributed in the hope that it will be useful,
  14.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16.    GNU General Public License for more details.
  17.    
  18.    You should have received a copy of the GNU General Public License
  19.    along with GNU trie-gen; see the file COPYING.  If not, write to
  20.    the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
  21.  
  22. #include <stdio.h>
  23. #include <std.h>
  24. #include <limits.h>
  25. #include <new.h>
  26. #include "options.h"
  27. #include "trie.h"
  28.  
  29. const int      MAX_ASCII        = 128;
  30.  
  31. /* Insert a new keyword into the data structure, possibly growing the
  32.    keyword table to accomodate the new entry.  Space for STR has already
  33.    been allocated in the caller.  In addition, the MAX_KEY_LEN is updated
  34.    if the current LEN is larger than the previous max.  This information
  35.    is needed later on when dynamically allocating the TRIE table. */
  36.    
  37. void 
  38. Trie::insert (char *str, int len)
  39. {
  40.   if (current_size >= total_size)
  41.     resize (total_size * 2);
  42.   keys[current_size++] = str;
  43.   if (max_key_len < len)
  44.     max_key_len = len;
  45. }
  46.  
  47. /* Grow the KEYS table to allow a maximum of NEW_SIZE entries. 
  48.    Old keys are copied into the new buffer. */
  49.  
  50. void 
  51. Trie::resize (int new_size)
  52. {
  53.   keys = new (keys, total_size = new_size) char *;
  54. }
  55.  
  56. /* Write the generated TRIE out as a static table.  Compaction is
  57.    performed if the user requests it, otherwise the table is 
  58.    not compacted at all! (this leads to ridiculously large tables; perhaps
  59.    compaction should be the default?) */
  60.  
  61. void 
  62. Trie::output (void)
  63. {
  64.   if (current_size <= 0)
  65.     return;
  66.   else
  67.     {
  68.       sort ();
  69.  
  70.       fputs ("#include <string.h>\n#define MAX_ASCII 128\n\nstatic", stdout);
  71.       if (option[CONST])
  72.         fputs (" const", stdout);
  73.       fputs (" char *const word_list[] = \n{\n  \"\",\n", stdout);
  74.  
  75.       for (int i = 0; i < current_size; i++) 
  76.         printf ("  \"%s\",\n", keys[i]);
  77.  
  78.       fflush (stdout);
  79.       fputs ("};\n\n", stdout);
  80.       build (current_size);
  81.  
  82.       if (option[COMPACT])
  83.         matrix.output ();
  84.       else
  85.         {
  86.           const int MAX_NUMBER
  87.         = (current_size > max_row) ? current_size : max_row;
  88.           int   field_width;
  89.           int   count = MAX_NUMBER;
  90.  
  91.           for (field_width = 2; (count /= 10) > 0; field_width++)
  92.             ;
  93.  
  94.           printf ("static const %s trie_array[][MAX_ASCII] = \n{", 
  95.                   MAX_NUMBER < SCHAR_MAX ?
  96.             (CHAR_MIN == 0 ? "signed char" : "char") :
  97.                   MAX_NUMBER < SHRT_MAX ? "short" : "int");
  98.  
  99.           for (i = 0; i < max_row; i++)
  100.             {
  101.               fputs ("\n  ", stdout);
  102.  
  103.               for (int j = 0; j < MAX_ASCII; j++)
  104.                 printf ("%*d,", field_width, matrix (i, j));
  105.             }
  106.           fputs ("\n};\n", stdout);
  107.         }
  108.  
  109.       printf ("\n%schar *\nin_word_set (const char *str, int len)\n{\n"
  110.               "  %schar *s = %sstr;\n  int i = 0;\n\n"
  111.               "  while ((i = %s) > 0)\n    ;\n\n"
  112.               "  return i == 0 || strncmp (s = word_list[-i], str, len)"
  113.               " ? 0 : s;\n}\n",
  114.               option[CONST] ? "const " : "",
  115.               option[CONST] ? "const " : "",
  116.               option[CONST] ? "" : "(char*)",
  117.               option[COMPACT] ? "next_state(i, *s++)" : "trie_array[i][*s++]");
  118.     }
  119. }
  120.  
  121. /* Comparison routine called by qsort. */
  122. int 
  123. Trie::cmp (char **s1, char **s2)
  124. {
  125.   return strcmp (*s1, *s2);
  126. }
  127.  
  128. /* Sort the keys by lexicographical order. */
  129.  
  130. void 
  131. Trie::sort (void)
  132. {
  133.   typedef int (*PTF)(void *, void *);
  134.   qsort ((void *) keys, current_size, sizeof *keys, PTF (cmp));
  135. }
  136.  
  137. /* Generate the trie, using recursive calls if necessary to handle 
  138.    duplicate keyword index positions. */
  139.  
  140. void 
  141. Trie::build (int hi, int lo, int col)
  142. {
  143.   if (option[FULL])
  144.     {
  145.       int row = max_row - 1;
  146.  
  147.       /* Process each key in the range lo..hi, possibly calling the function
  148.          recursively when duplicate consecutive characters are found (that's
  149.          why it is important to sort the keywords first!).  Note that calls
  150.          to member function MATRIX build the internal form used to generate 
  151.          the compacted sparse array.  Positive values indicate the next row
  152.          (which really encodes DFA states) to consider; negative values
  153.          are flags that provide (when negated) the correct offset into a generated 
  154.          array of strings. */
  155.       
  156.       for (int i = lo; i < hi; i++)
  157.         if (keys[i][col] == '\0')
  158.           matrix (row, keys[i][col], -i - 1);
  159.         else
  160.           {
  161.             /* Location the end of the duplicate characters in the current column. */
  162.             
  163.             for (lo = i; i < hi - 1 && keys[i][col] == keys[i + 1][col]; i++)
  164.               ;
  165.             
  166.             matrix (row, keys[lo][col], max_row++);
  167.             build (i + 1, lo, col + 1);
  168.           }
  169.     } 
  170.   else
  171.     {
  172.       int row = max_row - 1;
  173.  
  174.       /* Process each key in the range lo..hi, possibly calling the function
  175.          recursively when duplicate consecutive characters are found (that's
  176.          why it is important to sort the keywords first!).  Note that calls
  177.          to member function MATRIX build the internal form used to generate 
  178.          the compacted sparse array.  Positive values indicate the next row
  179.          (which really encodes DFA states) to consider; negative values
  180.          are flags that provide (when negated) the correct offset into a generated 
  181.          array of strings. */
  182.       
  183.       for (int i = lo; i < hi; i++)
  184.         if (keys[i][col] == '\0' || i == hi - 1 || keys[i][col] != keys[i + 1][col])
  185.           matrix (row, keys[i][col], -i - 1);
  186.         else
  187.           {
  188.             /* Location the end of the duplicate characters in the current column. */
  189.             
  190.             for (lo = i; i < hi - 1 && keys[i][col] == keys[i + 1][col]; i++)
  191.               ;
  192.             
  193.             matrix (row, keys[lo][col], max_row++);
  194.             build (i + 1, lo, col + 1);
  195.           }
  196.     } 
  197. }  
  198.