idl/source/cmptools/hash.cxx

   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 SvStringHashEntry::~SvStringHashEntry() { };
  31
  32 SvHashTable::SvHashTable( sal_uInt32 nMaxEntries )
  33 {
  34     nMax = nMaxEntries;     // set max entries
  35     nFill = 0;              // no entries
  36     lTry = 0;
  37     lAsk = 0;
  38 }
  39
  40 SvHashTable::~SvHashTable()
  41 {
  42 }
  43
  44 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     lAsk++;
  52     lTry++;
  53
  54     nHash =  HashFunc( rElement );
  55     nIndex = nHash % nMax;
  56
  57     nLoop = 0;                                      // divide to range
  58     while( (nMax != nLoop) && IsEntry( nIndex ) )
  59     {                     // is place occupied
  60         if( equals( rElement, nIndex ) )
  61         {
  62             if( pInsertPos )
  63                 *pInsertPos = nIndex;               // place of Element
  64             return true;
  65         }
  66         nLoop++;
  67         lTry++;
  68         nIndex = (sal_uInt16)(nIndex + nHash + 7) % nMax;
  69     }
  70
  71     if( bInsert )
  72     {
  73         DBG_ASSERT( nMax != nLoop, "Hash table full" );
  74         if( nMax != nLoop )
  75         {
  76             nFill++;
  77             *pInsertPos = nIndex;                       // return free place
  78             return true;
  79         }
  80     }
  81     return false;
  82 }
  83
  84 SvStringHashTable::SvStringHashTable( sal_uInt32 nMaxEntries )
  85         : SvHashTable( nMaxEntries )
  86 {
  87     pEntries = new SvStringHashEntry[ nMaxEntries ];
  88
  89     // set RefCount to one
  90     SvStringHashEntry * pPos, *pEnd;
  91     pPos    = pEntries;
  92     pEnd    = pEntries + nMaxEntries;
  93     while( pPos != pEnd )
  94     {
  95         pPos->AddFirstRef();
  96         pPos++;
  97     }
  98 }
  99
 100 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     delete [] pEntries;
 115 }
 116
 117 sal_uInt32 SvStringHashTable::HashFunc( const OString& rElement ) const
 118 {
 119     sal_uInt32          nHash = 0;  // hash value
 120     const char *    pStr = rElement.getStr();
 121
 122     int nShift = 0;
 123     while( *pStr )
 124     {
 125         if( isupper( *pStr ) )
 126             nHash ^= sal_uInt32(*pStr - 'A' + 26) << nShift;
 127         else
 128             nHash ^= sal_uInt32(*pStr - 'a') << nShift;
 129         if( nShift == 28 )
 130             nShift = 0;
 131         else
 132             nShift += 4;
 133         pStr++;
 134     }
 135     return nHash;
 136 }
 137
 138 OString SvStringHashTable::GetNearString( const OString& rName ) const
 139 {
 140     for( sal_uInt32 i = 0; i < GetMax(); i++ )
 141     {
 142         SvStringHashEntry * pE = Get( i );
 143         if( pE )
 144         {
 145             if( pE->GetName().equalsIgnoreAsciiCase( rName ) && !pE->GetName().equals( rName ) )
 146                 return pE->GetName();
 147         }
 148     }
 149     return OString();
 150 }
 151
 152 bool SvStringHashTable::IsEntry( sal_uInt32 nIndex ) const
 153 {
 154     if( nIndex >= GetMax() )
 155         return false;
 156     return pEntries[ nIndex ].HasId();
 157 }
 158
 159 bool SvStringHashTable::Insert( const OString& rName, sal_uInt32 * pIndex )
 160 {
 161     sal_uInt32 nIndex;
 162
 163     if( !pIndex ) pIndex = &nIndex;
 164
 165     if( !SvHashTable::Test_Insert( rName, true, pIndex ) )
 166         return false;
 167
 168     if( !IsEntry( *pIndex ) )
 169         pEntries[ *pIndex ] = SvStringHashEntry( rName, *pIndex );
 170     return true;
 171 }
 172
 173 bool SvStringHashTable::Test( const OString& rName, sal_uInt32 * pPos ) const
 174 {
 175     return const_cast<SvStringHashTable*>(this)->Test_Insert( rName, false, pPos );
 176 }
 177
 178 SvStringHashEntry * SvStringHashTable::Get( sal_uInt32 nIndex ) const
 179 {
 180     if( IsEntry( nIndex ) )
 181         return pEntries + nIndex;
 182     return NULL;
 183 }
 184
 185 bool SvStringHashTable::equals( const OString& rElement,
 186                                           sal_uInt32 nIndex ) const
 187 {
 188     return rElement.equals( pEntries[ nIndex ].GetName() );
 189 }
 190
 191 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */