Makefile.in (install): Some of HEADERS come from the stl dir now.

	* Makefile.in (install): Some of HEADERS come from the stl dir now.
	* algorithm, deque, functional, iterator, list, map, memory, numeric,
 	queue, set, stack, utility, vector: Now in stl dir.

stl/:
	* algo.h, algobase.h, alloc.h, bvector.h, defalloc.h, deque.h,
 	function.h, hash_map.h, hash_set.h, hashtable.h, heap.h, iterator.h,
 	list.h, map.h, multimap.h, multiset.h, pair.h, pthread_alloc.h,
 	rope.h, ropeimpl.h, set.h, slist.h, stack.h, stl_config.h, tempbuf.h,
 	tree.h, type_traits.h, vector.h: Update to October 27 SGI snapshot.
	* algorithm, deque, functional, hash_map, hash_set, iterator, list,
 	map, memory, numeric, pthread_alloc, queue, rope, set, slist, stack,
 	stl_algo.h, stl_algobase.h, stl_alloc.h, stl_bvector.h,
 	stl_construct.h, stl_deque.h, stl_function.h, stl_hash_fun.h,
 	stl_hash_map.h, stl_hash_set.h, stl_hashtable.h, stl_heap.h,
 	stl_iterator.h, stl_list.h, stl_map.h, stl_multimap.h, stl_multiset.h,
 	stl_numeric.h, stl_pair.h, stl_queue.h, stl_raw_storage_iter.h,
 	stl_relops.h, stl_rope.h, stl_set.h, stl_slist.h, stl_stack.h,
 	stl_tempbuf.h, stl_tree.h, stl_uninitialized.h, stl_vector.h,
 	utility, vector: New files in October 27 SGI snapshot.

From-SVN: r16277

1 files changed, 15 insertions, 959 deletions

diff --git a/libstdc++/stl/hashtable.h b/libstdc++/stl/hashtable.h
index fb4abc2..15dbfc9 100644
--- a/libstdc++/stl/hashtable.h
+++ b/libstdc++/stl/hashtable.h
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 1996
+ * Copyright (c) 1996,1997
  * Silicon Graphics Computer Systems, Inc.
  *
  * Permission to use, copy, modify, distribute and sell this software
@@ -24,969 +24,25 @@
  *
  */
 
+/* NOTE: This is an internal header file, included by other STL headers.
+ *   You should not attempt to use it directly.
+ */
+
 #ifndef __SGI_STL_HASHTABLE_H
 #define __SGI_STL_HASHTABLE_H
 
-// Hashtable class, used to implement the hashed associative containers
-// hash_set, hash_map, hash_multiset, and hash_multimap.
-
-
-#include <stdlib.h>
-#include <stddef.h>
+#include <stl_hashtable.h>
 #include <algo.h>
+#include <alloc.h>
 #include <vector.h>
 
-
-template <class Key> struct hash { };
-
-inline size_t __stl_hash_string(const char* s)
-{
-  unsigned long h = 0; 
-  for ( ; *s; ++s)
-    h = 5*h + *s;
-  
-  return size_t(h);
-}
-
-struct hash<char*>
-{
-  size_t operator()(const char* s) const { return __stl_hash_string(s); }
-};
-
-struct hash<const char*>
-{
-  size_t operator()(const char* s) const { return __stl_hash_string(s); }
-};
-
-struct hash<char> {
-  size_t operator()(char x) const { return x; }
-};
-struct hash<unsigned char> {
-  size_t operator()(unsigned char x) const { return x; }
-};
-struct hash<signed char> {
-  size_t operator()(unsigned char x) const { return x; }
-};
-struct hash<short> {
-  size_t operator()(short x) const { return x; }
-};
-struct hash<unsigned short> {
-  size_t operator()(unsigned short x) const { return x; }
-};
-struct hash<int> {
-  size_t operator()(int x) const { return x; }
-};
-struct hash<unsigned int> {
-  size_t operator()(unsigned int x) const { return x; }
-};
-struct hash<long> {
-  size_t operator()(long x) const { return x; }
-};
-struct hash<unsigned long> {
-  size_t operator()(unsigned long x) const { return x; }
-};
-
-template <class Value>
-struct __hashtable_node
-{
-  __hashtable_node* next;
-  Value val;
-};  
-
-template <class Value, class Key, class HashFcn,
-          class ExtractKey, class EqualKey, class Alloc = alloc>
-class hashtable;
-
-template <class Value, class Key, class HashFcn,
-          class ExtractKey, class EqualKey, class Alloc>
-struct __hashtable_iterator;
-
-template <class Value, class Key, class HashFcn,
-          class ExtractKey, class EqualKey, class Alloc>
-struct __hashtable_const_iterator;
-
-template <class Value, class Key, class HashFcn,
-          class ExtractKey, class EqualKey, class Alloc>
-struct __hashtable_iterator {
-  typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
-          hashtable;
-  typedef __hashtable_iterator<Value, Key, HashFcn, 
-                               ExtractKey, EqualKey, Alloc>
-          iterator;
-  typedef __hashtable_const_iterator<Value, Key, HashFcn, 
-                                     ExtractKey, EqualKey, Alloc>
-          const_iterator;
-  typedef __hashtable_node<Value> node;
-
-  typedef forward_iterator_tag iterator_category;
-  typedef Value value_type;
-  typedef ptrdiff_t difference_type;
-  typedef size_t size_type;
-  typedef Value& reference;
-  typedef Value* pointer;
-
-  node* cur;
-  hashtable* ht;
-
-  __hashtable_iterator(node* n, hashtable* tab) : cur(n), ht(tab) {}
-  __hashtable_iterator() {}
-  reference operator*() const { return cur->val; }
-#ifndef __SGI_STL_NO_ARROW_OPERATOR
-  pointer operator->() const { return &(operator*()); }
-#endif /* __SGI_STL_NO_ARROW_OPERATOR */
-  iterator& operator++();
-  iterator operator++(int);
-  bool operator==(const iterator& it) const { return cur == it.cur; }
-  bool operator!=(const iterator& it) const { return cur != it.cur; }
-};
-
-
-template <class Value, class Key, class HashFcn,
-          class ExtractKey, class EqualKey, class Alloc>
-struct __hashtable_const_iterator {
-  typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
-          hashtable;
-  typedef __hashtable_iterator<Value, Key, HashFcn, 
-                               ExtractKey, EqualKey, Alloc>
-          iterator;
-  typedef __hashtable_const_iterator<Value, Key, HashFcn, 
-                                     ExtractKey, EqualKey, Alloc>
-          const_iterator;
-  typedef __hashtable_node<Value> node;
-
-  typedef forward_iterator_tag iterator_category;
-  typedef Value value_type;
-  typedef ptrdiff_t difference_type;
-  typedef size_t size_type;
-  typedef const Value& reference;
-  typedef const Value* pointer;
-
-  const node* cur;
-  const hashtable* ht;
-
-  __hashtable_const_iterator(const node* n, const hashtable* tab)
-    : cur(n), ht(tab) {}
-  __hashtable_const_iterator() {}
-  __hashtable_const_iterator(const iterator& it) : cur(it.cur), ht(it.ht) {}
-  reference operator*() const { return cur->val; }
-#ifndef __SGI_STL_NO_ARROW_OPERATOR
-  pointer operator->() const { return &(operator*()); }
-#endif /* __SGI_STL_NO_ARROW_OPERATOR */
-  const_iterator& operator++();
-  const_iterator operator++(int);
-  bool operator==(const const_iterator& it) const { return cur == it.cur; }
-  bool operator!=(const const_iterator& it) const { return cur != it.cur; }
-};
-
-// Note: assumes long is at least 32 bits.
-static const int __stl_num_primes = 28;
-static const unsigned long __stl_prime_list[__stl_num_primes] =
-{
-  53,         97,         193,       389,       769,
-  1543,       3079,       6151,      12289,     24593,
-  49157,      98317,      196613,    393241,    786433,
-  1572869,    3145739,    6291469,   12582917,  25165843,
-  50331653,   100663319,  201326611, 402653189, 805306457, 
-  1610612741, 3221225473, 4294967291
-};
-
-inline unsigned long __stl_next_prime(unsigned long n)
-{
-  const unsigned long* first = __stl_prime_list;
-  const unsigned long* last = __stl_prime_list + __stl_num_primes;
-  const unsigned long* pos = lower_bound(first, last, n);
-  return pos == last ? *(last - 1) : *pos;
-}
-
-
-template <class Value, class Key, class HashFcn,
-          class ExtractKey, class EqualKey,
-          class Alloc>
-class hashtable {
-public:
-  typedef Key key_type;
-  typedef Value 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 hash; }
-  key_equal key_eq() const { return equals; }
-
-private:
-  hasher hash;
-  key_equal equals;
-  ExtractKey get_key;
-
-  typedef __hashtable_node<Value> node;
-  typedef simple_alloc<node, Alloc> node_allocator;
-
-  vector<node*,Alloc> buckets;
-  size_type num_elements;
-
-public:
-  typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, 
-                               Alloc>
-  iterator;
-
-  typedef __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey,
-                                     Alloc>
-  const_iterator;
-
-  friend struct
-  __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>;
-  friend struct
-  __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>;
-
-public:
-  hashtable(size_type n,
-            const HashFcn&    hf,
-            const EqualKey&   eql,
-            const ExtractKey& ext)
-    : hash(hf), equals(eql), get_key(ext), num_elements(0)
-  {
-    initialize_buckets(n);
-  }
-
-  hashtable(size_type n,
-            const HashFcn&    hf,
-            const EqualKey&   eql)
-    : hash(hf), equals(eql), get_key(ExtractKey()), num_elements(0)
-  {
-    initialize_buckets(n);
-  }
-
-  hashtable(const hashtable& ht)
-    : hash(ht.hash), equals(ht.equals), get_key(ht.get_key), num_elements(0)
-  {
-    copy_from(ht);
-  }
-
-  hashtable& operator= (const hashtable& ht)
-  {
-    if (&ht != this) {
-      clear();
-      hash = ht.hash;
-      equals = ht.equals;
-      get_key = ht.get_key;
-      copy_from(ht);
-    }
-    return *this;
-  }
-
-  ~hashtable() { clear(); }
-
-  size_type size() const { return num_elements; }
-  size_type max_size() const { return size_type(-1); }
-  bool empty() const { return size() == 0; }
-
-  void swap(hashtable& ht)
-  {
-    ::swap(hash, ht.hash);
-    ::swap(equals, ht.equals);
-    ::swap(get_key, ht.get_key);
-    buckets.swap(ht.buckets);
-    ::swap(num_elements, ht.num_elements);
-  }
-
-  iterator begin()
-  { 
-    for (size_type n = 0; n < buckets.size(); ++n)
-      if (buckets[n])
-        return iterator(buckets[n], this);
-    return end();
-  }
-
-  iterator end() { return iterator(0, this); }
-
-  const_iterator begin() const
-  {
-    for (size_type n = 0; n < buckets.size(); ++n)
-      if (buckets[n])
-        return const_iterator(buckets[n], this);
-    return end();
-  }
-
-  const_iterator end() const { return const_iterator(0, this); }
-
-  friend bool operator== (const hashtable<Value, Key,
-                                          HashFcn, ExtractKey, EqualKey,
-                                          Alloc>&,
-                          const hashtable<Value, Key,
-                                          HashFcn, ExtractKey, EqualKey,
-                                          Alloc>&);
-
-public:
-
-  size_type bucket_count() const { return buckets.size(); }
-
-  size_type max_bucket_count() const
-    { return __stl_prime_list[__stl_num_primes - 1]; } 
-
-  size_type elems_in_bucket(size_type bucket) const
-  {
-    size_type result = 0;
-    for (node* cur = buckets[bucket]; cur; cur = cur->next)
-      result += 1;
-    return result;
-  }
-
-  pair<iterator, bool> insert_unique(const value_type& obj)
-  {
-    resize(num_elements + 1);
-    return insert_unique_noresize(obj);
-  }
-
-  iterator insert_equal(const value_type& obj)
-  {
-    resize(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);
- 
-#ifdef __STL_MEMBER_TEMPLATES
-  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 = 0;
-    distance(f, l, n);
-    resize(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 = 0;
-    distance(f, l, n);
-    resize(num_elements + n);
-    for ( ; n > 0; --n, ++f)
-      insert_equal_noresize(*f);
-  }
-
-#else /* __STL_MEMBER_TEMPLATES */
-  void insert_unique(const value_type* f, const value_type* l)
-  {
-    size_type n = l - f;
-    resize(num_elements + n);
-    for ( ; n > 0; --n, ++f)
-      insert_unique_noresize(*f);
-  }
-
-  void insert_equal(const value_type* f, const value_type* l)
-  {
-    size_type n = l - f;
-    resize(num_elements + n);
-    for ( ; n > 0; --n, ++f)
-      insert_equal_noresize(*f);
-  }
-
-  void insert_unique(const_iterator f, const_iterator l)
-  {
-    size_type n = 0;
-    distance(f, l, n);
-    resize(num_elements + n);
-    for ( ; n > 0; --n, ++f)
-      insert_unique_noresize(*f);
-  }
-
-  void insert_equal(const_iterator f, const_iterator l)
-  {
-    size_type n = 0;
-    distance(f, l, n);
-    resize(num_elements + n);
-    for ( ; n > 0; --n, ++f)
-      insert_equal_noresize(*f);
-  }
-#endif /*__STL_MEMBER_TEMPLATES */
-
-  reference find_or_insert(const value_type& obj);
-
-  iterator find(const key_type& key) 
-  {
-    size_type n = bkt_num_key(key);
-    node* first;
-    for ( first = buckets[n];
-          first && !equals(get_key(first->val), key);
-          first = first->next)
-      {}
-    return iterator(first, this);
-  } 
-
-  const_iterator find(const key_type& key) const
-  {
-    size_type n = bkt_num_key(key);
-    const node* first;
-    for ( first = buckets[n];
-          first && !equals(get_key(first->val), key);
-          first = first->next)
-      {}
-    return const_iterator(first, this);
-  } 
-
-  size_type count(const key_type& key) const
-  {
-    const size_type n = bkt_num_key(key);
-    size_type result = 0;
-
-    for (const node* cur = buckets[n]; cur; cur = cur->next)
-      if (equals(get_key(cur->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 next_size(size_type n) const { return __stl_next_prime(n); }
-
-  void initialize_buckets(size_type n)
-  {
-    const size_type n_buckets = next_size(n);
-    buckets.reserve(n_buckets);
-    buckets.insert(buckets.end(), n_buckets, (node*) 0);
-    num_elements = 0;
-  }
-
-  size_type bkt_num_key(const key_type& key) const
-  {
-    return bkt_num_key(key, buckets.size());
-  }
-
-  size_type bkt_num(const value_type& obj) const
-  {
-    return bkt_num_key(get_key(obj));
-  }
-
-  size_type bkt_num_key(const key_type& key, size_t n) const
-  {
-    return hash(key) % n;
-  }
-
-  size_type bkt_num(const value_type& obj, size_t n) const
-  {
-    return bkt_num_key(get_key(obj), n);
-  }
-
-  node* new_node(const value_type& obj)
-  {
-    node* n = node_allocator::allocate();
-    n->next = 0;
-#       ifdef __STL_USE_EXCEPTIONS
-    try {
-#       endif /* __STL_USE_EXCEPTIONS */
-      construct(&n->val, obj);
-      return n;
-#       ifdef __STL_USE_EXCEPTIONS
-    }
-    catch(...) {
-      node_allocator::deallocate(n);
-      throw;
-    }
-#       endif /* __STL_USE_EXCEPTIONS */
-  }
-  
-  void delete_node(node* n)
-  {
-    destroy(&n->val);
-    node_allocator::deallocate(n);
-  }
-
-  void erase_bucket(const size_type n, node* first, node* last);
-  void erase_bucket(const size_type n, node* last);
-
-  void copy_from(const hashtable& ht);
-
-};
-
-template <class V, class K, class HF, class ExK, class EqK, class A>
-__hashtable_iterator<V, K, HF, ExK, EqK, A>&
-__hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++()
-{
-  const node* old = cur;
-  cur = cur->next;
-  if (!cur) {
-    size_type bucket = ht->bkt_num(old->val);
-    while (!cur && ++bucket < ht->buckets.size())
-      cur = ht->buckets[bucket];
-  }
-  return *this;
-}
-
-template <class V, class K, class HF, class ExK, class EqK, class A>
-inline __hashtable_iterator<V, K, HF, ExK, EqK, A>
-__hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++(int)
-{
-  iterator tmp = *this;
-  ++*this;
-  return tmp;
-}
-
-template <class V, class K, class HF, class ExK, class EqK, class A>
-__hashtable_const_iterator<V, K, HF, ExK, EqK, A>&
-__hashtable_const_iterator<V, K, HF, ExK, EqK, A>::operator++()
-{
-  const node* old = cur;
-  cur = cur->next;
-  if (!cur) {
-    size_type bucket = ht->bkt_num(old->val);
-    while (!cur && ++bucket < ht->buckets.size())
-      cur = ht->buckets[bucket];
-  }
-  return *this;
-}
-
-template <class V, class K, class HF, class ExK, class EqK, class A>
-inline __hashtable_const_iterator<V, K, HF, ExK, EqK, A>
-__hashtable_const_iterator<V, K, HF, ExK, EqK, A>::operator++(int)
-{
-  const_iterator tmp = *this;
-  ++*this;
-  return tmp;
-}
-
-#ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
-
-template <class V, class K, class HF, class ExK, class EqK, class All>
-inline forward_iterator_tag
-iterator_category(const __hashtable_iterator<V, K, HF, ExK, EqK, All>&)
-{
-  return forward_iterator_tag();
-}
-
-template <class V, class K, class HF, class ExK, class EqK, class All>
-inline V* value_type(const __hashtable_iterator<V, K, HF, ExK, EqK, All>&)
-{
-  return (V*) 0;
-}
-
-template <class V, class K, class HF, class ExK, class EqK, class All>
-inline hashtable<V, K, HF, ExK, EqK, All>::difference_type*
-distance_type(const __hashtable_iterator<V, K, HF, ExK, EqK, All>&)
-{
-  return (hashtable<V, K, HF, ExK, EqK, All>::difference_type*) 0;
-}
-
-template <class V, class K, class HF, class ExK, class EqK, class All>
-inline forward_iterator_tag
-iterator_category(const __hashtable_const_iterator<V, K, HF, ExK, EqK, All>&)
-{
-  return forward_iterator_tag();
-}
-
-template <class V, class K, class HF, class ExK, class EqK, class All>
-inline V* 
-value_type(const __hashtable_const_iterator<V, K, HF, ExK, EqK, All>&)
-{
-  return (V*) 0;
-}
-
-template <class V, class K, class HF, class ExK, class EqK, class All>
-inline hashtable<V, K, HF, ExK, EqK, All>::difference_type*
-distance_type(const __hashtable_const_iterator<V, K, HF, ExK, EqK, All>&)
-{
-  return (hashtable<V, K, HF, ExK, EqK, All>::difference_type*) 0;
-}
-
-#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
-
-template <class V, class K, class HF, class Ex, class Eq, class A>
-bool operator==(const hashtable<V, K, HF, Ex, Eq, A>& ht1,
-                const hashtable<V, K, HF, Ex, Eq, A>& ht2)
-{
-  typedef hashtable<V, K, HF, Ex, Eq, A>::node node;
-  if (ht1.buckets.size() != ht2.buckets.size())
-    return false;
-  for (int n = 0; n < ht1.buckets.size(); ++n) {
-    node* cur1 = ht1.buckets[n];
-    node* cur2 = ht2.buckets[n];
-    for ( ; cur1 && cur2 && cur1->val == cur2->val;
-          cur1 = cur1->next, cur2 = cur2->next)
-      {}
-    if (cur1 || cur2)
-      return false;
-  }
-  return true;
-}  
-
-template <class V, class K, class HF, class Ex, class Eq, class A>
-pair<hashtable<V, K, HF, Ex, Eq, A>::iterator, bool> 
-hashtable<V, K, HF, Ex, Eq, A>::insert_unique_noresize(const value_type& obj)
-{
-  const size_type n = bkt_num(obj);
-  node* first = buckets[n];
-
-  for (node* cur = first; cur; cur = cur->next) 
-    if (equals(get_key(cur->val), get_key(obj)))
-      return pair<iterator, bool>(iterator(cur, this), false);
-
-  node* tmp = new_node(obj);
-  tmp->next = first;
-  buckets[n] = tmp;
-  ++num_elements;
-  return pair<iterator, bool>(iterator(tmp, this), true);
-}
-
-template <class V, class K, class HF, class Ex, class Eq, class A>
-hashtable<V, K, HF, Ex, Eq, A>::iterator 
-hashtable<V, K, HF, Ex, Eq, A>::insert_equal_noresize(const value_type& obj)
-{
-  const size_type n = bkt_num(obj);
-  node* first = buckets[n];
-
-  for (node* cur = first; cur; cur = cur->next) 
-    if (equals(get_key(cur->val), get_key(obj))) {
-      node* tmp = new_node(obj);
-      tmp->next = cur->next;
-      cur->next = tmp;
-      ++num_elements;
-      return iterator(tmp, this);
-    }
-
-  node* tmp = new_node(obj);
-  tmp->next = first;
-  buckets[n] = tmp;
-  ++num_elements;
-  return iterator(tmp, this);
-}
-
-template <class V, class K, class HF, class Ex, class Eq, class A>
-hashtable<V, K, HF, Ex, Eq, A>::reference 
-hashtable<V, K, HF, Ex, Eq, A>::find_or_insert(const value_type& obj)
-{
-  resize(num_elements + 1);
-
-  size_type n = bkt_num(obj);
-  node* first = buckets[n];
-
-  for (node* cur = first; cur; cur = cur->next)
-    if (equals(get_key(cur->val), get_key(obj)))
-      return cur->val;
-
-  node* tmp = new_node(obj);
-  tmp->next = first;
-  buckets[n] = tmp;
-  ++num_elements;
-  return tmp->val;
-}
-
-template <class V, class K, class HF, class Ex, class Eq, class A>
-pair<hashtable<V, K, HF, Ex, Eq, A>::iterator,
-     hashtable<V, K, HF, Ex, Eq, A>::iterator> 
-hashtable<V, K, HF, Ex, Eq, A>::equal_range(const key_type& key)
-{
-  typedef pair<iterator, iterator> pii;
-  const size_type n = bkt_num_key(key);
-
-  for (node* first = buckets[n]; first; first = first->next) {
-    if (equals(get_key(first->val), key)) {
-      for (node* cur = first->next; cur; cur = cur->next)
-        if (!equals(get_key(cur->val), key))
-          return pii(iterator(first, this), iterator(cur, this));
-      for (size_type m = n + 1; m < buckets.size(); ++m)
-        if (buckets[m])
-          return pii(iterator(first, this),
-                     iterator(buckets[m], this));
-      return pii(iterator(first, this), end());
-    }
-  }
-  return pii(end(), end());
-}
-
-template <class V, class K, class HF, class Ex, class Eq, class A>
-pair<hashtable<V, K, HF, Ex, Eq, A>::const_iterator, 
-     hashtable<V, K, HF, Ex, Eq, A>::const_iterator> 
-hashtable<V, K, HF, Ex, Eq, A>::equal_range(const key_type& key) const
-{
-  typedef pair<const_iterator, const_iterator> pii;
-  const size_type n = bkt_num_key(key);
-
-  for (const node* first = buckets[n] ; first; first = first->next) {
-    if (equals(get_key(first->val), key)) {
-      for (const node* cur = first->next; cur; cur = cur->next)
-        if (!equals(get_key(cur->val), key))
-          return pii(const_iterator(first, this),
-                     const_iterator(cur, this));
-      for (size_type m = n + 1; m < buckets.size(); ++m)
-        if (buckets[m])
-          return pii(const_iterator(first, this),
-                     const_iterator(buckets[m], this));
-      return pii(const_iterator(first, this), end());
-    }
-  }
-  return pii(end(), end());
-}
-
-template <class V, class K, class HF, class Ex, class Eq, class A>
-hashtable<V, K, HF, Ex, Eq, A>::size_type 
-hashtable<V, K, HF, Ex, Eq, A>::erase(const key_type& key)
-{
-  const size_type n = bkt_num_key(key);
-  node* first = buckets[n];
-  size_type erased = 0;
-
-  if (first) {
-    node* cur = first;
-    node* next = cur->next;
-    while (next) {
-      if (equals(get_key(next->val), key)) {
-        cur->next = next->next;
-        delete_node(next);
-        next = cur->next;
-        ++erased;
-        --num_elements;
-      }
-      else {
-        cur = next;
-        next = cur->next;
-      }
-    }
-    if (equals(get_key(first->val), key)) {
-      buckets[n] = first->next;
-      delete_node(first);
-      ++erased;
-      --num_elements;
-    }
-  }
-  return erased;
-}
-
-template <class V, class K, class HF, class Ex, class Eq, class A>
-void hashtable<V, K, HF, Ex, Eq, A>::erase(const iterator& it)
-{
-  if (node* const p = it.cur) {
-    const size_type n = bkt_num(p->val);
-    node* cur = buckets[n];
-
-    if (cur == p) {
-      buckets[n] = cur->next;
-      delete_node(cur);
-      --num_elements;
-    }
-    else {
-      node* next = cur->next;
-      while (next) {
-        if (next == p) {
-          cur->next = next->next;
-          delete_node(next);
-          --num_elements;
-          break;
-        }
-        else {
-          cur = next;
-          next = cur->next;
-        }
-      }
-    }
-  }
-}
-
-template <class V, class K, class HF, class Ex, class Eq, class A>
-void hashtable<V, K, HF, Ex, Eq, A>::erase(iterator first, iterator last)
-{
-  size_type f_bucket = first.cur ? bkt_num(first.cur->val) : buckets.size();
-  size_type l_bucket = last.cur ? bkt_num(last.cur->val) : buckets.size();
-
-  if (first.cur == last.cur)
-    return;
-  else if (f_bucket == l_bucket)
-    erase_bucket(f_bucket, first.cur, last.cur);
-  else {
-    erase_bucket(f_bucket, first.cur, 0);
-    for (size_type n = f_bucket + 1; n < l_bucket; ++n)
-      erase_bucket(n, 0);
-    if (l_bucket != buckets.size())
-      erase_bucket(l_bucket, last.cur);
-  }
-}
-
-template <class V, class K, class HF, class Ex, class Eq, class A>
-inline void
-hashtable<V, K, HF, Ex, Eq, A>::erase(const_iterator first,
-                                      const_iterator last)
-{
-  erase(iterator(const_cast<hashtable::node*>(first.cur),
-                 const_cast<hashtable*>(first.ht)),
-        iterator(const_cast<hashtable::node*>(last.cur),
-                 const_cast<hashtable*>(last.ht)));
-}
-
-template <class V, class K, class HF, class Ex, class Eq, class A>
-inline void
-hashtable<V, K, HF, Ex, Eq, A>::erase(const const_iterator& it)
-{
-  erase(iterator(const_cast<hashtable::node*>(it.cur),
-                 const_cast<hashtable*>(it.ht)));
-}
-
-template <class V, class K, class HF, class Ex, class Eq, class A>
-void hashtable<V, K, HF, Ex, Eq, A>::resize(size_type num_elements_hint)
-{
-  const size_type old_n = buckets.size();
-  if (num_elements_hint > old_n) {
-    const size_type n = next_size(num_elements_hint);
-    if (n > old_n) {
-      vector<node*, A> tmp(n, (node*) 0);
-#         ifdef __STL_USE_EXCEPTIONS
-      try {
-#         endif /* __STL_USE_EXCEPTIONS */
-        for (size_type bucket = 0; bucket < old_n; ++bucket) {
-          node* first = buckets[bucket];
-          while (first) {
-            size_type new_bucket = bkt_num(first->val, n);
-            buckets[bucket] = first->next;
-            first->next = tmp[new_bucket];
-            tmp[new_bucket] = first;
-            first = buckets[bucket];          
-          }
-        }
-        buckets.swap(tmp);
-#         ifdef __STL_USE_EXCEPTIONS
-      }
-      catch(...) {
-        for (size_type bucket = 0; bucket < tmp.size(); ++bucket) {
-          while (tmp[bucket]) {
-            node* next = tmp[bucket]->next;
-            delete_node(tmp[bucket]);
-            tmp[bucket] = next;
-          }
-        }
-        throw;
-      }
-#         endif /* __STL_USE_EXCEPTIONS */
-    }
-  }
-}
-
-template <class V, class K, class HF, class Ex, class Eq, class A>
-void hashtable<V, K, HF, Ex, Eq, A>::erase_bucket(const size_type n, 
-                                                  node* first, node* last)
-{
-  node* cur = buckets[n];
-  if (cur == first)
-    erase_bucket(n, last);
-  else {
-    node* next;
-    for (next = cur->next; next != first; cur = next, next = cur->next)
-      ;
-    while (next) {
-      cur->next = next->next;
-      delete_node(next);
-      next = cur->next;
-      --num_elements;
-    }
-  }
-}
-
-template <class V, class K, class HF, class Ex, class Eq, class A>
-void 
-hashtable<V, K, HF, Ex, Eq, A>::erase_bucket(const size_type n, node* last)
-{
-  node* cur = buckets[n];
-  while (cur != last) {
-    node* next = cur->next;
-    delete_node(cur);
-    cur = next;
-    buckets[n] = cur;
-    --num_elements;
-  }
-}
-
-template <class V, class K, class HF, class Ex, class Eq, class A>
-void hashtable<V, K, HF, Ex, Eq, A>::clear()
-{
-  for (size_type i = 0; i < buckets.size(); ++i) {
-    node* cur = buckets[i];
-    while (cur != 0) {
-      node* next = cur->next;
-      delete_node(cur);
-      cur = next;
-    }
-    buckets[i] = 0;
-  }
-  num_elements = 0;
-}
-
-    
-template <class V, class K, class HF, class Ex, class Eq, class A>
-void hashtable<V, K, HF, Ex, Eq, A>::copy_from(const hashtable& ht)
-{
-  buckets.clear();
-  buckets.reserve(ht.buckets.size());
-  buckets.insert(buckets.end(), ht.buckets.size(), (node*) 0);
-#   ifdef __STL_USE_EXCEPTIONS
-  try {
-#   endif /* __STL_USE_EXCEPTIONS */
-    for (size_type i = 0; i < ht.buckets.size(); ++i) {
-      if (const node* cur = ht.buckets[i]) {
-        node* copy = new_node(cur->val);
-        buckets[i] = copy;
-
-        for (node* next = cur->next; next; cur = next, next = cur->next) {
-          copy->next = new_node(next->val);
-          copy = copy->next;
-        }
-      }
-    }
-    num_elements = ht.num_elements;
-#   ifdef __STL_USE_EXCEPTIONS
-  }
-  catch(...) {
-    clear();
-    throw;
-  }
-#   endif /* __STL_USE_EXCEPTIONS */
-}
-
+#ifdef __STL_USE_NAMESPACES
+using __STD::hash;
+using __STD::hashtable;
+#endif /* __STL_USE_NAMESPACES */
 
 #endif /* __SGI_STL_HASHTABLE_H */
+
+// Local Variables:
+// mode:C++
+// End: