Mercurial > repos > rliterman > csp2

comparison 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
comparison
equal deleted inserted replaced
67:0e9998148a16 69:33d812a61356
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