1// Copyright (c) 2011 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// Defines ChangeReorderBuffer, which can be used to sort a list of item
6// actions to achieve the ordering constraint required by the SyncObserver
7// interface of the SyncAPI.
8
9#ifndef CHROME_BROWSER_SYNC_ENGINE_CHANGE_REORDER_BUFFER_H_
10#define CHROME_BROWSER_SYNC_ENGINE_CHANGE_REORDER_BUFFER_H_
11#pragma once
12
13#include <map>
14#include <vector>
15
16#include "base/memory/linked_ptr.h"
17#include "chrome/browser/sync/engine/syncapi.h"
18#include "chrome/browser/sync/protocol/sync.pb.h"
19
20namespace sync_api {
21
22// ChangeReorderBuffer is a utility type which accepts an unordered set
23// of changes (via its Push methods), and yields a vector of ChangeRecords
24// (via the GetAllChangesInTreeOrder method) that are in the order that
25// the SyncObserver expects them to be. A buffer is initially empty.
26//
27// The ordering produced by ChangeReorderBuffer is as follows:
28//  (a) All Deleted items appear first.
29//  (b) For Updated and/or Added items, parents appear before their children.
30//  (c) When there are changes to the sibling order (this means Added items,
31//      or Updated items with the |position_changed| parameter set to true),
32//      all siblings under a parent will appear in the output, even if they
33//      are not explicitly pushed.  The sibling order will be preserved in
34//      the output list -- items will appear before their sibling-order
35//      successors.
36//  (d) When there are no changes to the sibling order under a parent node,
37//      the sibling order is not necessarily preserved in the output for
38//      its children.
39class ChangeReorderBuffer {
40 public:
41  typedef SyncManager::ChangeRecord ChangeRecord;
42  typedef SyncManager::ExtraPasswordChangeRecordData ExtraChangeRecordData;
43
44  ChangeReorderBuffer();
45  ~ChangeReorderBuffer();
46
47  // Insert an item, identified by the metahandle |id|, into the reorder
48  // buffer. This item will appear in the output list as an ACTION_ADD
49  // ChangeRecord.
50  void PushAddedItem(int64 id) {
51    operations_[id] = OP_ADD;
52  }
53
54  // Insert an item, identified by the metahandle |id|, into the reorder
55  // buffer. This item will appear in the output list as an ACTION_DELETE
56  // ChangeRecord.
57  void PushDeletedItem(int64 id) {
58    operations_[id] = OP_DELETE;
59  }
60
61  // Insert an item, identified by the metahandle |id|, into the reorder
62  // buffer. This item will appear in the output list as an ACTION_UPDATE
63  // ChangeRecord. Also, if |position_changed| is true, all siblings of this
64  // item will appear in the output list as well; if it wasn't explicitly
65  // pushed, the siblings will have an ACTION_UPDATE ChangeRecord.
66  void PushUpdatedItem(int64 id, bool position_changed) {
67    operations_[id] = position_changed ? OP_UPDATE_POSITION_AND_PROPERTIES :
68                                         OP_UPDATE_PROPERTIES_ONLY;
69  }
70
71  void SetExtraDataForId(int64 id, ExtraChangeRecordData* extra) {
72    extra_data_[id] = make_linked_ptr<ExtraChangeRecordData>(extra);
73  }
74
75  void SetSpecificsForId(int64 id, const sync_pb::EntitySpecifics& specifics) {
76    specifics_[id] = specifics;
77  }
78
79  // Reset the buffer, forgetting any pushed items, so that it can be used
80  // again to reorder a new set of changes.
81  void Clear() {
82    operations_.clear();
83  }
84
85  bool IsEmpty() const {
86    return operations_.empty();
87  }
88
89  // Output a reordered list of changes to |changelist| using the items that
90  // were pushed into the reorder buffer. |sync_trans| is used to determine the
91  // ordering.
92  void GetAllChangesInTreeOrder(const BaseTransaction* sync_trans,
93                                std::vector<ChangeRecord>* changelist);
94
95 private:
96  class Traversal;
97  enum Operation {
98    OP_ADD,                             // AddedItem.
99    OP_DELETE,                          // DeletedItem.
100    OP_UPDATE_PROPERTIES_ONLY,          // UpdatedItem with position_changed=0.
101    OP_UPDATE_POSITION_AND_PROPERTIES,  // UpdatedItem with position_changed=1.
102  };
103  typedef std::map<int64, Operation> OperationMap;
104  typedef std::map<int64, sync_pb::EntitySpecifics> SpecificsMap;
105  typedef std::map<int64, linked_ptr<ExtraChangeRecordData> > ExtraDataMap;
106
107  // Stores the items that have been pushed into the buffer, and the type of
108  // operation that was associated with them.
109  OperationMap operations_;
110
111  // Stores entity-specific ChangeRecord data per-ID.
112  SpecificsMap specifics_;
113
114  // Stores type-specific extra data per-ID.
115  ExtraDataMap extra_data_;
116
117  DISALLOW_COPY_AND_ASSIGN(ChangeReorderBuffer);
118};
119
120}  // namespace sync_api
121
122#endif  // CHROME_BROWSER_SYNC_ENGINE_CHANGE_REORDER_BUFFER_H_
123