ios/web/net/request_tracker_data_memoizing_store.h

   1 // Copyright 2015 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #ifndef IOS_WEB_NET_REQUEST_TRACKER_DATA_MEMOIZING_STORE_H_
   6 #define IOS_WEB_NET_REQUEST_TRACKER_DATA_MEMOIZING_STORE_H_
   7
   8 #include <map>
   9
  10 #include "base/bind.h"
  11 #include "base/synchronization/lock.h"
  12 #include "ios/web/public/web_thread.h"
  13
  14 namespace web {
  15
  16 // RequestTrackerDataMemoizingStore is a thread-safe container that retains
  17 // reference counted objects that are associated with one or more request
  18 // trackers. Objects are identified by an int and only a single reference to a
  19 // given object is retained.
  20 template <typename T>
  21 class RequestTrackerDataMemoizingStore {
  22  public:
  23   RequestTrackerDataMemoizingStore() : next_item_id_(1) {}
  24
  25   ~RequestTrackerDataMemoizingStore() {
  26     DCHECK_EQ(0U, id_to_item_.size()) << "Failed to outlive request tracker";
  27   }
  28
  29   // Store adds |item| to this collection, associates it with the given request
  30   // tracker id and returns an opaque identifier for it. If |item| is already
  31   // known, the same identifier will be returned.
  32   int Store(T* item, int request_tracker_id) {
  33     DCHECK(item);
  34     base::AutoLock auto_lock(lock_);
  35
  36     int item_id = 0;
  37
  38     // Is this item alread known?
  39     typename ReverseItemMap::iterator item_iter = item_to_id_.find(item);
  40     if (item_iter == item_to_id_.end()) {
  41       item_id = next_item_id_++;
  42       // Use 0 as an invalid item_id value.  In the unlikely event that
  43       // next_item_id_ wraps around, reset it to 1.
  44       if (next_item_id_ == 0)
  45         next_item_id_ = 1;
  46       id_to_item_[item_id] = item;
  47       item_to_id_[item] = item_id;
  48     } else {
  49       item_id = item_iter->second;
  50     }
  51
  52     // Update the bidirection request_tracker_id and item_id mappings.
  53     UpdateMap(&request_tracker_id_to_item_id_, request_tracker_id, item_id);
  54     UpdateMap(&item_id_to_request_tracker_id_, item_id, request_tracker_id);
  55
  56     DCHECK(item_id);
  57     return item_id;
  58   }
  59
  60   // Retrieves a previously Stored() item, identified by |item_id|.
  61   // If |item_id| is recognized, |item| will be updated and Retrieve() will
  62   // return true.
  63   bool Retrieve(int item_id, scoped_refptr<T>* item) {
  64     base::AutoLock auto_lock(lock_);
  65
  66     typename ItemMap::iterator iter = id_to_item_.find(item_id);
  67     if (iter == id_to_item_.end())
  68       return false;
  69     if (item)
  70       *item = iter->second;
  71     return true;
  72   }
  73
  74   // Removes any items associtated only with |request_tracker_id|.
  75   void RemoveForRequestTracker(int request_tracker_id) {
  76     RemoveRequestTrackerItems(request_tracker_id);
  77   }
  78
  79  private:
  80   typedef std::multimap<int, int> IDMap;
  81   typedef std::map<int, scoped_refptr<T>> ItemMap;
  82   typedef std::map<T*, int, typename T::LessThan> ReverseItemMap;
  83
  84   template <typename M>
  85   struct MatchSecond {
  86     explicit MatchSecond(const M& t) : value(t) {}
  87
  88     template <typename Pair>
  89     bool operator()(const Pair& p) const {
  90       return (value == p.second);
  91     }
  92
  93     M value;
  94   };
  95
  96   // Updates |map| to contain a key_id->value_id pair, ensuring that a duplicate
  97   // pair is not added if it was already present.
  98   static void UpdateMap(IDMap* map, int key_id, int value_id) {
  99     auto matching_key_range = map->equal_range(key_id);
 100     if (std::find_if(matching_key_range.first, matching_key_range.second,
 101                      MatchSecond<int>(value_id)) == matching_key_range.second) {
 102       map->insert(std::make_pair(key_id, value_id));
 103     }
 104   }
 105
 106   // Remove the item specified by |item_id| from id_to_item_ and item_to_id_.
 107   // NOTE: the caller (RemoveRequestTrackerItems) must hold lock_.
 108   void RemoveInternal(int item_id) {
 109     typename ItemMap::iterator item_iter = id_to_item_.find(item_id);
 110     DCHECK(item_iter != id_to_item_.end());
 111
 112     typename ReverseItemMap::iterator id_iter =
 113         item_to_id_.find(item_iter->second.get());
 114     DCHECK(id_iter != item_to_id_.end());
 115     item_to_id_.erase(id_iter);
 116
 117     id_to_item_.erase(item_iter);
 118   }
 119
 120   // Removes all the items associated with the specified request tracker from
 121   // the store.
 122   void RemoveRequestTrackerItems(int request_tracker_id) {
 123     base::AutoLock auto_lock(lock_);
 124
 125     // Iterate through all the item ids for that request tracker.
 126     auto request_tracker_ids =
 127         request_tracker_id_to_item_id_.equal_range(request_tracker_id);
 128     for (IDMap::iterator ids_iter = request_tracker_ids.first;
 129          ids_iter != request_tracker_ids.second; ++ids_iter) {
 130       int item_id = ids_iter->second;
 131       // Find all the request trackers referring to this item id in
 132       // item_id_to_request_tracker_id_, then locate the request tracker being
 133       // removed within that range.
 134       auto item_ids = item_id_to_request_tracker_id_.equal_range(item_id);
 135       IDMap::iterator proc_iter =
 136           std::find_if(item_ids.first, item_ids.second,
 137                        MatchSecond<int>(request_tracker_id));
 138       DCHECK(proc_iter != item_ids.second);
 139
 140       // Before removing, determine if no other request trackers refer to the
 141       // current item id. If |proc_iter| (the current request tracker) is the
 142       // lower bound of request trackers containing the current item id and if
 143       // |next_proc_iter| is the upper bound (the first request tracker that
 144       // does not), then only one request tracker, the one being removed, refers
 145       // to the item id.
 146       IDMap::iterator next_proc_iter = proc_iter;
 147       ++next_proc_iter;
 148       bool last_request_tracker_for_item_id =
 149           (proc_iter == item_ids.first && next_proc_iter == item_ids.second);
 150       item_id_to_request_tracker_id_.erase(proc_iter);
 151
 152       if (last_request_tracker_for_item_id) {
 153         // The current item id is not referenced by any other request trackers,
 154         // so remove it from id_to_item_ and item_to_id_.
 155         RemoveInternal(item_id);
 156       }
 157     }
 158     if (request_tracker_ids.first != request_tracker_ids.second)
 159       request_tracker_id_to_item_id_.erase(request_tracker_ids.first,
 160                                            request_tracker_ids.second);
 161   }
 162
 163   // Bidirectional mapping between items and the request trackers they are
 164   // associated with.
 165   IDMap request_tracker_id_to_item_id_;
 166   IDMap item_id_to_request_tracker_id_;
 167   // Bidirectional mappings between items and the item-level identifiers that
 168   // have been assigned to them.
 169   ItemMap id_to_item_;
 170   ReverseItemMap item_to_id_;
 171
 172   // The ID to assign to the next item stored.
 173   int next_item_id_;
 174
 175   // This lock protects: request_tracker_id_to_item_id_,
 176   // item_id_to_request_tracker_id_, id_to_item_, and item_to_id_.
 177   base::Lock lock_;
 178 };
 179
 180 }  // namespace web
 181
 182 #endif  // IOS_WEB_NET_REQUEST_TRACKER_DATA_MEMOIZING_STORE_H_