HashTable.h revision 533eae20118036f425f27bf0536ef0ccbb090b65 
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
20namespace 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 */
30template<typename HashEntryTy,
31         typename HashFunctionTy,
32         typename EntryFactoryTy = HashEntryFactory<HashEntryTy> >
33class HashTable : public HashTableImpl<HashEntryTy, HashFunctionTy>,
34                  private Uncopyable
35{
36private:
37  typedef HashTableImpl<HashEntryTy, HashFunctionTy> BaseTy;
38
39public:
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
59public:
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
112private:
113  EntryFactoryTy m_EntryFactory;
114
115};
116
117#include "HashTable.tcc"
118
119} // namespace of mcld
120
121#endif
122
123