X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2FAtomicHashArray-inl.h;h=95c86df35376690c56769347cc401245ffc6c7dd;hb=4de78cbfccb7d0a42ff52d3476180c7acd292f2a;hp=8982728b8be6f2623b1dbe6dd417a2aad5b522e1;hpb=bc46f015ee17b1c8fb00a546aff8fd0e80b029e4;p=folly.git

diff --git a/folly/AtomicHashArray-inl.h b/folly/AtomicHashArray-inl.h
index 8982728b..95c86df3 100644
--- a/folly/AtomicHashArray-inl.h
+++ b/folly/AtomicHashArray-inl.h
@@ -1,5 +1,5 @@
 /*
- * Copyright 2012 Facebook, Inc.
+ * Copyright 2014 Facebook, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -18,14 +18,15 @@
 #error "This should only be included by AtomicHashArray.h"
 #endif
 
-#include "folly/Bits.h"
-#include "folly/detail/AtomicHashUtils.h"
+#include <folly/Bits.h>
+#include <folly/detail/AtomicHashUtils.h>
 
 namespace folly {
 
 // AtomicHashArray private constructor --
-template <class KeyT, class ValueT, class HashFcn>
-AtomicHashArray<KeyT, ValueT, HashFcn>::
+template <class KeyT, class ValueT,
+          class HashFcn, class EqualFcn, class Allocator>
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 AtomicHashArray(size_t capacity, KeyT emptyKey, KeyT lockedKey,
                 KeyT erasedKey, double maxLoadFactor, size_t cacheSize)
     : capacity_(capacity), maxEntries_(size_t(maxLoadFactor * capacity_ + 0.5)),
@@ -41,9 +42,11 @@ AtomicHashArray(size_t capacity, KeyT emptyKey, KeyT lockedKey,
  *   of key and returns true, or if key does not exist returns false and
  *   ret.index is set to capacity_.
  */
-template <class KeyT, class ValueT, class HashFcn>
-typename AtomicHashArray<KeyT, ValueT, HashFcn>::SimpleRetT
-AtomicHashArray<KeyT, ValueT, HashFcn>::
+template <class KeyT, class ValueT,
+          class HashFcn, class EqualFcn, class Allocator>
+typename AtomicHashArray<KeyT, ValueT,
+         HashFcn, EqualFcn, Allocator>::SimpleRetT
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 findInternal(const KeyT key_in) {
   DCHECK_NE(key_in, kEmptyKey_);
   DCHECK_NE(key_in, kLockedKey_);
@@ -52,7 +55,7 @@ findInternal(const KeyT key_in) {
        ;
        idx = probeNext(idx, numProbes)) {
     const KeyT key = acquireLoadKey(cells_[idx]);
-    if (LIKELY(key == key_in)) {
+    if (LIKELY(EqualFcn()(key, key_in))) {
       return SimpleRetT(idx, true);
     }
     if (UNLIKELY(key == kEmptyKey_)) {
@@ -77,10 +80,12 @@ findInternal(const KeyT key_in) {
  *   this will be the previously inserted value, and if the map is full it is
  *   default.
  */
-template <class KeyT, class ValueT, class HashFcn>
+template <class KeyT, class ValueT,
+          class HashFcn, class EqualFcn, class Allocator>
 template <class T>
-typename AtomicHashArray<KeyT, ValueT, HashFcn>::SimpleRetT
-AtomicHashArray<KeyT, ValueT, HashFcn>::
+typename AtomicHashArray<KeyT, ValueT,
+         HashFcn, EqualFcn, Allocator>::SimpleRetT
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 insertInternal(KeyT key_in, T&& value) {
   const short NO_NEW_INSERTS = 1;
   const short NO_PENDING_INSERTS = 2;
@@ -140,6 +145,8 @@ insertInternal(KeyT key_in, T&& value) {
             --numPendingEntries_;
             throw;
           }
+          // Direct comparison rather than EqualFcn ok here
+          // (we just inserted it)
           DCHECK(relaxedLoadKey(*cell) == key_in);
           --numPendingEntries_;
           ++numEntries_;  // This is a thread cached atomic increment :)
@@ -159,7 +166,7 @@ insertInternal(KeyT key_in, T&& value) {
     }
 
     const KeyT thisKey = acquireLoadKey(*cell);
-    if (thisKey == key_in) {
+    if (EqualFcn()(thisKey, key_in)) {
       // Found an existing entry for our key, but we don't overwrite the
       // previous value.
       return SimpleRetT(idx, false);
@@ -191,8 +198,9 @@ insertInternal(KeyT key_in, T&& value) {
  *   erased key will never be reused. If there's an associated value, we won't
  *   touch it either.
  */
-template <class KeyT, class ValueT, class HashFcn>
-size_t AtomicHashArray<KeyT, ValueT, HashFcn>::
+template <class KeyT, class ValueT,
+          class HashFcn, class EqualFcn, class Allocator>
+size_t AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 erase(KeyT key_in) {
   CHECK_NE(key_in, kEmptyKey_);
   CHECK_NE(key_in, kLockedKey_);
@@ -208,10 +216,10 @@ erase(KeyT key_in) {
       // is similar to how it's handled in find().
       return 0;
     }
-    if (key_in == currentKey) {
+    if (EqualFcn()(currentKey, key_in)) {
       // Found an existing entry for our key, attempt to mark it erased.
       // Some other thread may have erased our key, but this is ok.
-      KeyT expect = key_in;
+      KeyT expect = currentKey;
       if (cellKeyPtr(*cell)->compare_exchange_strong(expect, kErasedKey_)) {
         numErases_.fetch_add(1, std::memory_order_relaxed);
 
@@ -234,13 +242,17 @@ erase(KeyT key_in) {
   }
 }
 
-template <class KeyT, class ValueT, class HashFcn>
-const typename AtomicHashArray<KeyT, ValueT, HashFcn>::Config
-AtomicHashArray<KeyT, ValueT, HashFcn>::defaultConfig;
-
-template <class KeyT, class ValueT, class HashFcn>
-typename AtomicHashArray<KeyT, ValueT, HashFcn>::SmartPtr
-AtomicHashArray<KeyT, ValueT, HashFcn>::
+template <class KeyT, class ValueT,
+          class HashFcn, class EqualFcn, class Allocator>
+const typename AtomicHashArray<KeyT, ValueT,
+      HashFcn, EqualFcn, Allocator>::Config
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::defaultConfig;
+
+template <class KeyT, class ValueT,
+         class HashFcn, class EqualFcn, class Allocator>
+typename AtomicHashArray<KeyT, ValueT,
+         HashFcn, EqualFcn, Allocator>::SmartPtr
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 create(size_t maxSize, const Config& c) {
   CHECK_LE(c.maxLoadFactor, 1.0);
   CHECK_GT(c.maxLoadFactor, 0.0);
@@ -248,10 +260,16 @@ create(size_t maxSize, const Config& c) {
   size_t capacity = size_t(maxSize / c.maxLoadFactor);
   size_t sz = sizeof(AtomicHashArray) + sizeof(value_type) * capacity;
 
-  std::unique_ptr<void, void(*)(void*)> mem(malloc(sz), free);
-  new(mem.get()) AtomicHashArray(capacity, c.emptyKey, c.lockedKey, c.erasedKey,
-                                 c.maxLoadFactor, c.entryCountThreadCacheSize);
-  SmartPtr map(static_cast<AtomicHashArray*>(mem.release()));
+  auto const mem = Allocator().allocate(sz);
+  try {
+    new (mem) AtomicHashArray(capacity, c.emptyKey, c.lockedKey, c.erasedKey,
+                              c.maxLoadFactor, c.entryCountThreadCacheSize);
+  } catch (...) {
+    Allocator().deallocate(mem, sz);
+    throw;
+  }
+
+  SmartPtr map(static_cast<AtomicHashArray*>((void *)mem));
 
   /*
    * Mark all cells as empty.
@@ -272,22 +290,28 @@ create(size_t maxSize, const Config& c) {
   return map;
 }
 
-template <class KeyT, class ValueT, class HashFcn>
-void AtomicHashArray<KeyT, ValueT, HashFcn>::
+template <class KeyT, class ValueT,
+          class HashFcn, class EqualFcn, class Allocator>
+void AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 destroy(AtomicHashArray* p) {
   assert(p);
+
+  size_t sz = sizeof(AtomicHashArray) + sizeof(value_type) * p->capacity_;
+
   FOR_EACH_RANGE(i, 0, p->capacity_) {
     if (p->cells_[i].first != p->kEmptyKey_) {
       p->cells_[i].~value_type();
     }
   }
   p->~AtomicHashArray();
-  free(p);
+
+  Allocator().deallocate((char *)p, sz);
 }
 
 // clear -- clears all keys and values in the map and resets all counters
-template <class KeyT, class ValueT, class HashFcn>
-void AtomicHashArray<KeyT, ValueT, HashFcn>::
+template <class KeyT, class ValueT,
+          class HashFcn, class EqualFcn, class Allocator>
+void AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
 clear() {
   FOR_EACH_RANGE(i, 0, capacity_) {
     if (cells_[i].first != kEmptyKey_) {
@@ -305,9 +329,10 @@ clear() {
 
 // Iterator implementation
 
-template <class KeyT, class ValueT, class HashFcn>
+template <class KeyT, class ValueT,
+          class HashFcn, class EqualFcn, class Allocator>
 template <class ContT, class IterVal>
-struct AtomicHashArray<KeyT, ValueT, HashFcn>::aha_iterator
+struct AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::aha_iterator
     : boost::iterator_facade<aha_iterator<ContT,IterVal>,
                              IterVal,
                              boost::forward_traversal_tag>