Use upstream libaddressinput in Chrome.

third_party/libaddressinput/chromium/trie.cc

+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "third_party/libaddressinput/chromium/trie.h"
+
+#include <cstddef>
+#include <map>
+#include <queue>
+#include <set>
+#include <string>
+#include <utility>
+
+#include "base/logging.h"
+#include "base/stl_util.h"
+
+// Separating template definitions and declarations requires defining all
+// possible template parameters to avoid linking errors.
+namespace i18n {
+namespace addressinput {
+class RegionData;
+}
+}
+
+namespace autofill {
+
+template <typename T>
+Trie<T>::Trie() {
+}
+
+template <typename T>
+Trie<T>::~Trie() {
+  STLDeleteValues(&sub_nodes_);
+}
+
+template <typename T>
+void Trie<T>::AddDataForKey(const uint8_t* key,
+                            int32_t key_size,
+                            const T& data_item) {
+  Trie<T>* current_node = this;
+  for (int32_t i = 0; i < key_size; ++i) {
+    typename std::map<uint8_t, Trie<T>*>::const_iterator sub_node_it =
+        current_node->sub_nodes_.find(key[i]);
+    if (sub_node_it == current_node->sub_nodes_.end()) {
+      sub_node_it =
+          current_node->sub_nodes_.insert(std::make_pair(key[i], new Trie<T>))
+              .first;
+    }
+    current_node = sub_node_it->second;
+    DCHECK(current_node);
+  }
+  current_node->data_list_.insert(data_item);
+}
+
+template <typename T>
+void Trie<T>::FindDataForKeyPrefix(const uint8_t* key_prefix,
+                                   int32_t key_prefix_size,
+                                   std::set<T>* results) const {
+  DCHECK(results);
+
+  // Find the sub-trie for the key prefix.
+  const Trie<T>* current_node = this;
+  for (int32_t i = 0; i < key_prefix_size; ++i) {
+    typename std::map<uint8_t, Trie<T>*>::const_iterator sub_node_it =
+        current_node->sub_nodes_.find(key_prefix[i]);
+    if (sub_node_it == current_node->sub_nodes_.end())
+      return;
+
+    current_node = sub_node_it->second;
+    DCHECK(current_node);
+  }
+
+  // Collect data from all sub-tries.
+  std::queue<const Trie<T>*> node_queue;
+  node_queue.push(current_node);
+  while (!node_queue.empty()) {
+    const Trie<T>* queue_front = node_queue.front();
+    node_queue.pop();
+
+    results->insert(queue_front->data_list_.begin(),
+                    queue_front->data_list_.end());
+
+    for (typename std::map<uint8_t, Trie<T>*>::const_iterator sub_node_it =
+             queue_front->sub_nodes_.begin();
+         sub_node_it != queue_front->sub_nodes_.end();
+         ++sub_node_it) {
+      node_queue.push(sub_node_it->second);
+    }
+  }
+}
+
+template class Trie<const ::i18n::addressinput::RegionData*>;
+template class Trie<std::string>;
+
+}  // namespace autofill