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

Generated by: LCOV version 1.10