payload_generator/graph_types.h

//
// Copyright (C) 2009 The Android Open Source Project
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//

#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_
#define UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_

#include <map>
#include <set>
#include <string>
#include <utility>
#include <vector>

#include <base/macros.h>

#include "update_engine/payload_generator/annotated_operation.h"
#include "update_engine/payload_generator/extent_utils.h"
#include "update_engine/update_metadata.pb.h"

// A few classes that help in generating delta images use these types
// for the graph work.

namespace chromeos_update_engine {

struct EdgeProperties {
  // Read-before extents. I.e., blocks in |extents| must be read by the
  // node pointed to before the pointing node runs (presumably b/c it
  // overwrites these blocks).
  std::vector<Extent> extents;

  // Write before extents. I.e., blocks in |write_extents| must be written
  // by the node pointed to before the pointing node runs (presumably
  // b/c it reads the data written by the other node).
  std::vector<Extent> write_extents;

  bool operator==(const EdgeProperties& that) const {
    return extents == that.extents && write_extents == that.write_extents;
  }
};

struct Vertex {
  Vertex() :
      valid(true),
      index(-1),
      lowlink(-1) {}
  bool valid;

  typedef std::map<std::vector<Vertex>::size_type, EdgeProperties> EdgeMap;
  EdgeMap out_edges;

  // We sometimes wish to consider a subgraph of a graph. A subgraph would have
  // a subset of the vertices from the graph and a subset of the edges.
  // When considering this vertex within a subgraph, subgraph_edges stores
  // the out-edges.
  typedef std::set<std::vector<Vertex>::size_type> SubgraphEdgeMap;
  SubgraphEdgeMap subgraph_edges;

  // For Tarjan's algorithm:
  std::vector<Vertex>::size_type index;
  std::vector<Vertex>::size_type lowlink;

  // Other Vertex properties:
  AnnotatedOperation aop;

  typedef std::vector<Vertex>::size_type Index;
  static const Vertex::Index kInvalidIndex;
};

typedef std::vector<Vertex> Graph;

typedef std::pair<Vertex::Index, Vertex::Index> Edge;

const uint64_t kTempBlockStart = 1ULL << 60;
static_assert(kTempBlockStart != 0, "kTempBlockStart invalid");

}  // namespace chromeos_update_engine

#endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_