libbase/string_table.cpp

   1 // string_table.cpp -- A shared string table for Gnash.
   2 //
   3 //   Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010 Free Software
   4 //   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
  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                         boost::mutex::scoped_lock aLock(_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
  66 string_table::insert(const std::string& to_insert)
  67 {
  68         boost::mutex::scoped_lock aLock(_lock);
  69     return already_locked_insert(to_insert);
  70 }
  71
  72 void
  73 string_table::insert_group(const svt* l, std::size_t size)
  74 {
  75         boost::mutex::scoped_lock aLock(_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
 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
 138 string_table::setHighestKnownLowercase(key k)
 139 {
 140     _highestKnownLowercase = k;
 141 }
 142
 143 string_table::key
 144 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
 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 }