?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
GUI: Fix Tomato RAF theme for all builds. Compilation typo.
[tomato.git] / release / src-rt-6.x.4708 / toolchains / hndtools-arm-linux-2.6.36-uclibc-4.5.3 / arm-brcm-linux-uclibcgnueabi / include / c++ / 4.5.3 / backward / hashtable.h
blob55c1d99bf5deea5b68ca021284db542918c807a3
1 // Hashtable implementation used by containers -*- C++ -*-
2
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
4 // Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
16
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
25
26 /*
27 * Copyright (c) 1996,1997
28 * Silicon Graphics Computer Systems, Inc.
29 *
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Silicon Graphics makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
37 *
38 *
39 * Copyright (c) 1994
40 * Hewlett-Packard Company
41 *
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Hewlett-Packard Company makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
49 *
50 */
51
52 /** @file backward/hashtable.h
53 * This file is a GNU extension to the Standard C++ Library (possibly
54 * containing extensions from the HP/SGI STL subset).
55 */
56
57 #ifndef _BACKWARD_HASHTABLE_H
58 #define _BACKWARD_HASHTABLE_H 1
59
60 // Hashtable class, used to implement the hashed associative containers
61 // hash_set, hash_map, hash_multiset, and hash_multimap.
62
63 #include <vector>
64 #include <iterator>
65 #include <algorithm>
66 #include <bits/stl_function.h>
67 #include <backward/hash_fun.h>
68
69 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
70
71 using std::size_t;
72 using std::ptrdiff_t;
73 using std::forward_iterator_tag;
74 using std::input_iterator_tag;
75 using std::_Construct;
76 using std::_Destroy;
77 using std::distance;
78 using std::vector;
79 using std::pair;
80 using std::__iterator_category;
81
82 template<class _Val>
83 struct _Hashtable_node
84 {
85 _Hashtable_node* _M_next;
86 _Val _M_val;
87 };
88
89 template<class _Val, class _Key, class _HashFcn, class _ExtractKey,
90 class _EqualKey, class _Alloc = std::allocator<_Val> >
91 class hashtable;
92
93 template<class _Val, class _Key, class _HashFcn,
94 class _ExtractKey, class _EqualKey, class _Alloc>
95 struct _Hashtable_iterator;
96
97 template<class _Val, class _Key, class _HashFcn,
98 class _ExtractKey, class _EqualKey, class _Alloc>
99 struct _Hashtable_const_iterator;
100
101 template<class _Val, class _Key, class _HashFcn,
102 class _ExtractKey, class _EqualKey, class _Alloc>
103 struct _Hashtable_iterator
104 {
105 typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>
106 _Hashtable;
107 typedef _Hashtable_iterator<_Val, _Key, _HashFcn,
108 _ExtractKey, _EqualKey, _Alloc>
109 iterator;
110 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
111 _ExtractKey, _EqualKey, _Alloc>
112 const_iterator;
113 typedef _Hashtable_node<_Val> _Node;
114 typedef forward_iterator_tag iterator_category;
115 typedef _Val value_type;
116 typedef ptrdiff_t difference_type;
117 typedef size_t size_type;
118 typedef _Val& reference;
119 typedef _Val* pointer;
120
121 _Node* _M_cur;
122 _Hashtable* _M_ht;
123
124 _Hashtable_iterator(_Node* __n, _Hashtable* __tab)
125 : _M_cur(__n), _M_ht(__tab) { }
126
127 _Hashtable_iterator() { }
128
129 reference
130 operator*() const
131 { return _M_cur->_M_val; }
132
133 pointer
134 operator->() const
135 { return &(operator*()); }
136
137 iterator&
138 operator++();
139
140 iterator
141 operator++(int);
142
143 bool
144 operator==(const iterator& __it) const
145 { return _M_cur == __it._M_cur; }
146
147 bool
148 operator!=(const iterator& __it) const
149 { return _M_cur != __it._M_cur; }
150 };
151
152 template<class _Val, class _Key, class _HashFcn,
153 class _ExtractKey, class _EqualKey, class _Alloc>
154 struct _Hashtable_const_iterator
155 {
156 typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>
157 _Hashtable;
158 typedef _Hashtable_iterator<_Val,_Key,_HashFcn,
159 _ExtractKey,_EqualKey,_Alloc>
160 iterator;
161 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
162 _ExtractKey, _EqualKey, _Alloc>
163 const_iterator;
164 typedef _Hashtable_node<_Val> _Node;
165
166 typedef forward_iterator_tag iterator_category;
167 typedef _Val value_type;
168 typedef ptrdiff_t difference_type;
169 typedef size_t size_type;
170 typedef const _Val& reference;
171 typedef const _Val* pointer;
172
173 const _Node* _M_cur;
174 const _Hashtable* _M_ht;
175
176 _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab)
177 : _M_cur(__n), _M_ht(__tab) { }
178
179 _Hashtable_const_iterator() { }
180
181 _Hashtable_const_iterator(const iterator& __it)
182 : _M_cur(__it._M_cur), _M_ht(__it._M_ht) { }
183
184 reference
185 operator*() const
186 { return _M_cur->_M_val; }
187
188 pointer
189 operator->() const
190 { return &(operator*()); }
191
192 const_iterator&
193 operator++();
194
195 const_iterator
196 operator++(int);
197
198 bool
199 operator==(const const_iterator& __it) const
200 { return _M_cur == __it._M_cur; }
201
202 bool
203 operator!=(const const_iterator& __it) const
204 { return _M_cur != __it._M_cur; }
205 };
206
207 // Note: assumes long is at least 32 bits.
208 enum { _S_num_primes = 29 };
209
210 static const unsigned long __stl_prime_list[_S_num_primes] =
211 {
212 5ul, 53ul, 97ul, 193ul, 389ul,
213 769ul, 1543ul, 3079ul, 6151ul, 12289ul,
214 24593ul, 49157ul, 98317ul, 196613ul, 393241ul,
215 786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul,
216 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul,
217 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul
218 };
219
220 inline unsigned long
221 __stl_next_prime(unsigned long __n)
222 {
223 const unsigned long* __first = __stl_prime_list;
224 const unsigned long* __last = __stl_prime_list + (int)_S_num_primes;
225 const unsigned long* pos = std::lower_bound(__first, __last, __n);
226 return pos == __last ? *(__last - 1) : *pos;
227 }
228
229 // Forward declaration of operator==.
230 template<class _Val, class _Key, class _HF, class _Ex,
231 class _Eq, class _All>
232 class hashtable;
233
234 template<class _Val, class _Key, class _HF, class _Ex,
235 class _Eq, class _All>
236 bool
237 operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
238 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2);
239
240 // Hashtables handle allocators a bit differently than other
241 // containers do. If we're using standard-conforming allocators, then
242 // a hashtable unconditionally has a member variable to hold its
243 // allocator, even if it so happens that all instances of the
244 // allocator type are identical. This is because, for hashtables,
245 // this extra storage is negligible. Additionally, a base class
246 // wouldn't serve any other purposes; it wouldn't, for example,
247 // simplify the exception-handling code.
248 template<class _Val, class _Key, class _HashFcn,
249 class _ExtractKey, class _EqualKey, class _Alloc>
250 class hashtable
251 {
252 public:
253 typedef _Key key_type;
254 typedef _Val value_type;
255 typedef _HashFcn hasher;
256 typedef _EqualKey key_equal;
257
258 typedef size_t size_type;
259 typedef ptrdiff_t difference_type;
260 typedef value_type* pointer;
261 typedef const value_type* const_pointer;
262 typedef value_type& reference;
263 typedef const value_type& const_reference;
264
265 hasher
266 hash_funct() const
267 { return _M_hash; }
268
269 key_equal
270 key_eq() const
271 { return _M_equals; }
272
273 private:
274 typedef _Hashtable_node<_Val> _Node;
275
276 public:
277 typedef typename _Alloc::template rebind<value_type>::other allocator_type;
278 allocator_type
279 get_allocator() const
280 { return _M_node_allocator; }
281
282 private:
283 typedef typename _Alloc::template rebind<_Node>::other _Node_Alloc;
284 typedef typename _Alloc::template rebind<_Node*>::other _Nodeptr_Alloc;
285 typedef vector<_Node*, _Nodeptr_Alloc> _Vector_type;
286
287 _Node_Alloc _M_node_allocator;
288
289 _Node*
290 _M_get_node()
291 { return _M_node_allocator.allocate(1); }
292
293 void
294 _M_put_node(_Node* __p)
295 { _M_node_allocator.deallocate(__p, 1); }
296
297 private:
298 hasher _M_hash;
299 key_equal _M_equals;
300 _ExtractKey _M_get_key;
301 _Vector_type _M_buckets;
302 size_type _M_num_elements;
303
304 public:
305 typedef _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey,
306 _EqualKey, _Alloc>
307 iterator;
308 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,
309 _EqualKey, _Alloc>
310 const_iterator;
311
312 friend struct
313 _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>;
314
315 friend struct
316 _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,
317 _EqualKey, _Alloc>;
318
319 public:
320 hashtable(size_type __n, const _HashFcn& __hf,
321 const _EqualKey& __eql, const _ExtractKey& __ext,
322 const allocator_type& __a = allocator_type())
323 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
324 _M_get_key(__ext), _M_buckets(__a), _M_num_elements(0)
325 { _M_initialize_buckets(__n); }
326
327 hashtable(size_type __n, const _HashFcn& __hf,
328 const _EqualKey& __eql,
329 const allocator_type& __a = allocator_type())
330 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
331 _M_get_key(_ExtractKey()), _M_buckets(__a), _M_num_elements(0)
332 { _M_initialize_buckets(__n); }
333
334 hashtable(const hashtable& __ht)
335 : _M_node_allocator(__ht.get_allocator()), _M_hash(__ht._M_hash),
336 _M_equals(__ht._M_equals), _M_get_key(__ht._M_get_key),
337 _M_buckets(__ht.get_allocator()), _M_num_elements(0)
338 { _M_copy_from(__ht); }
339
340 hashtable&
341 operator= (const hashtable& __ht)
342 {
343 if (&__ht != this)
344 {
345 clear();
346 _M_hash = __ht._M_hash;
347 _M_equals = __ht._M_equals;
348 _M_get_key = __ht._M_get_key;
349 _M_copy_from(__ht);
350 }
351 return *this;
352 }
353
354 ~hashtable()
355 { clear(); }
356
357 size_type
358 size() const
359 { return _M_num_elements; }
360
361 size_type
362 max_size() const
363 { return size_type(-1); }
364
365 bool
366 empty() const
367 { return size() == 0; }
368
369 void
370 swap(hashtable& __ht)
371 {
372 std::swap(_M_hash, __ht._M_hash);
373 std::swap(_M_equals, __ht._M_equals);
374 std::swap(_M_get_key, __ht._M_get_key);
375 _M_buckets.swap(__ht._M_buckets);
376 std::swap(_M_num_elements, __ht._M_num_elements);
377 }
378
379 iterator
380 begin()
381 {
382 for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
383 if (_M_buckets[__n])
384 return iterator(_M_buckets[__n], this);
385 return end();
386 }
387
388 iterator
389 end()
390 { return iterator(0, this); }
391
392 const_iterator
393 begin() const
394 {
395 for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
396 if (_M_buckets[__n])
397 return const_iterator(_M_buckets[__n], this);
398 return end();
399 }
400
401 const_iterator
402 end() const
403 { return const_iterator(0, this); }
404
405 template<class _Vl, class _Ky, class _HF, class _Ex, class _Eq,
406 class _Al>
407 friend bool
408 operator==(const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&,
409 const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&);
410
411 public:
412 size_type
413 bucket_count() const
414 { return _M_buckets.size(); }
415
416 size_type
417 max_bucket_count() const
418 { return __stl_prime_list[(int)_S_num_primes - 1]; }
419
420 size_type
421 elems_in_bucket(size_type __bucket) const
422 {
423 size_type __result = 0;
424 for (_Node* __n = _M_buckets[__bucket]; __n; __n = __n->_M_next)
425 __result += 1;
426 return __result;
427 }
428
429 pair<iterator, bool>
430 insert_unique(const value_type& __obj)
431 {
432 resize(_M_num_elements + 1);
433 return insert_unique_noresize(__obj);
434 }
435
436 iterator
437 insert_equal(const value_type& __obj)
438 {
439 resize(_M_num_elements + 1);
440 return insert_equal_noresize(__obj);
441 }
442
443 pair<iterator, bool>
444 insert_unique_noresize(const value_type& __obj);
445
446 iterator
447 insert_equal_noresize(const value_type& __obj);
448
449 template<class _InputIterator>
450 void
451 insert_unique(_InputIterator __f, _InputIterator __l)
452 { insert_unique(__f, __l, __iterator_category(__f)); }
453
454 template<class _InputIterator>
455 void
456 insert_equal(_InputIterator __f, _InputIterator __l)
457 { insert_equal(__f, __l, __iterator_category(__f)); }
458
459 template<class _InputIterator>
460 void
461 insert_unique(_InputIterator __f, _InputIterator __l,
462 input_iterator_tag)
463 {
464 for ( ; __f != __l; ++__f)
465 insert_unique(*__f);
466 }
467
468 template<class _InputIterator>
469 void
470 insert_equal(_InputIterator __f, _InputIterator __l,
471 input_iterator_tag)
472 {
473 for ( ; __f != __l; ++__f)
474 insert_equal(*__f);
475 }
476
477 template<class _ForwardIterator>
478 void
479 insert_unique(_ForwardIterator __f, _ForwardIterator __l,
480 forward_iterator_tag)
481 {
482 size_type __n = distance(__f, __l);
483 resize(_M_num_elements + __n);
484 for ( ; __n > 0; --__n, ++__f)
485 insert_unique_noresize(*__f);
486 }
487
488 template<class _ForwardIterator>
489 void
490 insert_equal(_ForwardIterator __f, _ForwardIterator __l,
491 forward_iterator_tag)
492 {
493 size_type __n = distance(__f, __l);
494 resize(_M_num_elements + __n);
495 for ( ; __n > 0; --__n, ++__f)
496 insert_equal_noresize(*__f);
497 }
498
499 reference
500 find_or_insert(const value_type& __obj);
501
502 iterator
503 find(const key_type& __key)
504 {
505 size_type __n = _M_bkt_num_key(__key);
506 _Node* __first;
507 for (__first = _M_buckets[__n];
508 __first && !_M_equals(_M_get_key(__first->_M_val), __key);
509 __first = __first->_M_next)
510 { }
511 return iterator(__first, this);
512 }
513
514 const_iterator
515 find(const key_type& __key) const
516 {
517 size_type __n = _M_bkt_num_key(__key);
518 const _Node* __first;
519 for (__first = _M_buckets[__n];
520 __first && !_M_equals(_M_get_key(__first->_M_val), __key);
521 __first = __first->_M_next)
522 { }
523 return const_iterator(__first, this);
524 }
525
526 size_type
527 count(const key_type& __key) const
528 {
529 const size_type __n = _M_bkt_num_key(__key);
530 size_type __result = 0;
531
532 for (const _Node* __cur = _M_buckets[__n]; __cur;
533 __cur = __cur->_M_next)
534 if (_M_equals(_M_get_key(__cur->_M_val), __key))
535 ++__result;
536 return __result;
537 }
538
539 pair<iterator, iterator>
540 equal_range(const key_type& __key);
541
542 pair<const_iterator, const_iterator>
543 equal_range(const key_type& __key) const;
544
545 size_type
546 erase(const key_type& __key);
547
548 void
549 erase(const iterator& __it);
550
551 void
552 erase(iterator __first, iterator __last);
553
554 void
555 erase(const const_iterator& __it);
556
557 void
558 erase(const_iterator __first, const_iterator __last);
559
560 void
561 resize(size_type __num_elements_hint);
562
563 void
564 clear();
565
566 private:
567 size_type
568 _M_next_size(size_type __n) const
569 { return __stl_next_prime(__n); }
570
571 void
572 _M_initialize_buckets(size_type __n)
573 {
574 const size_type __n_buckets = _M_next_size(__n);
575 _M_buckets.reserve(__n_buckets);
576 _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0);
577 _M_num_elements = 0;
578 }
579
580 size_type
581 _M_bkt_num_key(const key_type& __key) const
582 { return _M_bkt_num_key(__key, _M_buckets.size()); }
583
584 size_type
585 _M_bkt_num(const value_type& __obj) const
586 { return _M_bkt_num_key(_M_get_key(__obj)); }
587
588 size_type
589 _M_bkt_num_key(const key_type& __key, size_t __n) const
590 { return _M_hash(__key) % __n; }
591
592 size_type
593 _M_bkt_num(const value_type& __obj, size_t __n) const
594 { return _M_bkt_num_key(_M_get_key(__obj), __n); }
595
596 _Node*
597 _M_new_node(const value_type& __obj)
598 {
599 _Node* __n = _M_get_node();
600 __n->_M_next = 0;
601 __try
602 {
603 this->get_allocator().construct(&__n->_M_val, __obj);
604 return __n;
605 }
606 __catch(...)
607 {
608 _M_put_node(__n);
609 __throw_exception_again;
610 }
611 }
612
613 void
614 _M_delete_node(_Node* __n)
615 {
616 this->get_allocator().destroy(&__n->_M_val);
617 _M_put_node(__n);
618 }
619
620 void
621 _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last);
622
623 void
624 _M_erase_bucket(const size_type __n, _Node* __last);
625
626 void
627 _M_copy_from(const hashtable& __ht);
628 };
629
630 template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
631 class _All>
632 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
633 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
634 operator++()
635 {
636 const _Node* __old = _M_cur;
637 _M_cur = _M_cur->_M_next;
638 if (!_M_cur)
639 {
640 size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
641 while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
642 _M_cur = _M_ht->_M_buckets[__bucket];
643 }
644 return *this;
645 }
646
647 template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
648 class _All>
649 inline _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
650 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
651 operator++(int)
652 {
653 iterator __tmp = *this;
654 ++*this;
655 return __tmp;
656 }
657
658 template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
659 class _All>
660 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
661 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
662 operator++()
663 {
664 const _Node* __old = _M_cur;
665 _M_cur = _M_cur->_M_next;
666 if (!_M_cur)
667 {
668 size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
669 while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
670 _M_cur = _M_ht->_M_buckets[__bucket];
671 }
672 return *this;
673 }
674
675 template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
676 class _All>
677 inline _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
678 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
679 operator++(int)
680 {
681 const_iterator __tmp = *this;
682 ++*this;
683 return __tmp;
684 }
685
686 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
687 bool
688 operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
689 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
690 {
691 typedef typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_Node _Node;
692
693 if (__ht1._M_buckets.size() != __ht2._M_buckets.size())
694 return false;
695
696 for (size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n)
697 {
698 _Node* __cur1 = __ht1._M_buckets[__n];
699 _Node* __cur2 = __ht2._M_buckets[__n];
700 // Check same length of lists
701 for (; __cur1 && __cur2;
702 __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next)
703 { }
704 if (__cur1 || __cur2)
705 return false;
706 // Now check one's elements are in the other
707 for (__cur1 = __ht1._M_buckets[__n] ; __cur1;
708 __cur1 = __cur1->_M_next)
709 {
710 bool _found__cur1 = false;
711 for (__cur2 = __ht2._M_buckets[__n];
712 __cur2; __cur2 = __cur2->_M_next)
713 {
714 if (__cur1->_M_val == __cur2->_M_val)
715 {
716 _found__cur1 = true;
717 break;
718 }
719 }
720 if (!_found__cur1)
721 return false;
722 }
723 }
724 return true;
725 }
726
727 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
728 inline bool
729 operator!=(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
730 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
731 { return !(__ht1 == __ht2); }
732
733 template<class _Val, class _Key, class _HF, class _Extract, class _EqKey,
734 class _All>
735 inline void
736 swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1,
737 hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2)
738 { __ht1.swap(__ht2); }
739
740 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
741 pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, bool>
742 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
743 insert_unique_noresize(const value_type& __obj)
744 {
745 const size_type __n = _M_bkt_num(__obj);
746 _Node* __first = _M_buckets[__n];
747
748 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
749 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
750 return pair<iterator, bool>(iterator(__cur, this), false);
751
752 _Node* __tmp = _M_new_node(__obj);
753 __tmp->_M_next = __first;
754 _M_buckets[__n] = __tmp;
755 ++_M_num_elements;
756 return pair<iterator, bool>(iterator(__tmp, this), true);
757 }
758
759 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
760 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator
761 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
762 insert_equal_noresize(const value_type& __obj)
763 {
764 const size_type __n = _M_bkt_num(__obj);
765 _Node* __first = _M_buckets[__n];
766
767 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
768 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
769 {
770 _Node* __tmp = _M_new_node(__obj);
771 __tmp->_M_next = __cur->_M_next;
772 __cur->_M_next = __tmp;
773 ++_M_num_elements;
774 return iterator(__tmp, this);
775 }
776
777 _Node* __tmp = _M_new_node(__obj);
778 __tmp->_M_next = __first;
779 _M_buckets[__n] = __tmp;
780 ++_M_num_elements;
781 return iterator(__tmp, this);
782 }
783
784 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
785 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::reference
786 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
787 find_or_insert(const value_type& __obj)
788 {
789 resize(_M_num_elements + 1);
790
791 size_type __n = _M_bkt_num(__obj);
792 _Node* __first = _M_buckets[__n];
793
794 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
795 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
796 return __cur->_M_val;
797
798 _Node* __tmp = _M_new_node(__obj);
799 __tmp->_M_next = __first;
800 _M_buckets[__n] = __tmp;
801 ++_M_num_elements;
802 return __tmp->_M_val;
803 }
804
805 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
806 pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator,
807 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator>
808 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
809 equal_range(const key_type& __key)
810 {
811 typedef pair<iterator, iterator> _Pii;
812 const size_type __n = _M_bkt_num_key(__key);
813
814 for (_Node* __first = _M_buckets[__n]; __first;
815 __first = __first->_M_next)
816 if (_M_equals(_M_get_key(__first->_M_val), __key))
817 {
818 for (_Node* __cur = __first->_M_next; __cur;
819 __cur = __cur->_M_next)
820 if (!_M_equals(_M_get_key(__cur->_M_val), __key))
821 return _Pii(iterator(__first, this), iterator(__cur, this));
822 for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
823 if (_M_buckets[__m])
824 return _Pii(iterator(__first, this),
825 iterator(_M_buckets[__m], this));
826 return _Pii(iterator(__first, this), end());
827 }
828 return _Pii(end(), end());
829 }
830
831 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
832 pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator,
833 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator>
834 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
835 equal_range(const key_type& __key) const
836 {
837 typedef pair<const_iterator, const_iterator> _Pii;
838 const size_type __n = _M_bkt_num_key(__key);
839
840 for (const _Node* __first = _M_buckets[__n]; __first;
841 __first = __first->_M_next)
842 {
843 if (_M_equals(_M_get_key(__first->_M_val), __key))
844 {
845 for (const _Node* __cur = __first->_M_next; __cur;
846 __cur = __cur->_M_next)
847 if (!_M_equals(_M_get_key(__cur->_M_val), __key))
848 return _Pii(const_iterator(__first, this),
849 const_iterator(__cur, this));
850 for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
851 if (_M_buckets[__m])
852 return _Pii(const_iterator(__first, this),
853 const_iterator(_M_buckets[__m], this));
854 return _Pii(const_iterator(__first, this), end());
855 }
856 }
857 return _Pii(end(), end());
858 }
859
860 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
861 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::size_type
862 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
863 erase(const key_type& __key)
864 {
865 const size_type __n = _M_bkt_num_key(__key);
866 _Node* __first = _M_buckets[__n];
867 _Node* __saved_slot = 0;
868 size_type __erased = 0;
869
870 if (__first)
871 {
872 _Node* __cur = __first;
873 _Node* __next = __cur->_M_next;
874 while (__next)
875 {
876 if (_M_equals(_M_get_key(__next->_M_val), __key))
877 {
878 if (&_M_get_key(__next->_M_val) != &__key)
879 {
880 __cur->_M_next = __next->_M_next;
881 _M_delete_node(__next);
882 __next = __cur->_M_next;
883 ++__erased;
884 --_M_num_elements;
885 }
886 else
887 {
888 __saved_slot = __cur;
889 __cur = __next;
890 __next = __cur->_M_next;
891 }
892 }
893 else
894 {
895 __cur = __next;
896 __next = __cur->_M_next;
897 }
898 }
899 if (_M_equals(_M_get_key(__first->_M_val), __key))
900 {
901 _M_buckets[__n] = __first->_M_next;
902 _M_delete_node(__first);
903 ++__erased;
904 --_M_num_elements;
905 }
906 if (__saved_slot)
907 {
908 __next = __saved_slot->_M_next;
909 __saved_slot->_M_next = __next->_M_next;
910 _M_delete_node(__next);
911 ++__erased;
912 --_M_num_elements;
913 }
914 }
915 return __erased;
916 }
917
918 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
919 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
920 erase(const iterator& __it)
921 {
922 _Node* __p = __it._M_cur;
923 if (__p)
924 {
925 const size_type __n = _M_bkt_num(__p->_M_val);
926 _Node* __cur = _M_buckets[__n];
927
928 if (__cur == __p)
929 {
930 _M_buckets[__n] = __cur->_M_next;
931 _M_delete_node(__cur);
932 --_M_num_elements;
933 }
934 else
935 {
936 _Node* __next = __cur->_M_next;
937 while (__next)
938 {
939 if (__next == __p)
940 {
941 __cur->_M_next = __next->_M_next;
942 _M_delete_node(__next);
943 --_M_num_elements;
944 break;
945 }
946 else
947 {
948 __cur = __next;
949 __next = __cur->_M_next;
950 }
951 }
952 }
953 }
954 }
955
956 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
957 void
958 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
959 erase(iterator __first, iterator __last)
960 {
961 size_type __f_bucket = __first._M_cur ? _M_bkt_num(__first._M_cur->_M_val)
962 : _M_buckets.size();
963
964 size_type __l_bucket = __last._M_cur ? _M_bkt_num(__last._M_cur->_M_val)
965 : _M_buckets.size();
966
967 if (__first._M_cur == __last._M_cur)
968 return;
969 else if (__f_bucket == __l_bucket)
970 _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur);
971 else
972 {
973 _M_erase_bucket(__f_bucket, __first._M_cur, 0);
974 for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n)
975 _M_erase_bucket(__n, 0);
976 if (__l_bucket != _M_buckets.size())
977 _M_erase_bucket(__l_bucket, __last._M_cur);
978 }
979 }
980
981 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
982 inline void
983 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
984 erase(const_iterator __first, const_iterator __last)
985 {
986 erase(iterator(const_cast<_Node*>(__first._M_cur),
987 const_cast<hashtable*>(__first._M_ht)),
988 iterator(const_cast<_Node*>(__last._M_cur),
989 const_cast<hashtable*>(__last._M_ht)));
990 }
991
992 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
993 inline void
994 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
995 erase(const const_iterator& __it)
996 { erase(iterator(const_cast<_Node*>(__it._M_cur),
997 const_cast<hashtable*>(__it._M_ht))); }
998
999 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1000 void
1001 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1002 resize(size_type __num_elements_hint)
1003 {
1004 const size_type __old_n = _M_buckets.size();
1005 if (__num_elements_hint > __old_n)
1006 {
1007 const size_type __n = _M_next_size(__num_elements_hint);
1008 if (__n > __old_n)
1009 {
1010 _Vector_type __tmp(__n, (_Node*)(0), _M_buckets.get_allocator());
1011 __try
1012 {
1013 for (size_type __bucket = 0; __bucket < __old_n; ++__bucket)
1014 {
1015 _Node* __first = _M_buckets[__bucket];
1016 while (__first)
1017 {
1018 size_type __new_bucket = _M_bkt_num(__first->_M_val,
1019 __n);
1020 _M_buckets[__bucket] = __first->_M_next;
1021 __first->_M_next = __tmp[__new_bucket];
1022 __tmp[__new_bucket] = __first;
1023 __first = _M_buckets[__bucket];
1024 }
1025 }
1026 _M_buckets.swap(__tmp);
1027 }
1028 __catch(...)
1029 {
1030 for (size_type __bucket = 0; __bucket < __tmp.size();
1031 ++__bucket)
1032 {
1033 while (__tmp[__bucket])
1034 {
1035 _Node* __next = __tmp[__bucket]->_M_next;
1036 _M_delete_node(__tmp[__bucket]);
1037 __tmp[__bucket] = __next;
1038 }
1039 }
1040 __throw_exception_again;
1041 }
1042 }
1043 }
1044 }
1045
1046 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1047 void
1048 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1049 _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last)
1050 {
1051 _Node* __cur = _M_buckets[__n];
1052 if (__cur == __first)
1053 _M_erase_bucket(__n, __last);
1054 else
1055 {
1056 _Node* __next;
1057 for (__next = __cur->_M_next;
1058 __next != __first;
1059 __cur = __next, __next = __cur->_M_next)
1060 ;
1061 while (__next != __last)
1062 {
1063 __cur->_M_next = __next->_M_next;
1064 _M_delete_node(__next);
1065 __next = __cur->_M_next;
1066 --_M_num_elements;
1067 }
1068 }
1069 }
1070
1071 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1072 void
1073 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1074 _M_erase_bucket(const size_type __n, _Node* __last)
1075 {
1076 _Node* __cur = _M_buckets[__n];
1077 while (__cur != __last)
1078 {
1079 _Node* __next = __cur->_M_next;
1080 _M_delete_node(__cur);
1081 __cur = __next;
1082 _M_buckets[__n] = __cur;
1083 --_M_num_elements;
1084 }
1085 }
1086
1087 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1088 void
1089 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1090 clear()
1091 {
1092 if (_M_num_elements == 0)
1093 return;
1094
1095 for (size_type __i = 0; __i < _M_buckets.size(); ++__i)
1096 {
1097 _Node* __cur = _M_buckets[__i];
1098 while (__cur != 0)
1099 {
1100 _Node* __next = __cur->_M_next;
1101 _M_delete_node(__cur);
1102 __cur = __next;
1103 }
1104 _M_buckets[__i] = 0;
1105 }
1106 _M_num_elements = 0;
1107 }
1108
1109 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1110 void
1111 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1112 _M_copy_from(const hashtable& __ht)
1113 {
1114 _M_buckets.clear();
1115 _M_buckets.reserve(__ht._M_buckets.size());
1116 _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0);
1117 __try
1118 {
1119 for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) {
1120 const _Node* __cur = __ht._M_buckets[__i];
1121 if (__cur)
1122 {
1123 _Node* __local_copy = _M_new_node(__cur->_M_val);
1124 _M_buckets[__i] = __local_copy;
1125
1126 for (_Node* __next = __cur->_M_next;
1127 __next;
1128 __cur = __next, __next = __cur->_M_next)
1129 {
1130 __local_copy->_M_next = _M_new_node(__next->_M_val);
1131 __local_copy = __local_copy->_M_next;
1132 }
1133 }
1134 }
1135 _M_num_elements = __ht._M_num_elements;
1136 }
1137 __catch(...)
1138 {
1139 clear();
1140 __throw_exception_again;
1141 }
1142 }
1143
1144 _GLIBCXX_END_NAMESPACE
1145
1146 #endif
Tomato firmware and modifications.