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

   1 /*
   2     Copyright 2005-2010 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 "_concurrent_unordered_internal.h"
  36
  37 namespace tbb
  38 {
  39
  40 // Template class for hash compare
  41 template<typename Key>
  42 class tbb_hash
  43 {
  44 public:
  45     tbb_hash() {}
  46
  47     size_t operator()(const Key& key) const
  48     {
  49         return tbb_hasher(key);
  50     }
  51 };
  52
  53 namespace interface5 {
  54
  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
  58 {
  59 protected:
  60     typedef std::pair<const Key, T> value_type;
  61     typedef Key key_type;
  62     typedef Hash_compare hash_compare;
  63     typedef typename Allocator::template rebind<value_type>::other allocator_type;
  64     enum { allow_multimapping = Allow_multimapping };
  65
  66     concurrent_unordered_map_traits() : my_hash_compare() {}
  67     concurrent_unordered_map_traits(const hash_compare& hc) : my_hash_compare(hc) {}
  68
  69     class value_compare : public std::binary_function<value_type, value_type, bool>
  70     {
  71         friend class concurrent_unordered_map_traits<Key, T, Hash_compare, Allocator, Allow_multimapping>;
  72
  73     public:
  74         bool operator()(const value_type& left, const value_type& right) const
  75         {
  76             return (my_hash_compare(left.first, right.first));
  77         }
  78
  79         value_compare(const hash_compare& comparator) : my_hash_compare(comparator) {}
  80
  81     protected:
  82         hash_compare my_hash_compare;    // the comparator predicate for keys
  83     };
  84
  85     template<class Type1, class Type2>
  86     static const Key& get_key(const std::pair<Type1, Type2>& value) {
  87         return (value.first);
  88     }
  89
  90     hash_compare my_hash_compare; // the comparator predicate for keys
  91 };
  92
  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> >
  95 {
  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
 102 public:
 103 #endif
 104     using traits_type::allow_multimapping;
 105 public:
 106     using base_type::end;
 107     using base_type::find;
 108     using base_type::insert;
 109
 110     // Type definitions
 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;
 117
 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;
 123
 124     typedef typename base_type::size_type size_type;
 125     typedef typename base_type::difference_type difference_type;
 126
 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;
 131
 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)
 136     {
 137     }
 138
 139     concurrent_unordered_map(const Allocator& a) : base_type(8, key_compare(), a)
 140     {
 141     }
 142
 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)
 147     {
 148         for (; first != last; ++first)
 149             base_type::insert(*first);
 150     }
 151
 152     concurrent_unordered_map(const concurrent_unordered_map& table) : base_type(table)
 153     {
 154     }
 155
 156     concurrent_unordered_map(const concurrent_unordered_map& table, const Allocator& a)
 157         : base_type(table, a)
 158     {
 159     }
 160
 161     concurrent_unordered_map& operator=(const concurrent_unordered_map& table)
 162     {
 163         base_type::operator=(table);
 164         return (*this);
 165     }
 166
 167     iterator unsafe_erase(const_iterator where)
 168     {
 169         return base_type::unsafe_erase(where);
 170     }
 171
 172     size_type unsafe_erase(const key_type& key)
 173     {
 174         return base_type::unsafe_erase(key);
 175     }
 176
 177     iterator unsafe_erase(const_iterator first, const_iterator last)
 178     {
 179         return base_type::unsafe_erase(first, last);
 180     }
 181
 182     void swap(concurrent_unordered_map& table)
 183     {
 184         base_type::swap(table);
 185     }
 186
 187     // Observers
 188     hasher hash_function() const
 189     {
 190         return my_hash_compare.my_hash_object;
 191     }
 192
 193     key_equal key_eq() const
 194     {
 195         return my_hash_compare.my_key_compare_object;
 196     }
 197
 198     mapped_type& operator[](const key_type& key)
 199     {
 200         iterator where = find(key);
 201
 202         if (where == end())
 203         {
 204             where = insert(std::pair<key_type, mapped_type>(key, mapped_type())).first;
 205         }
 206
 207         return ((*where).second);
 208     }
 209
 210     mapped_type& at(const key_type& key)
 211     {
 212         iterator where = find(key);
 213
 214         if (where == end())
 215         {
 216             tbb::internal::throw_exception(tbb::internal::eid_invalid_key);
 217         }
 218
 219         return ((*where).second);
 220     }
 221
 222     const mapped_type& at(const key_type& key) const
 223     {
 224         const_iterator where = find(key);
 225
 226         if (where == end())
 227         {
 228             tbb::internal::throw_exception(tbb::internal::eid_invalid_key);
 229         }
 230
 231         return ((*where).second);
 232     }
 233 };
 234
 235 } // namespace interface5
 236
 237 using interface5::concurrent_unordered_map;
 238
 239 } // namespace tbb
 240
 241 #endif// __TBB_concurrent_unordered_map_H