silo/masstree/straccum.cc

   1 /* Masstree
   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
   5  *
   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
  14  * is legally binding.
  15  */
  16 /*
  17  * straccum.{cc,hh} -- build up strings with operator<<
  18  * Eddie Kohler
  19  *
  20  * Copyright (c) 1999-2000 Massachusetts Institute of Technology
  21  * Copyright (c) 2001-2013 Eddie Kohler
  22  *
  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
  31  * is legally binding.
  32  */
  33
  34 #include "straccum.hh"
  35 #include <stdarg.h>
  36 #include <stdio.h>
  37 #include <ctype.h>
  38 #include <errno.h>
  39 namespace lcdf {
  40
  41 /** @class StringAccum
  42  * @brief Efficiently build up Strings from pieces.
  43  *
  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.
  47  *
  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.
  53  *
  54  * <h3>Out-of-memory StringAccums</h3>
  55  *
  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.
  62  *
  63  * Note that appending an out-of-memory String to a StringAccum <em>does
  64  * not</em> make the StringAccum out-of-memory.
  65  */
  66
  67 /** @brief Change this StringAccum into an out-of-memory StringAccum. */
  68 void
  69 StringAccum::assign_out_of_memory()
  70 {
  71     if (r_.cap > 0)
  72         delete[] reinterpret_cast<char*>(r_.s - memo_space);
  73     r_.s = reinterpret_cast<unsigned char*>(const_cast<char*>(String_generic::empty_data));
  74     r_.cap = -1;
  75     r_.len = 0;
  76 }
  77
  78 char* StringAccum::grow(int ncap) {
  79     // can't append to out-of-memory strings
  80     if (r_.cap < 0) {
  81         errno = ENOMEM;
  82         return 0;
  83     }
  84
  85     if (ncap < r_.cap)
  86         return reinterpret_cast<char*>(r_.s + r_.len);
  87     else if (ncap < 128)
  88         ncap = 128;
  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);
  93
  94     char* n = new char[ncap + memo_space];
  95     if (!n) {
  96         assign_out_of_memory();
  97         errno = ENOMEM;
  98         return 0;
  99     }
 100
 101     n += memo_space;
 102     if (r_.cap > 0) {
 103         memcpy(n, r_.s, r_.len);
 104         delete[] reinterpret_cast<char*>(r_.s - memo_space);
 105     }
 106     r_.s = reinterpret_cast<unsigned char*>(n);
 107     r_.cap = ncap;
 108     return reinterpret_cast<char*>(r_.s + r_.len);
 109 }
 110
 111 /** @brief Set the StringAccum's length to @a len.
 112     @pre @a len >= 0
 113     @return 0 on success, -ENOMEM on failure */
 114 int
 115 StringAccum::resize(int len)
 116 {
 117     assert(len >= 0);
 118     if (len > r_.cap && !grow(len))
 119         return -ENOMEM;
 120     else {
 121         r_.len = len;
 122         return 0;
 123     }
 124 }
 125
 126 char *
 127 StringAccum::hard_extend(int nadjust, int nreserve)
 128 {
 129     char *x;
 130     if (r_.len + nadjust + nreserve <= r_.cap)
 131         x = reinterpret_cast<char*>(r_.s + r_.len);
 132     else
 133         x = grow(r_.len + nadjust + nreserve);
 134     if (x)
 135         r_.len += nadjust;
 136     return x;
 137 }
 138
 139 void StringAccum::transfer_from(String& x) {
 140     if (x.is_shared() || x._r.memo_offset != -memo_space) {
 141         append(x.begin(), x.end());
 142         x._r.deref();
 143     } else {
 144         r_.s = const_cast<unsigned char*>(x.udata());
 145         r_.len = x.length();
 146         r_.cap = x._r.memo()->capacity;
 147     }
 148 }
 149
 150 /** @brief Null-terminate this StringAccum and return its data.
 151
 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. */
 156 const char *
 157 StringAccum::c_str()
 158 {
 159     if (r_.len < r_.cap || grow(r_.len))
 160         r_.s[r_.len] = '\0';
 161     return reinterpret_cast<char *>(r_.s);
 162 }
 163
 164 /** @brief Append @a len copies of character @a c to the StringAccum. */
 165 void
 166 StringAccum::append_fill(int c, int len)
 167 {
 168     if (char *s = extend(len))
 169         memset(s, c, len);
 170 }
 171
 172 void
 173 StringAccum::hard_append(const char *s, int len)
 174 {
 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);
 178
 179     if (r_.len + len <= r_.cap) {
 180     success:
 181         memcpy(r_.s + r_.len, s, len);
 182         r_.len += len;
 183     } else if (likely(s < my_s || s >= my_s + r_.cap)) {
 184         if (grow(r_.len + len))
 185             goto success;
 186     } else {
 187         rep_t old_r = r_;
 188         r_ = rep_t();
 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);
 192         }
 193         delete[] reinterpret_cast<char*>(old_r.s - memo_space);
 194     }
 195 }
 196
 197 void
 198 StringAccum::hard_append_cstr(const char *cstr)
 199 {
 200     append(cstr, strlen(cstr));
 201 }
 202
 203 bool
 204 StringAccum::append_utf8_hard(int ch)
 205 {
 206     if (ch < 0x8000) {
 207         append(static_cast<char>(0xC0 | (ch >> 6)));
 208         goto char1;
 209     } else if (ch < 0x10000) {
 210         if (unlikely((ch >= 0xD800 && ch < 0xE000) || ch > 0xFFFD))
 211             return false;
 212         append(static_cast<char>(0xE0 | (ch >> 12)));
 213         goto char2;
 214     } else if (ch < 0x110000) {
 215         append(static_cast<char>(0xF0 | (ch >> 18)));
 216         append(static_cast<char>(0x80 | ((ch >> 12) & 0x3F)));
 217     char2:
 218         append(static_cast<char>(0x80 | ((ch >> 6) & 0x3F)));
 219     char1:
 220         append(static_cast<char>(0x80 | (ch & 0x3F)));
 221     } else
 222         return false;
 223     return true;
 224 }
 225
 226 /** @brief Return a String object with this StringAccum's contents.
 227
 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. */
 233 String
 234 StringAccum::take_string()
 235 {
 236     int len = length();
 237     int cap = r_.cap;
 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);
 243         r_ = rep_t();
 244         return String(str, len, memo);
 245     } else if (!out_of_memory())
 246         return String();
 247     else {
 248         clear();
 249         return String::make_out_of_memory();
 250     }
 251 }
 252
 253 /** @brief Swap this StringAccum's contents with @a x. */
 254 void
 255 StringAccum::swap(StringAccum &x)
 256 {
 257     rep_t xr = x.r_;
 258     x.r_ = r_;
 259     r_ = xr;
 260 }
 261
 262 /** @relates StringAccum
 263     @brief Append decimal representation of @a i to @a sa.
 264     @return @a sa */
 265 StringAccum &
 266 operator<<(StringAccum &sa, long i)
 267 {
 268     if (char *x = sa.reserve(24)) {
 269         int len = sprintf(x, "%ld", i);
 270         sa.adjust_length(len);
 271     }
 272     return sa;
 273 }
 274
 275 /** @relates StringAccum
 276     @brief Append decimal representation of @a u to @a sa.
 277     @return @a sa */
 278 StringAccum &
 279 operator<<(StringAccum &sa, unsigned long u)
 280 {
 281     if (char *x = sa.reserve(24)) {
 282         int len = sprintf(x, "%lu", u);
 283         sa.adjust_length(len);
 284     }
 285     return sa;
 286 }
 287
 288 /** @relates StringAccum
 289     @brief Append decimal representation of @a i to @a sa.
 290     @return @a sa */
 291 StringAccum &
 292 operator<<(StringAccum &sa, long long i)
 293 {
 294     if (char *x = sa.reserve(24)) {
 295         int len = sprintf(x, "%lld", i);
 296         sa.adjust_length(len);
 297     }
 298     return sa;
 299 }
 300
 301 /** @relates StringAccum
 302     @brief Append decimal representation of @a u to @a sa.
 303     @return @a sa */
 304 StringAccum &
 305 operator<<(StringAccum &sa, unsigned long long u)
 306 {
 307     if (char *x = sa.reserve(24)) {
 308         int len = sprintf(x, "%llu", u);
 309         sa.adjust_length(len);
 310     }
 311     return sa;
 312 }
 313
 314 StringAccum &
 315 operator<<(StringAccum &sa, double d)
 316 {
 317     if (char *x = sa.reserve(256)) {
 318         int len = sprintf(x, "%.12g", d);
 319         sa.adjust_length(len);
 320     }
 321     return sa;
 322 }
 323
 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
 328     @return *this
 329     @sa snprintf */
 330 StringAccum &
 331 StringAccum::vsnprintf(int n, const char *format, va_list val)
 332 {
 333     if (char *x = reserve(n + 1)) {
 334 #if HAVE_VSNPRINTF
 335         int len = ::vsnprintf(x, n + 1, format, val);
 336 #else
 337         int len = vsprintf(x, format, val);
 338         assert(len <= n);
 339 #endif
 340         adjust_length(len);
 341     }
 342     return *this;
 343 }
 344
 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()
 348     @return *this
 349
 350     The terminating null character is not appended to the string.
 351
 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
 357     terminating null.
 358     @sa vsnprintf */
 359 StringAccum &
 360 StringAccum::snprintf(int n, const char *format, ...)
 361 {
 362     va_list val;
 363     va_start(val, format);
 364     vsnprintf(n, format, val);
 365     va_end(val);
 366     return *this;
 367 }
 368
 369 void
 370 StringAccum::append_break_lines(const String& text, int linelen, const String &leftmargin)
 371 {
 372     if (text.length() == 0)
 373         return;
 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))
 380             s++;
 381         const char* word = s;
 382         while (s < ends && !isspace((unsigned char) *s))
 383             s++;
 384         if (s - line > linelen && start > line) {
 385             *this << leftmargin;
 386             append(line, start - line);
 387             *this << '\n';
 388             line = word;
 389         }
 390     }
 391     if (line < text.end()) {
 392         *this << leftmargin;
 393         append(line, text.end() - line);
 394         *this << '\n';
 395     }
 396 }
 397
 398 } // namespace lcdf