Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
4680 | right-hear | 1 | /* |
2 | * Copyright (c) 1996,1997 |
||
3 | * Silicon Graphics Computer Systems, Inc. |
||
4 | * |
||
5 | * Permission to use, copy, modify, distribute and sell this software |
||
6 | * and its documentation for any purpose is hereby granted without fee, |
||
7 | * provided that the above copyright notice appear in all copies and |
||
8 | * that both that copyright notice and this permission notice appear |
||
9 | * in supporting documentation. Silicon Graphics makes no |
||
10 | * representations about the suitability of this software for any |
||
11 | * purpose. It is provided "as is" without express or implied warranty. |
||
12 | * |
||
13 | * |
||
14 | * Copyright (c) 1994 |
||
15 | * Hewlett-Packard Company |
||
16 | * |
||
17 | * Permission to use, copy, modify, distribute and sell this software |
||
18 | * and its documentation for any purpose is hereby granted without fee, |
||
19 | * provided that the above copyright notice appear in all copies and |
||
20 | * that both that copyright notice and this permission notice appear |
||
21 | * in supporting documentation. Hewlett-Packard Company makes no |
||
22 | * representations about the suitability of this software for any |
||
23 | * purpose. It is provided "as is" without express or implied warranty. |
||
24 | * |
||
25 | */ |
||
26 | |||
27 | /* NOTE: This is an internal header file, included by other STL headers. |
||
28 | * You should not attempt to use it directly. |
||
29 | */ |
||
30 | |||
31 | #ifndef __SGI_STL_INTERNAL_HASHTABLE_H |
||
32 | #define __SGI_STL_INTERNAL_HASHTABLE_H |
||
33 | |||
34 | // Hashtable class, used to implement the hashed associative containers |
||
35 | // hash_set, hash_map, hash_multiset, and hash_multimap. |
||
36 | |||
37 | #include |
||
38 | #include |
||
39 | #include |
||
40 | #include |
||
41 | #include |
||
42 | #include |
||
43 | #include |
||
44 | #include |
||
45 | #include |
||
46 | |||
47 | namespace std |
||
48 | { |
||
49 | |||
50 | template |
||
51 | struct _Hashtable_node |
||
52 | { |
||
53 | _Hashtable_node* _M_next; |
||
54 | _Val _M_val; |
||
55 | }; |
||
56 | |||
57 | template |
||
58 | class _ExtractKey, class _EqualKey, class _Alloc = alloc> |
||
59 | class hashtable; |
||
60 | |||
61 | template |
||
62 | class _ExtractKey, class _EqualKey, class _Alloc> |
||
63 | struct _Hashtable_iterator; |
||
64 | |||
65 | template |
||
66 | class _ExtractKey, class _EqualKey, class _Alloc> |
||
67 | struct _Hashtable_const_iterator; |
||
68 | |||
69 | template |
||
70 | class _ExtractKey, class _EqualKey, class _Alloc> |
||
71 | struct _Hashtable_iterator { |
||
72 | typedef hashtable<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc> |
||
73 | _Hashtable; |
||
74 | typedef _Hashtable_iterator<_Val, _Key, _HashFcn, |
||
75 | _ExtractKey, _EqualKey, _Alloc> |
||
76 | iterator; |
||
77 | typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, |
||
78 | _ExtractKey, _EqualKey, _Alloc> |
||
79 | const_iterator; |
||
80 | typedef _Hashtable_node<_Val> _Node; |
||
81 | |||
82 | typedef forward_iterator_tag iterator_category; |
||
83 | typedef _Val value_type; |
||
84 | typedef ptrdiff_t difference_type; |
||
85 | typedef size_t size_type; |
||
86 | typedef _Val& reference; |
||
87 | typedef _Val* pointer; |
||
88 | |||
89 | _Node* _M_cur; |
||
90 | _Hashtable* _M_ht; |
||
91 | |||
92 | _Hashtable_iterator(_Node* __n, _Hashtable* __tab) |
||
93 | : _M_cur(__n), _M_ht(__tab) {} |
||
94 | _Hashtable_iterator() {} |
||
95 | reference operator*() const { return _M_cur->_M_val; } |
||
96 | pointer operator->() const { return &(operator*()); } |
||
97 | iterator& operator++(); |
||
98 | iterator operator++(int); |
||
99 | bool operator==(const iterator& __it) const |
||
100 | { return _M_cur == __it._M_cur; } |
||
101 | bool operator!=(const iterator& __it) const |
||
102 | { return _M_cur != __it._M_cur; } |
||
103 | }; |
||
104 | |||
105 | |||
106 | template |
||
107 | class _ExtractKey, class _EqualKey, class _Alloc> |
||
108 | struct _Hashtable_const_iterator { |
||
109 | typedef hashtable<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc> |
||
110 | _Hashtable; |
||
111 | typedef _Hashtable_iterator<_Val,_Key,_HashFcn, |
||
112 | _ExtractKey,_EqualKey,_Alloc> |
||
113 | iterator; |
||
114 | typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, |
||
115 | _ExtractKey, _EqualKey, _Alloc> |
||
116 | const_iterator; |
||
117 | typedef _Hashtable_node<_Val> _Node; |
||
118 | |||
119 | typedef forward_iterator_tag iterator_category; |
||
120 | typedef _Val value_type; |
||
121 | typedef ptrdiff_t difference_type; |
||
122 | typedef size_t size_type; |
||
123 | typedef const _Val& reference; |
||
124 | typedef const _Val* pointer; |
||
125 | |||
126 | const _Node* _M_cur; |
||
127 | const _Hashtable* _M_ht; |
||
128 | |||
129 | _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab) |
||
130 | : _M_cur(__n), _M_ht(__tab) {} |
||
131 | _Hashtable_const_iterator() {} |
||
132 | _Hashtable_const_iterator(const iterator& __it) |
||
133 | : _M_cur(__it._M_cur), _M_ht(__it._M_ht) {} |
||
134 | reference operator*() const { return _M_cur->_M_val; } |
||
135 | pointer operator->() const { return &(operator*()); } |
||
136 | const_iterator& operator++(); |
||
137 | const_iterator operator++(int); |
||
138 | bool operator==(const const_iterator& __it) const |
||
139 | { return _M_cur == __it._M_cur; } |
||
140 | bool operator!=(const const_iterator& __it) const |
||
141 | { return _M_cur != __it._M_cur; } |
||
142 | }; |
||
143 | |||
144 | // Note: assumes long is at least 32 bits. |
||
145 | enum { __stl_num_primes = 28 }; |
||
146 | |||
147 | static const unsigned long __stl_prime_list[__stl_num_primes] = |
||
148 | { |
||
149 | 53ul, 97ul, 193ul, 389ul, 769ul, |
||
150 | 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, |
||
151 | 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, |
||
152 | 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, |
||
153 | 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, |
||
154 | 1610612741ul, 3221225473ul, 4294967291ul |
||
155 | }; |
||
156 | |||
157 | inline unsigned long __stl_next_prime(unsigned long __n) |
||
158 | { |
||
159 | const unsigned long* __first = __stl_prime_list; |
||
160 | const unsigned long* __last = __stl_prime_list + (int)__stl_num_primes; |
||
161 | const unsigned long* pos = lower_bound(__first, __last, __n); |
||
162 | return pos == __last ? *(__last - 1) : *pos; |
||
163 | } |
||
164 | |||
165 | // Forward declaration of operator==. |
||
166 | |||
167 | template |
||
168 | class hashtable; |
||
169 | |||
170 | template |
||
171 | bool operator==(const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht1, |
||
172 | const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht2); |
||
173 | |||
174 | |||
175 | // Hashtables handle allocators a bit differently than other containers |
||
176 | // do. If we're using standard-conforming allocators, then a hashtable |
||
177 | // unconditionally has a member variable to hold its allocator, even if |
||
178 | // it so happens that all instances of the allocator type are identical. |
||
179 | // This is because, for hashtables, this extra storage is negligible. |
||
180 | // Additionally, a base class wouldn't serve any other purposes; it |
||
181 | // wouldn't, for example, simplify the exception-handling code. |
||
182 | |||
183 | template |
||
184 | class _ExtractKey, class _EqualKey, class _Alloc> |
||
185 | class hashtable { |
||
186 | public: |
||
187 | typedef _Key key_type; |
||
188 | typedef _Val value_type; |
||
189 | typedef _HashFcn hasher; |
||
190 | typedef _EqualKey key_equal; |
||
191 | |||
192 | typedef size_t size_type; |
||
193 | typedef ptrdiff_t difference_type; |
||
194 | typedef value_type* pointer; |
||
195 | typedef const value_type* const_pointer; |
||
196 | typedef value_type& reference; |
||
197 | typedef const value_type& const_reference; |
||
198 | |||
199 | hasher hash_funct() const { return _M_hash; } |
||
200 | key_equal key_eq() const { return _M_equals; } |
||
201 | |||
202 | private: |
||
203 | typedef _Hashtable_node<_Val> _Node; |
||
204 | |||
205 | public: |
||
206 | typedef typename _Alloc_traits<_Val,_Alloc>::allocator_type allocator_type; |
||
207 | allocator_type get_allocator() const { return _M_node_allocator; } |
||
208 | private: |
||
209 | typename _Alloc_traits<_Node, _Alloc>::allocator_type _M_node_allocator; |
||
210 | _Node* _M_get_node() { return _M_node_allocator.allocate(1); } |
||
211 | void _M_put_node(_Node* __p) { _M_node_allocator.deallocate(__p, 1); } |
||
212 | |||
213 | private: |
||
214 | hasher _M_hash; |
||
215 | key_equal _M_equals; |
||
216 | _ExtractKey _M_get_key; |
||
217 | vector<_Node*,_Alloc> _M_buckets; |
||
218 | size_type _M_num_elements; |
||
219 | |||
220 | public: |
||
221 | typedef _Hashtable_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc> |
||
222 | iterator; |
||
223 | typedef _Hashtable_const_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey, |
||
224 | _Alloc> |
||
225 | const_iterator; |
||
226 | |||
227 | friend struct |
||
228 | _Hashtable_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>; |
||
229 | friend struct |
||
230 | _Hashtable_const_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>; |
||
231 | |||
232 | public: |
||
233 | hashtable(size_type __n, |
||
234 | const _HashFcn& __hf, |
||
235 | const _EqualKey& __eql, |
||
236 | const _ExtractKey& __ext, |
||
237 | const allocator_type& __a = allocator_type()) |
||
238 | : _M_node_allocator(__a), |
||
239 | _M_hash(__hf), |
||
240 | _M_equals(__eql), |
||
241 | _M_get_key(__ext), |
||
242 | _M_buckets(__a), |
||
243 | _M_num_elements(0) |
||
244 | { |
||
245 | _M_initialize_buckets(__n); |
||
246 | } |
||
247 | |||
248 | hashtable(size_type __n, |
||
249 | const _HashFcn& __hf, |
||
250 | const _EqualKey& __eql, |
||
251 | const allocator_type& __a = allocator_type()) |
||
252 | : _M_node_allocator(__a), |
||
253 | _M_hash(__hf), |
||
254 | _M_equals(__eql), |
||
255 | _M_get_key(_ExtractKey()), |
||
256 | _M_buckets(__a), |
||
257 | _M_num_elements(0) |
||
258 | { |
||
259 | _M_initialize_buckets(__n); |
||
260 | } |
||
261 | |||
262 | hashtable(const hashtable& __ht) |
||
263 | : _M_node_allocator(__ht.get_allocator()), |
||
264 | _M_hash(__ht._M_hash), |
||
265 | _M_equals(__ht._M_equals), |
||
266 | _M_get_key(__ht._M_get_key), |
||
267 | _M_buckets(__ht.get_allocator()), |
||
268 | _M_num_elements(0) |
||
269 | { |
||
270 | _M_copy_from(__ht); |
||
271 | } |
||
272 | |||
273 | hashtable& operator= (const hashtable& __ht) |
||
274 | { |
||
275 | if (&__ht != this) { |
||
276 | clear(); |
||
277 | _M_hash = __ht._M_hash; |
||
278 | _M_equals = __ht._M_equals; |
||
279 | _M_get_key = __ht._M_get_key; |
||
280 | _M_copy_from(__ht); |
||
281 | } |
||
282 | return *this; |
||
283 | } |
||
284 | |||
285 | ~hashtable() { clear(); } |
||
286 | |||
287 | size_type size() const { return _M_num_elements; } |
||
288 | size_type max_size() const { return size_type(-1); } |
||
289 | bool empty() const { return size() == 0; } |
||
290 | |||
291 | void swap(hashtable& __ht) |
||
292 | { |
||
293 | std::swap(_M_hash, __ht._M_hash); |
||
294 | std::swap(_M_equals, __ht._M_equals); |
||
295 | std::swap(_M_get_key, __ht._M_get_key); |
||
296 | _M_buckets.swap(__ht._M_buckets); |
||
297 | std::swap(_M_num_elements, __ht._M_num_elements); |
||
298 | } |
||
299 | |||
300 | iterator begin() |
||
301 | { |
||
302 | for (size_type __n = 0; __n < _M_buckets.size(); ++__n) |
||
303 | if (_M_buckets[__n]) |
||
304 | return iterator(_M_buckets[__n], this); |
||
305 | return end(); |
||
306 | } |
||
307 | |||
308 | iterator end() { return iterator(0, this); } |
||
309 | |||
310 | const_iterator begin() const |
||
311 | { |
||
312 | for (size_type __n = 0; __n < _M_buckets.size(); ++__n) |
||
313 | if (_M_buckets[__n]) |
||
314 | return const_iterator(_M_buckets[__n], this); |
||
315 | return end(); |
||
316 | } |
||
317 | |||
318 | const_iterator end() const { return const_iterator(0, this); } |
||
319 | |||
320 | template |
||
321 | friend bool operator== (const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&, |
||
322 | const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&); |
||
323 | public: |
||
324 | |||
325 | size_type bucket_count() const { return _M_buckets.size(); } |
||
326 | |||
327 | size_type max_bucket_count() const |
||
328 | { return __stl_prime_list[(int)__stl_num_primes - 1]; } |
||
329 | |||
330 | size_type elems_in_bucket(size_type __bucket) const |
||
331 | { |
||
332 | size_type __result = 0; |
||
333 | for (_Node* __cur = _M_buckets[__bucket]; __cur; __cur = __cur->_M_next) |
||
334 | __result += 1; |
||
335 | return __result; |
||
336 | } |
||
337 | |||
338 | pair |
||
339 | { |
||
340 | resize(_M_num_elements + 1); |
||
341 | return insert_unique_noresize(__obj); |
||
342 | } |
||
343 | |||
344 | iterator insert_equal(const value_type& __obj) |
||
345 | { |
||
346 | resize(_M_num_elements + 1); |
||
347 | return insert_equal_noresize(__obj); |
||
348 | } |
||
349 | |||
350 | pair |
||
351 | iterator insert_equal_noresize(const value_type& __obj); |
||
352 | |||
353 | template |
||
354 | void insert_unique(_InputIterator __f, _InputIterator __l) |
||
355 | { |
||
356 | insert_unique(__f, __l, __iterator_category(__f)); |
||
357 | } |
||
358 | |||
359 | template |
||
360 | void insert_equal(_InputIterator __f, _InputIterator __l) |
||
361 | { |
||
362 | insert_equal(__f, __l, __iterator_category(__f)); |
||
363 | } |
||
364 | |||
365 | template |
||
366 | void insert_unique(_InputIterator __f, _InputIterator __l, |
||
367 | input_iterator_tag) |
||
368 | { |
||
369 | for ( ; __f != __l; ++__f) |
||
370 | insert_unique(*__f); |
||
371 | } |
||
372 | |||
373 | template |
||
374 | void insert_equal(_InputIterator __f, _InputIterator __l, |
||
375 | input_iterator_tag) |
||
376 | { |
||
377 | for ( ; __f != __l; ++__f) |
||
378 | insert_equal(*__f); |
||
379 | } |
||
380 | |||
381 | template |
||
382 | void insert_unique(_ForwardIterator __f, _ForwardIterator __l, |
||
383 | forward_iterator_tag) |
||
384 | { |
||
385 | size_type __n = 0; |
||
386 | distance(__f, __l, __n); |
||
387 | resize(_M_num_elements + __n); |
||
388 | for ( ; __n > 0; --__n, ++__f) |
||
389 | insert_unique_noresize(*__f); |
||
390 | } |
||
391 | |||
392 | template |
||
393 | void insert_equal(_ForwardIterator __f, _ForwardIterator __l, |
||
394 | forward_iterator_tag) |
||
395 | { |
||
396 | size_type __n = 0; |
||
397 | distance(__f, __l, __n); |
||
398 | resize(_M_num_elements + __n); |
||
399 | for ( ; __n > 0; --__n, ++__f) |
||
400 | insert_equal_noresize(*__f); |
||
401 | } |
||
402 | |||
403 | reference find_or_insert(const value_type& __obj); |
||
404 | |||
405 | iterator find(const key_type& __key) |
||
406 | { |
||
407 | size_type __n = _M_bkt_num_key(__key); |
||
408 | _Node* __first; |
||
409 | for ( __first = _M_buckets[__n]; |
||
410 | __first && !_M_equals(_M_get_key(__first->_M_val), __key); |
||
411 | __first = __first->_M_next) |
||
412 | {} |
||
413 | return iterator(__first, this); |
||
414 | } |
||
415 | |||
416 | const_iterator find(const key_type& __key) const |
||
417 | { |
||
418 | size_type __n = _M_bkt_num_key(__key); |
||
419 | const _Node* __first; |
||
420 | for ( __first = _M_buckets[__n]; |
||
421 | __first && !_M_equals(_M_get_key(__first->_M_val), __key); |
||
422 | __first = __first->_M_next) |
||
423 | {} |
||
424 | return const_iterator(__first, this); |
||
425 | } |
||
426 | |||
427 | size_type count(const key_type& __key) const |
||
428 | { |
||
429 | const size_type __n = _M_bkt_num_key(__key); |
||
430 | size_type __result = 0; |
||
431 | |||
432 | for (const _Node* __cur = _M_buckets[__n]; __cur; __cur = __cur->_M_next) |
||
433 | if (_M_equals(_M_get_key(__cur->_M_val), __key)) |
||
434 | ++__result; |
||
435 | return __result; |
||
436 | } |
||
437 | |||
438 | pair |
||
439 | equal_range(const key_type& __key); |
||
440 | |||
441 | pair |
||
442 | equal_range(const key_type& __key) const; |
||
443 | |||
444 | size_type erase(const key_type& __key); |
||
445 | void erase(const iterator& __it); |
||
446 | void erase(iterator __first, iterator __last); |
||
447 | |||
448 | void erase(const const_iterator& __it); |
||
449 | void erase(const_iterator __first, const_iterator __last); |
||
450 | |||
451 | void resize(size_type __num_elements_hint); |
||
452 | void clear(); |
||
453 | |||
454 | private: |
||
455 | size_type _M_next_size(size_type __n) const |
||
456 | { return __stl_next_prime(__n); } |
||
457 | |||
458 | void _M_initialize_buckets(size_type __n) |
||
459 | { |
||
460 | const size_type __n_buckets = _M_next_size(__n); |
||
461 | _M_buckets.reserve(__n_buckets); |
||
462 | _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0); |
||
463 | _M_num_elements = 0; |
||
464 | } |
||
465 | |||
466 | size_type _M_bkt_num_key(const key_type& __key) const |
||
467 | { |
||
468 | return _M_bkt_num_key(__key, _M_buckets.size()); |
||
469 | } |
||
470 | |||
471 | size_type _M_bkt_num(const value_type& __obj) const |
||
472 | { |
||
473 | return _M_bkt_num_key(_M_get_key(__obj)); |
||
474 | } |
||
475 | |||
476 | size_type _M_bkt_num_key(const key_type& __key, size_t __n) const |
||
477 | { |
||
478 | return _M_hash(__key) % __n; |
||
479 | } |
||
480 | |||
481 | size_type _M_bkt_num(const value_type& __obj, size_t __n) const |
||
482 | { |
||
483 | return _M_bkt_num_key(_M_get_key(__obj), __n); |
||
484 | } |
||
485 | |||
486 | _Node* _M_new_node(const value_type& __obj) |
||
487 | { |
||
488 | _Node* __n = _M_get_node(); |
||
489 | __n->_M_next = 0; |
||
490 | __STL_TRY { |
||
491 | construct(&__n->_M_val, __obj); |
||
492 | return __n; |
||
493 | } |
||
494 | __STL_UNWIND(_M_put_node(__n)); |
||
495 | } |
||
496 | |||
497 | void _M_delete_node(_Node* __n) |
||
498 | { |
||
499 | destroy(&__n->_M_val); |
||
500 | _M_put_node(__n); |
||
501 | } |
||
502 | |||
503 | void _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last); |
||
504 | void _M_erase_bucket(const size_type __n, _Node* __last); |
||
505 | |||
506 | void _M_copy_from(const hashtable& __ht); |
||
507 | |||
508 | }; |
||
509 | |||
510 | template |
||
511 | class _All> |
||
512 | _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>& |
||
513 | _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++() |
||
514 | { |
||
515 | const _Node* __old = _M_cur; |
||
516 | _M_cur = _M_cur->_M_next; |
||
517 | if (!_M_cur) { |
||
518 | size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); |
||
519 | while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) |
||
520 | _M_cur = _M_ht->_M_buckets[__bucket]; |
||
521 | } |
||
522 | return *this; |
||
523 | } |
||
524 | |||
525 | template |
||
526 | class _All> |
||
527 | inline _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All> |
||
528 | _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++(int) |
||
529 | { |
||
530 | iterator __tmp = *this; |
||
531 | ++*this; |
||
532 | return __tmp; |
||
533 | } |
||
534 | |||
535 | template |
||
536 | class _All> |
||
537 | _Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>& |
||
538 | _Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++() |
||
539 | { |
||
540 | const _Node* __old = _M_cur; |
||
541 | _M_cur = _M_cur->_M_next; |
||
542 | if (!_M_cur) { |
||
543 | size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); |
||
544 | while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) |
||
545 | _M_cur = _M_ht->_M_buckets[__bucket]; |
||
546 | } |
||
547 | return *this; |
||
548 | } |
||
549 | |||
550 | template |
||
551 | class _All> |
||
552 | inline _Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All> |
||
553 | _Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++(int) |
||
554 | { |
||
555 | const_iterator __tmp = *this; |
||
556 | ++*this; |
||
557 | return __tmp; |
||
558 | } |
||
559 | |||
560 | template |
||
561 | bool operator==(const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht1, |
||
562 | const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht2) |
||
563 | { |
||
564 | typedef typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::_Node _Node; |
||
565 | if (__ht1._M_buckets.size() != __ht2._M_buckets.size()) |
||
566 | return false; |
||
567 | for (size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n) { |
||
568 | _Node* __cur1 = __ht1._M_buckets[__n]; |
||
569 | _Node* __cur2 = __ht2._M_buckets[__n]; |
||
570 | for ( ; __cur1 && __cur2 && __cur1->_M_val == __cur2->_M_val; |
||
571 | __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next) |
||
572 | {} |
||
573 | if (__cur1 || __cur2) |
||
574 | return false; |
||
575 | } |
||
576 | return true; |
||
577 | } |
||
578 | |||
579 | template |
||
580 | inline bool operator!=(const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht1, |
||
581 | const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht2) { |
||
582 | return !(__ht1 == __ht2); |
||
583 | } |
||
584 | |||
585 | template |
||
586 | class _All> |
||
587 | inline void swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1, |
||
588 | hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2) { |
||
589 | __ht1.swap(__ht2); |
||
590 | } |
||
591 | |||
592 | |||
593 | template |
||
594 | pair |
||
595 | hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> |
||
596 | ::insert_unique_noresize(const value_type& __obj) |
||
597 | { |
||
598 | const size_type __n = _M_bkt_num(__obj); |
||
599 | _Node* __first = _M_buckets[__n]; |
||
600 | |||
601 | for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) |
||
602 | if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) |
||
603 | return pair |
||
604 | |||
605 | _Node* __tmp = _M_new_node(__obj); |
||
606 | __tmp->_M_next = __first; |
||
607 | _M_buckets[__n] = __tmp; |
||
608 | ++_M_num_elements; |
||
609 | return pair |
||
610 | } |
||
611 | |||
612 | template |
||
613 | typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator |
||
614 | hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> |
||
615 | ::insert_equal_noresize(const value_type& __obj) |
||
616 | { |
||
617 | const size_type __n = _M_bkt_num(__obj); |
||
618 | _Node* __first = _M_buckets[__n]; |
||
619 | |||
620 | for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) |
||
621 | if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) { |
||
622 | _Node* __tmp = _M_new_node(__obj); |
||
623 | __tmp->_M_next = __cur->_M_next; |
||
624 | __cur->_M_next = __tmp; |
||
625 | ++_M_num_elements; |
||
626 | return iterator(__tmp, this); |
||
627 | } |
||
628 | |||
629 | _Node* __tmp = _M_new_node(__obj); |
||
630 | __tmp->_M_next = __first; |
||
631 | _M_buckets[__n] = __tmp; |
||
632 | ++_M_num_elements; |
||
633 | return iterator(__tmp, this); |
||
634 | } |
||
635 | |||
636 | template |
||
637 | typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::reference |
||
638 | hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::find_or_insert(const value_type& __obj) |
||
639 | { |
||
640 | resize(_M_num_elements + 1); |
||
641 | |||
642 | size_type __n = _M_bkt_num(__obj); |
||
643 | _Node* __first = _M_buckets[__n]; |
||
644 | |||
645 | for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) |
||
646 | if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) |
||
647 | return __cur->_M_val; |
||
648 | |||
649 | _Node* __tmp = _M_new_node(__obj); |
||
650 | __tmp->_M_next = __first; |
||
651 | _M_buckets[__n] = __tmp; |
||
652 | ++_M_num_elements; |
||
653 | return __tmp->_M_val; |
||
654 | } |
||
655 | |||
656 | template |
||
657 | pair |
||
658 | typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator> |
||
659 | hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::equal_range(const key_type& __key) |
||
660 | { |
||
661 | typedef pair |
||
662 | const size_type __n = _M_bkt_num_key(__key); |
||
663 | |||
664 | for (_Node* __first = _M_buckets[__n]; __first; __first = __first->_M_next) |
||
665 | if (_M_equals(_M_get_key(__first->_M_val), __key)) { |
||
666 | for (_Node* __cur = __first->_M_next; __cur; __cur = __cur->_M_next) |
||
667 | if (!_M_equals(_M_get_key(__cur->_M_val), __key)) |
||
668 | return _Pii(iterator(__first, this), iterator(__cur, this)); |
||
669 | for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) |
||
670 | if (_M_buckets[__m]) |
||
671 | return _Pii(iterator(__first, this), |
||
672 | iterator(_M_buckets[__m], this)); |
||
673 | return _Pii(iterator(__first, this), end()); |
||
674 | } |
||
675 | return _Pii(end(), end()); |
||
676 | } |
||
677 | |||
678 | template |
||
679 | pair |
||
680 | typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::const_iterator> |
||
681 | hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> |
||
682 | ::equal_range(const key_type& __key) const |
||
683 | { |
||
684 | typedef pair |
||
685 | const size_type __n = _M_bkt_num_key(__key); |
||
686 | |||
687 | for (const _Node* __first = _M_buckets[__n] ; |
||
688 | __first; |
||
689 | __first = __first->_M_next) { |
||
690 | if (_M_equals(_M_get_key(__first->_M_val), __key)) { |
||
691 | for (const _Node* __cur = __first->_M_next; |
||
692 | __cur; |
||
693 | __cur = __cur->_M_next) |
||
694 | if (!_M_equals(_M_get_key(__cur->_M_val), __key)) |
||
695 | return _Pii(const_iterator(__first, this), |
||
696 | const_iterator(__cur, this)); |
||
697 | for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) |
||
698 | if (_M_buckets[__m]) |
||
699 | return _Pii(const_iterator(__first, this), |
||
700 | const_iterator(_M_buckets[__m], this)); |
||
701 | return _Pii(const_iterator(__first, this), end()); |
||
702 | } |
||
703 | } |
||
704 | return _Pii(end(), end()); |
||
705 | } |
||
706 | |||
707 | template |
||
708 | typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::size_type |
||
709 | hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const key_type& __key) |
||
710 | { |
||
711 | const size_type __n = _M_bkt_num_key(__key); |
||
712 | _Node* __first = _M_buckets[__n]; |
||
713 | size_type __erased = 0; |
||
714 | |||
715 | if (__first) { |
||
716 | _Node* __cur = __first; |
||
717 | _Node* __next = __cur->_M_next; |
||
718 | while (__next) { |
||
719 | if (_M_equals(_M_get_key(__next->_M_val), __key)) { |
||
720 | __cur->_M_next = __next->_M_next; |
||
721 | _M_delete_node(__next); |
||
722 | __next = __cur->_M_next; |
||
723 | ++__erased; |
||
724 | --_M_num_elements; |
||
725 | } |
||
726 | else { |
||
727 | __cur = __next; |
||
728 | __next = __cur->_M_next; |
||
729 | } |
||
730 | } |
||
731 | if (_M_equals(_M_get_key(__first->_M_val), __key)) { |
||
732 | _M_buckets[__n] = __first->_M_next; |
||
733 | _M_delete_node(__first); |
||
734 | ++__erased; |
||
735 | --_M_num_elements; |
||
736 | } |
||
737 | } |
||
738 | return __erased; |
||
739 | } |
||
740 | |||
741 | template |
||
742 | void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const iterator& __it) |
||
743 | { |
||
744 | _Node* __p = __it._M_cur; |
||
745 | if (__p) { |
||
746 | const size_type __n = _M_bkt_num(__p->_M_val); |
||
747 | _Node* __cur = _M_buckets[__n]; |
||
748 | |||
749 | if (__cur == __p) { |
||
750 | _M_buckets[__n] = __cur->_M_next; |
||
751 | _M_delete_node(__cur); |
||
752 | --_M_num_elements; |
||
753 | } |
||
754 | else { |
||
755 | _Node* __next = __cur->_M_next; |
||
756 | while (__next) { |
||
757 | if (__next == __p) { |
||
758 | __cur->_M_next = __next->_M_next; |
||
759 | _M_delete_node(__next); |
||
760 | --_M_num_elements; |
||
761 | break; |
||
762 | } |
||
763 | else { |
||
764 | __cur = __next; |
||
765 | __next = __cur->_M_next; |
||
766 | } |
||
767 | } |
||
768 | } |
||
769 | } |
||
770 | } |
||
771 | |||
772 | template |
||
773 | void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> |
||
774 | ::erase(iterator __first, iterator __last) |
||
775 | { |
||
776 | size_type __f_bucket = __first._M_cur ? |
||
777 | _M_bkt_num(__first._M_cur->_M_val) : _M_buckets.size(); |
||
778 | size_type __l_bucket = __last._M_cur ? |
||
779 | _M_bkt_num(__last._M_cur->_M_val) : _M_buckets.size(); |
||
780 | |||
781 | if (__first._M_cur == __last._M_cur) |
||
782 | return; |
||
783 | else if (__f_bucket == __l_bucket) |
||
784 | _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur); |
||
785 | else { |
||
786 | _M_erase_bucket(__f_bucket, __first._M_cur, 0); |
||
787 | for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n) |
||
788 | _M_erase_bucket(__n, 0); |
||
789 | if (__l_bucket != _M_buckets.size()) |
||
790 | _M_erase_bucket(__l_bucket, __last._M_cur); |
||
791 | } |
||
792 | } |
||
793 | |||
794 | template |
||
795 | inline void |
||
796 | hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const_iterator __first, |
||
797 | const_iterator __last) |
||
798 | { |
||
799 | erase(iterator(const_cast<_Node*>(__first._M_cur), |
||
800 | const_cast |
||
801 | iterator(const_cast<_Node*>(__last._M_cur), |
||
802 | const_cast |
||
803 | } |
||
804 | |||
805 | template |
||
806 | inline void |
||
807 | hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const const_iterator& __it) |
||
808 | { |
||
809 | erase(iterator(const_cast<_Node*>(__it._M_cur), |
||
810 | const_cast |
||
811 | } |
||
812 | |||
813 | template |
||
814 | void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> |
||
815 | ::resize(size_type __num_elements_hint) |
||
816 | { |
||
817 | const size_type __old_n = _M_buckets.size(); |
||
818 | if (__num_elements_hint > __old_n) { |
||
819 | const size_type __n = _M_next_size(__num_elements_hint); |
||
820 | if (__n > __old_n) { |
||
821 | vector<_Node*, _All> __tmp(__n, (_Node*)(0), |
||
822 | _M_buckets.get_allocator()); |
||
823 | __STL_TRY { |
||
824 | for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) { |
||
825 | _Node* __first = _M_buckets[__bucket]; |
||
826 | while (__first) { |
||
827 | size_type __new_bucket = _M_bkt_num(__first->_M_val, __n); |
||
828 | _M_buckets[__bucket] = __first->_M_next; |
||
829 | __first->_M_next = __tmp[__new_bucket]; |
||
830 | __tmp[__new_bucket] = __first; |
||
831 | __first = _M_buckets[__bucket]; |
||
832 | } |
||
833 | } |
||
834 | _M_buckets.swap(__tmp); |
||
835 | } |
||
836 | # ifdef __STL_USE_EXCEPTIONS |
||
837 | catch(...) { |
||
838 | for (size_type __bucket = 0; __bucket < __tmp.size(); ++__bucket) { |
||
839 | while (__tmp[__bucket]) { |
||
840 | _Node* __next = __tmp[__bucket]->_M_next; |
||
841 | _M_delete_node(__tmp[__bucket]); |
||
842 | __tmp[__bucket] = __next; |
||
843 | } |
||
844 | } |
||
845 | throw; |
||
846 | } |
||
847 | # endif /* __STL_USE_EXCEPTIONS */ |
||
848 | } |
||
849 | } |
||
850 | } |
||
851 | |||
852 | template |
||
853 | void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> |
||
854 | ::_M_erase_bucket(const size_type __n, _Node* __first, _Node* __last) |
||
855 | { |
||
856 | _Node* __cur = _M_buckets[__n]; |
||
857 | if (__cur == __first) |
||
858 | _M_erase_bucket(__n, __last); |
||
859 | else { |
||
860 | _Node* __next; |
||
861 | for (__next = __cur->_M_next; |
||
862 | __next != __first; |
||
863 | __cur = __next, __next = __cur->_M_next) |
||
864 | ; |
||
865 | while (__next != __last) { |
||
866 | __cur->_M_next = __next->_M_next; |
||
867 | _M_delete_node(__next); |
||
868 | __next = __cur->_M_next; |
||
869 | --_M_num_elements; |
||
870 | } |
||
871 | } |
||
872 | } |
||
873 | |||
874 | template |
||
875 | void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> |
||
876 | ::_M_erase_bucket(const size_type __n, _Node* __last) |
||
877 | { |
||
878 | _Node* __cur = _M_buckets[__n]; |
||
879 | while (__cur != __last) { |
||
880 | _Node* __next = __cur->_M_next; |
||
881 | _M_delete_node(__cur); |
||
882 | __cur = __next; |
||
883 | _M_buckets[__n] = __cur; |
||
884 | --_M_num_elements; |
||
885 | } |
||
886 | } |
||
887 | |||
888 | template |
||
889 | void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::clear() |
||
890 | { |
||
891 | for (size_type __i = 0; __i < _M_buckets.size(); ++__i) { |
||
892 | _Node* __cur = _M_buckets[__i]; |
||
893 | while (__cur != 0) { |
||
894 | _Node* __next = __cur->_M_next; |
||
895 | _M_delete_node(__cur); |
||
896 | __cur = __next; |
||
897 | } |
||
898 | _M_buckets[__i] = 0; |
||
899 | } |
||
900 | _M_num_elements = 0; |
||
901 | } |
||
902 | |||
903 | |||
904 | template |
||
905 | void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> |
||
906 | ::_M_copy_from(const hashtable& __ht) |
||
907 | { |
||
908 | _M_buckets.clear(); |
||
909 | _M_buckets.reserve(__ht._M_buckets.size()); |
||
910 | _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0); |
||
911 | __STL_TRY { |
||
912 | for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) { |
||
913 | const _Node* __cur = __ht._M_buckets[__i]; |
||
914 | if (__cur) { |
||
915 | _Node* __local_copy = _M_new_node(__cur->_M_val); |
||
916 | _M_buckets[__i] = __local_copy; |
||
917 | |||
918 | for (_Node* __next = __cur->_M_next; |
||
919 | __next; |
||
920 | __cur = __next, __next = __cur->_M_next) { |
||
921 | __local_copy->_M_next = _M_new_node(__next->_M_val); |
||
922 | __local_copy = __local_copy->_M_next; |
||
923 | } |
||
924 | } |
||
925 | } |
||
926 | _M_num_elements = __ht._M_num_elements; |
||
927 | } |
||
928 | __STL_UNWIND(clear()); |
||
929 | } |
||
930 | |||
931 | } // namespace std |
||
932 | |||
933 | #endif /* __SGI_STL_INTERNAL_HASHTABLE_H */ |
||
934 | |||
935 | // Local Variables: |
||
936 | // mode:C++ |
||
937 | // End:>>>>>>>>>>>> |