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 6This file is part of groff. 7 8groff is free software; you can redistribute it and/or modify it under 9the terms of the GNU General Public License as published by the Free 10Software Foundation; either version 2, or (at your option) any later 11version. 12 13groff is distributed in the hope that it will be useful, but WITHOUT ANY 14WARRANTY; without even the implied warranty of MERCHANTABILITY or 15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16for more details. 17 18You should have received a copy of the GNU General Public License along 19with groff; see the file COPYING. If not, write to the Free Software 20Foundation, 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 28const char **symbol::table = 0; 29int symbol::table_used = 0; 30int symbol::table_size = 0; 31char *symbol::block = 0; 32int symbol::block_size = 0; 33 34const symbol NULL_SYMBOL; 35const symbol EMPTY_SYMBOL(""); 36 37#ifdef BLOCK_SIZE 38#undef BLOCK_SIZE 39#endif 40 41const 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 45static 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}; 49const double FULL_MAX = 0.3; // don't let the table get more than this full 50 51static 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. 76inline void unused(void *) { } 77 78symbol::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 149symbol 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 159symbol default_symbol("default"); 160