jpayne@69: // Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors jpayne@69: // Licensed under the MIT License: jpayne@69: // jpayne@69: // Permission is hereby granted, free of charge, to any person obtaining a copy jpayne@69: // of this software and associated documentation files (the "Software"), to deal jpayne@69: // in the Software without restriction, including without limitation the rights jpayne@69: // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell jpayne@69: // copies of the Software, and to permit persons to whom the Software is jpayne@69: // furnished to do so, subject to the following conditions: jpayne@69: // jpayne@69: // The above copyright notice and this permission notice shall be included in jpayne@69: // all copies or substantial portions of the Software. jpayne@69: // jpayne@69: // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR jpayne@69: // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, jpayne@69: // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE jpayne@69: // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER jpayne@69: // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, jpayne@69: // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN jpayne@69: // THE SOFTWARE. jpayne@69: jpayne@69: #pragma once jpayne@69: jpayne@69: #include "string.h" jpayne@69: jpayne@69: KJ_BEGIN_HEADER jpayne@69: jpayne@69: namespace kj { jpayne@69: jpayne@69: class StringTree { jpayne@69: // A long string, represented internally as a tree of strings. This data structure is like a jpayne@69: // String, but optimized for concatenation and iteration at the expense of seek time. The jpayne@69: // structure is intended to be used for building large text blobs from many small pieces, where jpayne@69: // repeatedly concatenating smaller strings into larger ones would waste copies. This structure jpayne@69: // is NOT intended for use cases requiring random access or computing substrings. For those, jpayne@69: // you should use a Rope, which is a much more complicated data structure. jpayne@69: // jpayne@69: // The proper way to construct a StringTree is via kj::strTree(...), which works just like jpayne@69: // kj::str(...) but returns a StringTree rather than a String. jpayne@69: // jpayne@69: // KJ_STRINGIFY() functions that construct large strings from many smaller strings are encouraged jpayne@69: // to return StringTree rather than a flat char container. jpayne@69: jpayne@69: public: jpayne@69: inline StringTree(): size_(0) {} jpayne@69: inline StringTree(String&& text): size_(text.size()), text(kj::mv(text)) {} jpayne@69: jpayne@69: StringTree(Array&& pieces, StringPtr delim); jpayne@69: // Build a StringTree by concatenating the given pieces, delimited by the given delimiter jpayne@69: // (e.g. ", "). jpayne@69: jpayne@69: inline size_t size() const { return size_; } jpayne@69: jpayne@69: template jpayne@69: void visit(Func&& func) const; jpayne@69: jpayne@69: String flatten() const; jpayne@69: // Return the contents as a string. jpayne@69: jpayne@69: // TODO(someday): flatten() when *this is an rvalue and when branches.size() == 0 could simply jpayne@69: // return `kj::mv(text)`. Requires reference qualifiers (Clang 3.3 / GCC 4.8). jpayne@69: jpayne@69: char* flattenTo(char* __restrict__ target) const; jpayne@69: char* flattenTo(char* __restrict__ target, char* limit) const; jpayne@69: // Copy the contents to the given character array. Does not add a NUL terminator. Returns a jpayne@69: // pointer just past the end of what was filled. jpayne@69: jpayne@69: private: jpayne@69: size_t size_; jpayne@69: String text; jpayne@69: jpayne@69: struct Branch; jpayne@69: Array branches; // In order. jpayne@69: jpayne@69: inline void fill(char* pos, size_t branchIndex); jpayne@69: template jpayne@69: void fill(char* pos, size_t branchIndex, First&& first, Rest&&... rest); jpayne@69: template jpayne@69: void fill(char* pos, size_t branchIndex, StringTree&& first, Rest&&... rest); jpayne@69: template jpayne@69: void fill(char* pos, size_t branchIndex, Array&& first, Rest&&... rest); jpayne@69: template jpayne@69: void fill(char* pos, size_t branchIndex, String&& first, Rest&&... rest); jpayne@69: jpayne@69: template jpayne@69: static StringTree concat(Params&&... params); jpayne@69: static StringTree&& concat(StringTree&& param) { return kj::mv(param); } jpayne@69: jpayne@69: template jpayne@69: static inline size_t flatSize(const T& t) { return t.size(); } jpayne@69: static inline size_t flatSize(String&& s) { return 0; } jpayne@69: static inline size_t flatSize(StringTree&& s) { return 0; } jpayne@69: jpayne@69: template jpayne@69: static inline size_t branchCount(const T& t) { return 0; } jpayne@69: static inline size_t branchCount(String&& s) { return 1; } jpayne@69: static inline size_t branchCount(StringTree&& s) { return 1; } jpayne@69: jpayne@69: template jpayne@69: friend StringTree strTree(Params&&... params); jpayne@69: }; jpayne@69: jpayne@69: inline StringTree&& KJ_STRINGIFY(StringTree&& tree) { return kj::mv(tree); } jpayne@69: inline const StringTree& KJ_STRINGIFY(const StringTree& tree) { return tree; } jpayne@69: jpayne@69: inline StringTree KJ_STRINGIFY(Array&& trees) { return StringTree(kj::mv(trees), ""); } jpayne@69: jpayne@69: template jpayne@69: StringTree strTree(Params&&... params); jpayne@69: // Build a StringTree by stringifying the given parameters and concatenating the results. jpayne@69: // If any of the parameters stringify to StringTree rvalues, they will be incorporated as jpayne@69: // branches to avoid a copy. jpayne@69: jpayne@69: // ======================================================================================= jpayne@69: // Inline implementation details jpayne@69: jpayne@69: namespace _ { // private jpayne@69: jpayne@69: template jpayne@69: char* fill(char* __restrict__ target, const StringTree& first, Rest&&... rest) { jpayne@69: // Make str() work with stringifiers that return StringTree by patching fill(). jpayne@69: jpayne@69: first.flattenTo(target); jpayne@69: return fill(target + first.size(), kj::fwd(rest)...); jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: char* fillLimited(char* __restrict__ target, char* limit, const StringTree& first, Rest&&... rest) { jpayne@69: // Make str() work with stringifiers that return StringTree by patching fill(). jpayne@69: jpayne@69: target = first.flattenTo(target, limit); jpayne@69: return fillLimited(target + first.size(), limit, kj::fwd(rest)...); jpayne@69: } jpayne@69: jpayne@69: template constexpr bool isStringTree() { return false; } jpayne@69: template <> constexpr bool isStringTree() { return true; } jpayne@69: jpayne@69: inline StringTree&& toStringTreeOrCharSequence(StringTree&& tree) { return kj::mv(tree); } jpayne@69: inline StringTree toStringTreeOrCharSequence(String&& str) { return StringTree(kj::mv(str)); } jpayne@69: jpayne@69: template jpayne@69: inline auto toStringTreeOrCharSequence(T&& value) jpayne@69: -> decltype(toCharSequence(kj::fwd(value))) { jpayne@69: static_assert(!isStringTree>(), jpayne@69: "When passing a StringTree into kj::strTree(), either pass it by rvalue " jpayne@69: "(use kj::mv(value)) or explicitly call value.flatten() to make a copy."); jpayne@69: jpayne@69: return toCharSequence(kj::fwd(value)); jpayne@69: } jpayne@69: jpayne@69: } // namespace _ (private) jpayne@69: jpayne@69: struct StringTree::Branch { jpayne@69: size_t index; jpayne@69: // Index in `text` where this branch should be inserted. jpayne@69: jpayne@69: StringTree content; jpayne@69: }; jpayne@69: jpayne@69: template jpayne@69: void StringTree::visit(Func&& func) const { jpayne@69: size_t pos = 0; jpayne@69: for (auto& branch: branches) { jpayne@69: if (branch.index > pos) { jpayne@69: func(text.slice(pos, branch.index)); jpayne@69: pos = branch.index; jpayne@69: } jpayne@69: branch.content.visit(func); jpayne@69: } jpayne@69: if (text.size() > pos) { jpayne@69: func(text.slice(pos, text.size())); jpayne@69: } jpayne@69: } jpayne@69: jpayne@69: inline void StringTree::fill(char* pos, size_t branchIndex) { jpayne@69: KJ_IREQUIRE(pos == text.end() && branchIndex == branches.size(), jpayne@69: kj::str(text.end() - pos, ' ', branches.size() - branchIndex).cStr()); jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: void StringTree::fill(char* pos, size_t branchIndex, First&& first, Rest&&... rest) { jpayne@69: pos = _::fill(pos, kj::fwd(first)); jpayne@69: fill(pos, branchIndex, kj::fwd(rest)...); jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: void StringTree::fill(char* pos, size_t branchIndex, StringTree&& first, Rest&&... rest) { jpayne@69: branches[branchIndex].index = pos - text.begin(); jpayne@69: branches[branchIndex].content = kj::mv(first); jpayne@69: fill(pos, branchIndex + 1, kj::fwd(rest)...); jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: void StringTree::fill(char* pos, size_t branchIndex, String&& first, Rest&&... rest) { jpayne@69: branches[branchIndex].index = pos - text.begin(); jpayne@69: branches[branchIndex].content = StringTree(kj::mv(first)); jpayne@69: fill(pos, branchIndex + 1, kj::fwd(rest)...); jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: StringTree StringTree::concat(Params&&... params) { jpayne@69: StringTree result; jpayne@69: result.size_ = _::sum({params.size()...}); jpayne@69: result.text = heapString( jpayne@69: _::sum({StringTree::flatSize(kj::fwd(params))...})); jpayne@69: result.branches = heapArray( jpayne@69: _::sum({StringTree::branchCount(kj::fwd(params))...})); jpayne@69: result.fill(result.text.begin(), 0, kj::fwd(params)...); jpayne@69: return result; jpayne@69: } jpayne@69: jpayne@69: template jpayne@69: StringTree strTree(Params&&... params) { jpayne@69: return StringTree::concat(_::toStringTreeOrCharSequence(kj::fwd(params))...); jpayne@69: } jpayne@69: jpayne@69: } // namespace kj jpayne@69: jpayne@69: KJ_END_HEADER