ceph/src/boost/boost/graph/two_bit_color_map.hpp

   1 // Copyright (C) 2005-2006 The Trustees of Indiana University.
   2
   3 // Distributed under the Boost Software License, Version 1.0.
   4 // (See accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 //  Authors: Jeremiah Willcock
   8 //           Douglas Gregor
   9 //           Andrew Lumsdaine
  10
  11 // Two bit per color property map
  12
  13 #ifndef BOOST_TWO_BIT_COLOR_MAP_HPP
  14 #define BOOST_TWO_BIT_COLOR_MAP_HPP
  15
  16 #include <boost/property_map/property_map.hpp>
  17 #include <boost/graph/properties.hpp>
  18 #include <boost/shared_array.hpp>
  19 #include <boost/config.hpp>
  20 #include <boost/assert.hpp>
  21 #include <algorithm>
  22 #include <limits>
  23
  24 namespace boost {
  25
  26 enum two_bit_color_type {
  27   two_bit_white = 0,
  28   two_bit_gray  = 1,
  29   two_bit_green = 2,
  30   two_bit_black = 3
  31 };
  32
  33 template <>
  34 struct color_traits<two_bit_color_type>
  35 {
  36   static two_bit_color_type white() { return two_bit_white; }
  37   static two_bit_color_type gray()  { return two_bit_gray; }
  38   static two_bit_color_type green() { return two_bit_green; }
  39   static two_bit_color_type black() { return two_bit_black; }
  40 };
  41
  42
  43 template<typename IndexMap = identity_property_map>
  44 struct two_bit_color_map
  45 {
  46   std::size_t n;
  47   IndexMap index;
  48   shared_array<unsigned char> data;
  49
  50   BOOST_STATIC_CONSTANT(int, bits_per_char = std::numeric_limits<unsigned char>::digits);
  51   BOOST_STATIC_CONSTANT(int, elements_per_char = bits_per_char / 2);
  52   typedef typename property_traits<IndexMap>::key_type key_type;
  53   typedef two_bit_color_type value_type;
  54   typedef void reference;
  55   typedef read_write_property_map_tag category;
  56
  57   explicit two_bit_color_map(std::size_t n, const IndexMap& index = IndexMap())
  58     : n(n), index(index), data(new unsigned char[(n + elements_per_char - 1) / elements_per_char])
  59   {
  60     // Fill to white
  61     std::fill(data.get(), data.get() + (n + elements_per_char - 1) / elements_per_char, 0);
  62   }
  63 };
  64
  65 template<typename IndexMap>
  66 inline two_bit_color_type
  67 get(const two_bit_color_map<IndexMap>& pm,
  68     typename property_traits<IndexMap>::key_type key)
  69 {
  70   BOOST_STATIC_CONSTANT(int, elements_per_char = two_bit_color_map<IndexMap>::elements_per_char);
  71   typename property_traits<IndexMap>::value_type i = get(pm.index, key);
  72   BOOST_ASSERT ((std::size_t)i < pm.n);
  73   std::size_t byte_num = i / elements_per_char;
  74   std::size_t bit_position = ((i % elements_per_char) * 2);
  75   return two_bit_color_type((pm.data.get()[byte_num] >> bit_position) & 3);
  76 }
  77
  78 template<typename IndexMap>
  79 inline void
  80 put(const two_bit_color_map<IndexMap>& pm,
  81     typename property_traits<IndexMap>::key_type key,
  82     two_bit_color_type value)
  83 {
  84   BOOST_STATIC_CONSTANT(int, elements_per_char = two_bit_color_map<IndexMap>::elements_per_char);
  85   typename property_traits<IndexMap>::value_type i = get(pm.index, key);
  86   BOOST_ASSERT ((std::size_t)i < pm.n);
  87   BOOST_ASSERT (value >= 0 && value < 4);
  88   std::size_t byte_num = i / elements_per_char;
  89   std::size_t bit_position = ((i % elements_per_char) * 2);
  90     pm.data.get()[byte_num] =
  91       (unsigned char)
  92         ((pm.data.get()[byte_num] & ~(3 << bit_position))
  93          | (value << bit_position));
  94 }
  95
  96 template<typename IndexMap>
  97 inline two_bit_color_map<IndexMap>
  98 make_two_bit_color_map(std::size_t n, const IndexMap& index_map)
  99 {
 100   return two_bit_color_map<IndexMap>(n, index_map);
 101 }
 102
 103 } // end namespace boost
 104
 105 #endif // BOOST_TWO_BIT_COLOR_MAP_HPP
 106
 107 #ifdef BOOST_GRAPH_USE_MPI
 108 #  include <boost/graph/distributed/two_bit_color_map.hpp>
 109 #endif