string.cc

/* Masstree
 * Eddie Kohler, Yandong Mao, Robert Morris
 * Copyright (c) 2012-2013 President and Fellows of Harvard College
 * Copyright (c) 2012-2013 Massachusetts Institute of Technology
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, subject to the conditions
 * listed in the Masstree LICENSE file. These conditions include: you must
 * preserve this copyright notice, and you cannot mention the copyright
 * holders in advertising related to the Software without their permission.
 * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
 * notice is a summary of the Masstree LICENSE file; the license in that file
 * is legally binding.
 */
/*
 * string.{cc,hh} -- a String class with shared substrings
 * Eddie Kohler
 *
 * Copyright (c) 1999-2000 Massachusetts Institute of Technology
 * Copyright (c) 2001-2013 Eddie Kohler
 * Copyright (c) 2008-2009 Meraki, Inc.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, subject to the conditions
 * listed in the Click LICENSE file. These conditions include: you must
 * preserve this copyright notice, and you cannot mention the copyright
 * holders in advertising related to the Software without their permission.
 * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
 * notice is a summary of the Click LICENSE file; the license in that file
 * is legally binding.
 */

#include "string.hh"
#include "straccum.hh"
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <inttypes.h>
#include <vector>
namespace lcdf {

/** @file string.hh
 * @brief The LCDF String class.
 */

/** @class String
 * @brief A string of characters.
 *
 * The String class represents a string of characters.  Strings may be
 * constructed from C strings, characters, numbers, and so forth.  They may
 * also be added together.  The underlying character arrays are dynamically
 * allocated; String operations allocate and free memory as needed.  A String
 * and its substrings generally share memory.  Accessing a character by index
 * takes O(1) time; so does creating a substring.
 *
 * <h3>Out-of-memory strings</h3>
 *
 * When there is not enough memory to create a particular string, a special
 * "out-of-memory" string is returned instead. Out-of-memory strings are
 * contagious: the result of any concatenation operation involving an
 * out-of-memory string is another out-of-memory string. Thus, the final
 * result of a series of String operations will be an out-of-memory string,
 * even if the out-of-memory condition occurs in the middle.
 *
 * The canonical out-of-memory string is 14 bytes long, and equals the UTF-8
 * encoding of "\U0001F4A3ENOMEM\U0001F4A3" (that is, U+1F4A3 BOMB +
 * "ENOMEM" + U+1F4A3 BOMB). This sequence is unlikely to show up in normal
 * text, compares high relative to most other textual strings, and is valid
 * UTF-8.
 *
 * All canonical out-of-memory strings are equal and share the same data(),
 * which is different from the data() of any other string. See
 * String::out_of_memory_data(). The String::make_out_of_memory() function
 * returns a canonical out-of-memory string.
 *
 * Other strings may also be out-of-memory strings. For example,
 * String::make_stable(String::out_of_memory_data()) ==
 * String::make_out_of_memory(), and some (but not all) substrings of
 * out-of-memory strings are also out-of-memory strings.
 */

const char String_generic::empty_data[] = "";
// oom_data is the UTF-8 encoding of U+1F4A3 BOMB + "ENOMEM" + U+1F4A3 BOMB
const char String_generic::out_of_memory_data[] = "\360\237\222\243ENOMEM\360\237\222\243";
const char String_generic::bool_data[] = "false\0true";
const char String_generic::base64_encoding_table[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
const unsigned char String_generic::base64_decoding_map[] =
        "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
        "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
        "\0\0\0\0\0\0\0\0\0\0\0\x3F\0\0\0\x40"
        "\x35\x36\x37\x38\x39\x3A\x3B\x3C\x3D\x3E\0\0\0\0\0\0"
        "\0\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0A\x0B\x0C\x0D\x0E\x0F"
        "\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1A\0\0\0\0\0"
        "\0\x1B\x1C\x1D\x1E\x1F\x20\x21\x22\x23\x24\x25\x26\x27\x28\x29"
        "\x2A\x2B\x2C\x2D\x2E\x2F\x30\x31\x32\x33\x34\0\0\0\0\0"
        "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
        "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
        "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
        "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
        "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
        "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
        "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
        "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0";
const char String::int_data[] = "0\0001\0002\0003\0004\0005\0006\0007\0008\0009";

#if HAVE_STRING_PROFILING > 1
# define MEMO_INITIALIZER_TAIL , 0, 0
#else
# define MEMO_INITIALIZER_TAIL
#endif

const String::rep_type String::null_string_rep = {
    String_generic::empty_data, 0, 0
};
const String::rep_type String::oom_string_rep = {
    String_generic::out_of_memory_data, String_generic::out_of_memory_length, 0
};
const String::rep_type String::zero_string_rep = {
    &int_data[0], 0, 0
};

#if HAVE_STRING_PROFILING
uint64_t String::live_memo_count;
uint64_t String::memo_sizes[55];
uint64_t String::live_memo_sizes[55];
uint64_t String::live_memo_bytes[55];
# if HAVE_STRING_PROFILING > 1
String::memo_type *String::live_memos[55];
# endif
#endif

int
String_generic::compare(const char* a, int a_len, const char* b, int b_len)
{
    if (a != b) {
        int len = a_len < b_len ? a_len : b_len;
        int cmp = memcmp(a, b, len);
        if (cmp != 0)
            return cmp;
    }
    return a_len - b_len;
}

int String_generic::natural_compare(const char* a, int a_len,
                                    const char* b, int b_len) {
    const char* ae = a + a_len;
    const char* be = b + b_len;
    const char* aperiod = 0;
    bool aperiod_negative = false;
    int raw_compare = 0;

    while (a < ae && b < be) {
        if (isdigit((unsigned char) *a) && isdigit((unsigned char) *b)) {
            // compare the two numbers, but treat them as strings
            // (a decimal conversion might cause overflow)
            bool potential_decimal = (a == aperiod);

            // check if both are negative (note that if we get here, entire
            // string prefixes are identical)
            bool negative = false;
            if (a > ae - a_len && a[-1] == '-'
                && (a == ae - a_len + 1
                    || isspace((unsigned char) a[-2])))
                negative = true;

            // skip initial '0's, but remember any difference in length
            const char *ia = a, *ib = b;
            while (a < ae && *a == '0')
                ++a;
            while (b < be && *b == '0')
                ++b;
            int longer_zeros = (a - ia) - (b - ib);

            // walk over digits, remembering first nonidentical digit comparison
            int digit_compare = 0;
            bool a_good, b_good;
            while (1) {
                a_good = a < ae && isdigit((unsigned char) *a);
                b_good = b < be && isdigit((unsigned char) *b);
                if (!a_good || !b_good)
                    break;
                if (digit_compare == 0)
                    digit_compare = *a - *b;
                ++a;
                ++b;
            }

            // real number comparison: leading zeros are significant,
            // digit comparisons take precedence
            if (potential_decimal) {
                const char *ax = a, *bx = b;
                while (ax < ae && isdigit((unsigned char) *ax))
                    ++ax;
                while (bx < be && isdigit((unsigned char) *bx))
                    ++bx;
                // watch for IP addresses: don't treat "0.2." like a decimal
                if (!(ax + 1 < ae && *ax == '.' && !isspace((unsigned char) ax[1]))
                    && !(bx + 1 < be && *bx == '.' && !isspace((unsigned char) bx[1]))) {
                    negative = aperiod_negative;
                    if (longer_zeros)
                        return negative ? 1 : -1;
                    if (digit_compare)
                        a_good = b_good;
                }
            }
            // if one number is longer, it must also be larger
            if (a_good != b_good)
                return negative == a_good ? -1 : 1;
            // otherwise, digit comparisons take precedence
            if (digit_compare)
                return negative == (digit_compare > 0) ? -1 : 1;
            // as a last resort, the longer string of zeros is greater
            if (longer_zeros)
                return longer_zeros;
            // prepare for potential decimal comparison later
            if (!aperiod) {
                a_good = a + 1 < ae && *a == '.'
                    && isdigit((unsigned char) a[1]);
                b_good = b + 1 < be && *b == '.'
                    && isdigit((unsigned char) b[1]);
                if (a_good != b_good)
                    return negative == b_good ? 1 : -1;
                else if (a_good) {
                    aperiod = a + 1;
                    aperiod_negative = negative;
                }
            }

            // if we get here, the numeric portions were byte-for-byte
            // identical; move on
        } else if (isdigit((unsigned char) *a))
            return isalpha((unsigned char) *b) ? -1 : 1;
        else if (isdigit((unsigned char) *b))
            return isalpha((unsigned char) *a) ? 1 : -1;
        else {
            int alower = (unsigned char) tolower((unsigned char) *a);
            int blower = (unsigned char) tolower((unsigned char) *b);
            if (alower != blower)
                return alower - blower;
            if (raw_compare == 0)
                raw_compare = (unsigned char) *a - (unsigned char) *b;
            if (*a != '.')
                aperiod = 0;
            ++a;
            ++b;
        }
    }

    if ((ae - a) != (be - b))
        return (ae - a) - (be - b);
    else
        return raw_compare;
}

hashcode_t
String_generic::hashcode(const char *s, int len)
{
    if (len <= 0)
        return 0;

    uint32_t hash = len;
    int rem = hash & 3;
    const char *end = s + len - rem;
    uint32_t last16;

#if !HAVE_INDIFFERENT_ALIGNMENT
    if (!(reinterpret_cast<uintptr_t>(s) & 1)) {
#endif
#define get16(p) (*reinterpret_cast<const uint16_t *>((p)))
        for (; s != end; s += 4) {
            hash += get16(s);
            uint32_t tmp = (get16(s + 2) << 11) ^ hash;
            hash = (hash << 16) ^ tmp;
            hash += hash >> 11;
        }
        if (rem >= 2) {
            last16 = get16(s);
            goto rem2;
        }
#undef get16
#if !HAVE_INDIFFERENT_ALIGNMENT
    } else {
# if !__i386__ && !__x86_64__ && !__arch_um__
#  define get16(p) (((unsigned char) (p)[0] << 8) + (unsigned char) (p)[1])
# else
#  define get16(p) ((unsigned char) (p)[0] + ((unsigned char) (p)[1] << 8))
# endif
        // should be exactly the same as the code above
        for (; s != end; s += 4) {
            hash += get16(s);
            uint32_t tmp = (get16(s + 2) << 11) ^ hash;
            hash = (hash << 16) ^ tmp;
            hash += hash >> 11;
        }
        if (rem >= 2) {
            last16 = get16(s);
            goto rem2;
        }
# undef get16
    }
#endif

    /* Handle end cases */
    if (0) {                    // weird organization avoids uninitialized
      rem2:                     // variable warnings
        if (rem == 3) {
            hash += last16;
            hash ^= hash << 16;
            hash ^= ((unsigned char) s[2]) << 18;
            hash += hash >> 11;
        } else {
            hash += last16;
            hash ^= hash << 11;
            hash += hash >> 17;
        }
    } else if (rem == 1) {
        hash += (unsigned char) *s;
        hash ^= hash << 10;
        hash += hash >> 1;
    }

    /* Force "avalanching" of final 127 bits */
    hash ^= hash << 3;
    hash += hash >> 5;
    hash ^= hash << 4;
    hash += hash >> 17;
    hash ^= hash << 25;
    hash += hash >> 6;

    return hash;
}

int
String_generic::find_left(const char *s, int len, int start,
                          char x)
{
    if (start < 0)
        start = 0;
    for (int i = start; i < len; ++i)
        if (s[i] == x)
            return i;
    return -1;
}

int
String_generic::find_left(const char *s, int len, int start,
                          const char *x, int x_len)
{
    if (start < 0)
        start = 0;
    if (x_len == 0)
        return start <= len ? start : -1;
    int max_pos = len - x_len;
    for (int i = start; i <= max_pos; ++i)
        if (memcmp(s + i, x, x_len) == 0)
            return i;
    return -1;
}

int
String_generic::find_right(const char *s, int len, int start,
                           char x)
{
    if (start >= len)
        start = len - 1;
    for (int i = start; i >= 0; --i)
        if (s[i] == x)
            return i;
    return -1;
}

int
String_generic::find_right(const char *s, int len, int start,
                           const char *x, int x_len)
{
    if (start >= len)
        start = len - x_len;
    if (x_len == 0)
        return start >= 0 ? start : -1;
    for (int i = start; i >= 0; --i)
        if (memcmp(s + i, x, x_len) == 0)
            return i;
    return -1;
}

long String_generic::to_i(const char* s, const char* ends) {
    bool neg;
    if (s != ends && (s[0] == '-' || s[0] == '+')) {
        neg = s[0] == '-';
        ++s;
    } else
        neg = false;
    if (s == ends || !isdigit((unsigned char) *s))
        return 0;
    unsigned long x = (unsigned char) *s - '0';
    for (++s; s != ends && isdigit((unsigned char) *s); ++s)
        x = x * 10 + *s - '0';  // XXX overflow
    return neg ? -x : x;
}

bool String_generic::glob_match(const char* sbegin, int slen,
                                const char* pbegin, int plen) {
    const char* send = sbegin + slen;
    const char* pend = pbegin + plen;

    // quick common-case check for suffix matches
    while (pbegin < pend && sbegin < send
           && pend[-1] != '*' && pend[-1] != '?' && pend[-1] != ']'
           && (pbegin + 1 == pend || pend[-2] != '\\'))
        if (pend[-1] == send[-1])
            --pend, --send;
        else
            return false;

    std::vector<const char*> state, nextstate;
    state.push_back(pbegin);

    for (const char* s = sbegin; s != send && state.size(); ++s) {
        nextstate.clear();
        for (const char** pp = state.data(); pp != state.data() + state.size(); ++pp)
            if (*pp != pend) {
              reswitch:
                switch (**pp) {
                  case '?':
                    nextstate.push_back(*pp + 1);
                    break;
                  case '*':
                    if (*pp + 1 == pend)
                        return true;
                    if (nextstate.empty() || nextstate.back() != *pp)
                        nextstate.push_back(*pp);
                    ++*pp;
                    goto reswitch;
                  case '\\':
                    if (*pp + 1 != pend)
                        ++*pp;
                    goto normal_char;
                  case '[': {
                      const char *ec = *pp + 1;
                      bool negated;
                      if (ec != pend && *ec == '^') {
                          negated = true;
                          ++ec;
                      } else
                          negated = false;
                      if (ec == pend)
                          goto normal_char;

                      bool found = false;
                      do {
                          if (*++ec == *s)
                              found = true;
                      } while (ec != pend && *ec != ']');
                      if (ec == pend)
                          goto normal_char;

                      if (found == !negated)
                          nextstate.push_back(ec + 1);
                      break;
                  }
                  normal_char:
                  default:
                    if (**pp == *s)
                        nextstate.push_back(*pp + 1);
                    break;
                }
            }
        state.swap(nextstate);
    }

    for (const char** pp = state.data(); pp != state.data() + state.size(); ++pp) {
        while (*pp != pend && **pp == '*')
            ++*pp;
        if (*pp == pend)
            return true;
    }
    return false;
}


/** @cond never */
#if HAVE_STRING_PROFILING
void String::memo_type::account_new() {
    int bucket = profile_memo_size_bucket(this->dirty, this->capacity);
    ++memo_sizes[bucket];
    ++live_memo_sizes[bucket];
    live_memo_bytes[bucket] += this->capacity;
    ++live_memo_count;
# if HAVE_STRING_PROFILING > 1
    this->pprev = &live_memos[bucket];
    if ((this->next = *this->pprev))
        this->next->pprev = &this->next;
    *this->pprev = memo;
# endif
}

void String::memo_type::account_destroy() {
    int bucket = profile_memo_size_bucket(this->dirty, this->capacity);
    --live_memo_sizes[bucket];
    live_memo_bytes[bucket] -= this->capacity;
    --live_memo_count;
# if HAVE_STRING_PROFILING > 1
    if ((*this->pprev = this->next))
        this->next->pprev = this->pprev;
# endif
}
#endif

inline String::memo_type* String::create_memo(int capacity, int dirty) {
    assert(capacity > 0 && capacity >= dirty);
    memo_type *memo =
        reinterpret_cast<memo_type *>(new char[capacity + MEMO_SPACE]);
    if (memo)
        memo->initialize(capacity, dirty);
    return memo;
}

void
String::delete_memo(memo_type *memo)
{
    assert(memo->capacity > 0);
    assert(memo->capacity >= memo->dirty);
    memo->account_destroy();
    delete[] reinterpret_cast<char*>(memo);
}


#if HAVE_STRING_PROFILING
void
String::one_profile_report(StringAccum &sa, int i, int examples)
{
    if (i <= 16)
        sa << "memo_dirty_" << i;
    else if (i < 25) {
        uint32_t s = (i - 17) * 2 + 17;
        sa << "memo_cap_" << s << '_' << (s + 1);
    } else if (i < 29) {
        uint32_t s = (i - 25) * 8 + 33;
        sa << "memo_cap_" << s << '_' << (s + 7);
    } else {
        uint32_t s1 = (1U << (i - 23)) + 1;
        uint32_t s2 = (s1 - 1) << 1;
        sa << "memo_cap_" << s1 << '_' << s2;
    }
    sa << '\t' << live_memo_sizes[i] << '\t' << memo_sizes[i] << '\t' << live_memo_bytes[i] << '\n';
    if (examples) {
# if HAVE_STRING_PROFILING > 1
        for (memo_type *m = live_memos[i]; m; m = m->next) {
            sa << "    [" << m->dirty << "] ";
            uint32_t dirty = m->dirty;
            if (dirty > 0 && m->real_data[dirty - 1] == '\0')
                --dirty;
            sa.append(m->real_data, dirty > 128 ? 128 : dirty);
            sa << '\n';
        }
# endif
    }
}

void
String::profile_report(StringAccum &sa, int examples)
{
    uint64_t all_live_sizes = 0, all_sizes = 0, all_live_bytes = 0;
    for (int i = 0; i < 55; ++i) {
        if (memo_sizes[i])
            one_profile_report(sa, i, examples);
        all_live_sizes += live_memo_sizes[i];
        all_sizes += memo_sizes[i];
        all_live_bytes += live_memo_bytes[i];
    }
    sa << "memo_total\t" << all_live_sizes << '\t' << all_sizes << '\t' << all_live_bytes << '\n';
}
#endif

/** @endcond never */


/** @brief Construct a base-10 string representation of @a x. */
String::String(int x)
{
    if (x >= 0 && x < 10)
        _r.assign(int_data + 2 * x, 1, 0);
    else {
        char buf[128];
        sprintf(buf, "%d", x);
        assign(buf, -1, false);
    }
}

/** @overload */
String::String(unsigned x)
{
    if (x < 10)
        _r.assign(int_data + 2 * x, 1, 0);
    else {
        char buf[128];
        sprintf(buf, "%u", x);
        assign(buf, -1, false);
    }
}

/** @overload */
String::String(long x)
{
    if (x >= 0 && x < 10)
        _r.assign(int_data + 2 * x, 1, 0);
    else {
        char buf[128];
        sprintf(buf, "%ld", x);
        assign(buf, -1, false);
    }
}

/** @overload */
String::String(unsigned long x)
{
    if (x < 10)
        _r.assign(int_data + 2 * x, 1, 0);
    else {
        char buf[128];
        sprintf(buf, "%lu", x);
        assign(buf, -1, false);
    }
}

/** @overload */
String::String(long long x)
{
    if (x >= 0 && x < 10)
        _r.assign(int_data + 2 * x, 1, 0);
    else {
        char buf[128];
        sprintf(buf, "%lld", x);
        assign(buf, -1, false);
    }
}

/** @overload */
String::String(unsigned long long x)
{
    if (x < 10)
        _r.assign(int_data + 2 * x, 1, 0);
    else {
        char buf[128];
        sprintf(buf, "%llu", x);
        assign(buf, -1, false);
    }
}

String::String(double x)
{
    char buf[128];
    int len = sprintf(buf, "%.12g", x);
    assign(buf, len, false);
}

String
String::hard_make_stable(const char *s, int len)
{
    if (len < 0)
        len = strlen(s);
    return String(s, len, 0);
}

String
String::make_fill(int c, int len)
{
    String s;
    s.append_fill(c, len);
    return s;
}

void
String::assign_out_of_memory()
{
    _r.deref();
    _r = oom_string_rep;
}

void
String::assign(const char *s, int len, bool need_deref)
{
    if (!s) {
        assert(len <= 0);
        len = 0;
    } else if (len < 0)
        len = strlen(s);

    // need to start with dereference
    memo_type* m;
    if (need_deref) {
        if (unlikely((m = _r.memo())
                     && s >= m->real_data
                     && s + len <= m->real_data + m->capacity)) {
            // Be careful about "String s = ...; s = s.c_str();"
            _r.assign_noref(s, len, m);
            return;
        } else
            deref();
    }

    if (len == 0) {
        m = 0;
        s = String_generic::empty_data;

    } else {
        // Make the memo a multiple of 16 characters and bigger than 'len'.
        int memo_capacity = (len + 15 + MEMO_SPACE) & ~15;
        m = create_memo(memo_capacity - MEMO_SPACE, len);
        if (!m) {
            _r.reset_ref();
            assign_out_of_memory();
            return;
        }
        memcpy(m->real_data, s, len);
        s = m->real_data;
    }

    _r.assign_noref(s, len, m);
}

/** @brief Append @a len unknown characters to this string.
 * @return Modifiable pointer to the appended characters.
 *
 * The caller may safely modify the returned memory. Null is returned if
 * the string becomes out-of-memory. */
char *
String::append_uninitialized(int len)
{
    // Appending anything to "out of memory" leaves it as "out of memory"
    if (unlikely(len <= 0) || out_of_memory())
        return 0;

    // If we can, append into unused space. First, we check that there's
    // enough unused space for 'len' characters to fit; then, we check
    // that the unused space immediately follows the data in '*this'.
    uint32_t dirty;
    memo_type* m = _r.memo();
    if (m && ((dirty = m->dirty), m->capacity > dirty + len)) {
        char *real_dirty = m->real_data + dirty;
        if (real_dirty == _r.data + _r.length) {
            m->dirty = dirty + len;
            _r.length += len;
            assert(m->dirty < m->capacity);
#if HAVE_STRING_PROFILING
            profile_update_memo_dirty(m, dirty, dirty + len, m->capacity);
#endif
            return real_dirty;
        }
    }

    // Now we have to make new space. Make sure the memo is a multiple of 16
    // bytes and that it is at least 16. But for large strings, allocate a
    // power of 2, since power-of-2 sizes minimize waste in frequently-used
    // allocators, like Linux kmalloc.
    int want_memo_len = _r.length + len + MEMO_SPACE;
    int memo_capacity;
    if (want_memo_len <= 1024)
        memo_capacity = (want_memo_len + 15) & ~15;
    else
        for (memo_capacity = 2048; memo_capacity < want_memo_len; )
            memo_capacity *= 2;

    m = create_memo(memo_capacity - MEMO_SPACE, _r.length + len);
    if (!m) {
        assign_out_of_memory();
        return 0;
    }

    char *new_data = m->real_data;
    memcpy(new_data, _r.data, _r.length);

    deref();
    _r.assign_noref(new_data, _r.length + len, m);
    return const_cast<char*>(_r.data + _r.length - len);
}

void
String::append(const char* s, int len, memo_type* memo)
{
    if (!s) {
        assert(len <= 0);
        len = 0;
    } else if (len < 0)
        len = strlen(s);

    memo_type* my_memo;
    if (unlikely(len == 0) || out_of_memory())
        /* do nothing */;
    else if (unlikely(s == String_generic::out_of_memory_data) && !memo)
        // Appending "out of memory" to a regular string makes it "out of
        // memory"
        assign_out_of_memory();
    else if (_r.length == 0 && reinterpret_cast<uintptr_t>(memo) > 1) {
        deref();
        _r.assign(s, len, memo);
    } else if (likely(!((my_memo = _r.memo())
                        && s >= my_memo->real_data
                        && s + len <= my_memo->real_data + my_memo->capacity))) {
        if (char *space = append_uninitialized(len))
            memcpy(space, s, len);
    } else {
        String preserve_s(*this);
        if (char *space = append_uninitialized(len))
            memcpy(space, s, len);
    }
}

/** @brief Append @a len copies of character @a c to this string. */
void
String::append_fill(int c, int len)
{
    assert(len >= 0);
    if (char *space = append_uninitialized(len))
        memset(space, c, len);
}

/** @brief Ensure the string's data is unshared and return a mutable
    pointer to it. */
char *
String::mutable_data()
{
    // If _memo has a capacity (it's not one of the special strings) and it's
    // uniquely referenced, return _data right away.
    if (!is_shared())
        return const_cast<char *>(_r.data);

    // Otherwise, make a copy of it. Rely on: deref() doesn't change _data or
    // _length; and if _capacity == 0, then deref() doesn't free _real_data.
    // But in multithreaded situations we must hold a local copy of memo!
    String do_not_delete_underlying_memo(*this);
    deref();
    assign(_r.data, _r.length, false);
    return const_cast<char *>(_r.data);
}

const char *
String::hard_c_str() const
{
    // See also c_str().
    // We may already have a '\0' in the right place.  If _memo has no
    // capacity, then this is one of the special strings (null or
    // stable). We are guaranteed, in these strings, that _data[_length]
    // exists. Otherwise must check that _data[_length] exists.
    const char *end_data = _r.data + _r.length;
    memo_type* m = _r.memo();
    if ((m && end_data >= m->real_data + m->dirty)
        || *end_data != '\0') {
        if (char *x = const_cast<String *>(this)->append_uninitialized(1)) {
            *x = '\0';
            --_r.length;
        }
    }
    return _r.data;
}

/** @brief Null-terminate the string and return a mutable pointer to its
    data.
    @sa String::c_str */
char *
String::mutable_c_str()
{
    (void) mutable_data();
    (void) c_str();
    return const_cast<char *>(_r.data);
}

/** @brief Return a substring of this string, consisting of the @a len
    characters starting at index @a pos.
    @param pos substring's first position relative to the string
    @param len length of substring

    If @a pos is negative, starts that far from the end of the string. If @a
    len is negative, leaves that many characters off the end of the string.
    If @a pos and @a len specify a substring that is partly outside the
    string, only the part within the string is returned. If the substring is
    beyond either end of the string, returns an empty string (but this
    should be considered a programming error; a future version may generate
    a warning for this case).

    @note String::substr() is intended to behave like Perl's substr(). */
String
String::substr(int pos, int len) const
{
    if (pos < 0)
        pos += _r.length;

    int pos2;
    if (len < 0)
        pos2 = _r.length + len;
    else if (pos >= 0 && len >= _r.length) // avoid integer overflow
        pos2 = _r.length;
    else
        pos2 = pos + len;

    if (pos < 0)
        pos = 0;
    if (pos2 > _r.length)
        pos2 = _r.length;

    if (pos >= pos2)
        return String();
    else {
        _r.ref();
        return String(_r.data + pos, pos2 - pos, _r.memo());
    }
}

static String
hard_lower(const String &s, int pos)
{
    String new_s(s.data(), s.length());
    char *x = const_cast<char *>(new_s.data()); // know it's mutable
    int len = s.length();
    for (; pos < len; pos++)
        x[pos] = tolower((unsigned char) x[pos]);
    return new_s;
}

/** @brief Return a lowercased version of this string.

    Translates the ASCII characters 'A' through 'Z' into their lowercase
    equivalents. */
String
String::lower() const
{
    // avoid copies
    if (!out_of_memory())
        for (int i = 0; i < _r.length; i++)
            if (_r.data[i] >= 'A' && _r.data[i] <= 'Z')
                return hard_lower(*this, i);
    return *this;
}

static String
hard_upper(const String &s, int pos)
{
    String new_s(s.data(), s.length());
    char *x = const_cast<char *>(new_s.data()); // know it's mutable
    int len = s.length();
    for (; pos < len; pos++)
        x[pos] = toupper((unsigned char) x[pos]);
    return new_s;
}

/** @brief Return an uppercased version of this string.

    Translates the ASCII characters 'a' through 'z' into their uppercase
    equivalents. */
String
String::upper() const
{
    // avoid copies
    for (int i = 0; i < _r.length; i++)
        if (_r.data[i] >= 'a' && _r.data[i] <= 'z')
            return hard_upper(*this, i);
    return *this;
}

static String
hard_printable(const String &s, int pos, int type)
{
    StringAccum sa(s.length() * 2);
    sa.append(s.data(), pos);
    const unsigned char *x = reinterpret_cast<const unsigned char *>(s.data());
    int len = s.length();
    for (; pos < len; pos++) {
        if (type == 2 && (x[pos] == '\\' || x[pos] == '\"'))
            sa << '\\' << x[pos];
        else if (x[pos] >= 32 && x[pos] < 127)
            sa << x[pos];
        else if (x[pos] < 32 && type == 2) {
            if (x[pos] >= 9 && x[pos] <= 13)
                sa << '\\' << ("tnvfr"[x[pos] - 9]);
            else if (char *buf = sa.extend(4, 1))
                sprintf(buf, "\\%03o", x[pos]);
        } else if (x[pos] < 32 && type != 1)
            sa << '^' << (unsigned char)(x[pos] + 64);
        else if (char *buf = sa.extend(4, 1))
            sprintf(buf, "\\%03o", x[pos]);
    }
    return sa.take_string();
}

/** @brief Return a "printable" version of this string.
    @param type quoting type

    The default quoting type (0) translates control characters 0-31 into
    "control" sequences, such as "^@" for the null character, and characters
    127-255 into octal escape sequences, such as "\377" for 255. Quoting
    type 1 translates all characters outside of 32-126 into octal escape
    sequences. Quoting type 2 uses C escapes, including "\\" and "\"". */
String
String::printable(int type) const
{
    // avoid copies
    if (!out_of_memory())
        for (int i = 0; i < _r.length; i++)
            if (_r.data[i] < 32 || _r.data[i] > 126)
                return hard_printable(*this, i, type);
    return *this;
}

String String::to_hex() const {
    StringAccum sa;
    static const char hexval[] = "0123456789ABCDEF";
    char* x = sa.extend(2 * _r.length);
    for (int i = 0; i != _r.length; ++i) {
        *x++ = hexval[(unsigned char) _r.data[i] >> 4];
        *x++ = hexval[_r.data[i] & 15];
    }
    return sa.take_string();
}

/** @brief Return the substring with left whitespace removed. */
String
String::ltrim() const
{
    return String_generic::ltrim(*this);
}

/** @brief Return the substring with right whitespace removed. */
String
String::rtrim() const
{
    return String_generic::rtrim(*this);
}

/** @brief Return the substring with left and right whitespace removed. */
String
String::trim() const
{
    return String_generic::trim(*this);
}

void
String::align(int n)
{
    int offset = reinterpret_cast<uintptr_t>(_r.data) % n;
    if (offset) {
        String s;
        s.append_uninitialized(_r.length + n + 1);
        offset = reinterpret_cast<uintptr_t>(s._r.data) % n;
        memcpy((char *)s._r.data + n - offset, _r.data, _r.length);
        s._r.data += n - offset;
        s._r.length = _r.length;
        *this = s;
    }
}

/** @brief Return the pointer to the next character in UTF-8 encoding. */
const unsigned char *
String::skip_utf8_char(const unsigned char *s, const unsigned char *end)
{
    int c = *s;
    if (c > 0 && c < 0x80)
        return s + 1;
    else if (c < 0xC2)
        /* zero, or bad/overlong encoding */;
    else if (c < 0xE0) {        // 2 bytes: U+80-U+7FF
        if (likely(s + 1 < end
                   && s[1] >= 0x80 && s[1] < 0xC0))
            return s + 2;
    } else if (c < 0xF0) {      // 3 bytes: U+800-U+FFFF
        if (likely(s + 2 < end
                   && s[1] >= 0x80 && s[1] < 0xC0
                   && s[2] >= 0x80 && s[2] < 0xC0
                   && (c != 0xE0 || s[1] >= 0xA0) /* not overlong encoding */
                   && (c != 0xED || s[1] < 0xA0) /* not surrogate */))
            return s + 3;
    } else if (c < 0xF5) {      // 4 bytes: U+10000-U+10FFFF
        if (likely(s + 3 < end
                   && s[1] >= 0x80 && s[1] < 0xC0
                   && s[2] >= 0x80 && s[2] < 0xC0
                   && s[3] >= 0x80 && s[3] < 0xC0
                   && (c != 0xF0 || s[1] >= 0x90) /* not overlong encoding */
                   && (c != 0xF4 || s[1] < 0x90) /* not >U+10FFFF */))
            return s + 4;
    }
    return s;
}

int
String::parse_cesu8_char(const unsigned char *s, const unsigned char *end)
{
    if (s + 5 < end
        && s[0] == 0xED
        && s[1] >= 0xA0 && s[1] < 0xB0
        && s[2] >= 0x80 && s[2] < 0xC0
        && s[3] == 0xED
        && s[4] >= 0xB0 && s[4] < 0xC0
        && s[5] >= 0x80 && s[5] < 0xC0)
        return 0x10000
            + ((s[1] & 0x0F) << 16) + ((s[2] & 0x3F) << 10)
            + ((s[4] & 0x0F) << 6) + (s[5] & 0x3F);
    else
        return 0;
}

static const uint16_t windows1252_c1_mapping[] = {
    0x20AC, 0x0081, 0x201A, 0x0192, 0x201E, 0x2026, 0x2020, 0x2021,
    0x20C6, 0x2030, 0x0160, 0x2039, 0x0152, 0x008D, 0x017D, 0x008F,
    0x0090, 0x2018, 0x2019, 0x201C, 0x201D, 0x2022, 0x2013, 0x2014,
    0x20DC, 0x2122, 0x0161, 0x203A, 0x0153, 0x009D, 0x017E, 0x0178
};

String
String::windows1252_to_utf8() const
{
    const unsigned char *s = ubegin(), *last = s, *ends = uend();
    StringAccum sa;
    for (; s != ends; ++s) {
        int c = *s;
        if (unlikely(c == 0)) {
            sa.append(last, s);
            last = s + 1;
        } else if (likely(c < 128))
            /* do nothing */;
        else {
            sa.append(last, s);
            if (unlikely(c < 160))
                c = windows1252_c1_mapping[c - 128];
            sa.append_utf8(c);
            last = s + 1;
        }
    }
    if (last == ubegin())
        return *this;
    else {
        sa.append(last, s);
        return sa.take_string();
    }
}

String
String::utf16be_to_utf8(int flags) const
{
    const unsigned char *s = ubegin(), *ends = uend();
    if ((ends - s) & 1)
        --ends;
    if ((flags & utf_strip_bom) && s != ends
        && s[0] == 0xFE && s[1] == 0xFF)
        s += 2;
    StringAccum sa;
    sa.reserve((ends - s) / 2);
    for (; s != ends; s += 2) {
        int c = s[0] * 256 + s[1];
        if (likely(c < 0xD800) || c >= 0xE000)
            sa.append_utf8(c);
        else if (c < 0xDC00 && s + 2 != ends
                 && s[2] >= 0xDC && s[2] < 0xE0) {
            c = 0x10000 + ((c - 0xD800) << 10)
                + ((s[2] & 0x03) << 8) + s[3];
            sa.append_utf8(c);
            s += 2;
        } else if (c && (flags & utf_replacement))
            sa.append_utf8(u_replacement);
    }
    return sa.take_string();
}

String
String::utf16le_to_utf8(int flags) const
{
    const unsigned char *s = ubegin(), *ends = uend();
    if ((ends - s) & 1)
        --ends;
    if ((flags & utf_strip_bom) && s != ends
        && s[1] == 0xFE && s[0] == 0xFF)
        s += 2;
    StringAccum sa;
    sa.reserve((ends - s) / 2);
    for (; s != ends; s += 2) {
        int c = s[1] * 256 + s[0];
        if (likely(c < 0xD800) || c >= 0xE000)
            sa.append_utf8(c);
        else if (c < 0xDC00 && s + 2 != ends
                 && s[3] >= 0xDC && s[3] < 0xE0) {
            c = 0x10000 + ((c - 0xD800) << 10)
                + ((s[3] & 0x03) << 8) + s[2];
            sa.append_utf8(c);
            s += 2;
        } else if (c && (flags & utf_replacement))
            sa.append_utf8(u_replacement);
    }
    return sa.take_string();
}

String
String::utf16_to_utf8(int flags) const
{
    if (length() < 2)
        return String();
    const unsigned char *s = ubegin(), *ends = uend();
    if (ends - s < 2)
        return String();
    int c = s[0] * 256 + s[1];
    if (c == 0xFEFF || (c != 0xFFFE && !(flags & utf_prefer_le)))
        return utf16be_to_utf8(flags);
    else
        return utf16le_to_utf8(flags);
}

String
String::cesu8_to_utf8(int flags) const
{
    const unsigned char *s = ubegin(), *last = s, *t, *ends = uend();
    StringAccum sa;
    if (flags & utf_strip_bom)
        s = last = skip_utf8_bom(s, ends);
    while (s != ends) {
        int c = s[0];
        if (likely(c > 0 && c < 0x7F))
            ++s;
        else if (likely((t = skip_utf8_char(s, ends)) != s))
            s = t;
        else if ((c = parse_cesu8_char(s, ends))) {
            sa.append(last, s);
            sa.append_utf8(c);
            s += 6;
            last = s;
        } else {
            sa.append(last, s);
            if ((flags & utf_replacement) && c != 0)
                sa.append_utf8(u_replacement);
            for (++s; s != ends && *s >= 0x80 && *s < 0xC0; ++s)
                /* do nothing */;
            last = s;
        }
    }
    if (last == ubegin())
        return *this;
    else {
        sa.append(last, s);
        return sa.take_string();
    }
}

String
String::utf8_to_utf8(int flags) const
{
    const unsigned char *s = ubegin(), *last = s, *t, *ends = uend();
    StringAccum sa;
    if (flags & utf_strip_bom)
        s = last = skip_utf8_bom(s, ends);
    while (s != ends) {
        int c = s[0];
        if (likely(c > 0 && c < 0x7F))
            ++s;
        else if (likely((t = skip_utf8_char(s, ends)) != s))
            s = t;
        else {
            sa.append(last, s);
            if ((flags & utf_replacement) && c != 0)
                sa.append_utf8(u_replacement);
            for (++s; s != ends && *s >= 0x80 && *s < 0xC0; ++s)
                /* do nothing */;
            last = s;
        }
    }
    if (last == ubegin())
        return *this;
    else {
        sa.append(last, s);
        return sa.take_string();
    }
}

/** @brief Return a version of the string converted to UTF-8.

    Null characters are dropped.  Then, if the result contains invalid
    UTF-8, the string is assumed to be Windows-1252 encoded, and is
    converted to UTF-8 accordingly. */
String
String::to_utf8(int flags) const
{
    const unsigned char *s = ubegin(), *ends = uend();
    if (ends - s > 2) {
        if ((s[0] == 0xFF && s[1] == 0xFE)
            || (s[0] > 0 && s[0] < 0x80 && s[1] == 0))
            return utf16le_to_utf8(flags);
        else if ((s[0] == 0xFE && s[1] == 0xFF)
                 || (s[0] == 0 && s[1] > 0 && s[1] < 0x80))
            return utf16be_to_utf8(flags);
    }

    const unsigned char *last = s, *t;
    if (ends - s > 3 && (flags & utf_strip_bom))
        s = last = skip_utf8_bom(s, ends);
    StringAccum sa;
    bool any_long_utf8 = false;
    int c;
    while (s != ends) {
        if (likely(*s > 0 && *s < 128))
            ++s;
        else if (likely((t = skip_utf8_char(s, ends)) != s)) {
            any_long_utf8 = true;
            s = t;
        } else if ((c = parse_cesu8_char(s, ends)) != 0) {
            any_long_utf8 = true;
            sa.append(last, s);
            sa.append_utf8(c);
            s += 6;
            last = s;
        } else if (*s == 0) {
            sa.append(last, s);
            ++s;
            last = s;
        } else if (!any_long_utf8)
            goto windows1252;
        else {
            sa.append(last, s);
            int c = *s;
            if (c < 160)
                c = windows1252_c1_mapping[c - 128];
            sa.append_utf8(c);
            ++s;
            last = s;
        }
    }

 exit:
    if (last == ubegin())
        return *this;
    else {
        sa.append(last, ends);
        return sa.take_string();
    }

 windows1252:
    while (s != ends) {
        if (likely(*s > 0 && *s < 128))
            ++s;
        else {
            sa.append(last, s);
            if (*s != 0) {
                int c = *s;
                if (c < 160)
                    c = windows1252_c1_mapping[c - 128];
                sa.append_utf8(c);
            }
            ++s;
            last = s;
        }
    }
    goto exit;
}

/** @brief Return this string's contents encoded for JSON.
    @pre *this is encoded in UTF-8.

    For instance, String("a\"").encode_json() == "a\\\"". Note that the
    double-quote characters that usually surround a JSON string are not
    included. */
String String::encode_json() const {
    StringAccum sa;
    const char* last = encode_json_partial(sa);
    if (last == begin())
        return *this;
    else {
        sa.append(last, end());
        return sa.take_string();
    }
}

String String::encode_base64(bool pad) const {
    StringAccum sa;
    encode_base64(sa, pad);
    return sa.take_string();
}

String String::decode_base64() const {
    StringAccum sa;
    if (!decode_base64(sa))
        return String();
    return sa.take_string();
}

String String::encode_uri_component() const {
    StringAccum sa;
    encode_uri_component(sa);
    return sa.take_string();
}

} // namespace lcdf