HashTable.h revision f33f6de54db174aa679a4b6d1e040d37e95541c0 
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#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
23namespace 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 */
33template<typename HashEntryTy,
34         typename HashFunctionTy,
35         typename EntryFactoryTy = HashEntryFactory<HashEntryTy> >
36class HashTable : public HashTableImpl<HashEntryTy, HashFunctionTy>,
37                  private Uncopyable
38{
39private:
40  typedef HashTableImpl<HashEntryTy, HashFunctionTy> BaseTy;
41
42public:
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
62public:
63  // -----  constructor  ----- //
64  explicit HashTable(size_type pSize=3);
65  ~HashTable();
66
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
115private:
116  EntryFactoryTy m_EntryFactory;
117
118};
119
120#include "HashTable.tcc"
121
122} // namespace of mcld
123
124#endif
125
126