| 43 | #pragma mark - WRITING: |
| 44 | |
| 45 | class keyTreeWriter { |
| 46 | public: |
| 47 | keyTreeWriter(const std::vector<slice> &strings) |
| 48 | :_strings(strings), |
| 49 | _sizes(strings.size()) |
| 50 | { } |
| 51 | |
| 52 | alloc_slice writeTree() { |
| 53 | auto n = _strings.size(); |
| 54 | size_t totalSize = 1 + sizeKeyTree(0, n); |
| 55 | alloc_slice output(totalSize); |
| 56 | _out = (uint8_t*)output.buf; |
| 57 | |
| 58 | writeByte((uint8_t)ceil(log2(n))); // Write the depth first |
| 59 | writeKeyTree(0, n); |
| 60 | assert_postcondition(_out == output.end()); |
| 61 | return output; |
| 62 | } |
| 63 | |
| 64 | private: |
| 65 | const std::vector<slice> &_strings; |
| 66 | std::vector<size_t> _sizes; |
| 67 | uint8_t* _out; |
| 68 | |
| 69 | // Same logic as writeKeyTree, but just returns the size it would write, without writing. |
| 70 | size_t sizeKeyTree(size_t begin, size_t end) |
| 71 | { |
| 72 | size_t mid = (begin + end) / 2; |
| 73 | slice str = _strings[mid]; |
| 74 | size_t size = SizeOfVarInt(str.size) + str.size; // middle string, with length prefix |
| 75 | |
| 76 | if (end - begin > 1) { |
| 77 | size_t leftSize = sizeKeyTree(begin, mid); |
| 78 | if (mid+1 < end) { |
| 79 | size += SizeOfVarInt(leftSize); // right subtree offset |
| 80 | size += leftSize; // left subtree |
| 81 | size += sizeKeyTree(mid+1, end); // right subtree |
| 82 | } else { |
| 83 | size += 1; // no right subtree (offset 0) |
| 84 | size += leftSize; // left subtree |
| 85 | } |
| 86 | } |
| 87 | _sizes[mid] = size; |
| 88 | return size; |
| 89 | } |
| 90 | |
| 91 | void writeKeyTree(size_t begin, size_t end) |
| 92 | { |
| 93 | size_t mid = (begin + end) / 2; |
| 94 | // Write middle string, with length prefix: |
| 95 | slice str = _strings[mid]; |
| 96 | writeVarInt(str.size); |
| 97 | write(str); |
| 98 | |
| 99 | if (end - begin > 1) { |
| 100 | if (mid+1 < end) { |
| 101 | size_t leftSize = _sizes[(begin + mid) / 2]; |
| 102 | writeVarInt(leftSize); // Write right subtree offset |