diff options
Diffstat (limited to 'Build/source/texk/lcdf-typetools/lcdf-typetools-src/liblcdf/string.cc')
-rw-r--r-- | Build/source/texk/lcdf-typetools/lcdf-typetools-src/liblcdf/string.cc | 786 |
1 files changed, 0 insertions, 786 deletions
diff --git a/Build/source/texk/lcdf-typetools/lcdf-typetools-src/liblcdf/string.cc b/Build/source/texk/lcdf-typetools/lcdf-typetools-src/liblcdf/string.cc deleted file mode 100644 index 41e7ae0d602..00000000000 --- a/Build/source/texk/lcdf-typetools/lcdf-typetools-src/liblcdf/string.cc +++ /dev/null @@ -1,786 +0,0 @@ -// -*- 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-2019 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 <config.h> -#endif -#include <lcdf/string.hh> -#include <lcdf/straccum.hh> -#include <stdio.h> -#include <string.h> -#include <ctype.h> -#include <lcdf/inttypes.h> - -#ifndef likely -#define likely(x) (x) -#endif -#ifndef unlikely -#define unlikely(x) (x) -#endif - -/** @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. - * - * 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<memo_t *>(space); - else - memo = reinterpret_cast<memo_t *>(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<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_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 */ - - -/** @brief Construct a base-10 string representation of @a x. */ -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); - } -} - -/** @overload */ -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); - } -} - -/** @overload */ -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); - } -} - -/** @overload */ -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_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 *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 - if (need_deref) { - if (unlikely(_r.memo - && s >= _r.memo->real_data - && s + len <= _r.memo->real_data + _r.memo->capacity)) { - // Be careful about "String s = ...; s = s.c_str();" - _r.data = s; - _r.length = len; - return; - } else - deref(); - } - - if (len == 0) { - _r.memo = 0; - _r.data = (s == &oom_data ? s : &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, s, len); - _r.data = _r.memo->real_data; - } - - _r.length = len; -} - -/** @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; - 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, memo_t *memo) -{ - 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.length == 0 && memo && !out_of_memory()) { - deref(); - assign_memo(s, len, memo); - } else if (likely(!(_r.memo - && s >= _r.memo->real_data - && s + len <= _r.memo->real_data + _r.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 (_r.memo && _r.memo->refcount == 1) - 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. - 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<char *>(_r.data); -} - -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::substring() is intended to behave like Perl's substr(). */ -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; - int max_pos = length() - str.length(); - for (int i = start; i <= max_pos; ++i) - if (memcmp(_r.data + i, str.data(), str.length()) == 0) - return i; - 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<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 (x[pos] >= 32 && x[pos] < 127) - sa << 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. */ -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; -} - -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<uintptr_t>(begin) & 1)) { -#endif -#define get16(p) (*reinterpret_cast<const uint16_t *>((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 WORDS_BIGENDIAN -# define get16(p) (((unsigned char) (p)[0] << 8) + (unsigned char) (p)[1]) -# elif WORDS_BIGENDIAN_SET -# define get16(p) ((unsigned char) (p)[0] + ((unsigned char) (p)[1] << 8)) -# else -# error "unknown byte order" -# 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<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; - } -} |