1*38268e38SAndrew Rist /************************************************************** 2cdf0e10cSrcweir * 3*38268e38SAndrew Rist * Licensed to the Apache Software Foundation (ASF) under one 4*38268e38SAndrew Rist * or more contributor license agreements. See the NOTICE file 5*38268e38SAndrew Rist * distributed with this work for additional information 6*38268e38SAndrew Rist * regarding copyright ownership. The ASF licenses this file 7*38268e38SAndrew Rist * to you under the Apache License, Version 2.0 (the 8*38268e38SAndrew Rist * "License"); you may not use this file except in compliance 9*38268e38SAndrew Rist * with the License. You may obtain a copy of the License at 10cdf0e10cSrcweir * 11*38268e38SAndrew Rist * http://www.apache.org/licenses/LICENSE-2.0 12cdf0e10cSrcweir * 13*38268e38SAndrew Rist * Unless required by applicable law or agreed to in writing, 14*38268e38SAndrew Rist * software distributed under the License is distributed on an 15*38268e38SAndrew Rist * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 16*38268e38SAndrew Rist * KIND, either express or implied. See the License for the 17*38268e38SAndrew Rist * specific language governing permissions and limitations 18*38268e38SAndrew Rist * under the License. 19cdf0e10cSrcweir * 20*38268e38SAndrew Rist *************************************************************/ 21*38268e38SAndrew Rist 22*38268e38SAndrew Rist 23cdf0e10cSrcweir 24cdf0e10cSrcweir #ifndef _HASHTBL_HXX 25cdf0e10cSrcweir #define _HASHTBL_HXX 26cdf0e10cSrcweir 27cdf0e10cSrcweir // ADT hash table 28cdf0e10cSrcweir // 29cdf0e10cSrcweir // Invariante: 30cdf0e10cSrcweir // 1. m_lElem < m_lSize 31cdf0e10cSrcweir // 2. die Elemente in m_Array wurden double-hashed erzeugt 32cdf0e10cSrcweir // 33cdf0e10cSrcweir class HashItem; 34cdf0e10cSrcweir 35cdf0e10cSrcweir class HashTable 36cdf0e10cSrcweir { 37cdf0e10cSrcweir unsigned long m_lSize; 38cdf0e10cSrcweir unsigned long m_lElem; 39cdf0e10cSrcweir HashItem *m_pData; 40cdf0e10cSrcweir double m_dMaxLoadFactor; 41cdf0e10cSrcweir double m_dGrowFactor; 42cdf0e10cSrcweir bool m_bOwner; 43cdf0e10cSrcweir 44cdf0e10cSrcweir unsigned long Hash(const char *cKey) const; 45cdf0e10cSrcweir unsigned long DHash(const char *cKey , unsigned long lHash) const; 46cdf0e10cSrcweir unsigned long Probe(unsigned long lPos) const; 47cdf0e10cSrcweir 48cdf0e10cSrcweir HashItem* FindPos(const char *cKey) const; 49cdf0e10cSrcweir void SmartGrow(); 50cdf0e10cSrcweir double CalcLoadFactor() const; 51cdf0e10cSrcweir 52cdf0e10cSrcweir protected: 53cdf0e10cSrcweir friend class HashTableIterator; 54cdf0e10cSrcweir 55cdf0e10cSrcweir virtual void OnDeleteObject(void* pObject); 56cdf0e10cSrcweir 57cdf0e10cSrcweir void* GetObjectAt(unsigned long lPos) const; 58cdf0e10cSrcweir 59cdf0e10cSrcweir // Default-Werte 60cdf0e10cSrcweir public: 61cdf0e10cSrcweir static double m_defMaxLoadFactor; 62cdf0e10cSrcweir static double m_defDefGrowFactor; 63cdf0e10cSrcweir 64cdf0e10cSrcweir public: 65cdf0e10cSrcweir HashTable 66cdf0e10cSrcweir ( 67cdf0e10cSrcweir unsigned long lSize, 68cdf0e10cSrcweir bool bOwner, 69cdf0e10cSrcweir double dMaxLoadFactor = HashTable::m_defMaxLoadFactor /* 0.8 */, 70cdf0e10cSrcweir double dGrowFactor = HashTable::m_defDefGrowFactor /* 2.0 */ 71cdf0e10cSrcweir ); 72cdf0e10cSrcweir 73cdf0e10cSrcweir virtual ~HashTable(); 74cdf0e10cSrcweir 75cdf0e10cSrcweir bool IsFull() const; GetSize() const76cdf0e10cSrcweir unsigned long GetSize() const { return m_lSize; } 77cdf0e10cSrcweir 78cdf0e10cSrcweir void* Find (const char *cKey ) const; 79cdf0e10cSrcweir bool Insert (const char *cKey , void* pObject); 80cdf0e10cSrcweir void* Delete (const char *cKey); 81cdf0e10cSrcweir }; 82cdf0e10cSrcweir 83cdf0e10cSrcweir // ADT hash table iterator 84cdf0e10cSrcweir // 85cdf0e10cSrcweir // Invariante: 0 <= m_lAt < m_aTable.GetCount() 86cdf0e10cSrcweir // 87cdf0e10cSrcweir class HashTableIterator 88cdf0e10cSrcweir { 89cdf0e10cSrcweir unsigned long m_lAt; 90cdf0e10cSrcweir HashTable const& m_aTable; 91cdf0e10cSrcweir 92cdf0e10cSrcweir void operator =(HashTableIterator &); // not defined 93cdf0e10cSrcweir 94cdf0e10cSrcweir void* FindValidObject(bool bForward); 95cdf0e10cSrcweir 96cdf0e10cSrcweir protected: 97cdf0e10cSrcweir void* GetFirst(); // Interation _ohne_ Sortierung 98cdf0e10cSrcweir void* GetNext(); 99cdf0e10cSrcweir void* GetLast(); 100cdf0e10cSrcweir void* GetPrev(); 101cdf0e10cSrcweir 102cdf0e10cSrcweir public: 103cdf0e10cSrcweir HashTableIterator(HashTable const&); 104cdf0e10cSrcweir }; 105cdf0e10cSrcweir 106cdf0e10cSrcweir #endif // _HASHTBL_HXX 107cdf0e10cSrcweir 108