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/graph/detail/mpi_include.hpp>
  19 #include <boost/shared_array.hpp>
  20 #include <boost/config.hpp>
  21 #include <boost/assert.hpp>
  22 #include <algorithm>
  23 #include <limits>
  24
  25 namespace boost {
  26
  27 enum two_bit_color_type {
  28   two_bit_white = 0,
  29   two_bit_gray  = 1,
  30   two_bit_green = 2,
  31   two_bit_black = 3
  32 };
  33
  34 template <>
  35 struct color_traits<two_bit_color_type>
  36 {
  37   static two_bit_color_type white() { return two_bit_white; }
  38   static two_bit_color_type gray()  { return two_bit_gray; }
  39   static two_bit_color_type green() { return two_bit_green; }
  40   static two_bit_color_type black() { return two_bit_black; }
  41 };
  42
  43
  44 template<typename IndexMap = identity_property_map>
  45 struct two_bit_color_map
  46 {
  47   std::size_t n;
  48   IndexMap index;
  49   shared_array<unsigned char> data;
  50
  51   BOOST_STATIC_CONSTANT(int, bits_per_char = std::numeric_limits<unsigned char>::digits);
  52   BOOST_STATIC_CONSTANT(int, elements_per_char = bits_per_char / 2);
  53   typedef typename property_traits<IndexMap>::key_type key_type;
  54   typedef two_bit_color_type value_type;
  55   typedef void reference;
  56   typedef read_write_property_map_tag category;
  57
  58   explicit two_bit_color_map(std::size_t n, const IndexMap& index = IndexMap())
  59     : n(n), index(index), data(new unsigned char[(n + elements_per_char - 1) / elements_per_char])
  60   {
  61     // Fill to white
  62     std::fill(data.get(), data.get() + (n + elements_per_char - 1) / elements_per_char, 0);
  63   }
  64 };
  65
  66 template<typename IndexMap>
  67 inline two_bit_color_type
  68 get(const two_bit_color_map<IndexMap>& pm,
  69     typename property_traits<IndexMap>::key_type key)
  70 {
  71   BOOST_STATIC_CONSTANT(int, elements_per_char = two_bit_color_map<IndexMap>::elements_per_char);
  72   typename property_traits<IndexMap>::value_type i = get(pm.index, key);
  73   BOOST_ASSERT ((std::size_t)i < pm.n);
  74   std::size_t byte_num = i / elements_per_char;
  75   std::size_t bit_position = ((i % elements_per_char) * 2);
  76   return two_bit_color_type((pm.data.get()[byte_num] >> bit_position) & 3);
  77 }
  78
  79 template<typename IndexMap>
  80 inline void
  81 put(const two_bit_color_map<IndexMap>& pm,
  82     typename property_traits<IndexMap>::key_type key,
  83     two_bit_color_type value)
  84 {
  85   BOOST_STATIC_CONSTANT(int, elements_per_char = two_bit_color_map<IndexMap>::elements_per_char);
  86   typename property_traits<IndexMap>::value_type i = get(pm.index, key);
  87   BOOST_ASSERT ((std::size_t)i < pm.n);
  88   BOOST_ASSERT (value >= 0 && value < 4);
  89   std::size_t byte_num = i / elements_per_char;
  90   std::size_t bit_position = ((i % elements_per_char) * 2);
  91     pm.data.get()[byte_num] =
  92       (unsigned char)
  93         ((pm.data.get()[byte_num] & ~(3 << bit_position))
  94          | (value << bit_position));
  95 }
  96
  97 template<typename IndexMap>
  98 inline two_bit_color_map<IndexMap>
  99 make_two_bit_color_map(std::size_t n, const IndexMap& index_map)
 100 {
 101   return two_bit_color_map<IndexMap>(n, index_map);
 102 }
 103
 104 } // end namespace boost
 105
 106 #include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/two_bit_color_map.hpp>)
 107
 108 #endif // BOOST_TWO_BIT_COLOR_MAP_HPP