// Hashtable implementation used by containers -*- C++ -*-// Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.//// This file is part of the GNU ISO C++ Library.  This library is free// software; you can redistribute it and/or modify it under the// terms of the GNU General Public License as published by the// Free Software Foundation; either version 2, or (at your option)// any later version.// This library is distributed in the hope that it will be useful,// but WITHOUT ANY WARRANTY; without even the implied warranty of// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the// GNU General Public License for more details.// You should have received a copy of the GNU General Public License along// with this library; see the file COPYING.  If not, write to the Free// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,// USA.// As a special exception, you may use this file as part of a free software// library without restriction.  Specifically, if other files instantiate// templates or use macros or inline functions from this file, or you compile// this file and link it with other files to produce an executable, this// file does not by itself cause the resulting executable to be covered by// the GNU General Public License.  This exception does not however// invalidate any other reasons why the executable file might be covered by// the GNU General Public License./* * Copyright (c) 1996,1997 * Silicon Graphics Computer Systems, Inc. * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation.  Silicon Graphics makes no * representations about the suitability of this software for any * purpose.  It is provided "as is" without express or implied warranty. * * * Copyright (c) 1994 * Hewlett-Packard Company * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation.  Hewlett-Packard Company makes no * representations about the suitability of this software for any * purpose.  It is provided "as is" without express or implied warranty. * *//** @file ext/hashtable.h *  This file is a GNU extension to the Standard C++ Library (possibly *  containing extensions from the HP/SGI STL subset). */#ifndef _HASHTABLE_H#define _HASHTABLE_H 1// Hashtable class, used to implement the hashed associative containers// hash_set, hash_map, hash_multiset, and hash_multimap.#include <vector>#include <iterator>#include <bits/stl_algo.h>#include <bits/stl_function.h>#include <ext/hash_fun.h>namespace __gnu_cxx{  using std::size_t;  using std::ptrdiff_t;  using std::forward_iterator_tag;  using std::input_iterator_tag;  using std::_Construct;  using std::_Destroy;  using std::distance;  using std::vector;  using std::pair;  using std::__iterator_category;  template <class _Val>    struct _Hashtable_node    {      _Hashtable_node* _M_next;      _Val _M_val;    };  template <class _Val, class _Key, class _HashFcn, class _ExtractKey, 	    class _EqualKey, class _Alloc = std::allocator<_Val> >    class hashtable;  template <class _Val, class _Key, class _HashFcn,	    class _ExtractKey, class _EqualKey, class _Alloc>    struct _Hashtable_iterator;  template <class _Val, class _Key, class _HashFcn,	    class _ExtractKey, class _EqualKey, class _Alloc>    struct _Hashtable_const_iterator;  template <class _Val, class _Key, class _HashFcn,	    class _ExtractKey, class _EqualKey, class _Alloc>    struct _Hashtable_iterator    {      typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>        _Hashtable;      typedef _Hashtable_iterator<_Val, _Key, _HashFcn,				  _ExtractKey, _EqualKey, _Alloc>        iterator;      typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,					_ExtractKey, _EqualKey, _Alloc>        const_iterator;      typedef _Hashtable_node<_Val> _Node;      typedef forward_iterator_tag iterator_category;      typedef _Val value_type;      typedef ptrdiff_t difference_type;      typedef size_t size_type;      typedef _Val& reference;      typedef _Val* pointer;            _Node* _M_cur;      _Hashtable* _M_ht;      _Hashtable_iterator(_Node* __n, _Hashtable* __tab)      : _M_cur(__n), _M_ht(__tab) {}      _Hashtable_iterator() {}      reference      operator*() const      { return _M_cur->_M_val; }      pointer      operator->() const      { return &(operator*()); }      iterator&      operator++();      iterator      operator++(int);      bool      operator==(const iterator& __it) const      { return _M_cur == __it._M_cur; }      bool      operator!=(const iterator& __it) const      { return _M_cur != __it._M_cur; }    };  template <class _Val, class _Key, class _HashFcn,	    class _ExtractKey, class _EqualKey, class _Alloc>    struct _Hashtable_const_iterator    {      typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>        _Hashtable;      typedef _Hashtable_iterator<_Val,_Key,_HashFcn,				  _ExtractKey,_EqualKey,_Alloc>        iterator;      typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,					_ExtractKey, _EqualKey, _Alloc>        const_iterator;      typedef _Hashtable_node<_Val> _Node;      typedef forward_iterator_tag iterator_category;      typedef _Val value_type;      typedef ptrdiff_t difference_type;      typedef size_t size_type;      typedef const _Val& reference;      typedef const _Val* pointer;            const _Node* _M_cur;      const _Hashtable* _M_ht;      _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab)      : _M_cur(__n), _M_ht(__tab) {}      _Hashtable_const_iterator() {}      _Hashtable_const_iterator(const iterator& __it)      : _M_cur(__it._M_cur), _M_ht(__it._M_ht) {}      reference      operator*() const      { return _M_cur->_M_val; }      pointer      operator->() const      { return &(operator*()); }      const_iterator&      operator++();      const_iterator      operator++(int);      bool      operator==(const const_iterator& __it) const      { return _M_cur == __it._M_cur; }      bool      operator!=(const const_iterator& __it) const      { return _M_cur != __it._M_cur; }    };  // Note: assumes long is at least 32 bits.  enum { _S_num_primes = 28 };  static const unsigned long __stl_prime_list[_S_num_primes] =    {      53ul,         97ul,         193ul,       389ul,       769ul,      1543ul,       3079ul,       6151ul,      12289ul,     24593ul,      49157ul,      98317ul,      196613ul,    393241ul,    786433ul,      1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,      50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,      1610612741ul, 3221225473ul, 4294967291ul    };  inline unsigned long  __stl_next_prime(unsigned long __n)  {    const unsigned long* __first = __stl_prime_list;    const unsigned long* __last = __stl_prime_list + (int)_S_num_primes;    const unsigned long* pos = std::lower_bound(__first, __last, __n);    return pos == __last ? *(__last - 1) : *pos;  }  // Forward declaration of operator==.    template <class _Val, class _Key, class _HF, class _Ex,	    class _Eq, class _All>    class hashtable;  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);  // Hashtables handle allocators a bit differently than other  // containers do.  If we're using standard-conforming allocators, then  // a hashtable unconditionally has a member variable to hold its  // allocator, even if it so happens that all instances of the  // allocator type are identical.  This is because, for hashtables,  // this extra storage is negligible.  Additionally, a base class  // wouldn't serve any other purposes; it wouldn't, for example,  // simplify the exception-handling code.    template <class _Val, class _Key, class _HashFcn,	    class _ExtractKey, class _EqualKey, class _Alloc>    class hashtable    {    public:      typedef _Key key_type;      typedef _Val value_type;      typedef _HashFcn hasher;      typedef _EqualKey key_equal;      typedef size_t            size_type;      typedef ptrdiff_t         difference_type;      typedef value_type*       pointer;      typedef const value_type* const_pointer;      typedef value_type&       reference;      typedef const value_type& const_reference;      hasher      hash_funct() const      { return _M_hash; }      key_equal      key_eq() const      { return _M_equals; }    private:      typedef _Hashtable_node<_Val> _Node;    public:      typedef typename _Alloc::template rebind<value_type>::other allocator_type;      allocator_type      get_allocator() const      { return _M_node_allocator; }    private:      typedef typename _Alloc::template rebind<_Node>::other _Node_Alloc;      typedef typename _Alloc::template rebind<_Node*>::other _Nodeptr_Alloc;      typedef vector<_Node*, _Nodeptr_Alloc> _Vector_type;      _Node_Alloc _M_node_allocator;      _Node*      _M_get_node()      { return _M_node_allocator.allocate(1); }      void      _M_put_node(_Node* __p)      { _M_node_allocator.deallocate(__p, 1); }    private:      hasher                _M_hash;      key_equal             _M_equals;      _ExtractKey           _M_get_key;      _Vector_type          _M_buckets;      size_type             _M_num_elements;          public:      typedef _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey,				  _EqualKey, _Alloc>        iterator;      typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,					_EqualKey, _Alloc>        const_iterator;      friend struct      _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>;      friend struct      _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,				_EqualKey, _Alloc>;    public:      hashtable(size_type __n, const _HashFcn& __hf,		const _EqualKey& __eql, const _ExtractKey& __ext,		const allocator_type& __a = allocator_type())      : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),	_M_get_key(__ext), _M_buckets(__a), _M_num_elements(0)      { _M_initialize_buckets(__n); }      hashtable(size_type __n, const _HashFcn& __hf,		const _EqualKey& __eql,		const allocator_type& __a = allocator_type())      : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),	_M_get_key(_ExtractKey()), _M_buckets(__a), _M_num_elements(0)      { _M_initialize_buckets(__n); }      hashtable(const hashtable& __ht)      : _M_node_allocator(__ht.get_allocator()), _M_hash(__ht._M_hash),      _M_equals(__ht._M_equals), _M_get_key(__ht._M_get_key),      _M_buckets(__ht.get_allocator()), _M_num_elements(0)      { _M_copy_from(__ht); }      hashtable&      operator= (const hashtable& __ht)      {	if (&__ht != this)	  {	    clear();	    _M_hash = __ht._M_hash;	    _M_equals = __ht._M_equals;	    _M_get_key = __ht._M_get_key;	    _M_copy_from(__ht);	  }	return *this;      }      ~hashtable()      { clear(); }      size_type      size() const      { return _M_num_elements; }      size_type      max_size() const      { return size_type(-1); }      bool      empty() const      { return size() == 0; }      void      swap(hashtable& __ht)      {