LiteralTable.h 6.09 KB
Newer Older
1
/**************************************************************************
con's avatar
con committed
2
3
4
**
** This file is part of Qt Creator
**
con's avatar
con committed
5
** Copyright (c) 2011 Nokia Corporation and/or its subsidiary(-ies).
con's avatar
con committed
6
**
hjk's avatar
hjk committed
7
** Contact: Nokia Corporation (info@qt.nokia.com)
con's avatar
con committed
8
**
9
**
10
** GNU Lesser General Public License Usage
11
**
hjk's avatar
hjk committed
12
13
14
15
16
17
** 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.
18
**
con's avatar
con committed
19
** In addition, as a special exception, Nokia gives you certain additional
hjk's avatar
hjk committed
20
** rights. These rights are described in the Nokia Qt LGPL Exception
con's avatar
con committed
21
22
** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
**
hjk's avatar
hjk committed
23
24
25
26
27
** Other Usage
**
** Alternatively, this file may be used in accordance with the terms and
** conditions contained in a signed written agreement between you and Nokia.
**
con's avatar
con committed
28
** If you have questions regarding the use of this file, please contact
Tobias Hunger's avatar
Tobias Hunger committed
29
** Nokia at info@qt.nokia.com.
con's avatar
con committed
30
**
31
**************************************************************************/
con's avatar
con committed
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
// 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>
Roberto Raggi's avatar
Roberto Raggi committed
57
58

namespace CPlusPlus {
con's avatar
con committed
59
60
61
62
63
64
65
66

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

public:
Roberto Raggi's avatar
Roberto Raggi committed
67
    typedef _Literal *const *iterator;
con's avatar
con committed
68
69
70
71

public:
    LiteralTable()
       : _literals(0),
72
         _buckets(0),
con's avatar
con committed
73
74
75
76
77
78
         _allocatedLiterals(0),
         _literalCount(-1),
         _allocatedBuckets(0)
    { }

    ~LiteralTable()
79
80
81
82
83
    {
        reset();
    }

    void reset()
con's avatar
con committed
84
    {
Roberto Raggi's avatar
Roberto Raggi committed
85
86
87
88
89
90
91
92
        if (_literals) {
            _Literal **lastLiteral = _literals + _literalCount + 1;
            for (_Literal **it = _literals; it != lastLiteral; ++it)
                delete *it;
            std::free(_literals);
        }
        if (_buckets)
            std::free(_buckets);
93
94
95
96
97
98

        _literals = 0;
        _buckets = 0;
        _allocatedLiterals = 0;
        _literalCount = -1;
        _allocatedBuckets = 0;
con's avatar
con committed
99
100
101
102
103
104
105
106
    }

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

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

Roberto Raggi's avatar
Roberto Raggi committed
107
    const _Literal *at(unsigned index) const
con's avatar
con committed
108
109
110
111
112
113
114
115
    { return _literals[index]; }

    iterator begin() const
    { return _literals; }

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

Roberto Raggi's avatar
Roberto Raggi committed
116
    const _Literal *findLiteral(const char *chars, unsigned size) const
117
    {
Roberto Raggi's avatar
Roberto Raggi committed
118
119
120
121
122
123
124
125
126
127
128
        if (_buckets) {
            unsigned h = _Literal::hashCode(chars, size);
            _Literal *literal = _buckets[h % _allocatedBuckets];
            for (; literal; literal = static_cast<_Literal *>(literal->_next)) {
                if (literal->size() == size && ! std::strncmp(literal->chars(), chars, size))
                    return literal;
            }
        }

        return 0;
    }
129

Roberto Raggi's avatar
Roberto Raggi committed
130
    const _Literal *findOrInsertLiteral(const char *chars, unsigned size)
con's avatar
con committed
131
    {
Roberto Raggi's avatar
Roberto Raggi committed
132
133
134
135
136
137
138
139
        if (_buckets) {
            unsigned h = _Literal::hashCode(chars, size);
            _Literal *literal = _buckets[h % _allocatedBuckets];
            for (; literal; literal = static_cast<_Literal *>(literal->_next)) {
                if (literal->size() == size && ! std::strncmp(literal->chars(), chars, size))
                    return literal;
            }
        }
con's avatar
con committed
140

Roberto Raggi's avatar
Roberto Raggi committed
141
        _Literal *literal = new _Literal(chars, size);
con's avatar
con committed
142

Roberto Raggi's avatar
Roberto Raggi committed
143
        if (++_literalCount == _allocatedLiterals) {
144
145
146
147
148
            if (! _allocatedLiterals)
                _allocatedLiterals = 4;
            else
                _allocatedLiterals <<= 1;

Roberto Raggi's avatar
Roberto Raggi committed
149
150
            _literals = (_Literal **) std::realloc(_literals, sizeof(_Literal *) * _allocatedLiterals);
        }
con's avatar
con committed
151

Roberto Raggi's avatar
Roberto Raggi committed
152
        _literals[_literalCount] = literal;
con's avatar
con committed
153

154
        if (! _buckets || _literalCount * 5 >= _allocatedBuckets * 3)
Roberto Raggi's avatar
Roberto Raggi committed
155
156
157
158
159
160
            rehash();
        else {
            unsigned h = literal->hashCode() % _allocatedBuckets;
            literal->_next = _buckets[h];
            _buckets[h] = literal;
        }
con's avatar
con committed
161

Roberto Raggi's avatar
Roberto Raggi committed
162
        return literal;
con's avatar
con committed
163
164
165
166
167
168
    }

protected:
    void rehash()
    {
       if (_buckets)
169
           std::free(_buckets);
con's avatar
con committed
170

171
172
173
174
175
       if (! _allocatedBuckets)
           _allocatedBuckets = 4;
       else
           _allocatedBuckets <<= 1;

176
       _buckets = (_Literal **) std::calloc(_allocatedBuckets, sizeof(_Literal *));
con's avatar
con committed
177
178
179
180
181
182
183
184
185
186
187
188
189
190

       _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:
    _Literal **_literals;
191
    _Literal **_buckets;
con's avatar
con committed
192
193
194
195
196
    int _allocatedLiterals;
    int _literalCount;
    int _allocatedBuckets;
};

197
} // namespace CPlusPlus
Roberto Raggi's avatar
Roberto Raggi committed
198

con's avatar
con committed
199
200

#endif // CPLUSPLUS_LITERALTABLE_H