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