troff/symbol.cc

   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 const int BLOCK_SIZE = 1024;
  34 // the table will increase in size as necessary
  35 // the size will be chosen from the following array
  36 // add some more if you want
  37 // I think it unlikely that we'll need more than a million symbols
  38 static const unsigned int table_sizes[] = {
  39 101, 503, 1009, 2003, 3001, 4001, 5003, 10007, 20011, 40009, 80021, 160001, 500009, 1000003, 0
  40 };
  41 const double FULL_MAX = 0.3;    // don't let the table get more than this full
  42
  43 static unsigned int hash_string(const char *p)
  44 {
  45   // compute a hash code; this assumes 32-bit unsigned ints
  46   // see p436 of  Compilers by Aho, Sethi & Ullman
  47   // give special treatment to two-character names
  48   unsigned int hc = 0, g;
  49   if (*p != 0) {
  50     hc = *p++;
  51     if (*p != 0) {
  52       hc <<= 7;
  53       hc += *p++;
  54       for (; *p != 0; p++) {
  55         hc <<= 4;
  56         hc += *p;
  57         if ((g = (hc & 0xf0000000)) == 0) {
  58           hc ^= g >> 24;
  59           hc ^= g;
  60         }
  61       }
  62     }
  63   }
  64   return hc;
  65 }
  66
  67 symbol::symbol(const char *p, int how)
  68 {
  69   if (p == 0 || *p == 0) {
  70     s = 0;
  71     return;
  72   }
  73   if (table == 0) {
  74     table_size = table_sizes[0];
  75     table = new char*[table_size];
  76     for (int i = 0; i < table_size; i++)
  77       table[i] = 0;
  78     table_used = 0;
  79   }
  80   unsigned int hc = hash_string(p);
  81   for (const char **pp  = table + hc % table_size;
  82        *pp != 0;
  83        (pp == table ? pp = table + table_size - 1 : --pp))
  84     if (strcmp(p, *pp) == 0) {
  85       s = *pp;
  86       return;
  87     }
  88   if (how == MUST_ALREADY_EXIST) {
  89     s = 0;
  90     return;
  91   }
  92   if (table_used  >= table_size - 1 || table_used >= table_size*FULL_MAX) {
  93     const char **old_table = table;
  94     unsigned int old_table_size = table_size;
  95     for (int i = 1; table_sizes[i] <= old_table_size; i++)
  96       if (table_sizes[i] == 0)
  97         fatal("too many symbols");
  98     table_size = table_sizes[i];
  99     table_used = 0;
 100     table = new char*[table_size];
 101     for (i = 0; i < table_size; i++)
 102       table[i] = 0;
 103     for (pp = old_table + old_table_size - 1;
 104          pp >= old_table;
 105          --pp) {
 106            symbol temp(*pp, 1); /* insert it into the new table */
 107          }
 108     a_delete old_table;
 109     for (pp = table + hc % table_size;
 110          *pp != 0;
 111          (pp == table ? pp = table + table_size - 1 : --pp))
 112       ;
 113   }
 114   ++table_used;
 115   if (how == DONT_STORE) {
 116     s = *pp = p;
 117   }
 118   else {
 119     int len = strlen(p)+1;
 120     if (block == 0 || block_size < len) {
 121       block_size = len > BLOCK_SIZE ? len : BLOCK_SIZE;
 122       block = new char [block_size];
 123     }
 124     (void)strcpy(block, p);
 125     s = *pp = block;
 126     block += len;
 127     block_size -= len;
 128   }
 129 }
 130
 131 symbol concat(symbol s1, symbol s2)
 132 {
 133   char *buf = new char [strlen(s1.contents()) + strlen(s2.contents()) + 1];
 134   strcpy(buf, s1.contents());
 135   strcat(buf, s2.contents());
 136   symbol res(buf);
 137   a_delete buf;
 138   return res;
 139 }
 140