src/shared/cplusplus/LiteralTable.h

   1 /**************************************************************************
   2 **
   3 ** This file is part of Qt Creator
   4 **
   5 ** Copyright (c) 2011 Nokia Corporation and/or its subsidiary(-ies).
   6 **
   7 ** Contact: Nokia Corporation (qt-info@nokia.com)
   8 **
   9 ** No Commercial Usage
  10 **
  11 ** This file contains pre-release code and may not be distributed.
  12 ** You may use this file in accordance with the terms and conditions
  13 ** contained in the Technology Preview License Agreement accompanying
  14 ** this package.
  15 **
  16 ** GNU Lesser General Public License Usage
  17 **
  18 ** Alternatively, this file may be used under the terms of the GNU Lesser
  19 ** General Public License version 2.1 as published by the Free Software
  20 ** Foundation and appearing in the file LICENSE.LGPL included in the
  21 ** packaging of this file.  Please review the following information to
  22 ** ensure the GNU Lesser General Public License version 2.1 requirements
  23 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  24 **
  25 ** In addition, as a special exception, Nokia gives you certain additional
  26 ** rights.  These rights are described in the Nokia Qt LGPL Exception
  27 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  28 **
  29 ** If you have questions regarding the use of this file, please contact
  30 ** Nokia at qt-info@nokia.com.
  31 **
  32 **************************************************************************/
  33 // Copyright (c) 2008 Roberto Raggi <roberto.raggi@gmail.com>
  34 //
  35 // Permission is hereby granted, free of charge, to any person obtaining a copy
  36 // of this software and associated documentation files (the "Software"), to deal
  37 // in the Software without restriction, including without limitation the rights
  38 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  39 // copies of the Software, and to permit persons to whom the Software is
  40 // furnished to do so, subject to the following conditions:
  41 //
  42 // The above copyright notice and this permission notice shall be included in
  43 // all copies or substantial portions of the Software.
  44 //
  45 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  46 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  47 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  48 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  49 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  50 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  51 // THE SOFTWARE.
  52
  53 #ifndef CPLUSPLUS_LITERALTABLE_H
  54 #define CPLUSPLUS_LITERALTABLE_H
  55
  56 #include "CPlusPlusForwardDeclarations.h"
  57 #include <cstring>
  58
  59 namespace CPlusPlus {
  60
  61 template <typename _Literal>
  62 class LiteralTable
  63 {
  64     LiteralTable(const LiteralTable &other);
  65     void operator =(const LiteralTable &other);
  66
  67 public:
  68     typedef _Literal *const *iterator;
  69
  70 public:
  71     LiteralTable()
  72        : _literals(0),
  73          _buckets(0),
  74          _allocatedLiterals(0),
  75          _literalCount(-1),
  76          _allocatedBuckets(0)
  77     { }
  78
  79     ~LiteralTable()
  80     {
  81         reset();
  82     }
  83
  84     void reset()
  85     {
  86         if (_literals) {
  87             _Literal **lastLiteral = _literals + _literalCount + 1;
  88             for (_Literal **it = _literals; it != lastLiteral; ++it)
  89                 delete *it;
  90             std::free(_literals);
  91         }
  92         if (_buckets)
  93             std::free(_buckets);
  94
  95         _literals = 0;
  96         _buckets = 0;
  97         _allocatedLiterals = 0;
  98         _literalCount = -1;
  99         _allocatedBuckets = 0;
 100     }
 101
 102     bool empty() const
 103     { return _literalCount == -1; }
 104
 105     unsigned size() const
 106     { return _literalCount + 1; }
 107
 108     const _Literal *at(unsigned index) const
 109     { return _literals[index]; }
 110
 111     iterator begin() const
 112     { return _literals; }
 113
 114     iterator end() const
 115     { return _literals + _literalCount + 1; }
 116
 117     const _Literal *findLiteral(const char *chars, unsigned size) const
 118     {
 119         if (_buckets) {
 120             unsigned h = _Literal::hashCode(chars, size);
 121             _Literal *literal = _buckets[h % _allocatedBuckets];
 122             for (; literal; literal = static_cast<_Literal *>(literal->_next)) {
 123                 if (literal->size() == size && ! std::strncmp(literal->chars(), chars, size))
 124                     return literal;
 125             }
 126         }
 127
 128         return 0;
 129     }
 130
 131     const _Literal *findOrInsertLiteral(const char *chars, unsigned size)
 132     {
 133         if (_buckets) {
 134             unsigned h = _Literal::hashCode(chars, size);
 135             _Literal *literal = _buckets[h % _allocatedBuckets];
 136             for (; literal; literal = static_cast<_Literal *>(literal->_next)) {
 137                 if (literal->size() == size && ! std::strncmp(literal->chars(), chars, size))
 138                     return literal;
 139             }
 140         }
 141
 142         _Literal *literal = new _Literal(chars, size);
 143
 144         if (++_literalCount == _allocatedLiterals) {
 145             if (! _allocatedLiterals)
 146                 _allocatedLiterals = 4;
 147             else
 148                 _allocatedLiterals <<= 1;
 149
 150             _literals = (_Literal **) std::realloc(_literals, sizeof(_Literal *) * _allocatedLiterals);
 151         }
 152
 153         _literals[_literalCount] = literal;
 154
 155         if (! _buckets || _literalCount * 5 >= _allocatedBuckets * 3)
 156             rehash();
 157         else {
 158             unsigned h = literal->hashCode() % _allocatedBuckets;
 159             literal->_next = _buckets[h];
 160             _buckets[h] = literal;
 161         }
 162
 163         return literal;
 164     }
 165
 166 protected:
 167     void rehash()
 168     {
 169        if (_buckets)
 170            std::free(_buckets);
 171
 172        if (! _allocatedBuckets)
 173            _allocatedBuckets = 4;
 174        else
 175            _allocatedBuckets <<= 1;
 176
 177        _buckets = (_Literal **) std::calloc(_allocatedBuckets, sizeof(_Literal *));
 178
 179        _Literal **lastLiteral = _literals + (_literalCount + 1);
 180
 181        for (_Literal **it = _literals; it != lastLiteral; ++it) {
 182            _Literal *literal = *it;
 183            unsigned h = literal->hashCode() % _allocatedBuckets;
 184
 185            literal->_next = _buckets[h];
 186            _buckets[h] = literal;
 187        }
 188     }
 189
 190 protected:
 191     _Literal **_literals;
 192     _Literal **_buckets;
 193     int _allocatedLiterals;
 194     int _literalCount;
 195     int _allocatedBuckets;
 196 };
 197
 198 } // namespace CPlusPlus
 199
 200
 201 #endif // CPLUSPLUS_LITERALTABLE_H