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 = nullptr;
  44     if (!pInternPool)
  45     {
  46         static StringHashTable* pHash = rtl_str_hash_new(1024);
  47         pInternPool = pHash;
  48     }
  49     return pInternPool;
  50 }
  51
  52 // Better / smaller / faster hash set ....
  53
  54 // TODO: add bottom bit-set list terminator to string list
  55
  56 static sal_uInt32 getNextSize(sal_uInt32 nSize)
  57 {
  58     // Sedgewick - Algorithms in C P577.
  59     static const sal_uInt32 nPrimes[] = { 1021, 2039, 4093, 8191, 16381, 32749,
  60                                           65521, 131071,262139, 524287, 1048573,
  61                                           2097143, 4194301, 8388593, 16777213,
  62                                           33554393, 67108859, 134217689 };
  63
  64     for (sal_uInt32 nPrime : nPrimes)
  65     {
  66         if (nPrime > nSize)
  67             return nPrime;
  68     }
  69     return nSize * 2;
  70 }
  71
  72 static sal_uInt32 hashString(rtl_uString *pString)
  73 {
  74     return static_cast<sal_uInt32>(rtl_ustr_hashCode_WithLength(pString->buffer,
  75                                                      pString->length));
  76 }
  77
  78 static StringHashTable * rtl_str_hash_new(sal_uInt32 nSize)
  79 {
  80     StringHashTable *pHash = static_cast<StringHashTable *>(malloc(sizeof(StringHashTable)));
  81
  82     pHash->nEntries = 0;
  83     pHash->nSize = getNextSize (nSize);
  84     pHash->pData = static_cast< rtl_uString ** >(calloc(sizeof(rtl_uString *), pHash->nSize));
  85
  86     return pHash;
  87 }
  88
  89 static void rtl_str_hash_free(StringHashTable *pHash)
  90 {
  91     if (!pHash)
  92         return;
  93
  94     if (pHash->pData)
  95         free(pHash->pData);
  96
  97     free(pHash);
  98 }
  99
 100 static void
 101 rtl_str_hash_insert_nonequal(StringHashTable   *pHash,
 102                              rtl_uString       *pString)
 103 {
 104     sal_uInt32 nHash = hashString(pString);
 105     sal_uInt32 n;
 106
 107     n = nHash % pHash->nSize;
 108     while (pHash->pData[n])
 109     {
 110         n++;
 111         if (n >= pHash->nSize)
 112             n = 0;
 113     }
 114     pHash->pData[n] = pString;
 115 }
 116
 117 static void rtl_str_hash_resize(sal_uInt32 nNewSize)
 118 {
 119     sal_uInt32 i;
 120     StringHashTable *pNewHash;
 121     StringHashTable *pHash = getHashTable();
 122
 123     OSL_ASSERT(nNewSize > pHash->nEntries);
 124
 125     pNewHash = rtl_str_hash_new(nNewSize);
 126
 127     for (i = 0; i < pHash->nSize; i++)
 128     {
 129         if (pHash->pData[i])
 130             rtl_str_hash_insert_nonequal(pNewHash, pHash->pData[i]);
 131     }
 132
 133     pNewHash->nEntries = pHash->nEntries;
 134     free(pHash->pData);
 135     *pHash = *pNewHash;
 136     pNewHash->pData = nullptr;
 137     rtl_str_hash_free(pNewHash);
 138 }
 139
 140 static bool compareEqual(rtl_uString *pStringA, rtl_uString *pStringB)
 141 {
 142     if (pStringA == pStringB)
 143         return true;
 144
 145     if (pStringA->length != pStringB->length)
 146         return false;
 147
 148     return !rtl_ustr_compare_WithLength( pStringA->buffer, pStringA->length,
 149                                          pStringB->buffer, pStringB->length);
 150 }
 151
 152 rtl_uString * rtl_str_hash_intern (
 153                 rtl_uString *pString,
 154                 int         can_return)
 155 {
 156     sal_uInt32 nHash = hashString(pString);
 157     sal_uInt32 n;
 158     rtl_uString *pHashStr;
 159
 160     StringHashTable *pHash = getHashTable();
 161
 162     // Should we resize ?
 163     if (pHash->nEntries >= pHash->nSize/2)
 164         rtl_str_hash_resize(getNextSize(pHash->nSize));
 165
 166     n = nHash % pHash->nSize;
 167     while ((pHashStr = pHash->pData[n]))
 168     {
 169         if (compareEqual(pHashStr, pString))
 170         {
 171             rtl_uString_acquire(pHashStr);
 172             return pHashStr;
 173         }
 174
 175         n++;
 176         if (n >= pHash->nSize)
 177             n = 0;
 178     }
 179
 180     if (!can_return)
 181     {
 182         rtl_uString *pCopy = nullptr;
 183         rtl_uString_newFromString( &pCopy, pString );
 184         pString = pCopy;
 185
 186         if (!pString)
 187             return nullptr;
 188     }
 189
 190     if (!SAL_STRING_IS_STATIC(pString))
 191         pString->refCount |= SAL_STRING_INTERN_FLAG;
 192
 193     pHash->pData[n] = pString;
 194     pHash->nEntries++;
 195
 196     return pString;
 197 }
 198
 199 void rtl_str_hash_remove(rtl_uString *pString)
 200 {
 201     sal_uInt32 n;
 202     sal_uInt32 nHash = hashString(pString);
 203     rtl_uString *pHashStr;
 204
 205     StringHashTable *pHash = getHashTable();
 206
 207     n = nHash % pHash->nSize;
 208     while ((pHashStr = pHash->pData[n]))
 209     {
 210         if (compareEqual(pHashStr, pString))
 211             break;
 212
 213         n++;
 214
 215         if (n >= pHash->nSize)
 216             n = 0;
 217     }
 218
 219     OSL_ASSERT(pHash->pData[n]);
 220     if (!pHash->pData[n])
 221         return;
 222
 223     pHash->pData[n++] = nullptr;
 224     pHash->nEntries--;
 225
 226     if (n >= pHash->nSize)
 227         n = 0;
 228
 229     while ((pHashStr = pHash->pData[n]))
 230     {
 231         pHash->pData[n] = nullptr;
 232         // FIXME: rather unsophisticated and N^2 in chain-length, but robust.
 233         rtl_str_hash_insert_nonequal(pHash, pHashStr);
 234         n++;
 235
 236         if (n >= pHash->nSize)
 237             n = 0;
 238     }
 239     // FIXME: Should we down-size ?
 240 }
 241
 242 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */