LCOV - code coverage report
Current view: top level - idl/source/cmptools - hash.cxx (source / functions) Hit Total Coverage
Test: commit 10e77ab3ff6f4314137acd6e2702a6e5c1ce1fae Lines: 70 80 87.5 %
Date: 2014-11-03 Functions: 13 16 81.2 %
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             : // C and C++ includes
      22             : #include <stdlib.h>
      23             : #include <stdio.h>
      24             : #include <ctype.h>
      25             : 
      26             : // program-sensitive includes
      27             : #include <hash.hxx>
      28             : #include <tools/debug.hxx>
      29             : 
      30      202952 : SvStringHashEntry::~SvStringHashEntry() { };
      31             : 
      32          16 : SvHashTable::SvHashTable( sal_uInt32 nMaxEntries )
      33             : {
      34          16 :     nMax = nMaxEntries;     // set max entries
      35          16 :     nFill = 0;              // no entries
      36          16 :     lTry = 0;
      37          16 :     lAsk = 0;
      38          16 : }
      39             : 
      40          16 : SvHashTable::~SvHashTable()
      41             : {
      42          16 : }
      43             : 
      44      338603 : bool SvHashTable::Test_Insert( const OString& rElement, bool bInsert,
      45             :                                sal_uInt32 * pInsertPos )
      46             : {
      47             :     sal_uInt32    nHash;
      48             :     sal_uInt32    nIndex;
      49             :     sal_uInt32    nLoop;
      50             : 
      51      338603 :     lAsk++;
      52      338603 :     lTry++;
      53             : 
      54      338603 :     nHash =  HashFunc( rElement );
      55      338603 :     nIndex = nHash % nMax;
      56             : 
      57      338603 :     nLoop = 0;                                      // divide to range
      58      692036 :     while( (nMax != nLoop) && IsEntry( nIndex ) )
      59             :     {                     // is place occupied
      60      232525 :         if( equals( rElement, nIndex ) )
      61             :         {
      62      217695 :             if( pInsertPos )
      63      217695 :                 *pInsertPos = nIndex;               // place of Element
      64      217695 :             return true;
      65             :         }
      66       14830 :         nLoop++;
      67       14830 :         lTry++;
      68       14830 :         nIndex = (sal_uInt16)(nIndex + nHash + 7) % nMax;
      69             :     }
      70             : 
      71      120908 :     if( bInsert )
      72             :     {
      73             :         DBG_ASSERT( nMax != nLoop, "Hash table full" );
      74       20520 :         if( nMax != nLoop )
      75             :         {
      76       20520 :             nFill++;
      77       20520 :             *pInsertPos = nIndex;                       // return free place
      78       20520 :             return true;
      79             :         }
      80             :     }
      81      100388 :     return false;
      82             : }
      83             : 
      84          16 : SvStringHashTable::SvStringHashTable( sal_uInt32 nMaxEntries )
      85          16 :         : SvHashTable( nMaxEntries )
      86             : {
      87          16 :     pEntries = new SvStringHashEntry[ nMaxEntries ];
      88             : 
      89             :     // set RefCount to one
      90             :     SvStringHashEntry * pPos, *pEnd;
      91          16 :     pPos    = pEntries;
      92          16 :     pEnd    = pEntries + nMaxEntries;
      93      182464 :     while( pPos != pEnd )
      94             :     {
      95      182432 :         pPos->AddFirstRef();
      96      182432 :         pPos++;
      97             :     }
      98          16 : }
      99             : 
     100          48 : SvStringHashTable::~SvStringHashTable()
     101             : {
     102             : #ifdef DBG_UTIL
     103             :     // set RefCount to one
     104             :     SvStringHashEntry * pPos, *pEnd;
     105             :     pPos    = pEntries;
     106             :     pEnd    = pEntries + GetMax();
     107             :     while( pPos != pEnd )
     108             :     {
     109             :         DBG_ASSERT( pPos->GetRefCount() == 1, "Reference count != 1" );
     110             :         pPos++;
     111             :     }
     112             : #endif
     113             : 
     114          16 :     delete [] pEntries;
     115          32 : }
     116             : 
     117      338603 : sal_uInt32 SvStringHashTable::HashFunc( const OString& rElement ) const
     118             : {
     119      338603 :     sal_uInt32          nHash = 0;  // hash value
     120      338603 :     const char *    pStr = rElement.getStr();
     121             : 
     122      338603 :     int nShift = 0;
     123     4824035 :     while( *pStr )
     124             :     {
     125     4146829 :         if( isupper( *pStr ) )
     126     2221455 :             nHash ^= sal_uInt32(*pStr - 'A' + 26) << nShift;
     127             :         else
     128     1925374 :             nHash ^= sal_uInt32(*pStr - 'a') << nShift;
     129     4146829 :         if( nShift == 28 )
     130      374625 :             nShift = 0;
     131             :         else
     132     3772204 :             nShift += 4;
     133     4146829 :         pStr++;
     134             :     }
     135      338603 :     return( nHash );
     136             : }
     137             : 
     138           0 : OString SvStringHashTable::GetNearString( const OString& rName ) const
     139             : {
     140           0 :     for( sal_uInt32 i = 0; i < GetMax(); i++ )
     141             :     {
     142           0 :         SvStringHashEntry * pE = Get( i );
     143           0 :         if( pE )
     144             :         {
     145           0 :             if( pE->GetName().equalsIgnoreAsciiCase( rName ) && !pE->GetName().equals( rName ) )
     146           0 :                 return pE->GetName();
     147             :         }
     148             :     }
     149           0 :     return OString();
     150             : }
     151             : 
     152      612608 : bool SvStringHashTable::IsEntry( sal_uInt32 nIndex ) const
     153             : {
     154      612608 :     if( nIndex >= GetMax() )
     155           0 :         return false;
     156      612608 :     return pEntries[ nIndex ].HasId();
     157             : }
     158             : 
     159       20960 : bool SvStringHashTable::Insert( const OString& rName, sal_uInt32 * pIndex )
     160             : {
     161             :     sal_uInt32 nIndex;
     162             : 
     163       20960 :     if( !pIndex ) pIndex = &nIndex;
     164             : 
     165       20960 :     if( !SvHashTable::Test_Insert( rName, true, pIndex ) )
     166           0 :         return false;
     167             : 
     168       20960 :     if( !IsEntry( *pIndex ) )
     169       20520 :         pEntries[ *pIndex ] = SvStringHashEntry( rName, *pIndex );
     170       20960 :     return true;
     171             : }
     172             : 
     173      317643 : bool SvStringHashTable::Test( const OString& rName, sal_uInt32 * pPos ) const
     174             : {
     175      317643 :     return const_cast<SvStringHashTable*>(this)->Test_Insert( rName, false, pPos );
     176             : }
     177             : 
     178      238215 : SvStringHashEntry * SvStringHashTable::Get( sal_uInt32 nIndex ) const
     179             : {
     180      238215 :     if( IsEntry( nIndex ) )
     181      238215 :         return pEntries + nIndex;
     182           0 :     return( NULL );
     183             : }
     184             : 
     185      232525 : bool SvStringHashTable::equals( const OString& rElement,
     186             :                                           sal_uInt32 nIndex ) const
     187             : {
     188      232525 :     return rElement.equals( pEntries[ nIndex ].GetName() );
     189             : }
     190             : 
     191             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */

Generated by: LCOV version 1.10