Line data Source code
1 : // Author(s): Maurice Laveaux
2 : // Copyright: see the accompanying file COPYING or copy at
3 : // https://github.com/mCRL2org/mCRL2/blob/master/COPYING
4 : //
5 : // Distributed under the Boost Software License, Version 1.0.
6 : // (See accompanying file LICENSE_1_0.txt or copy at
7 : // http://www.boost.org/LICENSE_1_0.txt)
8 : //
9 :
10 : #ifndef MCRL2_UTILITIES_DETAIL_HASHTABLE_H
11 : #define MCRL2_UTILITIES_DETAIL_HASHTABLE_H
12 : #pragma once
13 :
14 : #include "mcrl2/utilities/power_of_two.h"
15 : #include "mcrl2/utilities/hashtable.h" // necessary for header test.
16 : #include "mcrl2/utilities/indexed_set.h" // necessary for header test.
17 :
18 : namespace mcrl2
19 : {
20 : namespace utilities
21 : {
22 :
23 : template <class Key, typename Hash, typename Equals, typename Allocator>
24 732 : inline void hashtable<Key, Hash, Equals, Allocator>::rehash(std::size_t size)
25 : {
26 : // Copy the old hashtable.
27 732 : std::vector<Key> old = std::move(m_hashtable);
28 :
29 732 : m_hashtable = std::vector<Key>(size, nullptr);
30 732 : m_buckets_mask = m_hashtable.size() - 1;
31 :
32 1344220 : for (const Key& key : old)
33 : {
34 1343488 : const std::size_t key_index = get_index(key);
35 1343488 : auto it = begin() + key_index;
36 : // Find the first empty position.
37 4132803 : while (*it != nullptr)
38 : {
39 2789315 : ++it;
40 2789315 : if (it == end())
41 : {
42 0 : it = begin();
43 : }
44 :
45 2789315 : assert(it != begin() + key_index);
46 : }
47 :
48 : // Found an empty spot, insert a new index belonging to key,
49 1343488 : *it = key;
50 : }
51 732 : }
52 :
53 : template <class Key, typename Hash, typename Equals, typename Allocator>
54 288 : inline hashtable<Key,Hash,Equals,Allocator>::hashtable()
55 288 : : hashtable(128)
56 : {
57 288 : }
58 :
59 : template <class Key, typename Hash, typename Equals, typename Allocator>
60 288 : inline hashtable<Key,Hash,Equals,Allocator>::hashtable(std::size_t initial_size,
61 : const hasher& hasher,
62 : const key_equal& equals)
63 288 : : m_hashtable(std::max(initial_size, detail::minimal_hashtable_size), nullptr),
64 : m_hasher(hasher),
65 288 : m_equals(equals)
66 : {
67 288 : assert(utilities::is_power_of_two(initial_size));
68 288 : m_buckets_mask = m_hashtable.size() - 1;
69 288 : }
70 :
71 : template <class Key, typename Hash, typename Equals, typename Allocator>
72 : inline void hashtable<Key,Hash,Equals,Allocator>::clear()
73 : {
74 : m_hashtable.clear();
75 : }
76 :
77 : template <class Key, typename Hash, typename Equals, typename Allocator>
78 43512922472 : bool hashtable<Key,Hash,Equals,Allocator>::must_resize()
79 : {
80 43512922472 : return (2 * m_number_of_elements >= m_hashtable.size());
81 : }
82 :
83 : template <class Key, typename Hash, typename Equals, typename Allocator>
84 732 : void hashtable<Key,Hash,Equals,Allocator>::resize()
85 : {
86 732 : rehash(2 * m_hashtable.size());
87 732 : }
88 :
89 : template <class Key, typename Hash, typename Equals, typename Allocator>
90 21756461236 : inline std::pair<typename hashtable<Key,Hash,Equals,Allocator>::iterator, bool> hashtable<Key,Hash,Equals,Allocator>::insert(const Key& key)
91 : {
92 : // Resize hashtable must be done explicitly.
93 21756461236 : assert(!must_resize());
94 21756461236 : ++m_number_of_elements;
95 :
96 21756461236 : const std::size_t key_index = get_index(key);
97 21756461236 : auto it = begin() + key_index;
98 :
99 : // Find the first empty position.
100 58959333401 : while (*it != nullptr)
101 : {
102 37202872165 : ++it;
103 37202872165 : if (it == end())
104 : {
105 9844 : it = begin();
106 : }
107 :
108 37202872165 : assert(it != begin() + key_index);
109 : }
110 :
111 : // Found an empty spot, insert a new index belonging to key,
112 21756461236 : *it = key;
113 21756461236 : return std::make_pair(it, true);
114 : }
115 :
116 :
117 : template <class Key, typename Hash, typename Equals, typename Allocator>
118 21756418616 : inline typename hashtable<Key,Hash,Equals,Allocator>::iterator hashtable<Key,Hash,Equals,Allocator>::erase(const Key& key)
119 : {
120 21756418616 : const std::size_t key_index = get_index(key);
121 21756418616 : auto it = begin() + key_index;
122 :
123 : // Find the key.
124 58958489769 : while (!m_equals(*it, key))
125 : {
126 37202071153 : ++it;
127 37202071153 : if (it == end())
128 : {
129 9838 : it = begin();
130 : }
131 :
132 37202071153 : if (it == begin() + key_index)
133 : {
134 : // An element not in the hashset is begin removed.
135 : // When optimizing, the gcc compiler tends to generate
136 : // destructions of non generated aterms. If this is
137 : // repaired, this safety escape can be removed.
138 0 : return it;
139 : }
140 37202071153 : assert(it != begin() + key_index);
141 : }
142 :
143 21756418616 : *it = nullptr;
144 21756418616 : --m_number_of_elements;
145 21756418616 : return it;
146 : }
147 :
148 :
149 : template <class Key, typename Hash, typename Equals, typename Allocator>
150 : inline typename hashtable<Key,Hash,Equals,Allocator>::iterator hashtable<Key,Hash,Equals,Allocator>::find(const Key& key)
151 : {
152 : for (auto it = begin(); it != end(); ++it)
153 : {
154 : if (*it == key)
155 : {
156 : return it;
157 : }
158 : }
159 :
160 : return end();
161 : }
162 :
163 : // PRIVATE FUNCTIONS
164 :
165 : template <class Key, typename Hash, typename Equals, typename Allocator>
166 43514223340 : inline std::size_t hashtable<Key,Hash,Equals,Allocator>::get_index(const Key& key)
167 : {
168 43514223340 : return m_hasher(key) & m_buckets_mask;
169 : }
170 :
171 :
172 : } // namespace utilities
173 :
174 : } // namespace mcrl2
175 :
176 : #endif // MCRL2_UTILITIES_DETAIL_INDEXED_SET_H
|
