X-Git-Url: http://plrg.eecs.uci.edu/git/?p=folly.git;a=blobdiff_plain;f=folly%2FAtomicHashMap.h;h=2243b6bef7415e07355987e0ecd383c9cc7c6ade;hp=33ab11c9f0249ccf20488af9d7cc2d3ef636390e;hb=39018ad5c77c53156cb7cd672c05a19fb75a6af7;hpb=22afce906d7e98d95f8c45c3301072d9fd891d41 diff --git a/folly/AtomicHashMap.h b/folly/AtomicHashMap.h index 33ab11c9..2243b6be 100644 --- a/folly/AtomicHashMap.h +++ b/folly/AtomicHashMap.h @@ -1,5 +1,5 @@ /* - * Copyright 2014 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. @@ -17,7 +17,7 @@ /* * AtomicHashMap -- * - * A high performance concurrent hash map with int32 or int64 keys. Supports + * A high-performance concurrent hash map with int32 or int64 keys. Supports * insert, find(key), findAt(index), erase(key), size, and more. Memory cannot * be freed or reclaimed by erase. Can grow to a maximum of about 18 times the * initial capacity, but performance degrades linearly with growth. Can also be @@ -25,7 +25,7 @@ * internal storage (retrieved with iterator::getIndex()). * * Advantages: - * - High performance (~2-4x tbb::concurrent_hash_map in heavily + * - High-performance (~2-4x tbb::concurrent_hash_map in heavily * multi-threaded environments). * - Efficient memory usage if initial capacity is not over estimated * (especially for small keys and values). @@ -56,7 +56,7 @@ * faster because of reduced data indirection. * * AHMap is a wrapper around AHArray sub-maps that allows growth and provides - * an interface closer to the stl UnorderedAssociativeContainer concept. These + * an interface closer to the STL UnorderedAssociativeContainer concept. These * sub-maps are allocated on the fly and are processed in series, so the more * there are (from growing past initial capacity), the worse the performance. * @@ -79,22 +79,22 @@ * */ -#ifndef FOLLY_ATOMICHASHMAP_H_ +#pragma once #define FOLLY_ATOMICHASHMAP_H_ #include #include #include -#include -#include #include +#include +#include -#include "folly/AtomicHashArray.h" -#include "folly/Foreach.h" -#include "folly/Hash.h" -#include "folly/Likely.h" -#include "folly/ThreadCachedInt.h" +#include +#include +#include +#include +#include namespace folly { @@ -155,10 +155,18 @@ struct AtomicHashMapFullError : std::runtime_error { {} }; -template +template < + class KeyT, + class ValueT, + class HashFcn, + class EqualFcn, + class Allocator, + class ProbeFcn, + class KeyConvertFcn> class AtomicHashMap : boost::noncopyable { - typedef AtomicHashArray SubMap; +typedef AtomicHashArray + SubMap; public: typedef KeyT key_type; @@ -166,6 +174,7 @@ class AtomicHashMap : boost::noncopyable { typedef std::pair value_type; typedef HashFcn hasher; typedef EqualFcn key_equal; + typedef KeyConvertFcn key_convert; typedef value_type* pointer; typedef value_type& reference; typedef const value_type& const_reference; @@ -173,7 +182,7 @@ class AtomicHashMap : boost::noncopyable { typedef std::size_t size_type; typedef typename SubMap::Config Config; - template + template struct ahm_iterator; typedef ahm_iterator insert(const value_type& r) { - return insert(r.first, r.second); + return emplace(r.first, r.second); + } + std::pair insert(key_type k, const mapped_type& v) { + return emplace(k, v); } - std::pair insert(key_type k, const mapped_type& v); std::pair insert(value_type&& r) { - return insert(r.first, std::move(r.second)); + return emplace(r.first, std::move(r.second)); } - std::pair insert(key_type k, mapped_type&& v); + std::pair insert(key_type k, mapped_type&& v) { + return emplace(k, std::move(v)); + } + + /* + * emplace -- + * + * Same contract as insert(), but performs in-place construction + * of the value type using the specified arguments. + * + * Also, like find(), this method optionally allows 'key_in' to have a type + * different from that stored in the table; see find(). If and only if no + * equal key is already present, this method converts 'key_in' to a key of + * type KeyT using the provided LookupKeyToKeyFcn. + */ + template < + typename LookupKeyT = key_type, + typename LookupHashFcn = hasher, + typename LookupEqualFcn = key_equal, + typename LookupKeyToKeyFcn = key_convert, + typename... ArgTs> + std::pair emplace(LookupKeyT k, ArgTs&&... vCtorArg); /* * find -- * - * Returns an iterator into the map. + * Returns the iterator to the element if found, otherwise end(). + * + * As an optional feature, the type of the key to look up (LookupKeyT) is + * allowed to be different from the type of keys actually stored (KeyT). + * + * This enables use cases where materializing the key is costly and usually + * redudant, e.g., canonicalizing/interning a set of strings and being able + * to look up by StringPiece. To use this feature, LookupHashFcn must take + * a LookupKeyT, and LookupEqualFcn must take KeyT and LookupKeyT as first + * and second parameter, respectively. * - * If the key is not found, returns end(). + * See folly/test/ArrayHashMapTest.cpp for sample usage. */ - iterator find(key_type k); - const_iterator find(key_type k) const; + template < + typename LookupKeyT = key_type, + typename LookupHashFcn = hasher, + typename LookupEqualFcn = key_equal> + iterator find(LookupKeyT k); + + template < + typename LookupKeyT = key_type, + typename LookupHashFcn = hasher, + typename LookupEqualFcn = key_equal> + const_iterator find(LookupKeyT k) const; /* * erase -- @@ -318,17 +366,21 @@ class AtomicHashMap : boost::noncopyable { } iterator begin() { - return iterator(this, 0, + iterator it(this, 0, subMaps_[0].load(std::memory_order_relaxed)->begin()); - } - - iterator end() { - return iterator(); + it.checkAdvanceToNextSubmap(); + return it; } const_iterator begin() const { - return const_iterator(this, 0, + const_iterator it(this, 0, subMaps_[0].load(std::memory_order_relaxed)->begin()); + it.checkAdvanceToNextSubmap(); + return it; + } + + iterator end() { + return iterator(); } const_iterator end() const { @@ -381,24 +433,33 @@ class AtomicHashMap : boost::noncopyable { static const uint32_t kSubMapIndexShift_ = 32 - kNumSubMapBits_ - 1; static const uint32_t kSubMapIndexMask_ = (1 << kSubMapIndexShift_) - 1; static const uint32_t kNumSubMaps_ = 1 << kNumSubMapBits_; - static const uintptr_t kLockedPtr_ = 0x88ul << 48; // invalid pointer + static const uintptr_t kLockedPtr_ = 0x88ULL << 48; // invalid pointer struct SimpleRetT { uint32_t i; size_t j; bool success; SimpleRetT(uint32_t ii, size_t jj, bool s) : i(ii), j(jj), success(s) {} - SimpleRetT() {} + SimpleRetT() = default; }; - template - SimpleRetT insertInternal(KeyT key, T&& value); + template < + typename LookupKeyT = key_type, + typename LookupHashFcn = hasher, + typename LookupEqualFcn = key_equal, + typename LookupKeyToKeyFcn = key_convert, + typename... ArgTs> + SimpleRetT insertInternal(LookupKeyT key, ArgTs&&... value); - SimpleRetT findInternal(const KeyT k) const; + template < + typename LookupKeyT = key_type, + typename LookupHashFcn = hasher, + typename LookupEqualFcn = key_equal> + SimpleRetT findInternal(const LookupKeyT k) const; SimpleRetT findAtInternal(uint32_t idx) const; std::atomic subMaps_[kNumSubMaps_]; std::atomic numMapsAllocated_; - inline bool tryLockMap(int idx) { + inline bool tryLockMap(unsigned int idx) { SubMap* val = nullptr; return subMaps_[idx].compare_exchange_strong(val, (SubMap*)kLockedPtr_, std::memory_order_acquire); @@ -408,8 +469,19 @@ class AtomicHashMap : boost::noncopyable { }; // AtomicHashMap +template < + class KeyT, + class ValueT, + class HashFcn = std::hash, + class EqualFcn = std::equal_to, + class Allocator = std::allocator> +using QuadraticProbingAtomicHashMap = + AtomicHashMap; } // namespace folly -#include "AtomicHashMap-inl.h" - -#endif // FOLLY_ATOMICHASHMAP_H_ +#include