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