1 files changed, 290 insertions, 0 deletions
diff --git a/base/containers/id_map.h b/base/containers/id_map.h
new file mode 100644
index 0000000000..4c816da376
--- /dev/null
+++ b/base/containers/id_map.h
@@ -0,0 +1,290 @@
+// Copyright (c) 2011 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 BASE_CONTAINERS_ID_MAP_H_
+#define BASE_CONTAINERS_ID_MAP_H_
+
+#include <stddef.h>
+#include <stdint.h>
+
+#include <memory>
+#include <set>
+#include <type_traits>
+#include <unordered_map>
+#include <utility>
+
+#include "base/containers/flat_set.h"
+#include "base/logging.h"
+#include "base/macros.h"
+#include "base/sequence_checker.h"
+
+namespace base {
+
+// This object maintains a list of IDs that can be quickly converted to
+// pointers to objects. It is implemented as a hash table, optimized for
+// relatively small data sets (in the common case, there will be exactly one
+// item in the list).
+//
+// Items can be inserted into the container with arbitrary ID, but the caller
+// must ensure they are unique. Inserting IDs and relying on automatically
+// generated ones is not allowed because they can collide.
+
+// The map's value type (the V param) can be any dereferenceable type, such as a
+// raw pointer or smart pointer
+template <typename V, typename K = int32_t>
+class IDMap final {
+ public:
+  using KeyType = K;
+
+ private:
+  using T = typename std::remove_reference<decltype(*V())>::type;
+
+  using HashTable = std::unordered_map<KeyType, V>;
+
+ public:
+  IDMap() : iteration_depth_(0), next_id_(1), check_on_null_data_(false) {
+    // A number of consumers of IDMap create it on one thread but always
+    // access it from a different, but consistent, thread (or sequence)
+    // post-construction. The first call to CalledOnValidSequence() will re-bind
+    // it.
+    DETACH_FROM_SEQUENCE(sequence_checker_);
+  }
+
+  ~IDMap() {
+    // Many IDMap's are static, and hence will be destroyed on the main
+    // thread. However, all the accesses may take place on another thread (or
+    // sequence), such as the IO thread. Detaching again to clean this up.
+    DETACH_FROM_SEQUENCE(sequence_checker_);
+  }
+
+  // Sets whether Add and Replace should DCHECK if passed in NULL data.
+  // Default is false.
+  void set_check_on_null_data(bool value) { check_on_null_data_ = value; }
+
+  // Adds a view with an automatically generated unique ID. See AddWithID.
+  KeyType Add(V data) { return AddInternal(std::move(data)); }
+
+  // Adds a new data member with the specified ID. The ID must not be in
+  // the list. The caller either must generate all unique IDs itself and use
+  // this function, or allow this object to generate IDs and call Add. These
+  // two methods may not be mixed, or duplicate IDs may be generated.
+  void AddWithID(V data, KeyType id) { AddWithIDInternal(std::move(data), id); }
+
+  void Remove(KeyType id) {
+    DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
+    typename HashTable::iterator i = data_.find(id);
+    if (i == data_.end() || IsRemoved(id)) {
+      NOTREACHED() << "Attempting to remove an item not in the list";
+      return;
+    }
+
+    if (iteration_depth_ == 0) {
+      data_.erase(i);
+    } else {
+      removed_ids_.insert(id);
+    }
+  }
+
+  // Replaces the value for |id| with |new_data| and returns the existing value.
+  // Should only be called with an already added id.
+  V Replace(KeyType id, V new_data) {
+    DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
+    DCHECK(!check_on_null_data_ || new_data);
+    typename HashTable::iterator i = data_.find(id);
+    DCHECK(i != data_.end());
+    DCHECK(!IsRemoved(id));
+
+    using std::swap;
+    swap(i->second, new_data);
+    return new_data;
+  }
+
+  void Clear() {
+    DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
+    if (iteration_depth_ == 0) {
+      data_.clear();
+    } else {
+      removed_ids_.reserve(data_.size());
+      removed_ids_.insert(KeyIterator(data_.begin()), KeyIterator(data_.end()));
+    }
+  }
+
+  bool IsEmpty() const {
+    DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
+    return size() == 0u;
+  }
+
+  T* Lookup(KeyType id) const {
+    DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
+    typename HashTable::const_iterator i = data_.find(id);
+    if (i == data_.end() || !i->second || IsRemoved(id))
+      return nullptr;
+    return &*i->second;
+  }
+
+  size_t size() const {
+    DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
+    return data_.size() - removed_ids_.size();
+  }
+
+#if defined(UNIT_TEST)
+  int iteration_depth() const {
+    return iteration_depth_;
+  }
+#endif  // defined(UNIT_TEST)
+
+  // It is safe to remove elements from the map during iteration. All iterators
+  // will remain valid.
+  template<class ReturnType>
+  class Iterator {
+   public:
+    Iterator(IDMap<V, K>* map) : map_(map), iter_(map_->data_.begin()) {
+      Init();
+    }
+
+    Iterator(const Iterator& iter)
+        : map_(iter.map_),
+          iter_(iter.iter_) {
+      Init();
+    }
+
+    const Iterator& operator=(const Iterator& iter) {
+      map_ = iter.map;
+      iter_ = iter.iter;
+      Init();
+      return *this;
+    }
+
+    ~Iterator() {
+      DCHECK_CALLED_ON_VALID_SEQUENCE(map_->sequence_checker_);
+
+      // We're going to decrement iteration depth. Make sure it's greater than
+      // zero so that it doesn't become negative.
+      DCHECK_LT(0, map_->iteration_depth_);
+
+      if (--map_->iteration_depth_ == 0)
+        map_->Compact();
+    }
+
+    bool IsAtEnd() const {
+      DCHECK_CALLED_ON_VALID_SEQUENCE(map_->sequence_checker_);
+      return iter_ == map_->data_.end();
+    }
+
+    KeyType GetCurrentKey() const {
+      DCHECK_CALLED_ON_VALID_SEQUENCE(map_->sequence_checker_);
+      return iter_->first;
+    }
+
+    ReturnType* GetCurrentValue() const {
+      DCHECK_CALLED_ON_VALID_SEQUENCE(map_->sequence_checker_);
+      if (!iter_->second || map_->IsRemoved(iter_->first))
+        return nullptr;
+      return &*iter_->second;
+    }
+
+    void Advance() {
+      DCHECK_CALLED_ON_VALID_SEQUENCE(map_->sequence_checker_);
+      ++iter_;
+      SkipRemovedEntries();
+    }
+
+   private:
+    void Init() {
+      DCHECK_CALLED_ON_VALID_SEQUENCE(map_->sequence_checker_);
+      ++map_->iteration_depth_;
+      SkipRemovedEntries();
+    }
+
+    void SkipRemovedEntries() {
+      while (iter_ != map_->data_.end() && map_->IsRemoved(iter_->first))
+        ++iter_;
+    }
+
+    IDMap<V, K>* map_;
+    typename HashTable::const_iterator iter_;
+  };
+
+  typedef Iterator<T> iterator;
+  typedef Iterator<const T> const_iterator;
+
+ private:
+  // Transforms a map iterator to an iterator on the keys of the map.
+  // Used by Clear() to populate |removed_ids_| in bulk.
+  struct KeyIterator : std::iterator<std::forward_iterator_tag, KeyType> {
+    using inner_iterator = typename HashTable::iterator;
+    inner_iterator iter_;
+
+    KeyIterator(inner_iterator iter) : iter_(iter) {}
+    KeyType operator*() const { return iter_->first; }
+    KeyIterator& operator++() {
+      ++iter_;
+      return *this;
+    }
+    KeyIterator operator++(int) { return KeyIterator(iter_++); }
+    bool operator==(const KeyIterator& other) const {
+      return iter_ == other.iter_;
+    }
+    bool operator!=(const KeyIterator& other) const {
+      return iter_ != other.iter_;
+    }
+  };
+
+  KeyType AddInternal(V data) {
+    DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
+    DCHECK(!check_on_null_data_ || data);
+    KeyType this_id = next_id_;
+    DCHECK(data_.find(this_id) == data_.end()) << "Inserting duplicate item";
+    data_[this_id] = std::move(data);
+    next_id_++;
+    return this_id;
+  }
+
+  void AddWithIDInternal(V data, KeyType id) {
+    DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
+    DCHECK(!check_on_null_data_ || data);
+    if (IsRemoved(id)) {
+      removed_ids_.erase(id);
+    } else {
+      DCHECK(data_.find(id) == data_.end()) << "Inserting duplicate item";
+    }
+    data_[id] = std::move(data);
+  }
+
+  bool IsRemoved(KeyType key) const {
+    return removed_ids_.find(key) != removed_ids_.end();
+  }
+
+  void Compact() {
+    DCHECK_EQ(0, iteration_depth_);
+    for (const auto& i : removed_ids_)
+      data_.erase(i);
+    removed_ids_.clear();
+  }
+
+  // Keep track of how many iterators are currently iterating on us to safely
+  // handle removing items during iteration.
+  int iteration_depth_;
+
+  // Keep set of IDs that should be removed after the outermost iteration has
+  // finished. This way we manage to not invalidate the iterator when an element
+  // is removed.
+  base::flat_set<KeyType> removed_ids_;
+
+  // The next ID that we will return from Add()
+  KeyType next_id_;
+
+  HashTable data_;
+
+  // See description above setter.
+  bool check_on_null_data_;
+
+  SEQUENCE_CHECKER(sequence_checker_);
+
+  DISALLOW_COPY_AND_ASSIGN(IDMap);
+};
+
+}  // namespace base
+
+#endif  // BASE_CONTAINERS_ID_MAP_H_