sal/rtl/source/hash.cxx

   1 /*************************************************************************
   2  *
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * Copyright 2008 by Sun Microsystems, Inc.
   6  *
   7  * OpenOffice.org - a multi-platform office productivity suite
   8  *
   9  * $RCSfile: hash.cxx,v $
  10  * $Revision: 1.5 $
  11  *
  12  * This file is part of OpenOffice.org.
  13  *
  14  * OpenOffice.org is free software: you can redistribute it and/or modify
  15  * it under the terms of the GNU Lesser General Public License version 3
  16  * only, as published by the Free Software Foundation.
  17  *
  18  * OpenOffice.org is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU Lesser General Public License version 3 for more details
  22  * (a copy is included in the LICENSE file that accompanied this code).
  23  *
  24  * You should have received a copy of the GNU Lesser General Public License
  25  * version 3 along with OpenOffice.org.  If not, see
  26  * <http://www.openoffice.org/license.html>
  27  * for a copy of the LGPLv3 License.
  28  *
  29  ************************************************************************/
  30
  31 // MARKER(update_precomp.py): autogen include statement, do not remove
  32 // #include "precompiled_sal.hxx"
  33
  34 #include "hash.h"
  35 #include "strimp.h"
  36 #include <osl/diagnose.h>
  37
  38 #if 0
  39
  40 #include "rtl/allocator.hxx"
  41
  42 #include <hash_set>
  43
  44 namespace {
  45     struct UStringHash
  46     {
  47         size_t operator()(rtl_uString * const &rString) const
  48             { return (size_t)rtl_ustr_hashCode_WithLength( rString->buffer, rString->length ); }
  49     };
  50     struct UStringEqual
  51     {
  52         sal_Bool operator() ( rtl_uString * const &pStringA,
  53                               rtl_uString * const &pStringB) const
  54         {
  55             if (pStringA == pStringB)
  56                 return true;
  57             if (pStringA->length != pStringB->length)
  58                 return false;
  59             return !rtl_ustr_compare_WithLength( pStringA->buffer, pStringA->length,
  60                                                  pStringB->buffer, pStringB->length);
  61         }
  62     };
  63 }
  64
  65 typedef std::hash_set< rtl_uString *, UStringHash, UStringEqual,
  66                        rtl::Allocator<rtl_uString *> > UniqueHash;
  67
  68 struct StringHashTableImpl : public UniqueHash
  69 {
  70     StringHashTableImpl(sal_uInt32 nSize) : UniqueHash( nSize ) {}
  71 };
  72
  73 StringHashTable *
  74 rtl_str_hash_new (sal_uInt32 nSize)
  75 {
  76     return new StringHashTableImpl (nSize);
  77 }
  78
  79 void
  80 rtl_str_hash_free (StringHashTable *pHash)
  81 {
  82     delete pHash;
  83 }
  84
  85 rtl_uString *
  86 rtl_str_hash_intern (StringHashTable   *pHash,
  87                      rtl_uString       *pString,
  88                      int                can_return)
  89 {
  90     UniqueHash::iterator aIter;
  91     aIter = pHash->find(pString);
  92     if (aIter != pHash->end())
  93     {
  94         rtl_uString *pHashStr = *aIter;
  95         rtl_uString_acquire (pHashStr);
  96         return pHashStr;
  97     }
  98     if (!can_return)
  99     {
 100         rtl_uString *pCopy = NULL;
 101         rtl_uString_newFromString( &pCopy, pString );
 102         pString = pCopy;
 103         if (!pString)
 104             return NULL;
 105     }
 106
 107     if (!SAL_STRING_IS_STATIC (pString))
 108         pString->refCount |= SAL_STRING_INTERN_FLAG;
 109     pHash->insert(pString);
 110
 111     return pString;
 112 }
 113
 114 void
 115 rtl_str_hash_remove (StringHashTable   *pHash,
 116                      rtl_uString       *pString)
 117 {
 118     pHash->erase(pString);
 119 }
 120
 121 #else
 122
 123 // --------------------------- start here ---------------------------
 124
 125 struct StringHashTableImpl {
 126     sal_uInt32    nEntries;
 127     sal_uInt32    nSize;
 128     rtl_uString **pData;
 129 };
 130
 131 // Better / smaller / faster hash set ....
 132
 133 // TODO: add bottom bit-set list terminator to string list
 134
 135 static sal_uInt32
 136 getNextSize (sal_uInt32 nSize)
 137 {
 138     // Sedgewick - Algorithms in C P577.
 139     static const sal_uInt32 nPrimes[] = { 1021, 2039, 4093, 8191, 16381, 32749,
 140                                           65521, 131071,262139, 524287, 1048573,
 141                                           2097143, 4194301, 8388593, 16777213,
 142                                           33554393, 67108859, 134217689 };
 143     #define NUM_PRIMES (sizeof (nPrimes)/ sizeof (nPrimes[0]))
 144     for (int i = 0; i < NUM_PRIMES; i++)
 145     {
 146         if (nPrimes[i] > nSize)
 147             return nPrimes[i];
 148     }
 149     return nSize * 2;
 150 }
 151
 152 static sal_uInt32
 153 hashString (rtl_uString *pString)
 154 {
 155     return (sal_uInt32) rtl_ustr_hashCode_WithLength (pString->buffer,
 156                                                       pString->length);
 157 }
 158
 159 StringHashTable *
 160 rtl_str_hash_new (sal_uInt32 nSize)
 161 {
 162     StringHashTable *pHash = (StringHashTable *)malloc (sizeof (StringHashTable));
 163
 164     pHash->nEntries = 0;
 165     pHash->nSize = getNextSize (nSize);
 166     pHash->pData = (rtl_uString **) calloc (sizeof (rtl_uString *), pHash->nSize);
 167
 168     return pHash;
 169 }
 170
 171 static void
 172 rtl_str_hash_insert_nonequal (StringHashTable   *pHash,
 173                               rtl_uString       *pString)
 174 {
 175     sal_uInt32  nHash = hashString (pString);
 176     sal_uInt32  n;
 177     rtl_uString *pHashStr;
 178
 179     n = nHash % pHash->nSize;
 180     while ((pHashStr = pHash->pData[n]) != NULL) {
 181         n++;
 182         if (n >= pHash->nSize)
 183             n = 0;
 184     }
 185     pHash->pData[n] = pString;
 186 }
 187
 188 static void
 189 rtl_str_hash_resize (StringHashTable  *pHash,
 190                      sal_uInt32        nNewSize)
 191 {
 192     sal_uInt32 i;
 193     StringHashTable *pNewHash;
 194
 195     OSL_ASSERT (nNewSize > pHash->nEntries);
 196
 197     pNewHash = rtl_str_hash_new (nNewSize);
 198
 199     for (i = 0; i < pHash->nSize; i++)
 200     {
 201         if (pHash->pData[i] != NULL)
 202             rtl_str_hash_insert_nonequal (pNewHash, pHash->pData[i]);
 203     }
 204     pNewHash->nEntries = pHash->nEntries;
 205     free (pHash->pData);
 206     *pHash = *pNewHash;
 207     pNewHash->pData = NULL;
 208     rtl_str_hash_free (pNewHash);
 209 }
 210
 211 void
 212 rtl_str_hash_free (StringHashTable *pHash)
 213 {
 214     if (!pHash)
 215         return;
 216     if (pHash->pData)
 217         free (pHash->pData);
 218     free (pHash);
 219 }
 220
 221 static int
 222 compareEqual (rtl_uString *pStringA, rtl_uString *pStringB)
 223 {
 224     if (pStringA == pStringB)
 225         return 1;
 226     if (pStringA->length != pStringB->length)
 227         return 0;
 228     return !rtl_ustr_compare_WithLength( pStringA->buffer, pStringA->length,
 229                                          pStringB->buffer, pStringB->length);
 230 }
 231
 232 rtl_uString *
 233 rtl_str_hash_intern (StringHashTable   *pHash,
 234                      rtl_uString       *pString,
 235                      int                can_return)
 236 {
 237     sal_uInt32  nHash = hashString (pString);
 238     sal_uInt32  n;
 239     rtl_uString *pHashStr;
 240
 241     // Should we resize ?
 242     if (pHash->nEntries >= pHash->nSize/2)
 243         rtl_str_hash_resize (pHash, getNextSize(pHash->nSize));
 244
 245     n = nHash % pHash->nSize;
 246     while ((pHashStr = pHash->pData[n]) != NULL) {
 247         if (compareEqual (pHashStr, pString))
 248         {
 249             rtl_uString_acquire (pHashStr);
 250             return pHashStr;
 251         }
 252         n++;
 253         if (n >= pHash->nSize)
 254             n = 0;
 255     }
 256
 257     if (!can_return)
 258     {
 259         rtl_uString *pCopy = NULL;
 260         rtl_uString_newFromString( &pCopy, pString );
 261         pString = pCopy;
 262         if (!pString)
 263             return NULL;
 264     }
 265
 266     if (!SAL_STRING_IS_STATIC (pString))
 267         pString->refCount |= SAL_STRING_INTERN_FLAG;
 268     pHash->pData[n] = pString;
 269     pHash->nEntries++;
 270
 271     return pString;
 272 }
 273
 274 void
 275 rtl_str_hash_remove (StringHashTable   *pHash,
 276                      rtl_uString       *pString)
 277 {
 278     sal_uInt32   n;
 279     sal_uInt32   nHash = hashString (pString);
 280     rtl_uString *pHashStr;
 281
 282     n = nHash % pHash->nSize;
 283     while ((pHashStr = pHash->pData[n]) != NULL) {
 284         if (compareEqual (pHashStr, pString))
 285             break;
 286         n++;
 287         if (n >= pHash->nSize)
 288             n = 0;
 289     }
 290     OSL_ASSERT (pHash->pData[n] != 0);
 291     if (pHash->pData[n] == NULL)
 292         return;
 293
 294     pHash->pData[n++] = NULL;
 295     pHash->nEntries--;
 296
 297     if (n >= pHash->nSize)
 298         n = 0;
 299
 300     while ((pHashStr = pHash->pData[n]) != NULL) {
 301         pHash->pData[n] = NULL;
 302         // FIXME: rather unsophisticated and N^2 in chain-length, but robust.
 303         rtl_str_hash_insert_nonequal (pHash, pHashStr);
 304         n++;
 305         if (n >= pHash->nSize)
 306             n = 0;
 307     }
 308     // FIXME: Should we down-size ?
 309 }
 310
 311 #endif