soltools/ldump/hashtbl.cxx

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