hashtable.h

mpeg4 video codec mpeg4 video codec

      }

      iterator
      begin()
      {
	for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
	  if (_M_buckets[__n])
	    return iterator(_M_buckets[__n], this);
	return end();
      }

      iterator
      end()
      { return iterator(0, this); }

      const_iterator
      begin() const
      {
	for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
	  if (_M_buckets[__n])
	    return const_iterator(_M_buckets[__n], this);
	return end();
      }

      const_iterator
      end() const
      { return const_iterator(0, this); }

      template <class _Vl, class _Ky, class _HF, class _Ex, class _Eq,
		class _Al>
        friend bool
        operator==(const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&,
		   const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&);

    public:
      size_type
      bucket_count() const
      { return _M_buckets.size(); }

      size_type
      max_bucket_count() const
      { return __stl_prime_list[(int)_S_num_primes - 1]; }

      size_type
      elems_in_bucket(size_type __bucket) const
      {
	size_type __result = 0;
	for (_Node* __cur = _M_buckets[__bucket]; __cur; __cur = __cur->_M_next)
	  __result += 1;
	return __result;
      }

      pair<iterator, bool>
      insert_unique(const value_type& __obj)
      {
	resize(_M_num_elements + 1);
	return insert_unique_noresize(__obj);
      }

      iterator
      insert_equal(const value_type& __obj)
      {
	resize(_M_num_elements + 1);
	return insert_equal_noresize(__obj);
      }

      pair<iterator, bool>
      insert_unique_noresize(const value_type& __obj);

      iterator
      insert_equal_noresize(const value_type& __obj);

      template <class _InputIterator>
        void
        insert_unique(_InputIterator __f, _InputIterator __l)
        { insert_unique(__f, __l, __iterator_category(__f)); }

      template <class _InputIterator>
        void
        insert_equal(_InputIterator __f, _InputIterator __l)
        { insert_equal(__f, __l, __iterator_category(__f)); }

      template <class _InputIterator>
        void
        insert_unique(_InputIterator __f, _InputIterator __l,
		      input_iterator_tag)
        {
	  for ( ; __f != __l; ++__f)
	    insert_unique(*__f);
	}

      template <class _InputIterator>
        void
        insert_equal(_InputIterator __f, _InputIterator __l,
		     input_iterator_tag)
        {
	  for ( ; __f != __l; ++__f)
	    insert_equal(*__f);
	}

      template <class _ForwardIterator>
        void
        insert_unique(_ForwardIterator __f, _ForwardIterator __l,
		      forward_iterator_tag)
        {
	  size_type __n = distance(__f, __l);
	  resize(_M_num_elements + __n);
	  for ( ; __n > 0; --__n, ++__f)
	    insert_unique_noresize(*__f);
	}

      template <class _ForwardIterator>
        void
        insert_equal(_ForwardIterator __f, _ForwardIterator __l,
		     forward_iterator_tag)
        {
	  size_type __n = distance(__f, __l);
	  resize(_M_num_elements + __n);
	  for ( ; __n > 0; --__n, ++__f)
	    insert_equal_noresize(*__f);
	}

      reference
      find_or_insert(const value_type& __obj);

      iterator
      find(const key_type& __key)
      {
	size_type __n = _M_bkt_num_key(__key);
	_Node* __first;
	for (__first = _M_buckets[__n];
	     __first && !_M_equals(_M_get_key(__first->_M_val), __key);
	     __first = __first->_M_next)
	  {}
	return iterator(__first, this);
      }

      const_iterator
      find(const key_type& __key) const
      {
	size_type __n = _M_bkt_num_key(__key);
	const _Node* __first;
	for (__first = _M_buckets[__n];
	     __first && !_M_equals(_M_get_key(__first->_M_val), __key);
	     __first = __first->_M_next)
	  {}
	return const_iterator(__first, this);
      }

      size_type
      count(const key_type& __key) const
      {
	const size_type __n = _M_bkt_num_key(__key);
	size_type __result = 0;
	
	for (const _Node* __cur = _M_buckets[__n]; __cur;
	     __cur = __cur->_M_next)
	  if (_M_equals(_M_get_key(__cur->_M_val), __key))
	    ++__result;
	return __result;
      }

      pair<iterator, iterator>
      equal_range(const key_type& __key);

      pair<const_iterator, const_iterator>
      equal_range(const key_type& __key) const;

      size_type
      erase(const key_type& __key);
      
      void
      erase(const iterator& __it);

      void
      erase(iterator __first, iterator __last);

      void
      erase(const const_iterator& __it);

      void
      erase(const_iterator __first, const_iterator __last);

      void
      resize(size_type __num_elements_hint);

      void
      clear();

    private:
      size_type
      _M_next_size(size_type __n) const
      { return __stl_next_prime((unsigned long)__n); }

      void
      _M_initialize_buckets(size_type __n)
      {
	const size_type __n_buckets = _M_next_size(__n);
	_M_buckets.reserve(__n_buckets);
	_M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0);
	_M_num_elements = 0;
      }

      size_type
      _M_bkt_num_key(const key_type& __key) const
      { return _M_bkt_num_key(__key, _M_buckets.size()); }

      size_type
      _M_bkt_num(const value_type& __obj) const
      { return _M_bkt_num_key(_M_get_key(__obj)); }

      size_type
      _M_bkt_num_key(const key_type& __key, size_t __n) const
      { return _M_hash(__key) % __n; }

      size_type
      _M_bkt_num(const value_type& __obj, size_t __n) const
      { return _M_bkt_num_key(_M_get_key(__obj), __n); }

      _Node*
      _M_new_node(const value_type& __obj)
      {
	_Node* __n = _M_get_node();
	__n->_M_next = 0;
	try
	  {
	    this->get_allocator().construct(&__n->_M_val, __obj);
	    return __n;
	  }
	catch(...)
	  {
	    _M_put_node(__n);
	    __throw_exception_again;
	  }
      }

      void
      _M_delete_node(_Node* __n)
      {
	this->get_allocator().destroy(&__n->_M_val);
	_M_put_node(__n);
      }
      
      void
      _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last);

      void
      _M_erase_bucket(const size_type __n, _Node* __last);

      void
      _M_copy_from(const hashtable& __ht);
    };

  template <class _Val, class _Key, class _HF, class _ExK, class _EqK,
	    class _All>
    _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
    _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
    operator++()
    {
      const _Node* __old = _M_cur;
      _M_cur = _M_cur->_M_next;
      if (!_M_cur)
	{
	  size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
	  while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
	    _M_cur = _M_ht->_M_buckets[__bucket];
	}
      return *this;
    }

  template <class _Val, class _Key, class _HF, class _ExK, class _EqK,
	    class _All>
    inline _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
    _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
    operator++(int)
    {
      iterator __tmp = *this;
      ++*this;
      return __tmp;
    }

  template <class _Val, class _Key, class _HF, class _ExK, class _EqK,
	    class _All>
    _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
    _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
    operator++()
    {
      const _Node* __old = _M_cur;
      _M_cur = _M_cur->_M_next;
      if (!_M_cur)
	{
	  size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
	  while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
	    _M_cur = _M_ht->_M_buckets[__bucket];
	}
      return *this;
    }

  template <class _Val, class _Key, class _HF, class _ExK, class _EqK,
	    class _All>
    inline _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
    _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
    operator++(int)
    {
      const_iterator __tmp = *this;
      ++*this;
      return __tmp;
    }

  template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
    bool
    operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
	       const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
    {
      typedef typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_Node _Node;

      if (__ht1._M_buckets.size() != __ht2._M_buckets.size())
	return false;

      for (size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n)
	{
	  _Node* __cur1 = __ht1._M_buckets[__n];
	  _Node* __cur2 = __ht2._M_buckets[__n];
	  // Check same length of lists
	  for (; __cur1 && __cur2;
	       __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next)
	    {}
	  if (__cur1 || __cur2)
	    return false;
	  // Now check one's elements are in the other
	  for (__cur1 = __ht1._M_buckets[__n] ; __cur1;
	       __cur1 = __cur1->_M_next)
	    {
	      bool _found__cur1 = false;
	      for (_Node* __cur2 = __ht2._M_buckets[__n];
		   __cur2; __cur2 = __cur2->_M_next)
		{
		  if (__cur1->_M_val == __cur2->_M_val)
		    {
		      _found__cur1 = true;
		      break;
		    }
		}
	      if (!_found__cur1)
		return false;
	    }
	}
      return true;
    }

  template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
    inline bool
    operator!=(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
	       const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
    { return !(__ht1 == __ht2); }

  template <class _Val, class _Key, class _HF, class _Extract, class _EqKey,
	    class _All>
    inline void
    swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1,
	 hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2)
    { __ht1.swap(__ht2); }

  template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
    pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, bool>
    hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
    insert_unique_noresize(const value_type& __obj)
    {
      const size_type __n = _M_bkt_num(__obj);
      _Node* __first = _M_buckets[__n];
      
      for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
	if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
	  return pair<iterator, bool>(iterator(__cur, this), false);
      
      _Node* __tmp = _M_new_node(__obj);
      __tmp->_M_next = __first;
      _M_buckets[__n] = __tmp;