1151497Sru// -*- C++ -*- 2151497Sru/* Copyright (C) 1989, 1990, 1991, 1992, 2002, 2004 3151497Sru Free Software Foundation, Inc. 4151497Sru Written by James Clark (jjc@jclark.com) 5151497Sru 6151497SruThis file is part of groff. 7151497Sru 8151497Srugroff is free software; you can redistribute it and/or modify it under 9151497Sruthe terms of the GNU General Public License as published by the Free 10151497SruSoftware Foundation; either version 2, or (at your option) any later 11151497Sruversion. 12151497Sru 13151497Srugroff is distributed in the hope that it will be useful, but WITHOUT ANY 14151497SruWARRANTY; without even the implied warranty of MERCHANTABILITY or 15151497SruFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16151497Srufor more details. 17151497Sru 18151497SruYou should have received a copy of the GNU General Public License along 19151497Sruwith groff; see the file COPYING. If not, write to the Free Software 20151497SruFoundation, 51 Franklin St - Fifth Floor, Boston, MA 02110-1301, USA. */ 21151497Sru 22151497Sru#include "lib.h" 23151497Sru 24151497Sru#include "errarg.h" 25151497Sru#include "error.h" 26151497Sru#include "symbol.h" 27151497Sru 28151497Sruconst char **symbol::table = 0; 29151497Sruint symbol::table_used = 0; 30151497Sruint symbol::table_size = 0; 31151497Sruchar *symbol::block = 0; 32151497Sruint symbol::block_size = 0; 33151497Sru 34151497Sruconst symbol NULL_SYMBOL; 35151497Sruconst symbol EMPTY_SYMBOL(""); 36151497Sru 37151497Sru#ifdef BLOCK_SIZE 38151497Sru#undef BLOCK_SIZE 39151497Sru#endif 40151497Sru 41151497Sruconst int BLOCK_SIZE = 1024; 42151497Sru// the table will increase in size as necessary 43151497Sru// the size will be chosen from the following array 44151497Sru// add some more if you want 45151497Srustatic const unsigned int table_sizes[] = { 46151497Sru 101, 503, 1009, 2003, 3001, 4001, 5003, 10007, 20011, 40009, 80021, 47151497Sru 160001, 500009, 1000003, 1500007, 2000003, 0 48151497Sru}; 49151497Sruconst double FULL_MAX = 0.3; // don't let the table get more than this full 50151497Sru 51151497Srustatic unsigned int hash_string(const char *p) 52151497Sru{ 53151497Sru // compute a hash code; this assumes 32-bit unsigned ints 54151497Sru // see p436 of Compilers by Aho, Sethi & Ullman 55151497Sru // give special treatment to two-character names 56151497Sru unsigned int hc = 0, g; 57151497Sru if (*p != 0) { 58151497Sru hc = *p++; 59151497Sru if (*p != 0) { 60151497Sru hc <<= 7; 61151497Sru hc += *p++; 62151497Sru for (; *p != 0; p++) { 63151497Sru hc <<= 4; 64151497Sru hc += *p; 65151497Sru if ((g = (hc & 0xf0000000)) == 0) { 66151497Sru hc ^= g >> 24; 67151497Sru hc ^= g; 68151497Sru } 69151497Sru } 70151497Sru } 71151497Sru } 72151497Sru return hc; 73151497Sru} 74151497Sru 75151497Sru// Tell compiler that a variable is intentionally unused. 76151497Sruinline void unused(void *) { } 77151497Sru 78151497Srusymbol::symbol(const char *p, int how) 79151497Sru{ 80151497Sru if (p == 0) { 81151497Sru s = 0; 82151497Sru return; 83151497Sru } 84151497Sru if (*p == 0) { 85151497Sru s = ""; 86151497Sru return; 87151497Sru } 88151497Sru if (table == 0) { 89151497Sru table_size = table_sizes[0]; 90151497Sru table = (const char **)new char*[table_size]; 91151497Sru for (int i = 0; i < table_size; i++) 92151497Sru table[i] = 0; 93151497Sru table_used = 0; 94151497Sru } 95151497Sru unsigned int hc = hash_string(p); 96151497Sru const char **pp; 97151497Sru for (pp = table + hc % table_size; 98151497Sru *pp != 0; 99151497Sru (pp == table ? pp = table + table_size - 1 : --pp)) 100151497Sru if (strcmp(p, *pp) == 0) { 101151497Sru s = *pp; 102151497Sru return; 103151497Sru } 104151497Sru if (how == MUST_ALREADY_EXIST) { 105151497Sru s = 0; 106151497Sru return; 107151497Sru } 108151497Sru if (table_used >= table_size - 1 || table_used >= table_size*FULL_MAX) { 109151497Sru const char **old_table = table; 110151497Sru unsigned int old_table_size = table_size; 111151497Sru int i; 112151497Sru for (i = 1; table_sizes[i] <= old_table_size; i++) 113151497Sru if (table_sizes[i] == 0) 114151497Sru fatal("too many symbols"); 115151497Sru table_size = table_sizes[i]; 116151497Sru table_used = 0; 117151497Sru table = (const char **)new char*[table_size]; 118151497Sru for (i = 0; i < table_size; i++) 119151497Sru table[i] = 0; 120151497Sru for (pp = old_table + old_table_size - 1; 121151497Sru pp >= old_table; 122151497Sru --pp) { 123151497Sru symbol temp(*pp, 1); /* insert it into the new table */ 124151497Sru unused(&temp); 125151497Sru } 126151497Sru a_delete old_table; 127151497Sru for (pp = table + hc % table_size; 128151497Sru *pp != 0; 129151497Sru (pp == table ? pp = table + table_size - 1 : --pp)) 130151497Sru ; 131151497Sru } 132151497Sru ++table_used; 133151497Sru if (how == DONT_STORE) { 134151497Sru s = *pp = p; 135151497Sru } 136151497Sru else { 137151497Sru int len = strlen(p)+1; 138151497Sru if (block == 0 || block_size < len) { 139151497Sru block_size = len > BLOCK_SIZE ? len : BLOCK_SIZE; 140151497Sru block = new char [block_size]; 141151497Sru } 142151497Sru (void)strcpy(block, p); 143151497Sru s = *pp = block; 144151497Sru block += len; 145151497Sru block_size -= len; 146151497Sru } 147151497Sru} 148151497Sru 149151497Srusymbol concat(symbol s1, symbol s2) 150151497Sru{ 151151497Sru char *buf = new char [strlen(s1.contents()) + strlen(s2.contents()) + 1]; 152151497Sru strcpy(buf, s1.contents()); 153151497Sru strcat(buf, s2.contents()); 154151497Sru symbol res(buf); 155151497Sru a_delete buf; 156151497Sru return res; 157151497Sru} 158151497Sru 159151497Srusymbol default_symbol("default"); 160