Mercurial > repos > rliterman > csp2

annotate CSP2/CSP2_env/env-d9b9114564458d9d-741b3de822f2aaca6c6caa4325c4afce/include/kj/string-tree.h @ 69:33d812a61356

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