settingsd/simple_settings_map.cc

// Copyright 2015 The Chromium OS Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "settingsd/simple_settings_map.h"

#include <algorithm>

#include <base/logging.h>

#include "settingsd/identifier_utils.h"
#include "settingsd/settings_document.h"

namespace settingsd {

SimpleSettingsMap::SimpleSettingsMap() {}

SimpleSettingsMap::~SimpleSettingsMap() {}

BlobRef SimpleSettingsMap::GetValue(const Key& key) const {
  const auto it = value_map_.find(key);
  return it == value_map_.end() ? BlobRef() : it->second->GetValue(key);
}

std::set<Key> SimpleSettingsMap::GetKeys(const Key& prefix) const {
  std::set<Key> keys;
  for (const auto& entry : utils::GetRange(prefix, value_map_))
    keys.insert(entry.first);
  return keys;
}

bool SimpleSettingsMap::HasLaterValueAssignment(
    const Key& key,
    const VersionStamp& lower_bound) {
  const auto entry = value_map_.find(key);
  return entry != value_map_.end() &&
         entry->second->GetVersionStamp().IsAfter(lower_bound);
}

bool SimpleSettingsMap::HasLaterSubtreeDeletion(
    const Key& prefix,
    const VersionStamp& lower_bound) const {
  Key current_prefix = prefix;
  do {
    const auto deletion = deletion_map_.find(current_prefix);
    if (deletion != deletion_map_.end() &&
        deletion->second->GetVersionStamp().IsAfter(lower_bound))
      return true;
    current_prefix = current_prefix.GetParent();
  } while (!current_prefix.IsRootKey());
  return false;
}

SimpleSettingsMap::DocumentWeakPtrList::iterator
SimpleSettingsMap::FindDocumentInSortedList(
    const SettingsDocument* document_ptr) {
  return std::find_if(
      documents_.begin(), documents_.end(),
      [document_ptr](const std::weak_ptr<const SettingsDocument> doc_ptr) {
        return doc_ptr.lock().get() == document_ptr;
      });
}

void SimpleSettingsMap::InsertDocumentIntoSortedList(
    std::shared_ptr<const SettingsDocument> document) {
  const auto pos = std::find_if(
      documents_.begin(), documents_.end(),
      [&document](const std::weak_ptr<const SettingsDocument>& document_ptr) {
        std::shared_ptr<const SettingsDocument> doc = document_ptr.lock();
        return doc->GetVersionStamp().IsAfter(document->GetVersionStamp());
      });
  documents_.insert(pos, document);
}

void SimpleSettingsMap::DeleteSubtree(const Key& prefix,
                                      const VersionStamp& upper_limit,
                                      std::set<Key>* modified_keys) {
  // Remove deletions.
  const auto deletion_range = utils::GetRange(prefix, deletion_map_);
  for (auto it = deletion_range.begin(); it != deletion_range.end();) {
    if (it->second->GetVersionStamp().IsBefore(upper_limit))
      deletion_map_.erase(it++);
    else
      ++it;
  }

  // Remove value assignments.
  const auto value_range = utils::GetRange(prefix, value_map_);
  for (auto it = value_range.begin(); it != value_range.end();) {
    if (it->second->GetVersionStamp().IsBefore(upper_limit)) {
      if (modified_keys)
        modified_keys->insert(it->first);
      value_map_.erase(it++);
    } else {
      ++it;
    }
  }
}

void SimpleSettingsMap::InsertDocumentSubset(
    std::shared_ptr<const SettingsDocument> document,
    const std::set<Key>& prefixes,
    std::set<Key>* modified_keys) {
  // Convenience shortcuts.
  const VersionStamp& version_stamp = document->GetVersionStamp();

  for (const auto& prefix : prefixes) {
    // Deletions are always processed first, so that value assignments in key
    // prefixes affected by a deletion in the same document are not clobbered by
    // those deletions.
    for (const auto& prefix_deletion : document->GetDeletions(prefix)) {
      // Check if there is a later deletion in place higher up in the
      // ancestorial key hierarchy which renders this deletion obsolete.
      if (!HasLaterSubtreeDeletion(prefix_deletion, version_stamp)) {
        DeleteSubtree(prefix_deletion, version_stamp, modified_keys);
        deletion_map_[prefix_deletion] = document;
      }
    }

    // After having processed all pending deletions, insert the new values into
    // |value_map_|.
    for (const auto& key : document->GetKeys(prefix)) {
      // Check if there is a later deletion in place higher up in the
      // ancestorial key hierarchy or whether there is a more recent value
      // assignment which would render this value assignment obsolete.
      if (!HasLaterSubtreeDeletion(key, version_stamp) &&
          !HasLaterValueAssignment(key, version_stamp)) {
        if (modified_keys)
          modified_keys->insert(key);
        value_map_[key] = document;
      }
    }
  }
}

bool SimpleSettingsMap::InsertDocument(
    const SettingsDocument* document,
    std::set<Key>* modified_keys,
    std::vector<const SettingsDocument*>* unreferenced_documents) {
  // |unreferenced_documents_| should be empty.
  DCHECK(unreferenced_documents_.empty());

  // Check if |document| has a prefix collision with a previously inserted,
  // concurrent document. In that case, abort.
  for (const auto& doc_ptr : documents_) {
    std::shared_ptr<const SettingsDocument> doc = doc_ptr.lock();
    if (doc->GetVersionStamp().IsConcurrent(document->GetVersionStamp()) &&
        SettingsDocument::HasOverlap(*document, *doc))
      return false;
  }

  // NOTE: The vector |documents_| actually has ownership of the
  // SettingsDocuments. Here we use the shared_ptr merely as a notification
  // system to inform SimpleSettingsMap of SettingsDocuments whose reference
  // count has dropped to zero. To accomplish this, we pass
  // OnDocumentUnreferenced as a deleter for
  // std::shared_ptr<const SettingsDocument>.
  std::shared_ptr<const SettingsDocument> document_ptr(
      document, std::bind(&SimpleSettingsMap::OnDocumentUnreferenced, this,
                          std::placeholders::_1));

  // Insert the whole document into |value_map_| and |deletion_map_|.
  std::set<Key> root_set;
  root_set.insert(Key());
  InsertDocumentSubset(document_ptr, root_set, modified_keys);

  // Insert the document into the sorted vector of active documents only if it
  // is currently providing a setting.
  if (!document_ptr.unique())
    InsertDocumentIntoSortedList(document_ptr);

  // If the document to be inserted has not become active, discarding the last
  // shared_ptr referring to it will add it to the list of unreferenced
  // documents.
  document_ptr.reset();

  // If the out parameter |unreferenced_documents| is non-null, output the list
  // of unreferenced documents.
  if (unreferenced_documents)
    std::swap(*unreferenced_documents, unreferenced_documents_);
  unreferenced_documents_.clear();

  return true;
}

void SimpleSettingsMap::RemoveDocument(
    const SettingsDocument* document_ptr,
    std::set<Key>* modified_keys,
    std::vector<const SettingsDocument*>* unreferenced_documents) {
  // |unreferenced_documents_| should be empty.
  DCHECK(unreferenced_documents_.empty());

  auto position = FindDocumentInSortedList(document_ptr);

  // If the SettingsDocument |document_ptr| is not in the list of active
  // documents, there is nothing to do.
  if (position == documents_.end())
    return;

  // Acquire a shared_ptr.
  std::shared_ptr<const SettingsDocument> document(*position);

  // Get a list of all keys from |document| currently providing values and
  // remove them from the |value_map_|.
  std::set<Key> prefixes_to_restore;
  for (auto it = value_map_.begin(); it != value_map_.end();) {
    if (it->second == document) {
      prefixes_to_restore.insert(it->first);
      if (modified_keys)
        modified_keys->insert(it->first);
      value_map_.erase(it++);
    } else {
      ++it;
    }
  }

  // Add all keys identifying prefixes which have been deleted by |document| and
  // remove them from the |deletion_map_|.
  for (auto it = deletion_map_.begin(); it != deletion_map_.end();) {
    if (it->second == document) {
      prefixes_to_restore.insert(it->first);
      deletion_map_.erase(it++);
    } else {
      ++it;
    }
  }

  // |document| should be the only remaining shared_ptr to the settings
  // document at this point.
  DCHECK_EQ(1, document.use_count());

  // Walk the sorted list of documents from the earliest document up to (but not
  // including) the current document and reinstall links in the |value_map_| and
  // |deletion_map_| which are now shining through.
  DocumentWeakPtrList::reverse_iterator current_document_ptr(position);
  for (; current_document_ptr != documents_.rend(); ++current_document_ptr) {
    std::shared_ptr<const SettingsDocument> current_document =
        current_document_ptr->lock();

    // Install the relevant prefixes into |value_map_| and |deletion_map_|.
    InsertDocumentSubset(current_document, prefixes_to_restore, modified_keys);
  }

  // Trigger clean-up of the document to be removed and addition to the list of
  // unreferenced documents by discarding the last shared_ptr referring to it.
  document.reset();

  // This should have triggered the clean-up of |document|.
  DCHECK(documents_.end() == FindDocumentInSortedList(document_ptr));

  // If the out parameter |unreferenced_documents| is non-null, output the list
  // of unreferenced documents.
  if (unreferenced_documents)
    std::swap(*unreferenced_documents, unreferenced_documents_);
  unreferenced_documents_.clear();
}

void SimpleSettingsMap::OnDocumentUnreferenced(
    const SettingsDocument* document) {
  DocumentWeakPtrList::iterator position =
      std::remove_if(documents_.begin(), documents_.end(),
                     [](const std::weak_ptr<const SettingsDocument>& doc) {
                       return doc.expired();
                     });
  documents_.erase(position, documents_.end());
  unreferenced_documents_.push_back(document);
}

void SimpleSettingsMap::Clear() {
  deletion_map_.clear();
  value_map_.clear();
}

}  // namespace settingsd