LiteralTable.h 5.39 KB
Newer Older
1
/**************************************************************************
con's avatar
con committed
2 3 4
**
** This file is part of Qt Creator
**
5
** Copyright (c) 2009 Nokia Corporation and/or its subsidiary(-ies).
con's avatar
con committed
6
**
7
** Contact: Nokia Corporation (qt-info@nokia.com)
con's avatar
con committed
8
**
9
** Commercial Usage
10
**
11 12 13 14
** Licensees holding valid Qt Commercial licenses may use this file in
** accordance with the Qt Commercial License Agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and Nokia.
15
**
16
** GNU Lesser General Public License Usage
17
**
18 19 20 21 22 23
** Alternatively, this file may be used under the terms of the GNU Lesser
** General Public License version 2.1 as published by the Free Software
** Foundation and appearing in the file LICENSE.LGPL included in the
** packaging of this file.  Please review the following information to
** ensure the GNU Lesser General Public License version 2.1 requirements
** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
24
**
25
** If you are unsure which license is appropriate for your use, please
26
** contact the sales department at http://www.qtsoftware.com/contact.
con's avatar
con committed
27
**
28
**************************************************************************/
con's avatar
con committed
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
// Copyright (c) 2008 Roberto Raggi <roberto.raggi@gmail.com>
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

#ifndef CPLUSPLUS_LITERALTABLE_H
#define CPLUSPLUS_LITERALTABLE_H

#include "CPlusPlusForwardDeclarations.h"
#include <cstring>
#include <cstdlib>

CPLUSPLUS_BEGIN_HEADER
CPLUSPLUS_BEGIN_NAMESPACE

template <typename _Literal>
class LiteralTable
{
    LiteralTable(const LiteralTable &other);
    void operator =(const LiteralTable &other);

public:
    typedef _Literal **iterator;

public:
    LiteralTable()
       : _literals(0),
         _allocatedLiterals(0),
         _literalCount(-1),
         _buckets(0),
         _allocatedBuckets(0)
    { }

    ~LiteralTable()
    {
       if (_literals) {
           _Literal **lastLiteral = _literals + _literalCount + 1;
           for (_Literal **it = _literals; it != lastLiteral; ++it)
              delete *it;
83
           std::free(_literals);
con's avatar
con committed
84 85
       }
       if (_buckets)
86
           std::free(_buckets);
con's avatar
con committed
87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109
    }

    bool empty() const
    { return _literalCount == -1; }

    unsigned size() const
    { return _literalCount + 1; }

    _Literal *at(unsigned index) const
    { return _literals[index]; }

    iterator begin() const
    { return _literals; }

    iterator end() const
    { return _literals + _literalCount + 1; }

    _Literal *findOrInsertLiteral(const char *chars, unsigned size)
    {
       if (_buckets) {
           unsigned h = _Literal::hashCode(chars, size);
           _Literal *literal = _buckets[h % _allocatedBuckets];
           for (; literal; literal = static_cast<_Literal *>(literal->_next)) {
110
               if (literal->size() == size && ! std::strncmp(literal->chars(), chars, size))
con's avatar
con committed
111 112 113 114 115 116 117 118 119 120 121 122
                  return literal;
           }
       }

       _Literal *literal = new _Literal(chars, size);

       if (++_literalCount == _allocatedLiterals) {
           _allocatedLiterals <<= 1;

           if (! _allocatedLiterals)
              _allocatedLiterals = 256;

123
           _literals = (_Literal **) std::realloc(_literals, sizeof(_Literal *) * _allocatedLiterals);
con's avatar
con committed
124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142
       }

       _literals[_literalCount] = literal;

       if (! _buckets || _literalCount >= _allocatedBuckets * .6)
           rehash();
       else {
           unsigned h = literal->hashCode() % _allocatedBuckets;
           literal->_next = _buckets[h];
           _buckets[h] = literal;
       }

       return literal;
    }

protected:
    void rehash()
    {
       if (_buckets)
143
           std::free(_buckets);
con's avatar
con committed
144 145 146 147 148 149

       _allocatedBuckets <<= 1;

       if (! _allocatedBuckets)
           _allocatedBuckets = 256;

150
       _buckets = (_Literal **) std::calloc(_allocatedBuckets, sizeof(_Literal *));
con's avatar
con committed
151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177

       _Literal **lastLiteral = _literals + (_literalCount + 1);

       for (_Literal **it = _literals; it != lastLiteral; ++it) {
           _Literal *literal = *it;
           unsigned h = literal->hashCode() % _allocatedBuckets;

           literal->_next = _buckets[h];
           _buckets[h] = literal;
       }
    }

protected:
    MemoryPool *_pool;

    _Literal **_literals;
    int _allocatedLiterals;
    int _literalCount;

    _Literal **_buckets;
    int _allocatedBuckets;
};

CPLUSPLUS_END_NAMESPACE
CPLUSPLUS_END_HEADER

#endif // CPLUSPLUS_LITERALTABLE_H