| 1097 | } |
| 1098 | |
| 1099 | size_t EndMap(size_t start) { |
| 1100 | // We should have interleaved keys and values on the stack. |
| 1101 | // Make sure it is an even number: |
| 1102 | auto len = stack_.size() - start; |
| 1103 | FLATBUFFERS_ASSERT(!(len & 1)); |
| 1104 | len /= 2; |
| 1105 | // Make sure keys are all strings: |
| 1106 | for (auto key = start; key < stack_.size(); key += 2) { |
| 1107 | FLATBUFFERS_ASSERT(stack_[key].type_ == FBT_KEY); |
| 1108 | } |
| 1109 | // Now sort values, so later we can do a binary search lookup. |
| 1110 | // We want to sort 2 array elements at a time. |
| 1111 | struct TwoValue { |
| 1112 | Value key; |
| 1113 | Value val; |
| 1114 | }; |
| 1115 | // TODO(wvo): strict aliasing? |
| 1116 | // TODO(wvo): allow the caller to indicate the data is already sorted |
| 1117 | // for maximum efficiency? With an assert to check sortedness to make sure |
| 1118 | // we're not breaking binary search. |
| 1119 | // Or, we can track if the map is sorted as keys are added which would be |
| 1120 | // be quite cheap (cheaper than checking it here), so we can skip this |
| 1121 | // step automatically when appliccable, and encourage people to write in |
| 1122 | // sorted fashion. |
| 1123 | // std::sort is typically already a lot faster on sorted data though. |
| 1124 | auto dict = |
| 1125 | reinterpret_cast<TwoValue *>(flatbuffers::vector_data(stack_) + start); |
| 1126 | std::sort(dict, dict + len, |
| 1127 | [&](const TwoValue &a, const TwoValue &b) -> bool { |
| 1128 | auto as = reinterpret_cast<const char *>( |
| 1129 | flatbuffers::vector_data(buf_) + a.key.u_); |
| 1130 | auto bs = reinterpret_cast<const char *>( |
| 1131 | flatbuffers::vector_data(buf_) + b.key.u_); |
| 1132 | auto comp = strcmp(as, bs); |
| 1133 | // We want to disallow duplicate keys, since this results in a |
| 1134 | // map where values cannot be found. |
| 1135 | // But we can't assert here (since we don't want to fail on |
| 1136 | // random JSON input) or have an error mechanism. |
| 1137 | // Instead, we set has_duplicate_keys_ in the builder to |
| 1138 | // signal this. |
| 1139 | // TODO: Have to check for pointer equality, as some sort |
| 1140 | // implementation apparently call this function with the same |
| 1141 | // element?? Why? |
| 1142 | if (!comp && &a != &b) has_duplicate_keys_ = true; |
| 1143 | return comp < 0; |
| 1144 | }); |
| 1145 | // First create a vector out of all keys. |
| 1146 | // TODO(wvo): if kBuilderFlagShareKeyVectors is true, see if we can share |
| 1147 | // the first vector. |
| 1148 | auto keys = CreateVector(start, len, 2, true, false); |
| 1149 | auto vec = CreateVector(start + 1, len, 2, false, false, &keys); |
| 1150 | // Remove temp elements and return map. |
| 1151 | stack_.resize(start); |
| 1152 | stack_.push_back(vec); |
| 1153 | return static_cast<size_t>(vec.u_); |
| 1154 | } |
| 1155 | |
| 1156 | // Call this after EndMap to see if the map had any duplicate keys. |
no test coverage detected