X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2FAtomicHashMap.h;h=2243b6bef7415e07355987e0ecd383c9cc7c6ade;hb=d0956208d06806377b05e4daef5450603ce4ad63;hp=c6f06bd8f27016d0dcf5e371e94ece91af2508cd;hpb=99de4c5fde6fce17ac9dab77b2b99ceffce999dc;p=folly.git diff --git a/folly/AtomicHashMap.h b/folly/AtomicHashMap.h index c6f06bd8..2243b6be 100644 --- a/folly/AtomicHashMap.h +++ b/folly/AtomicHashMap.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. @@ -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 -#include -#include #include #include +#include +#include namespace folly { @@ -155,10 +155,17 @@ 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 +typedef AtomicHashArray SubMap; public: @@ -167,6 +174,7 @@ typedef AtomicHashArray 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; @@ -174,7 +182,7 @@ typedef AtomicHashArray typedef std::size_t size_type; typedef typename SubMap::Config Config; - template + template struct ahm_iterator; typedef ahm_iterator explicit AtomicHashMap(size_t finalSizeEst, const Config& c = Config()); ~AtomicHashMap() { - const int numMaps = numMapsAllocated_.load(std::memory_order_relaxed); + const unsigned int numMaps = + numMapsAllocated_.load(std::memory_order_relaxed); FOR_EACH_RANGE (i, 0, numMaps) { SubMap* thisMap = subMaps_[i].load(std::memory_order_relaxed); DCHECK(thisMap); @@ -239,19 +248,47 @@ typedef AtomicHashArray * * 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(key_type k, ArgTs&&... vCtorArg); + 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). * - * If the key is not found, returns end(). + * 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. + * + * 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 -- @@ -403,17 +440,26 @@ typedef AtomicHashArray SimpleRetT() = default; }; - template - SimpleRetT insertInternal(KeyT key, ArgTs&&... 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); @@ -423,11 +469,12 @@ typedef AtomicHashArray }; // AtomicHashMap -template , - class EqualFcn = std::equal_to, - class Allocator = std::allocator> +template < + class KeyT, + class ValueT, + class HashFcn = std::hash, + class EqualFcn = std::equal_to, + class Allocator = std::allocator> using QuadraticProbingAtomicHashMap = AtomicHashMap - -#endif // FOLLY_ATOMICHASHMAP_H_