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

   1 // -*- C++ -*-
   2 /* Copyright (C) 1989, 1990, 1991, 1992, 2002, 2004
   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 2, or (at your option) any later
  11 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 along
  19 with groff; see the file COPYING.  If not, write to the Free Software
  20 Foundation, 51 Franklin St - Fifth Floor, Boston, MA 02110-1301, USA. */
  21
  22 #include "lib.h"
  23
  24 #include "errarg.h"
  25 #include "error.h"
  26 #include "symbol.h"
  27
  28 const char **symbol::table = 0;
  29 int symbol::table_used = 0;
  30 int symbol::table_size = 0;
  31 char *symbol::block = 0;
  32 int symbol::block_size = 0;
  33
  34 const symbol NULL_SYMBOL;
  35 const symbol EMPTY_SYMBOL("");
  36
  37 #ifdef BLOCK_SIZE
  38 #undef BLOCK_SIZE
  39 #endif
  40
  41 const int BLOCK_SIZE = 1024;
  42 // the table will increase in size as necessary
  43 // the size will be chosen from the following array
  44 // add some more if you want
  45 static const unsigned int table_sizes[] = {
  46   101, 503, 1009, 2003, 3001, 4001, 5003, 10007, 20011, 40009, 80021,
  47   160001, 500009, 1000003, 1500007, 2000003, 0
  48 };
  49 const double FULL_MAX = 0.3;    // don't let the table get more than this full
  50
  51 static unsigned int hash_string(const char *p)
  52 {
  53   // compute a hash code; this assumes 32-bit unsigned ints
  54   // see p436 of  Compilers by Aho, Sethi & Ullman
  55   // give special treatment to two-character names
  56   unsigned int hc = 0, g;
  57   if (*p != 0) {
  58     hc = *p++;
  59     if (*p != 0) {
  60       hc <<= 7;
  61       hc += *p++;
  62       for (; *p != 0; p++) {
  63         hc <<= 4;
  64         hc += *p;
  65         if ((g = (hc & 0xf0000000)) == 0) {
  66           hc ^= g >> 24;
  67           hc ^= g;
  68         }
  69       }
  70     }
  71   }
  72   return hc;
  73 }
  74
  75 // Tell compiler that a variable is intentionally unused.
  76 inline void unused(void *) { }
  77
  78 symbol::symbol(const char *p, int how)
  79 {
  80   if (p == 0) {
  81     s = 0;
  82     return;
  83   }
  84   if (*p == 0) {
  85     s = "";
  86     return;
  87   }
  88   if (table == 0) {
  89     table_size = table_sizes[0];
  90     table = (const char **)new char*[table_size];
  91     for (int i = 0; i < table_size; i++)
  92       table[i] = 0;
  93     table_used = 0;
  94   }
  95   unsigned int hc = hash_string(p);
  96   const char **pp;
  97   for (pp = table + hc % table_size;
  98        *pp != 0;
  99        (pp == table ? pp = table + table_size - 1 : --pp))
 100     if (strcmp(p, *pp) == 0) {
 101       s = *pp;
 102       return;
 103     }
 104   if (how == MUST_ALREADY_EXIST) {
 105     s = 0;
 106     return;
 107   }
 108   if (table_used  >= table_size - 1 || table_used >= table_size*FULL_MAX) {
 109     const char **old_table = table;
 110     unsigned int old_table_size = table_size;
 111     int i;
 112     for (i = 1; table_sizes[i] <= old_table_size; i++)
 113       if (table_sizes[i] == 0)
 114         fatal("too many symbols");
 115     table_size = table_sizes[i];
 116     table_used = 0;
 117     table = (const char **)new char*[table_size];
 118     for (i = 0; i < table_size; i++)
 119       table[i] = 0;
 120     for (pp = old_table + old_table_size - 1;
 121          pp >= old_table;
 122          --pp) {
 123            symbol temp(*pp, 1); /* insert it into the new table */
 124            unused(&temp);
 125          }
 126     a_delete old_table;
 127     for (pp = table + hc % table_size;
 128          *pp != 0;
 129          (pp == table ? pp = table + table_size - 1 : --pp))
 130       ;
 131   }
 132   ++table_used;
 133   if (how == DONT_STORE) {
 134     s = *pp = p;
 135   }
 136   else {
 137     int len = strlen(p)+1;
 138     if (block == 0 || block_size < len) {
 139       block_size = len > BLOCK_SIZE ? len : BLOCK_SIZE;
 140       block = new char [block_size];
 141     }
 142     (void)strcpy(block, p);
 143     s = *pp = block;
 144     block += len;
 145     block_size -= len;
 146   }
 147 }
 148
 149 symbol concat(symbol s1, symbol s2)
 150 {
 151   char *buf = new char [strlen(s1.contents()) + strlen(s2.contents()) + 1];
 152   strcpy(buf, s1.contents());
 153   strcat(buf, s2.contents());
 154   symbol res(buf);
 155   a_delete buf;
 156   return res;
 157 }
 158
 159 symbol default_symbol("default");