Home | History | Annotate | Download | only in internal_api 
      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
    218