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