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 #ifndef _HASHTBL_HXX 29 #define _HASHTBL_HXX 30 31 // ADT hash table 32 // 33 // Invariante: 34 // 1. m_lElem < m_lSize 35 // 2. die Elemente in m_Array wurden double-hashed erzeugt 36 // 37 class HashItem; 38 39 class HashTable 40 { 41 unsigned long m_lSize; 42 unsigned long m_lElem; 43 HashItem *m_pData; 44 double m_dMaxLoadFactor; 45 double m_dGrowFactor; 46 bool m_bOwner; 47 48 unsigned long Hash(const char *cKey) const; 49 unsigned long DHash(const char *cKey , unsigned long lHash) const; 50 unsigned long Probe(unsigned long lPos) const; 51 52 HashItem* FindPos(const char *cKey) const; 53 void SmartGrow(); 54 double CalcLoadFactor() const; 55 56 protected: 57 friend class HashTableIterator; 58 59 virtual void OnDeleteObject(void* pObject); 60 61 void* GetObjectAt(unsigned long lPos) const; 62 63 // Default-Werte 64 public: 65 static double m_defMaxLoadFactor; 66 static double m_defDefGrowFactor; 67 68 public: 69 HashTable 70 ( 71 unsigned long lSize, 72 bool bOwner, 73 double dMaxLoadFactor = HashTable::m_defMaxLoadFactor /* 0.8 */, 74 double dGrowFactor = HashTable::m_defDefGrowFactor /* 2.0 */ 75 ); 76 77 virtual ~HashTable(); 78 79 bool IsFull() const; 80 unsigned long GetSize() const { return m_lSize; } 81 82 void* Find (const char *cKey ) const; 83 bool Insert (const char *cKey , void* pObject); 84 void* Delete (const char *cKey); 85 }; 86 87 // ADT hash table iterator 88 // 89 // Invariante: 0 <= m_lAt < m_aTable.GetCount() 90 // 91 class HashTableIterator 92 { 93 unsigned long m_lAt; 94 HashTable const& m_aTable; 95 96 void operator =(HashTableIterator &); // not defined 97 98 void* FindValidObject(bool bForward); 99 100 protected: 101 void* GetFirst(); // Interation _ohne_ Sortierung 102 void* GetNext(); 103 void* GetLast(); 104 void* GetPrev(); 105 106 public: 107 HashTableIterator(HashTable const&); 108 }; 109 110 #endif // _HASHTBL_HXX 111 112