1c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// Copyright (c) 2012 The Chromium Authors. All rights reserved. 2c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 3c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// found in the LICENSE file. 4c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 5c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "sync/syncable/parent_child_index.h" 6c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 7c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "base/stl_util.h" 8c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 9c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "sync/syncable/entry_kernel.h" 10c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "sync/syncable/syncable_id.h" 11c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 12c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)namespace syncer { 13c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)namespace syncable { 14c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 15c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)bool ChildComparator::operator()( 16c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const syncable::EntryKernel* a, 17c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const syncable::EntryKernel* b) const { 18c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const UniquePosition& a_pos = a->ref(UNIQUE_POSITION); 19c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const UniquePosition& b_pos = b->ref(UNIQUE_POSITION); 20c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 21c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (a_pos.IsValid() && b_pos.IsValid()) { 22c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Position is important to this type. 23c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return a_pos.LessThan(b_pos); 24c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } else if (a_pos.IsValid() && !b_pos.IsValid()) { 25c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // TODO(rlarocque): Remove this case. 26c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // An item with valid position as sibling of one with invalid position. 27c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // We should not support this, but the tests rely on it. For now, just 28c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // move all invalid position items to the right. 29c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return true; 30c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } else if (!a_pos.IsValid() && b_pos.IsValid()) { 31c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // TODO(rlarocque): Remove this case. 32c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Mirror of the above case. 33c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return false; 34c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } else { 35c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Position doesn't matter. 36c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DCHECK(!a->ref(UNIQUE_POSITION).IsValid()); 37c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DCHECK(!b->ref(UNIQUE_POSITION).IsValid()); 38c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return a->ref(ID) < b->ref(ID); 39c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 40c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 41c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 42c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)ParentChildIndex::ParentChildIndex() { 43c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 44c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 45c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)ParentChildIndex::~ParentChildIndex() { 46c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) STLDeleteContainerPairSecondPointers( 47c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) parent_children_map_.begin(), parent_children_map_.end()); 48c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 49c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 50c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)bool ParentChildIndex::ShouldInclude(const EntryKernel* entry) { 51c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // This index excludes deleted items and the root item. The root 52c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // item is excluded so that it doesn't show up as a child of itself. 53c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return !entry->ref(IS_DEL) && !entry->ref(ID).IsRoot(); 54c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 55c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 56c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)bool ParentChildIndex::Insert(EntryKernel* entry) { 57c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DCHECK(ShouldInclude(entry)); 58c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 59c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const syncable::Id& parent_id = entry->ref(PARENT_ID); 60c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) OrderedChildSet* children = NULL; 61c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ParentChildrenMap::iterator i = parent_children_map_.find(parent_id); 62c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (i != parent_children_map_.end()) { 63c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) children = i->second; 64c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } else { 65c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) children = new OrderedChildSet(); 66c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) parent_children_map_.insert(std::make_pair(parent_id, children)); 67c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 68c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 69c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return children->insert(entry).second; 70c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 71c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 72c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// Like the other containers used to help support the syncable::Directory, this 73c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// one does not own any EntryKernels. This function removes references to the 74c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// given EntryKernel but does not delete it. 75c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)void ParentChildIndex::Remove(EntryKernel* e) { 76c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ParentChildrenMap::iterator parent = 77c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) parent_children_map_.find(e->ref(PARENT_ID)); 78c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DCHECK(parent != parent_children_map_.end()); 79c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 80c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) OrderedChildSet* children = parent->second; 81c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) OrderedChildSet::iterator j = children->find(e); 82c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DCHECK(j != children->end()); 83c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 84c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) children->erase(j); 85c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (children->empty()) { 86c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) delete children; 87c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) parent_children_map_.erase(parent); 88c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 89c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 90c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 91c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)bool ParentChildIndex::Contains(EntryKernel *e) const { 92c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const syncable::Id& parent_id = e->ref(PARENT_ID); 93c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ParentChildrenMap::const_iterator parent = 94c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) parent_children_map_.find(parent_id); 95c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (parent == parent_children_map_.end()) { 96c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return false; 97c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 98c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) const OrderedChildSet* children = parent->second; 99c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DCHECK(children && !children->empty()); 100c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return children->count(e) > 0; 101c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 102c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 103c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)const OrderedChildSet* ParentChildIndex::GetChildren(const syncable::Id& id) { 104c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) ParentChildrenMap::iterator parent = parent_children_map_.find(id); 105c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (parent == parent_children_map_.end()) { 106c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return NULL; 107c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 108c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 109c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // A successful lookup implies at least some children exist. 110c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DCHECK(!parent->second->empty()); 111c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) return parent->second; 112c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 113c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 114c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} // namespace syncable 115c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} // namespace syncer 116