1 // string_table.cpp -- A shared string table for Gnash.
2 //
3 // Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
4 // Free Software Foundation, Inc
5 //
6 // This program is free software; you can redistribute it and/or modify
7 // it under the terms of the GNU General Public License as published by
8 // the Free Software Foundation; either version 3 of the License, or
9 // (at your option) any later version.
10 //
11 // This program is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15 //
16 // You should have received a copy of the GNU General Public License
17 // along with this program; if not, write to the Free Software
18 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19
20 #include "string_table.h"
21 #ifdef HAVE_CONFIG_H
22 #include "gnashconfig.h" // GNASH_STATS_STRING_TABLE_NOCASE
23 #endif
24
25 #include <boost/algorithm/string/case_conv.hpp>
26
27 //#define DEBUG_STRING_TABLE 1
28 //#define GNASH_STATS_STRING_TABLE_NOCASE 1
29 //#define GNASH_PARANOIA_LEVEL 3
30
31 #ifdef GNASH_STATS_STRING_TABLE_NOCASE
32 # include "Stats.h"
33 #endif
34
35 namespace gnash {
36
37 const std::string string_table::_empty;
38
39 string_table::key
find(const std::string & t_f,bool insert_unfound)40 string_table::find(const std::string& t_f, bool insert_unfound)
41 {
42 if (t_f.empty()) return 0;
43
44 table::index<StringValue>::type::iterator i =
45 _table.get<StringValue>().find(t_f);
46
47 if (i == _table.get<StringValue>().end()) {
48
49 if (insert_unfound) {
50 // First we lock.
51 std::lock_guard<std::mutex> lock(_lock);
52 // Then we see if someone else managed to sneak past us.
53 i = _table.get<StringValue>().find(t_f);
54 // If they did, use that value.
55 if (i != _table.end()) return i->id;
56
57 return already_locked_insert(t_f);
58 }
59 return 0;
60 }
61
62 return i->id;
63 }
64
65 string_table::key
insert(const std::string & to_insert)66 string_table::insert(const std::string& to_insert)
67 {
68 std::lock_guard<std::mutex> lock(_lock);
69 return already_locked_insert(to_insert);
70 }
71
72 void
insert_group(const svt * l,std::size_t size)73 string_table::insert_group(const svt* l, std::size_t size)
74 {
75 std::lock_guard<std::mutex> lock(_lock);
76 for (std::size_t i = 0; i < size; ++i) {
77 // Copy to avoid changing the original table.
78 const svt s = l[i];
79
80 // The keys don't have to be consecutive, so any time we find a key
81 // that is too big, jump a few keys to avoid rewriting this on every
82 // item.
83 if (s.id > _highestKey) _highestKey = s.id + 256;
84 _table.insert(s);
85 }
86
87 for (std::size_t i = 0; i < size; ++i) {
88 const svt s = l[i];
89 const std::string& t = boost::to_lower_copy(s.value);
90 if (t != s.value) {
91 _caseTable[s.id] = already_locked_insert(t);
92 }
93 }
94 #ifdef DEBUG_STRING_TABLE
95 std::cerr << "string_table group insert end -- size is " << _table.size() << " _caseTable size is " << _caseTable.size() << std::endl;
96 #endif
97
98
99 }
100
101 string_table::key
already_locked_insert(const std::string & to_insert)102 string_table::already_locked_insert(const std::string& to_insert)
103 {
104 const key ret = _table.insert(svt(to_insert, ++_highestKey)).first->id;
105
106 #ifdef DEBUG_STRING_TABLE
107 int tscp = 100; // table size checkpoint
108 size_t ts = _table.size();
109 if ( ! (ts % tscp) ) { std::cerr << "string_table size grew to " << ts << std::endl; }
110 #endif
111
112 const std::string lower = boost::to_lower_copy(to_insert);
113
114 // Insert the caseless equivalent if it's not there. We're locked for
115 // the whole of this function, so we can do what we like.
116 if (lower != to_insert) {
117
118 // Find the caseless value in the table
119 table::index<StringValue>::type::iterator it =
120 _table.get<StringValue>().find(lower);
121
122 const key nocase = (it == _table.end()) ?
123 _table.insert(svt(lower, ++_highestKey)).first->id : it->id;
124
125 #ifdef DEBUG_STRING_TABLE
126 ++ts;
127 if ( ! (ts % tscp) ) { std::cerr << "string_table size grew to " << ts << std::endl; }
128 #endif // DEBUG_STRING_TABLE
129
130 _caseTable[ret] = nocase;
131
132 }
133
134 return ret;
135 }
136
137 void
setHighestKnownLowercase(key k)138 string_table::setHighestKnownLowercase(key k)
139 {
140 _highestKnownLowercase = k;
141 }
142
143 string_table::key
noCase(key a) const144 string_table::noCase(key a) const
145 {
146 #ifdef GNASH_STATS_STRING_TABLE_NOCASE
147 static stats::KeyLookup kcl("string_table::noCase(maplookups)", *this);
148 #endif // GNASH_STATS_STRING_TABLE_NOCASE
149
150 // Avoid checking keys known to be lowercase
151 if ( a <= _highestKnownLowercase ) {
152 #if GNASH_PARANOIA_LEVEL > 2
153 assert(_caseTable.find(a) == _caseTable.end());
154 #endif
155 return a;
156 }
157
158 // MOVE this block around for special needs
159 #ifdef GNASH_STATS_STRING_TABLE_NOCASE
160 kcl.check(a);
161 #endif
162
163 // TODO: an even/odd based rule to tell what's lowercase already
164 // would speed things up even for unknown
165 // strings.
166
167 std::map<key, key>::const_iterator i = _caseTable.find(a);
168 if ( i != _caseTable.end() ) return i->second;
169
170 return a;
171 }
172
173 bool
equal(string_table & st,string_table::key a,string_table::key b,bool caseless)174 equal(string_table& st, string_table::key a, string_table::key b,
175 bool caseless)
176 {
177 if (a == b) return true;
178 return caseless && (st.noCase(a) == st.noCase(b));
179 }
180
181 }
182