This is an automated email from the ASF dual-hosted git repository.
wwbmmm pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/brpc.git
The following commit(s) were added to refs/heads/master by this push:
new 53026cde Small FlatMap optimization with default initialization (#2620)
53026cde is described below
commit 53026cdea1441d5cb67c0ee9c491cda8481a54c4
Author: Bright Chen <[email protected]>
AuthorDate: Mon Dec 9 09:57:38 2024 +0800
Small FlatMap optimization with default initialization (#2620)
* Small FlatMap optimization
* Support optional
---
src/brpc/acceptor.cpp | 7 +-
src/brpc/builtin/hotspots_service.cpp | 1 -
src/brpc/controller.h | 2 -
src/brpc/details/hpack.cpp | 6 +-
src/brpc/details/naming_service_thread.cpp | 4 +-
src/brpc/extension.h | 3 +-
src/brpc/extension_inl.h | 9 -
src/brpc/http_header.cpp | 1 -
src/brpc/kvmap.h | 20 +-
src/brpc/partition_channel.cpp | 4 -
src/brpc/policy/http2_rpc_protocol.cpp | 6 +-
src/brpc/policy/locality_aware_load_balancer.h | 4 +-
src/brpc/policy/rtmp_protocol.cpp | 12 +-
src/brpc/server.cpp | 43 +-
src/brpc/server_id.cpp | 4 +-
src/brpc/uri.cpp | 6 -
src/brpc/uri.h | 1 -
src/bthread/mutex.cpp | 4 +-
src/butil/containers/flat_map.h | 145 ++++--
src/butil/containers/flat_map_inl.h | 447 ++++++++--------
src/butil/containers/optional.h | 560 +++++++++++++++++++++
src/butil/iobuf_profiler.cpp | 9 +-
src/butil/iobuf_profiler.h | 2 +-
src/butil/memory/aligned_memory.h | 2 +-
src/butil/memory/manual_constructor.h | 130 ++---
src/butil/object_pool_inl.h | 22 +-
src/butil/resource_pool_inl.h | 22 +-
src/butil/single_threaded_pool.h | 9 +-
src/butil/type_traits.h | 15 +-
src/bvar/mvariable.cpp | 4 +-
src/bvar/variable.cpp | 5 +-
src/mcpack2pb/mcpack2pb.cpp | 3 +-
test/BUILD.bazel | 3 +-
test/CMakeLists.txt | 4 +-
test/Makefile | 3 +-
test/brpc_controller_unittest.cpp | 2 +-
test/brpc_extension_unittest.cpp | 2 +-
test/brpc_http_message_unittest.cpp | 18 +-
test/flat_map_unittest.cpp | 236 ++++++---
test/optional_unittest.cpp | 298 +++++++++++
..._guard_unittest.cc => scope_guard_unittest.cpp} | 0
41 files changed, 1502 insertions(+), 576 deletions(-)
diff --git a/src/brpc/acceptor.cpp b/src/brpc/acceptor.cpp
index e8e6dcbe..616c1a30 100644
--- a/src/brpc/acceptor.cpp
+++ b/src/brpc/acceptor.cpp
@@ -165,9 +165,8 @@ void Acceptor::StopAccept(int /*closewait_ms*/) {
int Acceptor::Initialize() {
if (_socket_map.init(INITIAL_CONNECTION_CAP) != 0) {
- LOG(FATAL) << "Fail to initialize FlatMap, size="
+ LOG(WARNING) << "Fail to initialize FlatMap, size="
<< INITIAL_CONNECTION_CAP;
- return -1;
}
return 0;
}
@@ -217,10 +216,6 @@ void Acceptor::ListConnections(std::vector<SocketId>*
conn_list,
conn_list->reserve(ConnectionCount() + 10);
std::unique_lock<butil::Mutex> mu(_map_mutex);
- if (!_socket_map.initialized()) {
- // Optional. Uninitialized FlatMap should be iteratable.
- return;
- }
// Copy all the SocketId (protected by mutex) into a temporary
// container to avoid dealing with sockets inside the mutex.
size_t ntotal = 0;
diff --git a/src/brpc/builtin/hotspots_service.cpp
b/src/brpc/builtin/hotspots_service.cpp
index f714843d..8d4d97bc 100644
--- a/src/brpc/builtin/hotspots_service.cpp
+++ b/src/brpc/builtin/hotspots_service.cpp
@@ -68,7 +68,6 @@ static DisplayType StringToDisplayType(const std::string&
val) {
static std::once_flag flag;
std::call_once(flag, []() {
display_type_map = new butil::CaseIgnoredFlatMap<DisplayType>;
- display_type_map->init(10);
(*display_type_map)["dot"] = DisplayType::kDot;
#if defined(OS_LINUX)
(*display_type_map)["flame"] = DisplayType::kFlameGraph;
diff --git a/src/brpc/controller.h b/src/brpc/controller.h
index 2a4ec6b5..d9799f88 100644
--- a/src/brpc/controller.h
+++ b/src/brpc/controller.h
@@ -266,7 +266,6 @@ public:
UserFieldsMap* request_user_fields() {
if (!_request_user_fields) {
_request_user_fields = new UserFieldsMap;
- _request_user_fields->init(29);
}
return _request_user_fields;
}
@@ -276,7 +275,6 @@ public:
UserFieldsMap* response_user_fields() {
if (!_response_user_fields) {
_response_user_fields = new UserFieldsMap;
- _response_user_fields->init(29);
}
return _response_user_fields;
}
diff --git a/src/brpc/details/hpack.cpp b/src/brpc/details/hpack.cpp
index 559e9c6c..687a6145 100644
--- a/src/brpc/details/hpack.cpp
+++ b/src/brpc/details/hpack.cpp
@@ -241,12 +241,10 @@ int IndexTable::Init(const IndexTableOptions& options) {
_need_indexes = options.need_indexes;
if (_need_indexes) {
if (_name_index.init(num_headers * 2) != 0) {
- LOG(ERROR) << "Fail to init _name_index";
- return -1;
+ LOG(WARNING) << "Fail to init _name_index";
}
if (_header_index.init(num_headers * 2) != 0) {
- LOG(ERROR) << "Fail to init _name_index";
- return -1;
+ LOG(WARNING) << "Fail to init _name_index";
}
}
if (options.static_table_size > 0) {
diff --git a/src/brpc/details/naming_service_thread.cpp
b/src/brpc/details/naming_service_thread.cpp
index 89648e77..4891b3f1 100644
--- a/src/brpc/details/naming_service_thread.cpp
+++ b/src/brpc/details/naming_service_thread.cpp
@@ -441,9 +441,7 @@ int GetNamingServiceThread(
return -1;
}
if (g_nsthread_map->init(64) != 0) {
- mu.unlock();
- LOG(ERROR) << "Fail to init g_nsthread_map";
- return -1;
+ LOG(WARNING) << "Fail to init g_nsthread_map";
}
}
NamingServiceThread*& ptr = (*g_nsthread_map)[key];
diff --git a/src/brpc/extension.h b/src/brpc/extension.h
index 9d6c94bc..7190ac91 100644
--- a/src/brpc/extension.h
+++ b/src/brpc/extension.h
@@ -49,8 +49,7 @@ public:
private:
friend class butil::GetLeakySingleton<Extension<T> >;
- Extension();
- ~Extension();
+ Extension() = default;
butil::CaseIgnoredFlatMap<T*> _instance_map;
butil::Mutex _map_mutex;
};
diff --git a/src/brpc/extension_inl.h b/src/brpc/extension_inl.h
index 8eede30d..8a081c7f 100644
--- a/src/brpc/extension_inl.h
+++ b/src/brpc/extension_inl.h
@@ -29,15 +29,6 @@ Extension<T>* Extension<T>::instance() {
return butil::get_leaky_singleton<Extension<T> >();
}
-template <typename T>
-Extension<T>::Extension() {
- _instance_map.init(29);
-}
-
-template <typename T>
-Extension<T>::~Extension() {
-}
-
template <typename T>
int Extension<T>::Register(const std::string& name, T* instance) {
if (NULL == instance) {
diff --git a/src/brpc/http_header.cpp b/src/brpc/http_header.cpp
index aef40b17..9cc82b7b 100644
--- a/src/brpc/http_header.cpp
+++ b/src/brpc/http_header.cpp
@@ -31,7 +31,6 @@ HttpHeader::HttpHeader()
, _method(HTTP_METHOD_GET)
, _version(1, 1)
, _first_set_cookie(NULL) {
- CHECK_EQ(0, _headers.init(29));
// NOTE: don't forget to clear the field in Clear() as well.
}
diff --git a/src/brpc/kvmap.h b/src/brpc/kvmap.h
index 1fd70412..489ed2e6 100644
--- a/src/brpc/kvmap.h
+++ b/src/brpc/kvmap.h
@@ -39,14 +39,20 @@ public:
// Get value of a key(case-sensitive)
// Return pointer to the value, NULL on not found.
const std::string* Get(const char* key) const { return _entries.seek(key);
}
- const std::string* Get(const std::string& key) const { return
_entries.seek(key); }
+ const std::string* Get(const std::string& key) const {
+ return _entries.seek(key);
+ }
// Set value of a key
- void Set(const std::string& key, const std::string& value) { GetOrAdd(key)
= value; }
- void Set(const std::string& key, const char* value) { GetOrAdd(key) =
value; }
+ void Set(const std::string& key, const std::string& value) {
+ _entries[key] = value;
+ }
+ void Set(const std::string& key, const char* value) { _entries[key] =
value; }
// Convert other types to string as well
template <typename T>
- void Set(const std::string& key, const T& value) { GetOrAdd(key) =
std::to_string(value); }
+ void Set(const std::string& key, const T& value) {
+ _entries[key] = std::to_string(value);
+ }
// Remove a key
void Remove(const char* key) { _entries.erase(key); }
@@ -60,12 +66,6 @@ public:
size_t Count() const { return _entries.size(); }
private:
- std::string& GetOrAdd(const std::string& key) {
- if (!_entries.initialized()) {
- _entries.init(29);
- }
- return _entries[key];
- }
Map _entries;
};
diff --git a/src/brpc/partition_channel.cpp b/src/brpc/partition_channel.cpp
index c15fddd1..f6a37bc2 100644
--- a/src/brpc/partition_channel.cpp
+++ b/src/brpc/partition_channel.cpp
@@ -400,10 +400,6 @@ public:
if (options) {
_options = *options;
}
- if (_part_chan_map.init(32, 70) != 0) {
- LOG(ERROR) << "Fail to init _part_chan_map";
- return -1;
- }
return 0;
}
diff --git a/src/brpc/policy/http2_rpc_protocol.cpp
b/src/brpc/policy/http2_rpc_protocol.cpp
index f9b01206..1fd93bf7 100644
--- a/src/brpc/policy/http2_rpc_protocol.cpp
+++ b/src/brpc/policy/http2_rpc_protocol.cpp
@@ -362,12 +362,10 @@ H2Context::~H2Context() {
int H2Context::Init() {
if (_pending_streams.init(64, 70) != 0) {
- LOG(ERROR) << "Fail to init _pending_streams";
- return -1;
+ LOG(WARNING) << "Fail to init _pending_streams";
}
if (_hpacker.Init(_unack_local_settings.header_table_size) != 0) {
- LOG(ERROR) << "Fail to init _hpacker";
- return -1;
+ LOG(WARNING) << "Fail to init _hpacker";
}
return 0;
}
diff --git a/src/brpc/policy/locality_aware_load_balancer.h
b/src/brpc/policy/locality_aware_load_balancer.h
index f4392f4f..4129a2d5 100644
--- a/src/brpc/policy/locality_aware_load_balancer.h
+++ b/src/brpc/policy/locality_aware_load_balancer.h
@@ -118,7 +118,9 @@ private:
butil::FlatMap<SocketId, size_t> server_map;
Servers() {
- CHECK_EQ(0, server_map.init(1024, 70));
+ if (server_map.init(1024, 70) != 0) {
+ LOG(WARNING) << "Fail to init server_map";
+ }
}
// Add diff to left_weight of all parent nodes of node `index'.
diff --git a/src/brpc/policy/rtmp_protocol.cpp
b/src/brpc/policy/rtmp_protocol.cpp
index 99a3e085..8b251eb2 100644
--- a/src/brpc/policy/rtmp_protocol.cpp
+++ b/src/brpc/policy/rtmp_protocol.cpp
@@ -731,8 +731,12 @@ RtmpContext::RtmpContext(const RtmpClientOptions* copt,
const Server* server)
_service = server->options().rtmp_service;
}
_free_ms_ids.reserve(32);
- CHECK_EQ(0, _mstream_map.init(1024, 70));
- CHECK_EQ(0, _trans_map.init(1024, 70));
+ if (_mstream_map.init(1024, 70) != 0) {
+ LOG(FATAL) << "Fail to initialize _mstream_map";
+ }
+ if (_trans_map.init(1024, 70) != 0) {
+ LOG(FATAL) << "Fail to initialize _trans_map";
+ }
memset(static_cast<void*>(_cstream_ctx), 0, sizeof(_cstream_ctx));
}
@@ -1766,7 +1770,9 @@ static pthread_once_t s_cmd_handlers_init_once =
PTHREAD_ONCE_INIT;
static void InitCommandHandlers() {
// Dispatch commands based on "Command Name".
s_cmd_handlers = new CommandHandlerMap;
- CHECK_EQ(0, s_cmd_handlers->init(64, 70));
+ if (s_cmd_handlers->init(64, 70) != 0) {
+ LOG(WARNING) << "Fail to init s_cmd_handlers";
+ }
(*s_cmd_handlers)[RTMP_AMF0_COMMAND_CONNECT] = &RtmpChunkStream::OnConnect;
(*s_cmd_handlers)[RTMP_AMF0_COMMAND_ON_BW_DONE] =
&RtmpChunkStream::OnBWDone;
(*s_cmd_handlers)[RTMP_AMF0_COMMAND_RESULT] = &RtmpChunkStream::OnResult;
diff --git a/src/brpc/server.cpp b/src/brpc/server.cpp
index 2a5fb119..9ab79fc3 100644
--- a/src/brpc/server.cpp
+++ b/src/brpc/server.cpp
@@ -118,8 +118,6 @@ DEFINE_bool(enable_threads_service, false, "Enable
/threads");
DECLARE_int32(usercode_backup_threads);
DECLARE_bool(usercode_in_pthread);
-const int INITIAL_SERVICE_CAP = 64;
-const int INITIAL_CERT_MAP = 64;
// NOTE: never make s_ncore extern const whose ctor seq against other
// compilation units is undefined.
const int s_ncore = sysconf(_SC_NPROCESSORS_ONLN);
@@ -664,22 +662,6 @@ int Server::InitializeOnce() {
if (_status != UNINITIALIZED) {
return 0;
}
- if (_fullname_service_map.init(INITIAL_SERVICE_CAP) != 0) {
- LOG(ERROR) << "Fail to init _fullname_service_map";
- return -1;
- }
- if (_service_map.init(INITIAL_SERVICE_CAP) != 0) {
- LOG(ERROR) << "Fail to init _service_map";
- return -1;
- }
- if (_method_map.init(INITIAL_SERVICE_CAP * 2) != 0) {
- LOG(ERROR) << "Fail to init _method_map";
- return -1;
- }
- if (_ssl_ctx_map.init(INITIAL_CERT_MAP) != 0) {
- LOG(ERROR) << "Fail to init _ssl_ctx_map";
- return -1;
- }
_status = READY;
return 0;
}
@@ -2030,17 +2012,6 @@ int Server::AddCertificate(const CertInfo& cert) {
}
bool Server::AddCertMapping(CertMaps& bg, const SSLContext& ssl_ctx) {
- if (!bg.cert_map.initialized()
- && bg.cert_map.init(INITIAL_CERT_MAP) != 0) {
- LOG(ERROR) << "Fail to init _cert_map";
- return false;
- }
- if (!bg.wildcard_cert_map.initialized()
- && bg.wildcard_cert_map.init(INITIAL_CERT_MAP) != 0) {
- LOG(ERROR) << "Fail to init _wildcard_cert_map";
- return false;
- }
-
for (size_t i = 0; i < ssl_ctx.filters.size(); ++i) {
const char* hostname = ssl_ctx.filters[i].c_str();
CertMap* cmap = NULL;
@@ -2111,8 +2082,8 @@ int Server::ResetCertificates(const
std::vector<CertInfo>& certs) {
}
SSLContextMap tmp_map;
- if (tmp_map.init(INITIAL_CERT_MAP) != 0) {
- LOG(ERROR) << "Fail to initialize tmp_map";
+ if (tmp_map.init(certs.size() + 1) != 0) {
+ LOG(ERROR) << "Fail to init tmp_map";
return -1;
}
@@ -2156,16 +2127,6 @@ int Server::ResetCertificates(const
std::vector<CertInfo>& certs) {
}
bool Server::ResetCertMappings(CertMaps& bg, const SSLContextMap& ctx_map) {
- if (!bg.cert_map.initialized()
- && bg.cert_map.init(INITIAL_CERT_MAP) != 0) {
- LOG(ERROR) << "Fail to init _cert_map";
- return false;
- }
- if (!bg.wildcard_cert_map.initialized()
- && bg.wildcard_cert_map.init(INITIAL_CERT_MAP) != 0) {
- LOG(ERROR) << "Fail to init _wildcard_cert_map";
- return false;
- }
bg.cert_map.clear();
bg.wildcard_cert_map.clear();
diff --git a/src/brpc/server_id.cpp b/src/brpc/server_id.cpp
index c3a595bd..d745d6c5 100644
--- a/src/brpc/server_id.cpp
+++ b/src/brpc/server_id.cpp
@@ -23,7 +23,9 @@ namespace brpc {
ServerId2SocketIdMapper::ServerId2SocketIdMapper() {
_tmp.reserve(128);
- CHECK_EQ(0, _nref_map.init(128));
+ if (_nref_map.init(128) != 0) {
+ LOG(WARNING) << "Fail to init _nref_map";
+ }
}
ServerId2SocketIdMapper::~ServerId2SocketIdMapper() {
diff --git a/src/brpc/uri.cpp b/src/brpc/uri.cpp
index f5d544c1..5391368c 100644
--- a/src/brpc/uri.cpp
+++ b/src/brpc/uri.cpp
@@ -72,9 +72,6 @@ static void ParseQueries(URI::QueryMap& query_map, const
std::string &query) {
}
for (QuerySplitter sp(query.c_str()); sp; ++sp) {
if (!sp.key().empty()) {
- if (!query_map.initialized()) {
- query_map.init(URI::QUERY_MAP_INITIAL_BUCKET);
- }
std::string key(sp.key().data(), sp.key().size());
std::string value(sp.value().data(), sp.value().size());
query_map[key] = value;
@@ -347,9 +344,6 @@ void URI::PrintWithoutHost(std::ostream& os) const {
}
void URI::InitializeQueryMap() const {
- if (!_query_map.initialized()) {
- CHECK_EQ(0, _query_map.init(QUERY_MAP_INITIAL_BUCKET));
- }
ParseQueries(_query_map, _query);
_query_was_modified = false;
_initialized_query_map = true;
diff --git a/src/brpc/uri.h b/src/brpc/uri.h
index 3fbb1548..f8d551ca 100644
--- a/src/brpc/uri.h
+++ b/src/brpc/uri.h
@@ -51,7 +51,6 @@ namespace brpc {
// interpretable as extension
class URI {
public:
- static const size_t QUERY_MAP_INITIAL_BUCKET = 16;
typedef butil::FlatMap<std::string, std::string> QueryMap;
typedef QueryMap::const_iterator QueryIterator;
diff --git a/src/bthread/mutex.cpp b/src/bthread/mutex.cpp
index 451a5c90..bd705806 100644
--- a/src/bthread/mutex.cpp
+++ b/src/bthread/mutex.cpp
@@ -161,7 +161,9 @@ void ContentionProfiler::init_if_needed() {
if (!_init) {
// Already output nanoseconds, always set cycles/second to 1000000000.
_disk_buf.append("--- contention\ncycles/second=1000000000\n");
- CHECK_EQ(0, _dedup_map.init(1024, 60));
+ if (_dedup_map.init(1024, 60) != 0) {
+ LOG(WARNING) << "Fail to initialize dedup_map";
+ }
_init = true;
}
}
diff --git a/src/butil/containers/flat_map.h b/src/butil/containers/flat_map.h
index 955753d2..9ae72db9 100644
--- a/src/butil/containers/flat_map.h
+++ b/src/butil/containers/flat_map.h
@@ -94,6 +94,7 @@
#define BUTIL_FLAT_MAP_H
#include <stdint.h>
+#include <cstddef>
#include <functional>
#include <iostream> // std::ostream
#include <type_traits> // std::aligned_storage
@@ -105,7 +106,7 @@
#include "butil/bit_array.h" // bit_array_*
#include "butil/strings/string_piece.h" // StringPiece
#include "butil/memory/scope_guard.h"
-#include "butil/memory/manual_constructor.h"
+#include "butil/containers/optional.h"
namespace butil {
@@ -121,6 +122,14 @@ struct BucketInfo {
double average_length;
};
+#ifndef BRPC_FLATMAP_DEFAULT_NBUCKET
+#ifdef FLAT_MAP_ROUND_BUCKET_BY_USE_NEXT_PRIME
+#define BRPC_FLATMAP_DEFAULT_NBUCKET 29U
+#else
+#define BRPC_FLATMAP_DEFAULT_NBUCKET 16U
+#endif
+#endif // BRPC_FLATMAP_DEFAULT_NBUCKET
+
// NOTE: Objects stored in FlatMap MUST be copyable.
template <typename _K, typename _T,
// Compute hash code from key.
@@ -144,34 +153,39 @@ public:
_Sparse, SparseFlatMapIterator<FlatMap, value_type>,
FlatMapIterator<FlatMap, value_type> >::type iterator;
typedef typename conditional<
- _Sparse, SparseFlatMapIterator<FlatMap, const value_type>,
+ _Sparse, SparseFlatMapIterator<FlatMap, const value_type>,
FlatMapIterator<FlatMap, const value_type> >::type const_iterator;
typedef _Hash hasher;
typedef _Equal key_equal;
+ static constexpr size_t DEFAULT_NBUCKET = BRPC_FLATMAP_DEFAULT_NBUCKET;
+
struct PositionHint {
size_t nbucket;
size_t offset;
bool at_entry;
key_type key;
};
-
+
explicit FlatMap(const hasher& hashfn = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& alloc = allocator_type());
- ~FlatMap();
FlatMap(const FlatMap& rhs);
+ ~FlatMap();
+
FlatMap& operator=(const FlatMap& rhs);
void swap(FlatMap & rhs);
- // Must be called to initialize this map, otherwise insert/operator[]
- // crashes, and seek/erase fails.
- // `nbucket' is the initial number of buckets. `load_factor' is the
+ // FlatMap will be automatically initialized with small FlatMap
optimization,
+ // so this function only needs to be call when a large initial number of
+ // buckets or non-default `load_factor' is required.
+ // Returns 0 on success, -1 on error, but FlatMap can still be used
normally.
+ // `nbucket' is the initial number of buckets. `load_factor' is the
// maximum value of size()*100/nbucket, if the value is reached, nbucket
// will be doubled and all items stored will be rehashed which is costly.
// Choosing proper values for these 2 parameters reduces costs.
int init(size_t nbucket, u_int load_factor = 80);
-
- // Insert a pair of |key| and |value|. If size()*100/bucket_count() is
+
+ // Insert a pair of |key| and |value|. If size()*100/bucket_count() is
// more than load_factor(), a resize() will be done.
// Returns address of the inserted value, NULL on error.
mapped_type* insert(const key_type& key, const mapped_type& value);
@@ -198,7 +212,7 @@ public:
// Remove all items and return all allocated spaces to system.
void clear_and_reset_pool();
-
+
// Search for the value associated with |key|.
// If `_Multi=false', Search for any of multiple values associated with
|key|.
// Returns: address of the value.
@@ -217,7 +231,7 @@ public:
// insert() or operator[] if there're too many items.
// Returns successful or not.
bool resize(size_t nbucket);
-
+
// Iterators
iterator begin();
iterator end();
@@ -254,7 +268,7 @@ public:
void save_iterator(const const_iterator&, PositionHint*) const;
const_iterator restore_iterator(const PositionHint&) const;
- // True if init() was successfully called.
+ // Always returns true.
bool initialized() const { return _buckets != NULL; }
bool empty() const { return _size == 0; }
@@ -266,30 +280,42 @@ public:
BucketInfo bucket_info() const;
struct Bucket {
+ Bucket() : next((Bucket*)-1UL) {}
explicit Bucket(const _K& k) : next(NULL) {
- element_.Init(k);
+ element_space_.Init(k);
}
Bucket(const Bucket& other) : next(NULL) {
- element_.Init(other.element());
+ element_space_.Init(other.element());
}
bool is_valid() const { return next != (const Bucket*)-1UL; }
void set_invalid() { next = (Bucket*)-1UL; }
// NOTE: Only be called when is_valid() is true.
- Element& element() {
- return *element_;
- }
- const Element& element() const {
- return *element_;
+ Element& element() { return *element_space_; }
+ const Element& element() const { return *element_space_; }
+ void destroy_element() { element_space_.Destroy(); }
+
+ void swap(Bucket& rhs) {
+ if (!is_valid() && !rhs.is_valid()) {
+ return;
+ } else if (is_valid() && !rhs.is_valid()) {
+ rhs.element_space_.Init(std::move(element()));
+ destroy_element();
+ } else if (!is_valid() && rhs.is_valid()) {
+ element_space_.Init(std::move(rhs.element()));
+ rhs.destroy_element();
+ } else {
+ element().swap(rhs.element());
+ }
+ std::swap(next, rhs.next);
}
- Bucket *next;
+
+ Bucket* next;
private:
- ManualConstructor<Element> element_;
+ ManualConstructor<Element> element_space_;
};
- allocator_type& get_allocator() { return _pool.get_allocator(); }
-
private:
template <typename _Map, typename _Element> friend class FlatMapIterator;
template <typename _Map, typename _Element> friend class SparseFlatMapIterator;
@@ -299,12 +325,13 @@ template <typename _Map, typename _Element> friend class
SparseFlatMapIterator;
: buckets(NULL), thumbnail(NULL), nbucket(0) {}
NewBucketsInfo(Bucket* b, uint64_t* t, size_t n)
: buckets(b), thumbnail(t), nbucket(n) {}
+
Bucket* buckets;
uint64_t* thumbnail;
size_t nbucket;
};
- NewBucketsInfo new_buckets_and_thumbnail(size_t size, size_t new_nbucket);
+ optional<NewBucketsInfo> new_buckets_and_thumbnail(size_t size, size_t
new_nbucket);
// For `_Multi=true'.
// Insert a new default-constructed associated with |key| always.
@@ -314,6 +341,9 @@ template <typename _Map, typename _Element> friend class
SparseFlatMapIterator;
template<bool Multi = _Multi>
typename std::enable_if<Multi, mapped_type&>::type operator[](const
key_type& key);
+ allocator_type& get_allocator() { return _pool.get_allocator(); }
+ allocator_type get_allocator() const { return _pool.get_allocator(); }
+
// True if buckets need to be resized before holding `size' elements.
bool is_too_crowded(size_t size) const {
return is_too_crowded(size, _nbucket, _load_factor);
@@ -322,8 +352,21 @@ template <typename _Map, typename _Element> friend class
SparseFlatMapIterator;
return size * 100 >= nbucket * load_factor;
}
- static void init_buckets_and_thumbnail(
- Bucket* buckets, uint64_t* thumbnail, size_t nbucket) {
+ void init_load_factor(u_int load_factor) {
+ if (_is_default_load_factor) {
+ _is_default_load_factor = false;
+ _load_factor = load_factor;
+ }
+ }
+
+ // True if using default buckets.
+ bool is_default_buckets() const {
+ return _buckets == (Bucket*)(&_default_buckets);
+ }
+
+ static void init_buckets_and_thumbnail(Bucket* buckets,
+ uint64_t* thumbnail,
+ size_t nbucket) {
for (size_t i = 0; i < nbucket; ++i) {
buckets[i].set_invalid();
}
@@ -332,12 +375,18 @@ template <typename _Map, typename _Element> friend class
SparseFlatMapIterator;
bit_array_clear(thumbnail, nbucket);
}
}
-
+
+ static const size_t default_nthumbnail = BIT_ARRAY_LEN(DEFAULT_NBUCKET);
+ // Note: need an extra bucket to let iterator know where buckets end.
+ // Small map optimization.
+ Bucket _default_buckets[DEFAULT_NBUCKET + 1];
+ uint64_t _default_thumbnail[default_nthumbnail];
size_t _size;
size_t _nbucket;
Bucket* _buckets;
uint64_t* _thumbnail;
u_int _load_factor;
+ bool _is_default_load_factor;
hasher _hashfn;
key_equal _eql;
SingleThreadedPool<sizeof(Bucket), 1024, 16, allocator_type> _pool;
@@ -348,7 +397,8 @@ template <typename _K, typename _T,
typename _Equal = DefaultEqualTo<_K>,
bool _Sparse = false,
typename _Alloc = PtAllocator>
-using MultiFlatMap = FlatMap<_K, _T, _Hash, _Equal, _Sparse, _Alloc, true>;
+using MultiFlatMap = FlatMap<
+ _K, _T, _Hash, _Equal, _Sparse, _Alloc, true>;
template <typename _K,
typename _Hash = DefaultHasher<_K>,
@@ -357,7 +407,8 @@ template <typename _K,
typename _Alloc = PtAllocator>
class FlatSet {
public:
- typedef FlatMap<_K, FlatMapVoid, _Hash, _Equal, _Sparse, _Alloc> Map;
+ typedef FlatMap<_K, FlatMapVoid, _Hash, _Equal, _Sparse,
+ _Alloc, false> Map;
typedef typename Map::key_type key_type;
typedef typename Map::value_type value_type;
typedef typename Map::Bucket Bucket;
@@ -408,15 +459,18 @@ private:
template <typename _K, typename _T,
typename _Hash = DefaultHasher<_K>,
- typename _Equal = DefaultEqualTo<_K> >
-class SparseFlatMap : public FlatMap<_K, _T, _Hash, _Equal, true> {
-};
+ typename _Equal = DefaultEqualTo<_K>,
+ typename _Alloc = PtAllocator,
+ bool _Multi = false>
+class SparseFlatMap : public FlatMap<
+ _K, _T, _Hash, _Equal, true, _Alloc, _Multi> {};
template <typename _K,
typename _Hash = DefaultHasher<_K>,
- typename _Equal = DefaultEqualTo<_K> >
-class SparseFlatSet : public FlatSet<_K, _Hash, _Equal, true> {
-};
+ typename _Equal = DefaultEqualTo<_K>,
+ typename _Alloc = PtAllocator>
+class SparseFlatSet : public FlatSet<
+ _K, _Hash, _Equal, true, _Alloc> {};
// Implement FlatMapElement
template <typename K, typename T>
@@ -431,6 +485,13 @@ public:
// POD) which is wrong generally.
explicit FlatMapElement(const K& k) : _key(k), _value(T()) {}
// ^^^^^^^^^^^
+
+ FlatMapElement(const FlatMapElement& rhs)
+ : _key(rhs._key), _value(rhs._value) {}
+
+ FlatMapElement(FlatMapElement&& rhs) noexcept
+ : _key(std::move(rhs._key)), _value(std::move(rhs._value)) {}
+
const K& first_ref() const { return _key; }
T& second_ref() { return _value; }
T&& second_movable_ref() { return std::move(_value); }
@@ -442,8 +503,13 @@ public:
inline static T&& second_movable_ref_from_value(value_type& v)
{ return std::move(v.second); }
+ void swap(FlatMapElement& rhs) {
+ std::swap(_key, rhs._key);
+ std::swap(_value, rhs._value);
+ }
+
private:
- const K _key;
+ K _key;
T _value;
};
@@ -451,7 +517,11 @@ template <typename K>
class FlatMapElement<K, FlatMapVoid> {
public:
typedef const K value_type;
+ // See the comment in the above FlatMapElement.
explicit FlatMapElement(const K& k) : _key(k) {}
+ FlatMapElement(const FlatMapElement& rhs) : _key(rhs._key) {}
+ FlatMapElement(FlatMapElement&& rhs) noexcept : _key(std::move(rhs._key))
{}
+
const K& first_ref() const { return _key; }
FlatMapVoid& second_ref() { return second_ref_from_value(_key); }
FlatMapVoid& second_movable_ref() { return second_ref(); }
@@ -470,8 +540,7 @@ private:
// Implement DefaultHasher and DefaultEqualTo
template <typename K>
-struct DefaultHasher : public BUTIL_HASH_NAMESPACE::hash<K> {
-};
+struct DefaultHasher : public BUTIL_HASH_NAMESPACE::hash<K> {};
template <>
struct DefaultHasher<std::string> {
diff --git a/src/butil/containers/flat_map_inl.h
b/src/butil/containers/flat_map_inl.h
index f37baba1..3b82b9ec 100644
--- a/src/butil/containers/flat_map_inl.h
+++ b/src/butil/containers/flat_map_inl.h
@@ -90,17 +90,12 @@ public:
FlatMapIterator() : _node(NULL), _entry(NULL) {}
FlatMapIterator(const Map* map, size_t pos) {
- if (map->initialized()) {
- _entry = map->_buckets + pos;
- find_and_set_valid_node();
- } else {
- _node = NULL;
- _entry = NULL;
- }
+ _entry = map->_buckets + pos;
+ find_and_set_valid_node();
}
FlatMapIterator(const FlatMapIterator<Map, NonConstValue>& rhs)
: _node(rhs._node), _entry(rhs._entry) {}
- ~FlatMapIterator() {} // required by style-checker
+ ~FlatMapIterator() = default; // required by style-checker
// *this == rhs
bool operator==(const FlatMapIterator& rhs) const
@@ -163,20 +158,14 @@ public:
SparseFlatMapIterator() : _node(NULL), _pos(0), _map(NULL) {}
SparseFlatMapIterator(const Map* map, size_t pos) {
- if (map->initialized()) {
- _map = map;
- _pos = pos;
- find_and_set_valid_node();
- } else {
- _node = NULL;
- _map = NULL;
- _pos = 0;
- }
+ _map = map;
+ _pos = pos;
+ find_and_set_valid_node();
}
SparseFlatMapIterator(const SparseFlatMapIterator<Map, NonConstValue>& rhs)
: _node(rhs._node), _pos(rhs._pos), _map(rhs._map)
{}
- ~SparseFlatMapIterator() {} // required by style-checker
+ ~SparseFlatMapIterator() = default; // required by style-checker
// *this == rhs
bool operator==(const SparseFlatMapIterator& rhs) const
@@ -223,90 +212,85 @@ friend class SparseFlatMapIterator<Map, ConstValue>;
size_t _pos;
const Map* _map;
};
-
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A, bool _M>
-FlatMap<_K, _T, _H, _E, _S, _A, _M>::FlatMap(const hasher& hashfn, const
key_equal& eql, const allocator_type& alloc)
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
+FlatMap<_K, _T, _H, _E, _S, _A, _M>::FlatMap(const hasher& hashfn,
+ const key_equal& eql,
+ const allocator_type& alloc)
: _size(0)
- , _nbucket(0)
- , _buckets(NULL)
- , _thumbnail(NULL)
- , _load_factor(0)
+ , _nbucket(DEFAULT_NBUCKET)
+ , _buckets((Bucket*)(&_default_buckets))
+ , _thumbnail(_S ? _default_thumbnail : NULL)
+ , _load_factor(80)
+ , _is_default_load_factor(true)
, _hashfn(hashfn)
, _eql(eql)
- , _pool(alloc)
-{}
+ , _pool(alloc) {
+ init_buckets_and_thumbnail(_buckets, _thumbnail, _nbucket);
+}
+
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
+FlatMap<_K, _T, _H, _E, _S, _A, _M>::FlatMap(const FlatMap& rhs)
+ : FlatMap(rhs._hashfn, rhs._eql, rhs.get_allocator()) {
+ init_buckets_and_thumbnail(_buckets, _thumbnail, _nbucket);
+ if (!rhs.empty()) {
+ operator=(rhs);
+ }
+}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A, bool _M>
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
FlatMap<_K, _T, _H, _E, _S, _A, _M>::~FlatMap() {
clear();
- get_allocator().Free(_buckets);
- _buckets = NULL;
- bit_array_free(_thumbnail);
- _thumbnail = NULL;
+ if (!is_default_buckets()) {
+ get_allocator().Free(_buckets);
+ _buckets = NULL;
+ bit_array_free(_thumbnail);
+ _thumbnail = NULL;
+ }
_nbucket = 0;
_load_factor = 0;
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A, bool _M>
-FlatMap<_K, _T, _H, _E, _S, _A, _M>::FlatMap(const FlatMap& rhs)
- : _size(0)
- , _nbucket(0)
- , _buckets(NULL)
- , _thumbnail(NULL)
- , _load_factor(rhs._load_factor)
- , _hashfn(rhs._hashfn)
- , _eql(rhs._eql) {
- operator=(rhs);
-}
-
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A, bool _M>
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
FlatMap<_K, _T, _H, _E, _S, _A, _M>&
-FlatMap<_K, _T, _H, _E, _S, _A, _M>::operator=(const FlatMap<_K, _T, _H, _E,
_S, _A, _M>& rhs) {
+FlatMap<_K, _T, _H, _E, _S, _A, _M>::operator=(
+ const FlatMap<_K, _T, _H, _E, _S, _A, _M>& rhs) {
if (this == &rhs) {
return *this;
}
- // NOTE: assignment does not change _load_factor/_hashfn/_eql if |this| is
- // initialized
+
clear();
- if (!rhs.initialized()) {
+ if (rhs.empty()) {
return *this;
}
- _load_factor = rhs._load_factor;
- if (_buckets == NULL || is_too_crowded(rhs._size)) {
- NewBucketsInfo info = new_buckets_and_thumbnail(_size, rhs._nbucket);
- if (0 == info.nbucket) {
- LOG(ERROR) << "Invalid nbucket=0";
- return *this;
- }
- if (NULL == info.buckets) {
- LOG(ERROR) << "Fail to new buckets";
- return *this;
- }
- if (_S && NULL == info.thumbnail) {
- LOG(ERROR) << "Fail to new thumbnail";
- return *this;
- }
-
- _nbucket = info.nbucket;
- get_allocator().Free(_buckets);
- _buckets = info.buckets;
- if (_S) {
- bit_array_free(_thumbnail);
- _thumbnail = info.thumbnail;
+ // NOTE: assignment only changes _load_factor when it is default.
+ init_load_factor(rhs._load_factor);
+ if (is_too_crowded(rhs._size)) {
+ optional<NewBucketsInfo> info =
+ new_buckets_and_thumbnail(rhs._size, rhs._nbucket);
+ if (info.has_value()) {
+ _nbucket = info->nbucket;
+ if (!is_default_buckets()) {
+ get_allocator().Free(_buckets);
+ if (_S) {
+ bit_array_free(_thumbnail);
+ }
+ }
+ _buckets = info->buckets;
+ _thumbnail = info->thumbnail;
}
- }
- if (rhs.empty()) {
- // No need to copy, returns directly.
- return *this;
+ // Failed new of buckets or thumbnail is OK.
+ // Use old buckets and thumbnail even if map will be crowded.
}
if (_nbucket == rhs._nbucket) {
// For equivalent _nbucket, walking through _buckets instead of using
// iterators is more efficient.
for (size_t i = 0; i < rhs._nbucket; ++i) {
- if (!rhs._buckets[i].is_valid()) {
- _buckets[i].set_invalid();
- } else {
+ if (rhs._buckets[i].is_valid()) {
if (_S) {
bit_array_set(_thumbnail, i);
}
@@ -331,79 +315,77 @@ FlatMap<_K, _T, _H, _E, _S, _A, _M>::operator=(const
FlatMap<_K, _T, _H, _E, _S,
return *this;
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A, bool _M>
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
int FlatMap<_K, _T, _H, _E, _S, _A, _M>::init(size_t nbucket, u_int
load_factor) {
- if (initialized()) {
- LOG(ERROR) << "Already initialized";
- return -1;
- }
- if (nbucket == 0) {
- LOG(WARNING) << "Fail to init FlatMap, nbucket=" << nbucket;
- return -1;
- }
- if (load_factor < 10 || load_factor > 100) {
- LOG(ERROR) << "Invalid load_factor=" << load_factor;
- return -1;
+ if (nbucket <= _nbucket || load_factor < 10 || load_factor > 100 ||
+ !_is_default_load_factor || !empty() || !is_default_buckets()) {
+ return 0;
}
- _size = 0;
- _load_factor = load_factor;
- NewBucketsInfo info = new_buckets_and_thumbnail(_size, nbucket);
- if (0 == info.nbucket) {
- LOG(ERROR) << "Invalid nbucket=0";
- return -1;
- }
- if (NULL == info.buckets) {
- LOG(ERROR) << "Fail to new buckets";
- return -1;
- }
- if (_S && NULL == info.thumbnail) {
- LOG(ERROR) << "Fail to new thumbnail";
- return -1;
- }
- _nbucket = info.nbucket;
- _buckets = info.buckets;
- if (_S) {
- _thumbnail = info.thumbnail;
- bit_array_clear(_thumbnail, _nbucket);
- }
- return 0;
+ init_load_factor(load_factor);
+ return resize(nbucket) ? 0 : -1;
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A, bool _M>
-void FlatMap<_K, _T, _H, _E, _S, _A, _M>::swap(FlatMap<_K, _T, _H, _E, _S, _A,
_M> & rhs) {
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
+void FlatMap<_K, _T, _H, _E, _S, _A, _M>::swap(
+ FlatMap<_K, _T, _H, _E, _S, _A, _M>& rhs) {
+ if (!is_default_buckets() && !rhs.is_default_buckets()) {
+ std::swap(rhs._buckets, _buckets);
+ std::swap(rhs._thumbnail, _thumbnail);
+ } else {
+ for (size_t i = 0; i < DEFAULT_NBUCKET; ++i) {
+ _default_buckets[i].swap(rhs._default_buckets[i]);
+ }
+ if (_S) {
+ for (size_t i = 0; i < default_nthumbnail; ++i) {
+ std::swap(_default_thumbnail[i], rhs._default_thumbnail[i]);
+ }
+ }
+ if (!is_default_buckets() && rhs.is_default_buckets()) {
+ rhs._buckets = _buckets;
+ rhs._thumbnail = _thumbnail;
+ _buckets = _default_buckets;
+ _thumbnail = _default_thumbnail;
+ } else if (is_default_buckets() && !rhs.is_default_buckets()) {
+ _buckets = rhs._buckets;
+ _thumbnail = rhs._thumbnail;
+ rhs._buckets = rhs._default_buckets;
+ rhs._thumbnail = rhs._thumbnail;
+ } // else both are default buckets which has been swapped, so no need
to swap `_buckets'.
+ }
+
std::swap(rhs._size, _size);
std::swap(rhs._nbucket, _nbucket);
- std::swap(rhs._buckets, _buckets);
- std::swap(rhs._thumbnail, _thumbnail);
+ std::swap(rhs._is_default_load_factor, _is_default_load_factor);
std::swap(rhs._load_factor, _load_factor);
std::swap(rhs._hashfn, _hashfn);
std::swap(rhs._eql, _eql);
rhs._pool.swap(_pool);
}
-template <typename _K, typename _T, typename _H,
- typename _E, bool _S, typename _A, bool _M>
-_T* FlatMap<_K, _T, _H, _E, _S, _A, _M>::insert(const key_type& key,
- const mapped_type& value) {
- mapped_type *p = &operator[]<_M>(key);
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
+_T* FlatMap<_K, _T, _H, _E, _S, _A, _M>::insert(
+ const key_type& key, const mapped_type& value) {
+ mapped_type *p = &operator[](key);
*p = value;
return p;
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A, bool _M>
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
_T* FlatMap<_K, _T, _H, _E, _S, _A, _M>::insert(
const std::pair<key_type, mapped_type>& kv) {
return insert(kv.first, kv.second);
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A, bool _M>
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
template <typename K2, bool Multi>
typename std::enable_if<!Multi, size_t >::type
FlatMap<_K, _T, _H, _E, _S, _A, _M>::erase(const K2& key, _T* old_value) {
- if (!initialized()) {
- return 0;
- }
// TODO: Do we need auto collapsing here?
const size_t index = flatmap_mod(_hashfn(key), _nbucket);
Bucket& first_node = _buckets[index];
@@ -415,7 +397,7 @@ FlatMap<_K, _T, _H, _E, _S, _A, _M>::erase(const K2& key,
_T* old_value) {
*old_value = first_node.element().second_movable_ref();
}
if (first_node.next == NULL) {
- first_node.element().~Element();
+ first_node.destroy_element();
first_node.set_invalid();
if (_S) {
bit_array_unset(_thumbnail, index);
@@ -423,7 +405,7 @@ FlatMap<_K, _T, _H, _E, _S, _A, _M>::erase(const K2& key,
_T* old_value) {
} else {
// A seemingly correct solution is to copy the memory of *p to
// first_node directly like this:
- // first_node.element().~Element();
+ // first_node.destroy_element();
// first_node = *p;
// It works at most of the time, but is wrong generally.
// If _T references self inside like this:
@@ -439,7 +421,7 @@ FlatMap<_K, _T, _H, _E, _S, _A, _M>::erase(const K2& key,
_T* old_value) {
const_cast<_K&>(first_node.element().first_ref()) =
p->element().first_ref();
first_node.element().second_ref() =
p->element().second_movable_ref();
- p->element().~Element();
+ p->destroy_element();
_pool.back(p);
}
--_size;
@@ -453,7 +435,7 @@ FlatMap<_K, _T, _H, _E, _S, _A, _M>::erase(const K2& key,
_T* old_value) {
*old_value = p->element().second_movable_ref();
}
last_p->next = p->next;
- p->element().~Element();
+ p->destroy_element();
_pool.back(p);
--_size;
return 1UL;
@@ -464,14 +446,12 @@ FlatMap<_K, _T, _H, _E, _S, _A, _M>::erase(const K2& key,
_T* old_value) {
return 0;
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A, bool _M>
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
template <typename K2, bool Multi>
typename std::enable_if<Multi, size_t >::type
-FlatMap<_K, _T, _H, _E, _S, _A, _M>::erase(const K2& key,
- std::vector<mapped_type>*
old_values) {
- if (!initialized()) {
- return 0;
- }
+FlatMap<_K, _T, _H, _E, _S, _A, _M>::erase(
+ const K2& key, std::vector<mapped_type>* old_values) {
// TODO: Do we need auto collapsing here?
const size_t index = flatmap_mod(_hashfn(key), _nbucket);
Bucket& first_node = _buckets[index];
@@ -490,7 +470,7 @@ FlatMap<_K, _T, _H, _E, _S, _A, _M>::erase(const K2& key,
}
Bucket* temp = p;
p = p->next;
- temp->element().~Element();
+ temp->destroy_element();
if (temp != &first_node) {
_pool.back(temp);
}
@@ -521,13 +501,14 @@ FlatMap<_K, _T, _H, _E, _S, _A, _M>::erase(const K2& key,
const_cast<_K&>(first_node.element().first_ref()) =
new_head->element().first_ref();
first_node.element().second_ref() =
new_head->element().second_movable_ref();
- new_head->element().~Element();
+ new_head->destroy_element();
_pool.back(new_head);
}
return total - _size;
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A, bool _M>
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
void FlatMap<_K, _T, _H, _E, _S, _A, _M>::clear() {
if (0 == _size) {
return;
@@ -537,11 +518,11 @@ void FlatMap<_K, _T, _H, _E, _S, _A, _M>::clear() {
for (size_t i = 0; i < _nbucket; ++i) {
Bucket& first_node = _buckets[i];
if (first_node.is_valid()) {
- first_node.element().~Element();
+ first_node.destroy_element();
Bucket* p = first_node.next;
while (p) {
Bucket* next_p = p->next;
- p->element().~Element();
+ p->destroy_element();
_pool.back(p);
p = next_p;
}
@@ -554,18 +535,17 @@ void FlatMap<_K, _T, _H, _E, _S, _A, _M>::clear() {
}
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A, bool _M>
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
void FlatMap<_K, _T, _H, _E, _S, _A, _M>::clear_and_reset_pool() {
clear();
_pool.reset();
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A, bool _M>
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
template <typename K2>
_T* FlatMap<_K, _T, _H, _E, _S, _A, _M>::seek(const K2& key) const {
- if (!initialized()) {
- return NULL;
- }
Bucket& first_node = _buckets[flatmap_mod(_hashfn(key), _nbucket)];
if (!first_node.is_valid()) {
return NULL;
@@ -583,13 +563,11 @@ _T* FlatMap<_K, _T, _H, _E, _S, _A, _M>::seek(const K2&
key) const {
return NULL;
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A, bool _M>
-template <typename K2>
-std::vector<_T*> FlatMap<_K, _T, _H, _E, _S, _A, _M>::seek_all(const K2& key)
const {
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
+template <typename K2> std::vector<_T*>
+FlatMap<_K, _T, _H, _E, _S, _A, _M>::seek_all(const K2& key) const {
std::vector<_T*> v;
- if (!initialized()) {
- return v;
- }
Bucket& first_node = _buckets[flatmap_mod(_hashfn(key), _nbucket)];
if (!first_node.is_valid()) {
return v;
@@ -607,12 +585,14 @@ std::vector<_T*> FlatMap<_K, _T, _H, _E, _S, _A,
_M>::seek_all(const K2& key) co
return v;
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A, bool _M>
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
template<bool Multi>
typename std::enable_if<!Multi, _T&>::type
FlatMap<_K, _T, _H, _E, _S, _A, _M>::operator[](const key_type& key) {
const size_t index = flatmap_mod(_hashfn(key), _nbucket);
Bucket& first_node = _buckets[index];
+ // LOG(INFO) << "index=" << index;
if (!first_node.is_valid()) {
++_size;
if (_S) {
@@ -627,12 +607,10 @@ FlatMap<_K, _T, _H, _E, _S, _A, _M>::operator[](const
key_type& key) {
return p->element().second_ref();
}
if (NULL == p->next) {
- if (is_too_crowded(_size)) {
- if (resize(_nbucket + 1)) {
- return operator[](key);
- }
- // fail to resize is OK
+ if (is_too_crowded(_size) && resize(_nbucket + 1)) {
+ return operator[](key);
}
+ // Fail to resize is OK.
++_size;
Bucket* newp = new (_pool.get()) Bucket(key);
p->next = newp;
@@ -642,7 +620,8 @@ FlatMap<_K, _T, _H, _E, _S, _A, _M>::operator[](const
key_type& key) {
}
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A, bool _M>
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
template<bool Multi>
typename std::enable_if<Multi, _T&>::type
FlatMap<_K, _T, _H, _E, _S, _A, _M>::operator[](const key_type& key) {
@@ -671,7 +650,7 @@ FlatMap<_K, _T, _H, _E, _S, _A, _M>::operator[](const
key_type& key) {
if (need_scale && resize(_nbucket + 1)) {
return operator[](key);
}
- // fail to resize is OK
+ // Failed resize is OK.
}
++_size;
Bucket* newp = new (_pool.get()) Bucket(key);
@@ -680,7 +659,8 @@ FlatMap<_K, _T, _H, _E, _S, _A, _M>::operator[](const
key_type& key) {
return newp->element().second_ref();
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A, bool _M>
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
void FlatMap<_K, _T, _H, _E, _S, _A, _M>::save_iterator(
const const_iterator& it, PositionHint* hint) const {
hint->nbucket = _nbucket;
@@ -694,9 +674,11 @@ void FlatMap<_K, _T, _H, _E, _S, _A, _M>::save_iterator(
}
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A, bool _M>
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
typename FlatMap<_K, _T, _H, _E, _S, _A, _M>::const_iterator
-FlatMap<_K, _T, _H, _E, _S, _A, _M>::restore_iterator(const PositionHint&
hint) const {
+FlatMap<_K, _T, _H, _E, _S, _A, _M>::restore_iterator(
+ const PositionHint& hint) const {
if (hint.nbucket != _nbucket) // resized
return begin(); // restart
@@ -728,60 +710,26 @@ FlatMap<_K, _T, _H, _E, _S, _A,
_M>::restore_iterator(const PositionHint& hint)
return const_iterator(this, hint.offset);
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A, bool _M>
-bool FlatMap<_K, _T, _H, _E, _S, _A, _M>::resize(size_t nbucket2) {
- nbucket2 = flatmap_round(nbucket2);
- if (_nbucket == nbucket2) {
- return false;
- }
-
- // NOTE: following functors must be kept after resizing otherwise the
- // internal state is lost.
- FlatMap new_map(_hashfn, _eql, get_allocator());
- if (new_map.init(nbucket2, _load_factor) != 0) {
- LOG(ERROR) << "Fail to init new_map, nbucket=" << nbucket2;
- return false;
- }
- for (iterator it = begin(); it != end(); ++it) {
- new_map[Element::first_ref_from_value(*it)] =
- Element::second_movable_ref_from_value(*it);
- }
- new_map.swap(*this);
- return true;
-}
-
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A, bool _M>
-BucketInfo FlatMap<_K, _T, _H, _E, _S, _A, _M>::bucket_info() const {
- size_t max_n = 0;
- size_t nentry = 0;
- for (size_t i = 0; i < _nbucket; ++i) {
- if (_buckets[i].is_valid()) {
- size_t n = 1;
- for (Bucket* p = _buckets[i].next; p; p = p->next, ++n);
- max_n = std::max(max_n, n);
- ++nentry;
- }
- }
- const BucketInfo info = { max_n, size() / (double)nentry };
- return info;
-}
-
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A, bool _M>
-typename FlatMap<_K, _T, _H, _E, _S, _A, _M>::NewBucketsInfo
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
+optional<typename FlatMap<_K, _T, _H, _E, _S, _A, _M>::NewBucketsInfo>
FlatMap<_K, _T, _H, _E, _S, _A, _M>::new_buckets_and_thumbnail(size_t size,
size_t
new_nbucket) {
do {
new_nbucket = flatmap_round(new_nbucket);
} while (is_too_crowded(size, new_nbucket, _load_factor));
+ if (_nbucket == new_nbucket) {
+ return nullopt;
+ }
// Note: need an extra bucket to let iterator know where buckets end.
- auto buckets = (Bucket*)get_allocator().Alloc(sizeof(Bucket) * (
- new_nbucket + 1/*note*/));
+ auto buckets = (Bucket*)get_allocator().Alloc(
+ sizeof(Bucket) * (new_nbucket + 1/*note*/));
auto guard = MakeScopeGuard([buckets, this]() {
get_allocator().Free(buckets);
});
if (NULL == buckets) {
LOG(FATAL) << "Fail to new Buckets";
- return {};
+ return nullopt;
}
uint64_t* thumbnail = NULL;
@@ -789,13 +737,72 @@ FlatMap<_K, _T, _H, _E, _S, _A,
_M>::new_buckets_and_thumbnail(size_t size,
thumbnail = bit_array_malloc(new_nbucket);
if (NULL == thumbnail) {
LOG(FATAL) << "Fail to new thumbnail";
- return {};
+ return nullopt;
}
}
guard.dismiss();
init_buckets_and_thumbnail(buckets, thumbnail, new_nbucket);
- return { buckets, thumbnail, new_nbucket };
+ return NewBucketsInfo{buckets, thumbnail, new_nbucket};
+}
+
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
+bool FlatMap<_K, _T, _H, _E, _S, _A, _M>::resize(size_t nbucket) {
+ optional<NewBucketsInfo> info = new_buckets_and_thumbnail(_size, nbucket);
+ if (!info.has_value()) {
+ return false;
+ }
+
+ for (iterator it = begin(); it != end(); ++it) {
+ const key_type& key = Element::first_ref_from_value(*it);
+ const size_t index = flatmap_mod(_hashfn(key), info->nbucket);
+ Bucket& first_node = info->buckets[index];
+ if (!first_node.is_valid()) {
+ if (_S) {
+ bit_array_set(info->thumbnail, index);
+ }
+ new (&first_node) Bucket(key);
+ first_node.element().second_ref() =
+ Element::second_movable_ref_from_value(*it);
+ } else {
+ Bucket* newp = new (_pool.get()) Bucket(key);
+ newp->element().second_ref() =
+ Element::second_movable_ref_from_value(*it);
+ newp->next = first_node.next;
+ first_node.next = newp;
+ }
+ }
+ size_t saved_size = _size;
+ clear();
+ if (!is_default_buckets()) {
+ get_allocator().Free(_buckets);
+ if (_S) {
+ bit_array_free(_thumbnail);
+ }
+ }
+ _nbucket = info->nbucket;
+ _buckets = info->buckets;
+ _thumbnail = info->thumbnail;
+ _size = saved_size;
+
+ return true;
+}
+
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
+BucketInfo FlatMap<_K, _T, _H, _E, _S, _A, _M>::bucket_info() const {
+ size_t max_n = 0;
+ size_t nentry = 0;
+ for (size_t i = 0; i < _nbucket; ++i) {
+ if (_buckets[i].is_valid()) {
+ size_t n = 1;
+ for (Bucket* p = _buckets[i].next; p; p = p->next, ++n);
+ max_n = std::max(max_n, n);
+ ++nentry;
+ }
+ }
+ return { max_n, size() / (double)nentry };
}
inline std::ostream& operator<<(std::ostream& os, const BucketInfo& info) {
@@ -803,23 +810,31 @@ inline std::ostream& operator<<(std::ostream& os, const
BucketInfo& info) {
<< " avgb=" << info.average_length << '}';
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A, bool _M>
-typename FlatMap<_K, _T, _H, _E, _S, _A, _M>::iterator FlatMap<_K, _T, _H, _E,
_S, _A, _M>::begin() {
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
+typename FlatMap<_K, _T, _H, _E, _S, _A, _M>::iterator
+FlatMap<_K, _T, _H, _E, _S, _A, _M>::begin() {
return iterator(this, 0);
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A, bool _M>
-typename FlatMap<_K, _T, _H, _E, _S, _A, _M>::iterator FlatMap<_K, _T, _H, _E,
_S, _A, _M>::end() {
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
+typename FlatMap<_K, _T, _H, _E, _S, _A, _M>::iterator
+FlatMap<_K, _T, _H, _E, _S, _A, _M>::end() {
return iterator(this, _nbucket);
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A, bool _M>
-typename FlatMap<_K, _T, _H, _E, _S, _A, _M>::const_iterator FlatMap<_K, _T,
_H, _E, _S, _A, _M>::begin() const {
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
+typename FlatMap<_K, _T, _H, _E, _S, _A, _M>::const_iterator
+FlatMap<_K, _T, _H, _E, _S, _A, _M>::begin() const {
return const_iterator(this, 0);
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A, bool _M>
-typename FlatMap<_K, _T, _H, _E, _S, _A, _M>::const_iterator FlatMap<_K, _T,
_H, _E, _S, _A, _M>::end() const {
+template <typename _K, typename _T, typename _H, typename _E,
+ bool _S, typename _A, bool _M>
+typename FlatMap<_K, _T, _H, _E, _S, _A, _M>::const_iterator
+FlatMap<_K, _T, _H, _E, _S, _A, _M>::end() const {
return const_iterator(this, _nbucket);
}
diff --git a/src/butil/containers/optional.h b/src/butil/containers/optional.h
new file mode 100644
index 00000000..ffa5cb3b
--- /dev/null
+++ b/src/butil/containers/optional.h
@@ -0,0 +1,560 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you 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.
+
+#ifndef BUTIL_OPTIONAL_H
+#define BUTIL_OPTIONAL_H
+
+#include "butil/type_traits.h"
+#include "butil/memory/manual_constructor.h"
+
+// The `optional` for managing an optional contained value,
+// i.e. a value that may or may not be present, is a C++11
+// compatible version of the C++17 `std::optional` abstraction.
+// After C++17, `optional` is an alias for `std::optional`.
+
+#if __cplusplus >= 201703L
+namespace butil {
+using std::in_place_t;
+using std::in_place;
+using std::nullopt_t;
+using std::nullopt;
+using std::bad_optional_access;
+using std::optional;
+using std::make_optional;
+} // namespace butil
+#else
+namespace butil {
+
+// Tag type used to specify in-place construction of `optional'.
+struct in_place_t {};
+
+// Instance used for in-place construction of `optional',
+const in_place_t in_place;
+
+namespace internal {
+ // Tag type used as a constructor parameter type for `nullopt_t'.
+ struct optional_forbidden_t {};
+}
+
+// Used to indicate an optional object that does not contain a value.
+struct nullopt_t {
+ // It must not be default-constructible to avoid ambiguity for `opt = {}'.
+ explicit nullopt_t(internal::optional_forbidden_t) noexcept {}
+};
+
+// Instance to use for the construction of `optional`.
+const nullopt_t nullopt(internal::optional_forbidden_t{});
+
+// Thrown by `optional::value()' when accessing an optional object
+// that does not contain a value.
+class bad_optional_access : public std::exception {
+public:
+ bad_optional_access() = default;
+ ~bad_optional_access() override = default;
+ const char* what() const noexcept override {
+ return "optional has no value";
+ }
+};
+
+template <typename T>
+class optional;
+
+namespace internal {
+
+// Whether `T' is constructible or convertible from `optional<U>'.
+template <typename T, typename U>
+struct is_constructible_from_optional : integral_constant<
+ bool, std::is_constructible<T, optional<U>&>::value ||
+ std::is_constructible<T, optional<U>&&>::value ||
+ std::is_constructible<T, const optional<U>&>::value ||
+ std::is_constructible<T, const optional<U>&&>::value> {};
+
+// Whether `T' is constructible or convertible from `butil::optional<U>'.
+template <typename T, typename U>
+struct is_convertible_from_optional
+ : integral_constant<bool,
+ std::is_convertible<optional<U>&, T>::value ||
+ std::is_convertible<optional<U>&&, T>::value ||
+ std::is_convertible<const optional<U>&, T>::value ||
+ std::is_convertible<const optional<U>&&, T>::value> {};
+
+// Whether `T' is constructible or convertible or assignable from
`optional<U>'.
+template <typename T, typename U>
+struct is_assignable_from_optional
+ : integral_constant<bool,
+ std::is_assignable<T&, optional<U>&>::value ||
+ std::is_assignable<T&, optional<U>&&>::value ||
+ std::is_assignable<T&, const optional<U>&>::value ||
+ std::is_assignable<T&, const optional<U>&&>::value> {};
+
+// Whether `T' is constructible or convertible from `optional<U>'.
+template <typename T, typename U>
+struct is_constructible_convertible_from_optional
+ : integral_constant<bool,
+ is_constructible_from_optional<T, U>::value ||
+ is_convertible_from_optional<T, U>::value> {};
+
+// Whether `T' is constructible or convertible or assignable from
`optional<U>'.
+template <typename T, typename U>
+struct is_constructible_convertible_assignable_from_optional
+ : integral_constant<bool,
+ is_constructible_from_optional<T, U>::value ||
+ is_convertible_from_optional<T, U>::value ||
+ is_assignable_from_optional<T, U>::value> {};
+
+} // namespace internal
+
+template<typename T>
+class optional {
+public:
+ typedef T value_type;
+
+ static_assert(!is_same<typename remove_cvref<value_type>::type,
in_place_t>::value,
+ "Instantiation of optional with in_place_t is ill-formed");
+ static_assert(!is_same<typename remove_cvref<value_type>::type,
nullopt_t>::value,
+ "Instantiation of optional with nullopt_t is ill-formed");
+ static_assert(!is_reference<value_type>::value,
+ "Instantiation of optional with a reference type is
ill-formed");
+ static_assert(std::is_destructible<value_type>::value,
+ "Instantiation of optional with a non-destructible type is
ill-formed");
+ static_assert(!is_array<value_type>::value,
+ "Instantiation of optional with an array type is
ill-formed");
+
+ optional() : _engaged(false) {}
+
+ optional(nullopt_t) : optional() {}
+
+ optional(const optional& rhs) = default;
+
+ optional(optional&& rhs) noexcept = default;
+
+ template <typename U, typename std::enable_if<
+ !std::is_same<T, U>::value &&
+ std::is_constructible<T, const U&>::value &&
+ !internal::is_constructible_convertible_from_optional<T, U>::value &&
+ std::is_convertible<const U&, T>::value, bool>::type = false>
+ optional(const optional<U>& rhs) : _engaged(rhs.has_value()) {
+ if (_engaged) {
+ _storage.Init(*rhs);
+ }
+ }
+
+ template <typename U, typename std::enable_if<
+ !std::is_same<T, U>::value &&
+ std::is_constructible<T, const U&>::value &&
+ !internal::is_constructible_convertible_from_optional<T, U>::value &&
+ !std::is_convertible<const U&, T>::value, bool>::type = false>
+ explicit optional(const optional<U>& rhs) : _engaged(rhs.has_value()) {
+ if (_engaged) {
+ _storage.Init(*rhs);
+ }
+ }
+
+ template <typename U, typename std::enable_if<
+ !std::is_same<T, U>::value &&
+ std::is_constructible<T, U&&>::value &&
+ !internal::is_constructible_convertible_from_optional<T, U>::value &&
+ std::is_convertible<U&&, T>::value, bool>::type = false>
+ optional(optional<U>&& rhs) : _engaged(rhs.has_value()) {
+ if (_engaged) {
+ _storage.Init(std::move(*rhs));
+ rhs.reset();
+ }
+ }
+
+ template <typename U, typename std::enable_if<
+ !std::is_same<T, U>::value &&
+ std::is_constructible<T, U&&>::value &&
+ !internal::is_constructible_convertible_from_optional<T, U>::value &&
+ !std::is_convertible<U&&, T>::value, bool>::type = false>
+ explicit optional(optional<U>&& rhs) : _engaged(rhs.has_value()) {
+ if (_engaged) {
+ _storage.Init(std::move(*rhs));
+ rhs.reset();
+ }
+ }
+
+ optional(const T& value) : _engaged(true) {
+ _storage.Init(value);
+ }
+
+ optional(T&& value) : _engaged(true) {
+ _storage.Init(std::move(value));
+ }
+
+ template <typename... Args,
+ std::enable_if<std::is_constructible<T, Args&&...>::value>* =
nullptr>
+ explicit optional(const in_place_t, Args&&... args) : _engaged(true) {
+ _storage.Init(std::forward<Args>(args)...);
+ }
+
+ template <typename U, typename... Args, typename std::enable_if<
+ std::is_constructible<T, std::initializer_list<U>&,
Args&&...>::value>::type>
+ optional(in_place_t, std::initializer_list<U> il, Args&&... args)
+ : _engaged(true) {
+ _storage.Init(il, std::forward<Args>(args)...);
+ }
+
+ template <typename U = T, typename std::enable_if<
+ !std::is_same<in_place_t, typename std::decay<U>::type>::value &&
+ !std::is_same<optional<T>, typename std::decay<U>::type>::value &&
+ std::is_constructible<T, U&&>::value &&
+ std::is_convertible<U&&, T>::value, bool>::type = false>
+ optional(U&& v) : _engaged(true) {
+ _storage.Init(std::forward<U>(v));
+ }
+
+ template <typename U = T, typename std::enable_if<
+ !std::is_same<in_place_t, typename std::decay<U>::type>::value &&
+ !std::is_same<optional<T>, typename std::decay<U>::type>::value &&
+ std::is_constructible<T, U&&>::value &&
+ !std::is_convertible<U&&, T>::value, bool>::type = false>
+ explicit optional(U&& v) : _engaged(true) {
+ _storage.Init(std::forward<U>(v));
+ }
+
+ ~optional() {
+ reset();
+ }
+
+ optional& operator=(nullopt_t) noexcept {
+ reset();
+ return *this;
+ }
+
+ optional& operator=(const optional& rhs) = default;
+
+ optional& operator=(optional&& rhs) = default;
+
+ // Value assignment operators
+ template <typename U = T, typename = typename std::enable_if<
+ !std::is_same<optional<T>, typename std::decay<U>::type>::value &&
+ !std::is_same<optional<T>, typename remove_cvref<U>::type>::value &&
+ std::is_constructible<T, U>::value && std::is_assignable<T&, U>::value
&&
+ (!std::is_scalar<T>::value || !std::is_same<T, typename
std::decay<U>::type>::value)>::type>
+ optional& operator=(U&& v) {
+ reset();
+ _storage.Init(std::forward<U>(v));
+ _engaged = true;
+ return *this;
+ }
+
+ template <typename U, typename = typename std::enable_if<
+ !std::is_same<T, U>::value &&
+ !internal::is_constructible_convertible_assignable_from_optional<T,
U>::value &&
+ std::is_constructible<T, const U&>::value &&
+ std::is_assignable<T&, const U&>::value>::type>
+ optional& operator=(const optional<U>& rhs) {
+ if (rhs) {
+ operator=(*rhs);
+ } else {
+ reset();
+ }
+ return *this;
+ }
+
+ template <typename U, typename = typename std::enable_if<
+ !std::is_same<T, U>::value &&
+ !internal::is_constructible_convertible_assignable_from_optional<T,
U>::value &&
+ std::is_constructible<T, U>::value &&
+ std::is_assignable<T&, U>::value>::type>
+ optional& operator=(optional<U>&& rhs) {
+ if (rhs) {
+ operator=(std::move(*rhs));
+ } else {
+ reset();
+ }
+ return *this;
+ }
+
+ // Accesses the contained value.
+ T& operator*() {
+ if (!_engaged) {
+ throw bad_optional_access();
+ }
+ return *_storage;
+ }
+ const T& operator*() const {
+ if (!_engaged) {
+ throw bad_optional_access();
+ }
+ return *_storage;
+ }
+ T* operator->() {
+ return _storage.get();
+ }
+ const T* operator->() const {
+ return _storage.get();
+ }
+
+ explicit operator bool() const { return _engaged; }
+
+ bool has_value() const { return _engaged; }
+
+ // Returns the contained value if the `optional` is not empty,
+ // otherwise throws `bad_optional_access`.
+ const T& value() const & {
+ if (!_engaged) {
+ throw bad_optional_access();
+ }
+
+ return *_storage;
+ }
+ T& value() & {
+ if (!_engaged) {
+ throw bad_optional_access();
+ }
+
+ return *_storage;
+ }
+ T&& value() && {
+ if (!_engaged) {
+ throw bad_optional_access();
+ }
+
+ return std::move(*_storage);
+ }
+ const T&& value() const && {
+ if (!_engaged) {
+ throw bad_optional_access();
+ }
+
+ return std::move(*_storage);
+ }
+
+ // Returns the contained value if the `optional` is not empty,
+ // otherwise returns default `v'.
+ template <typename U>
+ constexpr T value_or(U&& v) const& {
+ static_assert(std::is_copy_constructible<value_type>::value,
+ "T can not be copy constructible");
+ static_assert(std::is_convertible<U&&, value_type>::value,
+ "U can not be convertible to T");
+
+ return static_cast<bool>(*this) ? **this :
static_cast<T>(std::forward<U>(v));
+ }
+ template <typename U>
+ T value_or(U&& v) && {
+ static_assert(std::is_move_constructible<value_type>::value,
+ "T can not be move constructible");
+ static_assert(std::is_convertible<U&&, value_type>::value,
+ "U can not be convertible to T");
+
+ return static_cast<bool>(*this) ?
+ std::move(**this) : static_cast<T>(std::forward<U>(v));
+ }
+
+ void swap(optional& rhs) noexcept {
+ if (_engaged && rhs._engaged) {
+ std::swap(**this, *rhs);
+ } else if (_engaged) {
+ rhs = std::move(*this);
+ reset();
+ } else if (rhs._engaged) {
+ *this = std::move(rhs);
+ rhs.reset();
+ }
+ }
+
+ // Destroys any contained value if the `optional` is not empty.
+ void reset() {
+ if (_engaged) {
+ _storage.Destroy();
+ _engaged = false;
+ }
+ }
+
+ // Constructs the contained value in-place.
+ // Return a reference to the new contained value.
+ template <typename... Args>
+ T& emplace(Args&&... args) {
+ static_assert(std::is_constructible<T, Args&&...>::value,
+ "T can not be constructible with these arguments");
+ reset();
+ _storage.Init(std::forward<Args>(args)...);
+ _engaged = true;
+ return *_storage;
+ }
+ template <typename U, typename... Args>
+ T& emplace(std::initializer_list<U> il, Args&&... args) {
+ static_assert(std::is_constructible<T, std::initializer_list<U>&,
Args&&...>::value,
+ "T can not be constructible with these arguments");
+
+ return emplace(il, std::forward<Args>(args)...);
+ }
+
+private:
+ bool _engaged;
+ ManualConstructor<T> _storage;
+};
+
+template <typename T>
+void swap(optional<T>& a, optional<T>& b) noexcept { a.swap(b); }
+
+// Creates a non-empty 'optional<T>`.
+template <typename T>
+optional<typename std::decay<T>::type> make_optional(T&& v) {
+ return optional<typename std::decay<T>::type>(std::forward<T>(v));
+}
+
+template <typename T, typename... Args>
+optional<T> make_optional(Args&&... args) {
+ return optional<T>(in_place, std::forward<Args>(args)...);
+}
+
+template <typename T, typename U, typename... Args>
+optional<T> make_optional(std::initializer_list<U> il, Args&&... args) {
+ return optional<T>(in_place, il, std::forward<Args>(args)...);
+}
+
+// Compares optional objects.
+// Supports comparisons between 'optional<T>` and 'optional<U>`,
+// between 'optional<T>` and `U', and between 'optional<T>` and `nullopt'.
+// Empty optionals are considered equal to each other and less than non-empty
optionals.
+template <typename T, typename U>
+bool operator==(const optional<T>& x, const optional<U>& y) {
+ return static_cast<bool>(x) != static_cast<bool>(y)
+ ? false : static_cast<bool>(x) == false ? true : *x == *y;
+}
+
+template <typename T, typename U>
+bool operator!=(const optional<T>& x, const optional<U>& y) {
+ return !(x == y);
+}
+
+template <typename T, typename U>
+bool operator<=(const optional<T>& x, const optional<U>& y) {
+ return !x ? true : !y ? false : *x <= *y;
+}
+
+template <typename T, typename U>
+bool operator>=(const optional<T>& x, const optional<U>& y) {
+ return !y ? true : !x ? false : *x >= *y;
+}
+
+template <typename T, typename U>
+bool operator<(const optional<T>& x, const optional<U>& y) {
+ return !(x >= y);
+}
+
+template <typename T, typename U>
+bool operator>(const optional<T>& x, const optional<U>& y) {
+ return !(x <= y);
+}
+
+template <typename T>
+bool operator==(const optional<T>& x, nullopt_t) { return !x; }
+
+template <typename T>
+bool operator==(nullopt_t, const optional<T>& x) { return !x; }
+
+template <typename T>
+bool operator!=(const optional<T>& x, nullopt_t) { return
static_cast<bool>(x); }
+
+template <typename T>
+bool operator!=(nullopt_t, const optional<T>& x) { return
static_cast<bool>(x);}
+
+template <typename T>
+bool operator<(const optional<T>&, nullopt_t) { return false; }
+
+template <typename T>
+bool operator<(nullopt_t, const optional<T>& x) { return static_cast<bool>(x);
}
+
+template <typename T>
+bool operator<=(const optional<T>& x, nullopt_t) { return !x; }
+
+template <typename T>
+bool operator<=(nullopt_t, const optional<T>&) { return true; }
+
+template <typename T>
+bool operator>(const optional<T>& x, nullopt_t) { return static_cast<bool>(x);
}
+
+template <typename T>
+bool operator>(nullopt_t, const optional<T>&) { return false; }
+
+template <typename T>
+bool operator>=(const optional<T>&, nullopt_t) { return true; }
+template <typename T>
+bool operator>=(nullopt_t, const optional<T>& x) { return !x; }
+
+template <typename T, typename U>
+bool operator==(const optional<T>& x, const U& v) {
+ return x ? *x == v : false;
+}
+template <typename T, typename U>
+bool operator==(const U& v, const optional<T>& x) {
+ return x == v;
+}
+template <typename T, typename U>
+bool operator!=(const optional<T>& x, const U& v) {
+ return x ? *x != v : true;
+}
+template <typename T, typename U>
+bool operator!=(const U& v, const optional<T>& x) {
+ return x != v;
+}
+
+template <typename T, typename U>
+bool operator<=(const optional<T>& x, const U& v) {
+ return x ? *x <= v : true;
+}
+template <typename T, typename U>
+bool operator<=(const U& v, const optional<T>& x) {
+ return x ? v <= *x : false;
+}
+template <typename T, typename U>
+bool operator<(const optional<T>& x, const U& v) {
+ return !(x >= v);
+}
+template <typename T, typename U>
+bool operator<(const U& v, const optional<T>& x) {
+ return !(v >= x);
+}
+
+template <typename T, typename U>
+bool operator>=(const optional<T>& x, const U& v) {
+ return x ? *x >= v : false;
+}
+template <typename T, typename U>
+bool operator>=(const U& v, const optional<T>& x) {
+ return x ? v >= *x : true;
+}
+
+template <typename T, typename U>
+bool operator>(const optional<T>& x, const U& v) {
+ return !(x <= v);
+}
+template <typename T, typename U>
+bool operator>(const U& v, const optional<T>& x) {
+ return !(v <= x);
+}
+
+} // namespace butil
+
+namespace std {
+template <typename T>
+struct hash<butil::optional<T>> {
+ std::size_t operator()(const butil::optional<T>& opt) const {
+ return hash<T>()(opt.value_or(T()));
+ }
+};
+
+} // namespace std
+
+#endif // __cplusplus >= 201703L
+
+#endif // BUTIL_OPTIONAL_H
diff --git a/src/butil/iobuf_profiler.cpp b/src/butil/iobuf_profiler.cpp
index 11353beb..8d213a72 100644
--- a/src/butil/iobuf_profiler.cpp
+++ b/src/butil/iobuf_profiler.cpp
@@ -99,8 +99,12 @@ IOBufProfiler::IOBufProfiler()
: butil::SimpleThread("IOBufProfiler")
, _stop(false)
, _sleep_ms(MIN_SLEEP_MS) {
- CHECK_EQ(0, _stack_map.init(1024));
- CHECK_EQ(0, _block_info_map.init(1024));
+ if (_stack_map.init(1024) != 0) {
+ LOG(WARNING) << "Fail to init _stack_map";
+ }
+ if (_block_info_map.init(1024) != 0) {
+ LOG(WARNING) << "Fail to init _block_info_map";
+ }
Start();
}
@@ -161,7 +165,6 @@ void IOBufProfiler::Dump(IOBufSample* s) {
} else {
BlockInfo& new_info = _block_info_map[s->block];
new_info.ref += s->count;
- CHECK_EQ(0, new_info.stack_count_map.init(64));
new_info.stack_count_map[*stack_ptr] = s->count;
}
} while (false);
diff --git a/src/butil/iobuf_profiler.h b/src/butil/iobuf_profiler.h
index 7178f20a..4686886f 100644
--- a/src/butil/iobuf_profiler.h
+++ b/src/butil/iobuf_profiler.h
@@ -54,7 +54,7 @@ struct IOBufSample {
size_t stack_hash_code() const;
private:
- friend ObjectPool<IOBufSample>;
+friend ObjectPool<IOBufSample>;
IOBufSample()
: next(NULL)
diff --git a/src/butil/memory/aligned_memory.h
b/src/butil/memory/aligned_memory.h
index c6aaaeef..fbc24612 100644
--- a/src/butil/memory/aligned_memory.h
+++ b/src/butil/memory/aligned_memory.h
@@ -54,7 +54,7 @@ struct AlignedMemory {};
// std::aligned_storage has been deprecated in C++23,
// because aligned_* are harmful to codebases and should not be used.
// For details, see
https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p1413r3.pdf
-#if (__cplusplus >= 201103L)
+#if __cplusplus >= 201103L
// In most places, use the C++11 keyword "alignas", which is preferred.
#define DECL_ALIGNED_BUFFER(buffer_name, byte_alignment, size) \
alignas(byte_alignment) uint8_t buffer_name[size]
diff --git a/src/butil/memory/manual_constructor.h
b/src/butil/memory/manual_constructor.h
index 266f6cca..111d5ece 100644
--- a/src/butil/memory/manual_constructor.h
+++ b/src/butil/memory/manual_constructor.h
@@ -24,104 +24,52 @@ namespace butil {
template <typename Type>
class ManualConstructor {
- public:
- // No constructor or destructor because one of the most useful uses of
- // this class is as part of a union, and members of a union cannot have
- // constructors or destructors. And, anyway, the whole point of this
- // class is to bypass these.
-
- // Support users creating arrays of ManualConstructor<>s. This ensures that
- // the array itself has the correct alignment.
- static void* operator new[](size_t size) {
+public:
+ // No constructor or destructor because one of the most useful uses of
+ // this class is as part of a union, and members of a union cannot have
+ // constructors or destructors. And, anyway, the whole point of this
+ // class is to bypass these.
+
+ // Support users creating arrays of ManualConstructor<>s. This ensures
that
+ // the array itself has the correct alignment.
+ static void* operator new[](size_t size) {
#if defined(COMPILER_MSVC)
- return AlignedAlloc(size, __alignof(Type));
+ return AlignedAlloc(size, __alignof(Type));
#else
- return AlignedAlloc(size, __alignof__(Type));
+ return AlignedAlloc(size, __alignof__(Type));
#endif
- }
- static void operator delete[](void* mem) {
- AlignedFree(mem);
- }
-
- inline Type* get() {
- return space_.template data_as<Type>();
- }
- inline const Type* get() const {
- return space_.template data_as<Type>();
- }
-
- inline Type* operator->() { return get(); }
- inline const Type* operator->() const { return get(); }
-
- inline Type& operator*() { return *get(); }
- inline const Type& operator*() const { return *get(); }
-
- template<typename Ctor>
- inline void InitBy(Ctor ctor) {
- ctor(space_.void_data());
- }
-
- // You can pass up to eight constructor arguments as arguments of Init().
- inline void Init() {
- new(space_.void_data()) Type;
- }
-
- template <typename T1>
- inline void Init(const T1& p1) {
- new(space_.void_data()) Type(p1);
- }
-
- template <typename T1, typename T2>
- inline void Init(const T1& p1, const T2& p2) {
- new(space_.void_data()) Type(p1, p2);
- }
-
- template <typename T1, typename T2, typename T3>
- inline void Init(const T1& p1, const T2& p2, const T3& p3) {
- new(space_.void_data()) Type(p1, p2, p3);
- }
-
- template <typename T1, typename T2, typename T3, typename T4>
- inline void Init(const T1& p1, const T2& p2, const T3& p3, const T4& p4) {
- new(space_.void_data()) Type(p1, p2, p3, p4);
- }
-
- template <typename T1, typename T2, typename T3, typename T4, typename T5>
- inline void Init(const T1& p1, const T2& p2, const T3& p3, const T4& p4,
- const T5& p5) {
- new(space_.void_data()) Type(p1, p2, p3, p4, p5);
- }
-
- template <typename T1, typename T2, typename T3, typename T4, typename T5,
- typename T6>
- inline void Init(const T1& p1, const T2& p2, const T3& p3, const T4& p4,
- const T5& p5, const T6& p6) {
- new(space_.void_data()) Type(p1, p2, p3, p4, p5, p6);
- }
-
- template <typename T1, typename T2, typename T3, typename T4, typename T5,
- typename T6, typename T7>
- inline void Init(const T1& p1, const T2& p2, const T3& p3, const T4& p4,
- const T5& p5, const T6& p6, const T7& p7) {
- new(space_.void_data()) Type(p1, p2, p3, p4, p5, p6, p7);
- }
-
- template <typename T1, typename T2, typename T3, typename T4, typename T5,
- typename T6, typename T7, typename T8>
- inline void Init(const T1& p1, const T2& p2, const T3& p3, const T4& p4,
- const T5& p5, const T6& p6, const T7& p7, const T8& p8) {
- new(space_.void_data()) Type(p1, p2, p3, p4, p5, p6, p7, p8);
- }
-
- inline void Destroy() {
- get()->~Type();
- }
+ }
+
+ static void operator delete[](void* mem) {
+ AlignedFree(mem);
+ }
+
+ Type* get() {
+ return _space.template data_as<Type>();
+ }
+
+ const Type* get() const {
+ return _space.template data_as<Type>();
+ }
+
+ Type* operator->() { return get(); }
+ const Type* operator->() const { return get(); }
+
+ Type& operator*() { return *get(); }
+ const Type& operator*() const { return *get(); }
+
+ template<typename... Args>
+ void Init(Args&&... args) {
+ new (_space.void_data()) Type(std::forward<Args>(args)...);
+ }
+
+ void Destroy() { get()->~Type(); }
private:
#if defined(COMPILER_MSVC)
- AlignedMemory<sizeof(Type), __alignof(Type)> space_;
+ AlignedMemory<sizeof(Type), __alignof(Type)> _space;
#else
- AlignedMemory<sizeof(Type), __alignof__(Type)> space_;
+ AlignedMemory<sizeof(Type), __alignof__(Type)> _space;
#endif
};
diff --git a/src/butil/object_pool_inl.h b/src/butil/object_pool_inl.h
index 71b9b890..0055239d 100644
--- a/src/butil/object_pool_inl.h
+++ b/src/butil/object_pool_inl.h
@@ -25,11 +25,11 @@
#include <iostream> // std::ostream
#include <pthread.h> // pthread_mutex_t
#include <algorithm> // std::max, std::min
-#include "butil/atomicops.h" // butil::atomic
-#include "butil/macros.h" // BAIDU_CACHELINE_ALIGNMENT
-#include "butil/scoped_lock.h" // BAIDU_SCOPED_LOCK
-#include "butil/thread_local.h" // BAIDU_THREAD_LOCAL
-#include "butil/memory/manual_constructor.h"
+#include "butil/atomicops.h" // butil::atomic
+#include "butil/macros.h" // BAIDU_CACHELINE_ALIGNMENT
+#include "butil/scoped_lock.h" // BAIDU_SCOPED_LOCK
+#include "butil/thread_local.h" // BAIDU_THREAD_LOCAL
+#include "butil/memory/aligned_memory.h" // butil::AlignedMemory
#include <vector>
#ifdef BUTIL_OBJECT_POOL_NEED_FREE_ITEM_NUM
@@ -94,11 +94,12 @@ public:
typedef ObjectPoolFreeChunk<T, FREE_CHUNK_NITEM> FreeChunk;
typedef ObjectPoolFreeChunk<T, 0> DynamicFreeChunk;
+ typedef AlignedMemory<sizeof(T), __alignof__(T)> BlockItem;
// When a thread needs memory, it allocates a Block. To improve locality,
// items in the Block are only used by the thread.
// To support cache-aligned objects, align Block.items by cacheline.
struct BAIDU_CACHELINE_ALIGNMENT Block {
- ManualConstructor<T> items[BLOCK_NITEM];
+ BlockItem items[BLOCK_NITEM];
size_t nitem;
Block() : nitem(0) {}
@@ -160,12 +161,10 @@ public:
return _cur_free.ptrs[--_cur_free.nfree]; \
} \
T* obj = NULL; \
- auto ctor = [&](void* mem) { \
- obj = new (mem) T(__VA_ARGS__); \
- }; \
/* Fetch memory from local block */ \
if (_cur_block && _cur_block->nitem < BLOCK_NITEM) { \
- (_cur_block->items + _cur_block->nitem)->InitBy(ctor); \
+ auto item = _cur_block->items + _cur_block->nitem; \
+ obj = new (item->void_data()) T(__VA_ARGS__); \
if (!ObjectPoolValidator<T>::validate(obj)) { \
obj->~T(); \
return NULL; \
@@ -176,7 +175,8 @@ public:
/* Fetch a Block from global */ \
_cur_block = add_block(&_cur_block_index); \
if (_cur_block != NULL) { \
- (_cur_block->items + _cur_block->nitem)->InitBy(ctor); \
+ auto item = _cur_block->items + _cur_block->nitem; \
+ obj = new (item->void_data()) T(__VA_ARGS__); \
if (!ObjectPoolValidator<T>::validate(obj)) { \
obj->~T(); \
return NULL; \
diff --git a/src/butil/resource_pool_inl.h b/src/butil/resource_pool_inl.h
index 2ca858ad..316e37f3 100644
--- a/src/butil/resource_pool_inl.h
+++ b/src/butil/resource_pool_inl.h
@@ -25,11 +25,11 @@
#include <iostream> // std::ostream
#include <pthread.h> // pthread_mutex_t
#include <algorithm> // std::max, std::min
-#include "butil/atomicops.h" // butil::atomic
-#include "butil/macros.h" // BAIDU_CACHELINE_ALIGNMENT
-#include "butil/scoped_lock.h" // BAIDU_SCOPED_LOCK
-#include "butil/thread_local.h" // thread_atexit
-#include "butil/memory/manual_constructor.h"
+#include "butil/atomicops.h" // butil::atomic
+#include "butil/macros.h" // BAIDU_CACHELINE_ALIGNMENT
+#include "butil/scoped_lock.h" // BAIDU_SCOPED_LOCK
+#include "butil/thread_local.h" // thread_atexit
+#include "butil/memory/aligned_memory.h" // butil::AlignedMemory
#include <vector>
#ifdef BUTIL_RESOURCE_POOL_NEED_FREE_ITEM_NUM
@@ -110,11 +110,12 @@ public:
typedef ResourcePoolFreeChunk<T, FREE_CHUNK_NITEM> FreeChunk;
typedef ResourcePoolFreeChunk<T, 0> DynamicFreeChunk;
+ typedef AlignedMemory<sizeof(T), __alignof__(T)> BlockItem;
// When a thread needs memory, it allocates a Block. To improve locality,
// items in the Block are only used by the thread.
// To support cache-aligned objects, align Block.items by cacheline.
struct BAIDU_CACHELINE_ALIGNMENT Block {
- ManualConstructor<T> items[BLOCK_NITEM];
+ BlockItem items[BLOCK_NITEM];
size_t nitem;
Block() : nitem(0) {}
@@ -182,13 +183,11 @@ public:
return unsafe_address_resource(free_id); \
} \
T* p = NULL; \
- auto ctor = [&](void* mem) { \
- p = new (mem) T(__VA_ARGS__); \
- }; \
/* Fetch memory from local block */ \
if (_cur_block && _cur_block->nitem < BLOCK_NITEM) { \
id->value = _cur_block_index * BLOCK_NITEM + _cur_block->nitem; \
- (_cur_block->items + _cur_block->nitem)->InitBy(ctor); \
+ auto item = _cur_block->items + _cur_block->nitem; \
+ p = new (item->void_data()) T(__VA_ARGS__); \
if (!ResourcePoolValidator<T>::validate(p)) { \
p->~T(); \
return NULL; \
@@ -200,7 +199,8 @@ public:
_cur_block = add_block(&_cur_block_index); \
if (_cur_block != NULL) { \
id->value = _cur_block_index * BLOCK_NITEM + _cur_block->nitem; \
- (_cur_block->items + _cur_block->nitem)->InitBy(ctor); \
+ auto item = _cur_block->items + _cur_block->nitem; \
+ p = new (item->void_data()) T(__VA_ARGS__); \
if (!ResourcePoolValidator<T>::validate(p)) { \
p->~T(); \
return NULL; \
diff --git a/src/butil/single_threaded_pool.h b/src/butil/single_threaded_pool.h
index 591e423f..7f34b93c 100644
--- a/src/butil/single_threaded_pool.h
+++ b/src/butil/single_threaded_pool.h
@@ -61,10 +61,12 @@ public:
static const size_t NITEM = Block::NITEM;
static const size_t ITEM_SIZE = ITEM_SIZE_IN;
- SingleThreadedPool(const Allocator& alloc = Allocator())
+ explicit SingleThreadedPool(const Allocator& alloc = Allocator())
: _free_nodes(NULL), _blocks(NULL), _allocator(alloc) {}
~SingleThreadedPool() { reset(); }
+ DISALLOW_COPY_AND_ASSIGN(SingleThreadedPool);
+
void swap(SingleThreadedPool & other) {
std::swap(_free_nodes, other._free_nodes);
std::swap(_blocks, other._blocks);
@@ -132,12 +134,9 @@ public:
}
Allocator& get_allocator() { return _allocator; }
+ Allocator get_allocator() const { return _allocator; }
private:
- // You should not copy a pool.
- SingleThreadedPool(const SingleThreadedPool&);
- void operator=(const SingleThreadedPool&);
-
Node* _free_nodes;
Block* _blocks;
Allocator _allocator;
diff --git a/src/butil/type_traits.h b/src/butil/type_traits.h
index 3cf8473f..0ae91135 100644
--- a/src/butil/type_traits.h
+++ b/src/butil/type_traits.h
@@ -325,6 +325,17 @@ template <typename T> struct remove_pointer<T* const
volatile> {
typedef T type;
};
+// Shortcut for removing const, volatile and reference.
+#if __cplusplus >= 202002L
+template <typename T>
+using remove_cvref = std::remove_cvref<T>;
+#else
+template<typename T>
+struct remove_cvref {
+ typedef typename remove_cv<typename remove_reference<T>::type>::type type;
+};
+#endif
+
// is_reference is false except for reference types.
template<typename T> struct is_reference : false_type {};
template<typename T> struct is_reference<T&> : true_type {};
@@ -355,14 +366,14 @@ template <typename T> struct is_enum<const volatile T> :
is_enum<T> { };
// at compile time.
// If the callable is non-static member function,
// the first argument should be the class type.
-#if (__cplusplus >= 201703L)
+#if __cplusplus >= 201703L
// std::result_of is deprecated in C++17 and removed in C++20,
// use std::invoke_result instead.
template <typename>
struct result_of;
template <typename F, typename... Args>
struct result_of<F(Args...)> : std::invoke_result<F, Args...> {};
-#elif (__cplusplus >= 201103L)
+#elif __cplusplus >= 201103L
template <typename F>
using result_of = std::result_of<F>;
#else
diff --git a/src/bvar/mvariable.cpp b/src/bvar/mvariable.cpp
index 925dccdf..d826893e 100644
--- a/src/bvar/mvariable.cpp
+++ b/src/bvar/mvariable.cpp
@@ -75,7 +75,9 @@ struct MVarMapWithLock : public MVarMap {
pthread_mutex_t mutex;
MVarMapWithLock() {
- CHECK_EQ(0, init(256, 80));
+ if (init(256) != 0) {
+ LOG(WARNING) << "Fail to init";
+ }
pthread_mutex_init(&mutex, NULL);
}
};
diff --git a/src/bvar/variable.cpp b/src/bvar/variable.cpp
index 4da0b1e0..e4f09355 100644
--- a/src/bvar/variable.cpp
+++ b/src/bvar/variable.cpp
@@ -76,7 +76,10 @@ struct VarMapWithLock : public VarMap {
pthread_mutex_t mutex;
VarMapWithLock() {
- CHECK_EQ(0, init(1024, 80));
+ if (init(1024) != 0) {
+ LOG(WARNING) << "Fail to init VarMap";
+ }
+
pthread_mutexattr_t attr;
pthread_mutexattr_init(&attr);
pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE);
diff --git a/src/mcpack2pb/mcpack2pb.cpp b/src/mcpack2pb/mcpack2pb.cpp
index c810a011..7ab24e3e 100644
--- a/src/mcpack2pb/mcpack2pb.cpp
+++ b/src/mcpack2pb/mcpack2pb.cpp
@@ -32,8 +32,7 @@ static butil::FlatMap<std::string, MessageHandler>*
s_handler_map = NULL;
static void init_handler_map() {
s_handler_map = new butil::FlatMap<std::string, MessageHandler>;
if (s_handler_map->init(64, 50) != 0) {
- LOG(ERROR) << "Fail to init s_handler_map";
- exit(1);
+ LOG(WARNING) << "Fail to init s_handler_map";
}
}
void register_message_handler_or_die(const std::string& full_name,
diff --git a/test/BUILD.bazel b/test/BUILD.bazel
index 7f49fe71..3c4242da 100644
--- a/test/BUILD.bazel
+++ b/test/BUILD.bazel
@@ -139,7 +139,8 @@ TEST_BUTIL_SOURCES = [
#"popen_unittest.cpp",
"bounded_queue_unittest.cc",
"butil_unittest_main.cpp",
- "scope_guard_unittest.cc",
+ "scope_guard_unittest.cpp",
+ "optional_unittest.cpp",
] + select({
"@bazel_tools//tools/osx:darwin_x86_64": [],
"//conditions:default": [
diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
index 7b1766e9..11f1ad3b 100644
--- a/test/CMakeLists.txt
+++ b/test/CMakeLists.txt
@@ -174,8 +174,8 @@ SET(TEST_BUTIL_SOURCES
${PROJECT_SOURCE_DIR}/test/object_pool_unittest.cpp
${PROJECT_SOURCE_DIR}/test/test_switches.cc
${PROJECT_SOURCE_DIR}/test/scoped_locale.cc
- ${PROJECT_SOURCE_DIR}/test/scope_guard_unittest.cc
- ${PROJECT_SOURCE_DIR}/test/butil_unittest_main.cpp
+ ${PROJECT_SOURCE_DIR}/test/scope_guard_unittest.cpp
+ ${PROJECT_SOURCE_DIR}/test/optional_unittest.cpp
${PROJECT_SOURCE_DIR}/test/butil_unittest_main.cpp
)
diff --git a/test/Makefile b/test/Makefile
index f09b398d..874e6928 100644
--- a/test/Makefile
+++ b/test/Makefile
@@ -146,7 +146,8 @@ TEST_BUTIL_SOURCES = \
popen_unittest.cpp \
bounded_queue_unittest.cc \
butil_unittest_main.cpp \
- scope_guard_unittest.cc
+ scope_guard_unittest.cpp \
+ optional_unittest.cpp
ifeq ($(SYSTEM), Linux)
TEST_BUTIL_SOURCES += test_file_util_linux.cc \
diff --git a/test/brpc_controller_unittest.cpp
b/test/brpc_controller_unittest.cpp
index f7333281..3f410a25 100644
--- a/test/brpc_controller_unittest.cpp
+++ b/test/brpc_controller_unittest.cpp
@@ -130,7 +130,7 @@ TEST_F(ControllerTest, SessionKV) {
FLAGS_log_as_json = true;
}
- ASSERT_TRUE(endsWith(sink1, R"(,"@rid":"abcdEFG-456","M":"Session
ends.","Baidu":"NewStuff","Cisco":"33.330000","Apple":"1234567"})")) << sink1;
+ ASSERT_TRUE(endsWith(sink1, R"(,"@rid":"abcdEFG-456","M":"Session
ends.","Cisco":"33.330000","Apple":"1234567","Baidu":"NewStuff"})")) << sink1;
ASSERT_TRUE(startsWith(sink1, R"({"L":"I",)")) << sink1;
logging::SetLogSink(oldSink);
diff --git a/test/brpc_extension_unittest.cpp b/test/brpc_extension_unittest.cpp
index 7c01e5b1..eea238ee 100644
--- a/test/brpc_extension_unittest.cpp
+++ b/test/brpc_extension_unittest.cpp
@@ -68,5 +68,5 @@ TEST_F(ExtensionTest, basic) {
os.str("");
ConstIntExtension()->List(os, ':');
- ASSERT_EQ("bar:foo", os.str());
+ ASSERT_EQ("foo:bar", os.str());
}
diff --git a/test/brpc_http_message_unittest.cpp
b/test/brpc_http_message_unittest.cpp
index e9f25e8f..0d5a979a 100644
--- a/test/brpc_http_message_unittest.cpp
+++ b/test/brpc_http_message_unittest.cpp
@@ -610,27 +610,27 @@ TEST(HttpMessageTest, serialize_http_request) {
// user-set accept
header.SetHeader("accePT"/*intended uppercase*/, "blahblah");
MakeRawHttpRequest(&request, &header, ep, &content);
- ASSERT_EQ("POST / HTTP/1.1\r\nContent-Length: 4\r\naccePT:
blahblah\r\nFoo: Bar\r\nHost: MyHost: 4321\r\nUser-Agent: brpc/1.0
curl/7.0\r\n\r\ndata", request);
+ ASSERT_EQ("POST / HTTP/1.1\r\nContent-Length: 4\r\nFoo: Bar\r\naccePT:
blahblah\r\nHost: MyHost: 4321\r\nUser-Agent: brpc/1.0 curl/7.0\r\n\r\ndata",
request);
// user-set UA
header.SetHeader("user-AGENT", "myUA");
MakeRawHttpRequest(&request, &header, ep, &content);
- ASSERT_EQ("POST / HTTP/1.1\r\nContent-Length: 4\r\naccePT:
blahblah\r\nuser-AGENT: myUA\r\nFoo: Bar\r\nHost: MyHost: 4321\r\n\r\ndata",
request);
+ ASSERT_EQ("POST / HTTP/1.1\r\nContent-Length: 4\r\nFoo: Bar\r\naccePT:
blahblah\r\nHost: MyHost: 4321\r\nuser-AGENT: myUA\r\n\r\ndata", request);
// user-set Authorization
header.SetHeader("authorization", "myAuthString");
MakeRawHttpRequest(&request, &header, ep, &content);
- ASSERT_EQ("POST / HTTP/1.1\r\nContent-Length: 4\r\naccePT:
blahblah\r\nuser-AGENT: myUA\r\nauthorization: myAuthString\r\nFoo:
Bar\r\nHost: MyHost: 4321\r\n\r\ndata", request);
+ ASSERT_EQ("POST / HTTP/1.1\r\nContent-Length: 4\r\nFoo: Bar\r\naccePT:
blahblah\r\nHost: MyHost: 4321\r\nuser-AGENT: myUA\r\nauthorization:
myAuthString\r\n\r\ndata", request);
header.SetHeader("Transfer-Encoding", "chunked");
MakeRawHttpRequest(&request, &header, ep, &content);
- ASSERT_EQ("POST / HTTP/1.1\r\naccePT: blahblah\r\nTransfer-Encoding:
chunked\r\nuser-AGENT: myUA\r\nauthorization: myAuthString\r\nFoo: Bar\r\nHost:
MyHost: 4321\r\n\r\ndata", request);
+ ASSERT_EQ("POST / HTTP/1.1\r\nFoo: Bar\r\naccePT:
blahblah\r\nTransfer-Encoding: chunked\r\nHost: MyHost: 4321\r\nuser-AGENT:
myUA\r\nauthorization: myAuthString\r\n\r\ndata", request);
// GET does not serialize content and user-set content-length is ignored.
header.set_method(brpc::HTTP_METHOD_GET);
header.SetHeader("Content-Length", "100");
MakeRawHttpRequest(&request, &header, ep, &content);
- ASSERT_EQ("GET / HTTP/1.1\r\naccePT: blahblah\r\nuser-AGENT:
myUA\r\nauthorization: myAuthString\r\nFoo: Bar\r\nHost: MyHost: 4321\r\n\r\n",
request);
+ ASSERT_EQ("GET / HTTP/1.1\r\nFoo: Bar\r\naccePT: blahblah\r\nHost: MyHost:
4321\r\nuser-AGENT: myUA\r\nauthorization: myAuthString\r\n\r\n", request);
}
TEST(HttpMessageTest, serialize_http_response) {
@@ -649,12 +649,12 @@ TEST(HttpMessageTest, serialize_http_response) {
// NULL content
header.SetHeader("Content-Length", "100");
MakeRawHttpResponse(&response, &header, NULL);
- ASSERT_EQ("HTTP/1.1 200 OK\r\nContent-Length: 100\r\nFoo: Bar\r\n\r\n",
response)
+ ASSERT_EQ("HTTP/1.1 200 OK\r\nFoo: Bar\r\nContent-Length: 100\r\n\r\n",
response)
<< butil::ToPrintable(response);
header.SetHeader("Transfer-Encoding", "chunked");
MakeRawHttpResponse(&response, &header, NULL);
- ASSERT_EQ("HTTP/1.1 200 OK\r\nTransfer-Encoding: chunked\r\nFoo:
Bar\r\n\r\n", response)
+ ASSERT_EQ("HTTP/1.1 200 OK\r\nFoo: Bar\r\nTransfer-Encoding:
chunked\r\n\r\n", response)
<< butil::ToPrintable(response);
header.RemoveHeader("Transfer-Encoding");
@@ -667,7 +667,7 @@ TEST(HttpMessageTest, serialize_http_response) {
header.SetHeader("Content-Length", "100");
header.SetHeader("Transfer-Encoding", "chunked");
MakeRawHttpResponse(&response, &header, NULL);
- ASSERT_EQ("HTTP/1.1 200 OK\r\nTransfer-Encoding: chunked\r\nFoo:
Bar\r\n\r\n", response)
+ ASSERT_EQ("HTTP/1.1 200 OK\r\nFoo: Bar\r\nTransfer-Encoding:
chunked\r\n\r\n", response)
<< butil::ToPrintable(response);
header.RemoveHeader("Transfer-Encoding");
@@ -696,7 +696,7 @@ TEST(HttpMessageTest, serialize_http_response) {
// 2. User-set content-length is not ignored .
header.SetHeader("Content-Length", "100");
MakeRawHttpResponse(&response, &header, &content);
- ASSERT_EQ("HTTP/1.1 200 OK\r\nContent-Length: 100\r\nFoo: Bar\r\n\r\n",
response)
+ ASSERT_EQ("HTTP/1.1 200 OK\r\nFoo: Bar\r\nContent-Length: 100\r\n\r\n",
response)
<< butil::ToPrintable(response);
}
diff --git a/test/flat_map_unittest.cpp b/test/flat_map_unittest.cpp
index c3368d36..a394218a 100644
--- a/test/flat_map_unittest.cpp
+++ b/test/flat_map_unittest.cpp
@@ -95,31 +95,49 @@ TEST_F(FlatMapTest, swap_pooled_allocator) {
TEST_F(FlatMapTest, copy_flat_map) {
typedef butil::FlatMap<std::string, std::string> Map;
- Map uninit_m1;
- ASSERT_FALSE(uninit_m1.initialized());
- ASSERT_TRUE(uninit_m1.empty());
+ Map default_init_m1;
+ ASSERT_TRUE(default_init_m1.initialized());
+ ASSERT_TRUE(default_init_m1.empty());
+ ASSERT_EQ(BRPC_FLATMAP_DEFAULT_NBUCKET, default_init_m1.bucket_count());
// self assignment does nothing.
- uninit_m1 = uninit_m1;
- ASSERT_FALSE(uninit_m1.initialized());
- ASSERT_TRUE(uninit_m1.empty());
- // Copy construct from uninitialized map.
- Map uninit_m2 = uninit_m1;
- ASSERT_FALSE(uninit_m2.initialized());
- ASSERT_TRUE(uninit_m2.empty());
- // assign uninitialized map to uninitialized map.
- Map uninit_m3;
- uninit_m3 = uninit_m1;
- ASSERT_FALSE(uninit_m3.initialized());
- ASSERT_TRUE(uninit_m3.empty());
- // assign uninitialized map to initialized map.
+ default_init_m1 = default_init_m1;
+ ASSERT_TRUE(default_init_m1.initialized());
+ ASSERT_TRUE(default_init_m1.empty());
+ ASSERT_EQ(BRPC_FLATMAP_DEFAULT_NBUCKET, default_init_m1.bucket_count());
+
+ Map default_init_m2 = default_init_m1;
+ ASSERT_TRUE(default_init_m2.initialized());
+ ASSERT_TRUE(default_init_m2.empty());
+ ASSERT_EQ(BRPC_FLATMAP_DEFAULT_NBUCKET, default_init_m1.bucket_count());
+
+ Map init_m3;
+ ASSERT_TRUE(init_m3.initialized());
+ // smaller than the default value, and the default buckets
+ // is continued to be used.
+ ASSERT_EQ(0, init_m3.init(8));
+ ASSERT_TRUE(init_m3.initialized());
+ ASSERT_EQ(BRPC_FLATMAP_DEFAULT_NBUCKET, init_m3.bucket_count());
+ ASSERT_EQ(init_m3._default_buckets, init_m3._buckets);
+ init_m3["hello"] = "world";
+ ASSERT_EQ(1u, init_m3.size());
+ init_m3 = default_init_m1;
+ ASSERT_TRUE(init_m3.initialized());
+ ASSERT_TRUE(init_m3.empty());
+
Map init_m4;
- ASSERT_EQ(0, init_m4.init(16));
ASSERT_TRUE(init_m4.initialized());
+ // Resize to a larger buckets, and then not using the default buckets.
+ ASSERT_EQ(0, init_m4.init(BRPC_FLATMAP_DEFAULT_NBUCKET + 1));
+ ASSERT_EQ(butil::flatmap_round(BRPC_FLATMAP_DEFAULT_NBUCKET + 1),
+ init_m4.bucket_count());
+ ASSERT_NE(init_m4._default_buckets, init_m4._buckets);
init_m4["hello"] = "world";
ASSERT_EQ(1u, init_m4.size());
- init_m4 = uninit_m1;
+ init_m4 = default_init_m1;
ASSERT_TRUE(init_m4.initialized());
ASSERT_TRUE(init_m4.empty());
+ ASSERT_EQ(butil::flatmap_round(BRPC_FLATMAP_DEFAULT_NBUCKET + 1),
+ init_m4.bucket_count());
Map m1;
ASSERT_EQ(0, m1.init(16));
@@ -173,7 +191,7 @@ TEST_F(FlatMapTest, copy_flat_map) {
const void* old_buckets4 = m4._buckets;
m4 = m1;
ASSERT_EQ(m1.bucket_count(), m4.bucket_count());
- ASSERT_NE(old_buckets4, m4._buckets);
+ ASSERT_EQ(old_buckets4, m4._buckets);
ASSERT_EQ(expected_count, m4.size());
ASSERT_EQ("world", m4["hello"]);
ASSERT_EQ("bar", m4["foo"]);
@@ -226,7 +244,7 @@ TEST_F(FlatMapTest, to_lower) {
for (int c = -128; c < 128; ++c) {
ASSERT_EQ((char)::tolower(c), butil::ascii_tolower(c)) << "c=" << c;
}
-
+
const size_t input_len = 102;
char input[input_len + 1];
char input2[input_len + 1];
@@ -379,7 +397,7 @@ TEST_F(FlatMapTest, flat_map_of_string) {
for (size_t i = 0; i < N; ++i) {
keys.push_back(butil::string_printf("up_latency_as_key_%lu", i));
}
-
+
tm1.start();
for (size_t i = 0; i < N; ++i) {
m1[keys[i]] += i;
@@ -441,12 +459,64 @@ TEST_F(FlatMapTest, flat_map_of_string) {
LOG(INFO) << "finding c_strings takes " << tm1.n_elapsed()/N
<< " " << tm2.n_elapsed()/N << " " << tm3.n_elapsed()/N
<< " " << tm1_2.n_elapsed()/N << " sum=" << sum;
-
+
for (size_t i = 0; i < N; ++i) {
ASSERT_EQ(i, m1[keys[i]]) << "i=" << i;
ASSERT_EQ(i, m2[keys[i]]);
ASSERT_EQ(i, m3[keys[i]]);
}
+
+ butil::FlatMap<std::string, std::string> m4;
+ m4["111"] = "222";
+ ASSERT_TRUE(m4.seek("111"));
+ ASSERT_EQ("222", *m4.seek("111"));
+ ASSERT_EQ(1UL, m4.size());
+ butil::FlatMap<std::string, std::string> m5;
+ m5["333"] = "444";
+ ASSERT_TRUE(m5.seek("333"));
+ ASSERT_EQ("444", *m5.seek("333"));
+ ASSERT_EQ(1UL, m5.size());
+
+ m4.swap(m5);
+ ASSERT_TRUE(m4.seek("333"));
+ ASSERT_EQ("444", *m4.seek("333"));
+ ASSERT_EQ(1UL, m4.size());
+ ASSERT_TRUE(m5.seek("111"));
+ ASSERT_EQ("222", *m5.seek("111"));
+ ASSERT_EQ(1UL, m5.size());
+
+ m4.resize(BRPC_FLATMAP_DEFAULT_NBUCKET + 1);
+ ASSERT_EQ(1UL, m4.size());
+ ASSERT_TRUE(m4.seek("333"));
+ ASSERT_EQ("444", *m4.seek("333"));
+ m4.swap(m5);
+ ASSERT_TRUE(m4.seek("111"));
+ ASSERT_EQ("222", *m4.seek("111"));
+ ASSERT_EQ(1UL, m4.size());
+ ASSERT_TRUE(m5.seek("333"));
+ ASSERT_EQ("444", *m5.seek("333"));
+ ASSERT_EQ(1UL, m5.size());
+
+ m5.swap(m4);
+ ASSERT_TRUE(m4.seek("333"));
+ ASSERT_EQ("444", *m4.seek("333"));
+ ASSERT_EQ(1UL, m4.size());
+ ASSERT_TRUE(m5.seek("111"));
+ ASSERT_EQ("222", *m5.seek("111"));
+ ASSERT_EQ(1UL, m5.size());
+
+ m5.resize(BRPC_FLATMAP_DEFAULT_NBUCKET + 1);
+ ASSERT_EQ(1UL, m5.size());
+ ASSERT_EQ("222", *m5.seek("111"));
+ ASSERT_EQ(1UL, m5.size());
+ m5.swap(m4);
+ ASSERT_TRUE(m4.seek("111"));
+ ASSERT_EQ("222", *m4.seek("111"));
+ ASSERT_EQ(1UL, m4.size());
+ ASSERT_TRUE(m5.seek("333"));
+ ASSERT_EQ("444", *m5.seek("333"));
+ ASSERT_EQ(1UL, m5.size());
+
}
TEST_F(FlatMapTest, fast_iterator) {
@@ -457,7 +527,7 @@ TEST_F(FlatMapTest, fast_iterator) {
M2 m2;
ASSERT_EQ(0, m1.init(16384));
- ASSERT_EQ(-1, m1.init(1));
+ ASSERT_EQ(0, m1.init(1));
ASSERT_EQ(0, m2.init(16384));
ASSERT_EQ(NULL, m1._thumbnail);
@@ -537,11 +607,11 @@ typedef butil::FlatMap<uint64_t, uint64_t>
PositionHintMap;
static void fill_position_hint_map(PositionHintMap* map,
std::vector<uint64_t>* keys) {
srand(time(NULL));
- const size_t N = 170;
+ const size_t N = 5;
if (!map->initialized()) {
ASSERT_EQ(0, map->init(N * 3 / 2, 80));
}
-
+
keys->reserve(N);
keys->clear();
map->clear();
@@ -553,7 +623,7 @@ static void fill_position_hint_map(PositionHintMap* map,
keys->push_back(key);
(*map)[key] = i;
}
- LOG(INFO) << map->bucket_info();
+ LOG(INFO) << map->bucket_info() << ", size=" << map->size();
}
struct CountOnPause {
@@ -601,7 +671,7 @@ struct RemoveInsertVisitedOnPause {
removed_keys.insert(removed_key);
break;
} while (true);
-
+
// Insert one
uint64_t inserted_key =
((rand() % hint.offset) + rand() * hint.nbucket);
@@ -844,14 +914,17 @@ struct Value {
Value() : x_(0) { ++n_con; }
Value(int x) : x_(x) { ++ n_con; }
Value (const Value& rhs) : x_(rhs.x_) { ++ n_cp_con; }
- ~Value() { ++ n_des; }
-
+ ~Value() {
+ ++ n_des;
+ // CHECK(false);
+ }
+
Value& operator= (const Value& rhs) {
x_ = rhs.x_;
++ n_cp;
return *this;
}
-
+
bool operator== (const Value& rhs) const { return x_ == rhs.x_; }
bool operator!= (const Value& rhs) const { return x_ != rhs.x_; }
@@ -900,16 +973,41 @@ TEST_F(FlatMapTest,
key_value_are_not_constructed_before_first_insertion) {
TEST_F(FlatMapTest, manipulate_uninitialized_map) {
butil::FlatMap<int, int> m;
- ASSERT_FALSE(m.initialized());
- for (butil::FlatMap<int,int>::iterator it = m.begin(); it != m.end();
++it) {
- LOG(INFO) << "nothing";
- }
+ ASSERT_TRUE(m.initialized());
ASSERT_EQ(NULL, m.seek(1));
ASSERT_EQ(0u, m.erase(1));
ASSERT_EQ(0u, m.size());
ASSERT_TRUE(m.empty());
- ASSERT_EQ(0u, m.bucket_count());
- ASSERT_EQ(0u, m.load_factor());
+ ASSERT_EQ(BRPC_FLATMAP_DEFAULT_NBUCKET, m.bucket_count());
+ ASSERT_EQ(80u, m.load_factor());
+ m[1] = 1;
+ ASSERT_EQ(1UL, m.size());
+ auto one = m.seek(1);
+ ASSERT_NE(nullptr, one);
+ ASSERT_EQ(1, *one);
+
+ butil::FlatMap<int, int> m2 = m;
+ one = m2.seek(1);
+ ASSERT_NE(nullptr, one);
+ ASSERT_EQ(1, *one);
+ m2[2] = 2;
+ ASSERT_EQ(2UL, m2.size());
+
+ m.swap(m2);
+ ASSERT_EQ(2UL, m.size());
+ ASSERT_EQ(1UL, m2.size());
+ auto two = m.seek(2);
+ ASSERT_NE(nullptr, two);
+ ASSERT_EQ(2, *two);
+
+ ASSERT_EQ(1UL, m2.erase(1));
+ ASSERT_EQ(0, m.init(32));
+ one = m.seek(1);
+ ASSERT_NE(nullptr, one);
+ ASSERT_EQ(1, *one);
+ two = m.seek(2);
+ ASSERT_NE(nullptr, two);
+ ASSERT_EQ(2, *two);
}
TEST_F(FlatMapTest, perf_small_string_map) {
@@ -948,7 +1046,7 @@ TEST_F(FlatMapTest, perf_small_string_map) {
m2["Request-Id"] = "true";
m2["Status-Code"] = "200";
tm2.stop();
-
+
LOG(INFO) << "flatmap=" << tm1.n_elapsed()
<< " ci_flatmap=" << tm4.n_elapsed()
<< " map=" << tm2.n_elapsed()
@@ -956,12 +1054,10 @@ TEST_F(FlatMapTest, perf_small_string_map) {
}
}
-
TEST_F(FlatMapTest, sanity) {
typedef butil::FlatMap<uint64_t, long> Map;
Map m;
-
- ASSERT_FALSE(m.initialized());
+ ASSERT_TRUE(m.initialized());
m.init(1000, 70);
ASSERT_TRUE(m.initialized());
ASSERT_EQ(0UL, m.size());
@@ -981,7 +1077,7 @@ TEST_F(FlatMapTest, sanity) {
long* p = m.seek(k1);
ASSERT_TRUE(p && *p == 10);
ASSERT_EQ(0UL, m._pool.count_allocated());
-
+
ASSERT_EQ(NULL, m.seek(k2));
// Override
@@ -990,7 +1086,7 @@ TEST_F(FlatMapTest, sanity) {
ASSERT_FALSE(m.empty());
p = m.seek(k1);
ASSERT_TRUE(p && *p == 100);
-
+
// Insert another
m[k3] = 20;
ASSERT_EQ(2UL, m.size());
@@ -1006,7 +1102,7 @@ TEST_F(FlatMapTest, sanity) {
ASSERT_FALSE(m.empty());
p = m.seek(k2);
ASSERT_TRUE(p && *p == 30);
-
+
ASSERT_EQ(NULL, m.seek(2049));
Map::iterator it = m.begin();
@@ -1061,9 +1157,13 @@ TEST_F(FlatMapTest, random_insert_erase) {
for (int i = 0; i < 100000; ++i) {
int k = rand() % 0xFFFF;
int p = rand() % 1000;
+ ht[0].insert(k, i);
+ // LOG(INFO) << "i=" << i << " k=" << k;
+
+ // ASSERT_EQ(n_con + n_cp_con, n_des * 2)
+ // << " n_con=" << n_con << " n_cp_con=" << n_cp_con << "
n_des=" << n_des << " n_cp=" << n_cp;
+ ref[0][k] = i;
if (p < 600) {
- ht[0].insert(k, i);
- ref[0][k] = i;
} else if(p < 999) {
ht[0].erase (k);
ref[0].erase (k);
@@ -1072,8 +1172,8 @@ TEST_F(FlatMapTest, random_insert_erase) {
ref[0].clear();
}
}
-
- LOG(INFO) << "Check j=" << j;
+
+ // LOG(INFO) << "Check j=" << j;
// bi-check
for (int i=0; i<2; ++i) {
for (Map::iterator it = ht[i].begin(); it != ht[i].end(); ++it)
@@ -1082,7 +1182,7 @@ TEST_F(FlatMapTest, random_insert_erase) {
ASSERT_TRUE (it2 != ref[i].end());
ASSERT_EQ (it2->second, it->second);
}
-
+
for (butil::hash_map<uint64_t, Value>::iterator it =
ref[i].begin();
it != ref[i].end(); ++it)
{
@@ -1095,11 +1195,10 @@ TEST_F(FlatMapTest, random_insert_erase) {
}
}
- // cout << "ht[0] = " << show(ht[0]) << endl
- // << "ht[1] = " << show(ht[1]) << endl;
- //ASSERT_EQ (ht[0]._pool->alloc_num(), 0ul);
- ASSERT_EQ (n_con + n_cp_con, n_des);
+ ASSERT_EQ (n_con + n_cp_con, n_des)
+ // todo delete
+ << "n_con=" << n_con << " n_cp_con=" << n_cp_con << " n_des=" << n_des
<< " n_cp=" << n_cp;
LOG(INFO) << "n_con:" << n_con << std::endl
<< "n_cp_con:" << n_cp_con << std::endl
@@ -1156,8 +1255,8 @@ void perf_insert_erase(bool random, const T& value) {
if (random) {
random_shuffle(keys.begin(), keys.end());
}
-
- id_map.clear();
+
+ id_map.clear();
id_tm.start();
for (size_t i = 0; i < keys.size(); ++i) {
id_map[keys[i]] = value;
@@ -1293,7 +1392,7 @@ void perf_seek(const T& value) {
butil::hash_map<uint64_t, T> hash_map;
butil::Timer id_tm, multi_id_tm, std_tm, pooled_tm,
std_unordered_tm, std_unordered_multi_tm, hash_tm;
-
+
id_map.init((size_t)(nkeys[NPASS-1] * 1.5));
multi_id_map.init((size_t)(nkeys[NPASS-1] * 1.5));
LOG(INFO) << "[ value = " << sizeof(T) << " bytes ]";
@@ -1303,8 +1402,8 @@ void perf_seek(const T& value) {
for (size_t i = 0; i < nkeys[pass]; ++i) {
keys.push_back(start + i);
}
-
- id_map.clear();
+
+ id_map.clear();
for (size_t i = 0; i < keys.size(); ++i) {
id_map[keys[i]] = value;
}
@@ -1428,25 +1527,6 @@ TEST_F(FlatMapTest, copy) {
m2 = m1;
ASSERT_FALSE(m1.is_too_crowded(m1.size()));
ASSERT_FALSE(m2.is_too_crowded(m1.size()));
-
- butil::FlatMap<int, int> m3;
- ASSERT_FALSE(m3.initialized());
- m1 = m3;
- ASSERT_TRUE(m1.empty());
- ASSERT_TRUE(m1.initialized());
-
- m3 = m2;
- ASSERT_TRUE(m3.initialized());
- ASSERT_TRUE(m3.seek(1));
- ASSERT_TRUE(m3.seek(2));
- ASSERT_FALSE(m3.seek(3));
-
- m3.clear();
- ASSERT_TRUE(m3.initialized());
- ASSERT_TRUE(m3.empty());
- butil::FlatMap<int, int> m4 = m3;
- ASSERT_TRUE(m4.initialized());
- ASSERT_TRUE(m4.empty());
}
TEST_F(FlatMapTest, multi) {
@@ -1487,8 +1567,8 @@ TEST_F(FlatMapTest, multi) {
int same_bucket_key = 1 + bucket_count;
butil::DefaultHasher<int> hasher;
ASSERT_EQ(butil::flatmap_mod(hasher(1), bucket_count),
- butil::flatmap_mod(hasher(same_bucket_key), bucket_count));
- ASSERT_EQ(0, map.erase(same_bucket_key));
+ butil::flatmap_mod(hasher(same_bucket_key), bucket_count));
+ ASSERT_EQ(0UL, map.erase(same_bucket_key));
Foo& f5 = map[same_bucket_key];
ASSERT_EQ(4UL, map.size());
ASSERT_EQ(&f5, map.seek(same_bucket_key));
diff --git a/test/optional_unittest.cpp b/test/optional_unittest.cpp
new file mode 100644
index 00000000..8038105c
--- /dev/null
+++ b/test/optional_unittest.cpp
@@ -0,0 +1,298 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you 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.
+
+
+#include <gtest/gtest.h>
+#include "butil/containers/optional.h"
+
+namespace {
+
+butil::optional<int> empty_optional() {
+ return {};
+}
+
+TEST(OptionalTest, sanity) {
+ {
+ butil::optional<int> empty;
+ ASSERT_FALSE(empty);
+ }
+
+ {
+ butil::optional<int> empty{};
+ ASSERT_FALSE(empty);
+ }
+
+ {
+ butil::optional<int> empty = empty_optional();
+ ASSERT_FALSE(empty);
+ }
+
+ {
+ butil::optional<int> non_empty(42);
+ ASSERT_TRUE(non_empty);
+ ASSERT_TRUE(non_empty.has_value());
+ ASSERT_EQ(*non_empty, 42);
+ }
+
+ butil::optional<std::string> opt_string = "abc";
+ ASSERT_TRUE(opt_string);
+ ASSERT_EQ(*opt_string, "abc");
+}
+
+TEST(OptionalTest, nullopt) {
+ butil::optional<int> empty(butil::nullopt);
+ ASSERT_FALSE(empty);
+
+ empty = 1;
+ ASSERT_TRUE(empty);
+ ASSERT_EQ(1, empty);
+
+ empty = butil::nullopt;
+ ASSERT_FALSE(empty);
+}
+
+TEST(OptionalTest, copy) {
+ butil::optional<int> op(1);
+ ASSERT_TRUE(op);
+ ASSERT_EQ(1, op);
+
+ butil::optional<int> non_empty(op);
+ ASSERT_TRUE(non_empty);
+
+ op = butil::nullopt;
+ ASSERT_FALSE(op);
+
+ butil::optional<int> empty(op);
+ ASSERT_FALSE(empty);
+
+ non_empty = empty;
+ ASSERT_FALSE(non_empty);
+
+ op = 10;
+ non_empty = op;
+ ASSERT_TRUE(non_empty);
+ ASSERT_EQ(10, non_empty);
+}
+
+TEST(OptionalTest, move) {
+ butil::optional<int> empty;
+ ASSERT_FALSE(empty);
+ butil::optional<int> non_empty = 1;
+ ASSERT_TRUE(non_empty);
+ ASSERT_EQ(1, non_empty);
+
+ butil::optional<int> empty_move(std::move(empty));
+ ASSERT_FALSE(empty_move);
+
+ butil::optional<int> non_empty_move(std::move(non_empty));
+ ASSERT_TRUE(non_empty_move);
+ ASSERT_EQ(1, non_empty_move);
+
+ butil::optional<int> empty_move_assign;
+ empty_move_assign = std::move(empty);
+ ASSERT_FALSE(empty_move_assign);
+}
+
+struct Obj {};
+
+struct Convert {
+ Convert()
+ :default_ctor(false), move_ctor(false) { }
+ explicit Convert(const Obj&)
+ :default_ctor(true), move_ctor(false) { }
+ explicit Convert(Obj&&)
+ :default_ctor(true), move_ctor(true) { }
+
+ bool default_ctor;
+ bool move_ctor;
+};
+
+struct ConvertFromOptional {
+ ConvertFromOptional()
+ :default_ctor(false), move_ctor(false), from_optional(false) { }
+ ConvertFromOptional(const Obj&)
+ :default_ctor(true), move_ctor(false), from_optional(false) { }
+ ConvertFromOptional(Obj&&)
+ :default_ctor(true), move_ctor(true), from_optional(false) { }
+ ConvertFromOptional(
+ const butil::optional<Obj>&)
+ :default_ctor(true), move_ctor(false), from_optional(true) { }
+ ConvertFromOptional(butil::optional<Obj>&&)
+ :default_ctor(true), move_ctor(true), from_optional(true) { }
+
+ bool default_ctor;
+ bool move_ctor;
+ bool from_optional;
+};
+
+TEST(OptionalTest, convert) {
+ butil::optional<Obj> i_empty;
+ ASSERT_FALSE(i_empty);
+ butil::optional<Obj> i(butil::in_place);
+ ASSERT_TRUE(i);
+ {
+ butil::optional<Convert> empty(i_empty);
+ ASSERT_FALSE(empty);
+ butil::optional<Convert> opt_copy(i);
+ ASSERT_TRUE(opt_copy);
+ ASSERT_TRUE(opt_copy->default_ctor);
+ ASSERT_FALSE(opt_copy->move_ctor);
+
+ butil::optional<Convert> opt_move(butil::optional<Obj>{
butil::in_place });
+ ASSERT_TRUE(opt_move);
+ ASSERT_TRUE(opt_move->default_ctor);
+ ASSERT_TRUE(opt_move->move_ctor);
+ }
+
+ {
+ static_assert(
+ std::is_convertible<butil::optional<Obj>,
+ butil::optional<ConvertFromOptional>>::value,
+ "");
+ butil::optional<ConvertFromOptional> opt0 = i_empty;
+ ASSERT_TRUE(opt0);
+ ASSERT_TRUE(opt0->default_ctor);
+ ASSERT_FALSE(opt0->move_ctor);
+ ASSERT_TRUE(opt0->from_optional);
+ butil::optional<ConvertFromOptional> opt1 = butil::optional<Obj>();
+ ASSERT_TRUE(opt1);
+ ASSERT_TRUE(opt1->default_ctor);
+ ASSERT_TRUE(opt1->move_ctor);
+ ASSERT_TRUE(opt1->from_optional);
+ }
+}
+
+TEST(OptionalTest, value) {
+ butil::optional<double> opt_empty;
+ butil::optional<double> opt_double = 1.0;
+ ASSERT_THROW(opt_empty.value(), butil::bad_optional_access);
+ ASSERT_EQ(10.0, opt_empty.value_or(10));
+ ASSERT_EQ(1.0, opt_double.value());
+ ASSERT_EQ(1.0, opt_double.value_or(42));
+ ASSERT_EQ(10.0, butil::optional<double>().value_or(10));
+ ASSERT_EQ(1.0, butil::optional<double>(1).value_or(10));
+}
+
+TEST(OptionalTest, emplace) {
+ butil::optional<std::string> opt_string;
+ ASSERT_TRUE((std::is_same<std::string&,
decltype(opt_string.emplace("abc"))>::value));
+ std::string& str = opt_string.emplace("abc");
+ ASSERT_EQ(&str, &opt_string.value());
+}
+
+TEST(OptionalTest, swap) {
+ butil::optional<int> opt_empty, opt1 = 1, opt2 = 2;
+ ASSERT_FALSE(opt_empty);
+ ASSERT_TRUE(opt1);
+ ASSERT_EQ(1, opt1.value());
+ ASSERT_TRUE(opt2);
+ ASSERT_EQ(2, opt2.value());
+ swap(opt_empty, opt1);
+ ASSERT_FALSE(opt1);
+ ASSERT_TRUE(opt_empty);
+ ASSERT_EQ(1, opt_empty.value());
+ ASSERT_TRUE(opt2);
+ ASSERT_EQ(2, opt2.value());
+ swap(opt_empty, opt1);
+ ASSERT_FALSE(opt_empty);
+ ASSERT_TRUE(opt1);
+ ASSERT_EQ(1, opt1.value());
+ ASSERT_TRUE(opt2);
+ ASSERT_EQ(2, opt2.value());
+ swap(opt1, opt2);
+ ASSERT_FALSE(opt_empty);
+ ASSERT_TRUE(opt1);
+ ASSERT_EQ(2, opt1.value());
+ ASSERT_TRUE(opt2);
+ ASSERT_EQ(1, opt2.value());
+
+ ASSERT_TRUE(noexcept(opt1.swap(opt2)));
+ ASSERT_TRUE(noexcept(swap(opt1, opt2)));
+}
+
+TEST(OptionalTest, make_optional) {
+ auto opt_int = butil::make_optional(1);
+ ASSERT_TRUE((std::is_same<decltype(opt_int),
butil::optional<int>>::value));
+ ASSERT_EQ(1, opt_int);
+}
+
+TEST(OptionalTest, comparison) {
+ butil::optional<int> empty;
+ butil::optional<int> one = 1;
+ butil::optional<int> two = 2;
+ ASSERT_TRUE(empty == empty);
+ ASSERT_FALSE(empty == one);
+ ASSERT_FALSE(empty == two);
+ ASSERT_TRUE(empty == butil::nullopt);
+ ASSERT_TRUE(one == one);
+ ASSERT_FALSE(one == two);
+ ASSERT_FALSE(one == butil::nullopt);
+ ASSERT_TRUE(two == two);
+ ASSERT_FALSE(two == butil::nullopt);
+
+ ASSERT_FALSE(empty != empty);
+ ASSERT_TRUE(empty != one);
+ ASSERT_TRUE(empty != two);
+ ASSERT_FALSE(empty != butil::nullopt);
+ ASSERT_FALSE(one != one);
+ ASSERT_TRUE(one != two);
+ ASSERT_TRUE(one != butil::nullopt);
+ ASSERT_FALSE(two != two);
+ ASSERT_TRUE(two != butil::nullopt);
+
+ ASSERT_FALSE(empty < empty);
+ ASSERT_TRUE(empty < one);
+ ASSERT_TRUE(empty < two);
+ ASSERT_FALSE(empty < butil::nullopt);
+ ASSERT_FALSE(one < one);
+ ASSERT_TRUE(one < two);
+ ASSERT_FALSE(one < butil::nullopt);
+ ASSERT_FALSE(two < two);
+ ASSERT_FALSE(two < butil::nullopt);
+
+ ASSERT_TRUE(empty <= empty);
+ ASSERT_TRUE(empty <= one);
+ ASSERT_TRUE(empty <= two);
+ ASSERT_TRUE(empty <= butil::nullopt);
+ ASSERT_TRUE(one <= one);
+ ASSERT_TRUE(one <= two);
+ ASSERT_FALSE(one <= butil::nullopt);
+ ASSERT_TRUE(two <= two);
+ ASSERT_FALSE(two <= butil::nullopt);
+
+ ASSERT_FALSE(empty > empty);
+ ASSERT_FALSE(empty > one);
+ ASSERT_FALSE(empty > two);
+ ASSERT_FALSE(empty > butil::nullopt);
+ ASSERT_FALSE(one > one);
+ ASSERT_FALSE(one > two);
+ ASSERT_TRUE(one > butil::nullopt);
+ ASSERT_FALSE(two > two);
+ ASSERT_TRUE(two > butil::nullopt);
+
+ ASSERT_TRUE(empty >= empty);
+ ASSERT_FALSE(empty >= one);
+ ASSERT_FALSE(empty >= two);
+ ASSERT_TRUE(empty >= butil::nullopt);
+ ASSERT_TRUE(one >= one);
+ ASSERT_FALSE(one >= two);
+ ASSERT_TRUE(one >= butil::nullopt);
+ ASSERT_TRUE(two >= two);
+ ASSERT_TRUE(two >= butil::nullopt);
+}
+
+} // namespace
diff --git a/test/scope_guard_unittest.cc b/test/scope_guard_unittest.cpp
similarity index 100%
rename from test/scope_guard_unittest.cc
rename to test/scope_guard_unittest.cpp
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
