Use upstream libaddressinput in Chrome.

third_party/libaddressinput/chromium/trie.h

-// Copyright (C) 2014 Google Inc.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
+// 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.
 
-#ifndef I18N_ADDRESSINPUT_UTIL_TRIE_H_
-#define I18N_ADDRESSINPUT_UTIL_TRIE_H_
+#ifndef THIRD_PARTY_LIBADDRESSINPUT_CHROMIUM_TRIE_H_
+#define THIRD_PARTY_LIBADDRESSINPUT_CHROMIUM_TRIE_H_
 
-#include <libaddressinput/util/basictypes.h>
-
-#include <list>
 #include <map>
 #include <set>
 #include <string>
 
-namespace i18n {
-namespace addressinput {
+#include "base/basictypes.h"
+
+namespace autofill {
 
 // A prefix search tree. Can return all objects whose keys start with a prefix
 // string.
 //
 // Maps keys to multiple objects. This property is useful when mapping region
 // names to region objects. For example, there's a "St. Petersburg" in Florida,
 // and there's a "St. Petersburg" in Russia. A lookup for "St. Petersburg" key
 // should return two distinct objects.
 template <typename T>
 class Trie {
  public:
   Trie();
-
   ~Trie();
 
+  // Returns true if no data was added in AddDataForKey().
+  bool empty() const { return data_list_.empty() && sub_nodes_.empty(); }
+
   // Adds a mapping from |key| to |data_item|. Can be called with the same |key|
-  // multiple times.
-  void AddDataForKey(const std::string& key, const T& data_item);
+  // multiple times. Does not take ownership of |key|, which should not be NULL.
+  void AddDataForKey(const uint8_t* key, int32_t key_size, const T& data_item);
 
   // Adds all objects whose keys start with |key_prefix| to the |results|
-  // parameter. The |results| parameter should not be NULL.
-  void FindDataForKeyPrefix(const std::string& key_prefix,
+  // parameter. Does not take ownership of |key_prefix|, which should not be
+  // NULL. The |results| parameter should not be NULL.
+  void FindDataForKeyPrefix(const uint8_t* key_prefix,
+                            int32_t key_prefix_size,
                             std::set<T>* results) const;
 
  private:
   // All objects for this node in the trie. This field is a collection to enable
   // mapping the same key to multiple objects.
-  std::list<T> data_list_;
+  std::set<T> data_list_;
 
   // Trie sub nodes. The root trie stores the objects for the empty string key.
   // The children of the root trie store the objects for the one-letter keys.
   // The grand-children of the root trie store the objects for the two-letter
   // keys, and so on.
-  std::map<char, Trie<T>*> sub_nodes_;
+  std::map<uint8_t, Trie<T>*> sub_nodes_;
 
   DISALLOW_COPY_AND_ASSIGN(Trie);
 };
 
-}  // namespace addressinput
-}  // namespace i18n
+}  // namespace autofill
 
-#endif  // I18N_ADDRESSINPUT_UTIL_TRIE_H_
+#endif  // THIRD_PARTY_LIBADDRESSINPUT_CHROMIUM_TRIE_H_