-
Notifications
You must be signed in to change notification settings - Fork 0
/
hash_table_policy.hpp
177 lines (154 loc) · 7.09 KB
/
hash_table_policy.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#ifndef _ASP_HASH_TABLE_POLICY_HPP_
#define _ASP_HASH_TABLE_POLICY_HPP_
#include <cmath>
#include <cstring>
#include <memory>
#include "node.hpp"
#include "iterator.hpp"
namespace asp {
struct rehash_policy;
template <typename _Tp> struct hash_node;
template <typename _Value, typename _Alloc> struct hash_table_alloc;
struct _ExtractKey;
extern const unsigned long _prime_list[] = {
5ul, 11ul,
23ul, 47ul, 97ul, 193ul, 389ul,
769ul, 1543ul, 3079ul, 6151ul, 12289ul,
24593ul, 49157ul, 98317ul, 196613ul, 393241ul,
786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul,
25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul,
805306457ul, 1610612741ul, 3221225473ul, 4294967291ul
};
struct rehash_policy {
typedef size_type _State;
typedef short bucket_id;
// (0, x) indicates _buckets[x]
// (1, y) indicates _rehash_buckets[y]
typedef std::pair<bucket_id, size_type> bucket_index;
rehash_policy(float _z = 1.0) : _max_load_factor(_z) {}
rehash_policy(bool _enable) : _enable_rehash(_enable) {}
float max_load_factor() const { return _max_load_factor; }
_State state() const { return _next_resize; }
void reset(_State _s = 0) { _next_resize = _s; }
/**
* @param %_n = current number of buckets
* @return the next prime number that \ge %_n
*/
size_type next_bkt(size_type _n) const;
/**
* @param %_n = the number of elements
* @return the least number of buckets, which's able to contain %_n elements.
*/
size_type bkt_for_elements(size_type _n) const;
/**
* @param %_n_bkt = the number of buckets in @hash_table;
* %_n_elt = the number of elements in @hash_table;
* %_n_ins = the number of elements that need to insert.
* @return if rehash is needed，the return (true, new_bucket_count); else return (false, 0)
*/
std::pair<bool, size_type> need_rehash(size_type _n_bkt, size_type _n_elt, size_type _n_ins) const;
enum { _s_primes = sizeof(_prime_list) / sizeof(_prime_list[0]) };
static const size_type _s_growth_factor = 2;
// 负载因子，衡量桶的负载程度
float _max_load_factor = 1.0; // = _n_elt / _n_bkt
// resize 后，能保存元素个数的最佳上限
mutable size_type _next_resize = 0; // = _n_bkt * _max_load_factor
bool _in_rehash = false;
bucket_index _cur_process;
const bool _enable_rehash = true;
};
template <typename _Tp> struct hash_node : public node<_Tp> {
typedef node<_Tp> base;
typedef hash_node<_Tp> self;
typedef _Tp value_type;
typedef _Tp* pointer;
typedef self* bucket_type;
typedef size_type hash_code;
hash_node() : base() {}
hash_node(const value_type& _v): base(_v) {}
template <typename... _Args> hash_node(_Args&&... _args): base(std::forward<_Args>(_args)...) {}
hash_node(const self& r) : base(r), _hash_code(r._hash_code) {}
hash_node(self&& r) : base(std::move(r)), _hash_code(std::move(r._hash_code)) {}
virtual ~hash_node() = default;
self* _next = nullptr;
self* _prev = nullptr;
hash_code _hash_code;
friend bool operator==(const self& _x, const self& _y) {
return _x._hash_code == _y._hash_code && base::operator==(_x, _y);
}
friend bool operator!=(const self& _x, const self& _y) {
return _x._hash_code != _y._hash_code || base::operator!=(_x, _y);
}
};
template <typename _Value, typename _Alloc> struct hash_table_alloc : public _Alloc {
typedef hash_node<_Value> node_type;
typedef typename node_type::value_type value_type;
typedef typename node_type::bucket_type bucket_type;
typedef _Alloc elt_allocator_type;
typedef std::allocator_traits<elt_allocator_type> elt_alloc_traits;
typedef typename elt_alloc_traits::template rebind_alloc<node_type> node_allocator_type;
typedef std::allocator_traits<node_allocator_type> node_alloc_traits;
typedef typename elt_alloc_traits::template rebind_alloc<bucket_type> bucket_allocator_type;
typedef std::allocator_traits<bucket_allocator_type> bucket_alloc_traits;
elt_allocator_type& _M_get_elt_allocator() { return *static_cast<elt_allocator_type*>(this); }
const elt_allocator_type& _M_get_elt_allocator() const { return *static_cast<const elt_allocator_type*>(this); }
node_allocator_type _M_get_node_allocator() const { return node_allocator_type(_M_get_elt_allocator()); }
bucket_allocator_type _M_get_bucket_allocator() const { return bucket_allocator_type(_M_get_elt_allocator()); }
node_type* _M_allocate_node(const node_type& _x) {
node_allocator_type _node_alloc = _M_get_node_allocator();
auto _ptr = node_alloc_traits::allocate(_node_alloc, 1);
node_type* _p = std::addressof(*_ptr);
node_alloc_traits::construct(_node_alloc, _p, _x.val());
_p->_hash_code = _x._hash_code;
return _p;
}
template <typename... _Args> node_type* _M_allocate_node(_Args&&... _args) {
node_allocator_type _node_alloc = _M_get_node_allocator();
auto _ptr = node_alloc_traits::allocate(_node_alloc, 1);
node_type* _p = std::addressof(*_ptr);
node_alloc_traits::construct(_node_alloc, _p, std::forward<_Args>(_args)...);
return _p;
}
void _M_deallocate_node(node_type* _p) {
node_allocator_type _node_alloc = _M_get_node_allocator();
node_alloc_traits::destroy(_node_alloc, _p);
node_alloc_traits::deallocate(_node_alloc, _p, 1);
}
bucket_type* _M_allocate_buckets(size_type _n) {
bucket_allocator_type _bucket_alloc = _M_get_bucket_allocator();
auto _ptr = bucket_alloc_traits::allocate(_bucket_alloc, _n);
bucket_type* _p = std::addressof(*_ptr);
bzero(_p, _n * sizeof(bucket_type));
return _p;
}
void _M_deallocate_buckets(bucket_type* _p, size_type _n) {
bucket_allocator_type _bucket_alloc = _M_get_bucket_allocator();
bucket_alloc_traits::deallocate(_bucket_alloc, _p, _n);
}
};
size_type rehash_policy::next_bkt(size_type _n) const {
const unsigned long *_p = std::lower_bound(_prime_list, _prime_list + _s_primes - 1, _n);
_next_resize = static_cast<size_type>(std::ceil(*_p * _max_load_factor));
return *_p;
}
size_type rehash_policy::bkt_for_elements(size_type _n) const {
return std::ceil(_n / (long double)_max_load_factor);
}
std::pair<bool, size_type> rehash_policy::need_rehash(size_type _n_bkt, size_type _n_elt, size_type _n_ins) const {
if (_n_elt + _n_ins > _next_resize) {
float _min_bkts = ((float(_n_ins) + float(_n_elt)) / _max_load_factor);
if (_min_bkts > _n_bkt) {
_min_bkts = std::max(_min_bkts, float(_s_growth_factor * _n_bkt));
return std::make_pair(_enable_rehash, next_bkt(static_cast<size_type>(std::ceil(_min_bkts))));
}
else {
_next_resize = static_cast<size_type>(std::ceil(_n_bkt * _max_load_factor));
return std::make_pair(false, 0);
}
}
else {
return std::make_pair(false, 0);
}
}
};
#endif // _ASP_HASH_TABLE_POLICY_HPP_