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