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