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
  21 #include "hash.hxx"
  22 #include "strimp.hxx"
  23 #include <osl/diagnose.h>
  24 #include <sal/macros.h>
  25
  26 struct StringHashTableImpl {
  27     sal_uInt32    nEntries;
  28     sal_uInt32    nSize;
  29     rtl_uString **pData;
  30 };
  31
  32 typedef StringHashTableImpl StringHashTable;
  33
  34 // Only for use in the implementation
  35 static StringHashTable *rtl_str_hash_new (sal_uInt32 nSize);
  36 static void rtl_str_hash_free (StringHashTable *pHash);
  37
  38 StringHashTable *
  39 getHashTable ()
  40 {
  41     static StringHashTable *pInternPool = NULL;
  42     if (pInternPool == NULL) {
  43         static StringHashTable* pHash = rtl_str_hash_new(1024);
  44         pInternPool = pHash;
  45     }
  46     return pInternPool;
  47 }
  48
  49 // Better / smaller / faster hash set ....
  50
  51 // TODO: add bottom bit-set list terminator to string list
  52
  53 static sal_uInt32
  54 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 i = 0; i < SAL_N_ELEMENTS(nPrimes); i++)
  63     {
  64         if (nPrimes[i] > nSize)
  65             return nPrimes[i];
  66     }
  67     return nSize * 2;
  68 }
  69
  70 static sal_uInt32
  71 hashString (rtl_uString *pString)
  72 {
  73     return (sal_uInt32) rtl_ustr_hashCode_WithLength (pString->buffer,
  74                                                       pString->length);
  75 }
  76
  77 static StringHashTable *
  78 rtl_str_hash_new (sal_uInt32 nSize)
  79 {
  80     StringHashTable *pHash = (StringHashTable *)malloc (sizeof (StringHashTable));
  81
  82     pHash->nEntries = 0;
  83     pHash->nSize = getNextSize (nSize);
  84     pHash->pData = (rtl_uString **) calloc (sizeof (rtl_uString *), pHash->nSize);
  85
  86     return pHash;
  87 }
  88
  89 static void
  90 rtl_str_hash_free (StringHashTable *pHash)
  91 {
  92     if (!pHash)
  93         return;
  94     if (pHash->pData)
  95         free (pHash->pData);
  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] != NULL) {
 108         n++;
 109         if (n >= pHash->nSize)
 110             n = 0;
 111     }
 112     pHash->pData[n] = pString;
 113 }
 114
 115 static void
 116 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] != NULL)
 129             rtl_str_hash_insert_nonequal (pNewHash, pHash->pData[i]);
 130     }
 131     pNewHash->nEntries = pHash->nEntries;
 132     free (pHash->pData);
 133     *pHash = *pNewHash;
 134     pNewHash->pData = NULL;
 135     rtl_str_hash_free (pNewHash);
 136 }
 137
 138 static int
 139 compareEqual (rtl_uString *pStringA, rtl_uString *pStringB)
 140 {
 141     if (pStringA == pStringB)
 142         return 1;
 143     if (pStringA->length != pStringB->length)
 144         return 0;
 145     return !rtl_ustr_compare_WithLength( pStringA->buffer, pStringA->length,
 146                                          pStringB->buffer, pStringB->length);
 147 }
 148
 149
 150 rtl_uString *
 151 rtl_str_hash_intern (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]) != NULL) {
 166         if (compareEqual (pHashStr, pString))
 167         {
 168             rtl_uString_acquire (pHashStr);
 169             return pHashStr;
 170         }
 171         n++;
 172         if (n >= pHash->nSize)
 173             n = 0;
 174     }
 175
 176     if (!can_return)
 177     {
 178         rtl_uString *pCopy = NULL;
 179         rtl_uString_newFromString( &pCopy, pString );
 180         pString = pCopy;
 181         if (!pString)
 182             return NULL;
 183     }
 184
 185     if (!SAL_STRING_IS_STATIC (pString))
 186         pString->refCount |= SAL_STRING_INTERN_FLAG;
 187     pHash->pData[n] = pString;
 188     pHash->nEntries++;
 189
 190     return pString;
 191 }
 192
 193 void
 194 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]) != NULL) {
 204         if (compareEqual (pHashStr, pString))
 205             break;
 206         n++;
 207         if (n >= pHash->nSize)
 208             n = 0;
 209     }
 210     OSL_ASSERT (pHash->pData[n] != 0);
 211     if (pHash->pData[n] == NULL)
 212         return;
 213
 214     pHash->pData[n++] = NULL;
 215     pHash->nEntries--;
 216
 217     if (n >= pHash->nSize)
 218         n = 0;
 219
 220     while ((pHashStr = pHash->pData[n]) != NULL) {
 221         pHash->pData[n] = NULL;
 222         // FIXME: rather unsophisticated and N^2 in chain-length, but robust.
 223         rtl_str_hash_insert_nonequal (pHash, pHashStr);
 224         n++;
 225         if (n >= pHash->nSize)
 226             n = 0;
 227     }
 228     // FIXME: Should we down-size ?
 229 }
 230
 231 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */