X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2FAtomicHashMap.h;h=b4a0563e9f15049f8ac9d03110c55428b2de897f;hb=2dafcc987ed3e65f006a5c5beaa7832d3f3a7ec0;hp=bc95bbd67cca44860f6fdadbf72e83911664c7b7;hpb=367a8b2c6881c572e7f975d6a22a009d997e81ad;p=folly.git diff --git a/folly/AtomicHashMap.h b/folly/AtomicHashMap.h index bc95bbd6..b4a0563e 100644 --- a/folly/AtomicHashMap.h +++ b/folly/AtomicHashMap.h @@ -1,5 +1,5 @@ /* - * Copyright 2012 Facebook, Inc. + * Copyright 2016 Facebook, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -79,7 +79,7 @@ * */ -#ifndef FOLLY_ATOMICHASHMAP_H_ +#pragma once #define FOLLY_ATOMICHASHMAP_H_ #include @@ -90,11 +90,11 @@ #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 { @@ -135,7 +135,9 @@ namespace folly { * make_pair everywhere), and providing both can lead to some gross * template error messages. * - * - Not Allocator-aware. + * - The Allocator must not be stateful (a new instance will be spun up for + * each allocation), and its allocate() method must take a raw number of + * bytes. * * - KeyT must be a 32 bit or 64 bit atomic integer type, and you must * define special 'locked' and 'empty' key values in the ctor @@ -143,10 +145,6 @@ namespace folly { * - We don't take the Hash function object as an instance in the * constructor. * - * - We don't take a Compare template parameter (since our keys must - * be integers, and the underlying hash array here uses atomic - * compare-and-swap instructions, we only allow normal integer - * comparisons). */ // Thrown when insertion fails due to running out of space for @@ -157,16 +155,20 @@ struct AtomicHashMapFullError : std::runtime_error { {} }; -template +template class AtomicHashMap : boost::noncopyable { - typedef AtomicHashArray SubMap; +typedef AtomicHashArray + SubMap; public: typedef KeyT key_type; typedef ValueT mapped_type; typedef std::pair value_type; typedef HashFcn hasher; - typedef std::equal_to key_equal; + typedef EqualFcn key_equal; + typedef KeyConvertFcn key_convert; typedef value_type* pointer; typedef value_type& reference; typedef const value_type& const_reference; @@ -192,8 +194,7 @@ class AtomicHashMap : boost::noncopyable { // The constructor takes a finalSizeEst which is the optimal // number of elements to maximize space utilization and performance, // and a Config object to specify more advanced options. - static const Config defaultConfig; - explicit AtomicHashMap(size_t finalSizeEst, const Config& = defaultConfig); + explicit AtomicHashMap(size_t finalSizeEst, const Config& c = Config()); ~AtomicHashMap() { const int numMaps = numMapsAllocated_.load(std::memory_order_relaxed); @@ -204,11 +205,9 @@ class AtomicHashMap : boost::noncopyable { } } - key_equal key_eq() const { return key_eq(); } + key_equal key_eq() const { return key_equal(); } hasher hash_function() const { return hasher(); } - // TODO: emplace() support would be nice. - /* * insert -- * @@ -225,23 +224,61 @@ class AtomicHashMap : boost::noncopyable { * AtomicHashMapFullError is thrown. */ std::pair 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) { + return emplace(k, std::move(v)); } - std::pair insert(key_type k, mapped_type&& 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 + 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 + iterator find(LookupKeyT k); + + template + const_iterator find(LookupKeyT k) const; /* * erase -- @@ -319,17 +356,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 { @@ -382,19 +423,26 @@ 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 + SimpleRetT insertInternal(LookupKeyT key, ArgTs&&... value); - SimpleRetT findInternal(const KeyT k) const; + template + SimpleRetT findInternal(const LookupKeyT k) const; - SimpleRetT findAtInternal(const uint32_t idx) const; + SimpleRetT findAtInternal(uint32_t idx) const; std::atomic subMaps_[kNumSubMaps_]; std::atomic numMapsAllocated_; @@ -409,8 +457,18 @@ class AtomicHashMap : boost::noncopyable { }; // AtomicHashMap +template , + class EqualFcn = std::equal_to, + class Allocator = std::allocator> +using QuadraticProbingAtomicHashMap = + AtomicHashMap; } // namespace folly -#include "AtomicHashMap-inl.h" - -#endif // FOLLY_ATOMICHASHMAP_H_ +#include