X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2FAtomicHashMap.h;h=b4a0563e9f15049f8ac9d03110c55428b2de897f;hb=a56309f581c1ddfc803b9f4e163b56fd1d749957;hp=bac9b4b9243fd6936019af242257b22d36468e58;hpb=2129f9b5e34ae3a958e50f9fcb3032086366abb8;p=folly.git diff --git a/folly/AtomicHashMap.h b/folly/AtomicHashMap.h index bac9b4b9..b4a0563e 100644 --- a/folly/AtomicHashMap.h +++ b/folly/AtomicHashMap.h @@ -1,5 +1,5 @@ /* - * Copyright 2013 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 { @@ -155,10 +155,12 @@ struct AtomicHashMapFullError : std::runtime_error { {} }; -template +template class AtomicHashMap : boost::noncopyable { - typedef AtomicHashArray SubMap; +typedef AtomicHashArray + SubMap; public: typedef KeyT key_type; @@ -166,6 +168,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; @@ -191,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); @@ -206,8 +208,6 @@ class AtomicHashMap : boost::noncopyable { key_equal key_eq() const { return key_equal(); } hasher hash_function() const { return hasher(); } - // TODO: emplace() support would be nice. - /* * insert -- * @@ -224,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 -- @@ -318,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 { @@ -381,17 +423,24 @@ 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(uint32_t idx) const; @@ -408,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