diff options
Diffstat (limited to 'base/values.cc')
| -rw-r--r-- | base/values.cc | 108 |
1 files changed, 108 insertions, 0 deletions
diff --git a/base/values.cc b/base/values.cc index 031e1ca..8fdd4ea 100644 --- a/base/values.cc +++ b/base/values.cc @@ -874,6 +874,114 @@ void DictionaryValue::MergeDictionary(const DictionaryValue* dictionary) { } } +bool DictionaryValue::GetDifferingPathsHelper( + const std::string& path_prefix, + const DictionaryValue* other, + std::vector<std::string>* different_paths) const { + bool added_path = false; + std::map<std::string, Value*>::const_iterator current_this; + std::map<std::string, Value*>::const_iterator end_this; + current_this = dictionary_.begin(); + end_this = dictionary_.end(); + if (!other) { + // Recursively add all paths from the |this| dictionary, since they are + // not in |other|. + for (; current_this != end_this; ++current_this) { + std::string full_path_for_key(path_prefix.empty() ? current_this->first : + path_prefix + "." + current_this->first); + different_paths->push_back(full_path_for_key); + added_path = true; + if (current_this->second->IsType(Value::TYPE_DICTIONARY)) { + const DictionaryValue* dictionary_this = + static_cast<const DictionaryValue*>(current_this->second); + dictionary_this->GetDifferingPathsHelper(full_path_for_key, + NULL, + different_paths); + } + } + } else { + // Both the |this| and |other| dictionaries have entries. Iterate over + // both simultaneously. Paths that are in one but not the other are + // added to |different_paths| and DictionaryValues are processed + // recursively. + std::map<std::string, Value*>::const_iterator current_other = + other->dictionary_.begin(); + std::map<std::string, Value*>::const_iterator end_other = + other->dictionary_.end(); + while (current_this != end_this || current_other != end_other) { + const Value* recursion_this = NULL; + const Value* recursion_other = NULL; + const std::string* key_name = NULL; + bool current_value_known_equal = false; + if (current_this == end_this || + (current_other != end_other && + (current_other->first < current_this->first))) { + key_name = ¤t_other->first; + if (current_other->second->IsType(Value::TYPE_DICTIONARY)) + recursion_this = current_other->second; + ++current_other; + } else { + key_name = ¤t_this->first; + if (current_other == end_other || + current_this->first < current_other->first) { + if (current_this->second->IsType(Value::TYPE_DICTIONARY)) + recursion_this = current_this->second; + ++current_this; + } else { + DCHECK(current_this->first == current_other->first); + if (current_this->second->IsType(Value::TYPE_DICTIONARY)) { + recursion_this = current_this->second; + if (current_other->second->IsType(Value::TYPE_DICTIONARY)) { + recursion_other = current_other->second; + } + } else { + if (current_other->second->IsType(Value::TYPE_DICTIONARY)) { + recursion_this = current_other->second; + } else { + current_value_known_equal = + current_this->second->Equals(current_other->second); + } + } + ++current_this; + ++current_other; + } + } + const std::string& full_path_for_key(path_prefix.empty() ? + *key_name : path_prefix + "." + *key_name); + if (!current_value_known_equal) + different_paths->push_back(full_path_for_key); + if (recursion_this) { + const DictionaryValue* dictionary_this = + static_cast<const DictionaryValue*>(recursion_this); + bool subtree_changed = dictionary_this->GetDifferingPathsHelper( + full_path_for_key, + static_cast<const DictionaryValue*>(recursion_other), + different_paths); + if (subtree_changed) { + added_path = true; + } else { + // In order to maintain lexicographical sorting order, directory + // paths are pushed "optimistically" assuming that their subtree will + // contain differences. If in retrospect there were no differences + // in the subtree, the assumption was false and the dictionary path + // must be removed. + different_paths->pop_back(); + } + } else { + added_path |= !current_value_known_equal; + } + } + } + return added_path; +} + +void DictionaryValue::GetDifferingPaths( + const DictionaryValue* other, + std::vector<std::string>* different_paths) const { + different_paths->clear(); + GetDifferingPathsHelper("", other, different_paths); +} + ///////////////////// ListValue //////////////////// ListValue::ListValue() : Value(TYPE_LIST) { |