| /* |
| * Copyright (c) 1996 |
| * 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. |
| * |
| */ |
| |
| #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 <algo.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 const Value& const_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; } |
| 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 Value& reference; |
| typedef const Value& const_reference; |
| typedef 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) {} |
| const_reference operator*() const { return cur->val; } |
| 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); |
| } |
| |
| template <class BidirectionalIterator> |
| void insert_unique(BidirectionalIterator f, BidirectionalIterator l, |
| bidirectional_iterator_tag) |
| { |
| insert_unique(f, l, forward_iterator_tag()); |
| } |
| |
| template <class BidirectionalIterator> |
| void insert_equal(BidirectionalIterator f, BidirectionalIterator l, |
| bidirectional_iterator_tag) |
| { |
| insert_equal(f, l, forward_iterator_tag()); |
| } |
| |
| template <class RandomAccessIterator> |
| void insert_unique(RandomAccessIterator f, RandomAccessIterator l, |
| random_access_iterator_tag) |
| { |
| insert_unique(f, l, forward_iterator_tag()); |
| } |
| |
| template <class RandomAccessIterator> |
| void insert_equal(RandomAccessIterator f, RandomAccessIterator l, |
| random_access_iterator_tag) |
| { |
| insert_equal(f, l, forward_iterator_tag()); |
| } |
| |
| #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; |
| } |
| |
| |
| 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; |
| } |
| |
| 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 */ |
| } |
| |
| |
| #endif /* __SGI_STL_HASHTABLE_H */ |