sal/rtl/hash.cxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * This file is part of the LibreOffice project.
   4  *
   5  * This Source Code Form is subject to the terms of the Mozilla Public
   6  * License, v. 2.0. If a copy of the MPL was not distributed with this
   7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
   8  *
   9  * This file incorporates work covered by the following license notice:
  10  *
  11  *   Licensed to the Apache Software Foundation (ASF) under one or more
  12  *   contributor license agreements. See the NOTICE file distributed
  13  *   with this work for additional information regarding copyright
  14  *   ownership. The ASF licenses this file to you under the Apache
  15  *   License, Version 2.0 (the "License"); you may not use this file
  16  *   except in compliance with the License. You may obtain a copy of
  17  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
  18  */
  19
  20 #include <sal/config.h>
  21
  22 #include <stdlib.h>
  23
  24 #include "hash.hxx"
  25 #include "strimp.hxx"
  26 #include <osl/diagnose.h>
  27 #include <sal/macros.h>
  28
  29 struct StringHashTableImpl {
  30     sal_uInt32    nEntries;
  31     sal_uInt32    nSize;
  32     rtl_uString **pData;
  33 };
  34
  35 typedef StringHashTableImpl StringHashTable;
  36
  37 // Only for use in the implementation
  38 static StringHashTable *rtl_str_hash_new(sal_uInt32 nSize);
  39 static void rtl_str_hash_free(StringHashTable *pHash);
  40
  41 static StringHashTable * getHashTable()
  42 {
  43     static StringHashTable* pInternPool = rtl_str_hash_new(1024);
  44     return pInternPool;
  45 }
  46
  47 // Better / smaller / faster hash set...
  48
  49 // TODO: add bottom bit-set list terminator to string list
  50
  51 static sal_uInt32 getNextSize(sal_uInt32 nSize)
  52 {
  53     // Sedgewick - Algorithms in C P577.
  54     static const sal_uInt32 nPrimes[] = { 1021, 2039, 4093, 8191, 16381, 32749,
  55                                           65521, 131071,262139, 524287, 1048573,
  56                                           2097143, 4194301, 8388593, 16777213,
  57                                           33554393, 67108859, 134217689 };
  58
  59     for (sal_uInt32 nPrime : nPrimes)
  60     {
  61         if (nPrime > nSize)
  62             return nPrime;
  63     }
  64     return nSize * 2;
  65 }
  66
  67 static sal_uInt32 hashString(rtl_uString *pString)
  68 {
  69     return static_cast<sal_uInt32>(rtl_ustr_hashCode_WithLength(pString->buffer,
  70                                                      pString->length));
  71 }
  72
  73 static StringHashTable * rtl_str_hash_new(sal_uInt32 nSize)
  74 {
  75     StringHashTable *pHash = static_cast<StringHashTable *>(malloc(sizeof(StringHashTable)));
  76
  77     pHash->nEntries = 0;
  78     pHash->nSize = getNextSize (nSize);
  79     pHash->pData = static_cast< rtl_uString ** >(calloc(sizeof(rtl_uString *), pHash->nSize));
  80
  81     return pHash;
  82 }
  83
  84 static void rtl_str_hash_free(StringHashTable *pHash)
  85 {
  86     if (!pHash)
  87         return;
  88
  89     if (pHash->pData)
  90         free(pHash->pData);
  91
  92     free(pHash);
  93 }
  94
  95 static void
  96 rtl_str_hash_insert_nonequal(StringHashTable   *pHash,
  97                              rtl_uString       *pString)
  98 {
  99     sal_uInt32 nHash = hashString(pString);
 100     sal_uInt32 n;
 101
 102     n = nHash % pHash->nSize;
 103     while (pHash->pData[n])
 104     {
 105         n++;
 106         if (n >= pHash->nSize)
 107             n = 0;
 108     }
 109     pHash->pData[n] = pString;
 110 }
 111
 112 static void rtl_str_hash_resize(sal_uInt32 nNewSize)
 113 {
 114     sal_uInt32 i;
 115     StringHashTable *pNewHash;
 116     StringHashTable *pHash = getHashTable();
 117
 118     OSL_ASSERT(nNewSize > pHash->nEntries);
 119
 120     pNewHash = rtl_str_hash_new(nNewSize);
 121
 122     for (i = 0; i < pHash->nSize; i++)
 123     {
 124         if (pHash->pData[i])
 125             rtl_str_hash_insert_nonequal(pNewHash, pHash->pData[i]);
 126     }
 127
 128     pNewHash->nEntries = pHash->nEntries;
 129     free(pHash->pData);
 130     *pHash = *pNewHash;
 131     pNewHash->pData = nullptr;
 132     rtl_str_hash_free(pNewHash);
 133 }
 134
 135 static bool compareEqual(rtl_uString *pStringA, rtl_uString *pStringB)
 136 {
 137     if (pStringA == pStringB)
 138         return true;
 139
 140     if (pStringA->length != pStringB->length)
 141         return false;
 142
 143     return !rtl_ustr_compare_WithLength( pStringA->buffer, pStringA->length,
 144                                          pStringB->buffer, pStringB->length);
 145 }
 146
 147 rtl_uString * rtl_str_hash_intern (
 148                 rtl_uString *pString,
 149                 int         can_return)
 150 {
 151     sal_uInt32 nHash = hashString(pString);
 152     sal_uInt32 n;
 153     rtl_uString *pHashStr;
 154
 155     StringHashTable *pHash = getHashTable();
 156
 157     // Should we resize ?
 158     if (pHash->nEntries >= pHash->nSize/2)
 159         rtl_str_hash_resize(getNextSize(pHash->nSize));
 160
 161     n = nHash % pHash->nSize;
 162     while ((pHashStr = pHash->pData[n]))
 163     {
 164         if (compareEqual(pHashStr, pString))
 165         {
 166             rtl_uString_acquire(pHashStr);
 167             return pHashStr;
 168         }
 169
 170         n++;
 171         if (n >= pHash->nSize)
 172             n = 0;
 173     }
 174
 175     if (!can_return)
 176     {
 177         rtl_uString *pCopy = nullptr;
 178         rtl_uString_newFromString( &pCopy, pString );
 179         pString = pCopy;
 180
 181         if (!pString)
 182             return nullptr;
 183     }
 184
 185     if (!SAL_STRING_IS_STATIC(pString))
 186         pString->refCount |= SAL_STRING_INTERN_FLAG;
 187
 188     pHash->pData[n] = pString;
 189     pHash->nEntries++;
 190
 191     return pString;
 192 }
 193
 194 void rtl_str_hash_remove(rtl_uString *pString)
 195 {
 196     sal_uInt32 n;
 197     sal_uInt32 nHash = hashString(pString);
 198     rtl_uString *pHashStr;
 199
 200     StringHashTable *pHash = getHashTable();
 201
 202     n = nHash % pHash->nSize;
 203     while ((pHashStr = pHash->pData[n]))
 204     {
 205         if (compareEqual(pHashStr, pString))
 206             break;
 207
 208         n++;
 209
 210         if (n >= pHash->nSize)
 211             n = 0;
 212     }
 213
 214     OSL_ASSERT(pHash->pData[n]);
 215     if (!pHash->pData[n])
 216         return;
 217
 218     pHash->pData[n++] = nullptr;
 219     pHash->nEntries--;
 220
 221     if (n >= pHash->nSize)
 222         n = 0;
 223
 224     while ((pHashStr = pHash->pData[n]))
 225     {
 226         pHash->pData[n] = nullptr;
 227         // FIXME: rather unsophisticated and N^2 in chain-length, but robust.
 228         rtl_str_hash_insert_nonequal(pHash, pHashStr);
 229         n++;
 230
 231         if (n >= pHash->nSize)
 232             n = 0;
 233     }
 234     // FIXME: Should we down-size ?
 235 }
 236
 237 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */