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