text:
#ifdef STAN_OPENCL
#include <stan/math/prim/mat.hpp>
#include <stan/math/gpu/copy.hpp>
#include <stan/math/gpu/multiply.hpp>
#include <boost/random/mersenne_twister.hpp>
#include <gtest/gtest.h>
#include <algorithm>
#ifdef STAN_OPENCL
boost::random::mt19937 rng;

#define EXPECT_MATRIX_NEAR(A, B, DELTA) \
  for (int i = 0; i < A.size(); i++)    \
    EXPECT_NEAR(A(i), B(i), DELTA);

TEST(MathMatrix, vector_row_vector) {
  stan::math::vector_d v(3);
  stan::math::row_vector_d rv(3);
  stan::math::matrix_gpu v_gpu(v);
  stan::math::matrix_gpu rv_gpu(rv);
  stan::math::matrix_gpu m_gpu(1, 1);
  EXPECT_NO_THROW(m_gpu = rv_gpu * v_gpu);
}

TEST(MathMatrix, one_dim_zero_matrix) {
  stan::math::matrix_d m0(5, 0);
  stan::math::matrix_d m1(0, 3);

  stan::math::matrix_gpu m0_gpu(m0);
  stan::math::matrix_gpu m1_gpu(m1);
  EXPECT_NO_THROW(m0_gpu * m1_gpu);

  EXPECT_NO_THROW(m0_gpu * 2.0);
  EXPECT_NO_THROW(2.0 * m0_gpu);

  EXPECT_NO_THROW(m1_gpu * 2.0);
  EXPECT_NO_THROW(2.0 * m1_gpu);
}

TEST(MathMatrix, zero_result_matrix) {
  stan::math::matrix_d m0(0, 5);
  stan::math::matrix_d m1(5, 0);

  stan::math::matrix_gpu m0_gpu(m0);
  stan::math::matrix_gpu m1_gpu(m1);
  EXPECT_NO_THROW(m0_gpu * m1_gpu);
}

TEST(MathMatrix, zero_size_input_matrix) {
  stan::math::matrix_d m0(0, 0);
  stan::math::matrix_d m1(0, 0);

  stan::math::matrix_gpu m0_gpu(m0);
  stan::math::matrix_gpu m1_gpu(m1);
  EXPECT_NO_THROW(m0_gpu * m1_gpu);

  EXPECT_NO_THROW(m0_gpu * 2.0);
  EXPECT_NO_THROW(2.0 * m0_gpu);
}

TEST(MathMatrix, non_matching_dim_excpetion) {
  stan::math::matrix_d m0(5, 3);
  stan::math::matrix_d m1(2, 6);

  stan::math::matrix_gpu m0_gpu(m0);
  stan::math::matrix_gpu m1_gpu(m1);
  EXPECT_THROW(m0_gpu * m1_gpu, std::invalid_argument);
}

TEST(MathMatrix, multiply_scalar) {
  auto v = stan::math::vector_d::Random(25).eval();
  stan::math::vector_d v_gpu_res(25);
  auto rv = stan::math::row_vector_d::Random(25).eval();
  stan::math::row_vector_d rv_gpu_res(25);
  auto m = stan::math::matrix_d::Random(5, 5).eval();
  stan::math::matrix_d m_gpu_res(5, 5);

  stan::math::matrix_gpu v_gpu(v);
  v_gpu = v_gpu * 2.0;
  stan::math::copy(v_gpu_res, v_gpu);

  stan::math::matrix_gpu rv_gpu(rv);
  rv_gpu = rv_gpu * 2.0;
  stan::math::copy(rv_gpu_res, rv_gpu);

  stan::math::matrix_gpu m_gpu(m);
  m_gpu = m_gpu * 2.0;
  stan::math::copy(m_gpu_res, m_gpu);

  v = v * 2.0;
  rv = rv * 2.0;
  m = m * 2.0;

  EXPECT_MATRIX_NEAR(v, v_gpu_res, 1e-10);
  EXPECT_MATRIX_NEAR(rv, rv_gpu_res, 1e-10);
  EXPECT_MATRIX_NEAR(m, m_gpu_res, 1e-10);
}

TEST(MathMatrix, row_vector_vector) {
  auto v = stan::math::vector_d::Random(5).eval();
  auto rv = stan::math::row_vector_d::Random(5).eval();
  stan::math::matrix_d m0(1, 1);
  stan::math::matrix_d m0_gpu_res(1, 1);
  stan::math::matrix_d m1(5, 5);
  stan::math::matrix_d m1_gpu_res(5, 5);

  m0 = rv * v;
  m1 = v * rv;

  stan::math::matrix_gpu v_gpu(v);
  stan::math::matrix_gpu rv_gpu(rv);
  stan::math::matrix_gpu m0_gpu(1, 1);
  stan::math::matrix_gpu m1_gpu(5, 5);

  m0_gpu = rv_gpu * v_gpu;
  m1_gpu = v_gpu * rv_gpu;
  stan::math::copy(m0_gpu_res, m0_gpu);
  stan::math::copy(m1_gpu_res, m1_gpu);

  EXPECT_MATRIX_NEAR(m0, m0_gpu_res, 1e-10);
  EXPECT_MATRIX_NEAR(m1, m1_gpu_res, 1e-10);
}

TEST(AgradRevMatrix, multiply_small) {
  using stan::math::multiply;
  auto m1 = stan::math::matrix_d::Random(3, 3).eval();
  auto m2 = stan::math::matrix_d::Random(3, 3).eval();
  stan::math::matrix_d m3_gpu_res(3, 3);

  stan::math::matrix_gpu m11(m1);
  stan::math::matrix_gpu m22(m2);

  auto m3 = (m1 * m2).eval();

  auto m33 = m11 * m22;

  stan::math::copy(m3_gpu_res, m33);

  EXPECT_MATRIX_NEAR(m3, m3_gpu_res, 1e-10);
}

TEST(AgradRevMatrix, multiply_big) {
  using stan::math::multiply;
  int size = 512;
  auto m1 = stan::math::matrix_d::Random(size, size).eval();
  auto m2 = stan::math::matrix_d::Random(size, size).eval();
  stan::math::matrix_d m3_gpu_res(size, size);

  stan::math::matrix_gpu m11(m1);
  stan::math::matrix_gpu m22(m2);

  auto m3 = (m1 * m2).eval();

  auto m33 = m11 * m22;

  stan::math::copy(m3_gpu_res, m33);

  EXPECT_MATRIX_NEAR(m3, m3_gpu_res, 1e-10);
}
#endif
#endif

max_stars_repo_name: jrmie/math

max_issues_repo_name: jrmie/math

max_forks_repo_name: jrmie/math


text:
// Copyright 2015-2018 Hans Dembinski
//
// 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)

#include <boost/core/lightweight_test.hpp>
#include <boost/histogram/accumulators/ostream.hpp>
#include <boost/histogram/accumulators/sum.hpp>
#include <boost/histogram/accumulators/weighted_sum.hpp>
#include <boost/histogram/detail/square.hpp>
#include <boost/histogram/weight.hpp>
#include <sstream>
#include "throw_exception.hpp"
#include "utility_str.hpp"

using namespace boost::histogram;
using namespace std::literals;

using w_t = accumulators::weighted_sum<double>;

int main() {
  {
    w_t w;
    BOOST_TEST_EQ(str(w), "weighted_sum(0, 0)"s);
    BOOST_TEST_EQ(str(w, 20, false), "  weighted_sum(0, 0)"s);
    BOOST_TEST_EQ(str(w, 20, true), "weighted_sum(0, 0)  "s);
    BOOST_TEST_EQ(w, w_t{});

    BOOST_TEST_EQ(w, w_t(0));
    BOOST_TEST_NE(w, w_t(1));
    w = w_t(1);
    BOOST_TEST_EQ(w.value(), 1);
    BOOST_TEST_EQ(w.variance(), 1);
    BOOST_TEST_EQ(w, 1);
    BOOST_TEST_NE(w, 2);

    w += weight(2);
    BOOST_TEST_EQ(w.value(), 3);
    BOOST_TEST_EQ(w.variance(), 5);
    BOOST_TEST_EQ(w, w_t(3, 5));
    BOOST_TEST_NE(w, w_t(3));

    w += w_t(1, 2);
    BOOST_TEST_EQ(w.value(), 4);
    BOOST_TEST_EQ(w.variance(), 7);

    // consistency: a weighted counter increased by weight 1 multiplied
    // by 2 must be the same as a weighted counter increased by weight 2
    w_t u(0);
    ++u;
    u *= 2;
    BOOST_TEST_EQ(u, w_t(2, 4));

    w_t v(0);
    v += weight(2);
    BOOST_TEST_EQ(u, v);

    // conversion to RealType
    w_t y(1, 2);
    BOOST_TEST_NE(y, 1);
    BOOST_TEST_EQ(static_cast<double>(y), 1);

    BOOST_TEST_EQ(w_t() += w_t(), w_t());
  }

  // sum nested in weighted_sum
  {
    using s_t = accumulators::weighted_sum<accumulators::sum<double>>;
    s_t w;

    ++w;
    w += weight(1e100);
    ++w;
    w += weight(-1e100);

    BOOST_TEST_EQ(w.value(), 2);
    BOOST_TEST_EQ(w.variance(), 2e200);

    BOOST_TEST_EQ(s_t() += s_t(), s_t());
  }

  // division 1
  {
    w_t a{1, 2};
    w_t b{2, 3};

    auto c = a;
    c /= b;

    BOOST_TEST_EQ(c.value(), 0.5);
    // error propagation for independent a and b:
    // var(c)/c^2 = var(a)/a^2 + var(b)/b^2
    BOOST_TEST_EQ(c.variance() / detail::square(c.value()),
                  a.variance() / detail::square(a.value()) +
                      b.variance() / detail::square(b.value()));
  }

  // division with implicit conversion
  {
    w_t a{1, 2};
    double b = 2;

    auto c = a;
    c /= b;

    BOOST_TEST_EQ(c.value(), 0.5);
    // var(b) = b
    BOOST_TEST_EQ(c.variance() / detail::square(c.value()),
                  a.variance() / detail::square(a.value()) + 1.0 / b);
  }

  return boost::report_errors();
}

ext: cpp

max_stars_repo_name: bazelboost/histogram

max_issues_repo_name: bazelboost/histogram

max_forks_repo_name: bazelboost/histogram


text:
/*
 * Copyright 2019 © Centre Interdisciplinaire de développement en Cartographie des Océans (CIDCO), Tous droits réservés
 */

#ifndef PING_HPP
#define PING_HPP

#include <iostream>
#include <Eigen/Dense>
#include "Attitude.hpp"
#include "Position.hpp"

/*!
 * \brief Ping class
 * \author Guillaume Labbe-Morissette, Jordan McManus, Emile Gagne
 * \date September 14, 2018, 10:10 AM
 */
class Ping {
private:

    /**Time value calculated since January 1970 (micro-second)*/
    uint64_t timestamp; //in microseconds since epoch

    /**Value of the identification of the ping*/
    uint64_t id;

    /**Value of the quality of the ping*/
    uint32_t quality;

    /**Value of the intensity of the ping in decibels*/
    double intensity;

    /**The sound speed value of the surface*/
    double surfaceSoundSpeed;

    /**Time value of transition between two points (micro-second)*/
    double twoWayTravelTime;

    /**Value of the angle that passes along the track (degrees)*/
    double alongTrackAngle; // In degrees, AKA emission angle, alpha, kappa or tilt angle

    /**Value of the angle that passes across the track (degrees)*/
    double acrossTrackAngle; // In degrees, AKA reception angle, beta, zeta, beam angle

    /*Trigonometry is stored to prevent redundant recalculations*/
    /**Sine value of the along track angle*/
    double sA;

    /**Cosine value of the along track angle*/
    double cA;

    /**Sine value of the across track angle*/
    double sB;

    /**Cosine value of the across track angle*/
    double cB;

public:

    /**
     * Create the ping
     *
     * @param microEpoch timestamp value of the ping
     * @param id identification of the ping
     * @param quality quality of the ping
     * @param intensity intensity of the ping
     * @param surfaceSoundSpeed the sound speed of the surface
     * @param twoWayTravelTime time value of the transition between
     * @param alongTrackAngle Angle who pass along the track
     * @param acrossTrackAngle Angle who pass across the track
     */
    Ping(
            uint64_t microEpoch,
            long id,
            uint32_t quality,
            double intensity,

            double surfaceSoundSpeed,
            double twoWayTravelTime,
            double alongTrackAngle,
            double acrossTrackAngle
            ) :
    timestamp(microEpoch),
    id(id),
    quality(quality),
    intensity(intensity),
    surfaceSoundSpeed(surfaceSoundSpeed),
    twoWayTravelTime(twoWayTravelTime),
    alongTrackAngle(alongTrackAngle),
    acrossTrackAngle(acrossTrackAngle),
    sA(sin(alongTrackAngle*D2R)),
    cA(cos(alongTrackAngle*D2R)),
    sB(sin(acrossTrackAngle*D2R)),
    cB(cos(acrossTrackAngle*D2R)) {
    }

    Ping(long id) : id(id), quality(0), intensity(0), alongTrackAngle(0), acrossTrackAngle(0) {
        refresh();
    }

    /** Destroy the ping*/
    ~Ping() {

    }

    void refresh() {
        sA = sin(alongTrackAngle * D2R);
        cA = cos(alongTrackAngle * D2R);
        sB = sin(acrossTrackAngle * D2R);
        cB = cos(acrossTrackAngle * D2R);
    }

    /**Return the across track angle*/
    double getAcrossTrackAngle() {
        return acrossTrackAngle;
    }

    void setAcrossTrackAngle(double acrossAngle) {
        acrossTrackAngle = acrossAngle;
        sB = sin(acrossAngle * D2R);
        cB = cos(acrossAngle * D2R);
    }

    /**Return the along track angle*/
    double getAlongTrackAngle() {
        return alongTrackAngle;
    }

    void setAlongTrackAngle(double alongAngle) {
        alongTrackAngle = alongAngle;
        sA = sin(alongAngle * D2R);
        cA = cos(alongAngle * D2R);
    }

    /**Return the cosine value of the along track angle*/
    double getCA() {
        return cA;
    }

    /**Return the cosine value of the across track angle*/
    double getCB() {
        return cB;
    }

    /**Return the timestamp of the ping*/
    uint64_t getTimestamp() {
        return timestamp;
    }

    /**Return the timestamp of the ping*/
    void setTimestamp(uint64_t t) {
        timestamp = t;
    }

    /**
     * Returns the ID
     * @return ID
     */
    long getId() {
        return id;
    }

    /**
     * Sets the ID
     */
    void setId(long id) {
        id = id;
    }

    /**Return the sine value of the along track angle*/
    double getSA() {
        return sA;
    }

    /**Return the sine value of the across track angle*/
    double getSB() {
        return sB;
    }

    /**Return the sound speed of the surface*/
    double getSurfaceSoundSpeed() {
        return surfaceSoundSpeed;
    }

    /**
     * Set the surface sound speed
     * @param sss Surface Sound Speed
     */
    void setSurfaceSoundSpeed(double sss) {
        surfaceSoundSpeed = sss;
    }

    /**Return the time value of the transition between two points*/
    double getTwoWayTravelTime() {
        return twoWayTravelTime;
    }

    /**
     * Set the two-way travel time
     * @param twtt
     */
    void setTwoWayTravelTime(double twtt) {
        twoWayTravelTime = twtt;
    }

    /**Return the quality of the ping*/
    uint32_t getQuality() {
        return quality;
    }

    /**
     * Set the quality factor
     * @param quality
     */
    void setQuality(uint32_t quality) {
        quality = quality;
    }

    /**Return the intensity of the ping*/
    double getIntensity() {
        return intensity;
    }

    /**
     * Set the backscatter intensity
     * @param intensity
     */
    void setIntensity(double intensity) {
        intensity = intensity;
    }

    static bool sortByTimestamp(Ping & p1, Ping & p2) {
        return p1.getTimestamp() < p2.getTimestamp();
    }

    /**
     * Returns the stream in which this ping will be writen
     *
     * @param os the stream in which to write this ping
     * @param obj the ping to write in the stream
     */
    friend std::ostream& operator<<(std::ostream & os, const Ping & obj) {
        return os <<
                "timestamp: " << obj.timestamp << std::endl <<
                "id: " << obj.id << std::endl <<
                "quality: " << obj.quality << std::endl <<
                "intensity: " << obj.intensity << std::endl <<
                "surfaceSoundSpeed: " << obj.surfaceSoundSpeed << std::endl <<
                "twoWayTravelTime: " << obj.twoWayTravelTime << std::endl <<
                "alongTrackAngle: " << obj.alongTrackAngle << std::endl <<
                "acrossTrackAngle: " << obj.acrossTrackAngle << std::endl;
    }
};

#endif /* PING_HPP */

ext: hpp

max_stars_repo_name: HugoValcourt/MBES-lib

max_issues_repo_name: HugoValcourt/MBES-lib

max_forks_repo_name: HugoValcourt/MBES-lib


text:
#include <boost/python.hpp>
#include <boost/python/def.hpp>
#include <boost/python/module.hpp>

#include <rtamt_stl_library/stl_sample.h>

using namespace boost::python;
using namespace stl_library;

BOOST_PYTHON_MODULE(stl_sample)
{
    class_<Sample>("Sample")
        .def_readwrite("seq", &Sample::seq)
        .def_readwrite("time", &Sample::time)
        .def_readwrite("value", &Sample::value)
        ;
}

max_stars_repo_name: BentleyJOakes/rtamt

max_issues_repo_name: BentleyJOakes/rtamt

max_forks_repo_name: BentleyJOakes/rtamt


text:
#include "data.h"

#include <boost/qvm/vec_access.hpp>

using namespace boost::qvm;

DataOutput::DataOutput(std::string &filename) {
    output_stream.open(filename.c_str());
}

DataOutput::~DataOutput() {
    output_stream.close();
}

void DataOutput::write_bounding_box(BoundingBox *bb) {
    boost::qvm::vec<float, 3> min = bb->get_min();
    boost::qvm::vec<float, 3> max = bb->get_max();
    output_stream << "BOUNDINGBOX " << A<0>(min) << " " << A<1>(min) << " " << A<2>(min) << " "
        << A<0>(max) << " " << A<1>(max) << " " << A<2>(max) << std::endl;
}

void DataOutput::write_datapoint(boost::qvm::vec<float, 3> pos) {
    output_stream << "DATAPOINT " << A<0>(pos) << " " << A<1>(pos) << " " << A<2>(pos) << std::endl;
}

void DataOutput::add_datapoints(Particles &particles) {
    for(int i = 0; i < particles.get_count(); i++)
        write_datapoint(particles.get(i).get_position());
}

void DataOutput::add_octree_bounding_boxes(OctreeNode *parent) {
    // Write the current bounding box
    write_bounding_box(&(parent->get_bounding_box()));

    // Recurse down through children
    for(int i = 0; i < 8; i++) {
        if (parent->get_particle_count() > 1) {
            OctreeNode *child = parent->get_child(i);
            if(child->get_particle_count() > 0)
                add_octree_bounding_boxes(child);
        }
    }
}


text:
/*=============================================================================
  Copyright (c) 2010-2016 Bolero MURAKAMI
  https://github.com/bolero-MURAKAMI/Sprig

  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)
=============================================================================*/
#ifndef SPRIG_VARIANTS_FUNCTIONAL_HPP
#define SPRIG_VARIANTS_FUNCTIONAL_HPP

#include <sprig/config/config.hpp>

#ifdef SPRIG_USING_PRAGMA_ONCE
#	pragma once
#endif	// #ifdef SPRIG_USING_PRAGMA_ONCE

#include <boost/type_traits/remove_pointer.hpp>
#include <boost/type_traits/remove_reference.hpp>
#include <boost/preprocessor/punctuation/comma.hpp>
#include <sprig/type_traits/remove_const_reference.hpp>
#include <sprig/variants/foundation.hpp>

namespace sprig {
	namespace variants {
		namespace functional {
			//
			// SPRIG_VARIANTS_FUNCTIONAL_BINARY_OPERATION_DECL
			//
#define SPRIG_VARIANTS_FUNCTIONAL_BINARY_OPERATION_DECL(NAME, OP) \
			template< \
				typename Arg1, \
				typename Arg2 = Arg1, \
				typename Result = typename sprig::remove_const_reference<Arg1>::type \
			> \
			class NAME : public operator2<Arg1, Arg2, Result> { \
			public: \
				typedef operator2<Arg1, Arg2, Result> operator_type; \
				typedef typename operator_type::result_type result_type; \
				typedef typename operator_type::first_argument_type first_argument_type; \
				typedef typename operator_type::second_argument_type second_argument_type; \
			public: \
				result_type operator()(first_argument_type arg1, second_argument_type arg2) { \
					return arg1 OP arg2; \
				} \
			}
			//
			// SPRIG_VARIANTS_FUNCTIONAL_COMPARISON_OPERATION_DECL
			//
#define SPRIG_VARIANTS_FUNCTIONAL_COMPARISON_OPERATION_DECL(NAME, OP) \
			template< \
				typename Arg1, \
				typename Arg2 = Arg1, \
				typename Result = bool \
			> \
			class NAME : public operator2<Arg1, Arg2, Result> { \
			public: \
				typedef operator2<Arg1, Arg2, Result> operator_type; \
				typedef typename operator_type::result_type result_type; \
				typedef typename operator_type::first_argument_type first_argument_type; \
				typedef typename operator_type::second_argument_type second_argument_type; \
			public: \
				result_type operator()(first_argument_type arg1, second_argument_type arg2) { \
					return arg1 OP arg2; \
				} \
			}
			//
			// SPRIG_VARIANTS_FUNCTIONAL_LOGICAL_BINARY_OPERATION_DECL
			//
#define SPRIG_VARIANTS_FUNCTIONAL_LOGICAL_BINARY_OPERATION_DECL(NAME, OP) \
			SPRIG_VARIANTS_FUNCTIONAL_COMPARISON_OPERATION_DECL(NAME, OP)
			//
			// SPRIG_VARIANTS_FUNCTIONAL_BITWISE_BINARY_OPERATION_DECL
			//
#define SPRIG_VARIANTS_FUNCTIONAL_BITWISE_BINARY_OPERATION_DECL(NAME, OP) \
			SPRIG_VARIANTS_FUNCTIONAL_BINARY_OPERATION_DECL(NAME, OP)
			//
			// SPRIG_VARIANTS_FUNCTIONAL_ASSIGN_OPERATION_DECL
			//
#define SPRIG_VARIANTS_FUNCTIONAL_ASSIGN_OPERATION_DECL(NAME, OP) \
			template< \
				typename Arg1, \
				typename Arg2 = typename boost::remove_reference<Arg1>::type const&, \
				typename Result = Arg1 \
			> \
			class NAME : public operator2<Arg1, Arg2, Result> { \
			public: \
				typedef operator2<Arg1, Arg2, Result> operator_type; \
				typedef typename operator_type::result_type result_type; \
				typedef typename operator_type::first_argument_type first_argument_type; \
				typedef typename operator_type::second_argument_type second_argument_type; \
			public: \
				result_type operator()(first_argument_type arg1, second_argument_type arg2) { \
					return arg1 OP arg2; \
				} \
			}
			//
			// SPRIG_VARIANTS_FUNCTIONAL_UNARY_OPERATION_DECL
			//
#define SPRIG_VARIANTS_FUNCTIONAL_UNARY_OPERATION_DECL(NAME, OP) \
			template< \
				typename Arg1, \
				typename Result = typename sprig::remove_const_reference<Arg1>::type \
			> \
			class NAME : public operator1<Arg1, Result> { \
			public: \
				typedef operator1<Arg1, Result> operator_type; \
				typedef typename operator_type::result_type result_type; \
				typedef typename operator_type::argument_type argument_type; \
			public: \
				result_type operator()(argument_type arg1) { \
					return OP arg1; \
				} \
			}
			//
			// SPRIG_VARIANTS_FUNCTIONAL_LOGICAL_UNARY_OPERATION_DECL
			//
#define SPRIG_VARIANTS_FUNCTIONAL_LOGICAL_UNARY_OPERATION_DECL(NAME, OP) \
			template< \
				typename Arg1, \
				typename Result = bool \
			> \
			class NAME : public operator1<Arg1, Result> { \
			public: \
				typedef operator1<Arg1, Result> operator_type; \
				typedef typename operator_type::result_type result_type; \
				typedef typename operator_type::argument_type argument_type; \
			public: \
				result_type operator()(argument_type arg1) { \
					return OP arg1; \
				} \
			}
			//
			// SPRIG_VARIANTS_FUNCTIONAL_BITWISE_UNARY_OPERATION_DECL
			//
#define SPRIG_VARIANTS_FUNCTIONAL_BITWISE_UNARY_OPERATION_DECL(NAME, OP) \
			SPRIG_VARIANTS_FUNCTIONAL_UNARY_OPERATION_DECL(NAME, OP)
			//
			// SPRIG_VARIANTS_FUNCTIONAL_INCDEC_FRONT_UNARY_OPERATION_DECL
			//
#define SPRIG_VARIANTS_FUNCTIONAL_INCDEC_FRONT_UNARY_OPERATION_DECL(NAME, OP) \
			template< \
				typename Arg1, \
				typename Result = Arg1 \
			> \
			class NAME : public operator1<Arg1, Result> { \
			public: \
				typedef operator1<Arg1, Result> operator_type; \
				typedef typename operator_type::result_type result_type; \
				typedef typename operator_type::argument_type argument_type; \
			public: \
				result_type operator()(argument_type arg1) { \
					return OP arg1; \
				} \
			}
			//
			// SPRIG_VARIANTS_FUNCTIONAL_INDIRECT_OPERATION_DECL
			//
#define SPRIG_VARIANTS_FUNCTIONAL_INDIRECT_OPERATION_DECL(NAME, OP) \
			template< \
				typename Arg1, \
				typename Result = typename boost::remove_pointer<Arg1>::type \
			> \
			class NAME : public operator1<Arg1, Result> { \
			public: \
				typedef operator1<Arg1, Result> operator_type; \
				typedef typename operator_type::result_type result_type; \
				typedef typename operator_type::argument_type argument_type; \
			public: \
				result_type operator()(argument_type arg1) { \
					return OP arg1; \
				} \
			}
			//
			// SPRIG_VARIANTS_FUNCTIONAL_ADDRESS_OPERATION_DECL
			//
#define SPRIG_VARIANTS_FUNCTIONAL_ADDRESS_OPERATION_DECL(NAME, OP) \
			template< \
				typename Arg1, \
				typename Result = typename boost::remove_reference<Arg1>::type*\
			> \
			class NAME : public operator1<Arg1, Result> { \
			public: \
				typedef operator1<Arg1, Result> operator_type; \
				typedef typename operator_type::result_type result_type; \
				typedef typename operator_type::argument_type argument_type; \
			public: \
				result_type operator()(argument_type arg1) { \
					return OP arg1; \
				} \
			}
			//
			// SPRIG_VARIANTS_FUNCTIONAL_INCDEC_BACK_UNARY_OPERATION_DECL
			//
#define SPRIG_VARIANTS_FUNCTIONAL_INCDEC_BACK_UNARY_OPERATION_DECL(NAME, OP) \
			template< \
				typename Arg1, \
				typename Result = typename boost::remove_reference<Arg1>::type\
			> \
			class NAME : public operator1<Arg1, Result> { \
			public: \
				typedef operator1<Arg1, Result> operator_type; \
				typedef typename operator_type::result_type result_type; \
				typedef typename operator_type::argument_type argument_type; \
			public: \
				result_type operator()(argument_type arg1) { \
					return arg1 OP; \
				} \
			}
			//
			// SPRIG_VARIANTS_FUNCTIONAL_COMMA_OPERATION_DECL
			//
#define SPRIG_VARIANTS_FUNCTIONAL_COMMA_OPERATION_DECL(NAME, OP) \
			template< \
				typename Arg1, \
				typename Arg2 = typename sprig::remove_const_reference<Arg1>::type&, \
				typename Result = Arg2 \
			> \
			class NAME : public operator2<Arg1, Arg2, Result> { \
			public: \
				typedef operator2<Arg1, Arg2, Result> operator_type; \
				typedef typename operator_type::result_type result_type; \
				typedef typename operator_type::first_argument_type first_argument_type; \
				typedef typename operator_type::second_argument_type second_argument_type; \
			public: \
				result_type operator()(first_argument_type arg1, second_argument_type arg2) { \
					return arg1 OP arg2; \
				} \
			}
			//
			// SPRIG_VARIANTS_FUNCTIONAL_INDIRECT_ARROW_OPERATION_DECL
			//
#define SPRIG_VARIANTS_FUNCTIONAL_INDIRECT_ARROW_OPERATION_DECL(NAME, OP) \
			template< \
				typename Arg1, \
				typename Arg2 = typename boost::remove_reference<Arg1>::type const&, \
				typename Result = Arg1\
			> \
			class NAME : public operator2<Arg1, Arg2, Result> { \
			public: \
				typedef operator2<Arg1, Arg2, Result> operator_type; \
				typedef typename operator_type::result_type result_type; \
				typedef typename operator_type::first_argument_type first_argument_type; \
				typedef typename operator_type::second_argument_type second_argument_type; \
			public: \
				result_type operator()(first_argument_type arg1, second_argument_type arg2) { \
					return arg1 OP arg2; \
				} \
			}
			//
			// SPRIG_VARIANTS_FUNCTIONAL_SUBSCRIPT_OPERATION_DECL
			//
#define SPRIG_VARIANTS_FUNCTIONAL_SUBSCRIPT_OPERATION_DECL(NAME, OP1, OP2) \
			template< \
				typename Arg1, \
				typename Arg2 = int const, \
				typename Result = typename boost::remove_pointer<typename sprig::remove_const_reference<Arg1>::type>::type& \
			> \
			class NAME : public operator2<Arg1, Arg2, Result> { \
			public: \
				typedef operator2<Arg1, Arg2, Result> operator_type; \
				typedef typename operator_type::result_type result_type; \
				typedef typename operator_type::first_argument_type first_argument_type; \
				typedef typename operator_type::second_argument_type second_argument_type; \
			public: \
				result_type operator()(first_argument_type arg1, second_argument_type arg2) { \
					return arg1 OP1 arg2 OP2; \
				} \
			}
			//
			// binary operations
			//
			SPRIG_VARIANTS_FUNCTIONAL_BINARY_OPERATION_DECL(plus, +);
			SPRIG_VARIANTS_FUNCTIONAL_BINARY_OPERATION_DECL(minus, -);
			SPRIG_VARIANTS_FUNCTIONAL_BINARY_OPERATION_DECL(multiplies, *);
			SPRIG_VARIANTS_FUNCTIONAL_BINARY_OPERATION_DECL(divides, /);
			SPRIG_VARIANTS_FUNCTIONAL_BINARY_OPERATION_DECL(modulus, %);
			//
			// comparison operators
			//
			SPRIG_VARIANTS_FUNCTIONAL_COMPARISON_OPERATION_DECL(equal_to, ==);
			SPRIG_VARIANTS_FUNCTIONAL_COMPARISON_OPERATION_DECL(not_equal_to, !=);
			SPRIG_VARIANTS_FUNCTIONAL_COMPARISON_OPERATION_DECL(greater, >);
			SPRIG_VARIANTS_FUNCTIONAL_COMPARISON_OPERATION_DECL(less, <);
			SPRIG_VARIANTS_FUNCTIONAL_COMPARISON_OPERATION_DECL(greater_equal, >=);
			SPRIG_VARIANTS_FUNCTIONAL_COMPARISON_OPERATION_DECL(less_equal, <=);
			//
			// logical binary operations
			//
			SPRIG_VARIANTS_FUNCTIONAL_LOGICAL_BINARY_OPERATION_DECL(and_, &&);
			SPRIG_VARIANTS_FUNCTIONAL_LOGICAL_BINARY_OPERATION_DECL(or_, ||);
			//
			// bitwise binary operations
			//
			SPRIG_VARIANTS_FUNCTIONAL_BITWISE_BINARY_OPERATION_DECL(shift_left, <<);
			SPRIG_VARIANTS_FUNCTIONAL_BITWISE_BINARY_OPERATION_DECL(shift_right, >>);
			SPRIG_VARIANTS_FUNCTIONAL_BITWISE_BINARY_OPERATION_DECL(bitand_, &);
			SPRIG_VARIANTS_FUNCTIONAL_BITWISE_BINARY_OPERATION_DECL(bitxor_, ^);
			SPRIG_VARIANTS_FUNCTIONAL_BITWISE_BINARY_OPERATION_DECL(bitor_, |);
			//
			// assign operations
			//
			SPRIG_VARIANTS_FUNCTIONAL_ASSIGN_OPERATION_DECL(plus_assign, +=);
			SPRIG_VARIANTS_FUNCTIONAL_ASSIGN_OPERATION_DECL(minus_assign, -=);
			SPRIG_VARIANTS_FUNCTIONAL_ASSIGN_OPERATION_DECL(multiplies_assign, *=);
			SPRIG_VARIANTS_FUNCTIONAL_ASSIGN_OPERATION_DECL(divides_assign, /=);
			SPRIG_VARIANTS_FUNCTIONAL_ASSIGN_OPERATION_DECL(modulus_assign, %=);
			SPRIG_VARIANTS_FUNCTIONAL_ASSIGN_OPERATION_DECL(left_shift_assign, <<=);
			SPRIG_VARIANTS_FUNCTIONAL_ASSIGN_OPERATION_DECL(right_shift_assign, >>=);
			SPRIG_VARIANTS_FUNCTIONAL_ASSIGN_OPERATION_DECL(and_assign, &=);
			SPRIG_VARIANTS_FUNCTIONAL_ASSIGN_OPERATION_DECL(xor_assign, ^=);
			SPRIG_VARIANTS_FUNCTIONAL_ASSIGN_OPERATION_DECL(or_assign, |=);
			//
			// unary operations
			//
			SPRIG_VARIANTS_FUNCTIONAL_UNARY_OPERATION_DECL(posite, +);
			SPRIG_VARIANTS_FUNCTIONAL_UNARY_OPERATION_DECL(negate, -);
			//
			// logical unary operations
			//
			SPRIG_VARIANTS_FUNCTIONAL_LOGICAL_UNARY_OPERATION_DECL(not_, !);
			//
			// bitwise unary operations
			//
			SPRIG_VARIANTS_FUNCTIONAL_BITWISE_UNARY_OPERATION_DECL(bitnot_, ~);
			//
			// increase and decrease front operations
			//
			SPRIG_VARIANTS_FUNCTIONAL_INCDEC_FRONT_UNARY_OPERATION_DECL(increase_front, ++);
			SPRIG_VARIANTS_FUNCTIONAL_INCDEC_FRONT_UNARY_OPERATION_DECL(decrease_front, --);
			//
			// indirect operations
			//
			SPRIG_VARIANTS_FUNCTIONAL_INDIRECT_OPERATION_DECL(indirect, *);
			//
			// address operations
			//
			SPRIG_VARIANTS_FUNCTIONAL_ADDRESS_OPERATION_DECL(address, &);
			//
			// increase and decrease back operations
			//
			SPRIG_VARIANTS_FUNCTIONAL_INCDEC_BACK_UNARY_OPERATION_DECL(increase_back, ++);
			SPRIG_VARIANTS_FUNCTIONAL_INCDEC_BACK_UNARY_OPERATION_DECL(decrease_back, --);
			//
			// comma operations
			//
			SPRIG_VARIANTS_FUNCTIONAL_COMMA_OPERATION_DECL(comma, BOOST_PP_COMMA());
			//
			// indirect arrow operations
			//
			SPRIG_VARIANTS_FUNCTIONAL_INDIRECT_ARROW_OPERATION_DECL(indirect_arrow, ->*);
			//
			// subscript operations
			//
			SPRIG_VARIANTS_FUNCTIONAL_SUBSCRIPT_OPERATION_DECL(subscript, [, ]);
		}	// namespace functional
	}	// namespace variants
}	// namespace sprig

#endif	// #ifndef SPRIG_VARIANTS_FUNCTIONAL_HPP

max_stars_repo_name: bolero-MURAKAMI/Sprig

max_issues_repo_name: bolero-MURAKAMI/Sprig

max_forks_repo_name: bolero-MURAKAMI/Sprig


text:
/*
 * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
 */

#include <sys/socket.h>
#include <sys/types.h>
#if defined(__linux__)
#include <linux/netlink.h>
#include <linux/rtnetlink.h>
#include <linux/sockios.h>
#endif

#include <boost/bind.hpp>
#include <boost/assign/list_of.hpp>

#include <base/logging.h>
#include <db/db.h>
#include <db/db_entry.h>
#include <db/db_table.h>
#include <db/db_table_partition.h>

#include <sandesh/sandesh_trace.h>

#include "ksync_index.h"
#include "ksync_entry.h"
#include "ksync_object.h"
#include "ksync_types.h"

SandeshTraceBufferPtr KSyncErrorTraceBuf(
                      SandeshTraceBufferCreate("KSync Error", 5000));

KSyncObject::FwdRefTree  KSyncObject::fwd_ref_tree_;
KSyncObject::BackRefTree  KSyncObject::back_ref_tree_;
KSyncObjectManager *KSyncObjectManager::singleton_ = NULL;
std::auto_ptr<KSyncEntry> KSyncObjectManager::default_defer_entry_;

typedef std::map<uint32_t, std::string> VrouterErrorDescriptionMap;
VrouterErrorDescriptionMap g_error_description =
                    boost::assign::map_list_of<uint32_t, std::string>
                                (ENOENT, "Entry not present")
                                (EBADF, "Key mismatch")
                                (ENOMEM, "Memory insufficient")
                                (EBUSY, "Object cannot be modified")
                                (EEXIST, "Object already present")
                                (ENODEV, "Object not present")
                                (EINVAL, "Invalid object parameters")
                                (ENOSPC, "Object table full");

// to be used only by test code, for triggering
// stale entry timer callback explicitly
void TestTriggerStaleEntryCleanupCb(KSyncObject *obj) {
    obj->StaleEntryCleanupCb();
}

KSyncObject::KSyncObject(const std::string &name) : need_index_(false), index_table_(),
                         delete_scheduled_(false), stale_entry_tree_(),
                         stale_entry_cleanup_timer_(NULL),
                         stale_entry_cleanup_intvl_(0),
                         stale_entries_per_intvl_(0) {
    KSyncTraceBuf = SandeshTraceBufferCreate(name, 1000);
}

KSyncObject::KSyncObject(const std::string &name, int max_index) :
                         need_index_(true), index_table_(max_index),
                         delete_scheduled_(false), stale_entry_tree_(),
                         stale_entry_cleanup_timer_(NULL),
                         stale_entry_cleanup_intvl_(0),
                         stale_entries_per_intvl_(0) {
    KSyncTraceBuf = SandeshTraceBufferCreate(name, 1000);
}

KSyncObject::~KSyncObject() {
    assert(tree_.size() == 0);
    if (stale_entry_cleanup_timer_ != NULL) {
        TimerManager::DeleteTimer(stale_entry_cleanup_timer_);
    }
}

void KSyncObject::InitStaleEntryCleanup(boost::asio::io_service &ios,
                                        uint32_t cleanup_time,
                                        uint32_t cleanup_intvl,
                                        uint16_t entries_per_intvl) {
    // init should be called only once
    assert(stale_entry_cleanup_timer_ == NULL);
    stale_entry_cleanup_timer_ = TimerManager::CreateTimer(ios,
            "KSync Stale Entry Cleanup Timer",
            TaskScheduler::GetInstance()->GetTaskId("Agent::KSync"), 0);
    stale_entry_cleanup_timer_->Start(cleanup_time,
            boost::bind(&KSyncObject::StaleEntryCleanupCb, this));
    stale_entry_cleanup_intvl_ = cleanup_intvl;
    stale_entries_per_intvl_ = entries_per_intvl;
}

void KSyncObject::Shutdown() {
    assert(fwd_ref_tree_.size() == 0);
    assert(back_ref_tree_.size() == 0);
}

KSyncEntry *KSyncObject::Find(const KSyncEntry *key) {
    Tree::iterator  it = tree_.find(*key);
    if (it != tree_.end()) {
        return it.operator->();
    }

    return NULL;
}

KSyncEntry *KSyncObject::Next(const KSyncEntry *entry) const {
    tbb::recursive_mutex::scoped_lock lock(lock_);
    Tree::const_iterator it;
    if (entry == NULL) {
        it = tree_.begin();
    } else {
        it = tree_.iterator_to(*entry);
        it++;
    }
    if (it != tree_.end()) {
        return const_cast<KSyncEntry *>(it.operator->());
    }
    return NULL;
}
KSyncEntry *KSyncObject::CreateImpl(const KSyncEntry *key) {
    // should not create an entry while scheduled for deletion
    assert(delete_scheduled_ == false);

    KSyncEntry *entry;
    if (need_index_) {
        entry = Alloc(key, index_table_.Alloc());
    } else {
        entry = Alloc(key, KSyncEntry::kInvalidIndex);
    }
    std::pair<Tree::iterator, bool> ret = tree_.insert(*entry);
    if (ret.second == false) {
        // entry with same key already exists in the Ksync tree
        // delete the allocated entry and use the entry available
        // in ksync tree
        delete entry;
        entry = ret.first.operator->();
    } else {
        // add reference only if tree insert for newly allocated
        // entry succeeds, otherwise reference for tree insertion
        // is already accounted for
        intrusive_ptr_add_ref(entry);
    }
    return entry;
}

void KSyncObject::ClearStale(KSyncEntry *entry) {
    // Clear stale marked entry and remove from stale entry tree
    entry->stale_ = false;
    stale_entry_tree_.erase(entry);
}

// Creates a KSync entry. Calling routine sets no_lookup to TRUE when its
// guaranteed that KSync entry is not present (ex: flow)
KSyncEntry *KSyncObject::Create(const KSyncEntry *key, bool no_lookup) {
    tbb::recursive_mutex::scoped_lock lock(lock_);

    KSyncEntry *entry = NULL;
    if (no_lookup == false)
        entry = Find(key);
    if (entry == NULL) {
        entry = CreateImpl(key);
    } else {
        if (entry->stale_) {
            // Clear stale marked entry
            ClearStale(entry);
        } else if (entry->GetState() != KSyncEntry::TEMP && !entry->IsDeleted()) {
            // If entry is already present, it should be in TEMP state
            // or deleted state.
            assert(0);
        }
    }

    NotifyEvent(entry, KSyncEntry::ADD_CHANGE_REQ);
    return entry;
}

KSyncEntry *KSyncObject::Create(const KSyncEntry *key) {
    return Create(key, false);
}

KSyncEntry *KSyncObject::CreateStale(const KSyncEntry *key) {
    // Should not be called without initialising stale entry
    // cleanup InitStaleEntryCleanup
    assert(stale_entry_cleanup_timer_ != NULL);
    tbb::recursive_mutex::scoped_lock lock(lock_);
    KSyncEntry *entry = Find(key);
    if (entry == NULL) {
        entry = CreateImpl(key);
    } else {
        if (entry->GetState() != KSyncEntry::TEMP && !entry->IsDeleted()) {
            // If entry is already present, it should be in TEMP state
            // or deleted state to form a stale entry
            return NULL;
        }
        // cleanup associated DB entry for KSyncDBObject
        // so that DB operation on this KSyncEntry does not happen
        // without re-claiming this entry
        CleanupOnDel(entry);
    }

    // mark the entry stale and add to stale entry tree.
    entry->stale_ = true;
    stale_entry_tree_.insert(entry);

    NotifyEvent(entry, KSyncEntry::ADD_CHANGE_REQ);
    // try starting the timer if not running already
    stale_entry_cleanup_timer_->Start(stale_entry_cleanup_intvl_,
            boost::bind(&KSyncObject::StaleEntryCleanupCb, this));
    return entry;
}

KSyncEntry *KSyncObject::GetReference(const KSyncEntry *key) {
    KSyncEntry *entry = Find(key);

    if (entry != NULL)
        return entry;

    entry = CreateImpl(key);
    entry->SetState(KSyncEntry::TEMP);
    return entry;
}

void KSyncObject::Change(KSyncEntry *entry) {
    SafeNotifyEvent(entry, KSyncEntry::ADD_CHANGE_REQ);
}

void KSyncObject::Delete(KSyncEntry *entry) {
    if (entry->stale_) {
        ClearStale(entry);
    }
    SafeNotifyEvent(entry, KSyncEntry::DEL_REQ);
}

void KSyncObject::ChangeKey(KSyncEntry *entry, uint32_t arg) {
    tbb::recursive_mutex::scoped_lock lock(lock_);
    assert(tree_.erase(*entry) > 0);
    uint32_t old_key = GetKey(entry);
    UpdateKey(entry, arg);
    std::pair<Tree::iterator, bool> ret = tree_.insert(*entry);
    if (ret.second == false) {
        // entry with the same key already exist, to proceed further
        // switch place with the existing entry
        KSyncEntry *current = ret.first.operator->();
        assert(tree_.erase(*current) > 0);
        UpdateKey(current, old_key);
        // following tree insertions should always pass
        assert(tree_.insert(*current).second == true);
        assert(tree_.insert(*entry).second == true);
    }
}

uint32_t KSyncObject::GetKey(KSyncEntry *entry) {
    assert(false);
    return 0;
}

void KSyncObject::FreeInd(KSyncEntry *entry, uint32_t index) {
    assert(tree_.erase(*entry) > 0);
    if (need_index_ == true && index != KSyncEntry::kInvalidIndex) {
        index_table_.Free(index);
    }
    PreFree(entry);
    Free(entry);
}

void KSyncObject::Free(KSyncEntry *entry) {
    delete entry;
}

void KSyncObject::SafeNotifyEvent(KSyncEntry *entry,
                                  KSyncEntry::KSyncEvent event) {
    tbb::recursive_mutex::scoped_lock lock(lock_);
    NotifyEvent(entry, event);
}

///////////////////////////////////////////////////////////////////////////////
// KSyncDBObject routines
///////////////////////////////////////////////////////////////////////////////
KSyncDBObject::KSyncDBObject(const std::string &name) : KSyncObject(name), test_id_(-1) {
    table_ = NULL;
}

KSyncDBObject::KSyncDBObject(const std::string &name,
                             int max_index) : KSyncObject(name, max_index), test_id_(-1) {
    table_ = NULL;
}

KSyncDBObject::KSyncDBObject(const std::string &name,
                             DBTableBase *table) : KSyncObject(name), test_id_(-1) {
    table_ = table;
    id_ = table->Register(boost::bind(&KSyncDBObject::Notify, this, _1, _2));
}

KSyncDBObject::KSyncDBObject(const std::string &name,
                             DBTableBase *table, int max_index)
    : KSyncObject(name, max_index), test_id_(-1) {
    table_ = table;
    id_ = table->Register(boost::bind(&KSyncDBObject::Notify, this, _1, _2));
}

KSyncDBObject::~KSyncDBObject() {
    if (table_) {
        UnregisterDb(table_);
    }
}

void KSyncDBObject::RegisterDb(DBTableBase *table) {
    assert(table_ == NULL);
    table_ = table;
    id_ = table->Register(boost::bind(&KSyncDBObject::Notify, this, _1, _2));
}

void KSyncDBObject::UnregisterDb(DBTableBase *table) {
    assert(table_ == table);
    table_->Unregister(id_);
    id_ = -1;
    table_ = NULL;
}

KSyncDBObject::DBFilterResp KSyncDBObject::DBEntryFilter(
        const DBEntry *entry, const KSyncDBEntry *ksync) {
    // Default accept all
    return DBFilterAccept;
}

void KSyncDBObject::set_test_id(DBTableBase::ListenerId id) {
    test_id_ = id;
}

DBTableBase::ListenerId KSyncDBObject::GetListenerId(DBTableBase *table) {
    assert(table_ == table);
    if (test_id_ != -1) {
        return test_id_;
    }
    return id_;
}

void KSyncDBObject::CleanupOnDel(KSyncEntry *entry) {
    KSyncDBEntry *kentry = static_cast<KSyncDBEntry *>(entry);
    if (kentry->GetDBEntry() != NULL) {
        // when object is created only because of reference it will be in
        // temp state without DB entry, deletion of which doesn't need
        // this cleanup
        kentry->GetDBEntry()->ClearState(table_, id_);
        kentry->SetDBEntry(NULL);
    }

    if (delete_scheduled()) {
        // we are in cleanup process remove all duplicate entries
        while (kentry->dup_entry_list_.empty() == false) {
            // and clear db entry state
            kentry->dup_entry_list_.front()->ClearState(table_, id_);
            kentry->dup_entry_list_.pop_front();
        }
    }
}

// DBTable notification handler.
// Generates events for the KSyncEntry state-machine based DBEntry
// Stores the KSyncEntry allocated as DBEntry-state
void KSyncDBObject::Notify(DBTablePartBase *partition, DBEntryBase *e) {
    tbb::recursive_mutex::scoped_lock lock(lock_);
    DBEntry *entry = static_cast<DBEntry *>(e);
    DBTableBase *table = partition->parent();
    assert(table_ == table);
    KSyncDBEntry *ksync =
        static_cast<KSyncDBEntry *>(entry->GetState(table, id_));
    DBFilterResp resp = DBFilterAccept;

    // cleanup is in-process, ignore All db notifications.
    if (delete_scheduled()) {
        return;
    }

    // Trigger DB Filter callback only for ADD/CHANGE, since we need to handle
    // cleanup for delete anyways.
    if (!entry->IsDeleted()) {
        resp = DBEntryFilter(entry, ksync);
    }

    if (entry->IsDeleted() || resp == DBFilterDelete ||
        resp == DBFilterDelAdd) {
        if (ksync != NULL) {
            // Check if there is any entry present in dup_entry_list
            if (!ksync->dup_entry_list_.empty()) {
                // Check if entry getting deleted is actively associated with
                // Ksync Entry.
                if (entry == ksync->GetDBEntry()) {
                    // clean up db entry state.
                    CleanupOnDel(ksync);
                    ksync->SetDBEntry(ksync->dup_entry_list_.front());
                    ksync->dup_entry_list_.pop_front();

                    // DB entry association changed, trigger re-sync.
                    if (ksync->Sync(ksync->GetDBEntry())) {
                        NotifyEvent(ksync, KSyncEntry::ADD_CHANGE_REQ);
                    }
                } else {
                    // iterate through entries and delete the
                    // corresponding DB ref.
                    KSyncDBEntry::DupEntryList::iterator it_dup;
                    for (it_dup = ksync->dup_entry_list_.begin();
                            it_dup != ksync->dup_entry_list_.end(); ++it_dup) {
                        if (entry == *it_dup)
                            break;
                    }
                    // something bad has happened if we fail to find the entry.
                    assert(it_dup != ksync->dup_entry_list_.end());
                    ksync->dup_entry_list_.erase(it_dup);
                    entry->ClearState(table_, id_);
                }
            } else {
                if (resp == DBFilterDelAdd) {
                    // clean up db entry state, so that other ksync entry can
                    // replace the states appropriately.
                    // cleanup needs to be triggered before notifying delete
                    // after that ksync entry might be already free'd
                    CleanupOnDel(ksync);
                }
                // We may get duplicate delete notification in
                // case of db entry reuse
                // add -> change ->delete(Notify) -> change -> delete(Notify)
                // delete and change gets suppresed as delete and we get
                // a duplicate delete notification
                if (ksync->IsDeleted() == false) {
                    NotifyEvent(ksync, KSyncEntry::DEL_REQ);
                }
            }
        }
        if (resp != DBFilterDelAdd) {
            // return from here except for DBFilterDelAdd case, where
            // ADD needs to be triggered after Delete
            return;
        }
        // reset ksync entry pointer, as ksync and DB entry is already
        // dissassociated
        ksync = NULL;
    }

    if (resp == DBFilterIgnore) {
        // DB filter tells us to ignore this Add/Change.
        return;
    }

    bool need_sync = false;
    if (ksync == NULL) {
        KSyncEntry *key, *found;

        // TODO : Memory is allocated and freed only for lookup. Fix this.
        key = DBToKSyncEntry(entry);
        found = Find(key);
        if (found == NULL) {
            ksync = static_cast<KSyncDBEntry *>(CreateImpl(key));
        } else {
            ksync = static_cast<KSyncDBEntry *>(found);
            if (ksync->stale()) {
                // Clear stale marked entry and remove from stale entry tree
                ClearStale(ksync);
            }
        }
        delete key;
        entry->SetState(table, id_, ksync);
        // Allow reuse of KSync Entry if the previous associated DB Entry
        // is marked deleted. This can happen when Key for OPER DB entry
        // deferes from that used in KSync Object.
        DBEntry *old_db_entry = ksync->GetDBEntry();
        if (old_db_entry != NULL) {
            // cleanup previous state id the old db entry is delete marked.
            if (old_db_entry->IsDeleted()) {
                CleanupOnDel(ksync);
            } else {
                // In case Oper DB and Ksync use different Keys, its
                // possible to have multiple Oper DB entries pointing to
                // same Ksync Entry.
                // add the entry to dup_entry_list and return
                ksync->dup_entry_list_.push_back(entry);
                return;
            }
        }
        ksync->SetDBEntry(entry);
        need_sync = true;
    } else {
        // ignore change on non-associated entry.
        if (entry != ksync->GetDBEntry()) {
            return;
        }
    }

    if (ksync->IsDeleted()) {
        // ksync entry was marked as delete, sync required.
        need_sync = true;
    }

    if (ksync->Sync(entry) || need_sync) {
        NotifyEvent(ksync, KSyncEntry::ADD_CHANGE_REQ);
    }
}

///////////////////////////////////////////////////////////////////////////////
// KSyncEntry routines
///////////////////////////////////////////////////////////////////////////////
bool KSyncEntry::IsResolved() {
    KSyncObject *obj = GetObject();
    if (obj->IsIndexValid() && index_ == kInvalidIndex)
        return false;
    if (IsDataResolved() == false)
        return false;
    return ((state_ >= IN_SYNC) && (state_ < DEL_DEFER_SYNC));
}

std::string KSyncEntry::VrouterErrorToString(uint32_t error) {
    std::map<uint32_t, std::string>::iterator iter =
        g_error_description.find(error);
    if (iter == g_error_description.end())
        return strerror(error);
    return iter->second;
}

std::string KSyncEntry::VrouterError(uint32_t error) const {
    return VrouterErrorToString(error);
}

void KSyncEntry::ErrorHandler(int err, uint32_t seq_no,
                              KSyncEvent event) const {
    if (err == 0) {
        return;
    }
    std::string error_msg = VrouterError(err);
    KSYNC_ERROR(VRouterError, "VRouter operation failed. Error <", err,
                ":", error_msg, ">. Object <", ToString(),
                ">. Operation <", AckOperationString(event),
                ">. Message number :", seq_no);

    std::stringstream sstr;
    sstr << "VRouter operation failed. Error <" << err << ":" << error_msg <<
            ">. Object <" << ToString() << ">. Operation <" <<
            AckOperationString(event) << ">. Message number :" << seq_no;
    KSYNC_ERROR_TRACE(Trace, sstr.str().c_str());
    LOG(ERROR, sstr.str().c_str());
}

std::string KSyncEntry::AckOperationString(KSyncEvent event) const {
    switch(event) {
    case ADD_ACK:
        return "Addition";

    case CHANGE_ACK:
        return "Change";

    case DEL_ACK:
        return "Deletion";

    default:
        // AckOperationString should track only acks, if something else is
        // passed convert it to EventString
        return EventString(event);
    }
}

std::string KSyncEntry::StateString() const {
    std::stringstream str;

    switch (state_) {
        case INIT:
            str << "Init";
            break;

        case TEMP:
            str << "Temp";
            break;

        case ADD_DEFER:
            str << "Add defer";
            break;

        case CHANGE_DEFER:
            str << "Change defer";
            break;

        case IN_SYNC:
            str << "In sync";
            break;

        case SYNC_WAIT:
            str << "Sync wait";
            break;

        case NEED_SYNC:
            str << "Need sync";
            break;

        case DEL_DEFER_SYNC:
            str << "Delete defer sync";
            break;

        case DEL_DEFER_REF:
            str << "Delete pending due to reference";
            break;

        case DEL_DEFER_DEL_ACK:
            str << "Delete pending due to Delete ack wait";
            break;

        case DEL_ACK_WAIT:
            str << "Delete ack wait";
            break;

        case RENEW_WAIT:
            str << "Renew wait";
            break;

        case FREE_WAIT:
            str << "Free wait";
            break;
    }

    if (stale_) {
        str << " (Stale entry) ";
    }

    str << '(' << state_ << ')';
    str << '(' << refcount_ << ')';
    return str.str();
}

std::string KSyncEntry::EventString(KSyncEvent event) const {
    std::stringstream str;
    switch (event) {
    case ADD_CHANGE_REQ:
        str << "Add/Change request";
        break;

    case ADD_ACK:
        str << "Add Ack";
        break;

    case CHANGE_ACK:
        str << "Change ack";
        break;

    case DEL_REQ:
        str << "Delete request";
        break;

    case DEL_ADD_REQ:
        str << "Delete followed by Add request";
        break;

    case DEL_ACK:
        str << "Delete ack";
        break;

    case RE_EVAL:
        str << "Re-evaluate";
        break;

    case INT_PTR_REL:
        str << "Reference release";
        break;
    case INVALID:
        str << "Invalid";
        break;
    }
    str << '(' << event << ')';
    return str.str();
}

void intrusive_ptr_add_ref(KSyncEntry *p) {
    p->refcount_++;
};

// KSync adds a reference to object when its created.
// Delete the object if reference falls to 1 and either
// (i) delete was deferred due to refcount or
// (ii) the ksync entry is in TEMP state.
void intrusive_ptr_release(KSyncEntry *p) {
    if (--p->refcount_ == 1) {
        KSyncObject *obj = p->GetObject();
        switch(p->state_) {
            case KSyncEntry::TEMP:
            // FALLTHRU
            case KSyncEntry::DEL_DEFER_REF:
                obj->SafeNotifyEvent(p, KSyncEntry::INT_PTR_REL);
                break;
            default:
                break;
        }
    }
}

///////////////////////////////////////////////////////////////////////////////
// KSyncEntry state machine.
//
// Brief description of States:
//
// INIT         : KSyncEntry created. No events notified to the object yet
// TEMP         : Temporary object created either due to reference or on
//                process restart.
//                Ex: Obj-A refers to Obj-B. If Obj-B is not present when Obj-A
//                    is to be sent, then Obj-B is created in TEMP state
//
// ADD_DEFER    : Object deferred since it has some unmet constraints.
//                Ex: Obj-A refers to Obj-B. Obj-B is not yet added to kernel.
//                    Obj-A will get to ADD_DEFER state
//                    Obj-A goes into BackRefTree for Obj-B.
//                    Creation of Obj-B will take Obj-A out of this state
// CHANGE_DEFER : Object already added to kernel, subsequent change deferred
//                since it has some unmet constraints.
//                Ex: Obj-A refers to Obj-B. Obj-B is not yet added to kernel.
//                    Obj-A will get to ADD_DEFER state
//                    Obj-A goes into BackRefTree for Obj-B.
//                    Add of Obj-B will take Obj-A out of this state
// IN_SYNC      : Object in-sync with kernel
// SYNC_WAIT    : Add or Change sent to kernel. Waiting for ACK from Kernel
// NEED_SYNC    : Object out-of-sync with kernel. Need to send a change message
//                to sync kernel state
// DEL_DEFER_SYNC:Object deleted when waiting for ACK from kernel. Delete must
//                be sent to kernel on getting ACK
// DEL_DEFER_REF: Object deleted with pending references . Delete must be sent
//                to kernel when all pending references goes away.
// DEL_DEFER_DEL_ACK: Object delete with pending delete ack wait, Delete
//                needs to be sent after receiving a del ACK.
// DEL_ACK_WAIT : Delete sent to Kernel. Waiting for ACK from kernel.
//                Can get renewed if there is request to ADD in this case
// RENEW_WAIT   : Object being renewed. Waiting for ACK of delete to renew the
//                object
// FREE_WAIT    : Object marked to be freed at the end of this function call.
//                Can only be a temporary state
//
// Brief description of Events:
// ADD_CHANGE_REQ   : Request to Add or Change an entry
// ADD_ACK,         : Ack from kernel for ADD request
// CHANGE_ACK       : Ack from kernel for CHANGE request
// DEL_REQ          : Request to DEL an entry
// DEL_ADD_REQ      : Request to DEL an entry followed by ADD for the same
// DEL_ACK          : Ack from kernel for DEL request
// RE_EVAL          : Event to re-evaluate dependencies.
//                    Ex: If Obj-A is added into Obj-B back-ref tree
//                        When Obj-B is created, RE_EVAL is sent to Obj-A
///////////////////////////////////////////////////////////////////////////////

// Utility function to handle Add of KSyncEntry.
// If operation is complete, move state to IN_SYNC. Else move to SYNC_WAIT
KSyncEntry::KSyncState KSyncSM_Add(KSyncObject *obj, KSyncEntry *entry) {
    KSyncEntry *dep;
    if ((dep = entry->UnresolvedReference()) != NULL) {
        obj->BackRefAdd(entry, dep);
        return KSyncEntry::ADD_DEFER;
    }

    entry->SetSeen();
    if (entry->Add()) {
        return KSyncEntry::IN_SYNC;
    } else {
        return KSyncEntry::SYNC_WAIT;
    }
}

// Utility function to handle Change of KSyncEntry.
// If operation is complete, move state to IN_SYNC. Else move to SYNC_WAIT
KSyncEntry::KSyncState KSyncSM_Change(KSyncObject *obj, KSyncEntry *entry) {
    KSyncEntry *dep;

    assert(entry->Seen());
    if ((dep = entry->UnresolvedReference()) != NULL) {
        obj->BackRefAdd(entry, dep);
        return KSyncEntry::CHANGE_DEFER;
    }

    if (entry->Change()) {
        return KSyncEntry::IN_SYNC;
    } else {
        return KSyncEntry::SYNC_WAIT;
    }
}

// Utility function to handle Delete of KSyncEntry.
// If there are more references to the object, then move it to DEL_DEFER
// state. Object will be deleted when all references drop. If object is
// still not seen by Kernel yet we don't have to delete it.
//
// If operation is complete, move state to IN_SYNC. Else move to SYNC_WAIT
KSyncEntry::KSyncState KSyncSM_Delete(KSyncEntry *entry) {
    if (entry->GetRefCount() > 1) {
        return KSyncEntry::DEL_DEFER_REF;
    }

    assert(entry->GetRefCount() == 1);
    if (!entry->Seen() && entry->AllowDeleteStateComp()) {
        return KSyncEntry::FREE_WAIT;
    }
    if (entry->Delete()) {
        return KSyncEntry::FREE_WAIT;
    } else {
        return KSyncEntry::DEL_ACK_WAIT;
    }
}

// Utility function to handle Delete followed by ADD of KSyncEntry.
// delete is triggered irrespective of the references to the object
// followed by ADD of the object
//
// If operation is complete, move state to IN_SYNC. Else move to SYNC_WAIT
KSyncEntry::KSyncState KSyncSM_DeleteAdd(KSyncObject *obj, KSyncEntry *entry) {
    // DeleteAdd operation is not supported/defined for stale entries
    // when such an operation is required for stale entry, it must be
    // sufficient to trigger only a delete and let Add happen when
    // entry is ready to become non-stale
    assert(!entry->stale());

    // NOTE this API doesnot support managing references for delete trigger
    if (entry->Seen() || !entry->AllowDeleteStateComp()) {
        if (!entry->Delete()) {
            // move to renew wait to trigger Add on DEL_ACK
            return KSyncEntry::RENEW_WAIT;
        }
    }

    return KSyncSM_Add(obj, entry);
}

//
//
// ADD_CHANGE_REQ :
//      If entry has unresolved references, move it to ADD_DEFER
//      Else, send ADD message and move to SYNC_WAIT state
//
// No other events are expected in this state
KSyncEntry::KSyncState KSyncSM_Init(KSyncObject *obj, KSyncEntry *entry,
                                    KSyncEntry::KSyncEvent event) {
    KSyncEntry::KSyncState state = KSyncEntry::INIT;

    assert(entry->GetRefCount());
    switch (event) {
    case KSyncEntry::ADD_CHANGE_REQ:
        state = KSyncSM_Add(obj, entry);
        break;

    default:
        assert(0);
        break;
    }

    return state;
}

// ADD_CHANGE_REQ :
//      ADD_CHANGE_REQ event for an entry in TEMP state.
//      If entry has unresolved references, move it to ADD_DEFER
//      Else, send ADD message and move to SYNC_WAIT state
//
// DEL_REQ :
//      DEL_REQ event for an entry in TEMP state. Can happen only when reference
//      for the TEMP entry is dropped
//
//      Explicit DEL_REQ event is not expected. This is enforced by checking
//      ref-count
//
//      Event notified when refcount for object goes to 1 In TEMP state.
//      Entry not sent to kernel, so dont send delete message
//      Delete object in this state
//
KSyncEntry::KSyncState KSyncSM_Temp(KSyncObject *obj, KSyncEntry *entry,
                                    KSyncEntry::KSyncEvent event) {
    KSyncEntry::KSyncState state = KSyncEntry::TEMP;

    assert(entry->GetRefCount());
    switch (event) {
    case KSyncEntry::ADD_CHANGE_REQ:
    case KSyncEntry::DEL_ADD_REQ:
        state = KSyncSM_Add(obj, entry);
        break;

    case KSyncEntry::INT_PTR_REL:
    case KSyncEntry::DEL_REQ:
        if (entry->GetRefCount() == 1) {
            state = KSyncEntry::FREE_WAIT;
        }
        break;

    default:
        assert(0);
        break;
    }

    return state;
}

// ADD_CHANGE_REQ :
//  ADD_CHANGE_REQ event for an entry in ADD_DEFER state.
//  Remove the old dependency constraint.
//  Re-evaluate to see if there are any further unmet dependencies
//
// RE_EVAL:
//  Triggred from back-ref tree when KSyncEntry waited on is added to Kernel
//  Entry would already be removed from backref tree
//  Re-evaluate to see if there are any further unmet dependencies
//
// DEL_REQ :
//  Delete when entry is not yet added to kernel. Dont delete entry. Move state
//  based on ref-count
KSyncEntry::KSyncState KSyncSM_AddDefer(KSyncObject *obj, KSyncEntry *entry,
                                        KSyncEntry::KSyncEvent event) {
    KSyncEntry::KSyncState state = KSyncEntry::ADD_DEFER;

    assert(entry->GetRefCount());
    switch (event) {
    case KSyncEntry::ADD_CHANGE_REQ:
        obj->BackRefDel(entry);
        // FALLTHRU
    case KSyncEntry::RE_EVAL:
        state = KSyncSM_Add(obj, entry);
        break;

    // Remove any back-ref entry
    // Free entry if there are no more references. Else wait in TEMP
    // state for either release of reference or for movement to different
    // state.
    case KSyncEntry::DEL_REQ:
        obj->BackRefDel(entry);
        if (entry->AllowDeleteStateComp() == false) {
            state = KSyncSM_Delete(entry);
        } else if (entry->GetRefCount() > 1) {
            state = KSyncEntry::TEMP;
        } else {
            state = KSyncEntry::FREE_WAIT;
        }
        break;

    case KSyncEntry::DEL_ADD_REQ:
        obj->BackRefDel(entry);
        state = KSyncSM_DeleteAdd(obj, entry);
        break;

    case KSyncEntry::INT_PTR_REL:
        break;

    default:
        assert(0);
        break;
    }

    return state;
}

// ADD_CHANGE_REQ :
//  ADD_CHANGE_REQ event for an entry in CHANGE_DEFER state.
//  Remove the old dependency constraint.
//  Re-evaluate to see if there are any further unmet dependencies
//
// RE_EVAL:
//  Triggred from back-ref tree when KSyncEntry waited on is added to Kernel
//  Entry would already be removed from backref tree
//  Re-evaluate to see if there are any further unmet dependencies
//
// DEL_REQ :
//  Move state based on ref-count.
KSyncEntry::KSyncState KSyncSM_ChangeDefer(KSyncObject *obj, KSyncEntry *entry,
                                           KSyncEntry::KSyncEvent event) {
    KSyncEntry::KSyncState state = KSyncEntry::CHANGE_DEFER;

    assert(entry->GetRefCount());
    switch (event) {
    case KSyncEntry::ADD_CHANGE_REQ:
        obj->BackRefDel(entry);
        // FALLTHRU
    case KSyncEntry::RE_EVAL:
        state = KSyncSM_Change(obj, entry);
        break;

    // Remove any back-ref entry and process delete
    case KSyncEntry::DEL_REQ:
        obj->BackRefDel(entry);
        state = KSyncSM_Delete(entry);
        break;

    case KSyncEntry::DEL_ADD_REQ:
        obj->BackRefDel(entry);
        state = KSyncSM_DeleteAdd(obj, entry);
        break;

    case KSyncEntry::INT_PTR_REL:
        break;

    default:
        assert(0);
        break;
    }

    return state;
}

// Object state IN-SYNC with kernel
//
// ADD_CHANGE_REQ :
// Invoke Change on the object
//
// DEL_REQ :
//  Delete of entry that is already added to kernel.
KSyncEntry::KSyncState KSyncSM_InSync(KSyncObject *obj, KSyncEntry *entry,
                                      KSyncEntry::KSyncEvent event) {
    KSyncEntry::KSyncState state = KSyncEntry::IN_SYNC;

    assert(entry->GetRefCount());
    switch (event) {
    case KSyncEntry::ADD_CHANGE_REQ:
        state = KSyncSM_Change(obj, entry);
        break;

    case KSyncEntry::DEL_REQ:
        state = KSyncSM_Delete(entry);
        break;

    case KSyncEntry::DEL_ADD_REQ:
        state = KSyncSM_DeleteAdd(obj, entry);
        break;

    case KSyncEntry::INT_PTR_REL:
        break;

    default:
        assert(0);
        break;
    }

    return state;
}

// Entry waiting on ACK or Add or Change
// If event is change request, move to NEED_SYNC
// If event is delete request, move to DEL_DEFER for references to drop
KSyncEntry::KSyncState KSyncSM_SyncWait(KSyncObject *obj, KSyncEntry *entry,
                                        KSyncEntry::KSyncEvent event) {
    KSyncEntry::KSyncState state = KSyncEntry::SYNC_WAIT;

    assert(entry->GetRefCount());
    switch (event) {
    case KSyncEntry::ADD_CHANGE_REQ:
        state = KSyncEntry::NEED_SYNC;
        break;

    case KSyncEntry::ADD_ACK:
    case KSyncEntry::CHANGE_ACK:
        if (entry->del_add_pending()) {
            // del_add_pending trigger DeleteAdd
            entry->set_del_add_pending(false);
            state = KSyncSM_DeleteAdd(obj, entry);
        } else {
            state = KSyncEntry::IN_SYNC;
        }
        break;

    case KSyncEntry::DEL_REQ:
        state = KSyncEntry::DEL_DEFER_SYNC;
        entry->set_del_add_pending(false);
        break;

    case KSyncEntry::DEL_ADD_REQ:
        // entry is waiting for Ack, mark del_add_pending flag
        // to trigger DeleteAdd on receiving Ack
        entry->set_del_add_pending(true);
        break;

    case KSyncEntry::INT_PTR_REL:
        break;

    default:
        assert(0);
        break;
    }

    return state;
}

// NEED_SYNC state means object was modified while waiting for ACK
KSyncEntry::KSyncState KSyncSM_NeedSync(KSyncObject *obj, KSyncEntry *entry,
                                        KSyncEntry::KSyncEvent event) {
    KSyncEntry::KSyncState state = KSyncEntry::NEED_SYNC;

    assert(entry->GetRefCount());
    switch (event) {
    // Continue in NEED_SYNC state on change
    case KSyncEntry::ADD_CHANGE_REQ:
        break;

    // Wait for ACK to arrive in DEL_DEFER_SYNC state
    case KSyncEntry::DEL_REQ:
        state = KSyncEntry::DEL_DEFER_SYNC;
        entry->set_del_add_pending(false);
        break;

    case KSyncEntry::DEL_ADD_REQ:
        // entry is waiting for Ack, mark del_add_pending flag
        // to trigger DeleteAdd on receiving Ack
        entry->set_del_add_pending(true);
        break;

    // Try to resend on getting ACK of pending operation
    case KSyncEntry::ADD_ACK:
    case KSyncEntry::CHANGE_ACK:
        if (entry->del_add_pending()) {
            // del_add_pending trigger DeleteAdd
            entry->set_del_add_pending(false);
            state = KSyncSM_DeleteAdd(obj, entry);
        } else {
            state = KSyncSM_Change(obj, entry);
        }
        break;

    case KSyncEntry::INT_PTR_REL:
        break;

    default:
        assert(0);
        break;
    }

    return state;
}

// Object waiting for DELETE to be sent.
// ADD_CHANGE_REQ will result in renew of object. Send only a Change
// On ADD/CHANGE ACK, try sending delete
KSyncEntry::KSyncState KSyncSM_DelPending_Sync(KSyncObject *obj,
                                               KSyncEntry *entry,
                                               KSyncEntry::KSyncEvent event) {
    KSyncEntry::KSyncState state = KSyncEntry::DEL_DEFER_SYNC;

    assert(entry->GetRefCount());
    switch (event) {
    case KSyncEntry::ADD_CHANGE_REQ:
        state = KSyncEntry::NEED_SYNC;
        break;

    case KSyncEntry::DEL_ADD_REQ:
        // entry is waiting for Ack, mark del_add_pending flag
        // to trigger DeleteAdd on receiving Ack
        entry->set_del_add_pending(true);
        state = KSyncEntry::NEED_SYNC;
        break;

    case KSyncEntry::ADD_ACK:
    case KSyncEntry::CHANGE_ACK:
        state = KSyncSM_Delete(entry);
        break;

    case KSyncEntry::INT_PTR_REL:
        break;

    default:
        assert(0);
        break;
    }

    return state;
}

// Object waiting for DELETE to be sent.
// ADD_CHANGE_REQ will result in renew of object. Send only a Change
// On ADD/CHANGE ACK, try sending delete
KSyncEntry::KSyncState KSyncSM_DelPending_Ref(KSyncObject *obj,
                                              KSyncEntry *entry,
                                              KSyncEntry::KSyncEvent event) {
    KSyncEntry::KSyncState state = KSyncEntry::DEL_DEFER_REF;

    assert(entry->GetRefCount());
    switch (event) {
    case KSyncEntry::ADD_CHANGE_REQ:
        if (!entry->Seen()) {
            // Trigger Add if entry was not seen earlier
            state = KSyncSM_Add(obj, entry);
        } else {
            state = KSyncSM_Change(obj, entry);
        }
        break;

    case KSyncEntry::INT_PTR_REL:
    case KSyncEntry::DEL_REQ:
        assert(entry->GetRefCount()== 1);
        state = KSyncSM_Delete(entry);
        break;

    case KSyncEntry::DEL_ADD_REQ:
        state = KSyncSM_DeleteAdd(obj, entry);
        break;

    default:
        assert(0);
        break;
    }

    return state;
}

// Object waiting for DELETE to be sent.
// ADD_CHANGE_REQ will result in renew of object. Send only a Change
// On DEL ACK, try sending delete
KSyncEntry::KSyncState KSyncSM_DelPending_DelAck(KSyncObject *obj,
                                                 KSyncEntry *entry,
                                                 KSyncEntry::KSyncEvent event) {
    KSyncEntry::KSyncState state = KSyncEntry::DEL_DEFER_DEL_ACK;

    assert(entry->GetRefCount());
    assert(entry->AllowDeleteStateComp() == false);

    switch (event) {
    case KSyncEntry::ADD_CHANGE_REQ:
        state = KSyncEntry::RENEW_WAIT;
        entry->set_del_add_pending(false);
        break;

    case KSyncEntry::DEL_ACK:
        if (entry->del_add_pending()) {
            // del_add_pending trigger DeleteAdd
            entry->set_del_add_pending(false);
            state = KSyncSM_DeleteAdd(obj, entry);
        } else {
            state = KSyncSM_Delete(entry);
        }
        break;

    case KSyncEntry::DEL_ADD_REQ:
        // entry is waiting for Ack, mark del_add_pending flag
        // to trigger DeleteAdd on receiving Ack
        entry->set_del_add_pending(true);
        break;

    case KSyncEntry::INT_PTR_REL:
        break;

    default:
        assert(0);
        break;
    }

    return state;
}

// Object waiting for ACK of DELETE sent earlier
// ADD_CHANGE_REQ will result in renew of object. TODO: This is TBD
KSyncEntry::KSyncState KSyncSM_DelAckWait(KSyncObject *obj, KSyncEntry *entry,
                                          KSyncEntry::KSyncEvent event) {
    KSyncEntry::KSyncState state = KSyncEntry::DEL_ACK_WAIT;

    assert(entry->GetRefCount());
    switch (event) {
    case KSyncEntry::ADD_CHANGE_REQ:
        state = KSyncEntry::RENEW_WAIT;
        entry->set_del_add_pending(false);
        break;

    case KSyncEntry::DEL_ACK:
        if (entry->del_add_pending()) {
            // del_add_pending trigger DeleteAdd
            entry->set_del_add_pending(false);
            state = KSyncSM_DeleteAdd(obj, entry);
        } else {
            if (entry->GetRefCount() > 1) {
                state = KSyncEntry::TEMP;
            } else {
                state = KSyncEntry::FREE_WAIT;
            }
        }
        break;

    case KSyncEntry::DEL_ADD_REQ:
        // entry is waiting for Ack, mark del_add_pending flag
        // to trigger DeleteAdd on receiving Ack
        entry->set_del_add_pending(true);
        break;

    case KSyncEntry::INT_PTR_REL:
        break;

    default:
        assert(0);
        break;
    }

    return state;
}

// TODO: Object renewal. This is not yet handled
KSyncEntry::KSyncState KSyncSM_RenewWait(KSyncObject *obj, KSyncEntry *entry,
                                         KSyncEntry::KSyncEvent event) {
    KSyncEntry::KSyncState state = KSyncEntry::RENEW_WAIT;

    assert(entry->GetRefCount());
    switch (event) {
    case KSyncEntry::ADD_CHANGE_REQ:
        entry->set_del_add_pending(false);
        break;

    case KSyncEntry::DEL_REQ:
        entry->set_del_add_pending(false);
        if (entry->AllowDeleteStateComp()) {
            state = KSyncEntry::DEL_ACK_WAIT;
        } else {
            state = KSyncEntry::DEL_DEFER_DEL_ACK;
        }
        break;

    case KSyncEntry::DEL_ADD_REQ:
        // entry is waiting for Ack, mark del_add_pending flag
        // to trigger DeleteAdd on receiving Ack
        entry->set_del_add_pending(true);
        break;

    case KSyncEntry::DEL_ACK:
        if (entry->del_add_pending()) {
            // del_add_pending trigger DeleteAdd
            entry->set_del_add_pending(false);
            state = KSyncSM_DeleteAdd(obj, entry);
        } else {
            state = KSyncSM_Add(obj, entry);
        }
        break;

    case KSyncEntry::INT_PTR_REL:
        break;

    default:
        assert(0);
        break;
    }

    return state;
}

void KSyncObject::NotifyEvent(KSyncEntry *entry, KSyncEntry::KSyncEvent event) {

    KSyncEntry::KSyncState state;
    bool dep_reval = false;
    KSyncEntry::KSyncState from_state = entry->GetState();

    if (DoEventTrace()) {
        std::string obj_string(entry->ToString());
        std::string state_string(entry->StateString());
        std::string event_string(entry->EventString(event));
        KSYNC_TRACE(Event, this, obj_string, state_string,
                    event_string);
    }
    switch (entry->GetState()) {
        case KSyncEntry::INIT:
            state = KSyncSM_Init(this, entry, event);
            break;

        case KSyncEntry::TEMP:
            dep_reval = true;
            state = KSyncSM_Temp(this, entry, event);
            break;

        case KSyncEntry::ADD_DEFER:
            dep_reval = true;
            state = KSyncSM_AddDefer(this, entry, event);
            break;

        case KSyncEntry::CHANGE_DEFER:
            dep_reval = true;
            state = KSyncSM_ChangeDefer(this, entry, event);
            break;

        case KSyncEntry::IN_SYNC:
            state = KSyncSM_InSync(this, entry, event);
            break;

        case KSyncEntry::SYNC_WAIT:
            dep_reval = true;
            state = KSyncSM_SyncWait(this, entry, event);
            break;

        case KSyncEntry::NEED_SYNC:
            state = KSyncSM_NeedSync(this, entry, event);
            break;

        case KSyncEntry::DEL_DEFER_SYNC:
            state = KSyncSM_DelPending_Sync(this, entry, event);
            break;

        case KSyncEntry::DEL_DEFER_REF:
            dep_reval = true;
            state = KSyncSM_DelPending_Ref(this, entry, event);
            break;

        case KSyncEntry::DEL_DEFER_DEL_ACK:
            state = KSyncSM_DelPending_DelAck(this, entry, event);
            break;

        case KSyncEntry::DEL_ACK_WAIT:
            state = KSyncSM_DelAckWait(this, entry, event);
            break;

        case KSyncEntry::RENEW_WAIT:
            dep_reval = true;
            state = KSyncSM_RenewWait(this, entry, event);
            break;

        default:
            assert(0);
            break;
    }

    entry->SetState(state);
    entry->RecordTransition(from_state, state, event);

    if (dep_reval == true && entry->IsResolved() &&
        entry->ShouldReEvalBackReference()) {
        BackRefReEval(entry);
    }

    if (state == KSyncEntry::FREE_WAIT || state == KSyncEntry::TEMP) {
        CleanupOnDel(entry);
    }

    if (state == KSyncEntry::FREE_WAIT) {
        intrusive_ptr_release(entry);
        FreeInd(entry, entry->GetIndex());
    }

    if (tree_.empty() == true) {
        EmptyTable();
    }
}

void KSyncObject::NetlinkAckInternal(KSyncEntry *entry, KSyncEntry::KSyncEvent event) {
    tbb::recursive_mutex::scoped_lock lock(lock_);
    entry->Response();
    NotifyEvent(entry, event);
}

bool KSyncObject::StaleEntryCleanupCb() {
    // donot reschedule timer if no stale entries
    if (stale_entry_tree_.empty()) {
        return false;
    }

    uint32_t count = 0;
    std::set<KSyncEntry::KSyncEntryPtr>::iterator it = stale_entry_tree_.begin();
    while (it != stale_entry_tree_.end()) {
        if (count == stale_entries_per_intvl_) {
            break;
        }
        KSyncEntry *entry = (*it).get();
        // Notify entry of stale timer expiration
        entry->StaleTimerExpired();
        // Delete removes entry from stale entry tree
        Delete(entry);
        it = stale_entry_tree_.begin();
        count++;
    }

    // iterate entries and trigger delete
    return stale_entry_cleanup_timer_->Reschedule(stale_entry_cleanup_intvl_);
}

void KSyncObject::NetlinkAck(KSyncEntry *entry, KSyncEntry::KSyncEvent event) {
    NetlinkAckInternal(entry, event);
}

///////////////////////////////////////////////////////////////////////////////
// KSyncEntry dependency management
///////////////////////////////////////////////////////////////////////////////
void KSyncObject::BackRefAdd(KSyncEntry *key, KSyncEntry *reference) {
    KSyncFwdReference *fwd_node = new KSyncFwdReference(key, reference);
    FwdRefTree::iterator fwd_it = fwd_ref_tree_.find(*fwd_node);
    assert(fwd_it == fwd_ref_tree_.end());
    fwd_ref_tree_.insert(*fwd_node);
    intrusive_ptr_add_ref(key);
    intrusive_ptr_add_ref(reference);

    KSyncBackReference *back_node = new KSyncBackReference(reference, key);
    BackRefTree::iterator back_it = back_ref_tree_.find(*back_node);
    assert(back_it == back_ref_tree_.end());
    back_ref_tree_.insert(*back_node);
}

void KSyncObject::BackRefDel(KSyncEntry *key) {
    KSyncFwdReference fwd_search_node(key, NULL);
    FwdRefTree::iterator fwd_it = fwd_ref_tree_.find(fwd_search_node);
    if (fwd_it == fwd_ref_tree_.end()) {
        return;
    }
    KSyncFwdReference *entry = fwd_it.operator->();
    KSyncEntry *reference = entry->reference_;
    fwd_ref_tree_.erase(fwd_it);
    delete entry;

    KSyncBackReference back_search_node(reference, key);
    BackRefTree::iterator back_it = back_ref_tree_.find(back_search_node);
    assert(back_it != back_ref_tree_.end());
    KSyncBackReference *back_node = back_it.operator->();
    back_ref_tree_.erase(back_it);
    delete back_node;

    intrusive_ptr_release(key);
    intrusive_ptr_release(reference);
}

void KSyncObject::BackRefReEval(KSyncEntry *key) {
    std::vector<KSyncEntry *> buf;
    KSyncBackReference node(key, NULL);

    for (BackRefTree::iterator it = back_ref_tree_.upper_bound(node);
         it != back_ref_tree_.end(); ) {
        BackRefTree::iterator it_work = it;

        KSyncBackReference *entry = it_work.operator->();
        if (entry->key_ != key) {
            break;
        }
        KSyncEntry *back_ref = entry->back_reference_;
        buf.push_back(back_ref);
        BackRefDel(entry->back_reference_);
        it = back_ref_tree_.upper_bound(node);
    }

    std::vector<KSyncEntry *>::iterator it = buf.begin();
    while (it != buf.end()) {
        tbb::recursive_mutex::scoped_lock lock((*it)->GetObject()->lock_);
        NotifyEvent(*it, KSyncEntry::RE_EVAL);
        it++;
    }
}

bool KSyncObjectManager::Process(KSyncObjectEvent *event) {
    switch(event->event_) {
    case KSyncObjectEvent::UNREGISTER:
        if (event->obj_->Size() == 0) {
            delete event->obj_;
        }
        break;
    case KSyncObjectEvent::DEL:
        {
            int count = 0;
            // hold reference to entry to ensure the pointer sanity
            KSyncEntry::KSyncEntryPtr entry(NULL);
            if (event->ref_.get() == NULL) {
                event->obj_->set_delete_scheduled();
                if (event->obj_->IsEmpty()) {
                    // trigger explicit empty table callback for client to
                    // complete deletion of object in KSync Context.
                    event->obj_->EmptyTable();
                    break;
                }
                // get the first entry to start with
                entry = event->obj_->Next(NULL);
            } else {
                entry = event->ref_.get();
            }

            // hold reference to entry to ensure the pointer sanity
            // next entry can get free'd in certain cases while processing
            // current entry
            KSyncEntry::KSyncEntryPtr next_entry(NULL);
            while (entry.get() != NULL) {
                next_entry = event->obj_->Next(entry.get());
                count++;
                if (entry->IsDeleted() == false) {
                    // trigger delete if entry is not marked delete already.
                    event->obj_->Delete(entry.get());
                }

                if (count == kMaxEntriesProcess && next_entry.get() != NULL) {
                    // update reference with which entry to start with
                    // in next iteration.
                    event->ref_ = next_entry.get();
                    // yeild and re-enqueue event for processing later.
                    event_queue_->Enqueue(event);

                    // release reference to deleted entry.
                    entry = NULL;
                    return false;
                }
                entry = next_entry.get();
            }
            break;
        }
    default:
        assert(0);
    }
    delete event;
    return true;
}

void KSyncObjectManager::Enqueue(KSyncObjectEvent *event) {
    event_queue_->Enqueue(event);
}

void KSyncObjectManager::Unregister(KSyncObject *table) {
    KSyncObjectEvent *event = new KSyncObjectEvent(table,
                                      KSyncObjectEvent::UNREGISTER);
    singleton_->Enqueue(event);
}

KSyncObjectManager::KSyncObjectManager() {
    event_queue_ = new WorkQueue<KSyncObjectEvent *>
                   (TaskScheduler::GetInstance()->GetTaskId("Agent::KSync"), 0,
                    boost::bind(&KSyncObjectManager::Process, this, _1));
}

KSyncObjectManager::~KSyncObjectManager() {
    delete event_queue_;
}

KSyncObjectManager *KSyncObjectManager::Init() {
    if (singleton_ == NULL) {
        singleton_ = new KSyncObjectManager();
    }
    return singleton_;
}

void KSyncObjectManager::Shutdown() {
    if (singleton_) {
        delete singleton_;
    }
    singleton_ = NULL;
}

// Create a KSync Object event to trigger Delete of all the KSync Entries
// present in the given object.
// Once the delete is scheduled new entry creation is not allowed for this
// object and EmptyTable callback is trigger when all the entries of given
// object are cleaned up. As part of which client can delete the object.
//
// This API can be used to clean up KSync objects irrespective of config
// or oper tables

void KSyncObjectManager::Delete(KSyncObject *object) {
    KSyncObjectEvent *event = new KSyncObjectEvent(object,
                                      KSyncObjectEvent::DEL);
    Enqueue(event);
}

KSyncObjectManager* KSyncObjectManager::GetInstance() {
    return singleton_;
}

// Create a dummy KSync Entry. This entry will all ways be in deferred state
// Any back-ref added to it will never get resolved.
// Can be used to defer an incomplete entry

class KSyncDummyEntry : public KSyncEntry {
public:
    KSyncDummyEntry() : KSyncEntry() { }
    virtual ~KSyncDummyEntry() { }
    virtual bool IsLess(const KSyncEntry &rhs) const {
        return false;
    }
    std::string ToString() const { return "Dummy"; }
    bool Add() { return false;}
    bool Change() { return false; }
    bool Delete() { return false; }
    KSyncObject *GetObject() const { return NULL; }
    KSyncEntry *UnresolvedReference() { return NULL; }
    bool IsDataResolved() {return false;}
private:
    DISALLOW_COPY_AND_ASSIGN(KSyncDummyEntry);
};

KSyncEntry *KSyncObjectManager::default_defer_entry() {
    if (default_defer_entry_.get() == NULL) {
        default_defer_entry_.reset(new KSyncDummyEntry());
    }
    return default_defer_entry_.get();
}

ext: cc

max_stars_repo_name: jnpr-pranav/contrail-controller

max_issues_repo_name: jnpr-pranav/contrail-controller

max_forks_repo_name: jnpr-pranav/contrail-controller


text:
#ifndef WALI_KEYED_SEMELEMSET_HPP
#define WALI_KEYED_SEMELEMSET_HPP

#include "wali/SemElem.hpp"

#include <boost/iterator/iterator_facade.hpp>
#include <boost/optional.hpp>
#include "wali/util/unordered_map.hpp"
#include "wali/util/unordered_set.hpp"
#include <limits>
#include <typeinfo>

#include <iostream>

namespace {
  std::string
  clamp(std::string const & str)
  {
    const size_t maxlen = 50;
    if (str.size() < maxlen) {
      return str;
    }
    else {
      return str.substr(0, maxlen-3) + "...";
    }
  }
}

namespace wali
{
  namespace domains
  {

    /// Represents a domain from a key to a weight.
    ///
    /// The "key" acts a bit like a guard, except that keys that are not
    /// present act like 0/bottom (concretizes to nothing) rather than top
    /// (concretizes to the universe).
    ///
    /// Thus, if I denote an element by <k,w> where k is the key and w the
    /// weight:
    ///
    ///   o  zero is the empty set {}
    ///   o  one  is the singleton set { <1,1> }
    ///   o  combine does set union (it's possible to have multiple weights
    ///      with the same key, though not more than one entry with the same
    ///      key AND weight)
    ///   o  extend extends every mapping of the first with every mapping of
    ///      the second, doing extend of both key and weight: if the extend
    ///      of the key is 0, then that pair is dropped and the extend of the
    ///      weights is not computed
    ///
    /// The key is treated as a sem_elem_t, but it really doesn't have to be
    /// one -- in particular, keys are never combined.
    ///
    /// Another way that the keys aren't like guards (i.e. what the word
    /// 'guard' suggests) is that there is no mixing of weights between keys.
    class KeyedSemElemSet
      : public wali::SemElem
    {
    public:
      typedef wali::util::unordered_map<sem_elem_t, sem_elem_t,
                                        SemElemRefPtrHash, SemElemRefPtrEqual>
              BackingMap;

      typedef BackingMap::const_iterator const_iterator;

      static
      size_t
      get_hash(BackingMap const & m) {
        size_t xor_part = 0u;
        size_t sum_part = 0u;

        for (BackingMap::const_iterator it = m.begin();
             it != m.end(); ++it)
        {
          size_t elem_hash = it->first->hash() + 17*it->second->hash();
          xor_part ^= elem_hash;
          sum_part += elem_hash;
        }
        return xor_part + 17*sum_part;
      }

      static
      BackingMap
      remove_zeroes(BackingMap m)
      {
        for (BackingMap::const_iterator it = m.begin();
             it != m.end(); /*nothing*/ )
        {
          sem_elem_t guard = it->first;
          sem_elem_t weight = it->second;

          if (guard->equal(guard->zero())
              || weight->equal(weight->zero()))
          {
            it = m.erase(it);
          }
          else {
            ++it;
          }
        }
        return m;
      }

      KeyedSemElemSet(BackingMap const & m)
        : map_(remove_zeroes(m))
        , hash_(get_hash(map_))
      {
        assert(m.size() > 0u);
        one_key_ = m.begin()->first->one();
        one_value_ = m.begin()->second->one();
      }

      KeyedSemElemSet(BackingMap const & m,
                      sem_elem_t example_key,
                      sem_elem_t example_value)
        : map_(remove_zeroes(m))
        , one_key_(example_key->one())
        , one_value_(example_value->one())
        , hash_(get_hash(map_))
      {}

      std::pair<const_iterator, const_iterator>
      equal_range(sem_elem_t key) const {
        return map_.equal_range(key);
      }

      const_iterator
      begin() const {
        return map_.begin();
      }

      const_iterator
      end() const {
        return map_.end();
      }

      size_t size() const {
        return map_.size();
      }

      sem_elem_t one() const {
        BackingMap m;
        m[one_key_] = one_value_;
        return new KeyedSemElemSet(m);
      }

      sem_elem_t zero() const {
        BackingMap m;
        return new KeyedSemElemSet(m, one_key_, one_value_);
      }

      sem_elem_t extend(SemElem * se) {
        KeyedSemElemSet * that = dynamic_cast<KeyedSemElemSet*>(se);
        assert(that);

        BackingMap m;

        for (BackingMap::const_iterator this_guard = this->map_.begin();
             this_guard != this->map_.end(); ++this_guard)
        {
          for (BackingMap::const_iterator that_guard = that->map_.begin();
               that_guard != that->map_.end(); ++that_guard)
          {
            sem_elem_t new_guard = this_guard->first->extend(that_guard->first);

            if (!new_guard->equal(new_guard->zero())) {
              sem_elem_t new_weight =
                this_guard->second->extend(that_guard->second);

              BackingMap::iterator loc = m.find(new_guard);
              if (loc == m.end()) {
                m.insert(loc, std::make_pair(new_guard, new_weight));
              }
              else {
                new_weight = new_weight->combine(loc->second);
                loc->second = new_weight;
              }
            }
          }
        }

        return new KeyedSemElemSet(m, one_key_, one_value_);
      }

      sem_elem_t combine(SemElem * se) {
        KeyedSemElemSet * that = dynamic_cast<KeyedSemElemSet*>(se);
        assert(that);

        BackingMap m(this->map_);
        for (BackingMap::const_iterator that_guard = that->map_.begin();
             that_guard != that->map_.end(); ++that_guard)
        {
          BackingMap::iterator new_loc = m.find(that_guard->first);

          if (new_loc == m.end()) {
            m.insert(new_loc, *that_guard);
          }
          else {
            sem_elem_t new_weight = new_loc->second->combine(that_guard->second);
            new_loc->second = new_weight;
          }
        }

        return new KeyedSemElemSet(m, one_key_, one_value_);
      }

      bool equal(SemElem * se) const {
        KeyedSemElemSet * that = dynamic_cast<KeyedSemElemSet*>(se);
        assert(that);

        if (this->map_.size() != that->map_.size()
            || !this->one_key_->equal(that->one_key_)
            || !this->one_value_->equal(that->one_value_))
        {
          return false;
        }

        for (BackingMap::const_iterator this_guard = this->map_.begin();
             this_guard != this->map_.end(); ++this_guard)
        {
          BackingMap::const_iterator that_loc = that->map_.find(this_guard->first);

          if (that_loc == that->map_.end()
              || !that_loc->second->equal(this_guard->second))
          {
            return false;
          }
        }

        return true;
      }

      std::ostream& print( std::ostream & o ) const {
        o << "{ ";
        bool first = true;
        for (BackingMap::const_iterator element = this->map_.begin();
             element != this->map_.end(); ++element)
        {
          if (!first) {
            o << ", ";
          }
          first = false;
          element->first->print(o) << ": ";
          element->second->print(o);
        }
        o << "}";
        return o;
      }

      virtual size_t hash() const { return hash_; }

      virtual
      std::ostream &
      print_typename(std::ostream & os) const {
        os << "KeyedSemElemSet<";
        if (size() == 0u) {
          os << "(empty)";
        }
        else {
          begin()->first->print_typename(os) << " -> ";
          begin()->second->print_typename(os);
        }
        return os << ">";
      }

      // Pull in the sem_elem_t overloads
      using SemElem::extend;
      using SemElem::combine;
      using SemElem::equal;

    private:
      BackingMap map_;
      sem_elem_t one_key_, one_value_;
      size_t hash_;
    };

    /// Represents a key that might be written [s->s'](w). It applies when
    /// a portion of the current state moves from s to s'. s and s' are some
    /// literal value of type 'PositionType'.
    ///
    /// [s->s'] extend [s'->s''] gives [s->s''];
    ///
    /// The class tracks a distinguished 0 value that will produce 0 when
    /// extended.
    ///
    /// This is NOT an actual semiring, despite what the inheritance
    /// claims. If someone calls combine(), this will abort, as with
    /// one(). (See the comment on KeyedSemElemSet for more details.)
    ///
    /// To be useful in its intended context, PositionType should have an
    /// operator== defined as well as either operator< or a hash<>er, as
    /// appropriate (depending on the setting of KeyedSemElemSet). It should
    /// be copy-constructable. If you call print(), it should have an <<
    /// defined.
    template <typename PositionType>
    class PositionKey
      : public wali::SemElem
    {
      enum Special { SpecialOne, SpecialZero };

      boost::optional<PositionType> pre_, post_;
      boost::optional<Special> special_;

      PositionKey(Special s)
        : special_(s)
      {}

      bool valid() const {
        if (special_) {
          return !pre_ && !post_;
        }
        else {
          return pre_ && post_;
        }
      }

    public:

      virtual
      std::ostream &
      print_typename(std::ostream & os) const {
        os << "PositionKey<" << typeid(PositionType).name() << ">";
        return os;
      }

      static PositionKey makeOne() {
        return PositionKey(SpecialOne);
      }

      static PositionKey makeZero() {
        return PositionKey(SpecialZero);
      }

      PositionKey(PositionType const & pre, PositionType const & post)
        : pre_(pre)
        , post_(post)
      {}

      PositionType pre() const {
        assert(valid() && !special_);
        return *pre_;
      }

      PositionType post() const {
        assert(valid() && !special_);
        return *post_;
      }

      bool isZero() const {
        assert(valid());
        return special_ && *special_ == SpecialZero;
      }

      bool isOne() const {
        assert(valid());
        return special_ && *special_ == SpecialOne;
      }

      ///
      /// Actually returns one
      sem_elem_t one() const {
        static sem_elem_t o = new PositionKey(SpecialOne);
        return o;
      }

      ///
      /// This actually returns zero
      sem_elem_t zero() const {
        static sem_elem_t z = new PositionKey(SpecialZero);
        return z;
      }

      ///
      /// This actually extends, as described above
      sem_elem_t extend(SemElem * se)
      {
        PositionKey * that = dynamic_cast<PositionKey*>(se);
        assert(that != NULL);

        if (this->isZero() || that->isZero()) {
          return zero();
        }

        if (this->isOne()) {
          // Hmmm. I will assume that if the reference count is non-zero then
          // it is in a ref_pointer.
          if (that->count > 0) {
            return that;
          }
          else {
            return new PositionKey(*that);
          }
        }
        if (that->isOne()) {
          if (this->count > 0) {
            return this;
          }
          else {
            return new PositionKey(*this);
          }
        }

        if (*this->post_ != *that->pre_) {
          return zero();
        }

        return new PositionKey(*this->pre_, *that->post_);
      }

      using SemElem::extend;

      ///
      /// This aborts
      sem_elem_t combine(SemElem * UNUSED_PARAMETER(se)) {
        abort();
        return NULL;
      }

      ///
      /// This actually tells equality
      bool equal(SemElem * se) const {
        PositionKey * that = dynamic_cast<PositionKey*>(se);
        assert(that != NULL);

        if (this->isZero() && that->isZero()) {
          return true;
        }
        if (this->isZero() || that->isZero()) {
          return false;
        }

        if (this->isOne() && that->isOne()) {
          return true;
        }
        if (this->isOne() || that->isOne()) {
          return false;
        }

        return (*this->pre_ == *that->pre_)
          && (*this->post_ == *that->post_);
      }

      using SemElem::equal;
      using SemElem::combine;

      ///
      /// This actually prints the guard
      std::ostream& print( std::ostream & os ) const {
        assert(valid());
        if (isZero()) {
          os << "[ZERO]";
        }
        else if (isOne()) {
          os << "[ONE]";
        }
        else {
          os << "[" << *pre_ << "->" << *post_ << "]";
        }
        return os;
      }

      ///
      /// This actually does <
      bool containerLessThan(SemElem const * se) const {
        PositionKey const * that = dynamic_cast<PositionKey const *>(se);
        assert(that != NULL);

        if (this->isZero() && that->isZero()) {
          // this == that, so false
          return false;
        }
        if (this->isZero()) {
          // 0 sorts first
          return true;
        }
        if (that->isZero()) {
          // 0 sorts first
          return false;
        }

        if (this->isOne() && that->isOne()) {
          return false;
        }
        if (this->isOne()) {
          // One sorts first except for 0
          return true;
        }
        if (that->isOne()) {
          return false;
        }

        return std::make_pair(*this->pre_, *this->post_)
          < std::make_pair(*that->pre_, *that->post_);
      }

      ///
      /// This actually does hash
      size_t hash() const {
        wali::util::hash<PositionType> hasher;

        if (isZero()) {
          return std::numeric_limits<size_t>::max();
        }
        if (isOne()) {
          return std::numeric_limits<size_t>::max() - 1;
        }

        return hasher(*pre_) + 17*hasher(*post_);
      }
    };

  }
}

// Yo emacs!
// Local Variables:
//     c-file-style: "ellemtel"
//     c-basic-offset: 2
//     indent-tabs-mode: nil
// End:

#endif

max_stars_repo_name: WaliDev/WALi-OpenNWA

max_issues_repo_name: WaliDev/WALi-OpenNWA

max_forks_repo_name: WaliDev/WALi-OpenNWA


text:
//---------------------------------------------------------------------------//
// Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@gmail.com>
//
// 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://boostorg.github.com/compute for more information.
//---------------------------------------------------------------------------//

#define BOOST_TEST_MODULE TestUserDefinedTypes
#include <boost/test/unit_test.hpp>

#include <iostream>

#include <boost/compute/function.hpp>
#include <boost/compute/system.hpp>
#include <boost/compute/algorithm/sort.hpp>
#include <boost/compute/container/vector.hpp>
#include <boost/compute/types/struct.hpp>

namespace compute = boost::compute;

// user-defined data type containing two int's and a float
struct UDD
{
    int a;
    int b;
    float c;
};

// make UDD available to OpenCL
BOOST_COMPUTE_ADAPT_STRUCT(UDD, UDD, (a, b, c))

// comparison operator for UDD
bool operator==(const UDD &lhs, const UDD &rhs)
{
    return lhs.a == rhs.a && lhs.b == rhs.b && lhs.c == rhs.c;
}

// output stream operator for UDD
std::ostream& operator<<(std::ostream &stream, const UDD &x)
{
    return stream << "(" << x.a << ", " << x.b << ", " << x.c << ")";
}

// function to generate a random UDD on the host
UDD rand_UDD()
{
    UDD udd;
    udd.a = rand() % 100;
    udd.b = rand() % 100;
    udd.c = (float)(rand() % 100) / 1.3f;

    return udd;
}

// function to compare two UDD's on the host by their first component
bool compare_UDD_host(const UDD &lhs, const UDD &rhs)
{
    return lhs.a < rhs.a;
}

// function to compate two UDD's on the device by their first component
BOOST_COMPUTE_FUNCTION(bool, compare_UDD_device, (UDD lhs, UDD rhs),
{
    return lhs.a < rhs.a;
});

#include "check_macros.hpp"
#include "context_setup.hpp"

// see: issue #11 (https://github.com/boostorg/compute/issues/11)
BOOST_AUTO_TEST_CASE(issue_11)
{
    if(device.vendor() == "NVIDIA" && device.platform().name() == "Apple"){
        // FIXME: this test currently segfaults on NVIDIA GPUs on Apple
        std::cerr << "skipping issue test on NVIDIA GPU on Apple platform" << std::endl;
        return;
    }

    // create vector of random values on the host
    std::vector<UDD> host_vector(10);
    std::generate(host_vector.begin(), host_vector.end(), rand_UDD);

    // transfer the values to the device
    compute::vector<UDD> device_vector(host_vector.size(), context);
    compute::copy(
        host_vector.begin(), host_vector.end(), device_vector.begin(), queue
    );

    // sort values on the device
    compute::sort(
        device_vector.begin(),
        device_vector.end(),
        compare_UDD_device,
        queue
    );

    // sort values on the host
    std::sort(
        host_vector.begin(),
        host_vector.end(),
        compare_UDD_host
    );

    // copy sorted device values back to the host
    std::vector<UDD> tmp(10);
    compute::copy(
        device_vector.begin(),
        device_vector.end(),
        tmp.begin(),
        queue
    );

    // verify sorted values
    for(size_t i = 0; i < host_vector.size(); i++){
        BOOST_CHECK_EQUAL(tmp[i], host_vector[i]);
    }
}

BOOST_AUTO_TEST_SUITE_END()