OpenImageIO
 All Classes Files Friends Macros Pages
unordered_map_concurrent.h
1 /*
2 Copyright 2012 Larry Gritz and the other authors and contributors.
3 All Rights Reserved.
4 
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions are
7 met:
8 * Redistributions of source code must retain the above copyright
9  notice, this list of conditions and the following disclaimer.
10 * Redistributions in binary form must reproduce the above copyright
11  notice, this list of conditions and the following disclaimer in the
12  documentation and/or other materials provided with the distribution.
13 * Neither the name of the software's owners nor the names of its
14  contributors may be used to endorse or promote products derived from
15  this software without specific prior written permission.
16 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 
28 (This is the Modified BSD License)
29 */
30 
31 
32 #pragma once
33 
34 #ifndef OPENIMAGEIO_UNORDERED_MAP_CONCURRENT_H
35 #define OPENIMAGEIO_UNORDERED_MAP_CONCURRENT_H
36 
37 #include <boost/unordered_map.hpp>
38 #include "sysutil.h" // from OIIO
39 #include "thread.h" // from OIIO
40 #include "hash.h" // from OIIO
41 #include "dassert.h" // from OIIO
42 
43 OIIO_NAMESPACE_ENTER
44 {
45 
46 
78 
79 template<class KEY, class VALUE, class HASH=boost::hash<KEY>,
80  class PRED=std::equal_to<KEY>, size_t BINS=16>
81 class unordered_map_concurrent {
82 public:
83  typedef boost::unordered_map<KEY,VALUE,HASH,PRED> BinMap_t;
84  typedef typename boost::unordered_map<KEY,VALUE,HASH,PRED>::iterator BinMap_iterator_t;
85 
86 public:
87  unordered_map_concurrent () { m_size = 0; }
88 
89  ~unordered_map_concurrent () {
90 // for (size_t i = 0; i < BINS; ++i)
91 // std::cout << "Bin " << i << ": " << m_bins[i].map.size() << "\n";
92  }
93 
96  class iterator {
97  public:
98  friend class unordered_map_concurrent<KEY,VALUE,HASH,PRED,BINS>;
99  public:
102  iterator (unordered_map_concurrent *umc = NULL)
103  : m_umc(umc), m_bin(-1), m_locked(false) { }
104 
108  iterator (const iterator &src) {
109  m_umc = src.m_umc;
110  m_bin = src.m_bin;
111  m_biniterator = src.m_biniterator;
112  m_locked = src.m_locked;
113  // assignment transfers lock ownership
114  *(const_cast<bool *>(&src.m_locked)) = false;
115  }
116 
119  ~iterator () { clear(); }
120 
123  void clear () {
124  if (m_umc) {
125  unbin ();
126  m_umc = NULL;
127  }
128  }
129 
130  // Dereferencing returns a reference to the hash table entry the
131  // iterator refers to.
132  typename BinMap_t::value_type & operator* () {
133  return *m_biniterator;
134  }
135 
138  typename BinMap_t::value_type * operator-> () {
139  return &(*m_biniterator);
140  }
141 
145  operator bool() {
146  return m_umc && m_bin >= 0 &&
147  m_biniterator != m_umc->m_bins[m_bin].map.end();
148  }
149 
152  iterator& operator= (const iterator &src) {
153  unbin();
154  m_umc = src.m_umc;
155  m_bin = src.m_bin;
156  m_biniterator = src.m_biniterator;
157  m_locked = src.m_locked;
158  // assignment transfers lock ownership
159  *(const_cast<bool *>(&src.m_locked)) = false;
160  return *this;
161  }
162 
163  bool operator== (const iterator &other) const {
164  if (m_umc != other.m_umc)
165  return false;
166  if (m_bin == -1 && other.m_bin == -1)
167  return true;
168  return m_bin == other.m_bin &&
169  m_biniterator == other.m_biniterator;
170  }
171  bool operator!= (const iterator &other) {
172  return ! (*this == other);
173  }
174 
179  void operator++ () {
180  DASSERT (m_umc);
181  DASSERT (m_bin >= 0);
182  ++m_biniterator;
183  while (m_biniterator == m_umc->m_bins[m_bin].map.end()) {
184  if (m_bin == BINS-1) {
185  // ran off the end
186  unbin();
187  return;
188  }
189  rebin (m_bin+1);
190  }
191  }
192  void operator++ (int) { ++(*this); }
193 
195  void lock () {
196  if (m_bin >= 0 && !m_locked) {
197  m_umc->m_bins[m_bin].lock();
198  m_locked = true;
199  }
200  }
202  void unlock () {
203  if (m_bin >= 0 && m_locked) {
204  m_umc->m_bins[m_bin].unlock();
205  m_locked = false;
206  }
207  }
208 
214  bool incr_no_lock () {
215  ++m_biniterator;
216  return (m_biniterator != m_umc->m_bins[m_bin].map.end());
217  }
218 
219  private:
220  // No longer refer to a particular bin, release lock on the bin
221  // it had (if any).
222  void unbin () {
223  if (m_bin >= 0) {
224  if (m_locked)
225  unlock ();
226  m_bin = -1;
227  }
228  }
229 
230  // Point this iterator to a different bin, releasing locks on
231  // the bin it previously referred to.
232  void rebin (int newbin) {
233  DASSERT (m_umc);
234  unbin ();
235  m_bin = newbin;
236  lock ();
237  m_biniterator = m_umc->m_bins[m_bin].map.begin();
238  }
239 
240  unordered_map_concurrent *m_umc; // which umc this iterator refers to
241  int m_bin; // which bin within the umc
242  BinMap_iterator_t m_biniterator; // which entry within the bin
243  bool m_locked; // do we own the lock on the bin?
244  };
245 
246 
248  iterator begin () {
249  iterator i (this);
250  i.rebin (0);
251  while (i.m_biniterator == m_bins[i.m_bin].map.end()) {
252  if (i.m_bin == BINS-1) {
253  // ran off the end
254  i.unbin();
255  return i;
256  }
257  i.rebin (i.m_bin+1);
258  }
259  return i;
260  }
261 
264  iterator end () {
265  iterator i (this);
266  return i;
267  }
268 
277  iterator find (const KEY &key, bool do_lock = true) {
278  size_t b = whichbin(key);
279  Bin &bin (m_bins[b]);
280  if (do_lock)
281  bin.lock ();
282  typename BinMap_t::iterator it = bin.map.find (key);
283  if (it == bin.map.end()) {
284  // not found -- return the 'end' iterator
285  if (do_lock)
286  bin.unlock();
287  return end();
288  }
289  // Found
290  iterator i (this);
291  i.m_bin = (unsigned) b;
292  i.m_biniterator = it;
293  i.m_locked = do_lock;
294  return i;
295  }
296 
302  bool insert (const KEY &key, const VALUE &value,
303  bool do_lock = true) {
304  size_t b = whichbin(key);
305  Bin &bin (m_bins[b]);
306  if (do_lock)
307  bin.lock ();
308  bool add = (bin.map.find (key) == bin.map.end());
309  if (add) {
310  // not found -- add it!
311  bin.map[key] = value;
312  ++m_size;
313  }
314  if (do_lock)
315  bin.unlock();
316  return add;
317  }
318 
323  void erase (const KEY &key, bool do_lock = true) {
324  size_t b = whichbin(key);
325  Bin &bin (m_bins[b]);
326  if (do_lock)
327  bin.lock ();
328  typename BinMap_t::iterator it = bin.map.find (key);
329  if (it != bin.map.end()) {
330  bin.map.erase (it);
331  }
332  if (do_lock)
333  bin.unlock();
334  }
335 
337  bool empty() { return m_size == 0; }
338 
342  size_t lock_bin (const KEY &key) {
343  size_t b = whichbin(key);
344  m_bins[b].lock ();
345  return b;
346  }
347 
350  void unlock_bin (size_t bin) {
351  m_bins[bin].unlock ();
352  }
353 
354 private:
355  struct Bin {
356  // OIIO_CACHE_ALIGN // align to cache line -- doesn't seem to help
357  mutable spin_mutex mutex; // mutex for this bin
358  BinMap_t map; // hash map for this bin
359 #ifndef NDEBUG
360  mutable atomic_int m_nlocks; // for debugging
361 #endif
362 
363  Bin () {
364 #ifndef NDEBUG
365  m_nlocks = 0;
366 #endif
367  }
368  ~Bin () {
369 #ifndef NDEBUG
370  DASSERT (m_nlocks == 0);
371 #endif
372  }
373  void lock () const {
374  mutex.lock();
375 #ifndef NDEBUG
376  ++m_nlocks;
377  DASSERT_MSG (m_nlocks == 1, "oops, m_nlocks = %d", (int)m_nlocks);
378 #endif
379  }
380  void unlock () const {
381 #ifndef NDEBUG
382  DASSERT_MSG (m_nlocks == 1, "oops, m_nlocks = %d", (int)m_nlocks);
383  --m_nlocks;
384 #endif
385  mutex.unlock();
386  }
387  };
388 
389  HASH m_hash; // hashing function
390  atomic_int m_size; // total entries in all bins
391  Bin m_bins[BINS]; // the bins
392 
393  // Which bin will this key always appear in?
394  size_t whichbin (const KEY &key) {
395  size_t h = m_hash(key);
396  h = (size_t) murmur::fmix (uint64_t(h)); // scramble again
397  return h % BINS;
398  }
399 
400 };
401 
402 
403 }
404 OIIO_NAMESPACE_EXIT
405 
406 #endif // OPENIMAGEIO_UNORDERED_MAP_CONCURRENT_H