1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the Qt Mobility Components.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    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 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 // Copyright (c) 2008 Roberto Raggi <roberto.raggi@gmail.com>

    42 //

    43 // Permission is hereby granted, free of charge, to any person obtaining a copy

    44 // of this software and associated documentation files (the "Software"), to deal

    45 // in the Software without restriction, including without limitation the rights

    46 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell

    47 // copies of the Software, and to permit persons to whom the Software is

    48 // furnished to do so, subject to the following conditions:

    49 //

    50 // The above copyright notice and this permission notice shall be included in

    51 // all copies or substantial portions of the Software.

    52 //

    53 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

    54 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

    55 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

    56 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

    57 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,

    58 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN

    59 // THE SOFTWARE.

    60 

    61 #ifndef CPLUSPLUS_LITERALTABLE_H

    62 #define CPLUSPLUS_LITERALTABLE_H

    63 

    64 #include "CPlusPlusForwardDeclarations.h"

    65 #include <cstring>

    66 

    67 namespace CPlusPlus {

    68 

    69 template <typename _Literal>

    70 class LiteralTable

    71 {

    72     LiteralTable(const LiteralTable &other);

    73     void operator =(const LiteralTable &other);

    74 

    75 public:

    76     typedef _Literal *const *iterator;

    77 

    78 public:

    79     LiteralTable()

    80        : _literals(0),

    81          _allocatedLiterals(0),

    82          _literalCount(-1),

    83          _buckets(0),

    84          _allocatedBuckets(0)

    85     { }

    86 

    87     ~LiteralTable()

    88     {

    89         if (_literals) {

    90             _Literal **lastLiteral = _literals + _literalCount + 1;

    91             for (_Literal **it = _literals; it != lastLiteral; ++it)

    92                 delete *it;

    93             std::free(_literals);

    94         }

    95         if (_buckets)

    96             std::free(_buckets);

    97     }

    98 

    99     bool empty() const

   100     { return _literalCount == -1; }

   101 

   102     unsigned size() const

   103     { return _literalCount + 1; }

   104 

   105     const _Literal *at(unsigned index) const

   106     { return _literals[index]; }

   107 

   108     iterator begin() const

   109     { return _literals; }

   110 

   111     iterator end() const

   112     { return _literals + _literalCount + 1; }

   113 

   114     const _Literal *findLiteral(const char *chars, unsigned size) const

   115     {

   116         if (_buckets) {

   117             unsigned h = _Literal::hashCode(chars, size);

   118             _Literal *literal = _buckets[h % _allocatedBuckets];

   119             for (; literal; literal = static_cast<_Literal *>(literal->_next)) {

   120                 if (literal->size() == size && ! std::strncmp(literal->chars(), chars, size))

   121                     return literal;

   122             }

   123         }

   124 

   125         return 0;

   126     }

   127 

   128     const _Literal *findOrInsertLiteral(const char *chars, unsigned size)

   129     {

   130         if (_buckets) {

   131             unsigned h = _Literal::hashCode(chars, size);

   132             _Literal *literal = _buckets[h % _allocatedBuckets];

   133             for (; literal; literal = static_cast<_Literal *>(literal->_next)) {

   134                 if (literal->size() == size && ! std::strncmp(literal->chars(), chars, size))

   135                     return literal;

   136             }

   137         }

   138 

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

   140 

   141         if (++_literalCount == _allocatedLiterals) {

   142             _allocatedLiterals <<= 1;

   143 

   144             if (! _allocatedLiterals)

   145                 _allocatedLiterals = 256;

   146 

   147             _literals = (_Literal **) std::realloc(_literals, sizeof(_Literal *) * _allocatedLiterals);

   148         }

   149 

   150         _literals[_literalCount] = literal;

   151 

   152         if (! _buckets || _literalCount >= _allocatedBuckets * .6)

   153             rehash();

   154         else {

   155             unsigned h = literal->hashCode() % _allocatedBuckets;

   156             literal->_next = _buckets[h];

   157             _buckets[h] = literal;

   158         }

   159 

   160         return literal;

   161     }

   162 

   163 protected:

   164     void rehash()

   165     {

   166        if (_buckets)

   167            std::free(_buckets);

   168 

   169        _allocatedBuckets <<= 1;

   170 

   171        if (! _allocatedBuckets)

   172            _allocatedBuckets = 256;

   173 

   174        _buckets = (_Literal **) std::calloc(_allocatedBuckets, sizeof(_Literal *));

   175 

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

   177 

   178        for (_Literal **it = _literals; it != lastLiteral; ++it) {

   179            _Literal *literal = *it;

   180            unsigned h = literal->hashCode() % _allocatedBuckets;

   181 

   182            literal->_next = _buckets[h];

   183            _buckets[h] = literal;

   184        }

   185     }

   186 

   187 protected:

   188     _Literal **_literals;

   189     int _allocatedLiterals;

   190     int _literalCount;

   191 

   192     _Literal **_buckets;

   193     int _allocatedBuckets;

   194 };

   195 

   196 } // end of namespace CPlusPlus

   197 

   198 

   199 #endif // CPLUSPLUS_LITERALTABLE_H