src/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         syncable::Entry parent(trans, syncable::GET_BY_ID,
  63                                node.GetParentId());
  64         CHECK(parent.good());
  65         node_parent = parent.GetMetahandle();
  66
  67         ParentChildLink link(node_parent, node_to_include);
  68
  69         // If the link exists in the LinkSet |links_|, we don't need to search
  70         // any higher; we are done.
  71         if (links_.find(link) != links_.end())
  72           return;
  73
  74         // Otherwise, extend |links_|, and repeat on the parent.
  75         links_.insert(link);
  76         node_to_include = node_parent;
  77       }
  78     }
  79   }
  80
  81   // Return the top node of the traversal.  Use this as a starting point
  82   // for walking the tree.
  83   int64 top() const { return top_; }
  84
  85   // Return an iterator corresponding to the first child (in the traversal)
  86   // of the node specified by |parent_id|.  Iterate this return value until
  87   // it is equal to the value returned by end_children(parent_id).  The
  88   // enumeration thus provided is unordered.
  89   LinkSet::const_iterator begin_children(int64 parent_id) const {
  90     return links_.upper_bound(
  91         ParentChildLink(parent_id, numeric_limits<int64>::min()));
  92   }
  93
  94   // Return an iterator corresponding to the last child in the traversal
  95   // of the node specified by |parent_id|.
  96   LinkSet::const_iterator end_children(int64 parent_id) const {
  97     return begin_children(parent_id + 1);
  98   }
  99
 100  private:
 101   // The topmost point in the directory hierarchy that is in the traversal,
 102   // and thus the first node to be traversed.  If the traversal is empty,
 103   // this is kInvalidId.  If the traversal contains exactly one member, |top_|
 104   // will be the solitary member, and |links_| will be empty.
 105   int64 top_;
 106   // A set of single-level links that compose the traversal below |top_|.  The
 107   // (parent, child) ordering of values enables efficient lookup of children
 108   // given the parent handle, which is used for top-down traversal.  |links_|
 109   // is expected to be connected -- every node that appears as a parent in a
 110   // link must either appear as a child of another link, or else be the
 111   // topmost node, |top_|.
 112   LinkSet links_;
 113
 114   DISALLOW_COPY_AND_ASSIGN(Traversal);
 115 };
 116
 117 ChangeReorderBuffer::ChangeReorderBuffer() {
 118 }
 119
 120 ChangeReorderBuffer::~ChangeReorderBuffer() {
 121 }
 122
 123 void ChangeReorderBuffer::PushAddedItem(int64 id) {
 124   operations_[id] = ChangeRecord::ACTION_ADD;
 125 }
 126
 127 void ChangeReorderBuffer::PushDeletedItem(int64 id) {
 128   operations_[id] = ChangeRecord::ACTION_DELETE;
 129 }
 130
 131 void ChangeReorderBuffer::PushUpdatedItem(int64 id) {
 132   operations_[id] = ChangeRecord::ACTION_UPDATE;
 133 }
 134
 135 void ChangeReorderBuffer::SetExtraDataForId(
 136     int64 id,
 137     ExtraPasswordChangeRecordData* extra) {
 138   extra_data_[id] = make_linked_ptr<ExtraPasswordChangeRecordData>(extra);
 139 }
 140
 141 void ChangeReorderBuffer::SetSpecificsForId(
 142     int64 id,
 143     const sync_pb::EntitySpecifics& specifics) {
 144   specifics_[id] = specifics;
 145 }
 146
 147 void ChangeReorderBuffer::Clear() {
 148   operations_.clear();
 149 }
 150
 151 bool ChangeReorderBuffer::IsEmpty() const {
 152   return operations_.empty();
 153 }
 154
 155 bool ChangeReorderBuffer::GetAllChangesInTreeOrder(
 156     const BaseTransaction* sync_trans,
 157     ImmutableChangeRecordList* changes) {
 158   syncable::BaseTransaction* trans = sync_trans->GetWrappedTrans();
 159
 160   // Step 1: Iterate through the operations, doing three things:
 161   // (a) Push deleted items straight into the |changelist|.
 162   // (b) Construct a traversal spanning all non-deleted items.
 163   // (c) Construct a set of all parent nodes of any position changes.
 164   Traversal traversal;
 165
 166   ChangeRecordList changelist;
 167
 168   OperationMap::const_iterator i;
 169   for (i = operations_.begin(); i != operations_.end(); ++i) {
 170     if (i->second == ChangeRecord::ACTION_DELETE) {
 171       ChangeRecord record;
 172       record.id = i->first;
 173       record.action = i->second;
 174       if (specifics_.find(record.id) != specifics_.end())
 175         record.specifics = specifics_[record.id];
 176       if (extra_data_.find(record.id) != extra_data_.end())
 177         record.extra = extra_data_[record.id];
 178       changelist.push_back(record);
 179     } else {
 180       traversal.ExpandToInclude(trans, i->first);
 181     }
 182   }
 183
 184   // Step 2: Breadth-first expansion of the traversal.
 185   queue<int64> to_visit;
 186   to_visit.push(traversal.top());
 187   while (!to_visit.empty()) {
 188     int64 next = to_visit.front();
 189     to_visit.pop();
 190
 191     // If the node has an associated action, output a change record.
 192     i = operations_.find(next);
 193     if (i != operations_.end()) {
 194       ChangeRecord record;
 195       record.id = next;
 196       record.action = i->second;
 197       if (specifics_.find(record.id) != specifics_.end())
 198         record.specifics = specifics_[record.id];
 199       if (extra_data_.find(record.id) != extra_data_.end())
 200         record.extra = extra_data_[record.id];
 201       changelist.push_back(record);
 202     }
 203
 204     // Now add the children of |next| to |to_visit|.
 205     Traversal::LinkSet::const_iterator j = traversal.begin_children(next);
 206     Traversal::LinkSet::const_iterator end = traversal.end_children(next);
 207     for (; j != end; ++j) {
 208       CHECK(j->first == next);
 209       to_visit.push(j->second);
 210     }
 211   }
 212
 213   *changes = ImmutableChangeRecordList(&changelist);
 214   return true;
 215 }
 216
 217 }  // namespace syncer