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 4f85335d Fix invalid headers of multiple cookie and set-cookie (#2577)
4f85335d is described below
commit 4f85335dab82eb142383f52a81db3cc7376bb1b4
Author: Bright Chen <[email protected]>
AuthorDate: Mon Jun 3 16:47:44 2024 +0800
Fix invalid headers of multiple cookie and set-cookie (#2577)
* Fix invalid headers of multiple cookie and set-cookie
* Support MultiFlatMap
* Remove unused header
---
src/brpc/details/http_message.cpp | 13 +-
src/brpc/details/http_message.h | 4 +-
src/brpc/http_header.cpp | 113 +++++++++++----
src/brpc/http_header.h | 69 +++++++--
src/butil/containers/case_ignored_flat_map.h | 4 +
src/butil/containers/flat_map.h | 175 +++++++++++++----------
src/butil/containers/flat_map_inl.h | 206 +++++++++++++++++++++------
test/brpc_http_message_unittest.cpp | 116 +++++++++++++++
test/brpc_http_rpc_protocol_unittest.cpp | 1 +
test/flat_map_unittest.cpp | 184 ++++++++++++++++++++++--
10 files changed, 713 insertions(+), 172 deletions(-)
diff --git a/src/brpc/details/http_message.cpp
b/src/brpc/details/http_message.cpp
index 1dbef801..708f9415 100644
--- a/src/brpc/details/http_message.cpp
+++ b/src/brpc/details/http_message.cpp
@@ -99,10 +99,17 @@ int HttpMessage::on_header_value(http_parser *parser,
LOG(ERROR) << "Header name is empty";
return -1;
}
- http_message->_cur_value =
- &http_message->header().GetOrAddHeader(http_message->_cur_header);
+ HttpHeader& header = http_message->header();
+ if (header.CanFoldedInLine(http_message->_cur_header)) {
+ http_message->_cur_value =
+ &header.GetOrAddHeader(http_message->_cur_header);
+ } else {
+ http_message->_cur_value =
+ &header.AddHeader(http_message->_cur_header);
+ }
if (http_message->_cur_value && !http_message->_cur_value->empty()) {
- http_message->_cur_value->push_back(',');
+ http_message->_cur_value->append(
+ header.HeaderValueDelimiter(http_message->_cur_header));
}
}
if (http_message->_cur_value) {
diff --git a/src/brpc/details/http_message.h b/src/brpc/details/http_message.h
index 1b2ae26c..b86ffdd9 100644
--- a/src/brpc/details/http_message.h
+++ b/src/brpc/details/http_message.h
@@ -68,8 +68,8 @@ public:
HttpMethod request_method() const { return _request_method; }
- HttpHeader &header() { return _header; }
- const HttpHeader &header() const { return _header; }
+ HttpHeader& header() { return _header; }
+ const HttpHeader& header() const { return _header; }
size_t parsed_length() const { return _parsed_length; }
// Http parser callback functions
diff --git a/src/brpc/http_header.cpp b/src/brpc/http_header.cpp
index 5dbbd7ab..aef40b17 100644
--- a/src/brpc/http_header.cpp
+++ b/src/brpc/http_header.cpp
@@ -22,33 +22,19 @@
namespace brpc {
+const char* HttpHeader::SET_COOKIE = "set-cookie";
+const char* HttpHeader::COOKIE = "cookie";
+const char* HttpHeader::CONTENT_TYPE = "content-type";
+
HttpHeader::HttpHeader()
: _status_code(HTTP_STATUS_OK)
, _method(HTTP_METHOD_GET)
- , _version(1, 1) {
+ , _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.
}
-void HttpHeader::RemoveHeader(const char* key) {
- if (IsContentType(key)) {
- _content_type.clear();
- } else {
- _headers.erase(key);
- }
-}
-
-void HttpHeader::AppendHeader(const std::string& key,
- const butil::StringPiece& value) {
- std::string& slot = GetOrAddHeader(key);
- if (slot.empty()) {
- slot.assign(value.data(), value.size());
- } else {
- slot.reserve(slot.size() + 1 + value.size());
- slot.push_back(',');
- slot.append(value.data(), value.size());
- }
-}
-
void HttpHeader::Swap(HttpHeader &rhs) {
_headers.swap(rhs._headers);
_uri.Swap(rhs._uri);
@@ -69,6 +55,67 @@ void HttpHeader::Clear() {
_version = std::make_pair(1, 1);
}
+const std::string* HttpHeader::GetHeader(const char* key) const {
+ return GetHeader(std::string(key));
+}
+
+const std::string* HttpHeader::GetHeader(const std::string& key) const {
+ if (IsSetCookie(key)) {
+ return _first_set_cookie;
+ }
+ std::string* val = _headers.seek(key);
+ return val;
+}
+
+std::vector<const std::string*> HttpHeader::GetAllSetCookieHeader() const {
+ return GetMultiLineHeaders(SET_COOKIE);
+}
+
+std::vector<const std::string*>
+HttpHeader::GetMultiLineHeaders(const std::string& key) const {
+ std::vector<const std::string*> headers;
+ for (const auto& iter : _headers) {
+ if (_header_key_equal(iter.first, key)) {
+ headers.push_back(&iter.second);
+ }
+ }
+ return headers;
+}
+
+void HttpHeader::SetHeader(const std::string& key,
+ const std::string& value) {
+ GetOrAddHeader(key) = value;
+}
+
+void HttpHeader::RemoveHeader(const char* key) {
+ if (IsContentType(key)) {
+ _content_type.clear();
+ } else {
+ _headers.erase(key);
+ if (IsSetCookie(key)) {
+ _first_set_cookie = NULL;
+ }
+ }
+}
+
+void HttpHeader::AppendHeader(const std::string& key,
+ const butil::StringPiece& value) {
+ if (!CanFoldedInLine(key)) {
+ // Add a new Set-Cookie header field.
+ std::string& slot = AddHeader(key);
+ slot.assign(value.data(), value.size());
+ } else {
+ std::string& slot = GetOrAddHeader(key);
+ if (slot.empty()) {
+ slot.assign(value.data(), value.size());
+ } else {
+ slot.reserve(slot.size() + 1 + value.size());
+ slot.append(HeaderValueDelimiter(key));
+ slot.append(value.data(), value.size());
+ }
+ }
+}
+
const char* HttpHeader::reason_phrase() const {
return HttpReasonPhrase(_status_code);
}
@@ -82,10 +129,28 @@ std::string& HttpHeader::GetOrAddHeader(const std::string&
key) {
return _content_type;
}
- if (!_headers.initialized()) {
- _headers.init(29);
+ bool is_set_cookie = IsSetCookie(key);
+ // Only returns the first Set-Cookie header field for compatibility.
+ if (is_set_cookie && NULL != _first_set_cookie) {
+ return *_first_set_cookie;
+ }
+
+ std::string* val = _headers.seek(key);
+ if (NULL == val) {
+ val = _headers.insert({ key, "" });
+ if (is_set_cookie) {
+ _first_set_cookie = val;
+ }
+ }
+ return *val;
+}
+
+std::string& HttpHeader::AddHeader(const std::string& key) {
+ std::string* val = _headers.insert({ key, "" });
+ if (IsSetCookie(key) && NULL == _first_set_cookie) {
+ _first_set_cookie = val;
}
- return _headers[key];
+ return *val;
}
const HttpHeader& DefaultHttpHeader() {
diff --git a/src/brpc/http_header.h b/src/brpc/http_header.h
index c5af6448..39b2fa9b 100644
--- a/src/brpc/http_header.h
+++ b/src/brpc/http_header.h
@@ -19,6 +19,7 @@
#ifndef BRPC_HTTP_HEADER_H
#define BRPC_HTTP_HEADER_H
+#include <vector>
#include "butil/strings/string_piece.h" // StringPiece
#include "butil/containers/case_ignored_flat_map.h"
#include "brpc/uri.h" // URI
@@ -39,7 +40,7 @@ class H2StreamContext;
// Non-body part of a HTTP message.
class HttpHeader {
public:
- typedef butil::CaseIgnoredFlatMap<std::string> HeaderMap;
+ typedef butil::CaseIgnoredMultiFlatMap<std::string> HeaderMap;
typedef HeaderMap::const_iterator HeaderIterator;
typedef HeaderMap::key_equal HeaderKeyEqual;
@@ -80,24 +81,39 @@ public:
// Return pointer to the value, NULL on not found.
// NOTE: If the key is "Content-Type", `GetHeader("Content-Type")'
// (case-insensitive) is equal to `content_type()'.
- const std::string* GetHeader(const char* key) const
- { return _headers.seek(key); }
- const std::string* GetHeader(const std::string& key) const
- { return _headers.seek(key); }
+ const std::string* GetHeader(const char* key) const;
+ const std::string* GetHeader(const std::string& key) const;
+
+ std::vector<const std::string*> GetAllSetCookieHeader() const;
// Set value of a header.
// NOTE: If the key is "Content-Type", `SetHeader("Content-Type", ...)'
// (case-insensitive) is equal to `set_content_type(...)'.
- void SetHeader(const std::string& key, const std::string& value)
- { GetOrAddHeader(key) = value; }
+ void SetHeader(const std::string& key, const std::string& value);
- // Remove a header.
+ // Remove all headers of key.
void RemoveHeader(const char* key);
void RemoveHeader(const std::string& key) { RemoveHeader(key.c_str()); }
// Append value to a header. If the header already exists, separate
- // old value and new value with comma(,) according to:
- // https://www.w3.org/Protocols/rfc2616/rfc2616-sec4.html#sec4.2
+ // old value and new value with comma(,), two-byte delimiter of "; "
+ // or into a new header field, according to:
+ //
+ // https://datatracker.ietf.org/doc/html/rfc2616#section-4.2
+ // Multiple message-header fields with the same field-name MAY be
+ // present in a message if and only if the entire field-value for that
+ // header field is defined as a comma-separated list [i.e., #(values)].
+ //
+ // https://datatracker.ietf.org/doc/html/rfc9114#section-4.2.1
+ // If a decompressed field section contains multiple cookie field lines,
+ // these MUST be concatenated into a single byte string using the two-byte
+ // delimiter of "; " (ASCII 0x3b, 0x20) before being passed into a context
+ // other than HTTP/2 or HTTP/3, such as an HTTP/1.1 connection, or a
generic
+ // HTTP server application.
+ //
+ // https://datatracker.ietf.org/doc/html/rfc6265#section-3
+ // Origin servers SHOULD NOT fold multiple Set-Cookie header
+ // fields into a single header field.
void AppendHeader(const std::string& key, const butil::StringPiece& value);
// Get header iterators which are invalidated after calling AppendHeader()
@@ -145,12 +161,40 @@ friend class HttpMessageSerializer;
friend class policy::H2StreamContext;
friend void policy::ProcessHttpRequest(InputMessageBase *msg);
+ static const char* SET_COOKIE;
+ static const char* COOKIE;
+ static const char* CONTENT_TYPE;
+
+ std::vector<const std::string*> GetMultiLineHeaders(const std::string&
key) const;
+
std::string& GetOrAddHeader(const std::string& key);
- static bool IsContentType(const std::string& key) {
- return HeaderKeyEqual()(key, "content-type");
+ std::string& AddHeader(const std::string& key);
+
+ bool IsSetCookie(const std::string& key) const {
+ return _header_key_equal(key, SET_COOKIE);
+ }
+
+ bool IsCookie(const std::string& key) const {
+ return _header_key_equal(key, COOKIE);
+ }
+
+ bool IsContentType(const std::string& key) const {
+ return _header_key_equal(key, CONTENT_TYPE);
+ }
+
+ // Return true if the header can be folded in line,
+ // otherwise, returns false, i.e., Set-Cookie header.
+ // See comments of `AppendHeader'.
+ bool CanFoldedInLine(const std::string& key) {
+ return !IsSetCookie(key);
+ }
+
+ const char* HeaderValueDelimiter(const std::string& key) {
+ return IsCookie(key) ? "; " : ",";
}
+ HeaderKeyEqual _header_key_equal;
HeaderMap _headers;
URI _uri;
int _status_code;
@@ -158,6 +202,7 @@ friend void policy::ProcessHttpRequest(InputMessageBase
*msg);
std::string _content_type;
std::string _unresolved_path;
std::pair<int, int> _version;
+ std::string* _first_set_cookie;
};
const HttpHeader& DefaultHttpHeader();
diff --git a/src/butil/containers/case_ignored_flat_map.h
b/src/butil/containers/case_ignored_flat_map.h
index 30cfdda6..909e7317 100644
--- a/src/butil/containers/case_ignored_flat_map.h
+++ b/src/butil/containers/case_ignored_flat_map.h
@@ -68,6 +68,10 @@ class CaseIgnoredFlatMap : public butil::FlatMap<
class CaseIgnoredFlatSet : public butil::FlatSet<
std::string, CaseIgnoredHasher, CaseIgnoredEqual> {};
+template <typename T>
+class CaseIgnoredMultiFlatMap : public butil::FlatMap<
+ std::string, T, CaseIgnoredHasher, CaseIgnoredEqual, false, PtAllocator,
true> {};
+
} // namespace butil
#endif // BUTIL_CASE_IGNORED_FLAT_MAP_H
diff --git a/src/butil/containers/flat_map.h b/src/butil/containers/flat_map.h
index 50f44540..f0d1d1ca 100644
--- a/src/butil/containers/flat_map.h
+++ b/src/butil/containers/flat_map.h
@@ -23,72 +23,72 @@
// fastest hashmap for small-sized key/value ever.
//
// Performance comparisons between several maps:
-// [ value = 8 bytes ]
-// Sequentially inserting 100 into
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 11/108/55/58
-// Sequentially erasing 100 from
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 7/123/55/37
-// Sequentially inserting 1000 into
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 10/92/55/54
-// Sequentially erasing 1000 from
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/67/51/35
-// Sequentially inserting 10000 into
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 10/100/66/54
-// Sequentially erasing 10000 from
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/72/55/35
-// [ value = 32 bytes ]
-// Sequentially inserting 100 into
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 14/108/56/56
-// Sequentially erasing 100 from
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/77/53/38
-// Sequentially inserting 1000 into
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 14/94/54/53
-// Sequentially erasing 1000 from
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 4/66/49/36
-// Sequentially inserting 10000 into
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 13/106/62/54
-// Sequentially erasing 10000 from
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 4/69/53/36
-// [ value = 128 bytes ]
-// Sequentially inserting 100 into
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 31/182/96/96
-// Sequentially erasing 100 from
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 8/117/51/44
-// Sequentially inserting 1000 into
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 29/191/100/97
-// Sequentially erasing 1000 from
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/100/49/44
-// Sequentially inserting 10000 into
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 30/184/113/114
-// Sequentially erasing 10000 from
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/99/52/43
-// [ value = 8 bytes ]
-// Randomly inserting 100 into
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 11/171/108/60
-// Randomly erasing 100 from
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 8/158/126/37
-// Randomly inserting 1000 into
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 10/159/117/54
-// Randomly erasing 1000 from
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/153/135/36
-// Randomly inserting 10000 into
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 12/223/180/55
-// Randomly erasing 10000 from
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 7/237/210/48
-// [ value = 32 bytes ]
-// Randomly inserting 100 into
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 16/179/108/57
-// Randomly erasing 100 from
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 5/157/120/38
-// Randomly inserting 1000 into
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 15/168/127/54
-// Randomly erasing 1000 from
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 5/164/135/39
-// Randomly inserting 10000 into
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 19/241/201/56
-// Randomly erasing 10000 from
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 5/235/218/54
-// [ value = 128 bytes ]
-// Randomly inserting 100 into
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 35/242/154/97
-// Randomly erasing 100 from
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 7/185/119/56
-// Randomly inserting 1000 into
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 35/262/182/99
-// Randomly erasing 1000 from
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/215/157/66
-// Randomly inserting 10000 into
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 44/330/278/114
-// Randomly erasing 10000 from
FlatMap/std::map/butil::PooledMap/butil::hash_map takes 6/307/242/90
-// [ value = 8 bytes ]
-// Seeking 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes
6/51/52/13
-// Seeking 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes
4/98/82/14
-// Seeking 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes
4/175/170/14
-// [ value = 32 bytes ]
-// Seeking 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes
3/52/52/14
-// Seeking 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes
3/84/82/13
-// Seeking 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes
3/164/156/14
-// [ value = 128 bytes ]
-// Seeking 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes
3/54/53/14
-// Seeking 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes
4/88/90/13
-// Seeking 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes
4/178/185/14
-// [ value = 8 bytes ]
-// Seeking 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes
5/51/49/14
-// Seeking 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes
4/86/94/14
-// Seeking 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes
4/177/171/14
-// [ value = 32 bytes ]
-// Seeking 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes
3/51/53/14
-// Seeking 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes
3/98/82/13
-// Seeking 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes
3/163/156/14
-// [ value = 128 bytes ]
-// Seeking 100 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes
3/55/53/14
-// Seeking 1000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes
4/88/89/13
-// Seeking 10000 from FlatMap/std::map/butil::PooledMap/butil::hash_map takes
4/177/185/14
+// [ value = 8 bytes ]
+// Sequentially inserting 100 into
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 20/20/300/290/2010/210/230
+// Sequentially erasing 100 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 20/20/1700/150/160/170/250
+// Sequentially inserting 1000 into
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 16/15/360/342/206/195/219
+// Sequentially erasing 1000 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 15/18/178/159/149/159/149
+// Sequentially inserting 10000 into
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 15/15/415/410/200/192/235
+// Sequentially erasing 10000 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 14/17/201/181/151/181/154
+// [ value = 32 bytes ]
+// Sequentially inserting 100 into
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 20/10/280/280/250/200/230
+// Sequentially erasing 100 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 20/10/2070/150/160/160/160
+// Sequentially inserting 1000 into
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 17/17/330/329/207/185/212
+// Sequentially erasing 1000 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 13/17/172/163/146/157/148
+// Sequentially inserting 10000 into
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 17/17/405/406/197/185/215
+// Sequentially erasing 10000 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 13/16/206/188/158/168/159
+// [ value = 128 bytes ]
+// Sequentially inserting 100 into
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 20/30/290/290/420/220/250
+// Sequentially erasing 100 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 20/10/180/150/160/160/160
+// Sequentially inserting 1000 into
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 22/25/352/349/213/193/222
+// Sequentially erasing 1000 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 13/17/170/165/160/171/157
+// Sequentially inserting 10000 into
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 21/24/416/422/210/206/242
+// Sequentially erasing 10000 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 16/16/213/190/163/171/159
+// [ value = 8 bytes ]
+// Randomly inserting 100 into
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 20/20/290/260/250/220/220
+// Randomly erasing 100 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 20/20/240/220/170/170/180
+// Randomly inserting 1000 into
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 16/15/315/309/206/191/215
+// Randomly erasing 1000 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 15/17/258/240/155/193/156
+// Randomly inserting 10000 into
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 15/16/378/363/208/191/210
+// Randomly erasing 10000 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 14/16/311/290/162/187/169
+// [ value = 32 bytes ]
+// Randomly inserting 100 into
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 20/20/280/270/240/230/220
+// Randomly erasing 100 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 10/20/250/220/170/180/160
+// Randomly inserting 1000 into
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 18/18/310/304/209/192/209
+// Randomly erasing 1000 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 13/16/255/247/155/175/152
+// Randomly inserting 10000 into
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 17/17/381/367/209/197/214
+// Randomly erasing 10000 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 15/17/310/296/163/188/168
+// [ value = 128 bytes ]
+// Randomly inserting 100 into
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 30/40/300/290/280/230/230
+// Randomly erasing 100 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 20/20/230/220/160/180/170
+// Randomly inserting 1000 into
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 29/33/327/329/219/197/220
+// Randomly erasing 1000 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 14/16/257/247/159/182/156
+// Randomly inserting 10000 into
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 35/39/398/400/220/213/246
+// Randomly erasing 10000 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 35/36/330/319/221/224/200
+// [ value = 8 bytes ]
+// Seeking 100 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 10/20/140/130/60/70/50
+// Seeking 1000 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 13/13/172/161/77/54/46
+// Seeking 10000 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 13/16/216/211/73/56/51
+// [ value = 32 bytes ]
+// Seeking 100 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 10/20/130/130/70/60/50
+// Seeking 1000 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 13/13/174/163/73/54/49
+// Seeking 10000 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 13/13/218/217/75/58/52
+// [ value = 128 bytes ]
+// Seeking 100 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 20/10/140/130/80/50/60
+// Seeking 1000 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 13/13/173/171/73/55/49
+// Seeking 10000 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 26/22/238/252/107/89/91
+// [ value = 8 bytes ]
+// Seeking 100 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 20/10/140/130/70/50/60
+// Seeking 1000 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 13/14/180/160/68/57/47
+// Seeking 10000 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 13/13/221/210/72/57/51
+// [ value = 32 bytes ]
+// Seeking 100 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 20/10/140/130/70/60/50
+// Seeking 1000 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 13/13/167/160/69/53/50
+// Seeking 10000 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 15/14/224/219/75/59/52
+// [ value = 128 bytes ]
+// Seeking 100 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 10/10/140/130/80/50/60
+// Seeking 1000 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 13/13/170/167/70/54/52
+// Seeking 10000 from
FlatMap/MultiFlatMap/std::map/butil::PooledMap/std::unordered_map/std::unordered_multimap/butil::hash_map
takes 26/22/238/240/85/70/67
#ifndef BUTIL_FLAT_MAP_H
#define BUTIL_FLAT_MAP_H
@@ -128,7 +128,9 @@ template <typename _K, typename _T,
// stored-key is always on LHS, passed-key is always on RHS.
typename _Equal = DefaultEqualTo<_K>,
bool _Sparse = false,
- typename _Alloc = PtAllocator>
+ typename _Alloc = PtAllocator,
+ // If `_Multi' is true, allow containing multiple copies of each key
value.
+ bool _Multi = false>
class FlatMap {
public:
typedef _K key_type;
@@ -177,10 +179,17 @@ public:
// Returns address of the inserted value, NULL on error.
mapped_type* insert(const std::pair<key_type, mapped_type>& kv);
- // Remove |key| and the associated value
+ // For `_Multi=false'. (Default)
+ // Remove |key| and all associated value
// Returns: 1 on erased, 0 otherwise.
- template <typename K2>
- size_t erase(const K2& key, mapped_type* old_value = NULL);
+ template <typename K2, bool Multi = _Multi>
+ typename std::enable_if<!Multi, size_t >::type
+ erase(const K2& key, mapped_type* old_value = NULL);
+ // For `_Multi=true'.
+ // Returns: num of value on erased, 0 otherwise.
+ template <typename K2, bool Multi = _Multi>
+ typename std::enable_if<Multi, size_t >::type
+ erase(const K2& key, std::vector<mapped_type>* old_values = NULL);
// Remove all items. Allocated spaces are NOT returned by system.
void clear();
@@ -188,15 +197,19 @@ public:
// Remove all items and return all allocated spaces to system.
void clear_and_reset_pool();
- // Search for the value associated with |key|
- // Returns: address of the value
+ // Search for the value associated with |key|.
+ // If `_Multi=false', Search for any of multiple values associated with
|key|.
+ // Returns: address of the value.
template <typename K2> mapped_type* seek(const K2& key) const;
+ template <typename K2> std::vector<mapped_type*> seek_all(const K2& key)
const;
+ // For `_Multi=false'. (Default)
// Get the value associated with |key|. If |key| does not exist,
// insert with a default-constructed value. If size()*100/bucket_count()
// is more than load_factor, a resize will be done.
// Returns reference of the value
- mapped_type& operator[](const key_type& key);
+ template<bool Multi = _Multi>
+ typename std::enable_if<!Multi, mapped_type&>::type operator[](const
key_type& key);
// Resize this map. This is optional because resizing will be triggered by
// insert() or operator[] if there're too many items.
@@ -276,6 +289,15 @@ public:
private:
template <typename _Map, typename _Element> friend class FlatMapIterator;
template <typename _Map, typename _Element> friend class SparseFlatMapIterator;
+
+ // For `_Multi=true'.
+ // Insert a new default-constructed associated with |key| always.
+ // If size()*100/bucket_count() is more than load_factor,
+ // a resize will be done.
+ // Returns reference of the value
+ template<bool Multi = _Multi>
+ typename std::enable_if<Multi, mapped_type&>::type operator[](const
key_type& key);
+
// True if buckets need to be resized before holding `size' elements.
inline bool is_too_crowded(size_t size) const
{ return size * 100 >= _nbucket * _load_factor; }
@@ -290,6 +312,13 @@ template <typename _Map, typename _Element> friend class
SparseFlatMapIterator;
SingleThreadedPool<sizeof(Bucket), 1024, 16, allocator_type> _pool;
};
+template <typename _K, typename _T,
+ typename _Hash = DefaultHasher<_K>,
+ typename _Equal = DefaultEqualTo<_K>,
+ bool _Sparse = false,
+ typename _Alloc = PtAllocator>
+using MultiFlatMap = FlatMap<_K, _T, _Hash, _Equal, _Sparse, _Alloc, true>;
+
template <typename _K,
typename _Hash = DefaultHasher<_K>,
typename _Equal = DefaultEqualTo<_K>,
diff --git a/src/butil/containers/flat_map_inl.h
b/src/butil/containers/flat_map_inl.h
index 65830368..5218fab9 100644
--- a/src/butil/containers/flat_map_inl.h
+++ b/src/butil/containers/flat_map_inl.h
@@ -225,8 +225,8 @@ friend class SparseFlatMapIterator<Map, ConstValue>;
};
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A>
-FlatMap<_K, _T, _H, _E, _S, _A>::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)
@@ -237,8 +237,8 @@ FlatMap<_K, _T, _H, _E, _S, _A>::FlatMap(const hasher&
hashfn, const key_equal&
, _pool(alloc)
{}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A>
-FlatMap<_K, _T, _H, _E, _S, _A>::~FlatMap() {
+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;
@@ -248,8 +248,8 @@ FlatMap<_K, _T, _H, _E, _S, _A>::~FlatMap() {
_load_factor = 0;
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A>
-FlatMap<_K, _T, _H, _E, _S, _A>::FlatMap(const FlatMap& rhs)
+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)
@@ -260,9 +260,9 @@ FlatMap<_K, _T, _H, _E, _S, _A>::FlatMap(const FlatMap& rhs)
operator=(rhs);
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A>
-FlatMap<_K, _T, _H, _E, _S, _A>&
-FlatMap<_K, _T, _H, _E, _S, _A>::operator=(const FlatMap<_K, _T, _H, _E, _S,
_A>& rhs) {
+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) {
if (this == &rhs) {
return *this;
}
@@ -334,8 +334,8 @@ FlatMap<_K, _T, _H, _E, _S, _A>::operator=(const
FlatMap<_K, _T, _H, _E, _S, _A>
return *this;
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A>
-int FlatMap<_K, _T, _H, _E, _S, _A>::init(size_t nbucket, u_int load_factor) {
+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;
@@ -373,8 +373,8 @@ int FlatMap<_K, _T, _H, _E, _S, _A>::init(size_t nbucket,
u_int load_factor) {
return 0;
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A>
-void FlatMap<_K, _T, _H, _E, _S, _A>::swap(FlatMap<_K, _T, _H, _E, _S, _A> &
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) {
std::swap(rhs._size, _size);
std::swap(rhs._nbucket, _nbucket);
std::swap(rhs._buckets, _buckets);
@@ -385,22 +385,25 @@ void FlatMap<_K, _T, _H, _E, _S, _A>::swap(FlatMap<_K,
_T, _H, _E, _S, _A> & rhs
rhs._pool.swap(_pool);
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A>
-_T* FlatMap<_K, _T, _H, _E, _S, _A>::insert(const key_type& key,
- const mapped_type& value) {
- mapped_type *p = &operator[](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[]<_M>(key);
*p = value;
return p;
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A>
-_T* FlatMap<_K, _T, _H, _E, _S, _A>::insert(const std::pair<key_type,
mapped_type>& kv) {
+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>
-template <typename K2>
-size_t FlatMap<_K, _T, _H, _E, _S, _A>::erase(const K2& key, _T* old_value) {
+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;
}
@@ -464,8 +467,71 @@ size_t FlatMap<_K, _T, _H, _E, _S, _A>::erase(const K2&
key, _T* old_value) {
return 0;
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A>
-void FlatMap<_K, _T, _H, _E, _S, _A>::clear() {
+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;
+ }
+ // TODO: Do we need auto collapsing here?
+ const size_t index = flatmap_mod(_hashfn(key), _nbucket);
+ Bucket& first_node = _buckets[index];
+ if (!first_node.is_valid()) {
+ return 0;
+ }
+
+ Bucket* new_head = NULL;
+ Bucket* new_tail = NULL;
+ Bucket* p = &first_node;
+ size_t total = _size;
+ while (NULL != p) {
+ if (_eql(p->element().first_ref(), key)) {
+ if (NULL != old_values) {
+ old_values->push_back(p->element().second_movable_ref());
+ }
+ Bucket* temp = p;
+ p = p->next;
+ temp->element().~Element();
+ if (temp != &first_node) {
+ _pool.back(temp);
+ }
+ --_size;
+ } else {
+ if (NULL == new_head) {
+ new_head = p;
+ new_tail = p;
+ } else {
+ new_tail->next = p;
+ new_tail = new_tail->next;
+ }
+ p = p->next;
+ }
+ }
+ if (NULL != new_tail) {
+ new_tail->next = NULL;
+ }
+ if (NULL == new_head) {
+ // Erase all element.
+ first_node.set_invalid();
+ if (_S) {
+ bit_array_unset(_thumbnail, index);
+ }
+ } else if (new_head != &first_node) {
+ // The First node has been erased, need to move new head node as first
node.
+ first_node.next = new_head->next;
+ 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();
+ _pool.back(new_head);
+ }
+ return total - _size;
+}
+
+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;
}
@@ -491,15 +557,15 @@ void FlatMap<_K, _T, _H, _E, _S, _A>::clear() {
}
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A>
-void FlatMap<_K, _T, _H, _E, _S, _A>::clear_and_reset_pool() {
+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>
+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>::seek(const K2& key) const {
+_T* FlatMap<_K, _T, _H, _E, _S, _A, _M>::seek(const K2& key) const {
if (!initialized()) {
return NULL;
}
@@ -520,8 +586,34 @@ _T* FlatMap<_K, _T, _H, _E, _S, _A>::seek(const K2& key)
const {
return NULL;
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A>
-_T& FlatMap<_K, _T, _H, _E, _S, _A>::operator[](const key_type& key) {
+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;
+ }
+ if (_eql(first_node.element().first_ref(), key)) {
+ v.push_back(&first_node.element().second_ref());
+ }
+ Bucket *p = first_node.next;
+ while (p) {
+ if (_eql(p->element().first_ref(), key)) {
+ v.push_back(&p->element().second_ref());
+ }
+ p = p->next;
+ }
+ return v;
+}
+
+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];
if (!first_node.is_valid()) {
@@ -553,8 +645,28 @@ _T& FlatMap<_K, _T, _H, _E, _S, _A>::operator[](const
key_type& key) {
}
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A>
-void FlatMap<_K, _T, _H, _E, _S, _A>::save_iterator(
+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];
+ if (!first_node.is_valid()) {
+ ++_size;
+ if (_S) {
+ bit_array_set(_thumbnail, index);
+ }
+ new (&first_node) Bucket(key);
+ return first_node.element().second_ref();
+ }
+ Bucket* newp = new (_pool.get()) Bucket(key);
+ newp->next = first_node.next;
+ first_node.next = newp;
+ return newp->element().second_ref();
+}
+
+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;
hint->offset = it._entry - _buckets;
@@ -567,9 +679,9 @@ void FlatMap<_K, _T, _H, _E, _S, _A>::save_iterator(
}
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A>
-typename FlatMap<_K, _T, _H, _E, _S, _A>::const_iterator
-FlatMap<_K, _T, _H, _E, _S, _A>::restore_iterator(const PositionHint& hint)
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>::restore_iterator(const PositionHint&
hint) const {
if (hint.nbucket != _nbucket) // resized
return begin(); // restart
@@ -601,8 +713,8 @@ FlatMap<_K, _T, _H, _E, _S, _A>::restore_iterator(const
PositionHint& hint) cons
return const_iterator(this, hint.offset);
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A>
-bool FlatMap<_K, _T, _H, _E, _S, _A>::resize(size_t nbucket2) {
+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;
@@ -623,8 +735,8 @@ bool FlatMap<_K, _T, _H, _E, _S, _A>::resize(size_t
nbucket2) {
return true;
}
-template <typename _K, typename _T, typename _H, typename _E, bool _S,
typename _A>
-BucketInfo FlatMap<_K, _T, _H, _E, _S, _A>::bucket_info() const {
+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) {
@@ -644,23 +756,23 @@ 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>
-typename FlatMap<_K, _T, _H, _E, _S, _A>::iterator FlatMap<_K, _T, _H, _E, _S,
_A>::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>
-typename FlatMap<_K, _T, _H, _E, _S, _A>::iterator FlatMap<_K, _T, _H, _E, _S,
_A>::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>
-typename FlatMap<_K, _T, _H, _E, _S, _A>::const_iterator FlatMap<_K, _T, _H,
_E, _S, _A>::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>
-typename FlatMap<_K, _T, _H, _E, _S, _A>::const_iterator FlatMap<_K, _T, _H,
_E, _S, _A>::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/test/brpc_http_message_unittest.cpp
b/test/brpc_http_message_unittest.cpp
index 568162cd..651397aa 100644
--- a/test/brpc_http_message_unittest.cpp
+++ b/test/brpc_http_message_unittest.cpp
@@ -262,6 +262,71 @@ TEST(HttpMessageTest, parse_http_head_response) {
ASSERT_EQ("chunked", *transfer_encoding);
}
+TEST(HttpMessageTest, parse_http_cookie) {
+ const char* http_request =
+ "GET /CloudApiControl HTTP/1.1\r\n"
+ "Host: api.map.baidu.com\r\n"
+ "Accept: application/json\r\n"
+ "cookie: a=1\r\n"
+ "Cookie: b=2\r\n"
+ "\r\n";
+ butil::IOBuf buf;
+ buf.append(http_request);
+ brpc::HttpMessage http_message;
+ ASSERT_EQ((ssize_t)buf.size(), http_message.ParseFromIOBuf(buf));
+ ASSERT_TRUE(http_message.Completed());
+
+ const std::string* cookie
+ = http_message.header().GetHeader("cookie");
+ ASSERT_NE(nullptr, cookie);
+ ASSERT_EQ("a=1; b=2", *cookie);
+}
+
+TEST(HttpMessageTest, parse_http_set_cookie) {
+ char response[1024] = "HTTP/1.1 200 OK\r\n"
+ "Content-Type: text/plain\r\n"
+ "Content-Length: 1024\r\n"
+ "set-cookie: a=1\r\n"
+ "Set-Cookie: b=2\r\n"
+ "\r\n";
+ butil::IOBuf request;
+ request.append(response);
+ brpc::HttpMessage http_message(false, brpc::HTTP_METHOD_HEAD);
+ ASSERT_TRUE(http_message.ParseFromIOBuf(request) >= 0);
+ ASSERT_TRUE(http_message.Completed()) << http_message.stage();
+
+ const std::string* set_cookie =
http_message.header().GetHeader("set-cookie");
+ ASSERT_NE(nullptr, set_cookie);
+ ASSERT_EQ("a=1", *set_cookie);
+ std::vector<const std::string*> all_set_cookie
+ = http_message.header().GetAllSetCookieHeader();
+ for (const std::string* sc : all_set_cookie) {
+ ASSERT_NE(nullptr, sc);
+ if (set_cookie == sc) {
+ ASSERT_EQ("a=1", *sc);
+ } else {
+ ASSERT_EQ("b=2", *sc);
+ }
+ if (http_message.header().IsSetCookie(*sc)) {
+ }
+ }
+ int set_cookie_value1_count = 0;
+ int set_cookie_value2_count = 0;
+ for (auto iter = http_message.header().HeaderBegin();
+ iter != http_message.header().HeaderEnd(); ++iter) {
+ if (!http_message.header().IsSetCookie(iter->first)) {
+ continue;
+ }
+ if (iter->second == "b=2") {
+ ++set_cookie_value2_count;
+ } else if (iter->second == "a=1") {
+ ++set_cookie_value1_count;
+ }
+ }
+ ASSERT_EQ(1, set_cookie_value1_count);
+ ASSERT_EQ(1, set_cookie_value2_count);
+}
+
TEST(HttpMessageTest, cl_and_te) {
// https://datatracker.ietf.org/doc/html/rfc2616#section-14.41
// If multiple encodings have been applied to an entity, the transfer-
@@ -436,6 +501,57 @@ TEST(HttpMessageTest, http_header) {
header.RemoveHeader("key1");
ASSERT_FALSE(header.GetHeader("key1"));
+ ASSERT_FALSE(header.GetHeader(brpc::HttpHeader::COOKIE));
+ header.AppendHeader(brpc::HttpHeader::COOKIE, "value1=1");
+ value = header.GetHeader(brpc::HttpHeader::COOKIE);
+ ASSERT_TRUE(value && *value == "value1=1");
+ header.AppendHeader(brpc::HttpHeader::COOKIE, "value2=2");
+ value = header.GetHeader(brpc::HttpHeader::COOKIE);
+ ASSERT_TRUE(value && *value == "value1=1; value2=2");
+ header.SetHeader(brpc::HttpHeader::COOKIE, "value3");
+ value = header.GetHeader(brpc::HttpHeader::COOKIE);
+ ASSERT_TRUE(value && *value == "value3");
+ header.RemoveHeader(brpc::HttpHeader::COOKIE);
+ ASSERT_FALSE(header.GetHeader(brpc::HttpHeader::COOKIE));
+
+ std::string set_cookie_value1 = "a=1";
+ std::string set_cookie_value2 = "b=2";
+ std::string set_cookie_value3 = "c=3";
+ ASSERT_FALSE(header.GetHeader(brpc::HttpHeader::SET_COOKIE));
+ header.SetHeader(brpc::HttpHeader::SET_COOKIE, set_cookie_value1);
+ value = header.GetHeader(brpc::HttpHeader::SET_COOKIE);
+ ASSERT_TRUE(value && *value == set_cookie_value1);
+ header.AppendHeader(brpc::HttpHeader::SET_COOKIE, set_cookie_value2);
+ value = header.GetHeader(brpc::HttpHeader::SET_COOKIE);
+ ASSERT_TRUE(value && *value == set_cookie_value1);
+ header.SetHeader(brpc::HttpHeader::SET_COOKIE, set_cookie_value3);
+ value = header.GetHeader(brpc::HttpHeader::SET_COOKIE);
+ ASSERT_TRUE(value && *value == set_cookie_value3);
+ std::vector<const std::string*> all_set_cookie
+ = header.GetAllSetCookieHeader();
+ ASSERT_EQ(2u, all_set_cookie.size());
+ for (const std::string* sc : all_set_cookie) {
+ ASSERT_TRUE(sc);
+ ASSERT_TRUE(*sc == set_cookie_value2 || *sc == set_cookie_value3);
+ }
+ int set_cookie_value2_count = 0;
+ int set_cookie_value3_count = 0;
+ for (auto iter = header.HeaderBegin(); iter != header.HeaderEnd(); ++iter)
{
+ if (!header.IsSetCookie(brpc::HttpHeader::SET_COOKIE)) {
+ continue;
+ }
+ if (iter->second == set_cookie_value2) {
+ ++set_cookie_value2_count;
+ } else if (iter->second == set_cookie_value3) {
+ ++set_cookie_value3_count;
+ }
+ }
+ ASSERT_EQ(1, set_cookie_value2_count);
+ ASSERT_EQ(1, set_cookie_value3_count);
+ header.RemoveHeader(brpc::HttpHeader::SET_COOKIE);
+ ASSERT_FALSE(header.GetHeader(brpc::HttpHeader::SET_COOKIE));
+ ASSERT_EQ(header._first_set_cookie, nullptr);
+
ASSERT_EQ(brpc::HTTP_METHOD_GET, header.method());
header.set_method(brpc::HTTP_METHOD_POST);
ASSERT_EQ(brpc::HTTP_METHOD_POST, header.method());
diff --git a/test/brpc_http_rpc_protocol_unittest.cpp
b/test/brpc_http_rpc_protocol_unittest.cpp
index b4e0547c..f4bdec95 100644
--- a/test/brpc_http_rpc_protocol_unittest.cpp
+++ b/test/brpc_http_rpc_protocol_unittest.cpp
@@ -59,6 +59,7 @@ namespace brpc {
DECLARE_bool(rpc_dump);
DECLARE_string(rpc_dump_dir);
DECLARE_int32(rpc_dump_max_requests_in_one_file);
+DECLARE_bool(allow_chunked_length);
extern bvar::CollectorSpeedLimit g_rpc_dump_sl;
}
diff --git a/test/flat_map_unittest.cpp b/test/flat_map_unittest.cpp
index d689bdf1..5d9850d7 100644
--- a/test/flat_map_unittest.cpp
+++ b/test/flat_map_unittest.cpp
@@ -19,6 +19,7 @@
#include <stdio.h>
#include <stdlib.h>
#include <map>
+#include <unordered_map>
#include <vector>
#include "butil/time.h"
#include "butil/macros.h"
@@ -1107,23 +1108,28 @@ TEST_F(FlatMapTest, random_insert_erase) {
<< "n_cp:" << n_cp;
}
-template <typename T> void perf_insert_erase(bool random, const T& value)
-{
+template <typename T>
+void perf_insert_erase(bool random, const T& value) {
size_t nkeys[] = { 100, 1000, 10000 };
const size_t NPASS = ARRAY_SIZE(nkeys);
std::vector<uint64_t> keys;
butil::FlatMap<uint64_t, T> id_map;
+ butil::MultiFlatMap<uint64_t, T> multi_id_map;
std::map<uint64_t, T> std_map;
butil::PooledMap<uint64_t, T> pooled_map;
+ std::unordered_map<uint64_t, T> std_unordered_map;
+ std::unordered_multimap<uint64_t, T> std_unordered_multimap;
butil::hash_map<uint64_t, T> hash_map;
- butil::Timer id_tm, std_tm, pooled_tm, hash_tm;
+ butil::Timer id_tm, multi_id_tm, std_tm, pooled_tm,
+ std_unordered_tm, std_unordered_multi_tm, hash_tm;
size_t max_nkeys = 0;
for (size_t i = 0; i < NPASS; ++i) {
max_nkeys = std::max(max_nkeys, nkeys[i]);
}
id_map.init((size_t)(nkeys[NPASS-1] * 1.5));
+ multi_id_map.init((size_t)(nkeys[NPASS-1] * 1.5));
// Make DS hot
for (size_t i = 0; i < max_nkeys; ++i) {
@@ -1135,6 +1141,8 @@ template <typename T> void perf_insert_erase(bool random,
const T& value)
id_map.clear();
std_map.clear();
pooled_map.clear();
+ std_unordered_map.clear();
+ std_unordered_multimap.clear();
hash_map.clear();
LOG(INFO) << "[ value = " << sizeof(T) << " bytes ]";
@@ -1156,6 +1164,13 @@ template <typename T> void perf_insert_erase(bool
random, const T& value)
}
id_tm.stop();
+ multi_id_map.clear();
+ multi_id_tm.start();
+ for (size_t i = 0; i < keys.size(); ++i) {
+ multi_id_map[keys[i]] = value;
+ }
+ multi_id_tm.stop();
+
std_map.clear();
std_tm.start();
for (size_t i = 0; i < keys.size(); ++i) {
@@ -1170,6 +1185,20 @@ template <typename T> void perf_insert_erase(bool
random, const T& value)
}
pooled_tm.stop();
+ std_unordered_map.clear();
+ std_unordered_tm.start();
+ for (size_t i = 0; i < keys.size(); ++i) {
+ std_unordered_map[keys[i]] = value;
+ }
+ std_unordered_tm.stop();
+
+ std_unordered_multimap.clear();
+ std_unordered_multi_tm.start();
+ for (size_t i = 0; i < keys.size(); ++i) {
+ std_unordered_multimap.insert({ keys[i], value });
+ }
+ std_unordered_multi_tm.stop();
+
hash_map.clear();
hash_tm.start();
for (size_t i = 0; i < keys.size(); ++i) {
@@ -1179,10 +1208,14 @@ template <typename T> void perf_insert_erase(bool
random, const T& value)
LOG(INFO) << (random ? "Randomly" : "Sequentially")
<< " inserting " << keys.size()
- << " into FlatMap/std::map/butil::PooledMap/butil::hash_map
takes "
+ << " into FlatMap/MultiFlatMap/std::map/butil::PooledMap/"
+
"std::unordered_map/std::unordered_multimap/butil::hash_map takes "
<< id_tm.n_elapsed() / keys.size()
+ << "/" << multi_id_tm.n_elapsed() / keys.size()
<< "/" << std_tm.n_elapsed() / keys.size()
<< "/" << pooled_tm.n_elapsed() / keys.size()
+ << "/" << std_unordered_tm.n_elapsed() / keys.size()
+ << "/" << std_unordered_multi_tm.n_elapsed() / keys.size()
<< "/" << hash_tm.n_elapsed() / keys.size();
if (random) {
@@ -1195,6 +1228,12 @@ template <typename T> void perf_insert_erase(bool
random, const T& value)
}
id_tm.stop();
+ multi_id_tm.start();
+ for (size_t i = 0; i < keys.size(); ++i) {
+ multi_id_map.erase(keys[i]);
+ }
+ multi_id_tm.stop();
+
std_tm.start();
for (size_t i = 0; i < keys.size(); ++i) {
std_map.erase(keys[i]);
@@ -1207,6 +1246,18 @@ template <typename T> void perf_insert_erase(bool
random, const T& value)
}
pooled_tm.stop();
+ std_unordered_tm.start();
+ for (size_t i = 0; i < keys.size(); ++i) {
+ std_unordered_map.erase(keys[i]);
+ }
+ std_unordered_tm.stop();
+
+ std_unordered_multi_tm.start();
+ for (size_t i = 0; i < keys.size(); ++i) {
+ std_unordered_multimap.erase(keys[i]);
+ }
+ std_unordered_multi_tm.stop();
+
hash_tm.start();
for (size_t i = 0; i < keys.size(); ++i) {
hash_map.erase(keys[i]);
@@ -1215,27 +1266,36 @@ template <typename T> void perf_insert_erase(bool
random, const T& value)
LOG(INFO) << (random ? "Randomly" : "Sequentially")
<< " erasing " << keys.size()
- << " from FlatMap/std::map/butil::PooledMap/butil::hash_map
takes "
+ << " from FlatMap/MultiFlatMap/std::map/butil::PooledMap/"
+
"std::unordered_map/std::unordered_multimap/butil::hash_map takes "
<< id_tm.n_elapsed() / keys.size()
+ << "/" << multi_id_tm.n_elapsed() / keys.size()
<< "/" << std_tm.n_elapsed() / keys.size()
<< "/" << pooled_tm.n_elapsed() / keys.size()
+ << "/" << std_unordered_tm.n_elapsed() / keys.size()
+ << "/" << std_unordered_multi_tm.n_elapsed() / keys.size()
<< "/" << hash_tm.n_elapsed() / keys.size();
}
}
-template <typename T> void perf_seek(const T& value) {
+template <typename T>
+void perf_seek(const T& value) {
size_t nkeys[] = { 100, 1000, 10000 };
const size_t NPASS = ARRAY_SIZE(nkeys);
std::vector<uint64_t> keys;
std::vector<uint64_t> rkeys;
butil::FlatMap<uint64_t, T> id_map;
+ butil::MultiFlatMap<uint64_t, T> multi_id_map;
std::map<uint64_t, T> std_map;
butil::PooledMap<uint64_t, T> pooled_map;
+ std::unordered_map<uint64_t, T> std_unordered_map;
+ std::unordered_multimap<uint64_t, T> std_unordered_multimap;
butil::hash_map<uint64_t, T> hash_map;
-
- butil::Timer id_tm, std_tm, pooled_tm, hash_tm;
+ 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 ]";
for (size_t pass = 0; pass < NPASS; ++pass) {
int start = rand();
@@ -1249,6 +1309,11 @@ template <typename T> void perf_seek(const T& value) {
id_map[keys[i]] = value;
}
+ multi_id_map.clear();
+ for (size_t i = 0; i < keys.size(); ++i) {
+ multi_id_map[keys[i]] = value;
+ }
+
std_map.clear();
for (size_t i = 0; i < keys.size(); ++i) {
std_map[keys[i]] = value;
@@ -1259,6 +1324,16 @@ template <typename T> void perf_seek(const T& value) {
pooled_map[keys[i]] = value;
}
+ std_unordered_map.clear();
+ for (size_t i = 0; i < keys.size(); ++i) {
+ std_unordered_map[keys[i]] = value;
+ }
+
+ std_unordered_multimap.clear();
+ for (size_t i = 0; i < keys.size(); ++i) {
+ std_unordered_multimap.insert({ keys[i], value });
+ }
+
hash_map.clear();
for (size_t i = 0; i < keys.size(); ++i) {
hash_map[keys[i]] = value;
@@ -1273,6 +1348,12 @@ template <typename T> void perf_seek(const T& value) {
}
id_tm.stop();
+ multi_id_tm.start();
+ for (size_t i = 0; i < keys.size(); ++i) {
+ sum += *(long*)multi_id_map.seek(keys[i]);
+ }
+ multi_id_tm.stop();
+
std_tm.start();
for (size_t i = 0; i < keys.size(); ++i) {
sum += (long&)std_map.find(keys[i])->second;
@@ -1285,6 +1366,18 @@ template <typename T> void perf_seek(const T& value) {
}
pooled_tm.stop();
+ std_unordered_tm.start();
+ for (size_t i = 0; i < keys.size(); ++i) {
+ sum += (long&)std_unordered_map[keys[i]];
+ }
+ std_unordered_tm.stop();
+
+ std_unordered_multi_tm.start();
+ for (size_t i = 0; i < keys.size(); ++i) {
+ sum += (long&)std_unordered_multimap.find(keys[i])->second;
+ }
+ std_unordered_multi_tm.stop();
+
hash_tm.start();
for (size_t i = 0; i < keys.size(); ++i) {
sum += (long&)hash_map.find(keys[i])->second;
@@ -1292,12 +1385,15 @@ template <typename T> void perf_seek(const T& value) {
hash_tm.stop();
LOG(INFO) << "Seeking " << keys.size()
- << " from FlatMap/std::map/butil::PooledMap/butil::hash_map
takes "
+ << " from FlatMap/MultiFlatMap/std::map/butil::PooledMap/"
+
"std::unordered_map/std::unordered_multimap/butil::hash_map takes "
<< id_tm.n_elapsed() / keys.size()
+ << "/" << multi_id_tm.n_elapsed() / keys.size()
<< "/" << std_tm.n_elapsed() / keys.size()
<< "/" << pooled_tm.n_elapsed() / keys.size()
- << "/" << hash_tm.n_elapsed() / keys.size()
- << " sum=" << sum;
+ << "/" << std_unordered_tm.n_elapsed() / keys.size()
+ << "/" << std_unordered_multi_tm.n_elapsed() / keys.size()
+ << "/" << hash_tm.n_elapsed() / keys.size();
}
}
@@ -1349,4 +1445,70 @@ TEST_F(FlatMapTest, copy) {
ASSERT_TRUE(m4.empty());
}
+TEST_F(FlatMapTest, multi) {
+ // Construct non-POD values w/o copy-construction.
+ g_foo_ctor = 0;
+ g_foo_copy_ctor = 0;
+ g_foo_assign = 0;
+ butil::MultiFlatMap<int, Foo> map;
+ int bucket_count = 32;
+ ASSERT_EQ(0, map.init(bucket_count));
+ ASSERT_EQ(0, g_foo_ctor);
+ ASSERT_EQ(0, g_foo_copy_ctor);
+ ASSERT_EQ(0, g_foo_assign);
+ Foo& f1 = map[1];
+ ASSERT_EQ(1, g_foo_ctor);
+ ASSERT_EQ(0, g_foo_copy_ctor);
+ ASSERT_EQ(0, g_foo_assign);
+ Foo& f2 = map[1];
+ ASSERT_EQ(2, g_foo_ctor);
+ ASSERT_EQ(0, g_foo_copy_ctor);
+ ASSERT_EQ(0, g_foo_assign);
+ Foo f3;
+ Foo& f4 = *map.insert(1, f3);
+ ASSERT_EQ(4, g_foo_ctor);
+ ASSERT_EQ(0, g_foo_copy_ctor);
+ ASSERT_EQ(1, g_foo_assign);
+ ASSERT_EQ(&f1, map.seek(1));
+ std::vector<Foo*> f_vec = map.seek_all(1);
+ ASSERT_NE(f_vec.end(), std::find(f_vec.begin(), f_vec.end(), &f1));
+ ASSERT_NE(f_vec.end(), std::find(f_vec.begin(), f_vec.end(), &f2));
+ ASSERT_NE(f_vec.end(), std::find(f_vec.begin(), f_vec.end(), &f4));
+
+ ASSERT_EQ(bucket_count, map.bucket_count());
+ 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));
+ Foo& f5 = map[same_bucket_key];
+ ASSERT_EQ(&f5, map.seek(same_bucket_key));
+ ASSERT_EQ(1UL, map.seek_all(same_bucket_key).size());
+ ASSERT_EQ(5, g_foo_ctor);
+ ASSERT_EQ(0, g_foo_copy_ctor);
+ ASSERT_EQ(1, g_foo_assign);
+ ASSERT_EQ(&f5, map.seek(same_bucket_key));
+ ASSERT_EQ(3u, map.erase(1));
+ ASSERT_EQ(nullptr, map.seek(1));
+ ASSERT_TRUE(map.seek_all(1).empty());
+ // Value node of same_bucket_key is the last one in the bucket,
+ // so it has been moved to the first node.
+ ASSERT_EQ(&f1, map.seek(same_bucket_key));
+ ASSERT_EQ(1UL, map.erase(same_bucket_key));
+ ASSERT_EQ(nullptr, map.seek(same_bucket_key));
+ ASSERT_TRUE(map.seek_all(same_bucket_key).empty());
+
+ // Zeroize POD values.
+ butil::MultiFlatMap<int, Bar> map2;
+ ASSERT_EQ(0, map2.init(32));
+ Bar& g = map2[1];
+ ASSERT_EQ(0, g.x);
+ g.x = 123;
+ ASSERT_EQ(1u, map2.erase(1));
+ ASSERT_EQ(123, g.x); // g is still accessible in this case.
+ Bar& g2 = map2[1];
+ ASSERT_EQ(&g, &g2);
+ ASSERT_EQ(0, g2.x);
+}
+
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
