1 // string_table.h -- 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 #ifndef GNASH_STRING_TABLE_H 21 #define GNASH_STRING_TABLE_H 22 23 // Thread Status: SAFE, except for group functions. 24 // The group functions may have strange behavior when trying to automatically 25 // lowercase the additions. 26 27 #include <boost/multi_index_container.hpp> 28 #include <boost/multi_index/hashed_index.hpp> 29 #include <boost/multi_index/identity.hpp> 30 #include <boost/multi_index/member.hpp> 31 #include <string> 32 #include <map> 33 #include <mutex> 34 #include "dsodefs.h" 35 36 namespace gnash { 37 38 // So many strings are duplicated (such as standard property names) 39 // that a string table could give significant memory savings. 40 /// A general use string table. 41 class DSOEXPORT string_table 42 { 43 public: 44 45 /// A little helper for indexing. 46 struct svt 47 { svtsvt48 svt(std::string val, std::size_t i) 49 : 50 value(std::move(val)), 51 id(i) 52 {} 53 54 std::string value; 55 std::size_t id; 56 }; 57 58 /// A tag to identify the key index. 59 struct StringID {}; 60 61 /// A tag to identify the string index. 62 struct StringValue {}; 63 64 /// The container for indexing the strings 65 // 66 /// This contains two indices with no duplicate values: 67 /// 1. An index of unique, case-sensitive strings. 68 /// 2. An index of unique numeric keys. 69 typedef boost::multi_index_container<svt, 70 boost::multi_index::indexed_by< 71 72 boost::multi_index::hashed_unique< 73 boost::multi_index::tag<StringValue>, 74 boost::multi_index::member<svt, std::string, &svt::value> >, 75 76 boost::multi_index::hashed_unique< 77 boost::multi_index::tag<StringID>, 78 boost::multi_index::member<svt, std::size_t, &svt::id> 79 80 > 81 > > table; 82 83 typedef std::size_t key; 84 85 /// Find a key for a string. 86 // 87 /// By default a key will be created for a string that isn't present. 88 // 89 /// @param to_find The string to be found. 90 /// @param insert_unfound If this is set to false, a search is 91 /// performed, but no update. 92 /// @return A key which can be used in value or 0 if the 93 /// string is not yet in the table and 94 /// insert_unfound was false. 95 key find(const std::string& to_find, bool insert_unfound = true); 96 97 /// Find a string by its key. 98 // 99 /// @param key The key of the string to return. 100 /// @return The string which matches key or "" if an invalid key is 101 /// given. value(key to_find)102 const std::string& value(key to_find) const 103 { 104 if (_table.empty() || !to_find) return _empty; 105 106 table::index<StringID>::type::iterator r = 107 _table.get<StringID>().find(to_find); 108 return (r == _table.get<StringID>().end()) ? _empty : r->value; 109 } 110 111 /// Insert a string with auto-assigned id. 112 // 113 /// @return The assigned key 114 key insert(const std::string& to_insert); 115 116 /// Insert a group of strings with their ids preset. 117 // 118 /// @param pList An array of svt objects, these should be fully 119 /// constructed, including their ids. If any id is 120 /// duplicated, the insertion will fail. 121 /// @param size Number of elements in the svt objects array 122 void insert_group(const svt* pList, std::size_t size); 123 124 /// Insert a string when you will handle the locking yourself. 125 // 126 /// @param to_insert The string to insert 127 /// @return The assigned key 128 key already_locked_insert(const std::string& to_insert); 129 130 /// Construct the empty string_table string_table()131 string_table() 132 : 133 _highestKey(0), 134 _highestKnownLowercase(0) 135 {} 136 137 /// Return a caseless equivalent of the passed key. 138 // 139 /// @param a The key to find a caseless equivalent for. The key 140 /// may be its own caseless equivalent, in which case the 141 /// same key will be returned. 142 key noCase(key a) const; 143 144 /// Set the highest key value known to correspond to a lowercase name 145 // 146 void setHighestKnownLowercase(std::size_t k); 147 148 private: 149 150 table _table; 151 static const std::string _empty; 152 std::mutex _lock; 153 std::size_t _highestKey; 154 155 std::map<key, key> _caseTable; 156 key _highestKnownLowercase; 157 }; 158 159 /// Check whether two keys are equivalent 160 // 161 /// This function provides a simple way to check for equivalence either in 162 /// a case sensitive or case-insensitive way. It is mainly for convenience, to 163 /// reduce conditionals in the code. 164 // 165 /// If the comparison is case-sensitive, the keys are equivalent if they are 166 /// equal. 167 // 168 /// @param st The string table to use 169 /// @param a One key to check 170 /// @param b The other key to check 171 /// @param caseless Whether to compare in a case-insensitive way. 172 /// @return True if the keys are equivalent. 173 DSOEXPORT bool equal(string_table& st, string_table::key a, string_table::key b, 174 bool caseless); 175 176 } 177 #endif 178