| // Copyright 2003, Google Inc. All rights reserved. |
| |
| #include "gutil/strings/serialize.h" |
| |
| #include <stddef.h> |
| #include <stdlib.h> |
| #include <string> |
| using std::string; |
| #include <utility> |
| using std::make_pair; |
| using std::pair; |
| #include <vector> |
| using std::vector; |
| #include <unordered_map> |
| using std::unordered_map; |
| |
| #include "gutil/casts.h" |
| #include "gutil/integral_types.h" |
| #include "gutil/stringprintf.h" |
| #include "gutil/strtoint.h" |
| #include "gutil/strings/join.h" |
| #include "gutil/strings/split.h" |
| #include "gutil/hash/hash.h" |
| |
| // Convert a uint32 to a 4-byte string. |
| string Uint32ToKey(uint32 u32) { |
| string key; |
| KeyFromUint32(u32, &key); |
| return key; |
| } |
| |
| string Uint64ToKey(uint64 fp) { |
| string key; |
| KeyFromUint64(fp, &key); |
| return key; |
| } |
| |
| // Convert a uint128 to a 16-byte string. |
| string Uint128ToKey(uint128 u128) { |
| string key; |
| KeyFromUint128(u128, &key); |
| return key; |
| } |
| |
| // Converts int32 to a 4-byte string key |
| // NOTE: Lexicographic ordering of the resulting strings does not in |
| // general correspond to any natural ordering of the corresponding |
| // integers. For non-negative inputs, lexicographic ordering of the |
| // resulting strings corresponds to increasing ordering of the |
| // integers. However, negative inputs are sorted *after* the non-negative |
| // inputs. To obtain keys such that lexicographic ordering corresponds |
| // to the natural total order on the integers, use OrderedStringFromInt32() |
| // or ReverseOrderedStringFromInt32() instead. |
| void KeyFromInt32(int32 i32, string* key) { |
| // TODO(user): Redefine using bit_cast<> and KeyFromUint32()? |
| key->resize(sizeof(i32)); |
| for (int i = sizeof(i32) - 1; i >= 0; --i) { |
| (*key)[i] = i32 & 0xff; |
| i32 = (i32 >> 8); |
| } |
| } |
| |
| // Converts a 4-byte string key (typically generated by KeyFromInt32) |
| // into an int32 value |
| int32 KeyToInt32(const StringPiece& key) { |
| int32 i32 = 0; |
| CHECK_EQ(key.size(), sizeof(i32)); |
| for (size_t i = 0; i < sizeof(i32); ++i) { |
| i32 = (i32 << 8) | static_cast<unsigned char>(key[i]); |
| } |
| return i32; |
| } |
| |
| // Converts a double value to an 8-byte string key, so that |
| // the string keys sort in the same order as the original double values. |
| void KeyFromDouble(double x, string* key) { |
| uint64 n = bit_cast<uint64>(x); |
| // IEEE standard 754 floating point representation |
| // [sign-bit] [exponent] [mantissa] |
| // |
| // Let "a", "b" be two double values, and F(.) be following |
| // transformation. We have: |
| // If 0 < a < b: |
| // 0x80000000ULL < uint64(F(a)) < uint64(F(b)) |
| // If a == -0.0, b == +0.0: |
| // uint64(F(-0.0)) == uint64(F(+0.0)) = 0x80000000ULL |
| // If a < b < 0: |
| // uint64(F(a)) < uint64(F(b)) < 0x80000000ULL |
| const uint64 sign_bit = GG_ULONGLONG(1) << 63; |
| if ((n & sign_bit) == 0) { |
| n += sign_bit; |
| } else { |
| n = -n; |
| } |
| KeyFromUint64(n, key); |
| } |
| |
| // Version of KeyFromDouble that returns the key. |
| string DoubleToKey(double x) { |
| string key; |
| KeyFromDouble(x, &key); |
| return key; |
| } |
| |
| // Converts key generated by KeyFromDouble() back to double. |
| double KeyToDouble(const StringPiece& key) { |
| int64 n = KeyToUint64(key); |
| if (n & (GG_ULONGLONG(1) << 63)) |
| n -= (GG_ULONGLONG(1) << 63); |
| else |
| n = -n; |
| return bit_cast<double>(n); |
| } |
| |
| // Converts int32 to a 4-byte string key such that lexicographic |
| // ordering of strings is equivalent to sorting in increasing order by |
| // integer values. This can be useful when constructing secondary |
| void OrderedStringFromInt32(int32 i32, string* key) { |
| uint32 ui32 = static_cast<uint32>(i32) ^ 0x80000000; |
| key->resize(sizeof ui32); |
| for ( int i = (sizeof ui32) - 1; i >= 0; --i ) { |
| (*key)[i] = ui32 & 0xff; |
| ui32 = (ui32 >> 8); |
| } |
| } |
| |
| string Int32ToOrderedString(int32 i32) { |
| string key; |
| OrderedStringFromInt32(i32, &key); |
| return key; |
| } |
| |
| // The inverse of the above function. |
| int32 OrderedStringToInt32(const StringPiece& key) { |
| uint32 ui32 = 0; |
| CHECK(key.size() == sizeof ui32); |
| for ( int i = 0; i < sizeof ui32; ++i ) { |
| ui32 = (ui32 << 8); |
| ui32 = ui32 | static_cast<unsigned char>(key[i]); |
| } |
| return static_cast<int32>(ui32 ^ 0x80000000); |
| } |
| |
| // Converts int64 to a 8-byte string key such that lexicographic |
| // ordering of strings is equivalent to sorting in increasing order by |
| // integer values. |
| void OrderedStringFromInt64(int64 i64, string* key) { |
| uint64 ui64 = static_cast<uint64>(i64) ^ (GG_ULONGLONG(1) << 63); |
| key->resize(sizeof ui64); |
| for ( int i = (sizeof ui64) - 1; i >= 0; --i ) { |
| (*key)[i] = ui64 & 0xff; |
| ui64 = (ui64 >> 8); |
| } |
| } |
| |
| string Int64ToOrderedString(int64 i64) { |
| string key; |
| OrderedStringFromInt64(i64, &key); |
| return key; |
| } |
| |
| // The inverse of the above function. |
| int64 OrderedStringToInt64(const StringPiece& key) { |
| uint64 ui64 = 0; |
| CHECK(key.size() == sizeof ui64); |
| for ( int i = 0; i < sizeof ui64; ++i ) { |
| ui64 = (ui64 << 8); |
| ui64 = ui64 | static_cast<unsigned char>(key[i]); |
| } |
| return static_cast<int64>(ui64 ^ (GG_ULONGLONG(1) << 63)); |
| } |
| |
| // Converts int32 to a 4-byte string key such that lexicographic |
| // ordering of strings is equivalent to sorting in decreasing order |
| // by integer values. This can be useful when constructing secondary |
| void ReverseOrderedStringFromInt32(int32 i32, string* key) { |
| // ~ is like -, but works even for INT_MIN. (-INT_MIN == INT_MIN, |
| // but ~x = -x - 1, so ~INT_MIN = -INT_MIN - 1 = INT_MIN - 1 = INT_MAX). |
| OrderedStringFromInt32(~i32, key); |
| } |
| |
| string Int32ToReverseOrderedString(int32 i32) { |
| string key; |
| ReverseOrderedStringFromInt32(i32, &key); |
| return key; |
| } |
| |
| // The inverse of the above function. |
| int32 ReverseOrderedStringToInt32(const StringPiece& key) { |
| return ~OrderedStringToInt32(key); |
| } |
| |
| // Converts int64 to an 8-byte string key such that lexicographic |
| // ordering of strings is equivalent to sorting in decreasing order |
| // by integer values. This can be useful when constructing secondary |
| void ReverseOrderedStringFromInt64(int64 i64, string* key) { |
| return OrderedStringFromInt64(~i64, key); |
| } |
| |
| string Int64ToReverseOrderedString(int64 i64) { |
| string key; |
| ReverseOrderedStringFromInt64(i64, &key); |
| return key; |
| } |
| |
| // The inverse of the above function. |
| int64 ReverseOrderedStringToInt64(const StringPiece& key) { |
| return ~OrderedStringToInt64(key); |
| } |
| |
| // -------------------------------------------------------------------------- |
| // DictionaryInt32Encode |
| // DictionaryInt64Encode |
| // DictionaryDoubleEncode |
| // DictionaryInt32Decode |
| // DictionaryInt64Decode |
| // DictionaryDoubleDecode |
| // Routines to serialize/unserialize simple dictionaries |
| // (string->T hashmaps). We use ':' to separate keys and values, |
| // and commas to separate entries. |
| // -------------------------------------------------------------------------- |
| |
| string DictionaryInt32Encode(const unordered_map<string, int32>* dictionary) { |
| vector<string> entries; |
| for (const auto& entry : *dictionary) { |
| entries.push_back(StringPrintf("%s:%d", entry.first.c_str(), entry.second)); |
| } |
| |
| string result; |
| JoinStrings(entries, ",", &result); |
| return result; |
| } |
| |
| string DictionaryInt64Encode(const unordered_map<string, int64>* dictionary) { |
| vector<string> entries; |
| for (const auto& entry : *dictionary) { |
| entries.push_back(StringPrintf("%s:%" PRId64, |
| entry.first.c_str(), entry.second)); |
| } |
| |
| string result; |
| JoinStrings(entries, ",", &result); |
| return result; |
| } |
| |
| string DictionaryDoubleEncode(const unordered_map<string, double>* dictionary) { |
| vector<string> entries; |
| for (const auto& entry : *dictionary) { |
| entries.push_back(StringPrintf("%s:%g", entry.first.c_str(), entry.second)); |
| } |
| |
| string result; |
| JoinStrings(entries, ",", &result); |
| return result; |
| } |
| |
| bool DictionaryParse(const string& encoded_str, |
| vector<pair<string, string> >* items) { |
| vector<string> entries; |
| SplitStringUsing(encoded_str, ",", &entries); |
| for (const auto& entry : entries) { |
| vector<string> fields; |
| SplitStringAllowEmpty(entry, ":", &fields); |
| if (fields.size() != 2) // parsing error |
| return false; |
| items->push_back(make_pair(fields[0], fields[1])); |
| } |
| return true; |
| } |
| |
| bool DictionaryInt32Decode(unordered_map<string, int32>* dictionary, |
| const string& encoded_str) { |
| vector<pair<string, string> > items; |
| if (!DictionaryParse(encoded_str, &items)) |
| return false; |
| |
| dictionary->clear(); |
| for (const auto& item : items) { |
| char *error = nullptr; |
| const int32 value = strto32(item.second.c_str(), &error, 0); |
| if (error == item.second.c_str() || *error != '\0') { |
| // parsing error |
| return false; |
| } |
| (*dictionary)[item.first] = value; |
| } |
| return true; |
| } |
| |
| bool DictionaryInt64Decode(unordered_map<string, int64>* dictionary, |
| const string& encoded_str) { |
| vector<pair<string, string> > items; |
| if (!DictionaryParse(encoded_str, &items)) |
| return false; |
| |
| dictionary->clear(); |
| for (const auto& item : items) { |
| char *error = nullptr; |
| const int64 value = strto64(item.second.c_str(), &error, 0); |
| if (error == item.second.c_str() || *error != '\0') { |
| // parsing error |
| return false; |
| } |
| (*dictionary)[item.first] = value; |
| } |
| return true; |
| } |
| |
| |
| bool DictionaryDoubleDecode(unordered_map<string, double>* dictionary, |
| const string& encoded_str) { |
| vector<pair<string, string> > items; |
| if (!DictionaryParse(encoded_str, &items)) |
| return false; |
| |
| dictionary->clear(); |
| for (const auto& item : items) { |
| char *error = nullptr; |
| const double value = strtod(item.second.c_str(), &error); |
| if (error == item.second.c_str() || *error != '\0') { |
| // parsing error |
| return false; |
| } |
| (*dictionary)[item.first] = value; |
| } |
| return true; |
| } |