src/sync/syncable/parent_child_index.cc

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