git.sesse.net Git - casparcg/blob - tbb/include/tbb/concurrent_unordered_map.h

   1 /*
   2     Copyright 2005-2011 Intel Corporation.  All Rights Reserved.
   3
   4     This file is part of Threading Building Blocks.
   5
   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.
   9
  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.
  14
  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
  18
  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.
  27 */
  28
  29 /* Container implementations in this header are based on PPL implementations
  30    provided by Microsoft. */
  31
  32 #ifndef __TBB_concurrent_unordered_map_H
  33 #define __TBB_concurrent_unordered_map_H
  34
  35 #include "internal/_concurrent_unordered_impl.h"
  36
  37 namespace tbb
  38 {
  39
  40 namespace interface5 {
  41
  42 // Template class for hash map traits
  43 template<typename Key, typename T, typename Hash_compare, typename Allocator, bool Allow_multimapping>
  44 class concurrent_unordered_map_traits
  45 {
  46 protected:
  47     typedef std::pair<const Key, T> value_type;
  48     typedef Key key_type;
  49     typedef Hash_compare hash_compare;
  50     typedef typename Allocator::template rebind<value_type>::other allocator_type;
  51     enum { allow_multimapping = Allow_multimapping };
  52
  53     concurrent_unordered_map_traits() : my_hash_compare() {}
  54     concurrent_unordered_map_traits(const hash_compare& hc) : my_hash_compare(hc) {}
  55
  56     class value_compare : public std::binary_function<value_type, value_type, bool>
  57     {
  58         friend class concurrent_unordered_map_traits<Key, T, Hash_compare, Allocator, Allow_multimapping>;
  59
  60     public:
  61         bool operator()(const value_type& left, const value_type& right) const
  62         {
  63             return (my_hash_compare(left.first, right.first));
  64         }
  65
  66         value_compare(const hash_compare& comparator) : my_hash_compare(comparator) {}
  67
  68     protected:
  69         hash_compare my_hash_compare;    // the comparator predicate for keys
  70     };
  71
  72     template<class Type1, class Type2>
  73     static const Key& get_key(const std::pair<Type1, Type2>& value) {
  74         return (value.first);
  75     }
  76
  77     hash_compare my_hash_compare; // the comparator predicate for keys
  78 };
  79
  80 template <typename Key, typename T, typename Hasher = tbb::tbb_hash<Key>, typename Key_equality = std::equal_to<Key>, typename Allocator = tbb::tbb_allocator<std::pair<const Key, T> > >
  81 class concurrent_unordered_map : public internal::concurrent_unordered_base< concurrent_unordered_map_traits<Key, T, internal::hash_compare<Key, Hasher, Key_equality>, Allocator, false> >
  82 {
  83     // Base type definitions
  84     typedef internal::hash_compare<Key, Hasher, Key_equality> hash_compare;
  85     typedef internal::concurrent_unordered_base< concurrent_unordered_map_traits<Key, T, hash_compare, Allocator, false> > base_type;
  86     typedef concurrent_unordered_map_traits<Key, T, internal::hash_compare<Key, Hasher, Key_equality>, Allocator, false> traits_type;
  87     using traits_type::my_hash_compare;
  88 #if __TBB_EXTRA_DEBUG
  89 public:
  90 #endif
  91     using traits_type::allow_multimapping;
  92 public:
  93     using base_type::end;
  94     using base_type::find;
  95     using base_type::insert;
  96
  97     // Type definitions
  98     typedef Key key_type;
  99     typedef typename base_type::value_type value_type;
 100     typedef T mapped_type;
 101     typedef Hasher hasher;
 102     typedef Key_equality key_equal;
 103     typedef hash_compare key_compare;
 104
 105     typedef typename base_type::allocator_type allocator_type;
 106     typedef typename base_type::pointer pointer;
 107     typedef typename base_type::const_pointer const_pointer;
 108     typedef typename base_type::reference reference;
 109     typedef typename base_type::const_reference const_reference;
 110
 111     typedef typename base_type::size_type size_type;
 112     typedef typename base_type::difference_type difference_type;
 113
 114     typedef typename base_type::iterator iterator;
 115     typedef typename base_type::const_iterator const_iterator;
 116     typedef typename base_type::iterator local_iterator;
 117     typedef typename base_type::const_iterator const_local_iterator;
 118
 119     // Construction/destruction/copying
 120     explicit concurrent_unordered_map(size_type n_of_buckets = 8, const hasher& a_hasher = hasher(),
 121         const key_equal& a_keyeq = key_equal(), const allocator_type& a = allocator_type())
 122         : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
 123     {
 124     }
 125
 126     concurrent_unordered_map(const Allocator& a) : base_type(8, key_compare(), a)
 127     {
 128     }
 129
 130     template <typename Iterator>
 131     concurrent_unordered_map(Iterator first, Iterator last, size_type n_of_buckets = 8, const hasher& a_hasher = hasher(),
 132         const key_equal& a_keyeq = key_equal(), const allocator_type& a = allocator_type())
 133         : base_type(n_of_buckets, key_compare(a_hasher, a_keyeq), a)
 134     {
 135         for (; first != last; ++first)
 136             base_type::insert(*first);
 137     }
 138
 139     concurrent_unordered_map(const concurrent_unordered_map& table) : base_type(table)
 140     {
 141     }
 142
 143     concurrent_unordered_map(const concurrent_unordered_map& table, const Allocator& a)
 144         : base_type(table, a)
 145     {
 146     }
 147
 148     concurrent_unordered_map& operator=(const concurrent_unordered_map& table)
 149     {
 150         base_type::operator=(table);
 151         return (*this);
 152     }
 153
 154     iterator unsafe_erase(const_iterator where)
 155     {
 156         return base_type::unsafe_erase(where);
 157     }
 158
 159     size_type unsafe_erase(const key_type& key)
 160     {
 161         return base_type::unsafe_erase(key);
 162     }
 163
 164     iterator unsafe_erase(const_iterator first, const_iterator last)
 165     {
 166         return base_type::unsafe_erase(first, last);
 167     }
 168
 169     void swap(concurrent_unordered_map& table)
 170     {
 171         base_type::swap(table);
 172     }
 173
 174     // Observers
 175     hasher hash_function() const
 176     {
 177         return my_hash_compare.my_hash_object;
 178     }
 179
 180     key_equal key_eq() const
 181     {
 182         return my_hash_compare.my_key_compare_object;
 183     }
 184
 185     mapped_type& operator[](const key_type& key)
 186     {
 187         iterator where = find(key);
 188
 189         if (where == end())
 190         {
 191             where = insert(std::pair<key_type, mapped_type>(key, mapped_type())).first;
 192         }
 193
 194         return ((*where).second);
 195     }
 196
 197     mapped_type& at(const key_type& key)
 198     {
 199         iterator where = find(key);
 200
 201         if (where == end())
 202         {
 203             tbb::internal::throw_exception(tbb::internal::eid_invalid_key);
 204         }
 205
 206         return ((*where).second);
 207     }
 208
 209     const mapped_type& at(const key_type& key) const
 210     {
 211         const_iterator where = find(key);
 212
 213         if (where == end())
 214         {
 215             tbb::internal::throw_exception(tbb::internal::eid_invalid_key);
 216         }
 217
 218         return ((*where).second);
 219     }
 220 };
 221
 222 } // namespace interface5
 223
 224 using interface5::concurrent_unordered_map;
 225
 226 } // namespace tbb
 227
 228 #endif// __TBB_concurrent_unordered_map_H