From 1474b1094e2fe882d0c4b3f792ce5a0f7408b871 Mon Sep 17 00:00:00 2001 From: Andrei Alexandrescu Date: Wed, 4 Feb 2015 13:09:20 -0800 Subject: [PATCH] Add StringKeyed(Unordered){Set,Map} to folly Summary: We're using StringKeyed* from common/datastruct to avoid unnecessary string creation whenever we're looking up string keys. C++14 does offer a solution, see e.g. http://stackoverflow.com/questions/10536788/avoiding-key-construction-for-stdmapfind. That is not supported by current compilers. Test Plan: unittests Reviewed By: pavlo@fb.com Subscribers: trunkagent, net-systems@, folly-diffs@, yfeldblum FB internal diff: D1825700 Signature: t1:1825700:1423086724:530550c3c80e33c80900f31c0ade05c66b22cbe8 --- folly/experimental/StringKeyedCommon.h | 44 ++ folly/experimental/StringKeyedMap.h | 205 +++++++ folly/experimental/StringKeyedSet.h | 189 +++++++ folly/experimental/StringKeyedUnorderedMap.h | 232 ++++++++ folly/experimental/StringKeyedUnorderedSet.h | 225 ++++++++ .../test/StringKeyedBenchmark.cpp | 144 +++++ folly/experimental/test/StringKeyedTest.cpp | 528 ++++++++++++++++++ 7 files changed, 1567 insertions(+) create mode 100644 folly/experimental/StringKeyedCommon.h create mode 100644 folly/experimental/StringKeyedMap.h create mode 100644 folly/experimental/StringKeyedSet.h create mode 100644 folly/experimental/StringKeyedUnorderedMap.h create mode 100644 folly/experimental/StringKeyedUnorderedSet.h create mode 100644 folly/experimental/test/StringKeyedBenchmark.cpp create mode 100644 folly/experimental/test/StringKeyedTest.cpp diff --git a/folly/experimental/StringKeyedCommon.h b/folly/experimental/StringKeyedCommon.h new file mode 100644 index 00000000..a086210a --- /dev/null +++ b/folly/experimental/StringKeyedCommon.h @@ -0,0 +1,44 @@ +/* + * Copyright 2015 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +// Copyright 2013-present Facebook. All Rights Reserved. +// @author: Pavlo Kushnir (pavlo) + +#ifndef FOLLY_EXPERIMENTAL_STRINGKEYEDCOMMON_H_ +#define FOLLY_EXPERIMENTAL_STRINGKEYEDCOMMON_H_ + +#include +#include + +namespace folly { + +template +StringPiece stringPieceDup(StringPiece piece, const Alloc& alloc) { + auto size = piece.size(); + auto keyDup = typename Alloc::template rebind::other(alloc) + .allocate(size); + memcpy(keyDup, piece.data(), size * sizeof(typename StringPiece::value_type)); + return StringPiece(keyDup, size); +} + +template +void stringPieceDel(StringPiece piece, const Alloc& alloc) { + typename Alloc::template rebind::other(alloc) + .deallocate(const_cast(piece.data()), piece.size()); +} + +} // folly + +#endif /* FOLLY_EXPERIMENTAL_STRINGKEYEDCOMMON_H_ */ diff --git a/folly/experimental/StringKeyedMap.h b/folly/experimental/StringKeyedMap.h new file mode 100644 index 00000000..5b33a727 --- /dev/null +++ b/folly/experimental/StringKeyedMap.h @@ -0,0 +1,205 @@ +/* + * Copyright 2015 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +// Copyright 2013-present Facebook. All Rights Reserved. +// @author: Pavlo Kushnir (pavlo) + +#ifndef FOLLY_EXPERIMENTAL_STRINGKEYEDMAP_H_ +#define FOLLY_EXPERIMENTAL_STRINGKEYEDMAP_H_ + +#include +#include +#include +#include +#include + +namespace folly { + +/** + * Wrapper class for map that can + * perform lookup operations with StringPiece, not only string. + * + * It uses kind of hack: string pointed by StringPiece is copied when + * StringPiece is inserted into map + */ +template , + class Alloc = std::allocator>> +class StringKeyedMap + : private std::map { +private: + using Base = std::map; + +public: + typedef typename Base::key_type key_type; + typedef typename Base::mapped_type mapped_type; + typedef typename Base::value_type value_type; + typedef typename Base::key_compare key_compare; + typedef typename Base::allocator_type allocator_type; + typedef typename Base::reference reference; + typedef typename Base::const_reference const_reference; + typedef typename Base::pointer pointer; + typedef typename Base::const_pointer const_pointer; + typedef typename Base::iterator iterator; + typedef typename Base::const_iterator const_iterator; + typedef typename Base::reverse_iterator reverse_iterator; + typedef typename Base::const_reverse_iterator const_reverse_iterator; + typedef typename Base::difference_type difference_type; + typedef typename Base::size_type size_type; + + using Base::get_allocator; + + // Ctors in the same order as + // http://cplusplus.com/reference/map/map/map/ + explicit StringKeyedMap( + const key_compare& comp = key_compare(), + const allocator_type& alloc = allocator_type()) + : Base(comp, alloc) { + } + + explicit StringKeyedMap(const allocator_type& alloc) + : Base(alloc) { + } + + template + explicit StringKeyedMap( + InputIterator b, InputIterator e, + const key_compare& comp = key_compare(), + const allocator_type& alloc = allocator_type()) + : Base(comp, alloc) { + for (; b != e; ++b) { + // emplace() will carry the duplication + emplace(b->first, b->second); + } + } + + StringKeyedMap(const StringKeyedMap& rhs) + : StringKeyedMap(rhs, rhs.get_allocator()) { + } + + StringKeyedMap(const StringKeyedMap& rhs, const allocator_type& a) + : StringKeyedMap(rhs.begin(), rhs.end(), rhs.key_comp(), a) { + } + + StringKeyedMap(StringKeyedMap&& other) noexcept + : Base(std::move(other)) { + } + + StringKeyedMap(StringKeyedMap&& other, const allocator_type& a) noexcept + : Base(std::move(other)/*, a*/ /* not supported by gcc */) { + } + + StringKeyedMap(std::initializer_list il, + const key_compare& comp = key_compare(), + const allocator_type& alloc = allocator_type()) + : StringKeyedMap(il.begin(), il.end(), comp, alloc) { + } + + StringKeyedMap& operator=(const StringKeyedMap& other) & { + if (this == &other) { + return *this; + } + return *this = StringKeyedMap(other); + } + + StringKeyedMap& operator=(StringKeyedMap&& other) & noexcept { + assert(this != &other); + clear(); + Base::operator=(std::move(other)); + return *this; + } + + using Base::empty; + using Base::size; + using Base::max_size; + using Base::begin; + using Base::end; + using Base::rbegin; + using Base::rend; + using Base::cbegin; + using Base::cend; + using Base::crbegin; + using Base::crend; + + // no need for copy/move overload as StringPiece is small struct + mapped_type& operator[](StringPiece key) { + auto it = find(key); + if (it != end()) { + return it->second; + } + // operator[] will create new (key, value) pair + // we need to allocate memory for key + return Base::operator[](stringPieceDup(key, get_allocator())); + } + + using Base::at; + using Base::find; + using Base::lower_bound; + using Base::upper_bound; + + template + std::pair emplace(StringPiece key, Args&&... args) { + auto it = find(key); + if (it != end()) { + return {it, false}; + } + return Base::emplace(stringPieceDup(key, get_allocator()), + std::forward(args)...); + } + + std::pair insert(value_type val) { + auto it = find(val.first); + if (it != end()) { + return {it, false}; + } + return Base::insert( + std::make_pair(stringPieceDup(val.first, get_allocator()), + std::move(val.second))); + } + + iterator erase(const_iterator position) { + auto key = position->first; + auto result = Base::erase(position); + stringPieceDel(key, get_allocator()); + return result; + } + + size_type erase(StringPiece key) { + auto it = find(key); + if (it == end()) { + return 0; + } + erase(it); + return 1; + } + + void clear() noexcept { + for (auto& it : *this) { + stringPieceDel(it.first, get_allocator()); + } + Base::clear(); + } + + ~StringKeyedMap() { + // Here we assume that map doesn't use keys in destructor + for (auto& it : *this) { + stringPieceDel(it.first, get_allocator()); + } + } +}; + +} // folly + +#endif /* FOLLY_EXPERIMENTAL_STRINGKEYEDMAP_H_ */ diff --git a/folly/experimental/StringKeyedSet.h b/folly/experimental/StringKeyedSet.h new file mode 100644 index 00000000..e6a7e6ac --- /dev/null +++ b/folly/experimental/StringKeyedSet.h @@ -0,0 +1,189 @@ +/* + * Copyright 2015 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +// Copyright 2013-present Facebook. All Rights Reserved. +// @author: Pavlo Kushnir (pavlo) + +#ifndef FOLLY_EXPERIMENTAL_STRINGKEYEDSET_H_ +#define FOLLY_EXPERIMENTAL_STRINGKEYEDSET_H_ + +#include +#include +#include +#include +#include + +namespace folly { + +/** + * Wrapper class for set that can + * perform lookup operations with StringPiece, not only string. + * + * It uses kind of hack: string pointed by StringPiece is copied when + * StringPiece is inserted into set + */ +template , + class Alloc = std::allocator> +class StringKeyedSetBase + : private std::set { +private: + using Base = std::set; + +public: + typedef typename Base::key_type key_type; + typedef typename Base::value_type value_type; + typedef typename Base::key_compare key_compare; + typedef typename Base::allocator_type allocator_type; + typedef typename Base::reference reference; + typedef typename Base::const_reference const_reference; + typedef typename Base::pointer pointer; + typedef typename Base::const_pointer const_pointer; + typedef typename Base::iterator iterator; + typedef typename Base::const_iterator const_iterator; + typedef typename Base::reverse_iterator reverse_iterator; + typedef typename Base::const_reverse_iterator const_reverse_iterator; + typedef typename Base::size_type size_type; + typedef typename Base::difference_type difference_type; + + explicit StringKeyedSetBase( + const key_compare& comp = key_compare(), + const allocator_type& alloc = allocator_type()) + : Base(comp, alloc) { + } + + explicit StringKeyedSetBase(const allocator_type& alloc) + : Base(alloc) { + } + + template + StringKeyedSetBase( + InputIterator b, InputIterator e, + const key_compare& comp = key_compare(), + const allocator_type& alloc = allocator_type()) + : Base(comp, alloc) { + for (; b != e; ++b) { + emplace(*b); + } + } + + StringKeyedSetBase(const StringKeyedSetBase& rhs) + : StringKeyedSetBase(rhs, rhs.get_allocator()) { + } + + StringKeyedSetBase(const StringKeyedSetBase& rhs, + const allocator_type& a) + : StringKeyedSetBase(rhs.begin(), rhs.end(), rhs.key_comp(), a) { + } + + StringKeyedSetBase(StringKeyedSetBase&& other) noexcept + : Base(std::move(other)) { + assert(other.empty()); + } + + StringKeyedSetBase(StringKeyedSetBase&& other, + const allocator_type& alloc) noexcept + : Base(std::move(other), alloc) { + assert(other.empty()); + } + + StringKeyedSetBase( + std::initializer_list il, + const key_compare& comp = key_compare(), + const allocator_type& alloc = allocator_type()) + : StringKeyedSetBase(il.begin(), il.end(), comp, alloc) { + } + + StringKeyedSetBase& operator=(const StringKeyedSetBase& other) { + if (this == &other) { + return *this; + } + return *this = StringKeyedSetBase(other); + } + + StringKeyedSetBase& operator=(StringKeyedSetBase&& other) noexcept { + assert(this != &other); + clear(); + Base::operator=(std::move(other)); + assert(other.empty()); + return *this; + } + + using Base::empty; + using Base::size; + using Base::max_size; + using Base::begin; + using Base::end; + using Base::cbegin; + using Base::cend; + using Base::find; + using Base::lower_bound; + using Base::upper_bound; + + template + std::pair emplace(Args&&... args) { + auto key = StringPiece(std::forward(args)...); + auto it = find(key); + if (it != end()) { + return {it, false}; + } + return Base::emplace(stringPieceDup(key, get_allocator())); + } + + std::pair insert(value_type val) { + auto it = find(val); + if (it != end()) { + return {it, false}; + } + return Base::insert(stringPieceDup(val, get_allocator())); + } + + iterator erase(const_iterator position) { + auto key = *position; + auto result = Base::erase(position); + stringPieceDel(key, get_allocator()); + return result; + } + + size_type erase(StringPiece key) { + auto it = find(key); + if (it == end()) { + return 0; + } + erase(it); + return 1; + } + + void clear() noexcept { + for (auto it : *this) { + stringPieceDel(it, get_allocator()); + } + Base::clear(); + } + + using Base::get_allocator; + + ~StringKeyedSetBase() { + // Here we assume that set doesn't use keys in destructor + for (auto it : *this) { + stringPieceDel(it, get_allocator()); + } + } +}; + +using StringKeyedSet = StringKeyedSetBase<>; + +} // folly + +#endif /* FOLLY_EXPERIMENTAL_STRINGKEYEDSET_H_ */ diff --git a/folly/experimental/StringKeyedUnorderedMap.h b/folly/experimental/StringKeyedUnorderedMap.h new file mode 100644 index 00000000..395bc823 --- /dev/null +++ b/folly/experimental/StringKeyedUnorderedMap.h @@ -0,0 +1,232 @@ +/* + * Copyright 2015 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +// Copyright 2013-present Facebook. All Rights Reserved. +// @author: Pavlo Kushnir (pavlo) + +#ifndef FOLLY_EXPERIMENTAL_STRINGKEYEDUNORDEREDMAP_H_ +#define FOLLY_EXPERIMENTAL_STRINGKEYEDUNORDEREDMAP_H_ + +#include +#include +#include +#include +#include + +namespace folly { + +/** + * Wrapper class for unordered_map that can + * perform lookup operations with StringPiece, not only string. + * + * It uses kind of hack: string pointed by StringPiece is copied when + * StringPiece is inserted into map + */ +template , + class Alloc = std::allocator>> +class StringKeyedUnorderedMap + : private std::unordered_map { +private: + using Base = std::unordered_map; + +public: + typedef typename Base::key_type key_type; + typedef typename Base::mapped_type mapped_type; + typedef typename Base::value_type value_type; + typedef typename Base::hasher hasher; + typedef typename Base::key_equal key_equal; + typedef typename Base::allocator_type allocator_type; + typedef typename Base::reference reference; + typedef typename Base::const_reference const_reference; + typedef typename Base::pointer pointer; + typedef typename Base::const_pointer const_pointer; + typedef typename Base::iterator iterator; + typedef typename Base::const_iterator const_iterator; + typedef typename Base::size_type size_type; + typedef typename Base::difference_type difference_type; + + explicit StringKeyedUnorderedMap() {} + + explicit StringKeyedUnorderedMap( + size_type n, + const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& alloc = allocator_type()) + : Base(n, hf, eql, alloc) { + } + + explicit StringKeyedUnorderedMap(const allocator_type& a) + : Base(a) { + } + + template + StringKeyedUnorderedMap(InputIterator b, InputIterator e) { + for (; b != e; ++b) { + // insert() will carry the duplication + emplace(b->first, b->second); + } + } + + template + StringKeyedUnorderedMap( + InputIterator b, InputIterator e, + size_type n, + const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& alloc = allocator_type()) + : Base(n, hf, eql, alloc) { + for (; b != e; ++b) { + // insert() will carry the duplication + emplace(b->first, b->second); + } + } + + StringKeyedUnorderedMap(const StringKeyedUnorderedMap& rhs) + : StringKeyedUnorderedMap(rhs.begin(), rhs.end(), + rhs.bucket_count(), + rhs.hash_function(), + rhs.key_eq(), + rhs.get_allocator()) { + } + + StringKeyedUnorderedMap(StringKeyedUnorderedMap&& rhs) noexcept + : StringKeyedUnorderedMap(std::move(rhs), rhs.get_allocator()) { + } + + StringKeyedUnorderedMap(StringKeyedUnorderedMap&& other, + const allocator_type& a) noexcept + : Base(std::move(other)/*, a*/ /* not supported by gcc */) { + } + + StringKeyedUnorderedMap(std::initializer_list il) + : StringKeyedUnorderedMap(il.begin(), il.end()) { + } + + StringKeyedUnorderedMap( + std::initializer_list il, + size_type n, + const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& alloc = allocator_type()) + : StringKeyedUnorderedMap(il.begin(), il.end(), n, hf, eql, alloc) { + } + + StringKeyedUnorderedMap& operator=(const StringKeyedUnorderedMap& other) & { + if (this == &other) { + return *this; + } + return *this = StringKeyedUnorderedMap(other); + } + + StringKeyedUnorderedMap& + operator=(StringKeyedUnorderedMap&& other) & noexcept { + assert(this != &other); + clear(); + Base::operator=(std::move(other)); + return *this; + } + + using Base::empty; + using Base::size; + using Base::max_size; + using Base::begin; + using Base::end; + using Base::cbegin; + using Base::cend; + + bool operator==(const StringKeyedUnorderedMap& rhs) { + const Base& lhs = *this; + return lhs == rhs; + } + + // No need for copy/move overload as StringPiece is small struct. + mapped_type& operator[](StringPiece key) { + auto it = find(key); + if (it != end()) { + return it->second; + } + // operator[] will create new (key, value) pair + // we need to allocate memory for key + return Base::operator[](stringPieceDup(key, get_allocator())); + } + + using Base::at; + using Base::find; + + template + std::pair emplace(StringPiece key, Args&&... args) { + auto it = find(key); + if (it != end()) { + return {it, false}; + } + return Base::emplace(stringPieceDup(key, get_allocator()), + std::forward(args)...); + } + + std::pair insert(value_type val) { + auto it = find(val.first); + if (it != end()) { + return {it, false}; + } + auto valCopy = std::make_pair(stringPieceDup(val.first, get_allocator()), + std::move(val.second)); + return Base::insert(valCopy); + } + + iterator erase(const_iterator position) { + auto key = position->first; + auto result = Base::erase(position); + stringPieceDel(key, get_allocator()); + return result; + } + + size_type erase(StringPiece key) { + auto it = find(key); + if (it == end()) { + return 0; + } + erase(it); + return 1; + } + + void clear() noexcept { + for (auto& it : *this) { + stringPieceDel(it.first, get_allocator()); + } + Base::clear(); + } + + using Base::reserve; + using Base::hash_function; + using Base::key_eq; + using Base::get_allocator; + using Base::bucket_count; + using Base::max_bucket_count; + using Base::bucket_size; + using Base::bucket; + + ~StringKeyedUnorderedMap() { + // Here we assume that unordered_map doesn't use keys in destructor + for (auto& it : *this) { + stringPieceDel(it.first, get_allocator()); + } + } +}; + +} // folly + +#endif /* FOLLY_EXPERIMENTAL_STRINGKEYEDUNORDEREDMAP_H_ */ diff --git a/folly/experimental/StringKeyedUnorderedSet.h b/folly/experimental/StringKeyedUnorderedSet.h new file mode 100644 index 00000000..c4f3a658 --- /dev/null +++ b/folly/experimental/StringKeyedUnorderedSet.h @@ -0,0 +1,225 @@ +/* + * Copyright 2015 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +// Copyright 2013-present Facebook. All Rights Reserved. +// @author: Pavlo Kushnir (pavlo) + +#ifndef FOLLY_EXPERIMENTAL_STRINGKEYEDUNORDEREDSET_H_ +#define FOLLY_EXPERIMENTAL_STRINGKEYEDUNORDEREDSET_H_ + +#include +#include +#include +#include +#include + +namespace folly { + +/** + * Wrapper class for unordered_set that can + * perform lookup operations with StringPiece, not only string. + * + * It uses kind of hack: string pointed by StringPiece is copied when + * StringPiece is inserted into set + */ +template , + class Alloc = std::allocator> +class BasicStringKeyedUnorderedSet + : private std::unordered_set { + using Base = std::unordered_set; + +public: + typedef typename Base::key_type key_type; + typedef typename Base::value_type value_type; + typedef typename Base::hasher hasher; + typedef typename Base::key_equal key_equal; + typedef typename Base::allocator_type allocator_type; + typedef typename Base::reference reference; + typedef typename Base::const_reference const_reference; + typedef typename Base::pointer pointer; + typedef typename Base::const_pointer const_pointer; + typedef typename Base::iterator iterator; + typedef typename Base::const_iterator const_iterator; + typedef typename Base::size_type size_type; + typedef typename Base::difference_type difference_type; + + // Constructors in the same order as in + // http://cplusplus.com/reference/unordered_set/unordered_set/unordered_set/ + explicit BasicStringKeyedUnorderedSet() { + } + + explicit BasicStringKeyedUnorderedSet( + size_type n, + const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& alloc = allocator_type()) + : Base(n, hf, eql, alloc) { + } + + explicit BasicStringKeyedUnorderedSet(const allocator_type& alloc) + : Base(alloc) { + } + + template + BasicStringKeyedUnorderedSet(InputIterator b, InputIterator e) { + for (; b != e; ++b) { + emplace(*b); + } + } + + template + BasicStringKeyedUnorderedSet( + InputIterator b, InputIterator e, + size_type n, + const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& alloc = allocator_type()) + : Base(n, hf, eql, alloc) { + for (; b != e; ++b) { + emplace(*b); + } + } + + BasicStringKeyedUnorderedSet(const BasicStringKeyedUnorderedSet& rhs) + : BasicStringKeyedUnorderedSet(rhs, rhs.get_allocator()) { + } + + BasicStringKeyedUnorderedSet(const BasicStringKeyedUnorderedSet& rhs, + const allocator_type& a) + : BasicStringKeyedUnorderedSet(rhs.begin(), + rhs.end(), + rhs.bucket_count(), + rhs.hash_function(), + rhs.key_eq(), + a) { + } + + BasicStringKeyedUnorderedSet(BasicStringKeyedUnorderedSet&& rhs) noexcept + : Base(std::move(rhs)) { + assert(rhs.empty()); + } + + BasicStringKeyedUnorderedSet(BasicStringKeyedUnorderedSet&& rhs, + const allocator_type& a) noexcept + : Base(std::move(rhs)/* , a */ /* not supported by gcc */) { + assert(rhs.empty()); + } + + BasicStringKeyedUnorderedSet(std::initializer_list il) + : BasicStringKeyedUnorderedSet(il.begin(), il.end()) { + } + + BasicStringKeyedUnorderedSet( + std::initializer_list il, + size_type n, + const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& alloc = allocator_type()) + : BasicStringKeyedUnorderedSet(il.begin(), il.end(), n, hf, eql, alloc) { + } + + BasicStringKeyedUnorderedSet& + operator=(const BasicStringKeyedUnorderedSet& rhs) & { + if (this == &rhs) { + return *this; + } + // Cost is as bad as a full copy, so to it via copy + move + return *this = BasicStringKeyedUnorderedSet(rhs); + } + + BasicStringKeyedUnorderedSet& + operator=(BasicStringKeyedUnorderedSet&& rhs) & noexcept { + assert(this != &rhs); + clear(); + Base::operator=(std::move(rhs)); + return *this; + } + + using Base::empty; + using Base::size; + using Base::max_size; + using Base::begin; + using Base::end; + using Base::cbegin; + using Base::cend; + using Base::find; + + bool operator==(const BasicStringKeyedUnorderedSet& rhs) const { + const Base& lhs = *this; + return lhs == rhs; + } + + template + std::pair emplace(Args&&... args) { + auto key = StringPiece(std::forward(args)...); + auto it = find(key); + return it != end() + ? std::make_pair(it, false) + : Base::emplace(stringPieceDup(key, get_allocator())); + } + + std::pair insert(value_type val) { + auto it = find(val); + return it != end() + ? std::make_pair(it, false) + : Base::insert(stringPieceDup(val, get_allocator())); + } + + iterator erase(const_iterator position) { + auto key = *position; + auto result = Base::erase(position); + stringPieceDel(key, get_allocator()); + return result; + } + + size_type erase(folly::StringPiece key) { + auto it = find(key); + if (it == end()) { + return 0; + } + erase(it); + return 1; + } + + void clear() noexcept { + for (auto& it : *this) { + stringPieceDel(it, get_allocator()); + } + Base::clear(); + } + + using Base::reserve; + using Base::hash_function; + using Base::key_eq; + using Base::get_allocator; + using Base::bucket_count; + using Base::max_bucket_count; + using Base::bucket_size; + using Base::bucket; + + ~BasicStringKeyedUnorderedSet() { + // Here we assume that unordered_set doesn't use keys in destructor + for (auto& it : *this) { + stringPieceDel(it, get_allocator()); + } + } +}; + +typedef BasicStringKeyedUnorderedSet<> StringKeyedUnorderedSet; + +} // folly + +#endif /* FOLLY_EXPERIMENTAL_STRINGKEYEDUNORDEREDSET_H_ */ diff --git a/folly/experimental/test/StringKeyedBenchmark.cpp b/folly/experimental/test/StringKeyedBenchmark.cpp new file mode 100644 index 00000000..a8b9f542 --- /dev/null +++ b/folly/experimental/test/StringKeyedBenchmark.cpp @@ -0,0 +1,144 @@ +/* + * Copyright 2015 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +// Copyright 2013-present Facebook. All Rights Reserved. + +#include +#include + +#include +#include +#include +#include +#include + +#include +#include +#include +#include + +using folly::StringKeyedMap; +using folly::StringKeyedSet; +using folly::StringKeyedUnorderedMap; +using folly::StringKeyedUnorderedSet; +using folly::StringPiece; +using std::map; +using std::to_string; +using std::set; +using std::string; +using std::unordered_map; +using std::unordered_set; + +static map m; +static StringKeyedMap skm; +static set s; +static StringKeyedSet sks; +static unordered_map um; +static StringKeyedUnorderedMap skum; +static unordered_set us; +static StringKeyedUnorderedSet skus; +static const string lookup("123"); +static const folly::StringPiece lookupPiece(lookup); + +static void initBenchmarks() { + for (int i = 0; i < 1000; ++i) { + auto iStr = to_string(i); + m[iStr] = i; + skm.insert(make_pair(iStr, i)); + um[iStr] = i; + skum.insert(make_pair(iStr, i)); + s.insert(iStr); + sks.insert(iStr); + us.insert(iStr); + skus.insert(iStr); + } +} + +BENCHMARK(std_map_benchmark_find) { + folly::doNotOptimizeAway(m.find(lookupPiece.str())->second); +} + +BENCHMARK_RELATIVE(sk_map_benchmark_find) { + folly::doNotOptimizeAway(skm.find(lookupPiece)->second); +} + +BENCHMARK(std_map_benchmark_erase_emplace) { + m.erase(lookup); + m.emplace(lookup, 123); +} + +BENCHMARK_RELATIVE(sk_map_benchmark_erase_emplace) { + skm.erase(lookup); + skm.emplace(lookup, 123); +} + +BENCHMARK(std_unordered_map_benchmark_find) { + folly::doNotOptimizeAway(um.find(lookupPiece.str())->second); +} + +BENCHMARK_RELATIVE(sk_unordered_map_benchmark_find) { + folly::doNotOptimizeAway(skum.find(lookupPiece)->second); +} + +BENCHMARK(std_unordered_map_benchmark_erase_emplace) { + um.erase(lookup); + um.emplace(lookup, 123); +} + +BENCHMARK_RELATIVE(sk_unordered_map_benchmark_erase_emplace) { + skum.erase(lookup); + skum.emplace(lookup, 123); +} + +BENCHMARK(std_set_benchmark_find) { + folly::doNotOptimizeAway(s.find(lookupPiece.str())); +} + +BENCHMARK_RELATIVE(sk_set_benchmark_find) { + folly::doNotOptimizeAway(sks.find(lookupPiece)); +} + +BENCHMARK(std_set_benchmark_erase_emplace) { + s.erase(lookup); + s.emplace(lookup); +} + +BENCHMARK_RELATIVE(sk_set_benchmark_erase_emplace) { + sks.erase(lookup); + sks.emplace(lookup); +} + +BENCHMARK(std_unordered_set_benchmark_find) { + folly::doNotOptimizeAway(us.find(lookupPiece.str())); +} + +BENCHMARK_RELATIVE(sk_unordered_set_benchmark_find) { + folly::doNotOptimizeAway(skus.find(lookupPiece)); +} + +BENCHMARK(std_unordered_set_benchmark_erase_emplace) { + us.erase(lookup); + us.emplace(lookup); +} + +BENCHMARK_RELATIVE(sk_unordered_set_benchmark_erase_emplace) { + skus.erase(lookup); + skus.emplace(lookup); +} + +int main(int argc, char **argv) { + initBenchmarks(); + folly::runBenchmarks(); +} diff --git a/folly/experimental/test/StringKeyedTest.cpp b/folly/experimental/test/StringKeyedTest.cpp new file mode 100644 index 00000000..782e6cd3 --- /dev/null +++ b/folly/experimental/test/StringKeyedTest.cpp @@ -0,0 +1,528 @@ +/* + * Copyright 2015 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +// Copyright 2013-present Facebook. All Rights Reserved. + +#include +#include +#include + +#include +#include + +#include +#include +#include +#include +#include + +using folly::StringKeyedMap; +using folly::StringKeyedSetBase; +using folly::StringKeyedUnorderedMap; +using folly::BasicStringKeyedUnorderedSet; +using folly::StringPiece; +using std::string; + +static unsigned long long allocated = 0; +static unsigned long long freed = 0; + +template +struct MemoryLeakCheckerAllocator { + typedef typename Alloc::value_type value_type; + typedef value_type *pointer; + typedef value_type const *const_pointer; + typedef value_type &reference; + typedef value_type const *const_reference; + + typedef std::ptrdiff_t difference_type; + typedef std::size_t size_type; + + explicit MemoryLeakCheckerAllocator() { + } + + explicit MemoryLeakCheckerAllocator(Alloc alloc) + : alloc_(alloc) { + } + + template + MemoryLeakCheckerAllocator(const MemoryLeakCheckerAllocator& other) + : alloc_(other.allocator()) { + } + + value_type* allocate(size_t n, const void* hint = nullptr) { + auto p = alloc_.allocate(n, hint); + allocated += n * sizeof(value_type); + return p; + } + + void deallocate(value_type* p, size_t n) { + alloc_.deallocate(p, n); + freed += n * sizeof(value_type); + } + + size_t max_size() const { + return alloc_.max_size(); + } + + template + void construct(value_type* p, Args&&... args) { + alloc_.construct(p, std::forward(args)...); + } + + void destroy(value_type* p) { + alloc_.destroy(p); + } + + template + struct rebind { + typedef MemoryLeakCheckerAllocator< + typename std::allocator_traits::template rebind_alloc + > other; + }; + + const Alloc& allocator() const { + return alloc_; + } + + bool operator!=(const MemoryLeakCheckerAllocator& other) const { + return alloc_ != other.alloc_; + } + + bool operator==(const MemoryLeakCheckerAllocator& other) const { + return alloc_ == other.alloc_; + } + +private: + Alloc alloc_; +}; + +typedef MemoryLeakCheckerAllocator> KeyLeakChecker; +typedef MemoryLeakCheckerAllocator< + std::allocator>> ValueLeakChecker; + +typedef StringKeyedUnorderedMap, ValueLeakChecker> + LeakCheckedUnorderedMap; + +typedef StringKeyedSetBase, ValueLeakChecker> LeakCheckedSet; + +typedef StringKeyedMap, + ValueLeakChecker> LeakCheckedMap; + +using LeakCheckedUnorderedSet = BasicStringKeyedUnorderedSet< + folly::StringPieceHash, + std::equal_to, + ValueLeakChecker>; + +TEST(StringKeyedUnorderedMapTest, sanity) { + LeakCheckedUnorderedMap map; + EXPECT_TRUE(map.empty()); + EXPECT_EQ(map.size(), 0); + + { + string s("hello"); + StringPiece piece(s, 3); + map.insert({s, 1}); + EXPECT_FALSE(map.emplace(s, 2).second); + EXPECT_TRUE(map.emplace(piece, 3).second); + } + + EXPECT_EQ(map.size(), 2); + + map = map; + + EXPECT_EQ(map.find("hello")->second, 1); + EXPECT_EQ(map.find("lo")->second, 3); + + map.erase(map.find("hello")); + + EXPECT_EQ(map.size(), 1); + + for (auto& it : map) { + EXPECT_EQ(it.first, "lo"); + } +} + +TEST(StringKeyedUnorderedMapTest, constructors) { + LeakCheckedUnorderedMap map { + {"hello", 1}, + {"lo", 3} + }; + + LeakCheckedUnorderedMap map2(map); + EXPECT_EQ(map2.size(), 2); + EXPECT_TRUE(map2 == map); + + map2.erase("lo"); + for (auto& it : map2) { + EXPECT_EQ(it.first, "hello"); + } + + map2.clear(); + + EXPECT_TRUE(map2.empty()); + + map2.emplace("key1", 1); + + LeakCheckedUnorderedMap map3(move(map2)); + + EXPECT_EQ(map3.size(), 1); + EXPECT_EQ(map3["key1"], 1); + + EXPECT_EQ(map3["key0"], 0); + EXPECT_EQ(map3.size(), 2); + + map3.reserve(1000); + + EXPECT_EQ(map3.size(), 2); + + LeakCheckedUnorderedMap map4 { + {"key0", 0}, + {"key1", 1} + }; + + EXPECT_EQ(map4.erase("key0"), 1); + EXPECT_EQ(map4.size(), 1); + EXPECT_EQ(map4.find("key0"), map4.end()); + + map3 = map4; + + EXPECT_EQ(map3.size(), 1); + EXPECT_EQ(map4.size(), 1); + EXPECT_EQ(map4.max_size(), map3.max_size()); + + map4 = std::move(map3); + + EXPECT_EQ(map4.size(), 1); + EXPECT_EQ(map4.at("key1"), 1); +} + +TEST(StringKeyedSetTest, sanity) { + LeakCheckedSet set; + EXPECT_TRUE(set.empty()); + EXPECT_EQ(set.size(), 0); + + { + string s("hello"); + StringPiece piece(s, 3); + set.insert(s); + EXPECT_FALSE(set.emplace(s).second); + EXPECT_TRUE(set.emplace(piece).second); + } + + EXPECT_EQ(set.size(), 2); + + set = set; + + EXPECT_NE(set.find(StringPiece("hello")), set.end()); + EXPECT_NE(set.find("lo"), set.end()); + + auto it = set.begin(); + EXPECT_EQ(*it, "hello"); + EXPECT_EQ(*(++it), "lo"); + EXPECT_EQ(++it, set.end()); + + set.erase(set.find("hello")); + + EXPECT_EQ(set.size(), 1); + + for (auto it : set) { + EXPECT_EQ(it, "lo"); + } +} + +TEST(StringKeyedSetTest, constructors) { + LeakCheckedSet set { + "hello", + "lo" + }; + LeakCheckedSet set2(set); + + EXPECT_EQ(set2.size(), 2); + + set2.erase("lo"); + for (auto it : set2) { + EXPECT_EQ(it, "hello"); + } + + set2.clear(); + + EXPECT_TRUE(set2.empty()); + + set2.emplace("key1"); + + LeakCheckedSet set3(move(set2)); + + EXPECT_EQ(set3.size(), 1); + EXPECT_EQ(set3.insert("key1").second, false); + + EXPECT_EQ(set3.emplace("key0").second, true); + EXPECT_EQ(set3.size(), 2); + + EXPECT_EQ(set3.size(), 2); + + LeakCheckedSet set4 { + "key0", + "key1" + }; + + EXPECT_EQ(set4.erase("key0"), 1); + EXPECT_EQ(set4.size(), 1); + EXPECT_EQ(set4.find("key0"), set4.end()); + + set3 = set4; + + EXPECT_EQ(set3.size(), 1); + EXPECT_EQ(set4.size(), 1); + EXPECT_EQ(set4.max_size(), set3.max_size()); + + set4 = std::move(set3); + + EXPECT_EQ(set4.size(), 1); + EXPECT_NE(set4.find("key1"), set4.end()); +} + +TEST(StringKeyedUnorderedSetTest, sanity) { + LeakCheckedUnorderedSet set; + EXPECT_TRUE(set.empty()); + EXPECT_EQ(set.size(), 0); + + { + string s("hello"); + StringPiece piece(s, 3); + set.insert(s); + EXPECT_FALSE(set.emplace(s).second); + EXPECT_TRUE(set.emplace(piece).second); + } + + EXPECT_EQ(set.size(), 2); + + set = set; + + EXPECT_NE(set.find("hello"), set.end()); + EXPECT_NE(set.find("lo"), set.end()); + + set.erase(set.find("hello")); + + EXPECT_EQ(set.size(), 1); + + for (auto it : set) { + EXPECT_EQ(it, "lo"); + } +} + +TEST(StringKeyedUnorderedSetTest, constructors) { + LeakCheckedUnorderedSet s1; + EXPECT_TRUE(s1.empty()); + + LeakCheckedUnorderedSet s2(10); + EXPECT_TRUE(s2.empty()); + EXPECT_GE(s2.bucket_count(), 10); + + std::list lst { "abc", "def" }; + LeakCheckedUnorderedSet s3(lst.begin(), lst.end()); + EXPECT_EQ(s3.size(), 2); + EXPECT_NE(s3.find("abc"), s3.end()); + EXPECT_NE(s3.find("def"), s3.end()); + EXPECT_TRUE(s3 == (LeakCheckedUnorderedSet{"abc", "def"})); + + LeakCheckedUnorderedSet s4(const_cast(s3)); + EXPECT_TRUE(s4 == s3); + + LeakCheckedUnorderedSet s5(const_cast(s3), + ValueLeakChecker()); + EXPECT_TRUE(s5 == s3); + + LeakCheckedUnorderedSet s6(std::move(s3)); + EXPECT_TRUE(s3.empty()); + EXPECT_TRUE(s6 == s5); + + LeakCheckedUnorderedSet s7(std::move(s6), s6.get_allocator()); + EXPECT_TRUE(s6.empty()); + EXPECT_TRUE(s7 == s5); + + LeakCheckedUnorderedSet s8 { + "hello", + "lo" + }; + EXPECT_EQ(s8.size(), 2); + EXPECT_NE(s8.find("hello"), s8.end()); + EXPECT_NE(s8.find("lo"), s8.end()); + + LeakCheckedUnorderedSet s9({ + "hello", + "lo" + }, 10); + EXPECT_EQ(s9.size(), 2); + EXPECT_NE(s9.find("hello"), s9.end()); + EXPECT_NE(s9.find("lo"), s9.end()); + + LeakCheckedUnorderedSet set2(s8); + EXPECT_EQ(set2.size(), 2); + + set2.erase("lo"); + for (auto it : set2) { + EXPECT_EQ(it, "hello"); + } + + set2.clear(); + + EXPECT_TRUE(set2.empty()); + + set2.emplace("key1"); + + LeakCheckedUnorderedSet set3(move(set2)); + + EXPECT_EQ(set3.size(), 1); + EXPECT_EQ(set3.insert("key1").second, false); + + EXPECT_EQ(set3.emplace("key0").second, true); + EXPECT_EQ(set3.size(), 2); + + set3.reserve(1000); + + EXPECT_EQ(set3.size(), 2); + + LeakCheckedUnorderedSet set4 { + "key0", + "key1" + }; + + EXPECT_EQ(set4.erase("key0"), 1); + EXPECT_EQ(set4.size(), 1); + EXPECT_EQ(set4.find("key0"), set4.end()); + + set3 = set4; + + EXPECT_EQ(set3.size(), 1); + EXPECT_EQ(set4.size(), 1); + EXPECT_EQ(set4.max_size(), set3.max_size()); + + set4 = std::move(set3); + + EXPECT_EQ(set4.size(), 1); + EXPECT_NE(set4.find("key1"), set4.end()); +} + +TEST(StringKeyedMapTest, sanity) { + LeakCheckedMap map; + EXPECT_TRUE(map.empty()); + EXPECT_EQ(map.size(), 0); + + { + string s("hello"); + StringPiece piece(s, 3); + map.insert({s, 1}); + EXPECT_FALSE(map.emplace(s, 2).second); + EXPECT_TRUE(map.emplace(piece, 3).second); + } + + EXPECT_EQ(map.size(), 2); + + map = map; + + EXPECT_EQ(map.find("hello")->second, 1); + EXPECT_EQ(map.find("lo")->second, 3); + + auto it = map.begin(); + EXPECT_EQ(it->first, "hello"); + EXPECT_EQ((++it)->first, "lo"); + EXPECT_EQ(++it, map.end()); + + map.erase(map.find("hello")); + + EXPECT_EQ(map.size(), 1); + + for (auto& it : map) { + EXPECT_EQ(it.first, "lo"); + } +} + +TEST(StringKeyedMapTest, constructors) { + LeakCheckedMap map { + {"hello", 1}, + {"lo", 3} + }; + LeakCheckedMap map2(map); + + EXPECT_EQ(map2.size(), 2); + + map2.erase("lo"); + for (auto& it : map2) { + EXPECT_EQ(it.first, "hello"); + } + + map2.clear(); + + EXPECT_TRUE(map2.empty()); + + map2.emplace("key1", 1); + + LeakCheckedMap map3(move(map2)); + + EXPECT_EQ(map3.size(), 1); + EXPECT_EQ(map3["key1"], 1); + + EXPECT_EQ(map3["key0"], 0); + EXPECT_EQ(map3.size(), 2); + + LeakCheckedMap map4 { + {"key0", 0}, + {"key1", 1} + }; + + EXPECT_EQ(map4.erase("key0"), 1); + EXPECT_EQ(map4.size(), 1); + EXPECT_EQ(map4.find("key0"), map4.end()); + + map3 = map4; + + EXPECT_EQ(map3.size(), 1); + EXPECT_EQ(map4.size(), 1); + EXPECT_EQ(map4.max_size(), map3.max_size()); + + map4 = std::move(map3); + + EXPECT_EQ(map4.size(), 1); + EXPECT_EQ(map4.at("key1"), 1); +} + +int main(int argc, char **argv) { + FLAGS_logtostderr = true; + google::InitGoogleLogging(argv[0]); + testing::InitGoogleTest(&argc, argv); + google::ParseCommandLineFlags(&argc, &argv, true); + + return RUN_ALL_TESTS(); +} + +// This MUST be the LAST test. +TEST(StringKeyed, memory_balance) { + auto balance = allocated < freed + ? freed - allocated + : allocated - freed; + + LOG(INFO) << "allocated: " << allocated + << " freed: " << freed + << " balance: " << balance + << ( + allocated < freed + ? " negative (huh?)" + : freed < allocated + ? " positive (leak)" : "" + ); + + EXPECT_EQ(allocated, freed); +} -- 2.34.1