contrib/groff/src/libs/libgroff/symbol.cpp

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