// -*- related-file-name: "../include/lcdf/string.hh" -*- /* * string.{cc,hh} -- a String class with shared substrings * Eddie Kohler * * Copyright (c) 1999-2000 Massachusetts Institute of Technology * Copyright (c) 2001-2011 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. */ #ifdef HAVE_CONFIG_H # include #endif #include #include #include #include #include #include /** @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. * *

Initialization

* * The String implementation must be explicitly initialized before use; see * static_initialize(). Explicit initialization is used because static * constructors and other automatic initialization tricks don't work in the * kernel. However, at user level, you can declare a String::Initializer * object to initialize the library. * *

Out-of-memory strings

* * 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. * * Out-of-memory strings have zero characters, but they aren't equal to other * empty strings. If @a s is a normal String (even an empty string), and @a * oom is an out-of-memory string, then @a s @< @a oom. * * All 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 an out-of-memory string. */ const char String::null_data = '\0'; const char String::oom_data = '\0'; const char String::bool_data[] = "true\0false"; 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_t String::null_string_rep = { &null_data, 0, 0 }; const String::rep_t String::oom_string_rep = { &oom_data, 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_t *String::live_memos[55]; # endif #endif /** @cond never */ String::memo_t * String::create_memo(char *space, int dirty, int capacity) { assert(capacity > 0 && capacity >= dirty); memo_t *memo; if (space) memo = reinterpret_cast(space); else memo = reinterpret_cast(new char[MEMO_SPACE + capacity]); if (memo) { memo->capacity = capacity; memo->dirty = dirty; memo->refcount = (space ? 0 : 1); #if HAVE_STRING_PROFILING int bucket = profile_memo_size_bucket(dirty, capacity); ++memo_sizes[bucket]; ++live_memo_sizes[bucket]; live_memo_bytes[bucket] += capacity; ++live_memo_count; # if HAVE_STRING_PROFILING > 1 memo->pprev = &live_memos[bucket]; if ((memo->next = *memo->pprev)) memo->next->pprev = &memo->next; *memo->pprev = memo; # endif #endif } return memo; } void String::delete_memo(memo_t *memo) { assert(memo->capacity > 0); assert(memo->capacity >= memo->dirty); #if HAVE_STRING_PROFILING int bucket = profile_memo_size_bucket(memo->dirty, memo->capacity); --live_memo_sizes[bucket]; live_memo_bytes[bucket] -= memo->capacity; --live_memo_count; # if HAVE_STRING_PROFILING > 1 if ((*memo->pprev = memo->next)) memo->next->pprev = memo->pprev; # endif #endif delete[] reinterpret_cast(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_t *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 */ String::String(int x) { if (x >= 0 && x < 10) assign_memo(int_data + 2 * x, 1, 0); else { char buf[128]; sprintf(buf, "%d", x); assign(buf, -1, false); } } String::String(unsigned x) { if (x < 10) assign_memo(int_data + 2 * x, 1, 0); else { char buf[128]; sprintf(buf, "%u", x); assign(buf, -1, false); } } String::String(long x) { if (x >= 0 && x < 10) assign_memo(int_data + 2 * x, 1, 0); else { char buf[128]; sprintf(buf, "%ld", x); assign(buf, -1, false); } } String::String(unsigned long x) { if (x < 10) assign_memo(int_data + 2 * x, 1, 0); else { char buf[128]; sprintf(buf, "%lu", x); assign(buf, -1, false); } } String::String(double x) { char buf[128]; int len = sprintf(buf, "%.12g", x); assign(buf, len, false); } String String::make_claim(char *str, int len, int capacity) { assert(str && len > 0 && capacity >= len); memo_t *new_memo = create_memo(str - MEMO_SPACE, len, capacity); return String(str, len, new_memo); } String String::make_stable(const char *s, int len) { if (len < 0) len = (s ? strlen(s) : 0); return String(s, len, 0); } String String::make_garbage(int len) { String s; s.append_garbage(len); return s; } String String::make_fill(int c, int len) { String s; s.append_fill(c, len); return s; } void String::assign_out_of_memory() { if (_r.memo) deref(); _r.memo = 0; _r.data = &oom_data; _r.length = 0; } void String::assign(const char *str, int len, bool need_deref) { if (!str) { assert(len <= 0); len = 0; } else if (len < 0) len = strlen(str); // need to start with dereference if (need_deref) { if (_r.memo && str >= _r.memo->real_data && str + len <= _r.memo->real_data + _r.memo->capacity) { // Be careful about "String s = ...; s = s.c_str();" _r.data = str; _r.length = len; return; } else deref(); } if (len == 0) { _r.memo = 0; _r.data = (str == &oom_data ? str : &null_data); } else { // Make the memo a multiple of 16 characters and bigger than 'len'. int memo_capacity = (len + 15 + MEMO_SPACE) & ~15; _r.memo = create_memo(0, len, memo_capacity - MEMO_SPACE); if (!_r.memo) { assign_out_of_memory(); return; } memcpy(_r.memo->real_data, str, len); _r.data = _r.memo->real_data; } _r.length = len; } char * String::append_garbage(int len) { // Appending anything to "out of memory" leaves it as "out of memory" if (len <= 0 || _r.data == &oom_data) 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; if (_r.memo && ((dirty = _r.memo->dirty), _r.memo->capacity > dirty + len)) { char *real_dirty = _r.memo->real_data + dirty; if (real_dirty == _r.data + _r.length) { _r.memo->dirty = dirty + len; _r.length += len; assert(_r.memo->dirty < _r.memo->capacity); #if HAVE_STRING_PROFILING profile_update_memo_dirty(_r.memo, dirty, dirty + len, _r.memo->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; memo_t *new_memo = create_memo(0, _r.length + len, memo_capacity - MEMO_SPACE); if (!new_memo) { assign_out_of_memory(); return 0; } char *new_data = new_memo->real_data; memcpy(new_data, _r.data, _r.length); deref(); _r.data = new_data; new_data += _r.length; // now new_data points to the garbage _r.length += len; _r.memo = new_memo; return new_data; } void String::append(const char *s, int len) { if (!s) { assert(len <= 0); len = 0; } else if (len < 0) len = strlen(s); if (s == &oom_data) // Appending "out of memory" to a regular string makes it "out of // memory" assign_out_of_memory(); else if (len == 0) /* do nothing */; else if (!(_r.memo && s >= _r.memo->real_data && s + len <= _r.memo->real_data + _r.memo->capacity)) { if (char *space = append_garbage(len)) memcpy(space, s, len); } else { String preserve_s(*this); if (char *space = append_garbage(len)) memcpy(space, s, len); } } void String::append_fill(int c, int len) { assert(len >= 0); if (char *space = append_garbage(len)) memset(space, c, len); } 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 (_r.memo && _r.memo->refcount == 1) return const_cast(_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. assert(!_r.memo || _r.memo->refcount > 1); // 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(_r.data); } char * String::mutable_c_str() { (void) mutable_data(); (void) c_str(); return const_cast(_r.data); } String String::substring(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 return String(_r.data + pos, pos2 - pos, _r.memo); } int String::find_left(char c, int start) const { if (start < 0) start = 0; for (int i = start; i < _r.length; i++) if (_r.data[i] == c) return i; return -1; } int String::find_left(const String &str, int start) const { if (start < 0) start = 0; if (start >= length()) return -1; if (!str.length()) return 0; int first_c = (unsigned char)str[0]; int pos = start, max_pos = length() - str.length(); for (pos = find_left(first_c, pos); pos >= 0 && pos <= max_pos; pos = find_left(first_c, pos + 1)) if (!memcmp(_r.data + pos, str._r.data, str.length())) return pos; return -1; } int String::find_right(char c, int start) const { if (start >= _r.length) start = _r.length - 1; for (int i = start; i >= 0; i--) if (_r.data[i] == c) return i; return -1; } static String hard_lower(const String &s, int pos) { String new_s(s.data(), s.length()); char *x = const_cast(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; } String String::lower() const { // avoid copies 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(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; } 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) { StringAccum sa(s.length() * 2); sa.append(s.data(), pos); const unsigned char *x = reinterpret_cast(s.data()); int len = s.length(); for (; pos < len; pos++) { if (x[pos] >= 32 && x[pos] < 127) sa << x[pos]; else if (x[pos] < 32) sa << '^' << (unsigned char)(x[pos] + 64); else if (char *buf = sa.extend(4, 1)) sprintf(buf, "\\%03o", x[pos]); } return sa.take_string(); } String String::printable() const { // avoid copies for (int i = 0; i < _r.length; i++) if (_r.data[i] < 32 || _r.data[i] > 126) return hard_printable(*this, i); return *this; } hashcode_t String::hashcode(const char *begin, const char *end) { if (end <= begin) return 0; uint32_t hash = end - begin; int rem = hash & 3; end -= rem; uint32_t last16; #if !HAVE_INDIFFERENT_ALIGNMENT if (!(reinterpret_cast(begin) & 1)) { #endif #define get16(p) (*reinterpret_cast((p))) for (; begin != end; begin += 4) { hash += get16(begin); uint32_t tmp = (get16(begin + 2) << 11) ^ hash; hash = (hash << 16) ^ tmp; hash += hash >> 11; } if (rem >= 2) { last16 = get16(begin); goto rem2; } #undef get16 #if !HAVE_INDIFFERENT_ALIGNMENT } else { # if !__i386__ # 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 (; begin != end; begin += 4) { hash += get16(begin); uint32_t tmp = (get16(begin + 2) << 11) ^ hash; hash = (hash << 16) ^ tmp; hash += hash >> 11; } if (rem >= 2) { last16 = get16(begin); 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) begin[2]) << 18; hash += hash >> 11; } else { hash += last16; hash ^= hash << 11; hash += hash >> 17; } } else if (rem == 1) { hash += (unsigned char) *begin; 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; } #if 0 // 11.Apr.2008 -- This old hash function was swapped out in favor of // SuperFastHash, above. hashcode_t String::hashcode() const { int l = length(); const char *d = data(); if (!l) return 0; else if (l == 1) return d[0] | (d[0] << 8); else if (l < 4) return d[0] + (d[1] << 3) + (l << 12); else return d[0] + (d[1] << 8) + (d[2] << 16) + (d[3] << 24) + (l << 12) + (d[l-1] << 10); } #endif bool String::equals(const char *s, int len) const { // It'd be nice to make "out-of-memory" strings compare unequal to // anything, even themselves, but this would be a bad idea for Strings // used as (for example) keys in hashtables. Instead, "out-of-memory" // strings compare unequal to other null strings, but equal to each other. if (len < 0) len = strlen(s); if (_r.length != len) return false; else if (_r.data == s) return true; else if (len == 0) return (s != &oom_data && _r.data != &oom_data); else return memcmp(_r.data, s, len) == 0; } bool String::starts_with(const char *s, int len) const { // See note on equals() re: "out-of-memory" strings. if (len < 0) len = strlen(s); if (_r.length < len) return false; else if (_r.data == s) return true; else if (len == 0) return (s != &oom_data && _r.data != &oom_data); else return memcmp(_r.data, s, len) == 0; } int String::compare(const char *s, int len) const { if (len < 0) len = strlen(s); if (_r.data == s) return _r.length - len; else if (_r.data == &oom_data) return 1; else if (s == &oom_data) return -1; else if (_r.length == len) return memcmp(_r.data, s, len); else if (_r.length < len) { int v = memcmp(_r.data, s, _r.length); return (v ? v : -1); } else { int v = memcmp(_r.data, s, len); return (v ? v : 1); } } void String::align(int n) { int offset = reinterpret_cast(_r.data) % n; if (offset) { String s; s.append_garbage(_r.length + n + 1); offset = reinterpret_cast(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; } }