tools/workben/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.5 $
  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_tools.hxx"
  33
  34 #include <tlgen.hxx>
  35 #include "hashtbl.hxx"
  36
  37 #include <algorithm>
  38
  39 // -------------------------------------------------------------
  40 // class HashItem
  41 //
  42 class HashItem
  43 {
  44     enum ETag { TAG_EMPTY, TAG_USED, TAG_DELETED };
  45
  46     void*   m_pObject;
  47     ETag    m_Tag;
  48     String  m_Key;
  49
  50 public:
  51     HashItem() { m_Tag = TAG_EMPTY; m_pObject = NULL; }
  52
  53     BOOL IsDeleted() const
  54     {   return m_Tag == TAG_DELETED; }
  55
  56     BOOL IsEmpty() const
  57     {   return m_Tag == TAG_DELETED || m_Tag == TAG_EMPTY; }
  58
  59     BOOL IsFree() const
  60     {   return m_Tag == TAG_EMPTY; }
  61
  62     BOOL IsUsed() const
  63     {   return m_Tag == TAG_USED; }
  64
  65     void Delete()
  66     { m_Tag = TAG_DELETED; m_Key = ""; m_pObject = NULL; }
  67
  68     String const& GetKey() const
  69     { return m_Key; }
  70
  71     void* GetObject() const
  72     { return m_pObject; }
  73
  74     void SetObject(String const Key, void *pObject)
  75     { m_Tag = TAG_USED; m_Key = Key; m_pObject = pObject; }
  76 };
  77
  78 // #define MIN(a,b) (a)<(b)?(a):(b)
  79 // #define MAX(a,b) (a)>(b)?(a):(b)
  80
  81 // -------------------------------------------------------------
  82 // class HashTable
  83 //
  84
  85 /*static*/ double HashTable::m_defMaxLoadFactor = 0.8;
  86 /*static*/ double HashTable::m_defDefGrowFactor = 2.0;
  87
  88 HashTable::HashTable(ULONG lSize, BOOL bOwner, double dMaxLoadFactor, double dGrowFactor)
  89 {
  90     m_lSize          = lSize;
  91     m_bOwner         = bOwner;
  92     m_lElem          = 0;
  93     m_dMaxLoadFactor = std::max(0.5,std::min(1.0,dMaxLoadFactor));  // 0.5 ... 1.0
  94     m_dGrowFactor    = std::max(1.3,(5.0,dGrowFactor));     // 1.3 ... 5.0
  95     m_pData          = new HashItem [lSize];
  96
  97 // Statistik
  98 #ifdef DBG_UTIL
  99     m_aStatistic.m_lSingleHash = 0;
 100     m_aStatistic.m_lDoubleHash = 0;
 101     m_aStatistic.m_lProbe          = 0;
 102 #endif
 103 }
 104
 105 HashTable::~HashTable()
 106 {
 107     // Wenn die HashTable der Owner der Objecte ist,
 108     // müssen die Destruktoren separat gerufen werden.
 109     // Dies geschieht über die virtuelle Methode OnDeleteObject()
 110     //
 111     // Problem: Virtuelle Funktionen sind im Destructor nicht virtuell!!
 112     //          Der Code muß deshalb ins Macro
 113
 114     /*
 115     if (m_bOwner)
 116     {
 117         for (ULONG i=0; i<GetSize(); i++)
 118         {
 119             void *pObject = GetObjectAt(i);
 120
 121             if (pObject != NULL)
 122                 OnDeleteObject(pObject());
 123         }
 124     }
 125     */
 126
 127     // Speicher für HashItems freigeben
 128     delete [] m_pData;
 129 }
 130
 131 void* HashTable::GetObjectAt(ULONG lPos) const
 132 // Gibt Objekt zurück, wenn es eines gibt, sonst NULL;
 133 {
 134     DBG_ASSERT(lPos<m_lSize, "HashTable::GetObjectAt()");
 135
 136     HashItem *pItem = &m_pData[lPos];
 137
 138     return pItem->IsUsed() ? pItem->GetObject() : NULL;
 139 }
 140
 141 void HashTable::OnDeleteObject(void*)
 142 {
 143     DBG_ERROR("HashTable::OnDeleteObject(void*) nicht überladen");
 144 }
 145
 146 ULONG HashTable::Hash(String const& Key) const
 147 {
 148     /*
 149     ULONG lHash = 0;
 150     ULONG i,n;
 151
 152     for (i=0,n=Key.Len(); i<n; i++)
 153     {
 154         lHash *= 256L;
 155         lHash += (ULONG)(USHORT)Key.GetStr()[i];
 156         lHash %= m_lSize;
 157     }
 158     return lHash;
 159     */
 160
 161     // Hashfunktion von P.J. Weinberger
 162     // aus dem "Drachenbuch" von Aho/Sethi/Ullman
 163     ULONG i,n;
 164     ULONG h = 0;
 165     ULONG g = 0;
 166
 167     for (i=0,n=Key.Len(); i<n; i++)
 168     {
 169         h = (h<<4) + (ULONG)(USHORT)Key.GetStr()[i];
 170         g = h & 0xf0000000;
 171
 172         if (g != 0)
 173         {
 174             h = h ^ (g >> 24);
 175             h = h ^ g;
 176         }
 177     }
 178
 179     return h % m_lSize;
 180 }
 181
 182 ULONG HashTable::DHash(String const& Key, ULONG lOldHash) const
 183 {
 184     ULONG lHash = lOldHash;
 185     ULONG i,n;
 186
 187     for (i=0,n=Key.Len(); i<n; i++)
 188     {
 189         lHash *= 256L;
 190         lHash += (ULONG)(USHORT)Key.GetStr()[i];
 191         lHash %= m_lSize;
 192     }
 193     return lHash;
 194
 195 /*    return
 196         (
 197             lHash
 198         +       (char)Key.GetStr()[0] * 256
 199         +       (char)Key.GetStr()[Key.Len()-1]
 200         +       1
 201         )
 202         % m_lSize;
 203 */
 204 }
 205
 206 ULONG HashTable::Probe(ULONG lPos) const
 207 // gibt den Folgewert von lPos zurück
 208 {
 209     lPos++; if (lPos==m_lSize) lPos=0;
 210     return lPos;
 211 }
 212
 213 BOOL HashTable::IsFull() const
 214 {
 215     return m_lElem>=m_lSize;
 216 }
 217
 218 BOOL HashTable::Insert(String const& Key, void* pObject)
 219 // pre:  Key ist nicht im Dictionary enthalten, sonst return FALSE
 220 //       Dictionary ist nicht voll, sonst return FALSE
 221 // post: pObject ist unter Key im Dictionary; m_nElem wurde erhöht
 222 {
 223     SmartGrow();
 224
 225     if (IsFull())
 226     {
 227         DBG_ERROR("HashTable::Insert() is full");
 228         return FALSE;
 229     }
 230
 231     if (FindPos(Key) != NULL )
 232         return FALSE;
 233
 234     ULONG     lPos  = Hash(Key);
 235     HashItem *pItem = &m_pData[lPos];
 236
 237     // first hashing
 238     //
 239     if (pItem->IsEmpty())
 240     {
 241         pItem->SetObject(Key, pObject);
 242         m_lElem++;
 243
 244         #ifdef DBG_UTIL
 245         m_aStatistic.m_lSingleHash++;
 246         #endif
 247
 248         return TRUE;
 249     }
 250
 251     // double hashing
 252     //
 253     lPos  = DHash(Key,lPos);
 254     pItem = &m_pData[lPos];
 255
 256     if (pItem->IsEmpty())
 257     {
 258         pItem->SetObject(Key, pObject);
 259         m_lElem++;
 260
 261         #ifdef DBG_UTIL
 262         m_aStatistic.m_lDoubleHash++;
 263         #endif
 264
 265         return TRUE;
 266     }
 267
 268     // linear probing
 269     //
 270     do
 271     {
 272         #ifdef DBG_UTIL
 273         m_aStatistic.m_lProbe++;
 274         #endif
 275
 276         lPos  = Probe(lPos);
 277         pItem = &m_pData[lPos];
 278     }
 279     while(!pItem->IsEmpty());
 280
 281     pItem->SetObject(Key, pObject);
 282     m_lElem++;
 283     return TRUE;
 284 }
 285
 286 HashItem* HashTable::FindPos(String const& Key) const
 287 // sucht den Key; gibt Refrenz auf den Eintrag (gefunden)
 288 // oder NULL (nicht gefunden) zurück
 289 //
 290 // pre:  -
 291 // post: -
 292 {
 293     // first hashing
 294     //
 295     ULONG     lPos  = Hash(Key);
 296     HashItem *pItem = &m_pData[lPos];
 297
 298     if (pItem->IsUsed()
 299     &&  pItem->GetKey() == Key)
 300     {
 301         return pItem;
 302     }
 303
 304     // double hashing
 305     //
 306     if (pItem->IsDeleted() || pItem->IsUsed())
 307     {
 308         lPos  = DHash(Key,lPos);
 309         pItem = &m_pData[lPos];
 310
 311         if (pItem->IsUsed()
 312         &&  pItem->GetKey() == Key)
 313         {
 314             return pItem;
 315         }
 316
 317         // linear probing
 318         //
 319         if (pItem->IsDeleted() || pItem->IsUsed())
 320         {
 321             ULONG n      = 0;
 322             BOOL  bFound = FALSE;
 323             BOOL  bEnd   = FALSE;
 324
 325             do
 326             {
 327                 n++;
 328                 lPos   = Probe(lPos);
 329                 pItem  = &m_pData[lPos];
 330
 331                 bFound =  pItem->IsUsed()
 332                        && pItem->GetKey() == Key;
 333
 334                 bEnd = !(n<m_lSize || pItem->IsFree());
 335             }
 336             while(!bFound && !bEnd);
 337
 338             return bFound ? pItem : NULL;
 339         }
 340     }
 341
 342     // nicht gefunden
 343     //
 344     return NULL;
 345 }
 346
 347 void* HashTable::Find(String const& Key) const
 348 // Gibt Verweis des Objektes zurück, das unter Key abgespeichert ist,
 349 // oder NULL wenn nicht vorhanden.
 350 //
 351 // pre:  -
 352 // post: -
 353 {
 354     HashItem *pItem = FindPos(Key);
 355
 356     if (pItem != NULL
 357     &&  pItem->GetKey() == Key)
 358         return pItem->GetObject();
 359     else
 360         return NULL;
 361 }
 362
 363 void* HashTable::Delete(String const& Key)
 364 // Löscht Objekt, das unter Key abgespeichert ist und gibt Verweis
 365 // darauf zurück.
 366 // Gibt NULL zurück, wenn Key nicht vorhanden ist.
 367 //
 368 // pre:  -
 369 // post: Objekt ist nicht mehr enthalten; m_lElem dekrementiert
 370 //       Wenn die HashTable der Owner ist, wurde das Object gelöscht
 371 {
 372     HashItem *pItem = FindPos(Key);
 373
 374     if (pItem != NULL
 375     &&  pItem->GetKey() == Key)
 376     {
 377         void* pObject = pItem->GetObject();
 378
 379         if (m_bOwner)
 380             OnDeleteObject(pObject);
 381
 382         pItem->Delete();
 383         m_lElem--;
 384         return pObject;
 385     }
 386     else
 387     {
 388         return NULL;
 389     }
 390 }
 391
 392 double HashTable::CalcLoadFactor() const
 393 // prozentuale Belegung der Hashtabelle berechnen
 394 {
 395     return double(m_lElem) / double(m_lSize);
 396 }
 397
 398 void HashTable::SmartGrow()
 399 // Achtung: da die Objekte umkopiert werden, darf die OnDeleteObject-Methode
 400 //          nicht gerufen werden
 401 {
 402     double dLoadFactor = CalcLoadFactor();
 403
 404     if (dLoadFactor <= m_dMaxLoadFactor)
 405         return; // nothing to grow
 406
 407     ULONG     lOldSize = m_lSize;              // alte Daten sichern
 408     HashItem* pOldData = m_pData;
 409
 410     m_lSize = ULONG (m_dGrowFactor * m_lSize); // neue Größe
 411     m_pData = new HashItem[m_lSize];           // neue Daten holen
 412
 413     // kein Speicher:
 414     // Zustand "Tabelle voll" wird in Insert abgefangen
 415     //
 416     if (m_pData == NULL)
 417     {
 418         m_lSize = lOldSize;
 419         m_pData = pOldData;
 420         return;
 421     }
 422
 423     m_lElem = 0;                               // noch keine neuen Daten
 424
 425     // Umkopieren der Daten
 426     //
 427     for (ULONG i=0; i<lOldSize; i++)
 428     {
 429         HashItem *pItem = &pOldData[i];
 430
 431         if (pItem->IsUsed())
 432             Insert(pItem->GetKey(),pItem->GetObject());
 433     }
 434
 435     delete [] pOldData;
 436 }
 437
 438 // Iterator ---------------------------------------------------------
 439 //
 440
 441 HashTableIterator::HashTableIterator(HashTable const& aTable)
 442 : m_aTable(aTable)
 443 {
 444     m_lAt = 0;
 445 }
 446
 447 void* HashTableIterator::GetFirst()
 448 {
 449     m_lAt = 0;
 450     return FindValidObject(TRUE /* forward */);
 451 }
 452
 453 void* HashTableIterator::GetLast()
 454 {
 455     m_lAt = m_aTable.GetSize() -1;
 456     return FindValidObject(FALSE /* backward */);
 457 }
 458
 459 void* HashTableIterator::GetNext()
 460 {
 461     if (m_lAt+1 >= m_aTable.GetSize())
 462         return NULL;
 463
 464     m_lAt++;
 465     return FindValidObject(TRUE /* forward */);
 466 }
 467
 468 void* HashTableIterator::GetPrev()
 469 {
 470     if (m_lAt <= 0)
 471         return NULL;
 472
 473     m_lAt--;
 474     return FindValidObject(FALSE /* backward */);
 475 }
 476
 477 void* HashTableIterator::FindValidObject(BOOL bForward)
 478 // Sucht nach einem vorhandenen Objekt ab der aktuellen
 479 // Position.
 480 //
 481 // pre:  ab inkl. m_lAt soll die Suche beginnen
 482 // post: if not found then
 483 //                      if bForward == TRUE then
 484 //                              m_lAt == m_aTable.GetSize() -1
 485 //                      else
 486 //                              m_lAt == 0
 487 //               else
 488 //                      m_lAt ist die gefundene Position
 489 {
 490     void *pObject = m_aTable.GetObjectAt(m_lAt);
 491
 492     if (pObject != NULL)
 493         return pObject;
 494
 495     while (pObject == NULL
 496        && (bForward ? ((m_lAt+1) < m_aTable.GetSize())
 497                     :   m_lAt    > 0))
 498     {
 499         if (bForward)
 500             m_lAt++;
 501         else
 502             m_lAt--;
 503
 504         pObject = m_aTable.GetObjectAt(m_lAt);
 505     }
 506
 507 #ifdef DBG_UTIL
 508
 509     if (pObject == NULL)
 510     {
 511         DBG_ASSERT(bForward ? m_lAt == m_aTable.GetSize() -1 : m_lAt == 0,
 512             "HashTableIterator::FindValidObject()");
 513     }
 514
 515 #endif
 516
 517     return pObject;
 518 }