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