1 //===- HashTable.h --------------------------------------------------------===// 2 // 3 // The MCLinker Project 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 #ifndef MCLD_ADT_HASHTABLE_H_ 10 #define MCLD_ADT_HASHTABLE_H_ 11 12 #include "mcld/ADT/HashBase.h" 13 #include "mcld/ADT/HashEntryFactory.h" 14 #include "mcld/ADT/HashIterator.h" 15 #include "mcld/ADT/TypeTraits.h" 16 #include "mcld/Support/Allocators.h" 17 #include "mcld/Support/Compiler.h" 18 19 #include <utility> 20 21 namespace mcld { 22 23 /** \class HashTable 24 * \brief HashTable is a hash table which follows boost::unordered_map, but it 25 * is open addressing and can linear probing. 26 * 27 * mcld::HashTable is a linear probing hash table. It does not allocate 28 * the memory space of the entries by itself. Instead, entries are allocated 29 * outside and then emplaced into the hash table. 30 */ 31 template <typename HashEntryTy, 32 typename HashFunctionTy, 33 typename EntryFactoryTy = HashEntryFactory<HashEntryTy> > 34 class HashTable : public HashTableImpl<HashEntryTy, HashFunctionTy> { 35 private: 36 typedef HashTableImpl<HashEntryTy, HashFunctionTy> BaseTy; 37 38 public: 39 typedef size_t size_type; 40 typedef HashFunctionTy hasher; 41 typedef HashEntryTy entry_type; 42 typedef typename BaseTy::bucket_type bucket_type; 43 typedef typename HashEntryTy::key_type key_type; 44 45 typedef HashIterator<ChainIteratorBase<BaseTy>, NonConstTraits<HashEntryTy> > 46 chain_iterator; 47 typedef HashIterator<ChainIteratorBase<const BaseTy>, 48 ConstTraits<HashEntryTy> > const_chain_iterator; 49 50 typedef HashIterator<EntryIteratorBase<BaseTy>, NonConstTraits<HashEntryTy> > 51 entry_iterator; 52 typedef HashIterator<EntryIteratorBase<const BaseTy>, 53 ConstTraits<HashEntryTy> > const_entry_iterator; 54 55 typedef entry_iterator iterator; 56 typedef const_entry_iterator const_iterator; 57 58 public: 59 // ----- constructor ----- // 60 explicit HashTable(size_type pSize = 3); 61 ~HashTable(); 62 getEntryFactory()63 EntryFactoryTy& getEntryFactory() { return m_EntryFactory; } 64 65 // ----- modifiers ----- // 66 void clear(); 67 68 /// insert - insert a new element to the container. The element is 69 // constructed in-place, i.e. no copy or move operations are performed. 70 // If the element already exists, return the element, and set pExist true. 71 entry_type* insert(const key_type& pKey, bool& pExist); 72 73 /// erase - remove the element with the same key 74 size_type erase(const key_type& pKey); 75 76 // ----- lookups ----- // 77 /// find - finds an element with key pKey 78 // If the element does not exist, return end() 79 iterator find(const key_type& pKey); 80 81 /// find - finds an element with key pKey, constant version 82 // If the element does not exist, return end() 83 const_iterator find(const key_type& pKey) const; 84 85 size_type count(const key_type& pKey) const; 86 87 // ----- hash policy ----- // 88 float load_factor() const; 89 90 /// rehash - if the load factor is larger than 75%, or the empty buckets is 91 // less than 12.5%, the rehash the hash table 92 void rehash(); 93 94 /// rehash - immediately re-new the hash table to the size pCount, and 95 // rehash all elements. 96 void rehash(size_type pCount); 97 98 // ----- iterators ----- // 99 iterator begin(); 100 iterator end(); 101 102 const_entry_iterator begin() const; 103 const_entry_iterator end() const; 104 105 chain_iterator begin(const key_type& pKey); 106 chain_iterator end(const key_type& pKey); 107 const_chain_iterator begin(const key_type& pKey) const; 108 const_chain_iterator end(const key_type& pKey) const; 109 110 private: 111 EntryFactoryTy m_EntryFactory; 112 113 private: 114 DISALLOW_COPY_AND_ASSIGN(HashTable); 115 }; 116 117 #include "HashTable.tcc" 118 119 } // namespace mcld 120 121 #endif // MCLD_ADT_HASHTABLE_H_ 122