LCOV - code coverage report
Current view: top level - sal/rtl - hash.cxx (source / functions) Hit Total Coverage
Test: commit e02a6cb2c3e2b23b203b422e4e0680877f232636 Lines: 0 97 0.0 %
Date: 2014-04-14 Functions: 0 10 0.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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           0 : getHashTable ()
      39             : {
      40             :     static StringHashTable *pInternPool = NULL;
      41           0 :     if (pInternPool == NULL) {
      42           0 :         static StringHashTable* pHash = rtl_str_hash_new(1024);
      43           0 :         pInternPool = pHash;
      44             :     }
      45           0 :     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           0 : 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           0 :     for (sal_uInt32 i = 0; i < SAL_N_ELEMENTS(nPrimes); i++)
      62             :     {
      63           0 :         if (nPrimes[i] > nSize)
      64           0 :             return nPrimes[i];
      65             :     }
      66           0 :     return nSize * 2;
      67             : }
      68             : 
      69             : static sal_uInt32
      70           0 : hashString (rtl_uString *pString)
      71             : {
      72             :     return (sal_uInt32) rtl_ustr_hashCode_WithLength (pString->buffer,
      73           0 :                                                       pString->length);
      74             : }
      75             : 
      76             : static StringHashTable *
      77           0 : rtl_str_hash_new (sal_uInt32 nSize)
      78             : {
      79           0 :     StringHashTable *pHash = (StringHashTable *)malloc (sizeof (StringHashTable));
      80             : 
      81           0 :     pHash->nEntries = 0;
      82           0 :     pHash->nSize = getNextSize (nSize);
      83           0 :     pHash->pData = (rtl_uString **) calloc (sizeof (rtl_uString *), pHash->nSize);
      84             : 
      85           0 :     return pHash;
      86             : }
      87             : 
      88             : static void
      89           0 : rtl_str_hash_free (StringHashTable *pHash)
      90             : {
      91           0 :     if (!pHash)
      92           0 :         return;
      93           0 :     if (pHash->pData)
      94           0 :         free (pHash->pData);
      95           0 :     free (pHash);
      96             : }
      97             : 
      98             : static void
      99           0 : rtl_str_hash_insert_nonequal (StringHashTable   *pHash,
     100             :                               rtl_uString       *pString)
     101             : {
     102           0 :     sal_uInt32  nHash = hashString (pString);
     103             :     sal_uInt32  n;
     104             : 
     105           0 :     n = nHash % pHash->nSize;
     106           0 :     while (pHash->pData[n] != NULL) {
     107           0 :         n++;
     108           0 :         if (n >= pHash->nSize)
     109           0 :             n = 0;
     110             :     }
     111           0 :     pHash->pData[n] = pString;
     112           0 : }
     113             : 
     114             : static void
     115           0 : rtl_str_hash_resize (sal_uInt32        nNewSize)
     116             : {
     117             :     sal_uInt32 i;
     118             :     StringHashTable *pNewHash;
     119           0 :     StringHashTable *pHash = getHashTable();
     120             : 
     121             :     OSL_ASSERT (nNewSize > pHash->nEntries);
     122             : 
     123           0 :     pNewHash = rtl_str_hash_new (nNewSize);
     124             : 
     125           0 :     for (i = 0; i < pHash->nSize; i++)
     126             :     {
     127           0 :         if (pHash->pData[i] != NULL)
     128           0 :             rtl_str_hash_insert_nonequal (pNewHash, pHash->pData[i]);
     129             :     }
     130           0 :     pNewHash->nEntries = pHash->nEntries;
     131           0 :     free (pHash->pData);
     132           0 :     *pHash = *pNewHash;
     133           0 :     pNewHash->pData = NULL;
     134           0 :     rtl_str_hash_free (pNewHash);
     135           0 : }
     136             : 
     137             : static bool
     138           0 : compareEqual (rtl_uString *pStringA, rtl_uString *pStringB)
     139             : {
     140           0 :     if (pStringA == pStringB)
     141           0 :         return true;
     142           0 :     if (pStringA->length != pStringB->length)
     143           0 :         return false;
     144             :     return !rtl_ustr_compare_WithLength( pStringA->buffer, pStringA->length,
     145           0 :                                          pStringB->buffer, pStringB->length);
     146             : }
     147             : 
     148             : rtl_uString *
     149           0 : rtl_str_hash_intern (rtl_uString       *pString,
     150             :                      int                can_return)
     151             : {
     152           0 :     sal_uInt32  nHash = hashString (pString);
     153             :     sal_uInt32  n;
     154             :     rtl_uString *pHashStr;
     155             : 
     156           0 :     StringHashTable *pHash = getHashTable();
     157             : 
     158             :     // Should we resize ?
     159           0 :     if (pHash->nEntries >= pHash->nSize/2)
     160           0 :         rtl_str_hash_resize (getNextSize(pHash->nSize));
     161             : 
     162           0 :     n = nHash % pHash->nSize;
     163           0 :     while ((pHashStr = pHash->pData[n]) != NULL) {
     164           0 :         if (compareEqual (pHashStr, pString))
     165             :         {
     166           0 :             rtl_uString_acquire (pHashStr);
     167           0 :             return pHashStr;
     168             :         }
     169           0 :         n++;
     170           0 :         if (n >= pHash->nSize)
     171           0 :             n = 0;
     172             :     }
     173             : 
     174           0 :     if (!can_return)
     175             :     {
     176           0 :         rtl_uString *pCopy = NULL;
     177           0 :         rtl_uString_newFromString( &pCopy, pString );
     178           0 :         pString = pCopy;
     179           0 :         if (!pString)
     180           0 :             return NULL;
     181             :     }
     182             : 
     183           0 :     if (!SAL_STRING_IS_STATIC (pString))
     184           0 :         pString->refCount |= SAL_STRING_INTERN_FLAG;
     185           0 :     pHash->pData[n] = pString;
     186           0 :     pHash->nEntries++;
     187             : 
     188           0 :     return pString;
     189             : }
     190             : 
     191             : void
     192           0 : rtl_str_hash_remove (rtl_uString       *pString)
     193             : {
     194             :     sal_uInt32   n;
     195           0 :     sal_uInt32   nHash = hashString (pString);
     196             :     rtl_uString *pHashStr;
     197             : 
     198           0 :     StringHashTable *pHash = getHashTable();
     199             : 
     200           0 :     n = nHash % pHash->nSize;
     201           0 :     while ((pHashStr = pHash->pData[n]) != NULL) {
     202           0 :         if (compareEqual (pHashStr, pString))
     203           0 :             break;
     204           0 :         n++;
     205           0 :         if (n >= pHash->nSize)
     206           0 :             n = 0;
     207             :     }
     208             :     OSL_ASSERT (pHash->pData[n] != 0);
     209           0 :     if (pHash->pData[n] == NULL)
     210           0 :         return;
     211             : 
     212           0 :     pHash->pData[n++] = NULL;
     213           0 :     pHash->nEntries--;
     214             : 
     215           0 :     if (n >= pHash->nSize)
     216           0 :         n = 0;
     217             : 
     218           0 :     while ((pHashStr = pHash->pData[n]) != NULL) {
     219           0 :         pHash->pData[n] = NULL;
     220             :         // FIXME: rather unsophisticated and N^2 in chain-length, but robust.
     221           0 :         rtl_str_hash_insert_nonequal (pHash, pHashStr);
     222           0 :         n++;
     223           0 :         if (n >= pHash->nSize)
     224           0 :             n = 0;
     225             :     }
     226             :     // FIXME: Should we down-size ?
     227             : }
     228             : 
     229             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */

Generated by: LCOV version 1.10