HashTable.h revision 37b74a387bb3993387029859c2d9d051c41c724e 
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
21namespace 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 */
31template <typename HashEntryTy,
32          typename HashFunctionTy,
33          typename EntryFactoryTy = HashEntryFactory<HashEntryTy> >
34class 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
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