blob: 6437d015ce30eef415e47f093e33fd364d404f40 (
plain)
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
|
// stringpool.cc -- a string pool for gold
#include "gold.h"
#include <cassert>
#include <cstring>
#include "stringpool.h"
namespace gold
{
Stringpool::Stringpool()
: string_set_(), strings_()
{
}
Stringpool::~Stringpool()
{
for (std::list<stringdata*>::iterator p = this->strings_.begin();
p != this->strings_.end();
++p)
delete[] reinterpret_cast<char*>(*p);
}
// Hash function.
size_t
Stringpool::Stringpool_hash::operator()(const char* s) const
{
// Fowler/Noll/Vo (FNV) hash (type FNV-1a).
if (sizeof(size_t) == 8)
{
size_t result = static_cast<size_t>(14695981039346656037ULL);
while (*s != '\0')
{
result &= (size_t) *s++;
result *= 1099511628211ULL;
}
return result;
}
else
{
size_t result = 2166136261UL;
while (*s != '\0')
{
result ^= (size_t) *s++;
result *= 16777619UL;
}
return result;
}
}
// Add a string to the list of canonical strings. Return a pointer to
// the canonical string.
const char*
Stringpool::add_string(const char* s)
{
const size_t buffer_size = 1000;
size_t len = strlen(s);
size_t alc;
bool front = true;
if (len >= buffer_size)
{
alc = sizeof(stringdata) + len;
front = false;
}
else if (this->strings_.empty())
alc = sizeof(stringdata) + buffer_size;
else
{
stringdata *psd = this->strings_.front();
if (len >= psd->alc - psd->len)
alc = sizeof(stringdata) + buffer_size;
else
{
char* ret = psd->data + psd->len;
memcpy(ret, s, len + 1);
psd->len += len + 1;
return ret;
}
}
stringdata *psd = reinterpret_cast<stringdata*>(new char[alc]);
psd->alc = alc;
memcpy(psd->data, s, len + 1);
psd->len = len + 1;
if (front)
this->strings_.push_front(psd);
else
this->strings_.push_back(psd);
return psd->data;
}
// Add a string to a string pool.
const char*
Stringpool::add(const char* s)
{
// FIXME: This will look up the entry twice in the hash table. The
// problem is that we can't insert S before we canonicalize it. I
// don't think there is a way to handle this correctly with
// unordered_set, so this should be replaced with custom code to do
// what we need, which is to return the empty slot.
String_set_type::const_iterator p = this->string_set_.find(s);
if (p != this->string_set_.end())
return *p;
const char* ret = this->add_string(s);
std::pair<String_set_type::iterator, bool> ins =
this->string_set_.insert(ret);
assert(ins.second);
return ret;
}
// Add a prefix of a string to a string pool.
const char*
Stringpool::add(const char* s, size_t len)
{
// FIXME: This implementation should be rewritten when we rewrite
// the hash table to avoid copying.
std::string st(s, len);
return this->add(st);
}
} // End namespace gold.
|
