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
hash_string(const char * p)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.
unused(void *)76 inline void unused(void *) { }
77
symbol(const char * p,int how)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
concat(symbol s1,symbol s2)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");
160