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