text:
//
// MIT License
//
// Copyright 2019-2020
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.
//
#include <boost/core/ignore_unused.hpp>
#include <boost/filesystem.hpp>
#include <boost/interprocess/file_mapping.hpp>
#include <boost/interprocess/mapped_region.hpp>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <string>

#include "cartridge.hh"
#include "disassemble.hh"
#include "tool.hh"
#include "tool_decoder.hh"

namespace fs = boost::filesystem;
namespace ip = boost::interprocess;

namespace jd = jones::disassemble;
namespace jo = jones;

namespace {

std::string to_hex_string(uint8_t *data, size_t size, size_t width, bool left_to_right = true) {
  std::ostringstream oss;
  if (left_to_right) {
    for (int i = 0; i < static_cast<int>(size); i++) {
      oss << std::hex << std::uppercase << std::setw(2) << std::setfill('0') << static_cast<uint16_t>(data[i]);
    }
  } else {
    for (int i = (size - 1); i >= 0; i--) {
      oss << std::hex << std::uppercase << std::setw(2) << std::setfill('0') << static_cast<uint16_t>(data[i]);
    }
  }
  for (int i = 0; i < static_cast<int>(width - (size * 2)); i++) {
    oss << " ";
  }
  return oss.str();
}

void dump_code(const fs::path &root_path, const jo::cartridge &rom) {
  boost::ignore_unused(rom);

  const fs::path code_path = root_path / "code";
  fs::create_directories(code_path);
  fs::ofstream code_file{code_path / "prgrom.a65"};

  const fs::path prgrom_path = root_path / "raw" / "prgrom.bin";
  const ip::file_mapping mapped_file(prgrom_path.string().c_str(), ip::mode_t::read_only);
  const ip::mapped_region mapped_region(mapped_file, ip::mode_t::read_only);

  auto const &disassembled_code = jd::disassemble(static_cast<uint8_t *>(mapped_region.get_address()), mapped_region.get_size());
  auto const &disassembled_instructions = disassembled_code.instructions;
  for (auto instruction : disassembled_instructions) {
    auto instruction_address = instruction.address;
    code_file << "   " << to_hex_string(reinterpret_cast<uint8_t *>(&instruction_address), sizeof(instruction.address), 5, false);
    code_file << "   " << to_hex_string(&instruction.length_in_bytes, sizeof(instruction.length_in_bytes), 5);
    code_file << "   " << to_hex_string(instruction.binary.data(), instruction.length_in_bytes, 10);
    code_file << "   " << instruction.opcode << instruction.operand << std::endl;
  }
}

void dump_audio(const fs::path &root_path, const jo::cartridge &rom) {
  boost::ignore_unused(rom);
  const fs::path audio_path = root_path / "audio";
  fs::create_directories(audio_path);
}

void dump_image(const fs::path &root_path, const jo::cartridge &rom) {
  boost::ignore_unused(rom);

  const fs::path image_path = root_path / "image";
  fs::create_directories(image_path);

  const fs::path chrrom_path = root_path / "raw" / "chrrom.bin";
  const ip::file_mapping mapped_file(chrrom_path.string().c_str(), ip::mode_t::read_only);
  const ip::mapped_region mapped_region(mapped_file, ip::mode_t::read_only);

  jones::tool::decode_chrrom(static_cast<uint8_t *>(mapped_region.get_address()), mapped_region.get_size(), image_path.string().c_str());
}

void dump_raw(const fs::path &root_path, const jo::cartridge &rom) {
  const fs::path raw_path = root_path / "raw";
  fs::create_directories(raw_path);
  {
    const fs::path chrom_path = raw_path / "chrrom.bin";
    std::ofstream chrom_file{chrom_path.string()};
    rom.dump_chr(chrom_file);
  }
  {
    const fs::path prgrom_path = raw_path / "prgrom.bin";
    std::ofstream prgrom_file{prgrom_path.string()};
    rom.dump_prg(prgrom_file);
  }
}

void dump_header(const fs::path &root_path, const jo::cartridge &rom) {
  const fs::path header_path = root_path / "rom_header.txt";
  std::ofstream header_file{header_path.string()};
  rom.print(header_file);
}

} // namespace

namespace jones::tool {

int dump(const char *file_path, const char *output_path) {
  memory cpu_memory{"cpu"};
  memory ppu_memory{"ppu"};
  cartridge rom = cartridge(cpu_memory, ppu_memory);
  if (!rom.attach(file_path)) {
    std::cerr << "error: must specify valid rom file" << std::endl;
    return -1;
  }

  dump_header(output_path, rom);
  dump_raw(output_path, rom);
  dump_code(output_path, rom);
  dump_audio(output_path, rom);
  dump_image(output_path, rom);

  return 0;
}

} // namespace jones::tool

max_stars_repo_name: JonForShort/nes-emulator

max_issues_repo_name: JonForShort/nes-emulator

max_forks_repo_name: JonForShort/nes-emulator


text:
/**
 *  \file RMF/paths.cpp
 *  \brief Handle read/write of Model data from/to files.
 *
 *  Copyright 2007-2021 IMP Inventors. All rights reserved.
 *
 */

#include "avrocpp/api/Compiler.hh"
#include <boost/lexical_cast.hpp>
#include <exception>
#include <sstream>

#include "AllJSON.h"
#include "DataFile.hh"
#include "Decoder.hh"
#include "Encoder.hh"
#include "RMF/exceptions.h"
#include "RMF/internal/paths.h"
#include "SingleAvroFile.h"
#include "Specific.hh"
#include "Stream.hh"
#include "ValidSchema.hh"
#include "avro_schema_io.h"
#include "avrocpp/api/DataFile.hh"
#include "avrocpp/api/Decoder.hh"
#include "avrocpp/api/Encoder.hh"
#include "avrocpp/api/Specific.hh"
#include "avrocpp/api/Stream.hh"
#include "avrocpp/api/ValidSchema.hh"
#include "AvroKeysAndCategories.h"
#include "generated/embed_jsons.h"

RMF_ENABLE_WARNINGS

namespace RMF {
namespace avro_backend {

SingleAvroFile::SingleAvroFile(std::string path, bool create,
                               bool /*read_only*/)
    : AvroKeysAndCategories(path), dirty_(false), text_(get_is_text(path)) {
  if (!create) {
    reload();
  } else {
    initialize_frames();
    initialize_categories();
    initialize_node_keys();
    all_.file.version = 1;
  }
  null_static_frame_data_.frame = -1;
}

SingleAvroFile::SingleAvroFile(boost::shared_ptr<std::vector<char> > buffer,
                               bool create, bool)
    : AvroKeysAndCategories("buffer"),
      dirty_(false),
      text_(false),
      buffer_(buffer) {
  if (!create) {
    reload();
  } else {
    initialize_frames();
    initialize_categories();
    initialize_node_keys();
    all_.file.version = 1;
  }
  null_static_frame_data_.frame = -1;
}

void SingleAvroFile::initialize_frames() {
  all_.frames.push_back(RMF_avro_backend::Node());
  access_frame(ALL_FRAMES).name = "static";
  access_frame(ALL_FRAMES).type = "static";
}

void SingleAvroFile::initialize_categories() {
  for (std::map<std::string,
                std::vector<RMF_avro_backend::Data> >::const_iterator it =
           all_.category.begin();
       it != all_.category.end(); ++it) {
    get_category(it->first);
  }
}

void SingleAvroFile::initialize_node_keys() {
  clear_node_keys();
  for (unsigned int i = 0; i < all_.nodes.size(); ++i) {
    add_node_key();
  }
}

void SingleAvroFile::flush() {
  if (!dirty_) return;
  if (!buffer_) {
    if (!text_) {
      write(all_, internal_avro::compileJsonSchemaFromString(
                      data_deprecated_avro::all_json),
            get_file_path());
    } else {
      write_text(all_, internal_avro::compileJsonSchemaFromString(
                           data_deprecated_avro::all_json),
                 get_file_path());
    }
  } else {
    buffer_->clear();
    std::ostringstream oss(std::ios_base::binary);
    boost::shared_ptr<internal_avro::OutputStream> os =
        internal_avro::ostreamOutputStream(oss);
    boost::shared_ptr<internal_avro::Encoder> encoder =
        internal_avro::binaryEncoder();
    encoder->init(*os);
    internal_avro::encode(*encoder, all_);
    os->flush();
    encoder.reset();
    os.reset();
    const std::string& str = oss.str();
    buffer_->insert(buffer_->end(), str.begin(), str.end());
  }
  dirty_ = false;
}

void SingleAvroFile::reload() {
  if (!buffer_ && !text_) {
    bool success;
    try {
      internal_avro::DataFileReader<RMF_avro_backend::All> rd(
          get_file_path().c_str(), internal_avro::compileJsonSchemaFromString(
                                       data_deprecated_avro::all_json));
      success = rd.read(all_);
    }
    catch (std::exception& e) {
      RMF_THROW(Message(e.what()) << File(get_file_path()), IOException);
    }
    if (!success) {
      RMF_THROW(Message("Can't read input file on reload"), IOException);
    }
  } else if (!buffer_ && text_) {
    boost::shared_ptr<internal_avro::Decoder> decoder =
        internal_avro::jsonDecoder(internal_avro::compileJsonSchemaFromString(
            data_deprecated_avro::all_json));
    boost::shared_ptr<internal_avro::InputStream> stream =
        internal_avro::fileInputStream(get_file_path().c_str());
    decoder->init(*stream);
    bool success = false;
    try {
      internal_avro::decode(*decoder, all_);
      success = true;
    }
    catch (std::exception& e) {
      RMF_THROW(Message(e.what()) << File(get_file_path()), IOException);
    }
    if (!success) {
      RMF_THROW(Message("Can't read input file on reload"), IOException);
    }
  } else {
    boost::shared_ptr<internal_avro::InputStream> is =
        internal_avro::memoryInputStream(
            reinterpret_cast<uint8_t*>(&(*buffer_)[0]), buffer_->size());
    boost::shared_ptr<internal_avro::Decoder> decoder =
        internal_avro::binaryDecoder();
    decoder->init(*is);
    internal_avro::decode(*decoder, all_);
  }
  initialize_categories();
  initialize_node_keys();
  dirty_ = false;
}

FrameID SingleAvroFile::add_frame(std::string name, FrameType t) {
  FrameID index = FrameID(get_number_of_frames());
  access_frame(index).name = name;
  access_frame(index).type = boost::lexical_cast<std::string>(t);
  if (get_loaded_frame() != FrameID()) {
    access_frame(get_loaded_frame()).children.push_back(index.get_index());
  }
  RMF_INTERNAL_CHECK(get_number_of_frames() ==
                         static_cast<unsigned int>(index.get_index()) + 1,
                     "No frame added");
  return index;
}

void SingleAvroFile::add_child_frame(FrameID child_node) {
  access_frame(get_loaded_frame()).children.push_back(child_node.get_index());
}

FrameIDs SingleAvroFile::get_children(FrameID node) const {
  return FrameIDs(get_frame(node).children.begin(),
                  get_frame(node).children.end());
}

std::string SingleAvroFile::get_loaded_frame_name() const {
  return get_frame(get_loaded_frame()).name;
}
FrameType SingleAvroFile::get_loaded_frame_type() const {
  return boost::lexical_cast<FrameType>(get_frame(get_loaded_frame()).type);
}
unsigned int SingleAvroFile::get_number_of_frames() const {
  return get_frames().size() - 1;
}

}  // namespace avro_backend
} /* namespace RMF */

RMF_DISABLE_WARNINGS

ext: cpp

max_stars_repo_name: salilab/rmf

max_issues_repo_name: salilab/rmf

max_forks_repo_name: salilab/rmf


text:
#include <boost/program_options.hpp>
//#include <boost/filesystem.hpp>
#include <list>
#include <string>
#include <cstdio>
#include "trace.h"
#include "error.h"
#include "solution.h"
namespace po = boost::program_options;
#ifdef _DEBUG
#define DEFAULT_TRACING_DEPTH 0
#else
#define DEFAULT_TRACING_DEPTH 3
#endif
int main(int argc, char **argv) {
	try {
		po::options_description general("");
		general.add_options()
			("debug,d", "Show debug info")
			("maxdepth,m", po::value<int>()->default_value(DEFAULT_TRACING_DEPTH),
						"Max tracing depth")
			("help,h", "Show this message and exit")
			("output,o", po::value<std::string>()->default_value("makefile"),
						"Output file name")
			("silent,s", "Don't output any log")
			("verbose,v", "Show verbose info");
		po::options_description hidden("Hidden options");
		hidden.add_options()
			("input,i", po::value< std::vector<std::string> >()->composing(),
						"Input filename");
		po::options_description options;
		options.add(general).add(hidden);
		po::positional_options_description p;
		p.add("input", -1);

		po::variables_map vm;
		po::store(po::command_line_parser(argc, argv).
			options(options).positional(p).run(), vm);
		po::notify(vm);

		if (vm.count("help")) {
			puts(
				"Usage: gensol [options] [input] ...\n"
				"  -d [ --debug    ]                 Show debug info\n"
				"  -m [ --maxdepth ] arg (=2)        Max tracing depth\n"
				"  -h [ --help     ]                 Show this message and exit\n"
				"  -o [ --output   ] arg (=makefile) Output file name\n"
				"  -s [ --silent   ]                 Don't output any log\n"
				"  -v [ --verbose  ]                 Show more log");
			return 0;
		}

		if(vm.count("input")) {
			for(auto &f : vm["input"].as<std::vector<std::string> >())
				solution.addInput(f);
		} else solution.addInput("solution.json");

		solution.setOutput(vm["output"].as<std::string>().c_str());
		trace.setMaxTracingDepth(vm["maxdepth"].as<int>());
		if(vm.count("silent")) trace.setOutputLevel(0, 0, 0);
		else if(vm.count("verbose")) trace.setOutputLevel(1, 1, 1);
		else if(vm.count("debug")) trace.setOutputLevel(1, 1, 0);
		else trace.setOutputLevel(1, 0, 0);
		solution.execute();
	} catch (const ERR::ERR &ex) {
		trace.leadingSpace(trace.depth);
		fputs(ex.what(), stderr);
		fputc('\n', stderr);
		while(!trace.stack.empty()) {
			trace.leadingSpace(trace.depth);
			fprintf(stderr, "In %s\n", trace.stack.top().c_str()),
			trace.pop();
		}
		return 1;
	} catch (const std::exception &ex) {
		fputs(ex.what(), stderr);
		return 1;
	}
	return 0;
}


text:
/*
 * This file belongs to the Galois project, a C++ library for exploiting parallelism.
 * The code is being released under the terms of the 3-Clause BSD License (a
 * copy is located in LICENSE.txt at the top-level directory).
 *
 * Copyright (C) 2018, The University of Texas at Austin. All rights reserved.
 * UNIVERSITY EXPRESSLY DISCLAIMS ANY AND ALL WARRANTIES CONCERNING THIS
 * SOFTWARE AND DOCUMENTATION, INCLUDING ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR ANY PARTICULAR PURPOSE, NON-INFRINGEMENT AND WARRANTIES OF
 * PERFORMANCE, AND ANY WARRANTY THAT MIGHT OTHERWISE ARISE FROM COURSE OF
 * DEALING OR USAGE OF TRADE.  NO WARRANTY IS EITHER EXPRESS OR IMPLIED WITH
 * RESPECT TO THE USE OF THE SOFTWARE OR DOCUMENTATION. Under no circumstances
 * shall University be liable for incidental, special, indirect, direct or
 * consequential damages or loss of profits, interruption of business, or
 * related expenses which may arise from use of Software or Documentation,
 * including but not limited to those resulting from defects in Software and/or
 * Documentation, or loss or inaccuracy of data of any kind.
 */

#include <boost/accumulators/accumulators.hpp>
#include <boost/accumulators/statistics/stats.hpp>
#include <boost/accumulators/statistics/count.hpp>
#include <boost/accumulators/statistics/mean.hpp>
#include <boost/accumulators/statistics/max.hpp>
#include <boost/accumulators/statistics/min.hpp>
#include <boost/accumulators/statistics/median.hpp>
#include <boost/accumulators/statistics/variance.hpp>

#include "galois/Galois.h"
#include "galois/AtomicHelpers.h"
#include "galois/FlatMap.h"
#include "galois/Reduction.h"
#include "galois/PriorityQueue.h"
#include "galois/Timer.h"
#include "galois/gstl.h"
#include "galois/Timer.h"
#include "galois/graphs/LCGraph.h"
#include "galois/graphs/TypeTraits.h"
#include "llvm/Support/CommandLine.h"

#include "Lonestar/BoilerPlate.h"
#include "Lonestar/BFS_SSSP.h"

#include <iostream>
#include <chrono>
#include <iomanip>
#include <unordered_set>
#include <fstream>
#include "stack_vector.h"

#ifndef STACK_BITVECTOR_SIZE
#define STACK_BITVECTOR_SIZE 23947347
#endif

namespace cll = llvm::cl;
using namespace std::chrono;
namespace acc = boost::accumulators;

static const char* name = "Single Source Shortest Path";
static const char* desc =
    "Computes the shortest path from a source node to all nodes in a directed "
    "graph using a modified chaotic iteration algorithm";
static const char* url = "single_source_shortest_path";

static cll::opt<std::string>
    filename(cll::Positional, cll::desc("<input graph>"), cll::Required);

static cll::opt<unsigned int>
    startNode("startNode",
              cll::desc("Node to start search from (default value 0)"),
              cll::init(0));
static cll::opt<unsigned int>
    reportNode("reportNode",
               cll::desc("Node to report distance to(default value 1)"),
               cll::init(1));
static cll::opt<unsigned int>
    stepShift("delta",
              cll::desc("Shift value for the deltastep (default value 13)"),
              cll::init(13));

enum Algo {
  deltaTile = 0,
  deltaStep,
  serDeltaTile,
  serDelta,
  dijkstraTile,
  dijkstra,
  topo,
  topoTile,
  serSP1,
  serSP2,
  parSP1,
  parSP2
};

const char* const ALGO_NAMES[] = {"deltaTile", "deltaStep",    "serDeltaTile",
                                  "serDelta",  "dijkstraTile", "dijkstra",
                                  "topo", "topoTile", "serSP1", "serSP2", "parSP1", "parSP2"};

static cll::opt<Algo>
    algo("algo", cll::desc("Choose an algorithm:"),
         cll::values(clEnumVal(deltaTile, "deltaTile"),
                     clEnumVal(deltaStep, "deltaStep"),
                     clEnumVal(serDeltaTile, "serDeltaTile"),
                     clEnumVal(serDelta, "serDelta"),
                     clEnumVal(dijkstraTile, "dijkstraTile"),
                     clEnumVal(dijkstra, "dijkstra"), clEnumVal(topo, "topo"),
                     clEnumVal(topoTile, "topoTile"),
                     clEnumVal(serSP1, "serSP1"),
                     clEnumVal(serSP2, "serSP2"),
                     clEnumVal(parSP1, "parSP1"),
                     clEnumVal(parSP2, "parSP2"),
                     clEnumValEnd),
         cll::init(deltaTile));

constexpr static const bool TRACK_WORK          = false;
constexpr static const unsigned CHUNK_SIZE      = 64u;
constexpr static const ptrdiff_t EDGE_TILE_SIZE = 512;

high_resolution_clock::time_point start;

template<typename GraphTypes>
struct SerNodeData {
  typename GraphTypes::SerGraphType::GraphNode node;
  int pred;
  uint32_t dist;
  bool fixed;
  high_resolution_clock::time_point fixed_ts;
  uint32_t min_in_weight;
  SerNodeData(): node(-1), pred(0), dist(0), fixed(false) {}
};

template<typename GraphTypes>
struct ParNodeData {
  typename GraphTypes::ParGraphType::GraphNode node;
  std::atomic<int> pred;
  std::atomic<uint32_t> dist;
  std::atomic<bool> fixed;
  high_resolution_clock::time_point fixed_ts;
  uint32_t min_in_weight;
  ParNodeData(): node(-1), pred(0), dist(0), fixed(false) {}
};

struct GraphTypes {
  typedef SerNodeData<GraphTypes> SerNodeDataType;
  typedef galois::graphs::LC_CSR_Graph<typename GraphTypes::SerNodeDataType, uint32_t>::
  with_no_lockable<true>::type ::with_numa_alloc<true>::type SerGraphType;
  typedef ParNodeData<GraphTypes> ParNodeDataType;
  typedef galois::graphs::LC_CSR_Graph<typename GraphTypes::ParNodeDataType, uint32_t>::
  with_no_lockable<true>::type ::with_numa_alloc<true>::type ParGraphType;
};

std::vector<uint32_t> total_pred;

template<typename GType>
struct GraphTypeTraits {
  typedef BFS_SSSP<GType, uint32_t, true, EDGE_TILE_SIZE> SSSP;
  typedef typename SSSP::Dist Dist;
  typedef typename SSSP::UpdateRequest UpdateRequest;
  typedef typename SSSP::UpdateRequestIndexer UpdateRequestIndexer;
  typedef typename SSSP::SrcEdgeTile SrcEdgeTile;
  typedef typename SSSP::SrcEdgeTileMaker SrcEdgeTileMaker;
  typedef typename SSSP::SrcEdgeTilePushWrap SrcEdgeTilePushWrap;
  typedef typename SSSP::ReqPushWrap ReqPushWrap;
  typedef typename SSSP::OutEdgeRangeFn OutEdgeRangeFn;
  typedef typename SSSP::TileRangeFn TileRangeFn;
};

template<typename GType>
struct GraphType {
  typedef GType Graph;
  typedef typename GType::GraphNode GNode;
  typedef GraphTypeTraits<GType> Traits;
};

template <typename GType,
          typename T,
          typename P,
          typename R,
          typename Graph = typename GType::Graph,
          typename GNode = typename GType::GNode,
          typename Traits = typename GType::Traits>
void deltaStepAlgo(Graph& graph,
                   GNode source,
                   const P& pushWrap,
                   const R& edgeRange) {

  using Dist                 = typename Traits::Dist;
  using UpdateRequestIndexer = typename Traits::UpdateRequestIndexer;

  //! [reducible for self-defined stats]
  galois::GAccumulator<size_t> BadWork;
  //! [reducible for self-defined stats]
  galois::GAccumulator<size_t> WLEmptyWork;

  namespace gwl = galois::worklists;

  using PSchunk = gwl::PerSocketChunkFIFO<CHUNK_SIZE>;
  using OBIM = galois::worklists::OrderedByIntegerMetric<UpdateRequestIndexer, PSchunk>;

  graph.getData(source).dist = 0;

  galois::InsertBag<T> initBag;
  pushWrap(initBag, source, 0, "parallel");

  galois::for_each(galois::iterate(initBag),
                   [&](const T& item, auto& ctx) {
                     constexpr galois::MethodFlag flag =
                         galois::MethodFlag::UNPROTECTED;
                     const auto& sdata = graph.getData(item.src, flag);

                     if (sdata.dist < item.dist) {
                       if (TRACK_WORK)
                         WLEmptyWork += 1;
                       return;
                     }

                     for (auto ii : edgeRange(item)) {

                       GNode dst          = graph.getEdgeDst(ii);
                       auto& ddist        = graph.getData(dst, flag);
                       Dist ew            = graph.getEdgeData(ii, flag);
                       const Dist newDist = sdata.dist + ew;

                       while (true) {
                         Dist oldDist = ddist.dist;

                         if (oldDist <= newDist) {
                           break;
                         }

                         if (ddist.dist.compare_exchange_weak(
                                 oldDist, newDist, std::memory_order_relaxed)) {

                           ddist.fixed = true;
                           ddist.fixed_ts = high_resolution_clock::now();

                           if (TRACK_WORK) {
                             //! [per-thread contribution of self-defined stats]
                             if (oldDist != GType::Traits::SSSP::DIST_INFINITY) {
                               BadWork += 1;
                             }
                             //! [per-thread contribution of self-defined stats]
                           }

                           pushWrap(ctx, dst, newDist);
                           break;
                         }
                       }
                     }
                   },
                   galois::wl<OBIM>(UpdateRequestIndexer{stepShift}),
                   galois::no_conflicts(), galois::loopname("SSSP"));

  if (TRACK_WORK) {
    //! [report self-defined stats]
    galois::runtime::reportStat_Single("SSSP", "BadWork", BadWork.reduce());
    //! [report self-defined stats]
    galois::runtime::reportStat_Single("SSSP", "WLEmptyWork",
                                       WLEmptyWork.reduce());
  }
}

template <typename GType,
          typename T,
          typename P,
          typename R,
          typename Graph = typename GType::Graph,
          typename GNode = typename GType::GNode,
          typename Traits = typename GType::Traits>
void serDeltaAlgo(Graph& graph, const GNode& source,
                  const P& pushWrap, const R& edgeRange) {

  using UpdateRequestIndexer = typename Traits::UpdateRequestIndexer;

  SerialBucketWL<T, UpdateRequestIndexer> wl(UpdateRequestIndexer{stepShift});
  graph.getData(source).dist = 0;

  pushWrap(wl, source, 0);

  size_t iter = 0ul;
  while (!wl.empty()) {

    auto& curr = wl.minBucket();

    while (!curr.empty()) {
      ++iter;
      auto item = curr.front();
      curr.pop_front();

      if (graph.getData(item.src).dist < item.dist) {
        // empty work
        continue;
      }

      for (auto e : edgeRange(item)) {

        GNode dst   = graph.getEdgeDst(e);
        auto& ddata = graph.getData(dst);

        const auto newDist = item.dist + graph.getEdgeData(e);

        if (newDist < ddata.dist) {
          ddata.dist = newDist;
          pushWrap(wl, dst, newDist);
        }
      }
    }

    wl.goToNextBucket();
  }

  if (!wl.allEmpty()) {
    std::abort();
  }
  galois::runtime::reportStat_Single("SSSP-Serial-Delta", "Iterations", iter);
}

template <typename GType,
          typename T,
          typename P,
          typename R,
          typename Graph = typename GType::Graph,
          typename GNode = typename GType::GNode,
          typename Traits = typename GType::Traits>
void dijkstraAlgo(Graph& graph, const GNode& source, const P& pushWrap,
                  const R& edgeRange) {

  using WL = galois::MinHeap<T>;

  graph.getData(source).dist = 0;

  WL wl;
  pushWrap(wl, source, 0);

  while (!wl.empty()) {

    T item = wl.pop();

    if (graph.getData(item.src).dist < item.dist) {
      continue;
    }

    auto& nd = graph.getData(item.src);
    nd.fixed = true;
    nd.fixed_ts = high_resolution_clock::now();

    for (auto e : edgeRange(item)) {

      GNode dst   = graph.getEdgeDst(e);
      auto& ddata = graph.getData(dst);

      const auto newDist = item.dist + graph.getEdgeData(e);

      if (newDist < ddata.dist) {
        ddata.dist = newDist;
        pushWrap(wl, dst, newDist);
      }
    }
  }
}

template<typename Graph, typename R>
void calc_graph_predecessors(Graph& graph, R& edgeRange) {
  // Fill the pred array
  for (auto vertex : graph) {
    for (auto edge : edgeRange(vertex)) {
      auto& k_data = graph.getData(graph.getEdgeDst(edge));
      k_data.pred++;
      total_pred[k_data.node]++;
      k_data.min_in_weight = std::min(k_data.min_in_weight, graph.getEdgeData(edge));
    }
  }
}

#ifdef DEBUG
#define D(x) x
#else
#define D(x)
#endif

#define LIKELY(condition) __builtin_expect(static_cast<bool>(condition), 1)
#define UNLIKELY(condition) __builtin_expect(static_cast<bool>(condition), 0)

template <typename GType,
          typename T,
          typename P,
          typename R,
          typename Graph = typename GType::Graph,
          typename GNode = typename GType::GNode,
          typename GNodeData = typename GType::Graph::node_data_type,
          typename Traits = typename GType::Traits,
	  typename Cmp = std::less<typename Traits::Dist>>
void serSP1Algo(Graph& graph, const GNode& source,
                const P& pushWrap, const R& edgeRange) {

  using Heap = galois::MinHeap<T>;
  using Dist = typename Traits::Dist;

  bool changed;

  Heap heap;
  pushWrap(heap, source, 0);

  galois::gstl::Vector<GNodeData*> r_set;
  r_set.reserve(100);

  GNodeData* min = nullptr;
  Cmp cmp;

  // While the heap is not empty
  while (!heap.empty() || !r_set.empty()) {

    while (LIKELY(!heap.empty())) {
      T item = heap.top();
      GNodeData* item_data = &graph.getData(item.src);

      if (item_data->fixed || item_data->dist < item.dist) {
        // If we got a min, go do some work.
        heap.pop();
        if (!r_set.empty()) break;
        continue;
      }
      heap.pop();
      min = item_data;
      min->fixed = true;
      min->fixed_ts = high_resolution_clock::now();
      r_set.push_back(min);

      if (!(UNLIKELY(!heap.empty()) && heap.top().dist == min->dist)) break;
    }

    // Inner loop, go through the all the elements in R
    while(r_set.size() > 0) {
      GNodeData* z = r_set.back();
      r_set.pop_back();

      // Get all the vertices that have edges from z
      for (auto e : edgeRange(z->node)) {
        // If k vertex is not fixed, process the edge between z and k.
        auto k = &graph.getData(graph.getEdgeDst(e));
        if (k->fixed) continue;

        Dist z_k_dist = graph.getEdgeData(e);

        changed = false;
        if(z->dist + z_k_dist < k->dist) {
          k->dist = z->dist + z_k_dist;
          changed = true;
          if (k->dist < min->dist) min = k;
        }
        if (--k->pred <= 0) {
          k->fixed = true;
          k->fixed_ts = high_resolution_clock::now();
          r_set.push_back(k);
        } else if (changed) {
          pushWrap(heap,k->node,k->dist);
        }
      }

      if (r_set.empty() && !min->fixed && cmp(min->dist, heap.top().dist)){
        // We're done, but before we break, let's just check whether we have the new min in the q set
        // That is, if the heap is not empty and the current min is higher than the min in the q
        // set no point in pushing back to the heap, where it would have to bubble up.
        min->fixed = true;
        min->fixed_ts = high_resolution_clock::now();
        r_set.push_back(min);
      }
    }
  }
}

// template <typename GType,
//           typename T,
//           typename P,
//           typename R,
//           typename Graph = typename GType::Graph,
//           typename GNode = typename GType::GNode,
//           typename GNodeData = typename GType::Graph::node_data_type,
//           typename Traits = typename GType::Traits,
// 	  typename Cmp = std::less<typename Traits::Dist>>
// void serSP2Algo(Graph& graph, const GNode& source,
//                 const P& pushWrap, const R& edgeRange) {

//   using Heap = galois::MinHeap<T>;
//   using Dist = typename Traits::Dist;

//   bool changed;

//   Heap heap;
//   pushWrap(heap, source, 0);

//   galois::gstl::Vector<GNodeData*> r_set;
//   r_set.reserve(100);

//   GNodeData* min = nullptr;
//   Cmp cmp;

//   // While the heap is not empty
//   while (!heap.empty() || !r_set.empty()) {

//     while (LIKELY(!heap.empty())) {
//       T item = heap.top();
//       GNodeData* item_data = &graph.getData(item.src);

//       if (item_data->fixed || item_data->dist < item.dist) {
//         // If we got a min, go do some work.
//         heap.pop();
//         if (!r_set.empty()) break;
//         continue;
//       }
//       heap.pop();
//       min = item_data;
//       min->fixed = true;
//       min->fixed_ts = high_resolution_clock::now();
//       r_set.push_back(min);

//       if (heap.empty() || heap.top().dist != min->dist) break;
//     }

//     galois::gstl::Vector<GNodeData*> q_set1;
//     galois::gstl::Vector<GNodeData*> q_set2;
//     galois::gstl::Vector<GNodeData*>* q_set_current = &q_set1;
//     galois::gstl::Vector<GNodeData*>* q_set_aux = &q_set2;
//     // Inner loop, go through the all the elements in R
//     while(r_set.size() > 0) {
//       GNodeData* z = r_set.back();
//       r_set.pop_back();

//       // Get all the vertices that have edges from z
//       for (auto e : edgeRange(z->node)) {
//         auto k = &graph.getData(graph.getEdgeDst(e));
//         Dist z_k_dist = graph.getEdgeData(e);
//         // If k vertex is not fixed, process the edge between z and k.
//         if (k->fixed) continue;

//         changed = false;
//         if(z->dist + z_k_dist < k->dist) {
//           //std::cout << "Trying to relax to " <<  (z->dist + z_k_dist) << std::endl;
//           k->dist = z->dist + z_k_dist;
//           changed = true;
//           if (k->dist < min->dist) min = k;
//         }
//         if (--k->pred == 0 || k->dist <= (min->dist + k->min_in_weight)) {
//           k->fixed = true;
//           k->fixed_ts = high_resolution_clock::now();
//           r_set.push_back(k);
//         } else if (changed) {
//           q_set_current->push_back(k);
//         }
//       }

//       if (r_set.empty()) {
//         if (!min->fixed && min->dist <= heap.top().dist) {
//           // We're done, but before we break, let's just check whether we have the new min in the q set
//           // That is, if the heap is not empty and the current min is higher than the min in the q
//           // set no point in pushing back to the heap, where it would have to bubble up.
//           min->fixed = true;
//           min->fixed_ts = high_resolution_clock::now();
//           r_set.push_back(min);
//         }
//         for (auto& q : *q_set_current) {
//           if (q->fixed) {
//             r_set.push_back(q);
//           } else {
//             q_set_aux->push_back(q);
//           }
//         }
//         if (r_set.empty()) {
//           for (auto& q: *q_set_aux) {
//             pushWrap(heap, q->node, q->dist);
//           }
//         } else {
//           q_set_current->clear();
//           auto temp =  q_set_current;
//           q_set_current = q_set_aux;
//           q_set_aux = temp;
//         }
//       }
//     }
//   }
// }

template <typename GType,
          typename T,
          typename P,
          typename R,
          typename Graph = typename GType::Graph,
          typename GNode = typename GType::GNode,
          typename GNodeData = typename GType::Graph::node_data_type,
          typename Traits = typename GType::Traits,
	  typename Cmp = std::less<typename Traits::Dist>>
void serSP2Algo(Graph& graph, const GNode& source,
                const P& pushWrap, const R& edgeRange) {

  using Heap = galois::MinHeap<T>;
  using Dist = typename Traits::Dist;

  bool changed;

  Heap heap;
  pushWrap(heap, source, 0);

  galois::gstl::Vector<GNodeData*> r_set;
  r_set.reserve(100);

  GNodeData* min = nullptr;
  Cmp cmp;

  // While the heap is not empty
  while (!heap.empty() || !r_set.empty()) {

    while (LIKELY(!heap.empty())) {
      T item = heap.top();
      GNodeData* item_data = &graph.getData(item.src);

       heap.pop();
      if (item_data->fixed || item_data->dist < item.dist) {
        // If we got a min, go do some work.
        if (!r_set.empty()) break;
        continue;
      }
      min = item_data;
      min->fixed = true;
      min->fixed_ts = high_resolution_clock::now();
      r_set.push_back(min);

      if (heap.empty() || heap.top().dist != min->dist) break;
    }

    // Inner loop, go through the all the elements in R
    while(r_set.size() > 0) {
      GNodeData* z = r_set.back();
      //std::cout << "Processing node " << z->node << std::endl;
      r_set.pop_back();

      // Get all the vertices that have edges from z
      for (auto e : edgeRange(z->node)) {
        auto k = &graph.getData(graph.getEdgeDst(e));
        Dist z_k_dist = graph.getEdgeData(e);
        // If k vertex is not fixed, process the edge between z and k.
        if (k->fixed) continue;

        changed = false;
        if(z->dist + z_k_dist < k->dist) {
          k->dist = z->dist + z_k_dist;
          changed = true;
          if (k->dist < min->dist) min = k;
        }
        if (--k->pred == 0 || k->dist <= (min->dist + k->min_in_weight)) {
          k->fixed = true;
          k->fixed_ts = high_resolution_clock::now();
          r_set.push_back(k);
        } else if (changed) {
          pushWrap(heap,k->node,k->dist);
        }
      }

      if (r_set.empty() && !min->fixed && cmp(min->dist, heap.top().dist)){
        // We're done, but before we break, let's just check whether we have the new min in the q set
        // That is, if the heap is not empty and the current min is higher than the min in the q
        // set no point in pushing back to the heap, where it would have to bubble up.
        min->fixed = true;
        min->fixed_ts = high_resolution_clock::now();
        r_set.push_back(min);
      }
    }
  }
}

template<typename GNode,
         typename Graph,
         typename Container,
         typename R>
inline int push_back_edges_of_node(const GNode& node,
                                   Graph& graph,
                                   Container& c,
                                   const R& edgeRange) {
  int edges_pushed = 0;
  for (auto& edge : edgeRange(node)) {
    c.push_back(std::make_pair(node, *edge));
    edges_pushed++;
  }
  return edges_pushed;
}

template <typename GType,
          typename T,
          typename P,
          typename R,
          typename Graph = typename GType::Graph,
          typename GNode = typename GType::GNode,
          typename GEdge = typename GType::Graph::edge_iterator::value_type,
          typename GNodeData = typename GType::Graph::node_data_type,
          typename Traits = typename GType::Traits>
void parSP1VerticesAlgo(Graph& graph,
                        const GNode& source,
                        const P& pushWrap,
                        const R& edgeRange) {

  using Heap = galois::ThreadSafeMinHeap<T>;
  using WorkItem = T;
  using PSchunk = galois::worklists::PerSocketChunkFIFO<CHUNK_SIZE>;
  using Dist = typename Traits::Dist;

  constexpr galois::MethodFlag flag = galois::MethodFlag::UNPROTECTED;

  Heap heap;
  std::atomic<uint32_t> last_heap_pop_dist(0);
  std::atomic<int> r_set_counter(1);
  std::mutex mutex;
  auto& source_data = graph.getData(source);
  source_data.fixed = true;
  source_data.fixed_ts = high_resolution_clock::now();

  galois::for_each(galois::iterate({T{source, 0}}),
                   [&](WorkItem z_item, auto& ctx) {

                     const auto& z_data = graph.getData(z_item.src, flag);
                     //std::cout << "Processing node " << z_data.node << std::endl;

                     for (auto& z_edge : edgeRange(z_item.src)) {
                       auto k = graph.getEdgeDst(z_edge);
                       auto& k_data = graph.getData(k, flag);

                       //std::cout << "Processing edge " << *z_edge << " from " << z_item.src << " to dst : " << k_data.node << " Current dist: " << k_dist << " New dist: " << new_dist << std::endl;
                       if (k_data.fixed) continue;

                       auto z_k_dist = graph.getEdgeData(z_edge, flag);
                       auto new_dist = z_data.dist + z_k_dist;
                       unsigned int k_dist = k_data.dist;;
                       bool changed = false;

                       while (new_dist < k_dist) {
                         //std::cout << "Trying to relax to " << new_dist << std::endl;
                         if (k_data.dist.compare_exchange_weak(k_dist, new_dist, std::memory_order_relaxed)) {
                           changed = true;
                           break;
                         }
                         k_dist = k_data.dist;
                         new_dist = z_data.dist + z_k_dist;
                       }

                       // If the k vertex is now fixed, push the edges to the r set, otherwise push k
                       // to the heap.
                       if (--k_data.pred == 0) {
                         k_data.fixed = true;
                         k_data.fixed_ts = high_resolution_clock::now();
                         //std::cout << "Fixed " << k_data.node << " to " << k_data.dist << " at: " << duration_cast<microseconds>(k_data.fixed_ts - start).count() << std::endl;
                         //std::cout << "SP1 cond " << k_data.pred << " SP2 cond" << (last_heap_pop_dist.load() + k_data.min_in_weight) << std::endl;
                         pushWrap(ctx, k, k_data.dist);
                         ++r_set_counter;
                       } else if (changed){
                         pushWrap(heap, k, k_data.dist);
                       }
                     }

                     if (--r_set_counter == 0) {

                       uint32_t min_dist = 0;
                       uint32_t items_pushed = 0;
                       while(!heap.empty()) {
                         auto j = heap.top();
                         auto& j_data = graph.getData(j.src, flag);

                         if (j_data.fixed || j_data.dist < j.dist) {
                           heap.pop();
                           if (r_set_counter.load() > 0) break;
                           continue;
                         }

                         heap.pop();
                         last_heap_pop_dist = (unsigned int)j_data.dist;
                         min_dist = j_data.dist;
                         j_data.fixed = true;
			 j_data.fixed_ts = high_resolution_clock::now();
                         ++r_set_counter;
                         pushWrap(ctx, j.src, j.dist);
                         items_pushed++;

                         if (!(UNLIKELY(!heap.empty()) && heap.top().dist == min_dist)) break;
                       }
                     }
                   },
                   galois::wl<PSchunk>(),
                   galois::no_conflicts(),
                   galois::loopname("sssp_parsp2_inner"));
}

template <typename GType,
          typename T,
          typename P,
          typename R,
          typename Graph = typename GType::Graph,
          typename GNode = typename GType::GNode,
          typename GEdge = typename GType::Graph::edge_iterator::value_type,
          typename GNodeData = typename GType::Graph::node_data_type,
          typename Traits = typename GType::Traits>
void parSP2VerticesAlgo(Graph& graph,
                        const GNode& source,
                        const P& pushWrap,
                        const R& edgeRange) {

  using Heap = galois::ThreadSafeMinHeap<T>;
  using WorkItem = T;
  using PSchunk = galois::worklists::PerSocketChunkFIFO<CHUNK_SIZE>;
  using Dist = typename Traits::Dist;

  constexpr galois::MethodFlag flag = galois::MethodFlag::UNPROTECTED;

  Heap heap;
  std::atomic<uint32_t> min_dist(0);
  std::atomic<int> r_set_counter(1);
  std::mutex mutex;
  auto& source_data = graph.getData(source);
  source_data.fixed = true;
  source_data.fixed_ts = high_resolution_clock::now();

  galois::for_each(galois::iterate({T{source, 0}}),
                   [&](WorkItem z_item, auto& ctx) {

                     const auto& z_data = graph.getData(z_item.src, flag);
                     //std::cout << "Processing node " << z_data.node << std::endl;

                     for (auto& z_edge : edgeRange(z_item.src)) {
                       auto k = graph.getEdgeDst(z_edge);
                       auto& k_data = graph.getData(k, flag);

                       //std::cout << "Processing edge " << *z_edge << " from " << z_item.src << " to dst : " << k_data.node << " Current dist: " << k_dist << " New dist: " << new_dist << std::endl;
                       if (k_data.fixed) continue;

                       auto z_k_dist = graph.getEdgeData(z_edge, flag);
                       auto new_dist = z_data.dist + z_k_dist;
                       unsigned int k_dist = k_data.dist;;
                       bool changed = false;

                       while (new_dist < k_dist) {
                         //std::cout << "Trying to relax to " << new_dist << std::endl;
                         if (k_data.dist.compare_exchange_weak(k_dist, new_dist, std::memory_order_relaxed)) {
                           changed = true;
                           break;
                         }
                         k_dist = k_data.dist;
                         new_dist = z_data.dist + z_k_dist;
                       }

                       // If the k vertex is now fixed, push the edges to the r set, otherwise push k
                       // to the heap.
                       --k_data.pred;
                       if (k_dist <= min_dist + k_data.min_in_weight || k_data.pred <= 0) {
                         k_data.fixed = true;
                         k_data.fixed_ts = high_resolution_clock::now();
                         //std::cout << "Fixed " << k_data.node << " to " << k_data.dist << " at: " << duration_cast<microseconds>(k_data.fixed_ts - start).count() << std::endl;
                         //std::cout << "SP1 cond " << k_data.pred << " SP2 cond" << (last_heap_pop_dist.load() + k_data.min_in_weight) << std::endl;
                         ++r_set_counter;
                         pushWrap(ctx, k, k_data.dist);
                       } else if (changed){
                         pushWrap(heap, k, k_data.dist);
                       }
                     }

                     if (--r_set_counter == 0) {
                       while(!heap.empty()) {
                         auto j = heap.top();
                         auto& j_data = graph.getData(j.src, flag);
                         heap.pop();
                         if (j_data.fixed || j_data.dist < j.dist) {
                           if (r_set_counter.load() > 0) break;
                           continue;
                         }

                         min_dist = (unsigned int)j_data.dist;
                         j_data.fixed = true;
			 j_data.fixed_ts = high_resolution_clock::now();
                         ++r_set_counter;
                         pushWrap(ctx, j.src, j.dist);

                         if (heap.empty() || heap.top().dist != min_dist) break;
                       }
                     }
                   },
                   galois::wl<PSchunk>(),
                   galois::no_conflicts(),
                   galois::loopname("sssp_parsp2_inner"));
}

template <typename GType,
          typename Graph = typename GType::Graph,
          typename GNode = typename GType::GNode,
          typename Traits = typename GType::Traits>
void topoAlgo(Graph& graph, const GNode& source) {
  using SSSP                 = typename Traits::SSSP;
  using Dist                 = typename Traits::Dist;

  galois::LargeArray<Dist> oldDist;
  oldDist.allocateInterleaved(graph.size());

  constexpr Dist INFTY = SSSP::DIST_INFINITY;
  galois::do_all(galois::iterate(0ul, graph.size()),
                 [&](size_t i) { oldDist.constructAt(i, INFTY); },
                 galois::no_stats(), galois::loopname("initDistArray"));

  graph.getData(source).dist = 0;

  galois::GReduceLogicalOR changed;
  size_t rounds = 0;

  do {

    ++rounds;
    changed.reset();

    galois::do_all(galois::iterate(graph),
                   [&](const GNode& n) {
                     const auto& sdata = graph.getData(n);

                     if (oldDist[n] > sdata.dist) {

                       oldDist[n] = sdata.dist;
                       changed.update(true);

                       for (auto e : graph.edges(n)) {
                         const auto newDist = sdata.dist + graph.getEdgeData(e);
                         auto dst           = graph.getEdgeDst(e);
                         auto& ddata        = graph.getData(dst);
                         galois::atomicMin(ddata.dist, newDist);
                       }
                     }
                   },
                   galois::steal(), galois::loopname("Update"));

  } while (changed.reduce());

  galois::runtime::reportStat_Single("SSSP-topo", "rounds", rounds);
}

template <typename GType,
          typename Graph = typename GType::Graph,
          typename GNode = typename GType::GNode,
          typename Traits = typename GType::Traits>
void topoTileAlgo(Graph& graph, const GNode& source) {

  using SSSP                 = typename Traits::SSSP;
  using SrcEdgeTile          = typename Traits::SrcEdgeTile;
  using SrcEdgeTileMaker     = typename Traits::SrcEdgeTileMaker;

  galois::InsertBag<SrcEdgeTile> tiles;

  graph.getData(source).dist = 0;

  galois::do_all(galois::iterate(graph),
                 [&](const GNode& n) {
                   SSSP::pushEdgeTiles(
                       tiles, graph, n,
                       SrcEdgeTileMaker{n, SSSP::DIST_INFINITY});
                 },
                 galois::steal(), galois::loopname("MakeTiles"));

  galois::GReduceLogicalOR changed;
  size_t rounds = 0;

  do {
    ++rounds;
    changed.reset();

    galois::do_all(galois::iterate(tiles),
                   [&](SrcEdgeTile& t) {
                     const auto& sdata = graph.getData(t.src);

                     if (t.dist > sdata.dist) {

                       t.dist = sdata.dist;
                       changed.update(true);

                       for (auto e = t.beg; e != t.end; ++e) {
                         const auto newDist = sdata.dist + graph.getEdgeData(e);
                         auto dst           = graph.getEdgeDst(e);
                         auto& ddata        = graph.getData(dst);
                         galois::atomicMin(ddata.dist, newDist);
                       }
                     }
                   },
                   galois::steal(), galois::loopname("Update"));

  } while (changed.reduce());

  galois::runtime::reportStat_Single("SSSP-topo", "rounds", rounds);
}

template <typename GType,
          typename Graph = typename GType::Graph,
          typename GNode = typename GType::GNode>
void reset_graph(Graph& graph, GNode& source){

  using SSSP = typename GType::Traits::SSSP;

  galois::do_all(galois::iterate(graph),
                 [&graph](GNode n) {
                   auto& data = graph.getData(n);
                   data.dist = SSSP::DIST_INFINITY;
		   data.pred = total_pred[data.node];
		   data.fixed = false;
                 });

  graph.getData(source).dist = 0;
}

template <typename GType,
          typename Graph = typename GType::Graph,
          typename GNode = typename GType::GNode,
          typename Traits = typename GType::Traits>
void init_graph(Graph& graph, GNode& source, GNode& report) {

  using SSSP = typename Traits::SSSP;
  using Dist = typename Traits::Dist;
  std::cout << "Reading from file: " << filename << std::endl;
  galois::graphs::readGraph(graph, filename);
  std::cout << "Read " << graph.size() << " nodes, " << graph.sizeEdges()
            << " edges" << std::endl;

  if (startNode >= graph.size() || reportNode >= graph.size()) {
    std::cerr << "failed to set report: " << reportNode
              << " or failed to set source: " << startNode << "\n";
    assert(0);
    abort();
  }

  auto it = graph.begin();
  std::advance(it, startNode);
  source = *it;
  it     = graph.begin();
  std::advance(it, reportNode);
  report = *it;

  size_t approxNodeData = graph.size() * 64;
  // size_t approxEdgeData = graph.sizeEdges() * sizeof(typename
  // Graph::edge_data_type) * 2;
  galois::preAlloc(numThreads +
                   approxNodeData / galois::runtime::pagePoolSize());
  galois::reportPageAlloc("MeminfoPre");

  if (algo == deltaStep || algo == deltaTile || algo == serDelta ||
      algo == serDeltaTile) {
    std::cout << "INFO: Using delta-step of " << (1 << stepShift) << "\n";
    std::cout
        << "WARNING: Performance varies considerably due to delta parameter.\n";
    std::cout
        << "WARNING: Do not expect the default to be good for your graph.\n";
  }

   auto edgeRange = typename GType::Traits::OutEdgeRangeFn{graph};

   struct edgeComp {
     bool operator()( const Dist& lhs, const Dist& rhs ) const {
       return lhs < rhs;
     }
   };

  galois::do_all(galois::iterate(graph),
                 [&](GNode n) {
                   auto& data = graph.getData(n);
                   data.dist = SSSP::DIST_INFINITY;
                   data.min_in_weight = SSSP::DIST_INFINITY;
                   data.node = n;
                   //graph.sortEdgesByEdgeData(n, edgeComp());
                   //                   for (auto& e : edgeRange(n)) {
                   //  std::cout << "Node: " << n << " Edge: " << *e << " dist: " << graph.getEdgeData(e) << std::endl;
                   //}
                 });

  graph.getData(source).dist = 0;
  total_pred.resize(graph.size());
}

struct MatchPathSeparator {
  bool operator()( char ch ) const {
    return ch == '/';
  }
};

std::string basename( std::string const& pathname ) {
    return std::string(
        std::find_if( pathname.rbegin(), pathname.rend(),
                      MatchPathSeparator() ).base(),
        pathname.end() );
}

std::string removeExtension( std::string const& filename ) {
    std::string::const_reverse_iterator
                        pivot
            = std::find( filename.rbegin(), filename.rend(), '.' );
    return pivot == filename.rend()
        ? filename
        : std::string( filename.begin(), pivot.base() - 1 );
}

template <typename GType,
          typename Graph = typename GType::Graph,
          typename GNode = typename GType::GNode,
          typename Traits = typename GType::Traits>
void verify_and_report(Graph& graph, GNode& source, GNode& report, unsigned long exec_time) {
  galois::reportPageAlloc("MeminfoPost");

  std::cout << "Node " << reportNode << " has distance "
            << graph.getData(report).dist << "\n";

  if (!skipVerify) {
    if (Traits::SSSP::verify(graph, source)) {
      std::cout << "Verification successful.\n";
    } else {
      GALOIS_DIE("Verification failed");
    }
  }

  acc::accumulator_set<double, acc::stats<acc::tag::count,
                                          acc::tag::mean,
                                          acc::tag::variance,
                                          acc::tag::max,
                                          acc::tag::min,
                                          acc::tag::median>> stats;

  for (auto& node : graph) {
    auto& node_data = graph.getData(node);
    if (node_data.fixed) stats(duration_cast<microseconds>(node_data.fixed_ts - start).count());
  }

  auto count =  acc::count(stats);
  auto mean =  acc::mean(stats);
  auto median = acc::median(stats);
  auto max =  acc::max(stats);
  auto min = acc::min(stats);
  auto variance =  acc::variance(stats);

  std::cout << std::setprecision(16)
            << "count:    " << count    << '\n'
            << "mean:     " << mean     << '\n'
            << "median:   " << median   << '\n'
            << "max:      " << max      << '\n'
            << "min:      " << min      << '\n'
            << "variance: " << variance << '\n';

    //Auxiliary code for stat collection to CSV file
  std::string resultfile_name = "results.csv";
  std::string graph_name = removeExtension(basename(filename));
  std::ifstream in_data_stream(resultfile_name);
  bool print_header = false;
  if(in_data_stream.peek() == std::ifstream::traits_type::eof())
    print_header = true;
  in_data_stream.close();
  std::ofstream data_stream;
  data_stream.open(resultfile_name, std::ofstream::out | std::ofstream::app);
  if(print_header)
    data_stream << "Algo;Graph_name;Main_time;Count;Mean;Median;max;min;variance;";
  data_stream << std::endl << ALGO_NAMES[algo] << ';' << graph_name << ';' << exec_time << ';' << count << ';' << mean << ';' << median << ';' << max << ';' << min << ';' << variance;
  data_stream.close();

}

int main(int argc, char** argv) {
  using ParGType = GraphType<GraphTypes::ParGraphType>;
  using SerGType = GraphType<GraphTypes::SerGraphType>;

  galois::SharedMemSys G;
  LonestarStart(argc, argv, name, desc, url);

  //skipVerify = true;
  std::cout << "Running " << ALGO_NAMES[algo] << " algorithm" << std::endl;
  galois::StatTimer Tinit;
  galois::StatTimer Tmain;
  unsigned long Init_Time, Main_Time;

  switch (algo) {
    case deltaTile: {
      ParGType::Graph graph;
      ParGType::GNode source, report;
      init_graph<ParGType>(graph, source, report);
      auto edgeRange = ParGType::Traits::OutEdgeRangeFn{graph};
      calc_graph_predecessors(graph, edgeRange);

      start = high_resolution_clock::now();

      Tmain.start();
      deltaStepAlgo<ParGType, ParGType::Traits::SrcEdgeTile>(
          graph, source,
          ParGType::Traits::SrcEdgeTilePushWrap{graph},
          ParGType::Traits::TileRangeFn());
      Tmain.stop();

      verify_and_report<ParGType>(graph, source, report, Tmain.get());
      break;
    }
    case deltaStep: {
      ParGType::Graph graph;
      ParGType::GNode source, report;
      init_graph<ParGType>(graph, source, report);
      auto edgeRange = ParGType::Traits::OutEdgeRangeFn{graph};
      calc_graph_predecessors(graph, edgeRange);

      start = high_resolution_clock::now();

      Tmain.start();
      deltaStepAlgo<ParGType, ParGType::Traits::UpdateRequest>(
          graph, source,
          ParGType::Traits::ReqPushWrap(),
          ParGType::Traits::OutEdgeRangeFn{graph});
      Tmain.stop();

      verify_and_report<ParGType>(graph, source, report, Tmain.get());
      break;
    }
    case serDeltaTile: {
      SerGType::Graph graph;
      SerGType::GNode source, report;
      init_graph<SerGType>(graph, source, report);
      auto edgeRange = SerGType::Traits::OutEdgeRangeFn{graph};
      calc_graph_predecessors(graph, edgeRange);

      start = high_resolution_clock::now();

      Tmain.start();
      serDeltaAlgo<SerGType, SerGType::Traits::SrcEdgeTile>(
          graph, source,
          SerGType::Traits::SrcEdgeTilePushWrap{graph},
          SerGType::Traits::TileRangeFn());
      Tmain.stop();

      verify_and_report<SerGType>(graph, source, report, Tmain.get());
      break;
    }
    case serDelta: {
      SerGType::Graph graph;
      SerGType::GNode source, report;
      init_graph<SerGType>(graph, source, report);
      auto edgeRange = SerGType::Traits::OutEdgeRangeFn{graph};
      calc_graph_predecessors(graph, edgeRange);

      start = high_resolution_clock::now();

      start = high_resolution_clock::now();

      Tmain.start();
      serDeltaAlgo<SerGType, SerGType::Traits::UpdateRequest>(
          graph, source,
          SerGType::Traits::ReqPushWrap(),
          SerGType::Traits::OutEdgeRangeFn{graph});
      Tmain.stop();

      verify_and_report<SerGType>(graph, source, report, Tmain.get());
      break;
    }
    case dijkstraTile: {
      SerGType::Graph graph;
      SerGType::GNode source, report;
      init_graph<SerGType>(graph, source, report);
      auto edgeRange = SerGType::Traits::OutEdgeRangeFn{graph};
      calc_graph_predecessors(graph, edgeRange);

      start = high_resolution_clock::now();

      Tmain.start();
      dijkstraAlgo<SerGType, SerGType::Traits::SrcEdgeTile>(
          graph, source,
          SerGType::Traits::SrcEdgeTilePushWrap{graph},
          SerGType::Traits::TileRangeFn());
      Tmain.stop();

      verify_and_report<SerGType>(graph, source, report, Tmain.get());
      break;
    }
    case dijkstra: {
      SerGType::Graph graph;
      SerGType::GNode source, report;
      init_graph<SerGType>(graph, source, report);
      auto edgeRange = SerGType::Traits::OutEdgeRangeFn{graph};
      calc_graph_predecessors(graph, edgeRange);

      start = high_resolution_clock::now();

      Tmain.start();
      dijkstraAlgo<SerGType, SerGType::Traits::UpdateRequest>(
          graph, source,
          SerGType::Traits::ReqPushWrap(),
          SerGType::Traits::OutEdgeRangeFn{graph});
      Tmain.stop();

      verify_and_report<SerGType>(graph, source, report, Tmain.get());
      break;
    }
    case topo: {
      ParGType::Graph graph;
      ParGType::GNode source, report;
      init_graph<ParGType>(graph, source, report);
      auto edgeRange = ParGType::Traits::OutEdgeRangeFn{graph};
      calc_graph_predecessors(graph, edgeRange);

      start = high_resolution_clock::now();

      Tmain.start();
      topoAlgo<ParGType>(graph, source);
      Tmain.stop();

      verify_and_report<ParGType>(graph, source, report, Tmain.get());
      break;
    }
    case topoTile: {
      ParGType::Graph graph;
      ParGType::GNode source, report;
      init_graph<ParGType>(graph, source, report);
      auto edgeRange = ParGType::Traits::OutEdgeRangeFn{graph};
      calc_graph_predecessors(graph, edgeRange);

      start = high_resolution_clock::now();

      Tmain.start();
      topoTileAlgo<ParGType>(graph, source);
      Tmain.stop();

      verify_and_report<ParGType>(graph, source, report, Tmain.get());
      break;
    }
    case serSP1: {
      SerGType::Graph graph;
      SerGType::GNode source, report;
      init_graph<SerGType>(graph, source, report);
      auto edgeRange = SerGType::Traits::OutEdgeRangeFn{graph};
      calc_graph_predecessors(graph, edgeRange);

      start = high_resolution_clock::now();

      Tmain.start();
      serSP1Algo<SerGType, SerGType::Traits::UpdateRequest>(
          graph, source,
          SerGType::Traits::ReqPushWrap(),
          edgeRange);
      Tmain.stop();

      verify_and_report<SerGType>(graph, source, report, Tmain.get());
      break;
    }
    case serSP2: {
      SerGType::Graph graph;
      SerGType::GNode source, report;
      init_graph<SerGType>(graph, source, report);
      auto edgeRange = SerGType::Traits::OutEdgeRangeFn{graph};
      calc_graph_predecessors(graph, edgeRange);

      start = high_resolution_clock::now();

      Tmain.start();
      serSP2Algo<SerGType, SerGType::Traits::UpdateRequest>(
          graph, source,
          SerGType::Traits::ReqPushWrap(),
          edgeRange);
      Tmain.stop();

      verify_and_report<SerGType>(graph, source, report, Tmain.get());
      break;
    }
    case parSP1: {
      ParGType::Graph graph;
      ParGType::GNode source, report;
      init_graph<ParGType>(graph, source, report);
      auto edgeRange = ParGType::Traits::OutEdgeRangeFn{graph};
      calc_graph_predecessors(graph, edgeRange);

      start = high_resolution_clock::now();

      Tmain.start();
      parSP1VerticesAlgo<ParGType, ParGType::Traits::UpdateRequest>(
          graph, source,
          ParGType::Traits::ReqPushWrap(),
          edgeRange);
      Tmain.stop();

      verify_and_report<ParGType>(graph, source, report, Tmain.get());
      break;
    }
    case parSP2: {
      ParGType::Graph graph;
      ParGType::GNode source, report;
      init_graph<ParGType>(graph, source, report);
      auto edgeRange = ParGType::Traits::OutEdgeRangeFn{graph};
      calc_graph_predecessors(graph, edgeRange);

      start = high_resolution_clock::now();

      Tmain.start();
      parSP2VerticesAlgo<ParGType, ParGType::Traits::UpdateRequest>(
          graph, source,
          ParGType::Traits::ReqPushWrap(),
          edgeRange);
      Tmain.stop();

      //skipVerify = true;
      verify_and_report<ParGType>(graph, source, report, Tmain.get());
      break;
    }
    default:
      std::abort();
  }
  return 0;
}


text:
#ifndef BOOST_MPL_TRANSFORM_HPP_INCLUDED
#define BOOST_MPL_TRANSFORM_HPP_INCLUDED

// Copyright Aleksey Gurtovoy 2000-2004
// Copyright David Abrahams 2003-2004
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//
// See http://www.boost.org/libs/mpl for documentation.

// $Id$
// $Date$
// $Revision$

#include <boost/mpl/fold.hpp>
#include <boost/mpl/reverse_fold.hpp>
#include <boost/mpl/pair_view.hpp>
#include <boost/mpl/is_sequence.hpp>
#include <boost/mpl/eval_if.hpp>
#include <boost/mpl/lambda.hpp>
#include <boost/mpl/bind.hpp>
#include <boost/mpl/or.hpp>
#include <boost/mpl/not.hpp>
#include <boost/mpl/aux_/na.hpp>
#include <boost/mpl/aux_/inserter_algorithm.hpp>

namespace mars_boost {}
namespace boost = mars_boost;
namespace mars_boost {
namespace mpl {

namespace aux {

template<
    typename Seq, typename Op, typename In
>
struct transform1_impl
    : fold<
        Seq, typename In::state,
        bind2 < typename lambda<typename In::operation>::type, _1, bind1 < typename lambda<Op>::type, _2>
>
> {
};

template<
    typename Seq, typename Op, typename In
>
struct reverse_transform1_impl
    : reverse_fold<
        Seq, typename In::state,
        bind2 < typename lambda<typename In::operation>::type, _1, bind1 < typename lambda<Op>::type, _2>
>
> {
};

template<
    typename Seq1, typename Seq2, typename Op, typename In
>
struct transform2_impl
    : fold<
        pair_view < Seq1, Seq2>, typename In::state, bind2<typename lambda<typename In::operation>::type, _1, bind2 <
                                                                                typename lambda<Op>::type,
        bind1 < first<>, _2>, bind1<second<>, _2>
>
>
> {
};

template<
    typename Seq1, typename Seq2, typename Op, typename In
>
struct reverse_transform2_impl
    : reverse_fold<
        pair_view < Seq1, Seq2>,
      typename In::state,
      bind2<typename lambda<typename In::operation>::type, _1, bind2 < typename lambda<Op>::type, bind1 < first<>, _2>,
      bind1<second<>, _2>
>
>
>
{
};

} // namespace aux

BOOST_MPL_AUX_INSERTER_ALGORITHM_DEF(3, transform1)
BOOST_MPL_AUX_INSERTER_ALGORITHM_DEF(4, transform2)

#define AUX778076_TRANSFORM_DEF(name)                                   \
template<                                                               \
      typename BOOST_MPL_AUX_NA_PARAM(Seq1)                             \
    , typename BOOST_MPL_AUX_NA_PARAM(Seq2OrOperation)                  \
    , typename BOOST_MPL_AUX_NA_PARAM(OperationOrInserter)              \
    , typename BOOST_MPL_AUX_NA_PARAM(Inserter)                         \
    >                                                                   \
struct name                                                             \
{                                                                       \
    typedef typename eval_if<                                           \
          or_<                                                          \
              is_na<OperationOrInserter>                                \
            , is_lambda_expression< Seq2OrOperation >                   \
            , not_< is_sequence<Seq2OrOperation> >                      \
            >                                                           \
        , name##1<Seq1,Seq2OrOperation,OperationOrInserter>             \
        , name##2<Seq1,Seq2OrOperation,OperationOrInserter,Inserter>    \
        >::type type;                                                   \
};                                                                      \
BOOST_MPL_AUX_NA_SPEC(4, name)                                          \
/**/

AUX778076_TRANSFORM_DEF(transform)
AUX778076_TRANSFORM_DEF(reverse_transform)

#undef AUX778076_TRANSFORM_DEF

}}

#endif // BOOST_MPL_TRANSFORM_HPP_INCLUDED

ext: hpp

max_stars_repo_name: habbyge/mars

max_issues_repo_name: habbyge/mars

max_forks_repo_name: habbyge/mars


text:
/*
    Lightmetrica - A modern, research-oriented renderer

    Copyright (c) 2015 Hisanari Otsu

    Permission is hereby granted, free of charge, to any person obtaining a copy
    of this software and associated documentation files (the "Software"), to deal
    in the Software without restriction, including without limitation the rights
    to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
    copies of the Software, and to permit persons to whom the Software is
    furnished to do so, subject to the following conditions:

    The above copyright notice and this permission notice shall be included in
    all copies or substantial portions of the Software.

    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
    IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
    FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
    AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
    LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
    OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
    THE SOFTWARE.
*/

#include <lightmetrica/lightmetrica.h>
#include "radiosityutils.h"
#include <thread>
#include <boost/format.hpp>

LM_NAMESPACE_BEGIN

/*!
    \brief Progressive radiosity renderer.

    Implements progressive radiosity algorithm [Cohen et al. 1988].
    Similar to `renderer::radiosity`, this implementation only supports
    the diffues BSDF (`bsdf::diffuse`) and the area light (`light::area`).

    References:
      - [Cohen et al. 1988] A progressive refinement approach to fast radiosity image generation
      - [Cohen & Wallace 1995] Radiosity and realistic image synthesis
      - [Willmott & Heckbert 1997] An empirical comparison of radiosity algorithms
*/
class Renderer_ProgressiveRadiosity final : public Renderer
{
public:

    LM_IMPL_CLASS(Renderer_ProgressiveRadiosity, Renderer);

public:

    LM_IMPL_F(Initialize) = [this](const PropertyNode* prop) -> bool
    {
        subdivLimitArea_ = prop->ChildAs<Float>("subdivlimitarea", 0.1_f);
        wireframe_ = prop->ChildAs<int>("wireframe", 0);
        numIterations_ = prop->ChildAs<long long>("num_iterations", 1000L);
        return true;
    };

    LM_IMPL_F(Render) = [this](const Scene* scene_, Random* initRng, const std::string& outputPath) -> void
    {
        const auto* scene = static_cast<const Scene3*>(scene_);
        auto* film = static_cast<const Sensor*>(scene->GetSensor()->emitter)->GetFilm();

        // --------------------------------------------------------------------------------

        // Create patches
        Patches patches;
        patches.Create(scene, subdivLimitArea_);

        // --------------------------------------------------------------------------------

        #pragma region Solve radiosity equation

        LM_LOG_INFO("Solving radiosity equation");

        const int N = patches.Size();
        std::vector<Vec3> S(N);        // Unshot radiosity
        std::vector<Vec3> B(N);        // Solution

        // Setup emission term
        for (int i = 0; i < N; i++)
        {
            const auto& patch = patches.At(i);
            const auto* light = patch.primitive->light;
            if (!light)
            {
                continue;
            }
            S[i] = B[i] = light->Emittance().ToRGB();
        }

        for (long long iteration = 0; iteration < numIterations_; iteration++)
        {
            // Pick the patch with maximum power
            Float maxPower = 0;
            int maxPowerIndex = 0;
            for (int i = 0; i < N; i++)
            {
                const auto& patch = patches.At(i);
                const auto power = Math::Luminance(S[i]) * patch.Area();
                if (power > maxPower)
                {
                    maxPower = power;
                    maxPowerIndex = i;
                }
            }

            // Shoot the radiosity from the patch
            for (int i = 0; i < N; i++)
            {
                if (i == maxPowerIndex) continue;
                const auto ff = RadiosityUtils::EstimateFormFactor(scene, patches.At(i), patches.At(maxPowerIndex));
                const auto R = patches.At(i).primitive->bsdf->Reflectance().ToRGB();
                const auto deltaRad = S[maxPowerIndex] * ff * R;
                B[i] += deltaRad;
                S[i] += deltaRad;
            }
            S[maxPowerIndex] = Vec3();

            // Progress report
            if (iteration % 100 == 0)
            {
                const double progress = 100.0 * iteration / numIterations_;
                LM_LOG_INPLACE(boost::str(boost::format("Progress: %.1f%%") % progress));
            }
        }

        LM_LOG_INFO("Progress: 100.0%");

        #pragma endregion

        // --------------------------------------------------------------------------------

        #pragma region Rendering (ray casting)

        LM_LOG_INFO("Visualizing result");

        const int width  = film->Width();
        const int height = film->Height();
        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                // Raster position
                Vec2 rasterPos((Float(x) + 0.5_f) / Float(width), (Float(y) + 0.5_f) / Float(height));

                // Position and direction of a ray
                SurfaceGeometry geomE;
                Vec3 wo;
                scene->GetSensor()->emitter->SamplePositionAndDirection(rasterPos, Vec2(), geomE, wo);

                // Setup a ray
                Ray ray = { geomE.p, wo };

                // Intersection query
                Intersection isect;
                if (!scene->Intersect(ray, isect))
                {
                    // No intersection -> black
                    film->SetPixel(x, y, SPD());
                    continue;
                }

                // Compute patch index & visualize the radiosity
                patches.IteratePatches(isect, subdivLimitArea_, [&](size_t patchindex, const Vec2& uv) -> void
                {
                    if (wireframe_)
                    {
                        // Visualize wire frame
                        // Compute minimum distance from each edges
                        const auto mind = Math::Min(uv.x, Math::Min(uv.y, 1_f - uv.x - uv.y));
                        if (mind < 0.05f)
                        {
                            film->SetPixel(x, y, SPD(Math::Abs(Math::Dot(isect.geom.sn, -ray.d))));
                        }
                    }
                    else
                    {
                        film->SetPixel(x, y, SPD(B[patchindex]));
                    }
                });
            }

            if (y % 10 == 0)
            {
                const double progress = 100.0 * y / film->Height();
                LM_LOG_INPLACE(boost::str(boost::format("Progress: %.1f%%") % progress));
            }
        }

        LM_LOG_INFO("Progress: 100.0%");

        #pragma endregion

        // --------------------------------------------------------------------------------

        #pragma region Save image
        {
            LM_LOG_INFO("Saving image");
            LM_LOG_INDENTER();
            film->Save(outputPath);
        }
        #pragma endregion
    };

private:

    Float subdivLimitArea_;
    int wireframe_;
    long long numIterations_;

};

LM_COMPONENT_REGISTER_IMPL(Renderer_ProgressiveRadiosity, "renderer::progressiveradiosity");

LM_NAMESPACE_END


text:
// Copyright (c) 2012, Yahoo! Inc.  All rights reserved.
// Copyrights licensed under the New BSD License. See the accompanying LICENSE file for terms.

#include "ZooKeeper.h"

#include <zookeeper/zookeeper.h> /* for zoo_set_debug_level */

#include <gearbox/core/logger.h>
#include <gearbox/core/Json.h>
#include <gearbox/zookeeper/ZooKeeperClack.h>

#include <log4cxx/basicconfigurator.h>
#include <log4cxx/consoleappender.h>

#include <boost/program_options/variables_map.hpp>
#include <boost/program_options/parsers.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/asio/ip/host_name.hpp>

#include <string>
#include <iostream>
#include <vector>

#include <unistd.h>

namespace opt = boost::program_options;
using namespace Gearbox;

typedef std::vector<std::string> strvec_t;

namespace
{
    void del_recursively(ZooKeeper& zk, const std::string& path)
    {
        // /zookeper* is special and we do not want to be deleting it

        if( path.find("/zookeeper") == 0 ) {
            _WARN("Skipping attempted delete of " << path);
            return;
        }

        strvec_t children;
        zk.children(path, children);

        for (strvec_t::const_iterator it = children.begin(); it != children.end(); ++it) {
            std::string path2 = ZooKeeper::join_paths(path, *it);
            del_recursively(zk, path2);
        }

        zk.del(path);
    }

    void ls_recursively(ZooKeeper& zk, const std::string& path, bool long_fmt, const std::string& indent = "")
    {
        strvec_t children;
        zk.children(path, children);

        for (strvec_t::const_iterator it = children.begin(); it != children.end(); ++it) {
            if (long_fmt) {
                std::cout << ZooKeeper::join_paths(path, *it) << std::endl;
            }
            else {
                std::cout << indent << *it << std::endl;
            }
            std::string path2 = ZooKeeper::join_paths(path, *it);
            ls_recursively(zk, path2, long_fmt, indent + " ");
        }

    }
}

int main(int argc, char **argv)
{
    const std::string usage = "\
gearbox_zkutil [options] get PATH\n\
gearbox_zkutil [options] set [-p] PATH VALUE\n\
gearbox_zkutil [options] set [-p] PATH < VALUE_FILE\n\
gearbox_zkutil [options] ls [-R [-l]] PATH\n\
gearbox_zkutil [options] rm [-R] PATH\n\
gearbox_zkutil [options] stat PATH\n\
gearbox_zkutil [options] ack_success DATUM_PATH TX_ID\n\
gearbox_zkutil [options] ack_fail DATUM_PATH TX_ID MESSAGE\n\
gearbox_zkutil [options] ack_fail DATUM_PATH TX_ID < MESSAGE_FILE\n\
gearbox_zkutil [options] ack_txId DATUM_PATH \n\
\n";

    opt::options_description options("Options");

    try {
        options.add_options()
            ("help,h", "produce this help message")
            ("zookeepers,z", opt::value<std::string>()->default_value("localhost:2181"), "List of ZK servers and ports")
            ("timeout,t", opt::value<int>()->default_value(10000), "ZK receive timeout in milliseconds")
            ("parents,p", "create missing parents with empty node values")
            ("recursive,R", "list (ls) or remove (rm) PATH and all its children [*BE CAREFUL*]")
            ("verbose,v", "enable verbose logging from ZK")
            ("long,l", "with ls -R, show a full path for each znode")
            ;

        opt::variables_map args;
        {
            // The option to receive positional args is hidden from the help output
            opt::options_description options2;
            options2.add(options).add_options()("command", opt::value<strvec_t>(), "Command and its arguments");

            opt::positional_options_description positional;
            positional.add("command", -1);

            opt::store(opt::command_line_parser(argc, argv).options(options2).positional(positional).run(), args);
            opt::notify(args);
        }

        if (args.count("help")) {
            std::cout << usage << options << std::endl;
            return 0;
        }

        if (!args.count("command") || args["command"].as<strvec_t>().empty()) {
            throw opt::error("Please specify a command");
        }
        const strvec_t& cmd = args["command"].as<strvec_t>();

        // make log4cxx shut up about its missing config file
        log4cxx::BasicConfigurator::configure();

        // if there is a ConsoleAppender, make it log to stderr
        {
            log4cxx::AppenderList appenders = log4cxx::Logger::getRootLogger()->getAllAppenders();
            for (log4cxx::AppenderList::iterator it = appenders.begin(); it != appenders.end(); ++it) {
                log4cxx::ConsoleAppender *cap = dynamic_cast<log4cxx::ConsoleAppender *>(&**it);
                if (cap != NULL) {
                    cap->setTarget(log4cxx::ConsoleAppender::getSystemErr());
                    // Necessary for setTarget to have an effect.
                    // The Pool is not used, it could even be *NULL.
                    log4cxx::helpers::Pool p;
                    cap->activateOptions(p);
                }
            }
        }

        if (args.count("verbose")) {
            log4cxx::Logger::getRootLogger()->setLevel(log4cxx::Level::getDebug());
        }
        else {
            log4cxx::Logger::getRootLogger()->setLevel(log4cxx::Level::getError());
            // suppress the overly verbose logging in the ZK client
            zoo_set_debug_level(ZOO_LOG_LEVEL_WARN);
        }

        // check if the comand matches and enforce arg count if it does
        class cmd_is_t {
            const strvec_t& cmd_;
        public:
            cmd_is_t(const strvec_t& cmd) : cmd_(cmd) {}

            bool operator () (const std::string& c, size_t req_args, size_t opt_args = 0)
            {
                if (cmd_.front() == c) {
                    size_t nargs = cmd_.size() - 1;
                    if (nargs < req_args) {
                        std::ostringstream err;
                        err << "Too few args for command '" << c
                            << "', need at least " << (unsigned)req_args;
                        throw opt::error( err.str() );
                    }
                    if (nargs > req_args + opt_args) {
                        std::ostringstream err;
                        err << "Too many args for command '" << c
                            << "', need at most " << (unsigned)(req_args+opt_args);
                        throw opt::error( err.str() );
                    }
                    return true;
                }
                else {
                    return false;
                }
            }
        } cmd_is(cmd);

        if (cmd_is("ack_success", 2)) {
            const std::string datumPath = cmd.at(1);
            size_t found=datumPath.find_last_of("/\\");
            const std::string path = datumPath.substr(0,found);
            const std::string datumKey = datumPath.substr(found+1);

            const std::string& datumTxIdString = cmd.at(2);

            int64_t datumTxId = boost::lexical_cast<int64_t>(datumTxIdString);
            std::string hostName = boost::asio::ip::host_name();
            DatumConsumer dc(args["zookeepers"].as<std::string>(),
                             args["timeout"].as<int>(),
                             hostName,
                             path);
            dc.acknowledgeSuccess(datumKey, datumTxId);
        }
        else if (cmd_is("ack_fail", 2, 1)) {
            const std::string datumPath = cmd.at(1);
            size_t found=datumPath.find_last_of("/\\");
            const std::string path = datumPath.substr(0,found);
            const std::string datumKey = datumPath.substr(found+1);

            const std::string& datumTxIdString = cmd.at(2);

            std::string msg;
            if (cmd.size() == 4) {
                msg = cmd.at(3);
            }
            else {
                // this is probably not what the user intended, so warn them
                if (isatty(0)) {
                    std::cerr << "Please type in the desired value, or Ctrl-C yourself out (stdin is a tty)" << std::endl;
                }

                // load the value from stdin
                std::stringstream ss;
                ss << std::cin.rdbuf();
                msg = ss.str();
            }
            int64_t datumTxId = boost::lexical_cast<int64_t>(datumTxIdString);
            std::string hostName = boost::asio::ip::host_name();
            DatumConsumer dc(args["zookeepers"].as<std::string>(),
                             args["timeout"].as<int>(),
                             hostName,
                             path);
            dc.acknowledgeFailure(datumKey, datumTxId, msg);

        } else{
            ZooKeeper zk(args["zookeepers"].as<std::string>(), args["timeout"].as<int>());

            if (cmd_is("get", 1)) {
                const std::string& path = cmd.at(1);

                std::string data;
                zk.get(path, data);

                // be terminal-friendly, add a trailing line-break if missing
                if (data.empty() || data.at(data.size()-1) != '\n') {
                    data += "\n";
                }

                std::cout << data;
            }
            else if (cmd_is("set", 1, 1)) {
                const std::string& path = cmd.at(1);

                std::string data;
                if (cmd.size() == 3) {
                    data = cmd.at(2);
                }
                else {
                    // this is probably not what the user intended, so warn them
                    if (isatty(0)) {
                        std::cerr << "Please type in the desired value, or Ctrl-C yourself out (stdin is a tty)" << std::endl;
                    }

                    // load the value from stdin
                    std::stringstream ss;
                    ss << std::cin.rdbuf();
                    data = ss.str();
                }

                if (args.count("parents")) {
                    // create the parent path if necessary
                    std::string parent = ZooKeeper::normalize_path(path);
                    size_t slash_pos = parent.rfind('/');
                    if (slash_pos != std::string::npos && slash_pos != 0) {
                        parent.resize(slash_pos);
                        if (!zk.exists(parent)) {
                            zk.createFullPath(parent);
                        }
                    }
                }

                if (!zk.exists(path)) {
                    zk.create(path, data);
                }
                else {
                    zk.set(path, data);
                }
            }
            else if (cmd_is("rm", 1)) {
                const std::string& path = cmd.at(1);
                if (args.count("recursive")) {
                    del_recursively(zk, path);
                }
                else {
                    zk.del(path);
                }
            }
            else if (cmd_is("ls", 1)) {
                const std::string& path = cmd.at(1);

                if (args.count("recursive")) {
                    ls_recursively(zk, path, args.count("long"));
                }
                else {
                    strvec_t children;
                    zk.children(path, children);

                    for (strvec_t::const_iterator it = children.begin(); it != children.end(); ++it) {
                        std::cout << *it << std::endl;
                    }
                }
            }
            else if (cmd_is("stat", 1)) {
                const std::string& path = cmd.at(1);
                ZooKeeper::Stat s = zk.stat(path);
                std::cout << "version = " <<  s.version() << std::endl;
                std::cout << "modTxId = " <<  s.modTxId() << std::endl;
                std::cout << "mtime = " <<  s.mtime() << std::endl;
                std::cout << "ctime = " <<  s.ctime() << std::endl;
                std::cout << "dataLength = " <<  s.dataLength() << std::endl;
                std::cout << "numChildren = " <<  s.numChildren() << std::endl;
            }
            else if (cmd_is("ack_txId", 1)) {
                std::string hostName = boost::asio::ip::host_name();
                const std::string datumPath = cmd.at(1);
                size_t found=datumPath.find_last_of("/\\");
                std::string path = datumPath.substr(0,found);
                const std::string datumKey = datumPath.substr(found+1);

                path.append("/ack/").append(datumKey).append("/").append(hostName);
                std::string data;
                zk.get(path, data);

                Json ackJson;
                ackJson.parse(data);
                const int64_t jsonTxId =  ackJson["txId"].as<int64_t>();
                std::cout << jsonTxId << std::endl;
            }
            else {
                throw opt::error( "Unrecognized command '" + cmd.front() + "'");
            }
        }
        return 0;
    }
    catch (const opt::error& err) {
        // opt::error is thrown for usage errors, by the options parser, or by our code
        std::cerr << usage << options << std::endl << "Usage error: " << err.what() << std::endl;
        return 1;
    }
    catch (const std::exception& exc) {
        std::cerr << "ERROR: " << exc.what() << std::endl;
        return 2;
    }
}

/* Style Settings:
 *
 * Local Variables:
 *   mode: C++
 *   indent-tabs-mode: nil
 *   c-basic-offset: 4
 *   c-set-style: "knr"
 * End:
 * vim:set sw=4 ts=4 sts=4 cindent expandtab cinoptions=(0:
 */

ext: cc

max_stars_repo_name: coryb/gearbox

max_issues_repo_name: coryb/gearbox

max_forks_repo_name: coryb/gearbox