sync/internal_api/change_reorder_buffer.cc

   1 // Copyright 2012 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 #include "sync/internal_api/change_reorder_buffer.h"
   6
   7 #include <limits>
   8 #include <queue>
   9 #include <set>
  10 #include <utility>  // for pair<>
  11
  12 #include "sync/internal_api/public/base_node.h"
  13 #include "sync/internal_api/public/base_transaction.h"
  14 #include "sync/syncable/entry.h"
  15 #include "sync/syncable/syncable_base_transaction.h"
  16
  17 using std::numeric_limits;
  18 using std::pair;
  19 using std::queue;
  20 using std::set;
  21
  22 namespace syncer {
  23
  24 // Traversal provides a way to collect a set of nodes from the syncable
  25 // directory structure and then traverse them, along with any intermediate
  26 // nodes, in a top-down fashion, starting from a single common ancestor.  A
  27 // Traversal starts out empty and is grown by means of the ExpandToInclude
  28 // method.  Once constructed, the top(), begin_children(), and end_children()
  29 // methods can be used to explore the nodes in root-to-leaf order.
  30 class ChangeReorderBuffer::Traversal {
  31  public:
  32   typedef pair<int64, int64> ParentChildLink;
  33   typedef set<ParentChildLink> LinkSet;
  34
  35   Traversal() : top_(kInvalidId) { }
  36
  37   // Expand the traversal so that it includes the node indicated by
  38   // |child_handle|.
  39   void ExpandToInclude(syncable::BaseTransaction* trans,
  40                        int64 child_handle) {
  41     // If |top_| is invalid, this is the first insertion -- easy.
  42     if (top_ == kInvalidId) {
  43       top_ = child_handle;
  44       return;
  45     }
  46
  47     int64 node_to_include = child_handle;
  48     while (node_to_include != kInvalidId && node_to_include != top_) {
  49       int64 node_parent = 0;
  50
  51       syncable::Entry node(trans, syncable::GET_BY_HANDLE, node_to_include);
  52       CHECK(node.good());
  53       if (node.GetId().IsRoot()) {
  54         // If we've hit the root, and the root isn't already in the tree
  55         // (it would have to be |top_| if it were), start a new expansion
  56         // upwards from |top_| to unite the original traversal with the
  57         // path we just added that goes from |child_handle| to the root.
  58         node_to_include = top_;
  59         top_ = node.GetMetahandle();
  60       } else {
  61         // Otherwise, get the parent ID so that we can add a ParentChildLink.
  62
  63         // Treat nodes with unset parent ID as if they were linked to the root.
  64         // That is a valid way to traverse the tree because all hierarchical
  65         // datatypes must have a valid parent ID and the ones with unset parent
  66         // ID have flat hierarchy where the order doesn't matter.
  67         const syncable::Id& parent_id = !node.GetParentId().IsNull()
  68                                             ? node.GetParentId()
  69                                             : syncable::Id::GetRoot();
  70         syncable::Entry parent(trans, syncable::GET_BY_ID, parent_id);
  71         CHECK(parent.good());
  72         node_parent = parent.GetMetahandle();
  73
  74         ParentChildLink link(node_parent, node_to_include);
  75
  76         // If the link exists in the LinkSet |links_|, we don't need to search
  77         // any higher; we are done.
  78         if (links_.find(link) != links_.end())
  79           return;
  80
  81         // Otherwise, extend |links_|, and repeat on the parent.
  82         links_.insert(link);
  83         node_to_include = node_parent;
  84       }
  85     }
  86   }
  87
  88   // Return the top node of the traversal.  Use this as a starting point
  89   // for walking the tree.
  90   int64 top() const { return top_; }
  91
  92   // Return an iterator corresponding to the first child (in the traversal)
  93   // of the node specified by |parent_id|.  Iterate this return value until
  94   // it is equal to the value returned by end_children(parent_id).  The
  95   // enumeration thus provided is unordered.
  96   LinkSet::const_iterator begin_children(int64 parent_id) const {
  97     return links_.upper_bound(
  98         ParentChildLink(parent_id, numeric_limits<int64>::min()));
  99   }
 100
 101   // Return an iterator corresponding to the last child in the traversal
 102   // of the node specified by |parent_id|.
 103   LinkSet::const_iterator end_children(int64 parent_id) const {
 104     return begin_children(parent_id + 1);
 105   }
 106
 107  private:
 108   // The topmost point in the directory hierarchy that is in the traversal,
 109   // and thus the first node to be traversed.  If the traversal is empty,
 110   // this is kInvalidId.  If the traversal contains exactly one member, |top_|
 111   // will be the solitary member, and |links_| will be empty.
 112   int64 top_;
 113   // A set of single-level links that compose the traversal below |top_|.  The
 114   // (parent, child) ordering of values enables efficient lookup of children
 115   // given the parent handle, which is used for top-down traversal.  |links_|
 116   // is expected to be connected -- every node that appears as a parent in a
 117   // link must either appear as a child of another link, or else be the
 118   // topmost node, |top_|.
 119   LinkSet links_;
 120
 121   DISALLOW_COPY_AND_ASSIGN(Traversal);
 122 };
 123
 124 ChangeReorderBuffer::ChangeReorderBuffer() {
 125 }
 126
 127 ChangeReorderBuffer::~ChangeReorderBuffer() {
 128 }
 129
 130 void ChangeReorderBuffer::PushAddedItem(int64 id) {
 131   operations_[id] = ChangeRecord::ACTION_ADD;
 132 }
 133
 134 void ChangeReorderBuffer::PushDeletedItem(int64 id) {
 135   operations_[id] = ChangeRecord::ACTION_DELETE;
 136 }
 137
 138 void ChangeReorderBuffer::PushUpdatedItem(int64 id) {
 139   operations_[id] = ChangeRecord::ACTION_UPDATE;
 140 }
 141
 142 void ChangeReorderBuffer::SetExtraDataForId(
 143     int64 id,
 144     ExtraPasswordChangeRecordData* extra) {
 145   extra_data_[id] = make_linked_ptr<ExtraPasswordChangeRecordData>(extra);
 146 }
 147
 148 void ChangeReorderBuffer::SetSpecificsForId(
 149     int64 id,
 150     const sync_pb::EntitySpecifics& specifics) {
 151   specifics_[id] = specifics;
 152 }
 153
 154 void ChangeReorderBuffer::Clear() {
 155   operations_.clear();
 156 }
 157
 158 bool ChangeReorderBuffer::IsEmpty() const {
 159   return operations_.empty();
 160 }
 161
 162 bool ChangeReorderBuffer::GetAllChangesInTreeOrder(
 163     const BaseTransaction* sync_trans,
 164     ImmutableChangeRecordList* changes) {
 165   syncable::BaseTransaction* trans = sync_trans->GetWrappedTrans();
 166
 167   // Step 1: Iterate through the operations, doing three things:
 168   // (a) Push deleted items straight into the |changelist|.
 169   // (b) Construct a traversal spanning all non-deleted items.
 170   // (c) Construct a set of all parent nodes of any position changes.
 171   Traversal traversal;
 172
 173   ChangeRecordList changelist;
 174
 175   OperationMap::const_iterator i;
 176   for (i = operations_.begin(); i != operations_.end(); ++i) {
 177     if (i->second == ChangeRecord::ACTION_DELETE) {
 178       ChangeRecord record;
 179       record.id = i->first;
 180       record.action = i->second;
 181       if (specifics_.find(record.id) != specifics_.end())
 182         record.specifics = specifics_[record.id];
 183       if (extra_data_.find(record.id) != extra_data_.end())
 184         record.extra = extra_data_[record.id];
 185       changelist.push_back(record);
 186     } else {
 187       traversal.ExpandToInclude(trans, i->first);
 188     }
 189   }
 190
 191   // Step 2: Breadth-first expansion of the traversal.
 192   queue<int64> to_visit;
 193   to_visit.push(traversal.top());
 194   while (!to_visit.empty()) {
 195     int64 next = to_visit.front();
 196     to_visit.pop();
 197
 198     // If the node has an associated action, output a change record.
 199     i = operations_.find(next);
 200     if (i != operations_.end()) {
 201       ChangeRecord record;
 202       record.id = next;
 203       record.action = i->second;
 204       if (specifics_.find(record.id) != specifics_.end())
 205         record.specifics = specifics_[record.id];
 206       if (extra_data_.find(record.id) != extra_data_.end())
 207         record.extra = extra_data_[record.id];
 208       changelist.push_back(record);
 209     }
 210
 211     // Now add the children of |next| to |to_visit|.
 212     Traversal::LinkSet::const_iterator j = traversal.begin_children(next);
 213     Traversal::LinkSet::const_iterator end = traversal.end_children(next);
 214     for (; j != end; ++j) {
 215       CHECK(j->first == next);
 216       to_visit.push(j->second);
 217     }
 218   }
 219
 220   *changes = ImmutableChangeRecordList(&changelist);
 221   return true;
 222 }
 223
 224 }  // namespace syncer