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
16 #ifndef LCDF_STRACCUM_HH
17 #define LCDF_STRACCUM_HH
23 # define LCDF_SNPRINTF_ATTR __attribute__((__format__(__printf__, 3, 4)))
25 # define LCDF_SNPRINTF_ATTR /* nothing */
29 /** @file <lcdf/straccum.hh>
30 @brief Click's StringAccum class, used to construct Strings efficiently from pieces.
33 class StringAccum { public:
35 typedef const char *const_iterator;
36 typedef char *iterator;
38 typedef int (StringAccum::*unspecified_bool_type)() const;
41 explicit inline StringAccum(int capacity);
42 explicit inline StringAccum(const char* cstr);
43 inline StringAccum(const char* s, int len);
45 inline StringAccum(const String_base<T>& str);
46 inline StringAccum(const StringAccum& x);
47 #if HAVE_CXX_RVALUE_REFERENCES
48 inline StringAccum(StringAccum&& x);
49 inline StringAccum(String&& x);
51 inline ~StringAccum();
52 static inline StringAccum make_transfer(String& x);
54 inline StringAccum &operator=(const StringAccum& x);
55 #if HAVE_CXX_RVALUE_REFERENCES
56 inline StringAccum &operator=(StringAccum&& x);
59 inline const char* data() const;
61 inline const unsigned char* udata() const;
62 inline unsigned char* udata();
63 inline int length() const;
64 inline int capacity() const;
68 inline operator unspecified_bool_type() const;
69 inline bool empty() const;
70 inline bool operator!() const;
72 inline const_iterator begin() const;
73 inline iterator begin();
74 inline const_iterator end() const;
75 inline iterator end();
77 inline char operator[](int i) const;
78 inline char &operator[](int i);
79 inline char front() const;
81 inline char back() const;
84 inline bool out_of_memory() const;
85 void assign_out_of_memory();
88 inline char *reserve(int n);
89 inline void set_length(int len);
91 inline void adjust_length(int delta);
92 inline void set_end(char* end);
93 inline void set_end(unsigned char* end);
94 inline char *extend(int nadjust, int nreserve = 0);
96 inline void pop_back(int n = 1);
98 inline void append(char c);
99 inline void append(unsigned char c);
100 inline bool append_utf8(int ch);
101 inline void append(const char *cstr);
102 inline void append(const char *s, int len);
103 inline void append(const unsigned char *s, int len);
104 inline void append(const char *first, const char *last);
105 inline void append(const unsigned char *first, const unsigned char *last);
106 void append_fill(int c, int len);
108 template <typename T>
109 void append_encoded(T &state, const unsigned char *first,
110 const unsigned char *last);
111 template <typename T>
112 inline void append_encoded(T &state, const char *first, const char *last);
113 template <typename T>
114 void append_encoded(T &state);
115 template <typename T>
116 inline void append_encoded(const unsigned char *first, const unsigned char *last);
117 template <typename T>
118 inline void append_encoded(const char *first, const char *last);
121 template <typename I>
122 inline void append_join(const String &joiner, I first, I last);
123 template <typename T>
124 inline void append_join(const String &joiner, const T &x);
125 void append_break_lines(const String &text, int linelen, const String &leftmargin = String());
127 StringAccum &snprintf(int n, const char *format, ...) LCDF_SNPRINTF_ATTR;
128 StringAccum &vsnprintf(int n, const char *format, va_list val);
130 String take_string();
132 void swap(StringAccum& x);
134 // see also operator<< declarations below
139 memo_space = String::MEMO_SPACE
147 : s(reinterpret_cast<unsigned char *>(const_cast<char *>(String_generic::empty_data))),
150 explicit rep_t(uninitialized_type) {
156 char* grow(int ncap);
157 char* hard_extend(int nadjust, int nreserve);
158 void hard_append(const char *s, int len);
159 void hard_append_cstr(const char *cstr);
160 bool append_utf8_hard(int ch);
161 void transfer_from(String& x);
164 inline StringAccum &operator<<(StringAccum &sa, char c);
165 inline StringAccum &operator<<(StringAccum &sa, unsigned char c);
166 inline StringAccum &operator<<(StringAccum &sa, const char *cstr);
167 template <typename T> inline StringAccum &operator<<(StringAccum &sa, const String_base<T> &str);
168 inline StringAccum &operator<<(StringAccum &sa, const StringAccum &x);
170 inline StringAccum &operator<<(StringAccum &sa, bool x);
171 inline StringAccum &operator<<(StringAccum &sa, short x);
172 inline StringAccum &operator<<(StringAccum &sa, unsigned short x);
173 inline StringAccum &operator<<(StringAccum &sa, int x);
174 inline StringAccum &operator<<(StringAccum &sa, unsigned x);
175 StringAccum& operator<<(StringAccum& sa, long x);
176 StringAccum& operator<<(StringAccum& sa, unsigned long x);
177 StringAccum& operator<<(StringAccum& sa, long long x);
178 StringAccum& operator<<(StringAccum& sa, unsigned long long x);
179 StringAccum& operator<<(StringAccum& sa, double x);
181 /** @brief Construct an empty StringAccum (with length 0). */
182 inline StringAccum::StringAccum() {
185 /** @brief Construct a StringAccum with room for at least @a capacity
187 @param capacity initial capacity
189 If @a capacity == 0, the StringAccum is created empty. If @a capacity is
190 too large (so that @a capacity bytes of memory can't be allocated), the
191 StringAccum falls back to a smaller capacity (possibly zero). */
192 inline StringAccum::StringAccum(int capacity) {
193 assert(capacity >= 0);
197 /** @brief Construct a StringAccum containing the characters in @a cstr. */
198 inline StringAccum::StringAccum(const char *cstr) {
202 /** @brief Construct a StringAccum containing the characters in @a s. */
203 inline StringAccum::StringAccum(const char *s, int len) {
207 /** @brief Construct a StringAccum containing the characters in @a str. */
208 template <typename T>
209 inline StringAccum::StringAccum(const String_base<T> &str) {
210 append(str.begin(), str.end());
213 /** @brief Construct a StringAccum containing a copy of @a x. */
214 inline StringAccum::StringAccum(const StringAccum &x) {
215 append(x.data(), x.length());
218 #if HAVE_CXX_RVALUE_REFERENCES
219 /** @brief Move-construct a StringAccum from @a x. */
220 inline StringAccum::StringAccum(StringAccum&& x) {
225 inline StringAccum::StringAccum(String&& x) {
227 x._r = String::rep_type{String_generic::empty_data, 0, 0};
231 /** @brief Destroy a StringAccum, freeing its memory. */
232 inline StringAccum::~StringAccum() {
234 delete[] reinterpret_cast<char*>(r_.s - memo_space);
237 inline StringAccum StringAccum::make_transfer(String& x) {
240 x._r = String::rep_type{String_generic::empty_data, 0, 0};
244 /** @brief Return the contents of the StringAccum.
246 The returned data() value points to length() bytes of writable memory. */
247 inline const char* StringAccum::data() const {
248 return reinterpret_cast<const char*>(r_.s);
252 inline char* StringAccum::data() {
253 return reinterpret_cast<char*>(r_.s);
256 /** @brief Return the contents of the StringAccum.
258 The returned data() value points to length() bytes of writable memory. */
259 inline const unsigned char* StringAccum::udata() const {
264 inline unsigned char* StringAccum::udata() {
268 /** @brief Return the length of the StringAccum. */
269 inline int StringAccum::length() const {
273 /** @brief Return the StringAccum's current capacity.
275 The capacity is the maximum length the StringAccum can hold without
276 incurring a memory allocation. Returns -1 for out-of-memory
278 inline int StringAccum::capacity() const {
282 /** @brief Return an iterator for the first character in the StringAccum.
284 StringAccum iterators are simply pointers into string data, so they are
285 quite efficient. @sa StringAccum::data */
286 inline StringAccum::const_iterator StringAccum::begin() const {
287 return reinterpret_cast<char *>(r_.s);
291 inline StringAccum::iterator StringAccum::begin() {
292 return reinterpret_cast<char *>(r_.s);
295 /** @brief Return an iterator for the end of the StringAccum.
297 The return value points one character beyond the last character in the
299 inline StringAccum::const_iterator StringAccum::end() const {
300 return reinterpret_cast<char *>(r_.s + r_.len);
304 inline StringAccum::iterator StringAccum::end() {
305 return reinterpret_cast<char *>(r_.s + r_.len);
308 /** @brief Test if the StringAccum contains characters. */
309 inline StringAccum::operator unspecified_bool_type() const {
310 return r_.len != 0 ? &StringAccum::capacity : 0;
313 /** @brief Test if the StringAccum is empty.
315 Returns true iff length() == 0. */
316 inline bool StringAccum::operator!() const {
320 /** @brief Test if the StringAccum is empty. */
321 inline bool StringAccum::empty() const {
325 /** @brief Test if the StringAccum is out-of-memory. */
326 inline bool StringAccum::out_of_memory() const {
327 return unlikely(r_.cap < 0);
330 /** @brief Return the <a>i</a>th character in the string.
331 @param i character index
332 @pre 0 <= @a i < length() */
333 inline char StringAccum::operator[](int i) const {
334 assert((unsigned) i < (unsigned) r_.len);
335 return static_cast<char>(r_.s[i]);
338 /** @brief Return a reference to the <a>i</a>th character in the string.
339 @param i character index
340 @pre 0 <= @a i < length() */
341 inline char &StringAccum::operator[](int i) {
342 assert((unsigned) i < (unsigned) r_.len);
343 return reinterpret_cast<char &>(r_.s[i]);
346 /** @brief Return the first character in the string.
348 inline char StringAccum::front() const {
350 return static_cast<char>(r_.s[0]);
353 /** @brief Return a reference to the first character in the string.
355 inline char &StringAccum::front() {
357 return reinterpret_cast<char &>(r_.s[0]);
360 /** @brief Return the last character in the string.
362 inline char StringAccum::back() const {
364 return static_cast<char>(r_.s[r_.len - 1]);
367 /** @brief Return a reference to the last character in the string.
369 inline char &StringAccum::back() {
371 return reinterpret_cast<char &>(r_.s[r_.len - 1]);
374 /** @brief Clear the StringAccum's comments.
376 All characters in the StringAccum are erased. Also resets the
377 StringAccum's out-of-memory status. */
378 inline void StringAccum::clear() {
384 /** @brief Reserve space for at least @a n characters.
385 @return a pointer to at least @a n characters, or null if allocation
389 reserve() does not change the string's length(), only its capacity(). In
390 a frequent usage pattern, code calls reserve(), passing an upper bound
391 on the characters that could be written by a series of operations. After
392 writing into the returned buffer, adjust_length() is called to account
393 for the number of characters actually written.
395 On failure, null is returned and errno is set to ENOMEM. */
396 inline char *StringAccum::reserve(int n) {
398 if (r_.len + n <= r_.cap)
399 return reinterpret_cast<char *>(r_.s + r_.len);
401 return grow(r_.len + n);
404 /** @brief Set the StringAccum's length to @a len.
405 @param len new length in characters
406 @pre 0 <= @a len <= capacity()
408 inline void StringAccum::set_length(int len) {
409 assert(len >= 0 && r_.len <= r_.cap);
413 inline void StringAccum::set_end(unsigned char* x) {
414 assert(x >= r_.s && x <= r_.s + r_.cap);
418 inline void StringAccum::set_end(char* x) {
419 set_end((unsigned char*) x);
422 /** @brief Adjust the StringAccum's length.
423 @param delta length adjustment
424 @pre If @a delta > 0, then length() + @a delta <= capacity().
425 If @a delta < 0, then length() + delta >= 0.
427 The StringAccum's length after adjust_length(@a delta) equals its old
428 length plus @a delta. Generally adjust_length() is used after a call to
429 reserve(). @sa set_length */
430 inline void StringAccum::adjust_length(int delta) {
431 assert(r_.len + delta >= 0 && r_.len + delta <= r_.cap);
435 /** @brief Reserve space and adjust length in one operation.
436 @param nadjust number of characters to reserve and adjust length
437 @param nreserve additional characters to reserve
438 @pre @a nadjust >= 0 and @a nreserve >= 0
440 This operation combines the effects of reserve(@a nadjust + @a nreserve)
441 and adjust_length(@a nadjust). Returns the result of the reserve()
443 inline char *StringAccum::extend(int nadjust, int nreserve) {
444 #if HAVE_OPTIMIZE_SIZE || __OPTIMIZE_SIZE__
445 return hard_extend(nadjust, nreserve);
447 assert(nadjust >= 0 && nreserve >= 0);
448 if (r_.len + nadjust + nreserve <= r_.cap) {
449 char *x = reinterpret_cast<char *>(r_.s + r_.len);
453 return hard_extend(nadjust, nreserve);
457 /** @brief Remove characters from the end of the StringAccum.
458 @param n number of characters to remove
459 @pre @a n >= 0 and @a n <= length()
461 Same as adjust_length(-@a n). */
462 inline void StringAccum::pop_back(int n) {
463 assert(n >= 0 && r_.len >= n);
467 /** @brief Append character @a c to the StringAccum.
468 @param c character to append */
469 inline void StringAccum::append(char c) {
470 if (r_.len < r_.cap || grow(r_.len))
475 inline void StringAccum::append(unsigned char c) {
476 append(static_cast<char>(c));
479 /** @brief Append the first @a len characters of @a s to this StringAccum.
480 @param s data to append
481 @param len length of data
483 inline void StringAccum::append(const char *s, int len) {
484 #if HAVE_OPTIMIZE_SIZE || __OPTIMIZE_SIZE__
488 if (r_.len + len <= r_.cap) {
489 memcpy(r_.s + r_.len, s, len);
497 inline void StringAccum::append(const unsigned char *s, int len) {
498 append(reinterpret_cast<const char *>(s), len);
501 /** @brief Append the null-terminated C string @a s to this StringAccum.
502 @param s data to append */
503 inline void StringAccum::append(const char *cstr) {
504 if (LCDF_CONSTANT_CSTR(cstr))
505 append(cstr, strlen(cstr));
507 hard_append_cstr(cstr);
510 /** @brief Append the data from @a first to @a last to the end of this
513 Does nothing if @a first >= @a last. */
514 inline void StringAccum::append(const char *first, const char *last) {
516 append(first, last - first);
520 inline void StringAccum::append(const unsigned char *first, const unsigned char *last) {
522 append(first, last - first);
525 /** @brief Append Unicode character @a ch encoded in UTF-8.
526 @return true if character was valid.
528 Appends nothing if @a ch is not a valid Unicode character. */
529 inline bool StringAccum::append_utf8(int ch) {
530 if (unlikely(ch <= 0))
532 else if (likely(ch <= 0x7F)) {
533 append(static_cast<char>(ch));
536 return append_utf8_hard(ch);
539 template <typename T>
540 void StringAccum::append_encoded(T &encoder,
541 const unsigned char *first,
542 const unsigned char *last)
544 unsigned char *kills = 0;
546 first = encoder.start(first, last);
548 encoder.set_output(r_.s + r_.len, r_.s + r_.cap, first);
549 if (encoder.buffer_empty())
550 first = encoder.encode(first, last);
552 first = encoder.flush(first, last);
555 r_.len = encoder.output_begin() - r_.s;
559 grow(r_.len + last - first);
560 memcpy(r_.s, kills, r_.len);
562 grow(r_.len + last - first);
565 delete[] reinterpret_cast<char*>(kills - memo_space);
568 template <typename T>
569 inline void StringAccum::append_encoded(T &state,
572 append_encoded(state,
573 reinterpret_cast<const unsigned char *>(first),
574 reinterpret_cast<const unsigned char *>(last));
577 template <typename T>
578 inline void StringAccum::append_encoded(const char *first,
580 append_encoded<T>(reinterpret_cast<const unsigned char *>(first),
581 reinterpret_cast<const unsigned char *>(last));
584 template <typename T>
585 void StringAccum::append_encoded(T &encoder)
587 while (!encoder.buffer_empty()) {
588 encoder.set_output(r_.s + r_.len, r_.s + r_.cap, 0);
589 if (encoder.flush_clear()) {
590 r_.len = encoder.output_begin() - r_.s;
597 template <typename T>
598 inline void StringAccum::append_encoded(const unsigned char *first,
599 const unsigned char *last)
602 append_encoded(encoder, first, last);
603 if (!encoder.buffer_empty())
604 append_encoded(encoder);
607 template <typename I>
608 inline void StringAccum::append_join(const String &joiner, I first, I last) {
610 while (first != last) {
619 template <typename T>
620 inline void StringAccum::append_join(const String &joiner, const T &x) {
621 append_join(joiner, x.begin(), x.end());
624 /** @brief Assign this StringAccum to @a x. */
625 inline StringAccum &StringAccum::operator=(const StringAccum &x) {
630 append(x.data(), x.length());
635 #if HAVE_CXX_RVALUE_REFERENCES
636 /** @brief Move-assign this StringAccum to @a x. */
637 inline StringAccum &StringAccum::operator=(StringAccum &&x) {
643 /** @relates StringAccum
644 @brief Append character @a c to StringAccum @a sa.
646 @note Same as @a sa.append(@a c). */
647 inline StringAccum &operator<<(StringAccum &sa, char c) {
652 /** @relates StringAccum
653 @brief Append character @a c to StringAccum @a sa.
655 @note Same as @a sa.append(@a c). */
656 inline StringAccum &operator<<(StringAccum &sa, unsigned char c) {
661 /** @relates StringAccum
662 @brief Append null-terminated C string @a cstr to StringAccum @a sa.
664 @note Same as @a sa.append(@a cstr). */
665 inline StringAccum &operator<<(StringAccum &sa, const char *cstr) {
670 /** @relates StringAccum
671 @brief Append "true" or "false" to @a sa, depending on @a x.
673 inline StringAccum &operator<<(StringAccum &sa, bool x) {
674 sa.append(String_generic::bool_data + (-x & 6), 5 - x);
678 /** @relates StringAccum
679 @brief Append decimal representation of @a x to @a sa.
681 inline StringAccum &operator<<(StringAccum &sa, short x) {
682 return sa << static_cast<long>(x);
686 inline StringAccum &operator<<(StringAccum &sa, unsigned short x) {
687 return sa << static_cast<unsigned long>(x);
691 inline StringAccum &operator<<(StringAccum &sa, int x) {
692 return sa << static_cast<long>(x);
696 inline StringAccum &operator<<(StringAccum &sa, unsigned x) {
697 return sa << static_cast<unsigned long>(x);
700 /** @relates StringAccum
701 @brief Append the contents of @a str to @a sa.
703 template <typename T>
704 inline StringAccum &operator<<(StringAccum &sa, const String_base<T> &str) {
705 sa.append(str.data(), str.length());
709 inline StringAccum &operator<<(StringAccum &sa, const std::string &str) {
710 sa.append(str.data(), str.length());
714 /** @relates StringAccum
715 @brief Append the contents of @a x to @a sa.
717 inline StringAccum &operator<<(StringAccum &sa, const StringAccum &x) {
718 sa.append(x.begin(), x.end());
722 inline bool operator==(StringAccum &sa, const char *cstr) {
723 return strcmp(sa.c_str(), cstr) == 0;
726 inline bool operator!=(StringAccum &sa, const char *cstr) {
727 return strcmp(sa.c_str(), cstr) != 0;
730 inline void swap(StringAccum& a, StringAccum& b) {
735 #undef LCDF_SNPRINTF_ATTR