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