1 /************************************************************** 2 * 3 * Licensed to the Apache Software Foundation (ASF) under one 4 * or more contributor license agreements. See the NOTICE file 5 * distributed with this work for additional information 6 * regarding copyright ownership. The ASF licenses this file 7 * to you under the Apache License, Version 2.0 (the 8 * "License"); you may not use this file except in compliance 9 * with the License. You may obtain a copy of the License at 10 * 11 * http://www.apache.org/licenses/LICENSE-2.0 12 * 13 * Unless required by applicable law or agreed to in writing, 14 * software distributed under the License is distributed on an 15 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 16 * KIND, either express or implied. See the License for the 17 * specific language governing permissions and limitations 18 * under the License. 19 * 20 *************************************************************/ 21 22 23 24 #include <tools/gen.hxx> 25 #include <tools/debug.hxx> 26 #include <soldep/hashtbl.hxx> 27 28 // ------------------------------------------------------------- 29 // class HashItem 30 // 31 class HashItem 32 { 33 enum ETag { TAG_EMPTY, TAG_USED, TAG_DELETED }; 34 35 void* m_pObject; 36 ETag m_Tag; 37 ByteString m_Key; 38 39 public: 40 HashItem() { m_Tag = TAG_EMPTY; m_pObject = NULL; } 41 42 sal_Bool IsDeleted() const 43 { return m_Tag == TAG_DELETED; } 44 45 sal_Bool IsEmpty() const 46 { return m_Tag == TAG_DELETED || m_Tag == TAG_EMPTY; } 47 48 sal_Bool IsFree() const 49 { return m_Tag == TAG_EMPTY; } 50 51 sal_Bool IsUsed() const 52 { return m_Tag == TAG_USED; } 53 54 void Delete() 55 { m_Tag = TAG_DELETED; m_Key = ""; m_pObject = NULL; } 56 57 ByteString const& GetKey() const 58 { return m_Key; } 59 60 void* GetObject() const 61 { return m_pObject; } 62 63 void SetObject(ByteString const Key, void *pObject) 64 { m_Tag = TAG_USED; m_Key = Key; m_pObject = pObject; } 65 }; 66 67 #define MIN(a,b) (a)<(b)?(a):(b) 68 #define MAX(a,b) (a)>(b)?(a):(b) 69 70 // ------------------------------------------------------------- 71 // class HashTable 72 // 73 74 /*static*/ double HashTable::m_defMaxLoadFactor = 0.8; 75 /*static*/ double HashTable::m_defDefGrowFactor = 2.0; 76 77 HashTable::HashTable(sal_uIntPtr lSize, sal_Bool bOwner, double dMaxLoadFactor, double dGrowFactor) 78 { 79 m_lSize = lSize; 80 m_bOwner = bOwner; 81 m_lElem = 0; 82 m_dMaxLoadFactor = MAX(0.5,MIN(1.0,dMaxLoadFactor)); // 0.5 ... 1.0 83 m_dGrowFactor = MAX(1.3,MIN(5.0,dGrowFactor)); // 1.3 ... 5.0 84 m_pData = new HashItem [lSize]; 85 86 // Statistik 87 #ifdef DBG_UTIL 88 m_aStatistic.m_lSingleHash = 0; 89 m_aStatistic.m_lDoubleHash = 0; 90 m_aStatistic.m_lProbe = 0; 91 #endif 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 (sal_uIntPtr 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(sal_uIntPtr lPos) const 121 // Gibt Objekt zur�ck, wenn es eines gibt, sonst NULL; 122 { 123 DBG_ASSERT(lPos<m_lSize, "HashTable::GetObjectAt()"); 124 125 HashItem *pItem = &m_pData[lPos]; 126 127 return pItem->IsUsed() ? pItem->GetObject() : NULL; 128 } 129 130 void HashTable::OnDeleteObject(void*) 131 { 132 DBG_ERROR("HashTable::OnDeleteObject(void*) nicht �berladen"); 133 } 134 135 sal_uIntPtr HashTable::Hash(ByteString const& Key) const 136 { 137 /* 138 sal_uIntPtr lHash = 0; 139 sal_uIntPtr i,n; 140 141 for (i=0,n=Key.Len(); i<n; i++) 142 { 143 lHash *= 256L; 144 lHash += (sal_uIntPtr)(sal_uInt16)Key.GetStr()[i]; 145 lHash %= m_lSize; 146 } 147 return lHash; 148 */ 149 150 // Hashfunktion von P.J. Weinberger 151 // aus dem "Drachenbuch" von Aho/Sethi/Ullman 152 sal_uIntPtr i,n; 153 sal_uIntPtr h = 0; 154 sal_uIntPtr g = 0; 155 156 for (i=0,n=Key.Len(); i<n; i++) 157 { 158 h = (h<<4) + (sal_uIntPtr)(sal_uInt16)Key.GetBuffer()[i]; 159 g = h & 0xf0000000; 160 161 if (g != 0) 162 { 163 h = h ^ (g >> 24); 164 h = h ^ g; 165 } 166 } 167 168 return h % m_lSize; 169 } 170 171 sal_uIntPtr HashTable::DHash(ByteString const& Key, sal_uIntPtr lOldHash) const 172 { 173 sal_uIntPtr lHash = lOldHash; 174 sal_uIntPtr i,n; 175 176 for (i=0,n=Key.Len(); i<n; i++) 177 { 178 lHash *= 256L; 179 lHash += (sal_uIntPtr)(sal_uInt16)Key.GetBuffer()[i]; 180 lHash %= m_lSize; 181 } 182 return lHash; 183 184 /* return 185 ( 186 lHash 187 + (char)Key.GetStr()[0] * 256 188 + (char)Key.GetStr()[Key.Len()-1] 189 + 1 190 ) 191 % m_lSize; 192 */ 193 } 194 195 sal_uIntPtr HashTable::Probe(sal_uIntPtr lPos) const 196 // gibt den Folgewert von lPos zur�ck 197 { 198 lPos++; if (lPos==m_lSize) lPos=0; 199 return lPos; 200 } 201 202 sal_Bool HashTable::IsFull() const 203 { 204 return m_lElem>=m_lSize; 205 } 206 207 sal_Bool HashTable::Insert(ByteString const& Key, void* pObject) 208 // pre: Key ist nicht im Dictionary enthalten, sonst return FALSE 209 // Dictionary ist nicht voll, sonst return FALSE 210 // post: pObject ist unter Key im Dictionary; m_nElem wurde erh�ht 211 { 212 SmartGrow(); 213 214 if (IsFull()) 215 { 216 DBG_ERROR("HashTable::Insert() is full"); 217 return sal_False; 218 } 219 220 if (FindPos(Key) != NULL ) 221 return sal_False; 222 223 sal_uIntPtr lPos = Hash(Key); 224 HashItem *pItem = &m_pData[lPos]; 225 226 // first hashing 227 // 228 if (pItem->IsEmpty()) 229 { 230 pItem->SetObject(Key, pObject); 231 m_lElem++; 232 233 #ifdef DBG_UTIL 234 m_aStatistic.m_lSingleHash++; 235 #endif 236 237 return sal_True; 238 } 239 240 // double hashing 241 // 242 lPos = DHash(Key,lPos); 243 pItem = &m_pData[lPos]; 244 245 if (pItem->IsEmpty()) 246 { 247 pItem->SetObject(Key, pObject); 248 m_lElem++; 249 250 #ifdef DBG_UTIL 251 m_aStatistic.m_lDoubleHash++; 252 #endif 253 254 return sal_True; 255 } 256 257 // linear probing 258 // 259 do 260 { 261 #ifdef DBG_UTIL 262 m_aStatistic.m_lProbe++; 263 #endif 264 265 lPos = Probe(lPos); 266 pItem = &m_pData[lPos]; 267 } 268 while(!pItem->IsEmpty()); 269 270 pItem->SetObject(Key, pObject); 271 m_lElem++; 272 return sal_True; 273 } 274 275 HashItem* HashTable::FindPos(ByteString const& Key) const 276 // sucht den Key; gibt Refrenz auf den Eintrag (gefunden) 277 // oder NULL (nicht gefunden) zur�ck 278 // 279 // pre: - 280 // post: - 281 { 282 // first hashing 283 // 284 sal_uIntPtr lPos = Hash(Key); 285 HashItem *pItem = &m_pData[lPos]; 286 287 if (pItem->IsUsed() 288 && pItem->GetKey() == Key) 289 { 290 return pItem; 291 } 292 293 // double hashing 294 // 295 if (pItem->IsDeleted() || pItem->IsUsed()) 296 { 297 lPos = DHash(Key,lPos); 298 pItem = &m_pData[lPos]; 299 300 if (pItem->IsUsed() 301 && pItem->GetKey() == Key) 302 { 303 return pItem; 304 } 305 306 // linear probing 307 // 308 if (pItem->IsDeleted() || pItem->IsUsed()) 309 { 310 sal_uIntPtr n = 0; 311 sal_Bool bFound = sal_False; 312 sal_Bool bEnd = sal_False; 313 314 do 315 { 316 n++; 317 lPos = Probe(lPos); 318 pItem = &m_pData[lPos]; 319 320 bFound = pItem->IsUsed() 321 && pItem->GetKey() == Key; 322 323 bEnd = !(n<m_lSize || pItem->IsFree()); 324 } 325 while(!bFound && !bEnd); 326 327 return bFound ? pItem : NULL; 328 } 329 } 330 331 // nicht gefunden 332 // 333 return NULL; 334 } 335 336 void* HashTable::Find(ByteString const& Key) const 337 // Gibt Verweis des Objektes zur�ck, das unter Key abgespeichert ist, 338 // oder NULL wenn nicht vorhanden. 339 // 340 // pre: - 341 // post: - 342 { 343 HashItem *pItem = FindPos(Key); 344 345 if (pItem != NULL 346 && pItem->GetKey() == Key) 347 return pItem->GetObject(); 348 else 349 return NULL; 350 } 351 352 void* HashTable::Delete(ByteString const& Key) 353 // L�scht Objekt, das unter Key abgespeichert ist und gibt Verweis 354 // darauf zur�ck. 355 // Gibt NULL zur�ck, wenn Key nicht vorhanden ist. 356 // 357 // pre: - 358 // post: Objekt ist nicht mehr enthalten; m_lElem dekrementiert 359 // Wenn die HashTable der Owner ist, wurde das Object gel�scht 360 { 361 HashItem *pItem = FindPos(Key); 362 363 if (pItem != NULL 364 && pItem->GetKey() == Key) 365 { 366 void* pObject = pItem->GetObject(); 367 368 if (m_bOwner) 369 OnDeleteObject(pObject); 370 371 pItem->Delete(); 372 m_lElem--; 373 return pObject; 374 } 375 else 376 { 377 return NULL; 378 } 379 } 380 381 double HashTable::CalcLoadFactor() const 382 // prozentuale Belegung der Hashtabelle berechnen 383 { 384 return double(m_lElem) / double(m_lSize); 385 } 386 387 void HashTable::SmartGrow() 388 // Achtung: da die Objekte umkopiert werden, darf die OnDeleteObject-Methode 389 // nicht gerufen werden 390 { 391 double dLoadFactor = CalcLoadFactor(); 392 393 if (dLoadFactor <= m_dMaxLoadFactor) 394 return; // nothing to grow 395 396 sal_uIntPtr lOldSize = m_lSize; // alte Daten sichern 397 HashItem* pOldData = m_pData; 398 399 m_lSize = sal_uIntPtr (m_dGrowFactor * m_lSize); // neue Gr��e 400 m_pData = new HashItem[m_lSize]; // neue Daten holen 401 402 // kein Speicher: 403 // Zustand "Tabelle voll" wird in Insert abgefangen 404 // 405 if (m_pData == NULL) 406 { 407 m_lSize = lOldSize; 408 m_pData = pOldData; 409 return; 410 } 411 412 m_lElem = 0; // noch keine neuen Daten 413 414 // Umkopieren der Daten 415 // 416 for (sal_uIntPtr i=0; i<lOldSize; i++) 417 { 418 HashItem *pItem = &pOldData[i]; 419 420 if (pItem->IsUsed()) 421 Insert(pItem->GetKey(),pItem->GetObject()); 422 } 423 424 delete [] pOldData; 425 } 426 427 // Iterator --------------------------------------------------------- 428 // 429 430 HashTableIterator::HashTableIterator(HashTable const& aTable) 431 : m_aTable(aTable) 432 { 433 m_lAt = 0; 434 } 435 436 void* HashTableIterator::GetFirst() 437 { 438 m_lAt = 0; 439 return FindValidObject(sal_True /* forward */); 440 } 441 442 void* HashTableIterator::GetLast() 443 { 444 m_lAt = m_aTable.GetSize() -1; 445 return FindValidObject(sal_False /* backward */); 446 } 447 448 void* HashTableIterator::GetNext() 449 { 450 if (m_lAt+1 >= m_aTable.GetSize()) 451 return NULL; 452 453 m_lAt++; 454 return FindValidObject(sal_True /* forward */); 455 } 456 457 void* HashTableIterator::GetPrev() 458 { 459 if (m_lAt <= 0) 460 return NULL; 461 462 m_lAt--; 463 return FindValidObject(sal_False /* backward */); 464 } 465 466 void* HashTableIterator::FindValidObject(sal_Bool bForward) 467 // Sucht nach einem vorhandenen Objekt ab der aktuellen 468 // Position. 469 // 470 // pre: ab inkl. m_lAt soll die Suche beginnen 471 // post: if not found then 472 // if bForward == sal_True then 473 // m_lAt == m_aTable.GetSize() -1 474 // else 475 // m_lAt == 0 476 // else 477 // m_lAt ist die gefundene Position 478 { 479 void *pObject = m_aTable.GetObjectAt(m_lAt); 480 481 if (pObject != NULL) 482 return pObject; 483 484 while (pObject == NULL 485 && (bForward ? ((m_lAt+1) < m_aTable.GetSize()) 486 : m_lAt > 0)) 487 { 488 if (bForward) 489 m_lAt++; 490 else 491 m_lAt--; 492 493 pObject = m_aTable.GetObjectAt(m_lAt); 494 } 495 496 #ifdef DBG_UTIL 497 498 if (pObject == NULL) 499 { 500 DBG_ASSERT(bForward ? m_lAt == m_aTable.GetSize() -1 : m_lAt == 0, 501 "HashTableIterator::FindValidObject()"); 502 } 503 504 #endif 505 506 return pObject; 507 } 508