soltools/ldump/hashtbl.cxx

   1 /*************************************************************************
   2  *
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * Copyright 2008 by Sun Microsystems, Inc.
   6  *
   7  * OpenOffice.org - a multi-platform office productivity suite
   8  *
   9  * $RCSfile: hashtbl.cxx,v $
  10  * $Revision: 1.7 $
  11  *
  12  * This file is part of OpenOffice.org.
  13  *
  14  * OpenOffice.org is free software: you can redistribute it and/or modify
  15  * it under the terms of the GNU Lesser General Public License version 3
  16  * only, as published by the Free Software Foundation.
  17  *
  18  * OpenOffice.org is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU Lesser General Public License version 3 for more details
  22  * (a copy is included in the LICENSE file that accompanied this code).
  23  *
  24  * You should have received a copy of the GNU Lesser General Public License
  25  * version 3 along with OpenOffice.org.  If not, see
  26  * <http://www.openoffice.org/license.html>
  27  * for a copy of the LGPLv3 License.
  28  *
  29  ************************************************************************/
  30
  31 // MARKER(update_precomp.py): autogen include statement, do not remove
  32 #include "precompiled_soltools.hxx"
  33
  34 #include "hashtbl.hxx"
  35 #include <string.h>
  36
  37 // -------------------------------------------------------------
  38 // class HashItem
  39 //
  40 class HashItem
  41 {
  42     enum ETag { TAG_EMPTY, TAG_USED, TAG_DELETED };
  43
  44     void*   m_pObject;
  45     ETag    m_Tag;
  46     char*       m_Key;
  47
  48 public:
  49     HashItem() { m_Tag = TAG_EMPTY; m_Key = NULL; m_pObject = NULL; }
  50     ~HashItem() { delete [] m_Key; }
  51
  52     bool IsDeleted() const
  53     {   return m_Tag == TAG_DELETED; }
  54
  55     bool IsEmpty() const
  56     {   return m_Tag == TAG_DELETED || m_Tag == TAG_EMPTY; }
  57
  58     bool IsFree() const
  59     {   return m_Tag == TAG_EMPTY; }
  60
  61     bool IsUsed() const
  62     {   return m_Tag == TAG_USED; }
  63
  64     void Delete()
  65     { m_Tag = TAG_DELETED; delete [] m_Key; m_Key = new char[ 1 ]; m_Key[ 0 ] = 0; m_pObject = NULL; }
  66
  67     const char *GetKey() const
  68     { return m_Key; }
  69
  70     void* GetObject() const
  71     { return m_pObject; }
  72
  73     void SetObject(const char * Key, void *pObject)
  74     { m_Tag = TAG_USED; delete [] m_Key; m_Key = new char[ strlen( Key ) + 1 ]; strcpy( m_Key, Key ); m_pObject = pObject; }
  75 };
  76
  77 #define MIN(a,b) (a)<(b)?(a):(b)
  78 #define MAX(a,b) (a)>(b)?(a):(b)
  79
  80 // -------------------------------------------------------------
  81 // class HashTable
  82 //
  83
  84 /*static*/ double HashTable::m_defMaxLoadFactor = 0.5;
  85 /*static*/ double HashTable::m_defDefGrowFactor = 2.0;
  86
  87 HashTable::HashTable(unsigned long lSize, bool bOwner, double dMaxLoadFactor, double dGrowFactor)
  88 {
  89     m_lSize          = lSize;
  90     m_bOwner         = bOwner;
  91     m_lElem          = 0;
  92     m_dMaxLoadFactor = MAX(0.5,MIN(1.0,dMaxLoadFactor));  // 0.5 ... 1.0
  93     m_dGrowFactor    = MAX(2.0,MIN(5.0,dGrowFactor));     // 1.3 ... 5.0
  94     m_pData          = new HashItem [lSize];
  95 }
  96
  97 HashTable::~HashTable()
  98 {
  99     // Wenn die HashTable der Owner der Objecte ist,
 100     // müssen die Destruktoren separat gerufen werden.
 101     // Dies geschieht über die virtuelle Methode OnDeleteObject()
 102     //
 103     // Problem: Virtuelle Funktionen sind im Destructor nicht virtuell!!
 104     //          Der Code muß deshalb ins Macro
 105
 106     /*
 107     if (m_bOwner)
 108     {
 109         for (ULONG i=0; i<GetSize(); i++)
 110         {
 111             void *pObject = GetObjectAt(i);
 112
 113             if (pObject != NULL)
 114                 OnDeleteObject(pObject());
 115         }
 116     }
 117     */
 118
 119     // Speicher für HashItems freigeben
 120     delete [] m_pData;
 121 }
 122
 123 void* HashTable::GetObjectAt(unsigned long lPos) const
 124 // Gibt Objekt zurück, wenn es eines gibt, sonst NULL;
 125 {
 126     HashItem *pItem = &m_pData[lPos];
 127
 128     return pItem->IsUsed() ? pItem->GetObject() : NULL;
 129 }
 130
 131 void HashTable::OnDeleteObject(void*)
 132 {
 133 }
 134
 135 unsigned long HashTable::Hash(const char *Key) const
 136 {
 137     // Hashfunktion von P.J. Weinberger
 138     // aus dem "Drachenbuch" von Aho/Sethi/Ullman
 139     unsigned long i,n;
 140     unsigned long h = 0;
 141     unsigned long g = 0;
 142
 143     for (i=0,n=strlen( Key ); i<n; i++)
 144     {
 145         h = (h<<4) + (unsigned long)(unsigned short)Key[i];
 146         g = h & 0xf0000000;
 147
 148         if (g != 0)
 149         {
 150             h = h ^ (g >> 24);
 151             h = h ^ g;
 152         }
 153     }
 154
 155     return h % m_lSize;
 156 }
 157
 158 unsigned long HashTable::DHash(const char* Key, unsigned long lOldHash) const
 159 {
 160     unsigned long lHash = lOldHash;
 161     unsigned long i,n;
 162
 163     for (i=0,n=strlen( Key ); i<n; i++)
 164     {
 165         lHash *= 256L;
 166         lHash += (unsigned long)(unsigned short)Key[i];
 167         lHash %= m_lSize;
 168     }
 169     return lHash;
 170 }
 171
 172 unsigned long HashTable::Probe(unsigned long lPos) const
 173 // gibt den Folgewert von lPos zurück
 174 {
 175     lPos++; if (lPos==m_lSize) lPos=0;
 176     return lPos;
 177 }
 178
 179 bool HashTable::IsFull() const
 180 {
 181     return m_lElem>=m_lSize;
 182 }
 183
 184 bool HashTable::Insert(const char * Key, void* pObject)
 185 // pre:  Key ist nicht im Dictionary enthalten, sonst return FALSE
 186 //       Dictionary ist nicht voll, sonst return FALSE
 187 // post: pObject ist unter Key im Dictionary; m_nElem wurde erhöht
 188 {
 189     SmartGrow();
 190
 191     if (IsFull())
 192     {
 193         return false;
 194     }
 195
 196     if (FindPos(Key) != NULL )
 197         return false;
 198
 199     unsigned long     lPos  = Hash(Key);
 200     HashItem *pItem = &m_pData[lPos];
 201
 202     // first hashing
 203     //
 204     if (pItem->IsEmpty())
 205     {
 206         pItem->SetObject(Key, pObject);
 207         m_lElem++;
 208
 209         return true;
 210     }
 211
 212     // double hashing
 213     //
 214     lPos  = DHash(Key,lPos);
 215     pItem = &m_pData[lPos];
 216
 217     if (pItem->IsEmpty())
 218     {
 219         pItem->SetObject(Key, pObject);
 220         m_lElem++;
 221
 222         return true;
 223     }
 224
 225     // linear probing
 226     //
 227     do
 228     {
 229         lPos  = Probe(lPos);
 230         pItem = &m_pData[lPos];
 231     }
 232     while(!pItem->IsEmpty());
 233
 234     pItem->SetObject(Key, pObject);
 235     m_lElem++;
 236     return true;
 237 }
 238
 239 HashItem* HashTable::FindPos(const char * Key) const
 240 // sucht den Key; gibt Refrenz auf den Eintrag (gefunden)
 241 // oder NULL (nicht gefunden) zurück
 242 //
 243 // pre:  -
 244 // post: -
 245 {
 246     // first hashing
 247     //
 248     unsigned long     lPos  = Hash(Key);
 249     HashItem *pItem = &m_pData[lPos];
 250
 251     if (pItem->IsUsed()
 252     &&  !(strcmp( pItem->GetKey(), Key )))
 253     {
 254         return pItem;
 255     }
 256
 257     // double hashing
 258     //
 259     if (pItem->IsDeleted() || pItem->IsUsed())
 260     {
 261         lPos  = DHash(Key,lPos);
 262         pItem = &m_pData[lPos];
 263
 264         if (pItem->IsUsed()
 265         &&  (!strcmp( pItem->GetKey(), Key)))
 266         {
 267             return pItem;
 268         }
 269
 270         // linear probing
 271         //
 272         if (pItem->IsDeleted() || pItem->IsUsed())
 273         {
 274             unsigned long n      = 0;
 275             bool  bFound = false;
 276             bool  bEnd   = false;
 277
 278             do
 279             {
 280                 n++;
 281                 lPos   = Probe(lPos);
 282                 pItem  = &m_pData[lPos];
 283
 284                 bFound =  pItem->IsUsed()
 285                        && !( strcmp( pItem->GetKey(), Key ));
 286
 287                 bEnd = !(n<m_lSize || pItem->IsFree());
 288             }
 289             while(!bFound && !bEnd);
 290
 291             return bFound ? pItem : NULL;
 292         }
 293     }
 294
 295     // nicht gefunden
 296     //
 297     return NULL;
 298 }
 299
 300 void* HashTable::Find(const char *Key) const
 301 // Gibt Verweis des Objektes zurück, das unter Key abgespeichert ist,
 302 // oder NULL wenn nicht vorhanden.
 303 //
 304 // pre:  -
 305 // post: -
 306 {
 307     HashItem *pItem = FindPos(Key);
 308
 309     if (pItem != NULL
 310     && ( !strcmp( pItem->GetKey(), Key )))
 311         return pItem->GetObject();
 312     else
 313         return NULL;
 314 }
 315
 316 void* HashTable::Delete( const char * Key)
 317 // Löscht Objekt, das unter Key abgespeichert ist und gibt Verweis
 318 // darauf zurück.
 319 // Gibt NULL zurück, wenn Key nicht vorhanden ist.
 320 //
 321 // pre:  -
 322 // post: Objekt ist nicht mehr enthalten; m_lElem dekrementiert
 323 //       Wenn die HashTable der Owner ist, wurde das Object gelöscht
 324 {
 325     HashItem *pItem = FindPos(Key);
 326
 327     if (pItem != NULL
 328     &&  ( !strcmp( pItem->GetKey(), Key )))
 329     {
 330         void* pObject = pItem->GetObject();
 331
 332         if (m_bOwner)
 333             OnDeleteObject(pObject);
 334
 335         pItem->Delete();
 336         m_lElem--;
 337         return pObject;
 338     }
 339     else
 340     {
 341         return NULL;
 342     }
 343 }
 344
 345 double HashTable::CalcLoadFactor() const
 346 // prozentuale Belegung der Hashtabelle berechnen
 347 {
 348     return double(m_lElem) / double(m_lSize);
 349 }
 350
 351 void HashTable::SmartGrow()
 352 // Achtung: da die Objekte umkopiert werden, darf die OnDeleteObject-Methode
 353 //          nicht gerufen werden
 354 {
 355     double dLoadFactor = CalcLoadFactor();
 356
 357     if (dLoadFactor <= m_dMaxLoadFactor)
 358         return; // nothing to grow
 359
 360     unsigned long     lOldSize = m_lSize;              // alte Daten sichern
 361     HashItem* pOldData = m_pData;
 362
 363     m_lSize = (unsigned long) (m_dGrowFactor * m_lSize); // neue Größe
 364     m_pData = new HashItem[m_lSize];           // neue Daten holen
 365
 366     // kein Speicher:
 367     // Zustand "Tabelle voll" wird in Insert abgefangen
 368     //
 369     if (m_pData == NULL)
 370     {
 371         m_lSize = lOldSize;
 372         m_pData = pOldData;
 373         return;
 374     }
 375
 376     m_lElem = 0;                               // noch keine neuen Daten
 377
 378     // Umkopieren der Daten
 379     //
 380     for (unsigned long i=0; i<lOldSize; i++)
 381     {
 382         HashItem *pItem = &pOldData[i];
 383
 384         if (pItem->IsUsed())
 385             Insert(pItem->GetKey(),pItem->GetObject());
 386     }
 387
 388     delete [] pOldData;
 389 }
 390
 391 // Iterator ---------------------------------------------------------
 392 //
 393
 394 HashTableIterator::HashTableIterator(HashTable const& aTable)
 395 : m_aTable(aTable)
 396 {
 397     m_lAt = 0;
 398 }
 399
 400 void* HashTableIterator::GetFirst()
 401 {
 402     m_lAt = 0;
 403     return FindValidObject(true /* forward */);
 404 }
 405
 406 void* HashTableIterator::GetLast()
 407 {
 408     m_lAt = m_aTable.GetSize() -1;
 409     return FindValidObject(false /* backward */);
 410 }
 411
 412 void* HashTableIterator::GetNext()
 413 {
 414     if (m_lAt+1 >= m_aTable.GetSize())
 415         return NULL;
 416
 417     m_lAt++;
 418     return FindValidObject(true /* forward */);
 419 }
 420
 421 void* HashTableIterator::GetPrev()
 422 {
 423     if (m_lAt <= 0)
 424         return NULL;
 425
 426     m_lAt--;
 427     return FindValidObject(false /* backward */);
 428 }
 429
 430 void* HashTableIterator::FindValidObject(bool bForward)
 431 // Sucht nach einem vorhandenen Objekt ab der aktuellen
 432 // Position.
 433 //
 434 // pre:  ab inkl. m_lAt soll die Suche beginnen
 435 // post: if not found then
 436 //                      if bForward == TRUE then
 437 //                              m_lAt == m_aTable.GetSize() -1
 438 //                      else
 439 //                              m_lAt == 0
 440 //               else
 441 //                      m_lAt ist die gefundene Position
 442 {
 443     void *pObject = m_aTable.GetObjectAt(m_lAt);
 444
 445     if (pObject != NULL)
 446         return pObject;
 447
 448     while (pObject == NULL
 449        && (bForward ? ((m_lAt+1) < m_aTable.GetSize())
 450                     :   m_lAt    > 0))
 451     {
 452         if (bForward)
 453             m_lAt++;
 454         else
 455             m_lAt--;
 456
 457         pObject = m_aTable.GetObjectAt(m_lAt);
 458     }
 459
 460     return pObject;
 461 }