]>
Commit | Line | Data |
---|---|---|
b82f782b BK |
1 | // Internal policy header for TR1 unordered_set and unordered_map -*- C++ -*- |
2 | ||
e133ace8 | 3 | // Copyright (C) 2007 Free Software Foundation, Inc. |
b82f782b BK |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the | |
7 | // terms of the GNU General Public License as published by the | |
8 | // Free Software Foundation; either version 2, or (at your option) | |
9 | // any later version. | |
10 | ||
11 | // This library is distributed in the hope that it will be useful, | |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | // GNU General Public License for more details. | |
15 | ||
16 | // You should have received a copy of the GNU General Public License along | |
17 | // with this library; see the file COPYING. If not, write to the Free | |
18 | // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, | |
19 | // USA. | |
20 | ||
21 | // As a special exception, you may use this file as part of a free software | |
22 | // library without restriction. Specifically, if other files instantiate | |
23 | // templates or use macros or inline functions from this file, or you compile | |
24 | // this file and link it with other files to produce an executable, this | |
25 | // file does not by itself cause the resulting executable to be covered by | |
26 | // the GNU General Public License. This exception does not however | |
27 | // invalidate any other reasons why the executable file might be covered by | |
28 | // the GNU General Public License. | |
29 | ||
e133ace8 PC |
30 | /** @file tr1_impl/hashtable_policy.h |
31 | * This is an internal header file, included by other library headers. | |
32 | * You should not attempt to use it directly. | |
b82f782b BK |
33 | */ |
34 | ||
b82f782b BK |
35 | namespace std |
36 | { | |
e133ace8 PC |
37 | _GLIBCXX_BEGIN_NAMESPACE_TR1 |
38 | ||
95cefe5f | 39 | namespace __detail |
b82f782b | 40 | { |
b82f782b BK |
41 | // Helper function: return distance(first, last) for forward |
42 | // iterators, or 0 for input iterators. | |
95cefe5f PC |
43 | template<class _Iterator> |
44 | inline typename std::iterator_traits<_Iterator>::difference_type | |
45 | __distance_fw(_Iterator __first, _Iterator __last, | |
46 | std::input_iterator_tag) | |
b82f782b BK |
47 | { return 0; } |
48 | ||
95cefe5f PC |
49 | template<class _Iterator> |
50 | inline typename std::iterator_traits<_Iterator>::difference_type | |
51 | __distance_fw(_Iterator __first, _Iterator __last, | |
52 | std::forward_iterator_tag) | |
53 | { return std::distance(__first, __last); } | |
b82f782b | 54 | |
95cefe5f PC |
55 | template<class _Iterator> |
56 | inline typename std::iterator_traits<_Iterator>::difference_type | |
57 | __distance_fw(_Iterator __first, _Iterator __last) | |
b82f782b | 58 | { |
95cefe5f PC |
59 | typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag; |
60 | return __distance_fw(__first, __last, _Tag()); | |
b82f782b BK |
61 | } |
62 | ||
95cefe5f | 63 | // XXX This is a hack. _Prime_rehash_policy's member functions, and |
b82f782b BK |
64 | // certainly the list of primes, should be defined in a .cc file. |
65 | // We're temporarily putting them in a header because we don't have a | |
66 | // place to put TR1 .cc files yet. There's no good reason for any of | |
95cefe5f PC |
67 | // _Prime_rehash_policy's member functions to be inline, and there's |
68 | // certainly no good reason for _Primes<> to exist at all. | |
95cefe5f PC |
69 | template<int __ulongsize = sizeof(unsigned long)> |
70 | struct _Primes | |
b82f782b | 71 | { |
95cefe5f PC |
72 | static const int __n_primes = __ulongsize != 8 ? 256 : 256 + 48; |
73 | static const unsigned long __primes[256 + 48 + 1]; | |
b82f782b BK |
74 | }; |
75 | ||
95cefe5f PC |
76 | template<int __ulongsize> |
77 | const int _Primes<__ulongsize>::__n_primes; | |
b82f782b | 78 | |
95cefe5f PC |
79 | template<int __ulongsize> |
80 | const unsigned long _Primes<__ulongsize>::__primes[256 + 48 + 1] = | |
b82f782b BK |
81 | { |
82 | 2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul, | |
83 | 37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul, | |
84 | 83ul, 89ul, 97ul, 103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul, | |
85 | 157ul, 167ul, 179ul, 193ul, 199ul, 211ul, 227ul, 241ul, 257ul, | |
86 | 277ul, 293ul, 313ul, 337ul, 359ul, 383ul, 409ul, 439ul, 467ul, | |
87 | 503ul, 541ul, 577ul, 619ul, 661ul, 709ul, 761ul, 823ul, 887ul, | |
88 | 953ul, 1031ul, 1109ul, 1193ul, 1289ul, 1381ul, 1493ul, 1613ul, | |
89 | 1741ul, 1879ul, 2029ul, 2179ul, 2357ul, 2549ul, 2753ul, 2971ul, | |
90 | 3209ul, 3469ul, 3739ul, 4027ul, 4349ul, 4703ul, 5087ul, 5503ul, | |
91 | 5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul, | |
92 | 11113ul, 12011ul, 12983ul, 14033ul, 15173ul, 16411ul, 17749ul, | |
93 | 19183ul, 20753ul, 22447ul, 24281ul, 26267ul, 28411ul, 30727ul, | |
94 | 33223ul, 35933ul, 38873ul, 42043ul, 45481ul, 49201ul, 53201ul, | |
95 | 57557ul, 62233ul, 67307ul, 72817ul, 78779ul, 85229ul, 92203ul, | |
96 | 99733ul, 107897ul, 116731ul, 126271ul, 136607ul, 147793ul, | |
97 | 159871ul, 172933ul, 187091ul, 202409ul, 218971ul, 236897ul, | |
98 | 256279ul, 277261ul, 299951ul, 324503ul, 351061ul, 379787ul, | |
99 | 410857ul, 444487ul, 480881ul, 520241ul, 562841ul, 608903ul, | |
100 | 658753ul, 712697ul, 771049ul, 834181ul, 902483ul, 976369ul, | |
101 | 1056323ul, 1142821ul, 1236397ul, 1337629ul, 1447153ul, 1565659ul, | |
102 | 1693859ul, 1832561ul, 1982627ul, 2144977ul, 2320627ul, 2510653ul, | |
103 | 2716249ul, 2938679ul, 3179303ul, 3439651ul, 3721303ul, 4026031ul, | |
104 | 4355707ul, 4712381ul, 5098259ul, 5515729ul, 5967347ul, 6456007ul, | |
105 | 6984629ul, 7556579ul, 8175383ul, 8844859ul, 9569143ul, 10352717ul, | |
106 | 11200489ul, 12117689ul, 13109983ul, 14183539ul, 15345007ul, | |
107 | 16601593ul, 17961079ul, 19431899ul, 21023161ul, 22744717ul, | |
108 | 24607243ul, 26622317ul, 28802401ul, 31160981ul, 33712729ul, | |
109 | 36473443ul, 39460231ul, 42691603ul, 46187573ul, 49969847ul, | |
110 | 54061849ul, 58488943ul, 63278561ul, 68460391ul, 74066549ul, | |
111 | 80131819ul, 86693767ul, 93793069ul, 101473717ul, 109783337ul, | |
112 | 118773397ul, 128499677ul, 139022417ul, 150406843ul, 162723577ul, | |
113 | 176048909ul, 190465427ul, 206062531ul, 222936881ul, 241193053ul, | |
114 | 260944219ul, 282312799ul, 305431229ul, 330442829ul, 357502601ul, | |
115 | 386778277ul, 418451333ul, 452718089ul, 489790921ul, 529899637ul, | |
116 | 573292817ul, 620239453ul, 671030513ul, 725980837ul, 785430967ul, | |
117 | 849749479ul, 919334987ul, 994618837ul, 1076067617ul, 1164186217ul, | |
118 | 1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul, | |
119 | 1725587117ul, 1866894511ul, 2019773507ul, 2185171673ul, | |
120 | 2364114217ul, 2557710269ul, 2767159799ul, 2993761039ul, | |
121 | 3238918481ul, 3504151727ul, 3791104843ul, 4101556399ul, | |
122 | 4294967291ul, | |
123 | // Sentinel, so we don't have to test the result of lower_bound, | |
124 | // or, on 64-bit machines, rest of the table. | |
95cefe5f | 125 | __ulongsize != 8 ? 4294967291ul : (unsigned long)6442450933ull, |
b82f782b BK |
126 | (unsigned long)8589934583ull, |
127 | (unsigned long)12884901857ull, (unsigned long)17179869143ull, | |
128 | (unsigned long)25769803693ull, (unsigned long)34359738337ull, | |
129 | (unsigned long)51539607367ull, (unsigned long)68719476731ull, | |
130 | (unsigned long)103079215087ull, (unsigned long)137438953447ull, | |
131 | (unsigned long)206158430123ull, (unsigned long)274877906899ull, | |
132 | (unsigned long)412316860387ull, (unsigned long)549755813881ull, | |
133 | (unsigned long)824633720731ull, (unsigned long)1099511627689ull, | |
134 | (unsigned long)1649267441579ull, (unsigned long)2199023255531ull, | |
135 | (unsigned long)3298534883309ull, (unsigned long)4398046511093ull, | |
136 | (unsigned long)6597069766607ull, (unsigned long)8796093022151ull, | |
137 | (unsigned long)13194139533241ull, (unsigned long)17592186044399ull, | |
138 | (unsigned long)26388279066581ull, (unsigned long)35184372088777ull, | |
139 | (unsigned long)52776558133177ull, (unsigned long)70368744177643ull, | |
140 | (unsigned long)105553116266399ull, (unsigned long)140737488355213ull, | |
141 | (unsigned long)211106232532861ull, (unsigned long)281474976710597ull, | |
142 | (unsigned long)562949953421231ull, (unsigned long)1125899906842597ull, | |
143 | (unsigned long)2251799813685119ull, (unsigned long)4503599627370449ull, | |
144 | (unsigned long)9007199254740881ull, (unsigned long)18014398509481951ull, | |
145 | (unsigned long)36028797018963913ull, (unsigned long)72057594037927931ull, | |
146 | (unsigned long)144115188075855859ull, | |
147 | (unsigned long)288230376151711717ull, | |
148 | (unsigned long)576460752303423433ull, | |
149 | (unsigned long)1152921504606846883ull, | |
150 | (unsigned long)2305843009213693951ull, | |
151 | (unsigned long)4611686018427387847ull, | |
152 | (unsigned long)9223372036854775783ull, | |
153 | (unsigned long)18446744073709551557ull, | |
154 | (unsigned long)18446744073709551557ull | |
155 | }; | |
b82f782b | 156 | |
95cefe5f | 157 | // Auxiliary types used for all instantiations of _Hashtable: nodes |
b82f782b BK |
158 | // and iterators. |
159 | ||
160 | // Nodes, used to wrap elements stored in the hash table. A policy | |
95cefe5f | 161 | // template parameter of class template _Hashtable controls whether |
b82f782b BK |
162 | // nodes also store a hash code. In some cases (e.g. strings) this |
163 | // may be a performance win. | |
95cefe5f PC |
164 | template<typename _Value, bool __cache_hash_code> |
165 | struct _Hash_node; | |
b82f782b | 166 | |
95cefe5f PC |
167 | template<typename _Value> |
168 | struct _Hash_node<_Value, true> | |
b82f782b | 169 | { |
95cefe5f PC |
170 | _Value _M_v; |
171 | std::size_t _M_hash_code; | |
172 | _Hash_node* _M_next; | |
b82f782b BK |
173 | }; |
174 | ||
95cefe5f PC |
175 | template<typename _Value> |
176 | struct _Hash_node<_Value, false> | |
b82f782b | 177 | { |
95cefe5f PC |
178 | _Value _M_v; |
179 | _Hash_node* _M_next; | |
b82f782b BK |
180 | }; |
181 | ||
182 | // Local iterators, used to iterate within a bucket but not between | |
183 | // buckets. | |
95cefe5f PC |
184 | template<typename _Value, bool __cache> |
185 | struct _Node_iterator_base | |
b82f782b | 186 | { |
95cefe5f PC |
187 | _Node_iterator_base(_Hash_node<_Value, __cache>* __p) |
188 | : _M_cur(__p) { } | |
b82f782b BK |
189 | |
190 | void | |
95cefe5f PC |
191 | _M_incr() |
192 | { _M_cur = _M_cur->_M_next; } | |
b82f782b | 193 | |
95cefe5f | 194 | _Hash_node<_Value, __cache>* _M_cur; |
b82f782b BK |
195 | }; |
196 | ||
95cefe5f | 197 | template<typename _Value, bool __cache> |
b82f782b | 198 | inline bool |
95cefe5f PC |
199 | operator==(const _Node_iterator_base<_Value, __cache>& __x, |
200 | const _Node_iterator_base<_Value, __cache>& __y) | |
201 | { return __x._M_cur == __y._M_cur; } | |
b82f782b | 202 | |
95cefe5f | 203 | template<typename _Value, bool __cache> |
b82f782b | 204 | inline bool |
95cefe5f PC |
205 | operator!=(const _Node_iterator_base<_Value, __cache>& __x, |
206 | const _Node_iterator_base<_Value, __cache>& __y) | |
207 | { return __x._M_cur != __y._M_cur; } | |
b82f782b | 208 | |
95cefe5f PC |
209 | template<typename _Value, bool __constant_iterators, bool __cache> |
210 | struct _Node_iterator | |
211 | : public _Node_iterator_base<_Value, __cache> | |
b82f782b | 212 | { |
95cefe5f PC |
213 | typedef _Value value_type; |
214 | typedef typename | |
215 | __gnu_cxx::__conditional_type<__constant_iterators, | |
216 | const _Value*, _Value*>::__type | |
b82f782b | 217 | pointer; |
95cefe5f PC |
218 | typedef typename |
219 | __gnu_cxx::__conditional_type<__constant_iterators, | |
220 | const _Value&, _Value&>::__type | |
b82f782b BK |
221 | reference; |
222 | typedef std::ptrdiff_t difference_type; | |
223 | typedef std::forward_iterator_tag iterator_category; | |
224 | ||
95cefe5f PC |
225 | _Node_iterator() |
226 | : _Node_iterator_base<_Value, __cache>(0) { } | |
b82f782b BK |
227 | |
228 | explicit | |
95cefe5f PC |
229 | _Node_iterator(_Hash_node<_Value, __cache>* __p) |
230 | : _Node_iterator_base<_Value, __cache>(__p) { } | |
b82f782b BK |
231 | |
232 | reference | |
233 | operator*() const | |
95cefe5f | 234 | { return this->_M_cur->_M_v; } |
b82f782b BK |
235 | |
236 | pointer | |
237 | operator->() const | |
95cefe5f | 238 | { return &this->_M_cur->_M_v; } |
b82f782b | 239 | |
95cefe5f | 240 | _Node_iterator& |
b82f782b BK |
241 | operator++() |
242 | { | |
95cefe5f | 243 | this->_M_incr(); |
b82f782b BK |
244 | return *this; |
245 | } | |
246 | ||
95cefe5f | 247 | _Node_iterator |
b82f782b BK |
248 | operator++(int) |
249 | { | |
95cefe5f PC |
250 | _Node_iterator __tmp(*this); |
251 | this->_M_incr(); | |
252 | return __tmp; | |
b82f782b BK |
253 | } |
254 | }; | |
255 | ||
95cefe5f PC |
256 | template<typename _Value, bool __constant_iterators, bool __cache> |
257 | struct _Node_const_iterator | |
258 | : public _Node_iterator_base<_Value, __cache> | |
b82f782b | 259 | { |
95cefe5f PC |
260 | typedef _Value value_type; |
261 | typedef const _Value* pointer; | |
262 | typedef const _Value& reference; | |
b82f782b BK |
263 | typedef std::ptrdiff_t difference_type; |
264 | typedef std::forward_iterator_tag iterator_category; | |
265 | ||
95cefe5f PC |
266 | _Node_const_iterator() |
267 | : _Node_iterator_base<_Value, __cache>(0) { } | |
b82f782b BK |
268 | |
269 | explicit | |
95cefe5f PC |
270 | _Node_const_iterator(_Hash_node<_Value, __cache>* __p) |
271 | : _Node_iterator_base<_Value, __cache>(__p) { } | |
b82f782b | 272 | |
95cefe5f PC |
273 | _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators, |
274 | __cache>& __x) | |
275 | : _Node_iterator_base<_Value, __cache>(__x._M_cur) { } | |
b82f782b BK |
276 | |
277 | reference | |
278 | operator*() const | |
95cefe5f | 279 | { return this->_M_cur->_M_v; } |
b82f782b BK |
280 | |
281 | pointer | |
282 | operator->() const | |
95cefe5f | 283 | { return &this->_M_cur->_M_v; } |
b82f782b | 284 | |
95cefe5f | 285 | _Node_const_iterator& |
b82f782b BK |
286 | operator++() |
287 | { | |
95cefe5f | 288 | this->_M_incr(); |
b82f782b BK |
289 | return *this; |
290 | } | |
291 | ||
95cefe5f | 292 | _Node_const_iterator |
b82f782b BK |
293 | operator++(int) |
294 | { | |
95cefe5f PC |
295 | _Node_const_iterator __tmp(*this); |
296 | this->_M_incr(); | |
297 | return __tmp; | |
b82f782b BK |
298 | } |
299 | }; | |
300 | ||
95cefe5f PC |
301 | template<typename _Value, bool __cache> |
302 | struct _Hashtable_iterator_base | |
b82f782b | 303 | { |
95cefe5f PC |
304 | _Hashtable_iterator_base(_Hash_node<_Value, __cache>* __node, |
305 | _Hash_node<_Value, __cache>** __bucket) | |
306 | : _M_cur_node(__node), _M_cur_bucket(__bucket) { } | |
b82f782b BK |
307 | |
308 | void | |
95cefe5f | 309 | _M_incr() |
b82f782b | 310 | { |
95cefe5f PC |
311 | _M_cur_node = _M_cur_node->_M_next; |
312 | if (!_M_cur_node) | |
313 | _M_incr_bucket(); | |
b82f782b BK |
314 | } |
315 | ||
316 | void | |
95cefe5f | 317 | _M_incr_bucket(); |
b82f782b | 318 | |
95cefe5f PC |
319 | _Hash_node<_Value, __cache>* _M_cur_node; |
320 | _Hash_node<_Value, __cache>** _M_cur_bucket; | |
b82f782b BK |
321 | }; |
322 | ||
323 | // Global iterators, used for arbitrary iteration within a hash | |
324 | // table. Larger and more expensive than local iterators. | |
95cefe5f | 325 | template<typename _Value, bool __cache> |
b82f782b | 326 | void |
95cefe5f PC |
327 | _Hashtable_iterator_base<_Value, __cache>:: |
328 | _M_incr_bucket() | |
b82f782b | 329 | { |
95cefe5f | 330 | ++_M_cur_bucket; |
b82f782b BK |
331 | |
332 | // This loop requires the bucket array to have a non-null sentinel. | |
95cefe5f PC |
333 | while (!*_M_cur_bucket) |
334 | ++_M_cur_bucket; | |
335 | _M_cur_node = *_M_cur_bucket; | |
b82f782b BK |
336 | } |
337 | ||
95cefe5f | 338 | template<typename _Value, bool __cache> |
b82f782b | 339 | inline bool |
95cefe5f PC |
340 | operator==(const _Hashtable_iterator_base<_Value, __cache>& __x, |
341 | const _Hashtable_iterator_base<_Value, __cache>& __y) | |
342 | { return __x._M_cur_node == __y._M_cur_node; } | |
b82f782b | 343 | |
95cefe5f | 344 | template<typename _Value, bool __cache> |
b82f782b | 345 | inline bool |
95cefe5f PC |
346 | operator!=(const _Hashtable_iterator_base<_Value, __cache>& __x, |
347 | const _Hashtable_iterator_base<_Value, __cache>& __y) | |
348 | { return __x._M_cur_node != __y._M_cur_node; } | |
b82f782b | 349 | |
95cefe5f PC |
350 | template<typename _Value, bool __constant_iterators, bool __cache> |
351 | struct _Hashtable_iterator | |
352 | : public _Hashtable_iterator_base<_Value, __cache> | |
b82f782b | 353 | { |
95cefe5f PC |
354 | typedef _Value value_type; |
355 | typedef typename | |
356 | __gnu_cxx::__conditional_type<__constant_iterators, | |
357 | const _Value*, _Value*>::__type | |
b82f782b | 358 | pointer; |
95cefe5f PC |
359 | typedef typename |
360 | __gnu_cxx::__conditional_type<__constant_iterators, | |
361 | const _Value&, _Value&>::__type | |
b82f782b BK |
362 | reference; |
363 | typedef std::ptrdiff_t difference_type; | |
364 | typedef std::forward_iterator_tag iterator_category; | |
365 | ||
95cefe5f PC |
366 | _Hashtable_iterator() |
367 | : _Hashtable_iterator_base<_Value, __cache>(0, 0) { } | |
b82f782b | 368 | |
95cefe5f PC |
369 | _Hashtable_iterator(_Hash_node<_Value, __cache>* __p, |
370 | _Hash_node<_Value, __cache>** __b) | |
371 | : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { } | |
b82f782b BK |
372 | |
373 | explicit | |
95cefe5f PC |
374 | _Hashtable_iterator(_Hash_node<_Value, __cache>** __b) |
375 | : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { } | |
b82f782b BK |
376 | |
377 | reference | |
378 | operator*() const | |
95cefe5f | 379 | { return this->_M_cur_node->_M_v; } |
b82f782b BK |
380 | |
381 | pointer | |
382 | operator->() const | |
95cefe5f | 383 | { return &this->_M_cur_node->_M_v; } |
b82f782b | 384 | |
95cefe5f | 385 | _Hashtable_iterator& |
b82f782b BK |
386 | operator++() |
387 | { | |
95cefe5f | 388 | this->_M_incr(); |
b82f782b BK |
389 | return *this; |
390 | } | |
391 | ||
95cefe5f | 392 | _Hashtable_iterator |
b82f782b BK |
393 | operator++(int) |
394 | { | |
95cefe5f PC |
395 | _Hashtable_iterator __tmp(*this); |
396 | this->_M_incr(); | |
397 | return __tmp; | |
b82f782b BK |
398 | } |
399 | }; | |
400 | ||
95cefe5f PC |
401 | template<typename _Value, bool __constant_iterators, bool __cache> |
402 | struct _Hashtable_const_iterator | |
403 | : public _Hashtable_iterator_base<_Value, __cache> | |
b82f782b | 404 | { |
95cefe5f PC |
405 | typedef _Value value_type; |
406 | typedef const _Value* pointer; | |
407 | typedef const _Value& reference; | |
b82f782b BK |
408 | typedef std::ptrdiff_t difference_type; |
409 | typedef std::forward_iterator_tag iterator_category; | |
410 | ||
95cefe5f PC |
411 | _Hashtable_const_iterator() |
412 | : _Hashtable_iterator_base<_Value, __cache>(0, 0) { } | |
b82f782b | 413 | |
95cefe5f PC |
414 | _Hashtable_const_iterator(_Hash_node<_Value, __cache>* __p, |
415 | _Hash_node<_Value, __cache>** __b) | |
416 | : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { } | |
b82f782b BK |
417 | |
418 | explicit | |
95cefe5f PC |
419 | _Hashtable_const_iterator(_Hash_node<_Value, __cache>** __b) |
420 | : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { } | |
b82f782b | 421 | |
95cefe5f PC |
422 | _Hashtable_const_iterator(const _Hashtable_iterator<_Value, |
423 | __constant_iterators, __cache>& __x) | |
424 | : _Hashtable_iterator_base<_Value, __cache>(__x._M_cur_node, | |
425 | __x._M_cur_bucket) { } | |
b82f782b BK |
426 | |
427 | reference | |
428 | operator*() const | |
95cefe5f | 429 | { return this->_M_cur_node->_M_v; } |
b82f782b BK |
430 | |
431 | pointer | |
432 | operator->() const | |
95cefe5f | 433 | { return &this->_M_cur_node->_M_v; } |
b82f782b | 434 | |
95cefe5f | 435 | _Hashtable_const_iterator& |
b82f782b BK |
436 | operator++() |
437 | { | |
95cefe5f | 438 | this->_M_incr(); |
b82f782b BK |
439 | return *this; |
440 | } | |
441 | ||
95cefe5f | 442 | _Hashtable_const_iterator |
b82f782b BK |
443 | operator++(int) |
444 | { | |
95cefe5f PC |
445 | _Hashtable_const_iterator __tmp(*this); |
446 | this->_M_incr(); | |
447 | return __tmp; | |
b82f782b BK |
448 | } |
449 | }; | |
450 | ||
451 | ||
95cefe5f | 452 | // Many of class template _Hashtable's template parameters are policy |
b82f782b BK |
453 | // classes. These are defaults for the policies. |
454 | ||
b82f782b BK |
455 | // Default range hashing function: use division to fold a large number |
456 | // into the range [0, N). | |
95cefe5f | 457 | struct _Mod_range_hashing |
b82f782b BK |
458 | { |
459 | typedef std::size_t first_argument_type; | |
460 | typedef std::size_t second_argument_type; | |
461 | typedef std::size_t result_type; | |
462 | ||
463 | result_type | |
95cefe5f PC |
464 | operator()(first_argument_type __num, second_argument_type __den) const |
465 | { return __num % __den; } | |
b82f782b BK |
466 | }; |
467 | ||
468 | // Default ranged hash function H. In principle it should be a | |
469 | // function object composed from objects of type H1 and H2 such that | |
470 | // h(k, N) = h2(h1(k), N), but that would mean making extra copies of | |
471 | // h1 and h2. So instead we'll just use a tag to tell class template | |
472 | // hashtable to do that composition. | |
95cefe5f | 473 | struct _Default_ranged_hash { }; |
b82f782b BK |
474 | |
475 | // Default value for rehash policy. Bucket size is (usually) the | |
476 | // smallest prime that keeps the load factor small enough. | |
95cefe5f | 477 | struct _Prime_rehash_policy |
b82f782b | 478 | { |
95cefe5f PC |
479 | _Prime_rehash_policy(float __z = 1.0); |
480 | ||
b82f782b BK |
481 | float |
482 | max_load_factor() const; | |
483 | ||
484 | // Return a bucket size no smaller than n. | |
485 | std::size_t | |
95cefe5f | 486 | _M_next_bkt(std::size_t __n) const; |
b82f782b BK |
487 | |
488 | // Return a bucket count appropriate for n elements | |
489 | std::size_t | |
95cefe5f | 490 | _M_bkt_for_elements(std::size_t __n) const; |
b82f782b | 491 | |
95cefe5f PC |
492 | // __n_bkt is current bucket count, __n_elt is current element count, |
493 | // and __n_ins is number of elements to be inserted. Do we need to | |
b82f782b BK |
494 | // increase bucket count? If so, return make_pair(true, n), where n |
495 | // is the new bucket count. If not, return make_pair(false, 0). | |
496 | std::pair<bool, std::size_t> | |
95cefe5f PC |
497 | _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, |
498 | std::size_t __n_ins) const; | |
b82f782b | 499 | |
95cefe5f PC |
500 | float _M_max_load_factor; |
501 | float _M_growth_factor; | |
502 | mutable std::size_t _M_next_resize; | |
b82f782b BK |
503 | }; |
504 | ||
505 | inline | |
95cefe5f PC |
506 | _Prime_rehash_policy:: |
507 | _Prime_rehash_policy(float __z) | |
508 | : _M_max_load_factor(__z), _M_growth_factor(2.f), _M_next_resize(0) | |
b82f782b BK |
509 | { } |
510 | ||
511 | inline float | |
95cefe5f | 512 | _Prime_rehash_policy:: |
b82f782b | 513 | max_load_factor() const |
95cefe5f | 514 | { return _M_max_load_factor; } |
b82f782b BK |
515 | |
516 | // Return a prime no smaller than n. | |
517 | inline std::size_t | |
95cefe5f PC |
518 | _Prime_rehash_policy:: |
519 | _M_next_bkt(std::size_t __n) const | |
b82f782b | 520 | { |
95cefe5f PC |
521 | const unsigned long* const __last = (_Primes<>::__primes |
522 | + _Primes<>::__n_primes); | |
523 | const unsigned long* __p = std::lower_bound(_Primes<>::__primes, __last, | |
524 | __n); | |
525 | _M_next_resize = static_cast<std::size_t>(std::ceil(*__p | |
526 | * _M_max_load_factor)); | |
527 | return *__p; | |
b82f782b BK |
528 | } |
529 | ||
530 | // Return the smallest prime p such that alpha p >= n, where alpha | |
531 | // is the load factor. | |
532 | inline std::size_t | |
95cefe5f PC |
533 | _Prime_rehash_policy:: |
534 | _M_bkt_for_elements(std::size_t __n) const | |
b82f782b | 535 | { |
95cefe5f PC |
536 | const unsigned long* const __last = (_Primes<>::__primes |
537 | + _Primes<>::__n_primes); | |
538 | const float __min_bkts = __n / _M_max_load_factor; | |
539 | const unsigned long* __p = std::lower_bound(_Primes<>::__primes, __last, | |
e78b91ce | 540 | __min_bkts); |
95cefe5f PC |
541 | _M_next_resize = static_cast<std::size_t>(std::ceil(*__p |
542 | * _M_max_load_factor)); | |
543 | return *__p; | |
b82f782b BK |
544 | } |
545 | ||
95cefe5f PC |
546 | // Finds the smallest prime p such that alpha p > __n_elt + __n_ins. |
547 | // If p > __n_bkt, return make_pair(true, p); otherwise return | |
b82f782b | 548 | // make_pair(false, 0). In principle this isn't very different from |
95cefe5f | 549 | // _M_bkt_for_elements. |
b82f782b BK |
550 | |
551 | // The only tricky part is that we're caching the element count at | |
552 | // which we need to rehash, so we don't have to do a floating-point | |
553 | // multiply for every insertion. | |
554 | ||
555 | inline std::pair<bool, std::size_t> | |
95cefe5f PC |
556 | _Prime_rehash_policy:: |
557 | _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, | |
558 | std::size_t __n_ins) const | |
b82f782b | 559 | { |
95cefe5f | 560 | if (__n_elt + __n_ins > _M_next_resize) |
b82f782b | 561 | { |
95cefe5f PC |
562 | float __min_bkts = ((float(__n_ins) + float(__n_elt)) |
563 | / _M_max_load_factor); | |
564 | if (__min_bkts > __n_bkt) | |
b82f782b | 565 | { |
95cefe5f PC |
566 | __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt); |
567 | const unsigned long* const __last = (_Primes<>::__primes | |
568 | + _Primes<>::__n_primes); | |
569 | const unsigned long* __p = std::lower_bound(_Primes<>::__primes, | |
e78b91ce | 570 | __last, __min_bkts); |
95cefe5f PC |
571 | _M_next_resize = |
572 | static_cast<std::size_t>(std::ceil(*__p * _M_max_load_factor)); | |
573 | return std::make_pair(true, *__p); | |
b82f782b BK |
574 | } |
575 | else | |
576 | { | |
95cefe5f PC |
577 | _M_next_resize = |
578 | static_cast<std::size_t>(std::ceil(__n_bkt | |
579 | * _M_max_load_factor)); | |
b82f782b BK |
580 | return std::make_pair(false, 0); |
581 | } | |
582 | } | |
583 | else | |
584 | return std::make_pair(false, 0); | |
585 | } | |
586 | ||
95cefe5f | 587 | // Base classes for std::tr1::_Hashtable. We define these base |
b82f782b BK |
588 | // classes because in some cases we want to do different things |
589 | // depending on the value of a policy class. In some cases the | |
590 | // policy class affects which member functions and nested typedefs | |
591 | // are defined; we handle that by specializing base class templates. | |
592 | // Several of the base class templates need to access other members | |
95cefe5f | 593 | // of class template _Hashtable, so we use the "curiously recurring |
b82f782b BK |
594 | // template pattern" for them. |
595 | ||
95cefe5f | 596 | // class template _Map_base. If the hashtable has a value type of the |
b82f782b BK |
597 | // form pair<T1, T2> and a key extraction policy that returns the |
598 | // first part of the pair, the hashtable gets a mapped_type typedef. | |
599 | // If it satisfies those criteria and also has unique keys, then it | |
600 | // also gets an operator[]. | |
95cefe5f PC |
601 | template<typename _Key, typename _Value, typename _Ex, bool __unique, |
602 | typename _Hashtable> | |
603 | struct _Map_base { }; | |
b82f782b | 604 | |
95cefe5f PC |
605 | template<typename _Key, typename _Pair, typename _Hashtable> |
606 | struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable> | |
b82f782b | 607 | { |
95cefe5f | 608 | typedef typename _Pair::second_type mapped_type; |
b82f782b BK |
609 | }; |
610 | ||
95cefe5f PC |
611 | template<typename _Key, typename _Pair, typename _Hashtable> |
612 | struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable> | |
b82f782b | 613 | { |
95cefe5f | 614 | typedef typename _Pair::second_type mapped_type; |
b82f782b BK |
615 | |
616 | mapped_type& | |
95cefe5f | 617 | operator[](const _Key& __k); |
b82f782b BK |
618 | }; |
619 | ||
95cefe5f PC |
620 | template<typename _Key, typename _Pair, typename _Hashtable> |
621 | typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, | |
622 | true, _Hashtable>::mapped_type& | |
623 | _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: | |
624 | operator[](const _Key& __k) | |
b82f782b | 625 | { |
95cefe5f PC |
626 | _Hashtable* __h = static_cast<_Hashtable*>(this); |
627 | typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); | |
628 | std::size_t __n = __h->_M_bucket_index(__k, __code, | |
629 | __h->_M_bucket_count); | |
630 | ||
631 | typename _Hashtable::_Node* __p = | |
632 | __h->_M_find_node(__h->_M_buckets[__n], __k, __code); | |
633 | if (!__p) | |
634 | return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()), | |
635 | __n, __code)->second; | |
636 | return (__p->_M_v).second; | |
b82f782b BK |
637 | } |
638 | ||
95cefe5f PC |
639 | // class template _Rehash_base. Give hashtable the max_load_factor |
640 | // functions iff the rehash policy is _Prime_rehash_policy. | |
641 | template<typename _RehashPolicy, typename _Hashtable> | |
642 | struct _Rehash_base { }; | |
b82f782b | 643 | |
95cefe5f PC |
644 | template<typename _Hashtable> |
645 | struct _Rehash_base<_Prime_rehash_policy, _Hashtable> | |
b82f782b BK |
646 | { |
647 | float | |
648 | max_load_factor() const | |
649 | { | |
95cefe5f PC |
650 | const _Hashtable* __this = static_cast<const _Hashtable*>(this); |
651 | return __this->__rehash_policy().max_load_factor(); | |
b82f782b BK |
652 | } |
653 | ||
654 | void | |
95cefe5f | 655 | max_load_factor(float __z) |
b82f782b | 656 | { |
95cefe5f PC |
657 | _Hashtable* __this = static_cast<_Hashtable*>(this); |
658 | __this->__rehash_policy(_Prime_rehash_policy(__z)); | |
b82f782b BK |
659 | } |
660 | }; | |
661 | ||
95cefe5f | 662 | // Class template _Hash_code_base. Encapsulates two policy issues that |
b82f782b BK |
663 | // aren't quite orthogonal. |
664 | // (1) the difference between using a ranged hash function and using | |
665 | // the combination of a hash function and a range-hashing function. | |
666 | // In the former case we don't have such things as hash codes, so | |
667 | // we have a dummy type as placeholder. | |
668 | // (2) Whether or not we cache hash codes. Caching hash codes is | |
669 | // meaningless if we have a ranged hash function. | |
670 | // We also put the key extraction and equality comparison function | |
671 | // objects here, for convenience. | |
672 | ||
673 | // Primary template: unused except as a hook for specializations. | |
95cefe5f PC |
674 | template<typename _Key, typename _Value, |
675 | typename _ExtractKey, typename _Equal, | |
676 | typename _H1, typename _H2, typename _Hash, | |
677 | bool __cache_hash_code> | |
678 | struct _Hash_code_base; | |
b82f782b BK |
679 | |
680 | // Specialization: ranged hash function, no caching hash codes. H1 | |
681 | // and H2 are provided but ignored. We define a dummy hash code type. | |
95cefe5f PC |
682 | template<typename _Key, typename _Value, |
683 | typename _ExtractKey, typename _Equal, | |
684 | typename _H1, typename _H2, typename _Hash> | |
685 | struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, | |
686 | _Hash, false> | |
b82f782b BK |
687 | { |
688 | protected: | |
95cefe5f PC |
689 | _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, |
690 | const _H1&, const _H2&, const _Hash& __h) | |
691 | : _M_extract(__ex), _M_eq(__eq), _M_ranged_hash(__h) { } | |
b82f782b | 692 | |
95cefe5f | 693 | typedef void* _Hash_code_type; |
b82f782b | 694 | |
95cefe5f PC |
695 | _Hash_code_type |
696 | _M_hash_code(const _Key& __key) const | |
b82f782b BK |
697 | { return 0; } |
698 | ||
699 | std::size_t | |
95cefe5f PC |
700 | _M_bucket_index(const _Key& __k, _Hash_code_type, |
701 | std::size_t __n) const | |
702 | { return _M_ranged_hash(__k, __n); } | |
b82f782b BK |
703 | |
704 | std::size_t | |
95cefe5f PC |
705 | _M_bucket_index(const _Hash_node<_Value, false>* __p, |
706 | std::size_t __n) const | |
707 | { return _M_ranged_hash(_M_extract(__p->_M_v), __n); } | |
b82f782b BK |
708 | |
709 | bool | |
95cefe5f PC |
710 | _M_compare(const _Key& __k, _Hash_code_type, |
711 | _Hash_node<_Value, false>* __n) const | |
712 | { return _M_eq(__k, _M_extract(__n->_M_v)); } | |
b82f782b BK |
713 | |
714 | void | |
95cefe5f | 715 | _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const |
b82f782b BK |
716 | { } |
717 | ||
718 | void | |
95cefe5f PC |
719 | _M_copy_code(_Hash_node<_Value, false>*, |
720 | const _Hash_node<_Value, false>*) const | |
b82f782b BK |
721 | { } |
722 | ||
723 | void | |
95cefe5f | 724 | _M_swap(_Hash_code_base& __x) |
b82f782b | 725 | { |
95cefe5f PC |
726 | std::swap(_M_extract, __x._M_extract); |
727 | std::swap(_M_eq, __x._M_eq); | |
728 | std::swap(_M_ranged_hash, __x._M_ranged_hash); | |
b82f782b BK |
729 | } |
730 | ||
731 | protected: | |
95cefe5f PC |
732 | _ExtractKey _M_extract; |
733 | _Equal _M_eq; | |
734 | _Hash _M_ranged_hash; | |
b82f782b BK |
735 | }; |
736 | ||
737 | ||
738 | // No specialization for ranged hash function while caching hash codes. | |
739 | // That combination is meaningless, and trying to do it is an error. | |
740 | ||
741 | ||
742 | // Specialization: ranged hash function, cache hash codes. This | |
743 | // combination is meaningless, so we provide only a declaration | |
744 | // and no definition. | |
95cefe5f PC |
745 | template<typename _Key, typename _Value, |
746 | typename _ExtractKey, typename _Equal, | |
747 | typename _H1, typename _H2, typename _Hash> | |
748 | struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, | |
749 | _Hash, true>; | |
b82f782b BK |
750 | |
751 | // Specialization: hash function and range-hashing function, no | |
752 | // caching of hash codes. H is provided but ignored. Provides | |
753 | // typedef and accessor required by TR1. | |
95cefe5f PC |
754 | template<typename _Key, typename _Value, |
755 | typename _ExtractKey, typename _Equal, | |
756 | typename _H1, typename _H2> | |
757 | struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, | |
758 | _Default_ranged_hash, false> | |
b82f782b | 759 | { |
95cefe5f PC |
760 | typedef _H1 hasher; |
761 | ||
b82f782b BK |
762 | hasher |
763 | hash_function() const | |
95cefe5f | 764 | { return _M_h1; } |
b82f782b BK |
765 | |
766 | protected: | |
95cefe5f PC |
767 | _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, |
768 | const _H1& __h1, const _H2& __h2, | |
769 | const _Default_ranged_hash&) | |
770 | : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { } | |
b82f782b | 771 | |
95cefe5f PC |
772 | typedef std::size_t _Hash_code_type; |
773 | ||
774 | _Hash_code_type | |
775 | _M_hash_code(const _Key& __k) const | |
776 | { return _M_h1(__k); } | |
b82f782b BK |
777 | |
778 | std::size_t | |
95cefe5f PC |
779 | _M_bucket_index(const _Key&, _Hash_code_type __c, |
780 | std::size_t __n) const | |
781 | { return _M_h2(__c, __n); } | |
b82f782b BK |
782 | |
783 | std::size_t | |
95cefe5f PC |
784 | _M_bucket_index(const _Hash_node<_Value, false>* __p, |
785 | std::size_t __n) const | |
786 | { return _M_h2(_M_h1(_M_extract(__p->_M_v)), __n); } | |
b82f782b BK |
787 | |
788 | bool | |
95cefe5f PC |
789 | _M_compare(const _Key& __k, _Hash_code_type, |
790 | _Hash_node<_Value, false>* __n) const | |
791 | { return _M_eq(__k, _M_extract(__n->_M_v)); } | |
b82f782b BK |
792 | |
793 | void | |
95cefe5f | 794 | _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const |
b82f782b BK |
795 | { } |
796 | ||
797 | void | |
95cefe5f PC |
798 | _M_copy_code(_Hash_node<_Value, false>*, |
799 | const _Hash_node<_Value, false>*) const | |
b82f782b BK |
800 | { } |
801 | ||
802 | void | |
95cefe5f | 803 | _M_swap(_Hash_code_base& __x) |
b82f782b | 804 | { |
95cefe5f PC |
805 | std::swap(_M_extract, __x._M_extract); |
806 | std::swap(_M_eq, __x._M_eq); | |
807 | std::swap(_M_h1, __x._M_h1); | |
808 | std::swap(_M_h2, __x._M_h2); | |
b82f782b BK |
809 | } |
810 | ||
811 | protected: | |
95cefe5f PC |
812 | _ExtractKey _M_extract; |
813 | _Equal _M_eq; | |
814 | _H1 _M_h1; | |
815 | _H2 _M_h2; | |
b82f782b BK |
816 | }; |
817 | ||
818 | // Specialization: hash function and range-hashing function, | |
819 | // caching hash codes. H is provided but ignored. Provides | |
820 | // typedef and accessor required by TR1. | |
95cefe5f PC |
821 | template<typename _Key, typename _Value, |
822 | typename _ExtractKey, typename _Equal, | |
823 | typename _H1, typename _H2> | |
824 | struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, | |
825 | _Default_ranged_hash, true> | |
b82f782b | 826 | { |
95cefe5f | 827 | typedef _H1 hasher; |
b82f782b BK |
828 | |
829 | hasher | |
830 | hash_function() const | |
95cefe5f | 831 | { return _M_h1; } |
b82f782b BK |
832 | |
833 | protected: | |
95cefe5f PC |
834 | _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, |
835 | const _H1& __h1, const _H2& __h2, | |
836 | const _Default_ranged_hash&) | |
837 | : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { } | |
b82f782b | 838 | |
95cefe5f | 839 | typedef std::size_t _Hash_code_type; |
b82f782b | 840 | |
95cefe5f PC |
841 | _Hash_code_type |
842 | _M_hash_code(const _Key& __k) const | |
843 | { return _M_h1(__k); } | |
b82f782b BK |
844 | |
845 | std::size_t | |
95cefe5f PC |
846 | _M_bucket_index(const _Key&, _Hash_code_type __c, |
847 | std::size_t __n) const | |
848 | { return _M_h2(__c, __n); } | |
b82f782b BK |
849 | |
850 | std::size_t | |
95cefe5f PC |
851 | _M_bucket_index(const _Hash_node<_Value, true>* __p, |
852 | std::size_t __n) const | |
853 | { return _M_h2(__p->_M_hash_code, __n); } | |
b82f782b BK |
854 | |
855 | bool | |
95cefe5f PC |
856 | _M_compare(const _Key& __k, _Hash_code_type __c, |
857 | _Hash_node<_Value, true>* __n) const | |
858 | { return __c == __n->_M_hash_code && _M_eq(__k, _M_extract(__n->_M_v)); } | |
b82f782b BK |
859 | |
860 | void | |
95cefe5f PC |
861 | _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const |
862 | { __n->_M_hash_code = __c; } | |
b82f782b BK |
863 | |
864 | void | |
95cefe5f PC |
865 | _M_copy_code(_Hash_node<_Value, true>* __to, |
866 | const _Hash_node<_Value, true>* __from) const | |
867 | { __to->_M_hash_code = __from->_M_hash_code; } | |
b82f782b BK |
868 | |
869 | void | |
95cefe5f | 870 | _M_swap(_Hash_code_base& __x) |
b82f782b | 871 | { |
95cefe5f PC |
872 | std::swap(_M_extract, __x._M_extract); |
873 | std::swap(_M_eq, __x._M_eq); | |
874 | std::swap(_M_h1, __x._M_h1); | |
875 | std::swap(_M_h2, __x._M_h2); | |
b82f782b BK |
876 | } |
877 | ||
878 | protected: | |
95cefe5f PC |
879 | _ExtractKey _M_extract; |
880 | _Equal _M_eq; | |
881 | _H1 _M_h1; | |
882 | _H2 _M_h2; | |
b82f782b | 883 | }; |
95cefe5f | 884 | } // namespace __detail |
b82f782b | 885 | |
e133ace8 PC |
886 | _GLIBCXX_END_NAMESPACE_TR1 |
887 | } |