2 Copyright 2005-2011 Intel Corporation. All Rights Reserved.
4 This file is part of Threading Building Blocks.
6 Threading Building Blocks is free software; you can redistribute it
7 and/or modify it under the terms of the GNU General Public License
8 version 2 as published by the Free Software Foundation.
10 Threading Building Blocks is distributed in the hope that it will be
11 useful, but WITHOUT ANY WARRANTY; without even the implied warranty
12 of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with Threading Building Blocks; if not, write to the Free Software
17 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 As a special exception, you may use this file as part of a free software
20 library without restriction. Specifically, if other files instantiate
21 templates or use macros or inline functions from this file, or you compile
22 this file and link it with other files to produce an executable, this
23 file does not by itself cause the resulting executable to be covered by
24 the GNU General Public License. This exception does not however
25 invalidate any other reasons why the executable file might be covered by
26 the GNU General Public License.
29 /* Container implementations in this header are based on PPL implementations
30 provided by Microsoft. */
32 #ifndef __TBB_concurrent_unordered_map_H
33 #define __TBB_concurrent_unordered_map_H
35 #include "_concurrent_unordered_internal.h"
40 // Template class for hash compare
41 template<typename Key>
47 size_t operator()(const Key& key) const
49 return tbb_hasher(key);
53 namespace interface5 {
55 // Template class for hash map traits
56 template<typename Key, typename T, typename Hash_compare, typename Allocator, bool Allow_multimapping>
57 class concurrent_unordered_map_traits
60 typedef std::pair<const Key, T> value_type;
62 typedef Hash_compare hash_compare;
63 typedef typename Allocator::template rebind<value_type>::other allocator_type;
64 enum { allow_multimapping = Allow_multimapping };
66 concurrent_unordered_map_traits() : my_hash_compare() {}
67 concurrent_unordered_map_traits(const hash_compare& hc) : my_hash_compare(hc) {}
69 class value_compare : public std::binary_function<value_type, value_type, bool>
71 friend class concurrent_unordered_map_traits<Key, T, Hash_compare, Allocator, Allow_multimapping>;
74 bool operator()(const value_type& left, const value_type& right) const
76 return (my_hash_compare(left.first, right.first));
79 value_compare(const hash_compare& comparator) : my_hash_compare(comparator) {}
82 hash_compare my_hash_compare; // the comparator predicate for keys
85 template<class Type1, class Type2>
86 static const Key& get_key(const std::pair<Type1, Type2>& value) {
90 hash_compare my_hash_compare; // the comparator predicate for keys
93 template <typename Key, typename T, typename Hasher = tbb_hash<Key>, typename Key_equality = std::equal_to<Key>, typename Allocator = tbb::tbb_allocator<std::pair<const Key, T> > >
94 class concurrent_unordered_map : public internal::concurrent_unordered_base< concurrent_unordered_map_traits<Key, T, internal::hash_compare<Key, Hasher, Key_equality>, Allocator, false> >
96 // Base type definitions
97 typedef internal::hash_compare<Key, Hasher, Key_equality> hash_compare;
98 typedef internal::concurrent_unordered_base< concurrent_unordered_map_traits<Key, T, hash_compare, Allocator, false> > base_type;
99 typedef concurrent_unordered_map_traits<Key, T, internal::hash_compare<Key, Hasher, Key_equality>, Allocator, false> traits_type;
100 using traits_type::my_hash_compare;
101 #if __TBB_EXTRA_DEBUG
104 using traits_type::allow_multimapping;
106 using base_type::end;
107 using base_type::find;
108 using base_type::insert;
111 typedef Key key_type;
112 typedef typename base_type::value_type value_type;
113 typedef T mapped_type;
114 typedef Hasher hasher;
115 typedef Key_equality key_equal;
116 typedef hash_compare key_compare;
118 typedef typename base_type::allocator_type allocator_type;
119 typedef typename base_type::pointer pointer;
120 typedef typename base_type::const_pointer const_pointer;
121 typedef typename base_type::reference reference;
122 typedef typename base_type::const_reference const_reference;
124 typedef typename base_type::size_type size_type;
125 typedef typename base_type::difference_type difference_type;
127 typedef typename base_type::iterator iterator;
128 typedef typename base_type::const_iterator const_iterator;
129 typedef typename base_type::iterator local_iterator;
130 typedef typename base_type::const_iterator const_local_iterator;
132 // Construction/destruction/copying
133 explicit concurrent_unordered_map(size_type n_of_buckets = 8, const hasher& a_hasher = hasher(),
134 const key_equal& a_keyeq = key_equal(), const allocator_type& a = allocator_type())
135 : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
139 concurrent_unordered_map(const Allocator& a) : base_type(8, key_compare(), a)
143 template <typename Iterator>
144 concurrent_unordered_map(Iterator first, Iterator last, size_type n_of_buckets = 8, const hasher& a_hasher = hasher(),
145 const key_equal& a_keyeq = key_equal(), const allocator_type& a = allocator_type())
146 : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
148 for (; first != last; ++first)
149 base_type::insert(*first);
152 concurrent_unordered_map(const concurrent_unordered_map& table) : base_type(table)
156 concurrent_unordered_map(const concurrent_unordered_map& table, const Allocator& a)
157 : base_type(table, a)
161 concurrent_unordered_map& operator=(const concurrent_unordered_map& table)
163 base_type::operator=(table);
167 iterator unsafe_erase(const_iterator where)
169 return base_type::unsafe_erase(where);
172 size_type unsafe_erase(const key_type& key)
174 return base_type::unsafe_erase(key);
177 iterator unsafe_erase(const_iterator first, const_iterator last)
179 return base_type::unsafe_erase(first, last);
182 void swap(concurrent_unordered_map& table)
184 base_type::swap(table);
188 hasher hash_function() const
190 return my_hash_compare.my_hash_object;
193 key_equal key_eq() const
195 return my_hash_compare.my_key_compare_object;
198 mapped_type& operator[](const key_type& key)
200 iterator where = find(key);
204 where = insert(std::pair<key_type, mapped_type>(key, mapped_type())).first;
207 return ((*where).second);
210 mapped_type& at(const key_type& key)
212 iterator where = find(key);
216 tbb::internal::throw_exception(tbb::internal::eid_invalid_key);
219 return ((*where).second);
222 const mapped_type& at(const key_type& key) const
224 const_iterator where = find(key);
228 tbb::internal::throw_exception(tbb::internal::eid_invalid_key);
231 return ((*where).second);
235 } // namespace interface5
237 using interface5::concurrent_unordered_map;
241 #endif// __TBB_concurrent_unordered_map_H