X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2FAtomicHashArray.h;h=654077b1945759d30a9aa08711c2027cf3d7df90;hb=42ed17d93e734b5c54869146c4de9fc9244fa18e;hp=33c59247e38e5bc7e3a80b6b3499a7cbc08a0641;hpb=4e5cb0efba9454e3abb2dd203116ed8e9a056468;p=folly.git diff --git a/folly/AtomicHashArray.h b/folly/AtomicHashArray.h index 33c59247..654077b1 100644 --- a/folly/AtomicHashArray.h +++ b/folly/AtomicHashArray.h @@ -1,5 +1,5 @@ /* - * Copyright 2015 Facebook, Inc. + * Copyright 2017 Facebook, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -16,8 +16,8 @@ /** * AtomicHashArray is the building block for AtomicHashMap. It provides the - * core lock-free functionality, but is limitted by the fact that it cannot - * grow past it's initialization size and is a little more awkward (no public + * core lock-free functionality, but is limited by the fact that it cannot + * grow past its initialization size and is a little more awkward (no public * constructor, for example). If you're confident that you won't run out of * space, don't mind the awkardness, and really need bare-metal performance, * feel free to use AHA directly. @@ -29,7 +29,7 @@ * @author Jordan DeLong */ -#ifndef FOLLY_ATOMICHASHARRAY_H_ +#pragma once #define FOLLY_ATOMICHASHARRAY_H_ #include @@ -37,14 +37,17 @@ #include #include -#include #include +#include +#include namespace folly { struct AtomicHashArrayLinearProbeFcn { - inline size_t operator()(size_t idx, size_t numProbes, size_t capacity) const{ + inline size_t operator()(size_t idx, + size_t /* numProbes */, + size_t capacity) const { idx += 1; // linear probing // Avoid modulus because it's slow @@ -64,20 +67,11 @@ struct AtomicHashArrayQuadraticProbeFcn // Enables specializing checkLegalKey without specializing its class. namespace detail { -// Local copy of folly::gen::Identity, to avoid heavy dependencies. -class AHAIdentity { - public: - template - auto operator()(Value&& value) const -> - decltype(std::forward(value)) { - return std::forward(value); - } -}; - template -inline void checkLegalKeyIfKeyTImpl(NotKeyT ignored, KeyT emptyKey, - KeyT lockedKey, KeyT erasedKey) { -} +inline void checkLegalKeyIfKeyTImpl(NotKeyT /* ignored */, + KeyT /* emptyKey */, + KeyT /* lockedKey */, + KeyT /* erasedKey */) {} template inline void checkLegalKeyIfKeyTImpl(KeyT key_in, KeyT emptyKey, @@ -86,22 +80,26 @@ inline void checkLegalKeyIfKeyTImpl(KeyT key_in, KeyT emptyKey, DCHECK_NE(key_in, lockedKey); DCHECK_NE(key_in, erasedKey); } -} // namespace detail - -template , - class EqualFcn = std::equal_to, - class Allocator = std::allocator, - class ProbeFcn = AtomicHashArrayLinearProbeFcn, - class KeyConvertFcn = detail::AHAIdentity> +} // namespace detail + +template < + class KeyT, + class ValueT, + class HashFcn = std::hash, + class EqualFcn = std::equal_to, + class Allocator = std::allocator, + class ProbeFcn = AtomicHashArrayLinearProbeFcn, + class KeyConvertFcn = Identity> class AtomicHashMap; -template , - class EqualFcn = std::equal_to, - class Allocator = std::allocator, - class ProbeFcn = AtomicHashArrayLinearProbeFcn, - class KeyConvertFcn = detail::AHAIdentity> +template < + class KeyT, + class ValueT, + class HashFcn = std::hash, + class EqualFcn = std::equal_to, + class Allocator = std::allocator, + class ProbeFcn = AtomicHashArrayLinearProbeFcn, + class KeyConvertFcn = Identity> class AtomicHashArray : boost::noncopyable { static_assert((std::is_convertible::value || std::is_convertible::value || @@ -129,7 +127,7 @@ class AtomicHashArray : boost::noncopyable { const KeyT kLockedKey_; const KeyT kErasedKey_; - template + template struct aha_iterator; typedef aha_iterator const_iterator; @@ -173,15 +171,14 @@ class AtomicHashArray : boost::noncopyable { * deleter to make sure everything is cleaned up properly. */ struct Config { - KeyT emptyKey; - KeyT lockedKey; - KeyT erasedKey; + KeyT emptyKey; + KeyT lockedKey; + KeyT erasedKey; double maxLoadFactor; double growthFactor; - int entryCountThreadCacheSize; + uint32_t entryCountThreadCacheSize; size_t capacity; // if positive, overrides maxLoadFactor - public: // Cannot have constexpr ctor because some compilers rightly complain. Config() : emptyKey((KeyT)-1), lockedKey((KeyT)-2), @@ -212,17 +209,19 @@ class AtomicHashArray : boost::noncopyable { * * See folly/test/ArrayHashArrayTest.cpp for sample usage. */ - template + template < + typename LookupKeyT = key_type, + typename LookupHashFcn = hasher, + typename LookupEqualFcn = key_equal> iterator find(LookupKeyT k) { return iterator(this, findInternal(k).idx); } - template + template < + typename LookupKeyT = key_type, + typename LookupHashFcn = hasher, + typename LookupEqualFcn = key_equal> const_iterator find(LookupKeyT k) const { return const_cast(this)-> find(k); @@ -257,11 +256,12 @@ class AtomicHashArray : boost::noncopyable { * equal key is already present, this method converts 'key_in' to a key of * type KeyT using the provided LookupKeyToKeyFcn. */ - template + template < + typename LookupKeyT = key_type, + typename LookupHashFcn = hasher, + typename LookupEqualFcn = key_equal, + typename LookupKeyToKeyFcn = key_convert, + typename... ArgTs> std::pair emplace(LookupKeyT key_in, ArgTs&&... vCtorArgs) { SimpleRetT ret = insertInternal + template < + typename LookupKeyT = key_type, + typename LookupHashFcn = hasher, + typename LookupEqualFcn = key_equal, + typename LookupKeyToKeyFcn = Identity, + typename... ArgTs> SimpleRetT insertInternal(LookupKeyT key, ArgTs&&... vCtorArgs); - template + template < + typename LookupKeyT = key_type, + typename LookupHashFcn = hasher, + typename LookupEqualFcn = key_equal> SimpleRetT findInternal(const LookupKeyT key); template @@ -398,8 +398,13 @@ friend class AtomicHashMap - -#endif // FOLLY_ATOMICHASHARRAY_H_