string-tree.h (8502B)
1 // Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors 2 // Licensed under the MIT License: 3 // 4 // Permission is hereby granted, free of charge, to any person obtaining a copy 5 // of this software and associated documentation files (the "Software"), to deal 6 // in the Software without restriction, including without limitation the rights 7 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 8 // copies of the Software, and to permit persons to whom the Software is 9 // furnished to do so, subject to the following conditions: 10 // 11 // The above copyright notice and this permission notice shall be included in 12 // all copies or substantial portions of the Software. 13 // 14 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 17 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 18 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 19 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 20 // THE SOFTWARE. 21 22 #pragma once 23 24 #include "string.h" 25 26 KJ_BEGIN_HEADER 27 28 namespace kj { 29 30 class StringTree { 31 // A long string, represented internally as a tree of strings. This data structure is like a 32 // String, but optimized for concatenation and iteration at the expense of seek time. The 33 // structure is intended to be used for building large text blobs from many small pieces, where 34 // repeatedly concatenating smaller strings into larger ones would waste copies. This structure 35 // is NOT intended for use cases requiring random access or computing substrings. For those, 36 // you should use a Rope, which is a much more complicated data structure. 37 // 38 // The proper way to construct a StringTree is via kj::strTree(...), which works just like 39 // kj::str(...) but returns a StringTree rather than a String. 40 // 41 // KJ_STRINGIFY() functions that construct large strings from many smaller strings are encouraged 42 // to return StringTree rather than a flat char container. 43 44 public: 45 inline StringTree(): size_(0) {} 46 inline StringTree(String&& text): size_(text.size()), text(kj::mv(text)) {} 47 48 StringTree(Array<StringTree>&& pieces, StringPtr delim); 49 // Build a StringTree by concatenating the given pieces, delimited by the given delimiter 50 // (e.g. ", "). 51 52 inline size_t size() const { return size_; } 53 54 template <typename Func> 55 void visit(Func&& func) const; 56 57 String flatten() const; 58 // Return the contents as a string. 59 60 // TODO(someday): flatten() when *this is an rvalue and when branches.size() == 0 could simply 61 // return `kj::mv(text)`. Requires reference qualifiers (Clang 3.3 / GCC 4.8). 62 63 char* flattenTo(char* __restrict__ target) const; 64 char* flattenTo(char* __restrict__ target, char* limit) const; 65 // Copy the contents to the given character array. Does not add a NUL terminator. Returns a 66 // pointer just past the end of what was filled. 67 68 private: 69 size_t size_; 70 String text; 71 72 struct Branch; 73 Array<Branch> branches; // In order. 74 75 inline void fill(char* pos, size_t branchIndex); 76 template <typename First, typename... Rest> 77 void fill(char* pos, size_t branchIndex, First&& first, Rest&&... rest); 78 template <typename... Rest> 79 void fill(char* pos, size_t branchIndex, StringTree&& first, Rest&&... rest); 80 template <typename... Rest> 81 void fill(char* pos, size_t branchIndex, Array<char>&& first, Rest&&... rest); 82 template <typename... Rest> 83 void fill(char* pos, size_t branchIndex, String&& first, Rest&&... rest); 84 85 template <typename... Params> 86 static StringTree concat(Params&&... params); 87 static StringTree&& concat(StringTree&& param) { return kj::mv(param); } 88 89 template <typename T> 90 static inline size_t flatSize(const T& t) { return t.size(); } 91 static inline size_t flatSize(String&& s) { return 0; } 92 static inline size_t flatSize(StringTree&& s) { return 0; } 93 94 template <typename T> 95 static inline size_t branchCount(const T& t) { return 0; } 96 static inline size_t branchCount(String&& s) { return 1; } 97 static inline size_t branchCount(StringTree&& s) { return 1; } 98 99 template <typename... Params> 100 friend StringTree strTree(Params&&... params); 101 }; 102 103 inline StringTree&& KJ_STRINGIFY(StringTree&& tree) { return kj::mv(tree); } 104 inline const StringTree& KJ_STRINGIFY(const StringTree& tree) { return tree; } 105 106 inline StringTree KJ_STRINGIFY(Array<StringTree>&& trees) { return StringTree(kj::mv(trees), ""); } 107 108 template <typename... Params> 109 StringTree strTree(Params&&... params); 110 // Build a StringTree by stringifying the given parameters and concatenating the results. 111 // If any of the parameters stringify to StringTree rvalues, they will be incorporated as 112 // branches to avoid a copy. 113 114 // ======================================================================================= 115 // Inline implementation details 116 117 namespace _ { // private 118 119 template <typename... Rest> 120 char* fill(char* __restrict__ target, const StringTree& first, Rest&&... rest) { 121 // Make str() work with stringifiers that return StringTree by patching fill(). 122 123 first.flattenTo(target); 124 return fill(target + first.size(), kj::fwd<Rest>(rest)...); 125 } 126 127 template <typename... Rest> 128 char* fillLimited(char* __restrict__ target, char* limit, const StringTree& first, Rest&&... rest) { 129 // Make str() work with stringifiers that return StringTree by patching fill(). 130 131 target = first.flattenTo(target, limit); 132 return fillLimited(target + first.size(), limit, kj::fwd<Rest>(rest)...); 133 } 134 135 template <typename T> constexpr bool isStringTree() { return false; } 136 template <> constexpr bool isStringTree<StringTree>() { return true; } 137 138 inline StringTree&& toStringTreeOrCharSequence(StringTree&& tree) { return kj::mv(tree); } 139 inline StringTree toStringTreeOrCharSequence(String&& str) { return StringTree(kj::mv(str)); } 140 141 template <typename T> 142 inline auto toStringTreeOrCharSequence(T&& value) 143 -> decltype(toCharSequence(kj::fwd<T>(value))) { 144 static_assert(!isStringTree<Decay<T>>(), 145 "When passing a StringTree into kj::strTree(), either pass it by rvalue " 146 "(use kj::mv(value)) or explicitly call value.flatten() to make a copy."); 147 148 return toCharSequence(kj::fwd<T>(value)); 149 } 150 151 } // namespace _ (private) 152 153 struct StringTree::Branch { 154 size_t index; 155 // Index in `text` where this branch should be inserted. 156 157 StringTree content; 158 }; 159 160 template <typename Func> 161 void StringTree::visit(Func&& func) const { 162 size_t pos = 0; 163 for (auto& branch: branches) { 164 if (branch.index > pos) { 165 func(text.slice(pos, branch.index)); 166 pos = branch.index; 167 } 168 branch.content.visit(func); 169 } 170 if (text.size() > pos) { 171 func(text.slice(pos, text.size())); 172 } 173 } 174 175 inline void StringTree::fill(char* pos, size_t branchIndex) { 176 KJ_IREQUIRE(pos == text.end() && branchIndex == branches.size(), 177 kj::str(text.end() - pos, ' ', branches.size() - branchIndex).cStr()); 178 } 179 180 template <typename First, typename... Rest> 181 void StringTree::fill(char* pos, size_t branchIndex, First&& first, Rest&&... rest) { 182 pos = _::fill(pos, kj::fwd<First>(first)); 183 fill(pos, branchIndex, kj::fwd<Rest>(rest)...); 184 } 185 186 template <typename... Rest> 187 void StringTree::fill(char* pos, size_t branchIndex, StringTree&& first, Rest&&... rest) { 188 branches[branchIndex].index = pos - text.begin(); 189 branches[branchIndex].content = kj::mv(first); 190 fill(pos, branchIndex + 1, kj::fwd<Rest>(rest)...); 191 } 192 193 template <typename... Rest> 194 void StringTree::fill(char* pos, size_t branchIndex, String&& first, Rest&&... rest) { 195 branches[branchIndex].index = pos - text.begin(); 196 branches[branchIndex].content = StringTree(kj::mv(first)); 197 fill(pos, branchIndex + 1, kj::fwd<Rest>(rest)...); 198 } 199 200 template <typename... Params> 201 StringTree StringTree::concat(Params&&... params) { 202 StringTree result; 203 result.size_ = _::sum({params.size()...}); 204 result.text = heapString( 205 _::sum({StringTree::flatSize(kj::fwd<Params>(params))...})); 206 result.branches = heapArray<StringTree::Branch>( 207 _::sum({StringTree::branchCount(kj::fwd<Params>(params))...})); 208 result.fill(result.text.begin(), 0, kj::fwd<Params>(params)...); 209 return result; 210 } 211 212 template <typename... Params> 213 StringTree strTree(Params&&... params) { 214 return StringTree::concat(_::toStringTreeOrCharSequence(kj::fwd<Params>(params))...); 215 } 216 217 } // namespace kj 218 219 KJ_END_HEADER