1 /* 2 * Copyright (c) 2017-2018, Intel Corporation 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions are met: 6 * 7 * * Redistributions of source code must retain the above copyright notice, 8 * this list of conditions and the following disclaimer. 9 * * Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * * Neither the name of Intel Corporation nor the names of its contributors 13 * may be used to endorse or promote products derived from this software 14 * without specific prior written permission. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 26 * POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29 /** 30 * \brief Small Color Map: implements a property map designed to represent 31 * colors using minimal memory (two bits per index). 32 * 33 * This is based on the Boost BGL two_bit_color_map, but provides some extra 34 * functionality (such as a fill operation). 35 */ 36 37 #ifndef GRAPH_SMALL_COLOR_MAP_H 38 #define GRAPH_SMALL_COLOR_MAP_H 39 40 #include "ue2common.h" 41 42 #include <cstring> 43 #include <memory> 44 #include <vector> 45 46 namespace ue2 { 47 48 enum class small_color : u8 { 49 white = 0, 50 gray = 1, 51 black = 2 52 // Note: we have room for one more colour. 53 }; 54 55 } // namespace ue2 56 57 namespace boost { 58 59 /** \brief Specialisation of boost::color_traits for small_color. */ 60 template<> 61 struct color_traits<ue2::small_color> { 62 static ue2::small_color white() { return ue2::small_color::white; } 63 static ue2::small_color gray() { return ue2::small_color::gray; } 64 static ue2::small_color black() { return ue2::small_color::black; } 65 }; 66 67 } // namespace boost 68 69 namespace ue2 { 70 71 static constexpr u8 fill_lut[] = { 72 0, // white 73 0x55, // gray 74 0xaa, // black 75 }; 76 77 /** 78 * \brief Small Color Map: implements a property map designed to represent 79 * colors using minimal memory (two bits per index). 80 * 81 * If your graph type provides an index map in get(vertex_index, g), you can 82 * use make_small_color_map() to construct this. 83 */ 84 template<typename IndexMap> 85 class small_color_map { 86 size_t n; 87 IndexMap index_map; 88 89 // This class is passed by value into (potentially recursive) BGL 90 // algorithms, so we use a shared_ptr to keep the copy lightweight and 91 // ensure that data is correctly destroyed. 92 std::shared_ptr<std::vector<u8>> data; 93 94 static constexpr size_t bit_size = 2; 95 static constexpr size_t entries_per_byte = (sizeof(u8) * 8) / bit_size; 96 static constexpr u8 bit_mask = (1U << bit_size) - 1; 97 98 public: 99 using key_type = typename boost::property_traits<IndexMap>::key_type; 100 using value_type = small_color; 101 using reference = small_color; 102 using category = boost::read_write_property_map_tag; 103 104 small_color_map(size_t n_in, const IndexMap &index_map_in) 105 : n(n_in), index_map(index_map_in) { 106 size_t num_bytes = (n + entries_per_byte - 1) / entries_per_byte; 107 data = std::make_shared<std::vector<unsigned char>>(num_bytes); 108 fill(small_color::white); 109 } 110 111 void fill(small_color color) { 112 assert(static_cast<u8>(color) < sizeof(fill_lut)); 113 u8 val = fill_lut[static_cast<u8>(color)]; 114 std::memset(data->data(), val, data->size()); 115 } 116 117 size_t count(small_color color) const { 118 assert(static_cast<u8>(color) < sizeof(fill_lut)); 119 size_t num = 0; 120 for (size_t i = 0; i < n; i++) { 121 size_t byte = i / entries_per_byte; 122 assert(byte < data->size()); 123 size_t bit = (i % entries_per_byte) * bit_size; 124 u8 val = ((*data)[byte] >> bit) & bit_mask; 125 if (static_cast<small_color>(val) == color) { 126 num++; 127 } 128 } 129 return num; 130 } 131 132 small_color get_impl(key_type key) const { 133 auto i = get(index_map, key); 134 assert(i < n); 135 size_t byte = i / entries_per_byte; 136 assert(byte < data->size()); 137 size_t bit = (i % entries_per_byte) * bit_size; 138 u8 val = ((*data)[byte] >> bit) & bit_mask; 139 return static_cast<small_color>(val); 140 } 141 142 void put_impl(key_type key, small_color color) { 143 auto i = get(index_map, key); 144 assert(i < n); 145 size_t byte = i / entries_per_byte; 146 assert(byte < data->size()); 147 size_t bit = (i % entries_per_byte) * bit_size; 148 auto &block = (*data)[byte]; 149 u8 val = static_cast<u8>(color); 150 block = (block & ~(bit_mask << bit)) | (val << bit); 151 } 152 }; 153 154 template<typename IndexMap> 155 small_color get(const small_color_map<IndexMap> &color_map, 156 typename boost::property_traits<IndexMap>::key_type key) { 157 return color_map.get_impl(key); 158 } 159 160 template<typename IndexMap> 161 void put(small_color_map<IndexMap> &color_map, 162 typename boost::property_traits<IndexMap>::key_type key, 163 small_color val) { 164 color_map.put_impl(key, val); 165 } 166 167 template<typename Graph> 168 auto make_small_color_map(const Graph &g) 169 -> small_color_map<decltype(get(vertex_index, g))> { 170 return small_color_map<decltype(get(vertex_index, g))>( 171 num_vertices(g), get(vertex_index, g)); 172 } 173 174 } // namespace ue2 175 176 #endif // GRAPH_SMALL_COLOR_MAP_H 177