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