string_table.h

Go to the documentation of this file.

// string_table.h -- A shared string table for Gnash.
// 
//   Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
//   Free Software Foundation, Inc
// 
// This program 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.
// 
// This program 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, write to the Free Software
// Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

#ifndef GNASH_STRING_TABLE_H
#define GNASH_STRING_TABLE_H

// Thread Status: SAFE, except for group functions.
// The group functions may have strange behavior when trying to automatically
// lowercase the additions.

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/thread.hpp>
#include <string>
#include <map>
#include "dsodefs.h"

namespace gnash {

// So many strings are duplicated (such as standard property names)
// that a string table could give significant memory savings.
class DSOEXPORT string_table
{
public:

        struct svt
        {
                svt(const std::string& val, std::size_t i)
            :
                        value(val),
            id(i)
        {}

                std::string value;
                std::size_t id;
        };
    
    struct StringID {};

    struct StringValue {};

    //
        typedef boost::multi_index_container<svt,
                boost::multi_index::indexed_by<

                        boost::multi_index::hashed_unique<
                boost::multi_index::tag<StringValue>,
                                boost::multi_index::member<svt, std::string, &svt::value> >,

                        boost::multi_index::hashed_unique<
                boost::multi_index::tag<StringID>,
                                boost::multi_index::member<svt, std::size_t, &svt::id>

        > 
        > > table;

        typedef std::size_t key;

    //
    //
        key find(const std::string& to_find, bool insert_unfound = true);

        //
        const std::string& value(key to_find) const
        {
                if (_table.empty() || !to_find) return _empty;

                table::index<StringID>::type::iterator r =
            _table.get<StringID>().find(to_find);
                return (r == _table.get<StringID>().end()) ? _empty : r->value;
        }

        //
        key insert(const std::string& to_insert);

    //
        void insert_group(const svt* pList, std::size_t size);

    //
        key already_locked_insert(const std::string& to_insert);

        string_table()
        :
                _highestKey(0),
                _highestKnownLowercase(0)
        {}

    //
    key noCase(key a) const;

    //
    void setHighestKnownLowercase(std::size_t k);

private:

        table _table;
        static const std::string _empty;
        boost::mutex _lock;
        std::size_t _highestKey;

    std::map<key, key> _caseTable;
    key _highestKnownLowercase;
};

//
//
//
DSOEXPORT bool equal(string_table& st, string_table::key a, string_table::key b,
        bool caseless);

}
#endif