diff options
Diffstat (limited to 'libstdc++/stl/stl_hashtable.h')
| -rw-r--r-- | libstdc++/stl/stl_hashtable.h | 948 |
1 files changed, 948 insertions, 0 deletions
diff --git a/libstdc++/stl/stl_hashtable.h b/libstdc++/stl/stl_hashtable.h new file mode 100644 index 00000000000..2452f625d3d --- /dev/null +++ b/libstdc++/stl/stl_hashtable.h @@ -0,0 +1,948 @@ +/* + * 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. + * + */ + +/* NOTE: This is an internal header file, included by other STL headers. + * You should not attempt to use it directly. + */ + +#ifndef __SGI_STL_INTERNAL_HASHTABLE_H +#define __SGI_STL_INTERNAL_HASHTABLE_H + +// Hashtable class, used to implement the hashed associative containers +// hash_set, hash_map, hash_multiset, and hash_multimap. + +#include <stl_algobase.h> +#include <stl_alloc.h> +#include <stl_construct.h> +#include <stl_tempbuf.h> +#include <stl_algo.h> +#include <stl_uninitialized.h> +#include <stl_function.h> +#include <stl_vector.h> +#include <stl_hash_fun.h> + +__STL_BEGIN_NAMESPACE + +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) + { + __STD::swap(hash, ht.hash); + __STD::swap(equals, ht.equals); + __STD::swap(get_key, ht.get_key); + buckets.swap(ht.buckets); + __STD::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== __STL_NULL_TMPL_ARGS (const hashtable&, const hashtable&); + +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; + __STL_TRY { + construct(&n->val, obj); + return n; + } + __STL_UNWIND(node_allocator::deallocate(n)); + } + + 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 typename 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; +} + +#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER + +template <class Val, class Key, class HF, class Extract, class EqKey, class A> +inline void swap(hashtable<Val, Key, HF, Extract, EqKey, A>& ht1, + hashtable<Val, Key, HF, Extract, EqKay, A>& ht2) { + ht1.swap(ht2); +} + +#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ + + +template <class V, class K, class HF, class Ex, class Eq, class A> +pair<typename 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> +typename 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> +typename 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<typename hashtable<V, K, HF, Ex, Eq, A>::iterator, + typename 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<typename hashtable<V, K, HF, Ex, Eq, A>::const_iterator, + typename 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> +typename 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<node*>(first.cur), + const_cast<hashtable*>(first.ht)), + iterator(const_cast<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<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); + __STL_TRY { + 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); + __STL_TRY { + 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; + } + __STL_UNWIND(clear()); +} + +__STL_END_NAMESPACE + +#endif /* __SGI_STL_INTERNAL_HASHTABLE_H */ + +// Local Variables: +// mode:C++ +// End: |
