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