LCOV - code coverage report
Current view: top level - sal/rtl - hash.cxx (source / functions) Hit Total Coverage
Test: commit c8344322a7af75b84dd3ca8f78b05543a976dfd5 Lines: 90 97 92.8 %
Date: 2015-06-13 12:38:46 Functions: 10 10 100.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     1632951 : getHashTable ()
      39             : {
      40             :     static StringHashTable *pInternPool = NULL;
      41     1632951 :     if (pInternPool == NULL) {
      42         152 :         static StringHashTable* pHash = rtl_str_hash_new(1024);
      43         152 :         pInternPool = pHash;
      44             :     }
      45     1632951 :     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         456 : 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        1528 :     for (sal_uInt32 i = 0; i < SAL_N_ELEMENTS(nPrimes); i++)
      62             :     {
      63        1528 :         if (nPrimes[i] > nSize)
      64         456 :             return nPrimes[i];
      65             :     }
      66           0 :     return nSize * 2;
      67             : }
      68             : 
      69             : static sal_uInt32
      70     2109210 : hashString (rtl_uString *pString)
      71             : {
      72             :     return (sal_uInt32) rtl_ustr_hashCode_WithLength (pString->buffer,
      73     2109210 :                                                       pString->length);
      74             : }
      75             : 
      76             : static StringHashTable *
      77         304 : rtl_str_hash_new (sal_uInt32 nSize)
      78             : {
      79         304 :     StringHashTable *pHash = static_cast<StringHashTable *>(malloc (sizeof (StringHashTable)));
      80             : 
      81         304 :     pHash->nEntries = 0;
      82         304 :     pHash->nSize = getNextSize (nSize);
      83         304 :     pHash->pData = static_cast<rtl_uString **>(calloc (sizeof (rtl_uString *), pHash->nSize));
      84             : 
      85         304 :     return pHash;
      86             : }
      87             : 
      88             : static void
      89         152 : rtl_str_hash_free (StringHashTable *pHash)
      90             : {
      91         152 :     if (!pHash)
      92         152 :         return;
      93         152 :     if (pHash->pData)
      94           0 :         free (pHash->pData);
      95         152 :     free (pHash);
      96             : }
      97             : 
      98             : static void
      99      476411 : rtl_str_hash_insert_nonequal (StringHashTable   *pHash,
     100             :                               rtl_uString       *pString)
     101             : {
     102      476411 :     sal_uInt32  nHash = hashString (pString);
     103             :     sal_uInt32  n;
     104             : 
     105      476411 :     n = nHash % pHash->nSize;
     106     1025316 :     while (pHash->pData[n] != NULL) {
     107       72494 :         n++;
     108       72494 :         if (n >= pHash->nSize)
     109           0 :             n = 0;
     110             :     }
     111      476411 :     pHash->pData[n] = pString;
     112      476411 : }
     113             : 
     114             : static void
     115         152 : rtl_str_hash_resize (sal_uInt32        nNewSize)
     116             : {
     117             :     sal_uInt32 i;
     118             :     StringHashTable *pNewHash;
     119         152 :     StringHashTable *pHash = getHashTable();
     120             : 
     121             :     OSL_ASSERT (nNewSize > pHash->nEntries);
     122             : 
     123         152 :     pNewHash = rtl_str_hash_new (nNewSize);
     124             : 
     125      556160 :     for (i = 0; i < pHash->nSize; i++)
     126             :     {
     127      556008 :         if (pHash->pData[i] != NULL)
     128      277928 :             rtl_str_hash_insert_nonequal (pNewHash, pHash->pData[i]);
     129             :     }
     130         152 :     pNewHash->nEntries = pHash->nEntries;
     131         152 :     free (pHash->pData);
     132         152 :     *pHash = *pNewHash;
     133         152 :     pNewHash->pData = NULL;
     134         152 :     rtl_str_hash_free (pNewHash);
     135         152 : }
     136             : 
     137             : static bool
     138     1748838 : compareEqual (rtl_uString *pStringA, rtl_uString *pStringB)
     139             : {
     140     1748838 :     if (pStringA == pStringB)
     141      615454 :         return true;
     142     1133384 :     if (pStringA->length != pStringB->length)
     143      688111 :         return false;
     144             :     return !rtl_ustr_compare_WithLength( pStringA->buffer, pStringA->length,
     145      445273 :                                          pStringB->buffer, pStringB->length);
     146             : }
     147             : 
     148             : rtl_uString *
     149     1017345 : rtl_str_hash_intern (rtl_uString       *pString,
     150             :                      int                can_return)
     151             : {
     152     1017345 :     sal_uInt32  nHash = hashString (pString);
     153             :     sal_uInt32  n;
     154             :     rtl_uString *pHashStr;
     155             : 
     156     1017345 :     StringHashTable *pHash = getHashTable();
     157             : 
     158             :     // Should we resize ?
     159     1017345 :     if (pHash->nEntries >= pHash->nSize/2)
     160         152 :         rtl_str_hash_resize (getNextSize(pHash->nSize));
     161             : 
     162     1017345 :     n = nHash % pHash->nSize;
     163     2545168 :     while ((pHashStr = pHash->pData[n]) != NULL) {
     164      912186 :         if (compareEqual (pHashStr, pString))
     165             :         {
     166      401708 :             rtl_uString_acquire (pHashStr);
     167      401708 :             return pHashStr;
     168             :         }
     169      510478 :         n++;
     170      510478 :         if (n >= pHash->nSize)
     171           1 :             n = 0;
     172             :     }
     173             : 
     174      615637 :     if (!can_return)
     175             :     {
     176       39550 :         rtl_uString *pCopy = NULL;
     177       39550 :         rtl_uString_newFromString( &pCopy, pString );
     178       39550 :         pString = pCopy;
     179       39550 :         if (!pString)
     180           0 :             return NULL;
     181             :     }
     182             : 
     183      615637 :     if (!SAL_STRING_IS_STATIC (pString))
     184      615636 :         pString->refCount |= SAL_STRING_INTERN_FLAG;
     185      615637 :     pHash->pData[n] = pString;
     186      615637 :     pHash->nEntries++;
     187             : 
     188      615637 :     return pString;
     189             : }
     190             : 
     191             : void
     192      615454 : rtl_str_hash_remove (rtl_uString       *pString)
     193             : {
     194             :     sal_uInt32   n;
     195      615454 :     sal_uInt32   nHash = hashString (pString);
     196             :     rtl_uString *pHashStr;
     197             : 
     198      615454 :     StringHashTable *pHash = getHashTable();
     199             : 
     200      615454 :     n = nHash % pHash->nSize;
     201     1452106 :     while ((pHashStr = pHash->pData[n]) != NULL) {
     202      836652 :         if (compareEqual (pHashStr, pString))
     203      615454 :             break;
     204      221198 :         n++;
     205      221198 :         if (n >= pHash->nSize)
     206           0 :             n = 0;
     207             :     }
     208             :     OSL_ASSERT (pHash->pData[n] != 0);
     209      615454 :     if (pHash->pData[n] == NULL)
     210      615454 :         return;
     211             : 
     212      615454 :     pHash->pData[n++] = NULL;
     213      615454 :     pHash->nEntries--;
     214             : 
     215      615454 :     if (n >= pHash->nSize)
     216           0 :         n = 0;
     217             : 
     218     1429391 :     while ((pHashStr = pHash->pData[n]) != NULL) {
     219      198483 :         pHash->pData[n] = NULL;
     220             :         // FIXME: rather unsophisticated and N^2 in chain-length, but robust.
     221      198483 :         rtl_str_hash_insert_nonequal (pHash, pHashStr);
     222      198483 :         n++;
     223      198483 :         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.11