Subversion Repositories scarts

// 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)

      {

        std::swap(_M_hash, __ht._M_hash);

        std::swap(_M_equals, __ht._M_equals);

        std::swap(_M_get_key, __ht._M_get_key);

        _M_buckets.swap(__ht._M_buckets);

        std::swap(_M_num_elements, __ht._M_num_elements);

      }

      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(__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)

    {