stl_hashtable.h
上传用户:sichengcw
上传日期:2009-02-17
资源大小:202k
文件大小:26k
源码类别:

STL

开发平台:

Visual C++

  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. /* NOTE: This is an internal header file, included by other STL headers.
  27.  *   You should not attempt to use it directly.
  28.  */
  29. #ifndef __SGI_STL_INTERNAL_HASHTABLE_H
  30. #define __SGI_STL_INTERNAL_HASHTABLE_H
  31. // Hashtable class, used to implement the hashed associative containers
  32. // hash_set, hash_map, hash_multiset, and hash_multimap.
  33. #include <stl_algobase.h>
  34. #include <stl_alloc.h>
  35. #include <stl_construct.h>
  36. #include <stl_tempbuf.h>
  37. #include <stl_algo.h>
  38. #include <stl_uninitialized.h>
  39. #include <stl_function.h>
  40. #include <stl_vector.h>
  41. #include <stl_hash_fun.h>
  42. __STL_BEGIN_NAMESPACE
  43. template <class Value>
  44. struct __hashtable_node
  45. {
  46.   __hashtable_node* next;
  47.   Value val;
  48. };  
  49. template <class Value, class Key, class HashFcn,
  50.           class ExtractKey, class EqualKey, class Alloc = alloc>
  51. class hashtable;
  52. template <class Value, class Key, class HashFcn,
  53.           class ExtractKey, class EqualKey, class Alloc>
  54. struct __hashtable_iterator;
  55. template <class Value, class Key, class HashFcn,
  56.           class ExtractKey, class EqualKey, class Alloc>
  57. struct __hashtable_const_iterator;
  58. template <class Value, class Key, class HashFcn,
  59.           class ExtractKey, class EqualKey, class Alloc>
  60. struct __hashtable_iterator {
  61.   typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
  62.           hashtable;
  63.   typedef __hashtable_iterator<Value, Key, HashFcn, 
  64.                                ExtractKey, EqualKey, Alloc>
  65.           iterator;
  66.   typedef __hashtable_const_iterator<Value, Key, HashFcn, 
  67.                                      ExtractKey, EqualKey, Alloc>
  68.           const_iterator;
  69.   typedef __hashtable_node<Value> node;
  70.   typedef forward_iterator_tag iterator_category;
  71.   typedef Value value_type;
  72.   typedef ptrdiff_t difference_type;
  73.   typedef size_t size_type;
  74.   typedef Value& reference;
  75.   typedef Value* pointer;
  76.   node* cur;
  77.   hashtable* ht;
  78.   __hashtable_iterator(node* n, hashtable* tab) : cur(n), ht(tab) {}
  79.   __hashtable_iterator() {}
  80.   reference operator*() const { return cur->val; }
  81. #ifndef __SGI_STL_NO_ARROW_OPERATOR
  82.   pointer operator->() const { return &(operator*()); }
  83. #endif /* __SGI_STL_NO_ARROW_OPERATOR */
  84.   iterator& operator++();
  85.   iterator operator++(int);
  86.   bool operator==(const iterator& it) const { return cur == it.cur; }
  87.   bool operator!=(const iterator& it) const { return cur != it.cur; }
  88. };
  89. template <class Value, class Key, class HashFcn,
  90.           class ExtractKey, class EqualKey, class Alloc>
  91. struct __hashtable_const_iterator {
  92.   typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
  93.           hashtable;
  94.   typedef __hashtable_iterator<Value, Key, HashFcn, 
  95.                                ExtractKey, EqualKey, Alloc>
  96.           iterator;
  97.   typedef __hashtable_const_iterator<Value, Key, HashFcn, 
  98.                                      ExtractKey, EqualKey, Alloc>
  99.           const_iterator;
  100.   typedef __hashtable_node<Value> node;
  101.   typedef forward_iterator_tag iterator_category;
  102.   typedef Value value_type;
  103.   typedef ptrdiff_t difference_type;
  104.   typedef size_t size_type;
  105.   typedef const Value& reference;
  106.   typedef const Value* pointer;
  107.   const node* cur;
  108.   const hashtable* ht;
  109.   __hashtable_const_iterator(const node* n, const hashtable* tab)
  110.     : cur(n), ht(tab) {}
  111.   __hashtable_const_iterator() {}
  112.   __hashtable_const_iterator(const iterator& it) : cur(it.cur), ht(it.ht) {}
  113.   reference operator*() const { return cur->val; }
  114. #ifndef __SGI_STL_NO_ARROW_OPERATOR
  115.   pointer operator->() const { return &(operator*()); }
  116. #endif /* __SGI_STL_NO_ARROW_OPERATOR */
  117.   const_iterator& operator++();
  118.   const_iterator operator++(int);
  119.   bool operator==(const const_iterator& it) const { return cur == it.cur; }
  120.   bool operator!=(const const_iterator& it) const { return cur != it.cur; }
  121. };
  122. // Note: assumes long is at least 32 bits.
  123. static const int __stl_num_primes = 28;
  124. static const unsigned long __stl_prime_list[__stl_num_primes] =
  125. {
  126.   53,         97,           193,         389,       769,
  127.   1543,       3079,         6151,        12289,     24593,
  128.   49157,      98317,        196613,      393241,    786433,
  129.   1572869,    3145739,      6291469,     12582917,  25165843,
  130.   50331653,   100663319,    201326611,   402653189, 805306457, 
  131.   1610612741, 3221225473ul, 4294967291ul
  132. };
  133. inline unsigned long __stl_next_prime(unsigned long n)
  134. {
  135.   const unsigned long* first = __stl_prime_list;
  136.   const unsigned long* last = __stl_prime_list + __stl_num_primes;
  137.   const unsigned long* pos = lower_bound(first, last, n);
  138.   return pos == last ? *(last - 1) : *pos;
  139. }
  140. template <class Value, class Key, class HashFcn,
  141.           class ExtractKey, class EqualKey,
  142.           class Alloc>
  143. class hashtable {
  144. public:
  145.   typedef Key key_type;
  146.   typedef Value value_type;
  147.   typedef HashFcn hasher;
  148.   typedef EqualKey key_equal;
  149.   typedef size_t            size_type;
  150.   typedef ptrdiff_t         difference_type;
  151.   typedef value_type*       pointer;
  152.   typedef const value_type* const_pointer;
  153.   typedef value_type&       reference;
  154.   typedef const value_type& const_reference;
  155.   hasher hash_funct() const { return hash; }
  156.   key_equal key_eq() const { return equals; }
  157. private:
  158.   hasher hash;
  159.   key_equal equals;
  160.   ExtractKey get_key;
  161.   typedef __hashtable_node<Value> node;
  162.   typedef simple_alloc<node, Alloc> node_allocator;
  163.   vector<node*,Alloc> buckets;
  164.   size_type num_elements;
  165. public:
  166.   typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, 
  167.                                Alloc>
  168.   iterator;
  169.   typedef __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey,
  170.                                      Alloc>
  171.   const_iterator;
  172.   friend struct
  173.   __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>;
  174.   friend struct
  175.   __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>;
  176. public:
  177.   hashtable(size_type n,
  178.             const HashFcn&    hf,
  179.             const EqualKey&   eql,
  180.             const ExtractKey& ext)
  181.     : hash(hf), equals(eql), get_key(ext), num_elements(0)
  182.   {
  183.     initialize_buckets(n);
  184.   }
  185.   hashtable(size_type n,
  186.             const HashFcn&    hf,
  187.             const EqualKey&   eql)
  188.     : hash(hf), equals(eql), get_key(ExtractKey()), num_elements(0)
  189.   {
  190.     initialize_buckets(n);
  191.   }
  192.   hashtable(const hashtable& ht)
  193.     : hash(ht.hash), equals(ht.equals), get_key(ht.get_key), num_elements(0)
  194.   {
  195.     copy_from(ht);
  196.   }
  197.   hashtable& operator= (const hashtable& ht)
  198.   {
  199.     if (&ht != this) {
  200.       clear();
  201.       hash = ht.hash;
  202.       equals = ht.equals;
  203.       get_key = ht.get_key;
  204.       copy_from(ht);
  205.     }
  206.     return *this;
  207.   }
  208.   ~hashtable() { clear(); }
  209.   size_type size() const { return num_elements; }
  210.   size_type max_size() const { return size_type(-1); }
  211.   bool empty() const { return size() == 0; }
  212.   void swap(hashtable& ht)
  213.   {
  214.     __STD::swap(hash, ht.hash);
  215.     __STD::swap(equals, ht.equals);
  216.     __STD::swap(get_key, ht.get_key);
  217.     buckets.swap(ht.buckets);
  218.     __STD::swap(num_elements, ht.num_elements);
  219.   }
  220.   iterator begin()
  221.   { 
  222.     for (size_type n = 0; n < buckets.size(); ++n)
  223.       if (buckets[n])
  224.         return iterator(buckets[n], this);
  225.     return end();
  226.   }
  227.   iterator end() { return iterator(0, this); }
  228.   const_iterator begin() const
  229.   {
  230.     for (size_type n = 0; n < buckets.size(); ++n)
  231.       if (buckets[n])
  232.         return const_iterator(buckets[n], this);
  233.     return end();
  234.   }
  235.   const_iterator end() const { return const_iterator(0, this); }
  236.   friend bool
  237.   operator== __STL_NULL_TMPL_ARGS (const hashtable&, const hashtable&);
  238. public:
  239.   size_type bucket_count() const { return buckets.size(); }
  240.   size_type max_bucket_count() const
  241.     { return __stl_prime_list[__stl_num_primes - 1]; } 
  242.   size_type elems_in_bucket(size_type bucket) const
  243.   {
  244.     size_type result = 0;
  245.     for (node* cur = buckets[bucket]; cur; cur = cur->next)
  246.       result += 1;
  247.     return result;
  248.   }
  249.   pair<iterator, bool> insert_unique(const value_type& obj)
  250.   {
  251.     resize(num_elements + 1);
  252.     return insert_unique_noresize(obj);
  253.   }
  254.   iterator insert_equal(const value_type& obj)
  255.   {
  256.     resize(num_elements + 1);
  257.     return insert_equal_noresize(obj);
  258.   }
  259.   pair<iterator, bool> insert_unique_noresize(const value_type& obj);
  260.   iterator insert_equal_noresize(const value_type& obj);
  261.  
  262. #ifdef __STL_MEMBER_TEMPLATES
  263.   template <class InputIterator>
  264.   void insert_unique(InputIterator f, InputIterator l)
  265.   {
  266.     insert_unique(f, l, iterator_category(f));
  267.   }
  268.   template <class InputIterator>
  269.   void insert_equal(InputIterator f, InputIterator l)
  270.   {
  271.     insert_equal(f, l, iterator_category(f));
  272.   }
  273.   template <class InputIterator>
  274.   void insert_unique(InputIterator f, InputIterator l,
  275.                      input_iterator_tag)
  276.   {
  277.     for ( ; f != l; ++f)
  278.       insert_unique(*f);
  279.   }
  280.   template <class InputIterator>
  281.   void insert_equal(InputIterator f, InputIterator l,
  282.                     input_iterator_tag)
  283.   {
  284.     for ( ; f != l; ++f)
  285.       insert_equal(*f);
  286.   }
  287.   template <class ForwardIterator>
  288.   void insert_unique(ForwardIterator f, ForwardIterator l,
  289.                      forward_iterator_tag)
  290.   {
  291.     size_type n = 0;
  292.     distance(f, l, n);
  293.     resize(num_elements + n);
  294.     for ( ; n > 0; --n, ++f)
  295.       insert_unique_noresize(*f);
  296.   }
  297.   template <class ForwardIterator>
  298.   void insert_equal(ForwardIterator f, ForwardIterator l,
  299.                     forward_iterator_tag)
  300.   {
  301.     size_type n = 0;
  302.     distance(f, l, n);
  303.     resize(num_elements + n);
  304.     for ( ; n > 0; --n, ++f)
  305.       insert_equal_noresize(*f);
  306.   }
  307. #else /* __STL_MEMBER_TEMPLATES */
  308.   void insert_unique(const value_type* f, const value_type* l)
  309.   {
  310.     size_type n = l - f;
  311.     resize(num_elements + n);
  312.     for ( ; n > 0; --n, ++f)
  313.       insert_unique_noresize(*f);
  314.   }
  315.   void insert_equal(const value_type* f, const value_type* l)
  316.   {
  317.     size_type n = l - f;
  318.     resize(num_elements + n);
  319.     for ( ; n > 0; --n, ++f)
  320.       insert_equal_noresize(*f);
  321.   }
  322.   void insert_unique(const_iterator f, const_iterator l)
  323.   {
  324.     size_type n = 0;
  325.     distance(f, l, n);
  326.     resize(num_elements + n);
  327.     for ( ; n > 0; --n, ++f)
  328.       insert_unique_noresize(*f);
  329.   }
  330.   void insert_equal(const_iterator f, const_iterator l)
  331.   {
  332.     size_type n = 0;
  333.     distance(f, l, n);
  334.     resize(num_elements + n);
  335.     for ( ; n > 0; --n, ++f)
  336.       insert_equal_noresize(*f);
  337.   }
  338. #endif /*__STL_MEMBER_TEMPLATES */
  339.   reference find_or_insert(const value_type& obj);
  340.   iterator find(const key_type& key) 
  341.   {
  342.     size_type n = bkt_num_key(key);
  343.     node* first;
  344.     for ( first = buckets[n];
  345.           first && !equals(get_key(first->val), key);
  346.           first = first->next)
  347.       {}
  348.     return iterator(first, this);
  349.   } 
  350.   const_iterator find(const key_type& key) const
  351.   {
  352.     size_type n = bkt_num_key(key);
  353.     const node* first;
  354.     for ( first = buckets[n];
  355.           first && !equals(get_key(first->val), key);
  356.           first = first->next)
  357.       {}
  358.     return const_iterator(first, this);
  359.   } 
  360.   size_type count(const key_type& key) const
  361.   {
  362.     const size_type n = bkt_num_key(key);
  363.     size_type result = 0;
  364.     for (const node* cur = buckets[n]; cur; cur = cur->next)
  365.       if (equals(get_key(cur->val), key))
  366.         ++result;
  367.     return result;
  368.   }
  369.   pair<iterator, iterator> equal_range(const key_type& key);
  370.   pair<const_iterator, const_iterator> equal_range(const key_type& key) const;
  371.   size_type erase(const key_type& key);
  372.   void erase(const iterator& it);
  373.   void erase(iterator first, iterator last);
  374.   void erase(const const_iterator& it);
  375.   void erase(const_iterator first, const_iterator last);
  376.   void resize(size_type num_elements_hint);
  377.   void clear();
  378. private:
  379.   size_type next_size(size_type n) const { return __stl_next_prime(n); }
  380.   void initialize_buckets(size_type n)
  381.   {
  382.     const size_type n_buckets = next_size(n);
  383.     buckets.reserve(n_buckets);
  384.     buckets.insert(buckets.end(), n_buckets, (node*) 0);
  385.     num_elements = 0;
  386.   }
  387.   size_type bkt_num_key(const key_type& key) const
  388.   {
  389.     return bkt_num_key(key, buckets.size());
  390.   }
  391.   size_type bkt_num(const value_type& obj) const
  392.   {
  393.     return bkt_num_key(get_key(obj));
  394.   }
  395.   size_type bkt_num_key(const key_type& key, size_t n) const
  396.   {
  397.     return hash(key) % n;
  398.   }
  399.   size_type bkt_num(const value_type& obj, size_t n) const
  400.   {
  401.     return bkt_num_key(get_key(obj), n);
  402.   }
  403.   node* new_node(const value_type& obj)
  404.   {
  405.     node* n = node_allocator::allocate();
  406.     n->next = 0;
  407.     __STL_TRY {
  408.       construct(&n->val, obj);
  409.       return n;
  410.     }
  411.     __STL_UNWIND(node_allocator::deallocate(n));
  412.   }
  413.   
  414.   void delete_node(node* n)
  415.   {
  416.     destroy(&n->val);
  417.     node_allocator::deallocate(n);
  418.   }
  419.   void erase_bucket(const size_type n, node* first, node* last);
  420.   void erase_bucket(const size_type n, node* last);
  421.   void copy_from(const hashtable& ht);
  422. };
  423. template <class V, class K, class HF, class ExK, class EqK, class A>
  424. __hashtable_iterator<V, K, HF, ExK, EqK, A>&
  425. __hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++()
  426. {
  427.   const node* old = cur;
  428.   cur = cur->next;
  429.   if (!cur) {
  430.     size_type bucket = ht->bkt_num(old->val);
  431.     while (!cur && ++bucket < ht->buckets.size())
  432.       cur = ht->buckets[bucket];
  433.   }
  434.   return *this;
  435. }
  436. template <class V, class K, class HF, class ExK, class EqK, class A>
  437. inline __hashtable_iterator<V, K, HF, ExK, EqK, A>
  438. __hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++(int)
  439. {
  440.   iterator tmp = *this;
  441.   ++*this;
  442.   return tmp;
  443. }
  444. template <class V, class K, class HF, class ExK, class EqK, class A>
  445. __hashtable_const_iterator<V, K, HF, ExK, EqK, A>&
  446. __hashtable_const_iterator<V, K, HF, ExK, EqK, A>::operator++()
  447. {
  448.   const node* old = cur;
  449.   cur = cur->next;
  450.   if (!cur) {
  451.     size_type bucket = ht->bkt_num(old->val);
  452.     while (!cur && ++bucket < ht->buckets.size())
  453.       cur = ht->buckets[bucket];
  454.   }
  455.   return *this;
  456. }
  457. template <class V, class K, class HF, class ExK, class EqK, class A>
  458. inline __hashtable_const_iterator<V, K, HF, ExK, EqK, A>
  459. __hashtable_const_iterator<V, K, HF, ExK, EqK, A>::operator++(int)
  460. {
  461.   const_iterator tmp = *this;
  462.   ++*this;
  463.   return tmp;
  464. }
  465. #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
  466. template <class V, class K, class HF, class ExK, class EqK, class All>
  467. inline forward_iterator_tag
  468. iterator_category(const __hashtable_iterator<V, K, HF, ExK, EqK, All>&)
  469. {
  470.   return forward_iterator_tag();
  471. }
  472. template <class V, class K, class HF, class ExK, class EqK, class All>
  473. inline V* value_type(const __hashtable_iterator<V, K, HF, ExK, EqK, All>&)
  474. {
  475.   return (V*) 0;
  476. }
  477. template <class V, class K, class HF, class ExK, class EqK, class All>
  478. inline hashtable<V, K, HF, ExK, EqK, All>::difference_type*
  479. distance_type(const __hashtable_iterator<V, K, HF, ExK, EqK, All>&)
  480. {
  481.   return (hashtable<V, K, HF, ExK, EqK, All>::difference_type*) 0;
  482. }
  483. template <class V, class K, class HF, class ExK, class EqK, class All>
  484. inline forward_iterator_tag
  485. iterator_category(const __hashtable_const_iterator<V, K, HF, ExK, EqK, All>&)
  486. {
  487.   return forward_iterator_tag();
  488. }
  489. template <class V, class K, class HF, class ExK, class EqK, class All>
  490. inline V* 
  491. value_type(const __hashtable_const_iterator<V, K, HF, ExK, EqK, All>&)
  492. {
  493.   return (V*) 0;
  494. }
  495. template <class V, class K, class HF, class ExK, class EqK, class All>
  496. inline hashtable<V, K, HF, ExK, EqK, All>::difference_type*
  497. distance_type(const __hashtable_const_iterator<V, K, HF, ExK, EqK, All>&)
  498. {
  499.   return (hashtable<V, K, HF, ExK, EqK, All>::difference_type*) 0;
  500. }
  501. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  502. template <class V, class K, class HF, class Ex, class Eq, class A>
  503. bool operator==(const hashtable<V, K, HF, Ex, Eq, A>& ht1,
  504.                 const hashtable<V, K, HF, Ex, Eq, A>& ht2)
  505. {
  506.   typedef typename hashtable<V, K, HF, Ex, Eq, A>::node node;
  507.   if (ht1.buckets.size() != ht2.buckets.size())
  508.     return false;
  509.   for (int n = 0; n < ht1.buckets.size(); ++n) {
  510.     node* cur1 = ht1.buckets[n];
  511.     node* cur2 = ht2.buckets[n];
  512.     for ( ; cur1 && cur2 && cur1->val == cur2->val;
  513.           cur1 = cur1->next, cur2 = cur2->next)
  514.       {}
  515.     if (cur1 || cur2)
  516.       return false;
  517.   }
  518.   return true;
  519. }  
  520. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  521. template <class Val, class Key, class HF, class Extract, class EqKey, class A>
  522. inline void swap(hashtable<Val, Key, HF, Extract, EqKey, A>& ht1,
  523.                  hashtable<Val, Key, HF, Extract, EqKey, A>& ht2) {
  524.   ht1.swap(ht2);
  525. }
  526. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  527. template <class V, class K, class HF, class Ex, class Eq, class A>
  528. pair<typename hashtable<V, K, HF, Ex, Eq, A>::iterator, bool> 
  529. hashtable<V, K, HF, Ex, Eq, A>::insert_unique_noresize(const value_type& obj)
  530. {
  531.   const size_type n = bkt_num(obj);
  532.   node* first = buckets[n];
  533.   for (node* cur = first; cur; cur = cur->next) 
  534.     if (equals(get_key(cur->val), get_key(obj)))
  535.       return pair<iterator, bool>(iterator(cur, this), false);
  536.   node* tmp = new_node(obj);
  537.   tmp->next = first;
  538.   buckets[n] = tmp;
  539.   ++num_elements;
  540.   return pair<iterator, bool>(iterator(tmp, this), true);
  541. }
  542. template <class V, class K, class HF, class Ex, class Eq, class A>
  543. typename hashtable<V, K, HF, Ex, Eq, A>::iterator 
  544. hashtable<V, K, HF, Ex, Eq, A>::insert_equal_noresize(const value_type& obj)
  545. {
  546.   const size_type n = bkt_num(obj);
  547.   node* first = buckets[n];
  548.   for (node* cur = first; cur; cur = cur->next) 
  549.     if (equals(get_key(cur->val), get_key(obj))) {
  550.       node* tmp = new_node(obj);
  551.       tmp->next = cur->next;
  552.       cur->next = tmp;
  553.       ++num_elements;
  554.       return iterator(tmp, this);
  555.     }
  556.   node* tmp = new_node(obj);
  557.   tmp->next = first;
  558.   buckets[n] = tmp;
  559.   ++num_elements;
  560.   return iterator(tmp, this);
  561. }
  562. template <class V, class K, class HF, class Ex, class Eq, class A>
  563. typename hashtable<V, K, HF, Ex, Eq, A>::reference 
  564. hashtable<V, K, HF, Ex, Eq, A>::find_or_insert(const value_type& obj)
  565. {
  566.   resize(num_elements + 1);
  567.   size_type n = bkt_num(obj);
  568.   node* first = buckets[n];
  569.   for (node* cur = first; cur; cur = cur->next)
  570.     if (equals(get_key(cur->val), get_key(obj)))
  571.       return cur->val;
  572.   node* tmp = new_node(obj);
  573.   tmp->next = first;
  574.   buckets[n] = tmp;
  575.   ++num_elements;
  576.   return tmp->val;
  577. }
  578. template <class V, class K, class HF, class Ex, class Eq, class A>
  579. pair<typename hashtable<V, K, HF, Ex, Eq, A>::iterator,
  580.      typename hashtable<V, K, HF, Ex, Eq, A>::iterator> 
  581. hashtable<V, K, HF, Ex, Eq, A>::equal_range(const key_type& key)
  582. {
  583.   typedef pair<iterator, iterator> pii;
  584.   const size_type n = bkt_num_key(key);
  585.   for (node* first = buckets[n]; first; first = first->next) {
  586.     if (equals(get_key(first->val), key)) {
  587.       for (node* cur = first->next; cur; cur = cur->next)
  588.         if (!equals(get_key(cur->val), key))
  589.           return pii(iterator(first, this), iterator(cur, this));
  590.       for (size_type m = n + 1; m < buckets.size(); ++m)
  591.         if (buckets[m])
  592.           return pii(iterator(first, this),
  593.                      iterator(buckets[m], this));
  594.       return pii(iterator(first, this), end());
  595.     }
  596.   }
  597.   return pii(end(), end());
  598. }
  599. template <class V, class K, class HF, class Ex, class Eq, class A>
  600. pair<typename hashtable<V, K, HF, Ex, Eq, A>::const_iterator, 
  601.      typename hashtable<V, K, HF, Ex, Eq, A>::const_iterator> 
  602. hashtable<V, K, HF, Ex, Eq, A>::equal_range(const key_type& key) const
  603. {
  604.   typedef pair<const_iterator, const_iterator> pii;
  605.   const size_type n = bkt_num_key(key);
  606.   for (const node* first = buckets[n] ; first; first = first->next) {
  607.     if (equals(get_key(first->val), key)) {
  608.       for (const node* cur = first->next; cur; cur = cur->next)
  609.         if (!equals(get_key(cur->val), key))
  610.           return pii(const_iterator(first, this),
  611.                      const_iterator(cur, this));
  612.       for (size_type m = n + 1; m < buckets.size(); ++m)
  613.         if (buckets[m])
  614.           return pii(const_iterator(first, this),
  615.                      const_iterator(buckets[m], this));
  616.       return pii(const_iterator(first, this), end());
  617.     }
  618.   }
  619.   return pii(end(), end());
  620. }
  621. template <class V, class K, class HF, class Ex, class Eq, class A>
  622. typename hashtable<V, K, HF, Ex, Eq, A>::size_type 
  623. hashtable<V, K, HF, Ex, Eq, A>::erase(const key_type& key)
  624. {
  625.   const size_type n = bkt_num_key(key);
  626.   node* first = buckets[n];
  627.   size_type erased = 0;
  628.   if (first) {
  629.     node* cur = first;
  630.     node* next = cur->next;
  631.     while (next) {
  632.       if (equals(get_key(next->val), key)) {
  633.         cur->next = next->next;
  634.         delete_node(next);
  635.         next = cur->next;
  636.         ++erased;
  637.         --num_elements;
  638.       }
  639.       else {
  640.         cur = next;
  641.         next = cur->next;
  642.       }
  643.     }
  644.     if (equals(get_key(first->val), key)) {
  645.       buckets[n] = first->next;
  646.       delete_node(first);
  647.       ++erased;
  648.       --num_elements;
  649.     }
  650.   }
  651.   return erased;
  652. }
  653. template <class V, class K, class HF, class Ex, class Eq, class A>
  654. void hashtable<V, K, HF, Ex, Eq, A>::erase(const iterator& it)
  655. {
  656.   if (node* const p = it.cur) {
  657.     const size_type n = bkt_num(p->val);
  658.     node* cur = buckets[n];
  659.     if (cur == p) {
  660.       buckets[n] = cur->next;
  661.       delete_node(cur);
  662.       --num_elements;
  663.     }
  664.     else {
  665.       node* next = cur->next;
  666.       while (next) {
  667.         if (next == p) {
  668.           cur->next = next->next;
  669.           delete_node(next);
  670.           --num_elements;
  671.           break;
  672.         }
  673.         else {
  674.           cur = next;
  675.           next = cur->next;
  676.         }
  677.       }
  678.     }
  679.   }
  680. }
  681. template <class V, class K, class HF, class Ex, class Eq, class A>
  682. void hashtable<V, K, HF, Ex, Eq, A>::erase(iterator first, iterator last)
  683. {
  684.   size_type f_bucket = first.cur ? bkt_num(first.cur->val) : buckets.size();
  685.   size_type l_bucket = last.cur ? bkt_num(last.cur->val) : buckets.size();
  686.   if (first.cur == last.cur)
  687.     return;
  688.   else if (f_bucket == l_bucket)
  689.     erase_bucket(f_bucket, first.cur, last.cur);
  690.   else {
  691.     erase_bucket(f_bucket, first.cur, 0);
  692.     for (size_type n = f_bucket + 1; n < l_bucket; ++n)
  693.       erase_bucket(n, 0);
  694.     if (l_bucket != buckets.size())
  695.       erase_bucket(l_bucket, last.cur);
  696.   }
  697. }
  698. template <class V, class K, class HF, class Ex, class Eq, class A>
  699. inline void
  700. hashtable<V, K, HF, Ex, Eq, A>::erase(const_iterator first,
  701.                                       const_iterator last)
  702. {
  703.   erase(iterator(const_cast<node*>(first.cur),
  704.                  const_cast<hashtable*>(first.ht)),
  705.         iterator(const_cast<node*>(last.cur),
  706.                  const_cast<hashtable*>(last.ht)));
  707. }
  708. template <class V, class K, class HF, class Ex, class Eq, class A>
  709. inline void
  710. hashtable<V, K, HF, Ex, Eq, A>::erase(const const_iterator& it)
  711. {
  712.   erase(iterator(const_cast<node*>(it.cur),
  713.                  const_cast<hashtable*>(it.ht)));
  714. }
  715. template <class V, class K, class HF, class Ex, class Eq, class A>
  716. void hashtable<V, K, HF, Ex, Eq, A>::resize(size_type num_elements_hint)
  717. {
  718.   const size_type old_n = buckets.size();
  719.   if (num_elements_hint > old_n) {
  720.     const size_type n = next_size(num_elements_hint);
  721.     if (n > old_n) {
  722.       vector<node*, A> tmp(n, (node*) 0);
  723.       __STL_TRY {
  724.         for (size_type bucket = 0; bucket < old_n; ++bucket) {
  725.           node* first = buckets[bucket];
  726.           while (first) {
  727.             size_type new_bucket = bkt_num(first->val, n);
  728.             buckets[bucket] = first->next;
  729.             first->next = tmp[new_bucket];
  730.             tmp[new_bucket] = first;
  731.             first = buckets[bucket];          
  732.           }
  733.         }
  734.         buckets.swap(tmp);
  735.       }
  736. #         ifdef __STL_USE_EXCEPTIONS
  737.       catch(...) {
  738.         for (size_type bucket = 0; bucket < tmp.size(); ++bucket) {
  739.           while (tmp[bucket]) {
  740.             node* next = tmp[bucket]->next;
  741.             delete_node(tmp[bucket]);
  742.             tmp[bucket] = next;
  743.           }
  744.         }
  745.         throw;
  746.       }
  747. #         endif /* __STL_USE_EXCEPTIONS */
  748.     }
  749.   }
  750. }
  751. template <class V, class K, class HF, class Ex, class Eq, class A>
  752. void hashtable<V, K, HF, Ex, Eq, A>::erase_bucket(const size_type n, 
  753.                                                   node* first, node* last)
  754. {
  755.   node* cur = buckets[n];
  756.   if (cur == first)
  757.     erase_bucket(n, last);
  758.   else {
  759.     node* next;
  760.     for (next = cur->next; next != first; cur = next, next = cur->next)
  761.       ;
  762.     while (next) {
  763.       cur->next = next->next;
  764.       delete_node(next);
  765.       next = cur->next;
  766.       --num_elements;
  767.     }
  768.   }
  769. }
  770. template <class V, class K, class HF, class Ex, class Eq, class A>
  771. void 
  772. hashtable<V, K, HF, Ex, Eq, A>::erase_bucket(const size_type n, node* last)
  773. {
  774.   node* cur = buckets[n];
  775.   while (cur != last) {
  776.     node* next = cur->next;
  777.     delete_node(cur);
  778.     cur = next;
  779.     buckets[n] = cur;
  780.     --num_elements;
  781.   }
  782. }
  783. template <class V, class K, class HF, class Ex, class Eq, class A>
  784. void hashtable<V, K, HF, Ex, Eq, A>::clear()
  785. {
  786.   for (size_type i = 0; i < buckets.size(); ++i) {
  787.     node* cur = buckets[i];
  788.     while (cur != 0) {
  789.       node* next = cur->next;
  790.       delete_node(cur);
  791.       cur = next;
  792.     }
  793.     buckets[i] = 0;
  794.   }
  795.   num_elements = 0;
  796. }
  797.     
  798. template <class V, class K, class HF, class Ex, class Eq, class A>
  799. void hashtable<V, K, HF, Ex, Eq, A>::copy_from(const hashtable& ht)
  800. {
  801.   buckets.clear();
  802.   buckets.reserve(ht.buckets.size());
  803.   buckets.insert(buckets.end(), ht.buckets.size(), (node*) 0);
  804.   __STL_TRY {
  805.     for (size_type i = 0; i < ht.buckets.size(); ++i) {
  806.       if (const node* cur = ht.buckets[i]) {
  807.         node* copy = new_node(cur->val);
  808.         buckets[i] = copy;
  809.         for (node* next = cur->next; next; cur = next, next = cur->next) {
  810.           copy->next = new_node(next->val);
  811.           copy = copy->next;
  812.         }
  813.       }
  814.     }
  815.     num_elements = ht.num_elements;
  816.   }
  817.   __STL_UNWIND(clear());
  818. }
  819. __STL_END_NAMESPACE
  820. #endif /* __SGI_STL_INTERNAL_HASHTABLE_H */
  821. // Local Variables:
  822. // mode:C++
  823. // End: