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 } 459