1//===- StringUnorderedMap.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_SEARCH_TABLE_H
10#define MCLD_SEARCH_TABLE_H
11#include <vector>
12// For std::allocate.
13#include <memory>
14// For uint32_t.
15#include <stdint.h>
16#include <cassert>
17// For memset.
18#include <cstring>
19#ifdef ENABLE_UNITTEST
20#include <gtest.h>
21#endif
22/* FIXME: Move StringUnorderedMap under ADT. */
23
24namespace mcld
25{
26
27struct StringUnorderedMapDefaultHash
28{
29  size_t operator()(const char *pStr) {
30    size_t hashVal = 31;
31    while (*pStr)
32      hashVal = hashVal * 131 + (*pStr++);
33    return hashVal;
34  }
35};
36
37template<typename ValueType,
38         typename KeyType>
39struct StringUnorderedMapEntryInit
40{
41  template <typename InitType>
42  void operator()(KeyType &pKey, ValueType &pValue,
43                  const KeyType &pStr, InitType pInitVal) {
44    ::new ((void*)&pKey) KeyStorageType(pStr);
45    ::new ((void*)&pValue) ValueType(pInitVal);
46  }
47};
48
49uint32_t findNextPrime(uint32_t x);
50
51/** \class StringUnorderedMap
52 *  \brief The most simple hash of linked list version.
53 *
54 *  \see
55 */
56template<typename KeyType,
57         typename ValueType,
58         typename KeyCompareFunctor,
59         typename HashFunction = StringUnorderedMapDefaultHash,
60         typename Allocator = std::allocator<std::pair<KeyType, ValueType> > >
61class StringUnorderedMap
62{
63public:
64  explicit StringUnorderedMap(size_t pCapacity = 17)
65  : m_Impl(pCapacity)
66  {}
67
68  ~StringUnorderedMap();
69
70  void reserve(size_t pCapacity);
71
72  ValueType &getOrCreate(const KeyType &pStr, const ValueType &pInitVal);
73
74  ValueType &getOrCreate(const KeyType &pStr);
75
76  bool empty()
77  { return m_Size == 0; }
78
79  size_t capacity() const
80  { return m_Capacity; }
81
82  void clear();
83
84private:
85  struct HashEntry {
86    size_t hashVal;
87    std::pair<KeyType, ValueType>
88    HashEntry *next;
89  };
90  typedef Allocator::template rebind<HashEntry>::other HashEntryAllocator;
91  void rehash(size_t pCapacity);
92
93private:
94  size_t m_Capacity;
95  size_t m_Size;
96  // array of pointers to hash entries
97  HashEntry **m_HashTable;
98  HashEntryAllocator m_HashEntryAllocator;
99};
100
101
102// =================================implementation============================
103// StringUnorderedMap::StringUnorderedMapImpl
104template<typename ValueType,
105         typename KeyStorageType,
106         typename HashFunction,
107         typename Allocator>
108StringUnorderedMap<ValueType, KeyStorageType, HashFunction, Allocator>::
109StringUnorderedMapImpl::StringUnorderedMapImpl(size_t pCapacity)
110  : m_Capacity(0), m_Size(0), m_HashTable(0)
111{
112  this->reserve(pCapacity);
113}
114
115template<typename ValueType,
116         typename KeyStorageType,
117         typename HashFunction,
118         typename Allocator>
119void
120StringUnorderedMap<ValueType, KeyStorageType, HashFunction, Allocator>::
121StringUnorderedMapImpl::reserve(size_t pCapacity)
122{
123  if (pCapacity < this->m_Capacity)
124    return;
125  size_t nextSize = findNextPrime(static_cast<uint32_t>(pCapacity));
126  // FIXME: Error handling.
127  assert(nextSize > this->m_Capacity && "findNextPrime error.");
128  if (this->m_Capacity != nextSize)
129    this->rehash(nextSize);
130}
131
132template<typename ValueType,
133         typename KeyStorageType,
134         typename HashFunction,
135         typename Allocator>
136void
137StringUnorderedMap<ValueType, KeyStorageType, HashFunction, Allocator>::
138StringUnorderedMapImpl::rehash(size_t pCapacity)
139{
140  HashEntry **tmpTable = new HashEntry*[pCapacity];
141  std::memset(tmpTable, 0, pCapacity * sizeof(HashEntry*));
142  if (this->m_HashTable) {
143    for (size_t i = 0; i < this->m_Capacity; ++i)
144      for (HashEntry *j = this->m_HashTable[i]; j != 0; ) {
145        HashEntry *nextJ = j->next;
146        j->next = tmpTable[j->hashVal % pCapacity];
147        tmpTable[j->hashVal % pCapacity] = j;
148        j = nextJ;
149      }
150    delete[] m_HashTable;
151  }
152  this->m_Capacity = pCapacity;
153  this->m_HashTable = tmpTable;
154}
155
156template<typename ValueType,
157         typename KeyStorageType,
158         typename HashFunction,
159         typename Allocator>
160template<typename InitType>
161ValueType &
162StringUnorderedMap<ValueType, KeyStorageType, HashFunction, Allocator>::
163StringUnorderedMapImpl::getOrCreate(const KeyType &pStr, ValueType &pInitVal)
164{
165  HashFunction hash;
166  size_t hashVal = hash(pStr);
167  HashEntry *&head =  this->m_HashTable[hashVal % this->m_Capacity];
168
169  HashEntry *ans = 0;
170  for(HashEntry *ptr = head; ptr != 0; ptr = ptr->next)
171    if(hashVal == ptr->hashVal && pStr.equals(ptr->str)) {
172      ans = ptr;
173      break;
174    }
175  if (ans == 0) {
176    ans = this->allocate(1);
177    ans->hashVal = hashVal;
178    StringUnorderedMapEntryInit<ValueType, KeyStorageType> init;
179    init(ans->str, ans->value, pStr, pInitVal);
180    ans->next = head;
181    head = ans;
182    ++m_Size;
183    if(this->m_Size * 4LL >= this->m_Capacity * 3LL) // load factor = 0.75
184      this->reserve(this->m_Capacity+1);
185  }
186
187  return ans->value;
188}
189
190template<typename ValueType,
191         typename KeyStorageType,
192         typename HashFunction,
193         typename Allocator>
194void
195StringUnorderedMap<ValueType, KeyStorageType, HashFunction, Allocator>::
196StringUnorderedMapImpl::clear()
197{
198  if (this->m_HashTable) {
199    for (size_t i = 0; i < this->m_Capacity; ++i)
200      for (HashEntry *j = this->m_HashTable[i]; j != 0; ) {
201        HashEntry *nextJ = j->next;
202        this->destroy(j);
203        this->deallocate(j, 1);
204        j = nextJ;
205      }
206    delete[] m_HashTable;
207  }
208}
209
210
211template<typename ValueType,
212         typename KeyStorageType,
213         typename HashFunction,
214         typename Allocator>
215StringUnorderedMap<ValueType, KeyStorageType, HashFunction, Allocator>::
216StringUnorderedMapImpl::~StringUnorderedMapImpl()
217{
218  this->clear();
219}
220
221
222} // namespace of mcld
223
224#endif
225