sstring: implement push_back() #2106
Conversation
to be more compatible with basic_string<> this is also what we expect from a sequence-alike STL containers. Fixes scylladb#2104 Signed-off-by: Kefu Chai <[email protected]>
tchaikov
force-pushed
the
sstring-push-back
branch
from
5187e08
to
9ca6163
Compare
| */ | ||
| constexpr void push_back(char_type ch) { | ||
| if (is_internal()) { | ||
| if (static_cast<Size>(u.internal.size) < max_size) { |
There was a problem hiding this comment.
Should add padding() here, see the constructor from initialized_later.
| @@ -199,6 +199,27 @@ BOOST_AUTO_TEST_CASE(test_append) { | |||
| BOOST_REQUIRE_EQUAL(sstring("aba").append("1234", 0), "aba"); | |||
| } | |||
|
|
|||
| BOOST_AUTO_TEST_CASE(test_push_back) { | |||
There was a problem hiding this comment.
nit: push_back() against empty string looks like good corner case test
| if (static_cast<Size>(u.internal.size) < max_size) { | ||
| u.internal.str[u.internal.size++] = ch; | ||
| if (NulTerminate) { | ||
| u.internal.str[u.internal.size] = '\0'; |
There was a problem hiding this comment.
What if at this point u.internal.size already reached max_size?
| basic_sstring new_str(initialized_later(), u.external.size + 1); | ||
| std::copy(begin(), end(), new_str.begin()); | ||
| new_str.u.external.str[new_str.u.external.size - 1] = ch; | ||
| *this = std::move(new_str); |
There was a problem hiding this comment.
I am not familiar with NulTerminate but don't we need to do it here as well?
| return; | ||
| } | ||
| } | ||
| basic_sstring new_str(initialized_later(), u.external.size + 1); |
There was a problem hiding this comment.
What if we reached here despite is_internal() (because we reached max size)? Isn't u.external.size wrong?
Please make sure you tests check the case of an empty string growing and growing until passing the internal size and see it still works.
| BOOST_REQUIRE_EQUAL(s, "0123456789a"); | ||
| } | ||
| { | ||
| // append causing spilling to external storage |
There was a problem hiding this comment.
I would do this test in a loop, for many sizes, not just 15 - e.g. from size 0 to 50. I don't know if 15 exactly is the cutoff point, or maybe 14 or 16? I'm worried that the above code has multiple bugs (I pointed out my suspicions above) and this test doesn't make me confident.
Also please check the NulTerminate option, whatever it is.
| } | ||
| } | ||
| basic_sstring new_str(initialized_later(), u.external.size + 1); | ||
| std::copy(begin(), end(), new_str.begin()); |
There was a problem hiding this comment.
The documentation https://en.cppreference.com/w/cpp/string/basic_string/push_back says that push_back() should have "amortized constant" complexity. It means you cannot do this copy on every push_back() call - it would make it O(n) complexity. I think you need to multiply the size of the string by something (1.1 or 2 or whatever) and until you reach the preallocated size, just copy one character and not the entire string.
There was a problem hiding this comment.
We don't have unused capacity, so can't do that.
I think push_back is bad since it can't be implemented efficiently and will lead to accidentally quadratic users.
There was a problem hiding this comment.
If we can't do that, we shouldn't implement this function. Its complexity is part of its API.
There was a problem hiding this comment.
how about trading the implementation for a comment, noting that we don't intend to implement this because of the performance issues due to the inherent design decisions made by sstring (not because that we are lazy =).
There was a problem hiding this comment.
Nobody will read a comment on push_back. Everyone already knows how it works.
There was a problem hiding this comment.
@avikivity hi Avi, i didn't mean to add a comment near by this function. i wanted to put a comment in the place of it explaining why we don't have it. to explain that it is a design decision.
to be more compatible with basic_string<>
this is also what we expect from a sequence-alike STL containers.
Fixes #2104
Signed-off-by: Kefu Chai [email protected]