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