2 * Eddie Kohler, Yandong Mao, Robert Morris
3 * Copyright (c) 2012-2013 President and Fellows of Harvard College
4 * Copyright (c) 2012-2013 Massachusetts Institute of Technology
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the "Software"),
8 * to deal in the Software without restriction, subject to the conditions
9 * listed in the Masstree LICENSE file. These conditions include: you must
10 * preserve this copyright notice, and you cannot mention the copyright
11 * holders in advertising related to the Software without their permission.
12 * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
13 * notice is a summary of the Masstree LICENSE file; the license in that file
17 * straccum.{cc,hh} -- build up strings with operator<<
20 * Copyright (c) 1999-2000 Massachusetts Institute of Technology
21 * Copyright (c) 2001-2013 Eddie Kohler
23 * Permission is hereby granted, free of charge, to any person obtaining a
24 * copy of this software and associated documentation files (the "Software"),
25 * to deal in the Software without restriction, subject to the conditions
26 * listed in the Click LICENSE file. These conditions include: you must
27 * preserve this copyright notice, and you cannot mention the copyright
28 * holders in advertising related to the Software without their permission.
29 * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
30 * notice is a summary of the Click LICENSE file; the license in that file
34 #include "straccum.hh"
41 /** @class StringAccum
42 * @brief Efficiently build up Strings from pieces.
44 * Like the String class, StringAccum represents a string of characters.
45 * However, unlike a String, a StringAccum is inherently mutable, and
46 * efficiently supports building up a large string from many smaller pieces.
48 * StringAccum objects support operator<<() operations for most fundamental
49 * data types. A StringAccum is generally built up by operator<<(), and then
50 * turned into a String by the take_string() method. Extracting the String
51 * from a StringAccum does no memory allocation or copying; the StringAccum's
52 * memory is donated to the String.
54 * <h3>Out-of-memory StringAccums</h3>
56 * When there is not enough memory to add requested characters to a
57 * StringAccum object, the object becomes a special "out-of-memory"
58 * StringAccum. Out-of-memory objects are contagious: the result of any
59 * concatenation operation involving an out-of-memory StringAccum is another
60 * out-of-memory StringAccum. Calling take_string() on an out-of-memory
61 * StringAccum returns an out-of-memory String.
63 * Note that appending an out-of-memory String to a StringAccum <em>does
64 * not</em> make the StringAccum out-of-memory.
67 /** @brief Change this StringAccum into an out-of-memory StringAccum. */
69 StringAccum::assign_out_of_memory()
72 delete[] reinterpret_cast<char*>(r_.s - memo_space);
73 r_.s = reinterpret_cast<unsigned char*>(const_cast<char*>(String_generic::empty_data));
78 char* StringAccum::grow(int ncap) {
79 // can't append to out-of-memory strings
86 return reinterpret_cast<char*>(r_.s + r_.len);
89 else if (r_.cap < (1 << 20) && ncap < (r_.cap + memo_space) * 2 - memo_space)
90 ncap = (r_.cap + memo_space) * 2 - memo_space;
91 else if (r_.cap >= (1 << 20) && ncap < r_.cap + (1 << 19))
92 ncap = r_.cap + (1 << 19);
94 char* n = new char[ncap + memo_space];
96 assign_out_of_memory();
103 memcpy(n, r_.s, r_.len);
104 delete[] reinterpret_cast<char*>(r_.s - memo_space);
106 r_.s = reinterpret_cast<unsigned char*>(n);
108 return reinterpret_cast<char*>(r_.s + r_.len);
111 /** @brief Set the StringAccum's length to @a len.
113 @return 0 on success, -ENOMEM on failure */
115 StringAccum::resize(int len)
118 if (len > r_.cap && !grow(len))
127 StringAccum::hard_extend(int nadjust, int nreserve)
130 if (r_.len + nadjust + nreserve <= r_.cap)
131 x = reinterpret_cast<char*>(r_.s + r_.len);
133 x = grow(r_.len + nadjust + nreserve);
139 void StringAccum::transfer_from(String& x) {
140 if (x.is_shared() || x._r.memo_offset != -memo_space) {
141 append(x.begin(), x.end());
144 r_.s = const_cast<unsigned char*>(x.udata());
146 r_.cap = x._r.memo()->capacity;
150 /** @brief Null-terminate this StringAccum and return its data.
152 Note that the null character does not contribute to the StringAccum's
153 length(), and later append() and similar operations can overwrite it. If
154 appending the null character fails, the StringAccum becomes
155 out-of-memory and the returned value is a null string. */
159 if (r_.len < r_.cap || grow(r_.len))
161 return reinterpret_cast<char *>(r_.s);
164 /** @brief Append @a len copies of character @a c to the StringAccum. */
166 StringAccum::append_fill(int c, int len)
168 if (char *s = extend(len))
173 StringAccum::hard_append(const char *s, int len)
175 // We must be careful about calls like "sa.append(sa.begin(), sa.end())";
176 // a naive implementation might use sa's data after freeing it.
177 const char *my_s = reinterpret_cast<char *>(r_.s);
179 if (r_.len + len <= r_.cap) {
181 memcpy(r_.s + r_.len, s, len);
183 } else if (likely(s < my_s || s >= my_s + r_.cap)) {
184 if (grow(r_.len + len))
189 if (char *new_s = extend(old_r.len + len)) {
190 memcpy(new_s, old_r.s, old_r.len);
191 memcpy(new_s + old_r.len, s, len);
193 delete[] reinterpret_cast<char*>(old_r.s - memo_space);
198 StringAccum::hard_append_cstr(const char *cstr)
200 append(cstr, strlen(cstr));
204 StringAccum::append_utf8_hard(int ch)
207 append(static_cast<char>(0xC0 | (ch >> 6)));
209 } else if (ch < 0x10000) {
210 if (unlikely((ch >= 0xD800 && ch < 0xE000) || ch > 0xFFFD))
212 append(static_cast<char>(0xE0 | (ch >> 12)));
214 } else if (ch < 0x110000) {
215 append(static_cast<char>(0xF0 | (ch >> 18)));
216 append(static_cast<char>(0x80 | ((ch >> 12) & 0x3F)));
218 append(static_cast<char>(0x80 | ((ch >> 6) & 0x3F)));
220 append(static_cast<char>(0x80 | (ch & 0x3F)));
226 /** @brief Return a String object with this StringAccum's contents.
228 This operation donates the StringAccum's memory to the returned String.
229 After a call to take_string(), the StringAccum object becomes empty, and
230 any future append() operations may cause memory allocations. If the
231 StringAccum is out-of-memory, the returned String is also out-of-memory,
232 but the StringAccum's out-of-memory state is reset. */
234 StringAccum::take_string()
238 char* str = reinterpret_cast<char*>(r_.s);
239 if (len > 0 && cap > 0) {
240 String::memo_type* memo =
241 reinterpret_cast<String::memo_type*>(r_.s - memo_space);
242 memo->initialize(cap, len);
244 return String(str, len, memo);
245 } else if (!out_of_memory())
249 return String::make_out_of_memory();
253 /** @brief Swap this StringAccum's contents with @a x. */
255 StringAccum::swap(StringAccum &x)
262 /** @relates StringAccum
263 @brief Append decimal representation of @a i to @a sa.
266 operator<<(StringAccum &sa, long i)
268 if (char *x = sa.reserve(24)) {
269 int len = sprintf(x, "%ld", i);
270 sa.adjust_length(len);
275 /** @relates StringAccum
276 @brief Append decimal representation of @a u to @a sa.
279 operator<<(StringAccum &sa, unsigned long u)
281 if (char *x = sa.reserve(24)) {
282 int len = sprintf(x, "%lu", u);
283 sa.adjust_length(len);
288 /** @relates StringAccum
289 @brief Append decimal representation of @a i to @a sa.
292 operator<<(StringAccum &sa, long long i)
294 if (char *x = sa.reserve(24)) {
295 int len = sprintf(x, "%lld", i);
296 sa.adjust_length(len);
301 /** @relates StringAccum
302 @brief Append decimal representation of @a u to @a sa.
305 operator<<(StringAccum &sa, unsigned long long u)
307 if (char *x = sa.reserve(24)) {
308 int len = sprintf(x, "%llu", u);
309 sa.adjust_length(len);
315 operator<<(StringAccum &sa, double d)
317 if (char *x = sa.reserve(256)) {
318 int len = sprintf(x, "%.12g", d);
319 sa.adjust_length(len);
324 /** @brief Append result of vsnprintf() to this StringAccum.
325 @param n maximum number of characters to print
326 @param format format argument to snprintf()
327 @param val argument set
331 StringAccum::vsnprintf(int n, const char *format, va_list val)
333 if (char *x = reserve(n + 1)) {
335 int len = ::vsnprintf(x, n + 1, format, val);
337 int len = vsprintf(x, format, val);
345 /** @brief Append result of snprintf() to this StringAccum.
346 @param n maximum number of characters to print
347 @param format format argument to snprintf()
350 The terminating null character is not appended to the string.
352 @note The safe vsnprintf() variant is called if it exists. It does in
353 the Linux kernel, and on modern Unix variants. However, if it does not
354 exist on your machine, then this function is actually unsafe, and you
355 should make sure that the printf() invocation represented by your
356 arguments will never write more than @a n characters, not including the
360 StringAccum::snprintf(int n, const char *format, ...)
363 va_start(val, format);
364 vsnprintf(n, format, val);
370 StringAccum::append_break_lines(const String& text, int linelen, const String &leftmargin)
372 if (text.length() == 0)
374 const char* line = text.begin();
375 const char* ends = text.end();
376 linelen -= leftmargin.length();
377 for (const char* s = line; s < ends; s++) {
378 const char* start = s;
379 while (s < ends && isspace((unsigned char) *s))
381 const char* word = s;
382 while (s < ends && !isspace((unsigned char) *s))
384 if (s - line > linelen && start > line) {
386 append(line, start - line);
391 if (line < text.end()) {
393 append(line, text.end() - line);