Subject: [Boost-commit] svn:boost r60079 - in trunk/boost/graph: . distributed
From: jewillco_at_[hidden]
Date: 2010-03-02 14:53:49
Author: jewillco
Date: 2010-03-02 14:53:47 EST (Tue, 02 Mar 2010)
New Revision: 60079
URL: http://svn.boost.org/trac/boost/changeset/60079
Log:
Changed to allow characters that are not 8-bit; added one-bit-per-color color map
Added:
trunk/boost/graph/distributed/one_bit_color_map.hpp
- copied, changed from r60077, /trunk/boost/graph/distributed/two_bit_color_map.hpp
trunk/boost/graph/one_bit_color_map.hpp
- copied, changed from r60077, /trunk/boost/graph/two_bit_color_map.hpp
Text files modified:
trunk/boost/graph/distributed/one_bit_color_map.hpp | 56 ++++++++++++++--------------
trunk/boost/graph/one_bit_color_map.hpp | 75 +++++++++++++++++++++------------------
trunk/boost/graph/two_bit_color_map.hpp | 20 ++++++++--
3 files changed, 83 insertions(+), 68 deletions(-)
Copied: trunk/boost/graph/distributed/one_bit_color_map.hpp (from r60077, /trunk/boost/graph/distributed/two_bit_color_map.hpp)
==============================================================================
--- /trunk/boost/graph/distributed/two_bit_color_map.hpp (original)
+++ trunk/boost/graph/distributed/one_bit_color_map.hpp 2010-03-02 14:53:47 EST (Tue, 02 Mar 2010)
@@ -1,4 +1,4 @@
-// Copyright (C) 2006 The Trustees of Indiana University.
+// Copyright (C) 2006-2010 The Trustees of Indiana University.
// Use, modification and distribution is subject to the Boost Software
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
@@ -8,26 +8,26 @@
// Jeremiah Willcock
// Andrew Lumsdaine
-// Distributed version of the two-bit color map
-#ifndef BOOST_DISTRIBUTED_TWO_BIT_COLOR_MAP_HPP
-#define BOOST_DISTRIBUTED_TWO_BIT_COLOR_MAP_HPP
+// Distributed version of the one-bit color map
+#ifndef BOOST_DISTRIBUTED_ONE_BIT_COLOR_MAP_HPP
+#define BOOST_DISTRIBUTED_ONE_BIT_COLOR_MAP_HPP
#ifndef BOOST_GRAPH_USE_MPI
#error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
#endif
-#include <boost/graph/two_bit_color_map.hpp>
+#include <boost/graph/one_bit_color_map.hpp>
#include <boost/property_map/parallel/distributed_property_map.hpp>
#include <boost/property_map/parallel/local_property_map.hpp>
namespace boost {
template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
-class two_bit_color_map<local_property_map<ProcessGroup,GlobalMap,StorageMap> >
+class one_bit_color_map<local_property_map<ProcessGroup,GlobalMap,StorageMap> >
: public parallel::distributed_property_map<ProcessGroup, GlobalMap,
- two_bit_color_map<StorageMap> >
+ one_bit_color_map<StorageMap> >
{
- typedef two_bit_color_map<StorageMap> local_map;
+ typedef one_bit_color_map<StorageMap> local_map;
typedef parallel::distributed_property_map<ProcessGroup, GlobalMap,
local_map >
@@ -37,7 +37,7 @@
index_map_type;
public:
- two_bit_color_map(std::size_t inital_size,
+ one_bit_color_map(std::size_t inital_size,
const index_map_type& index = index_map_type())
: inherited(index.process_group(), index.global(),
local_map(inital_size, index.base())) { }
@@ -47,31 +47,31 @@
};
template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
-inline two_bit_color_type
-get(two_bit_color_map<local_property_map<ProcessGroup,GlobalMap,StorageMap> >
+inline one_bit_color_type
+get(one_bit_color_map<local_property_map<ProcessGroup,GlobalMap,StorageMap> >
const& pm,
- typename two_bit_color_map<GlobalMap>::key_type key)
+ typename one_bit_color_map<GlobalMap>::key_type key)
{
return get(pm.base(), key);
}
template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
inline void
-put(two_bit_color_map<local_property_map<ProcessGroup,GlobalMap,StorageMap> >
+put(one_bit_color_map<local_property_map<ProcessGroup,GlobalMap,StorageMap> >
const& pm,
- typename two_bit_color_map<GlobalMap>::key_type key,
- two_bit_color_type value)
+ typename one_bit_color_map<GlobalMap>::key_type key,
+ one_bit_color_type value)
{
put(pm.base(), key, value);
}
template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
-class two_bit_color_map<parallel::distributed_property_map<
+class one_bit_color_map<parallel::distributed_property_map<
ProcessGroup, GlobalMap, StorageMap> >
: public parallel::distributed_property_map<
- ProcessGroup, GlobalMap, two_bit_color_map<StorageMap> >
+ ProcessGroup, GlobalMap, one_bit_color_map<StorageMap> >
{
- typedef two_bit_color_map<StorageMap> local_map;
+ typedef one_bit_color_map<StorageMap> local_map;
typedef parallel::distributed_property_map<ProcessGroup,GlobalMap,local_map>
inherited;
@@ -81,7 +81,7 @@
index_map_type;
public:
- two_bit_color_map(std::size_t inital_size,
+ one_bit_color_map(std::size_t inital_size,
const index_map_type& index = index_map_type())
: inherited(index.process_group(), index.global(),
local_map(inital_size, index.base())) { }
@@ -91,26 +91,26 @@
};
template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
-inline two_bit_color_type
-get(two_bit_color_map<
+inline one_bit_color_type
+get(one_bit_color_map<
parallel::distributed_property_map<
- ProcessGroup, GlobalMap, two_bit_color_map<StorageMap> > > const& pm,
- typename two_bit_color_map<GlobalMap>::key_type key)
+ ProcessGroup, GlobalMap, one_bit_color_map<StorageMap> > > const& pm,
+ typename one_bit_color_map<GlobalMap>::key_type key)
{
return get(pm.base(), key);
}
template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
inline void
-put(two_bit_color_map<
+put(one_bit_color_map<
parallel::distributed_property_map<
- ProcessGroup, GlobalMap, two_bit_color_map<StorageMap> > > const& pm,
- typename two_bit_color_map<GlobalMap>::key_type key,
- two_bit_color_type value)
+ ProcessGroup, GlobalMap, one_bit_color_map<StorageMap> > > const& pm,
+ typename one_bit_color_map<GlobalMap>::key_type key,
+ one_bit_color_type value)
{
put(pm.base(), key, value);
}
} // end namespace boost
-#endif // BOOST_DISTRIBUTED_TWO_BIT_COLOR_MAP_HPP
+#endif // BOOST_DISTRIBUTED_ONE_BIT_COLOR_MAP_HPP
Copied: trunk/boost/graph/one_bit_color_map.hpp (from r60077, /trunk/boost/graph/two_bit_color_map.hpp)
==============================================================================
--- /trunk/boost/graph/two_bit_color_map.hpp (original)
+++ trunk/boost/graph/one_bit_color_map.hpp 2010-03-02 14:53:47 EST (Tue, 02 Mar 2010)
@@ -1,4 +1,4 @@
-// Copyright (C) 2005-2006 The Trustees of Indiana University.
+// Copyright (C) 2005-2010 The Trustees of Indiana University.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -8,93 +8,98 @@
// Douglas Gregor
// Andrew Lumsdaine
-// Two bit per color property map
+// One bit per color property map (gray and black are the same, green is not
+// supported)
-#ifndef BOOST_TWO_BIT_COLOR_MAP_HPP
-#define BOOST_TWO_BIT_COLOR_MAP_HPP
+#ifndef BOOST_ONE_BIT_COLOR_MAP_HPP
+#define BOOST_ONE_BIT_COLOR_MAP_HPP
#include <boost/property_map/property_map.hpp>
#include <boost/graph/properties.hpp>
#include <boost/shared_array.hpp>
+#include <boost/config.hpp>
#include <algorithm>
+#include <limits>
namespace boost {
-enum two_bit_color_type {
- two_bit_white = 0,
- two_bit_gray = 1,
- two_bit_green = 2,
- two_bit_black = 3
+enum one_bit_color_type {
+ one_bit_white = 0,
+ one_bit_not_white = 1
};
template <>
-struct color_traits<two_bit_color_type>
+struct color_traits<one_bit_color_type>
{
- static two_bit_color_type white() { return two_bit_white; }
- static two_bit_color_type gray() { return two_bit_gray; }
- static two_bit_color_type green() { return two_bit_green; }
- static two_bit_color_type black() { return two_bit_black; }
+ static one_bit_color_type white() { return one_bit_white; }
+ static one_bit_color_type gray() { return one_bit_not_white; }
+ static one_bit_color_type black() { return one_bit_not_white; }
};
template<typename IndexMap = identity_property_map>
-struct two_bit_color_map
+struct one_bit_color_map
{
+ BOOST_STATIC_CONSTANT(int, bits_per_char = std::numeric_limits<unsigned char>::digits);
+ BOOST_STATIC_ASSERT(std::numeric_limits<unsigned char>::radix == 2);
+ BOOST_STATIC_ASSERT(bits_per_char > 0);
std::size_t n;
IndexMap index;
shared_array<unsigned char> data;
typedef typename property_traits<IndexMap>::key_type key_type;
- typedef two_bit_color_type value_type;
+ typedef one_bit_color_type value_type;
typedef void reference;
typedef read_write_property_map_tag category;
- explicit two_bit_color_map(std::size_t n, const IndexMap& index = IndexMap())
- : n(n), index(index), data(new unsigned char[(n + 3) / 4])
+ explicit one_bit_color_map(std::size_t n, const IndexMap& index = IndexMap())
+ : n(n), index(index), data(new unsigned char[(n + bits_per_char - 1) / bits_per_char])
{
// Fill to white
- std::fill(data.get(), data.get() + (n + 3) / 4, 0);
+ std::fill(data.get(), data.get() + (n + bits_per_char - 1) / bits_per_char, 0);
}
};
template<typename IndexMap>
-inline two_bit_color_type
-get(const two_bit_color_map<IndexMap>& pm,
- typename two_bit_color_map<IndexMap>::key_type key)
+inline one_bit_color_type
+get(const one_bit_color_map<IndexMap>& pm,
+ typename one_bit_color_map<IndexMap>::key_type key)
{
+ BOOST_STATIC_CONSTANT(int, bits_per_char = one_bit_color_map<IndexMap>::bits_per_char);
typename property_traits<IndexMap>::value_type i = get(pm.index, key);
assert ((std::size_t)i < pm.n);
- return two_bit_color_type((pm.data.get()[i / 4] >> ((i % 4) * 2)) & 3);
+ return one_bit_color_type((pm.data.get()[i / bits_per_char] >> (i % bits_per_char)) & 1);
}
template<typename IndexMap>
inline void
-put(const two_bit_color_map<IndexMap>& pm,
- typename two_bit_color_map<IndexMap>::key_type key,
- two_bit_color_type value)
+put(const one_bit_color_map<IndexMap>& pm,
+ typename one_bit_color_map<IndexMap>::key_type key,
+ one_bit_color_type value)
{
+ BOOST_STATIC_CONSTANT(int, bits_per_char = one_bit_color_map<IndexMap>::bits_per_char);
typename property_traits<IndexMap>::value_type i = get(pm.index, key);
assert ((std::size_t)i < pm.n);
- assert (value >= 0 && value < 4);
- std::size_t byte_num = i / 4;
- std::size_t bit_position = ((i % 4) * 2);
+ assert (value >= 0 && value < 2);
+ std::size_t byte_num = i / bits_per_char;
+ std::size_t bit_position = (i % bits_per_char);
pm.data.get()[byte_num] =
(unsigned char)
- ((pm.data.get()[byte_num] & ~(3 << bit_position))
+ ((pm.data.get()[byte_num] & ~(1 << bit_position))
| (value << bit_position));
}
template<typename IndexMap>
-inline two_bit_color_map<IndexMap>
-make_two_bit_color_map(std::size_t n, const IndexMap& index_map)
+inline one_bit_color_map<IndexMap>
+make_one_bit_color_map(std::size_t n, const IndexMap& index_map)
{
- return two_bit_color_map<IndexMap>(n, index_map);
+ return one_bit_color_map<IndexMap>(n, index_map);
}
} // end namespace boost
-#endif // BOOST_TWO_BIT_COLOR_MAP_HPP
+#endif // BOOST_ONE_BIT_COLOR_MAP_HPP
#ifdef BOOST_GRAPH_USE_MPI
-# include <boost/graph/distributed/two_bit_color_map.hpp>
+# include <boost/graph/distributed/one_bit_color_map.hpp>
#endif
Modified: trunk/boost/graph/two_bit_color_map.hpp
==============================================================================
--- trunk/boost/graph/two_bit_color_map.hpp (original)
+++ trunk/boost/graph/two_bit_color_map.hpp 2010-03-02 14:53:47 EST (Tue, 02 Mar 2010)
@@ -16,7 +16,9 @@
#include <boost/property_map/property_map.hpp>
#include <boost/graph/properties.hpp>
#include <boost/shared_array.hpp>
+#include <boost/config.hpp>
#include <algorithm>
+#include <limits>
namespace boost {
@@ -44,16 +46,20 @@
IndexMap index;
shared_array<unsigned char> data;
+ BOOST_STATIC_CONSTANT(int, bits_per_char = std::numeric_limits<unsigned char>::digits);
+ BOOST_STATIC_CONSTANT(int, elements_per_char = bits_per_char / 2);
+ BOOST_STATIC_ASSERT(std::numeric_limits<unsigned char>::radix == 2);
+ BOOST_STATIC_ASSERT(elements_per_char > 0);
typedef typename property_traits<IndexMap>::key_type key_type;
typedef two_bit_color_type value_type;
typedef void reference;
typedef read_write_property_map_tag category;
explicit two_bit_color_map(std::size_t n, const IndexMap& index = IndexMap())
- : n(n), index(index), data(new unsigned char[(n + 3) / 4])
+ : n(n), index(index), data(new unsigned char[(n + elements_per_char - 1) / elements_per_char])
{
// Fill to white
- std::fill(data.get(), data.get() + (n + 3) / 4, 0);
+ std::fill(data.get(), data.get() + (n + elements_per_char - 1) / elements_per_char, 0);
}
};
@@ -62,9 +68,12 @@
get(const two_bit_color_map<IndexMap>& pm,
typename two_bit_color_map<IndexMap>::key_type key)
{
+ BOOST_STATIC_CONSTANT(int, elements_per_char = two_bit_color_map<IndexMap>::elements_per_char);
typename property_traits<IndexMap>::value_type i = get(pm.index, key);
assert ((std::size_t)i < pm.n);
- return two_bit_color_type((pm.data.get()[i / 4] >> ((i % 4) * 2)) & 3);
+ std::size_t byte_num = i / elements_per_char;
+ std::size_t bit_position = ((i % elements_per_char) * 2);
+ return two_bit_color_type((pm.data.get()[byte_num] >> bit_position) & 3);
}
template<typename IndexMap>
@@ -73,11 +82,12 @@
typename two_bit_color_map<IndexMap>::key_type key,
two_bit_color_type value)
{
+ BOOST_STATIC_CONSTANT(int, elements_per_char = two_bit_color_map<IndexMap>::elements_per_char);
typename property_traits<IndexMap>::value_type i = get(pm.index, key);
assert ((std::size_t)i < pm.n);
assert (value >= 0 && value < 4);
- std::size_t byte_num = i / 4;
- std::size_t bit_position = ((i % 4) * 2);
+ std::size_t byte_num = i / elements_per_char;
+ std::size_t bit_position = ((i % elements_per_char) * 2);
pm.data.get()[byte_num] =
(unsigned char)
((pm.data.get()[byte_num] & ~(3 << bit_position))