home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 4 / FreshFish_May-June1994.bin / bbs / gnu / groff-1.09-src.lha / src / amiga / groff-1.09 / troff / symbol.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1994-02-13  |  3.9 KB  |  149 lines
  1. // -*- C++ -*-
  2. /* Copyright (C) 1989, 1990, 1991, 1992 Free Software Foundation, Inc.
  3.      Written by James Clark (jjc@jclark.com)
  4.  
  5. This file is part of groff.
  6.  
  7. groff is free software; you can redistribute it and/or modify it under
  8. the terms of the GNU General Public License as published by the Free
  9. Software Foundation; either version 2, or (at your option) any later
  10. version.
  11.  
  12. groff is distributed in the hope that it will be useful, but WITHOUT ANY
  13. WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14. FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15. for more details.
  16.  
  17. You should have received a copy of the GNU General Public License along
  18. with groff; see the file COPYING.  If not, write to the Free Software
  19. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
  20.  
  21.  
  22. #include "troff.h"
  23. #include "symbol.h"
  24.  
  25. const char **symbol::table = 0;
  26. int symbol::table_used = 0;
  27. int symbol::table_size = 0;
  28. char *symbol::block = 0;
  29. int symbol::block_size = 0;
  30.  
  31. const symbol NULL_SYMBOL;
  32.  
  33. #ifdef BLOCK_SIZE
  34. #undef BLOCK_SIZE
  35. #endif
  36.  
  37. const int BLOCK_SIZE = 1024;
  38. // the table will increase in size as necessary
  39. // the size will be chosen from the following array
  40. // add some more if you want
  41. // I think it unlikely that we'll need more than a million symbols
  42. static const unsigned int table_sizes[] = { 
  43. 101, 503, 1009, 2003, 3001, 4001, 5003, 10007, 20011, 40009, 80021, 160001, 500009, 1000003, 0 
  44. };
  45. const double FULL_MAX = 0.3;    // don't let the table get more than this full
  46.  
  47. static unsigned int hash_string(const char *p)
  48. {
  49.   // compute a hash code; this assumes 32-bit unsigned ints
  50.   // see p436 of  Compilers by Aho, Sethi & Ullman
  51.   // give special treatment to two-character names
  52.   unsigned int hc = 0, g;
  53.   if (*p != 0) {
  54.     hc = *p++;
  55.     if (*p != 0) {
  56.       hc <<= 7;
  57.       hc += *p++;
  58.       for (; *p != 0; p++) {
  59.     hc <<= 4;
  60.     hc += *p;
  61.     if ((g = (hc & 0xf0000000)) == 0) {
  62.       hc ^= g >> 24;
  63.       hc ^= g;
  64.     }
  65.       }
  66.     }
  67.   }
  68.   return hc;
  69. }
  70.  
  71. // Tell compiler that a variable is intentionally unused.
  72. inline void unused(void *) { }
  73.  
  74. symbol::symbol(const char *p, int how)
  75. {
  76.   if (p == 0 || *p == 0) {
  77.     s = 0;
  78.     return;
  79.   }
  80.   if (table == 0) {
  81.     table_size = table_sizes[0];
  82.     table = (const char **)new char*[table_size];
  83.     for (int i = 0; i < table_size; i++)
  84.       table[i] = 0;
  85.     table_used = 0;
  86.   }
  87.   unsigned int hc = hash_string(p);
  88.   for (const char **pp  = table + hc % table_size; 
  89.        *pp != 0; 
  90.        (pp == table ? pp = table + table_size - 1 : --pp))
  91.     if (strcmp(p, *pp) == 0) {
  92.       s = *pp;
  93.       return;
  94.     }
  95.   if (how == MUST_ALREADY_EXIST) {
  96.     s = 0;
  97.     return;
  98.   }
  99.   if (table_used  >= table_size - 1 || table_used >= table_size*FULL_MAX) {
  100.     const char **old_table = table;
  101.     unsigned int old_table_size = table_size;
  102.     for (int i = 1; table_sizes[i] <= old_table_size; i++)
  103.       if (table_sizes[i] == 0)
  104.     fatal("too many symbols");
  105.     table_size = table_sizes[i];
  106.     table_used = 0;
  107.     table = (const char **)new char*[table_size];
  108.     for (i = 0; i < table_size; i++)
  109.       table[i] = 0;
  110.     for (pp = old_table + old_table_size - 1; 
  111.      pp >= old_table;
  112.      --pp) {
  113.        symbol temp(*pp, 1); /* insert it into the new table */
  114.        unused(&temp);
  115.      }
  116.     a_delete old_table;
  117.     for (pp = table + hc % table_size;
  118.      *pp != 0; 
  119.      (pp == table ? pp = table + table_size - 1 : --pp))
  120.       ;
  121.   }
  122.   ++table_used;
  123.   if (how == DONT_STORE) {
  124.     s = *pp = p;
  125.   }
  126.   else {
  127.     int len = strlen(p)+1;
  128.     if (block == 0 || block_size < len) {
  129.       block_size = len > BLOCK_SIZE ? len : BLOCK_SIZE;
  130.       block = new char [block_size];
  131.     }
  132.     (void)strcpy(block, p);
  133.     s = *pp = block;
  134.     block += len;
  135.     block_size -= len;
  136.   }
  137. }
  138.  
  139. symbol concat(symbol s1, symbol s2)
  140. {
  141.   char *buf = new char [strlen(s1.contents()) + strlen(s2.contents()) + 1];
  142.   strcpy(buf, s1.contents());
  143.   strcat(buf, s2.contents());
  144.   symbol res(buf);
  145.   a_delete buf;
  146.   return res;
  147. }
  148.  
  149.