1 /* 2 * Copyright Michael Schellenberger Costa 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining a 5 * copy of this software and associated documentation files (the "Software"), 6 * to deal in the Software without restriction, including without limitation 7 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8 * and/or sell copies of the Software, and to permit persons to whom the 9 * Software is furnished to do so, subject to the following conditions: 10 * 11 * The above copyright notice and this permission notice (including the next 12 * paragraph) shall be included in all copies or substantial portions of the 13 * Software. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 21 * IN THE SOFTWARE. 22 * 23 */ 24 25 #ifndef ACO_UTIL_H 26 #define ACO_UTIL_H 27 28 #include <cassert> 29 #include <iterator> 30 #include <vector> 31 32 namespace aco { 33 34 /*! \brief Definition of a span object 35 * 36 * \details A "span" is an "array view" type for holding a view of contiguous 37 * data. The "span" object does not own the data itself. 38 */ 39 template <typename T> 40 class span { 41 public: 42 using value_type = T; 43 using pointer = value_type*; 44 using const_pointer = const value_type*; 45 using reference = value_type&; 46 using const_reference = const value_type&; 47 using iterator = pointer; 48 using const_iterator = const_pointer; 49 using reverse_iterator = std::reverse_iterator<iterator>; 50 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 51 using size_type = uint16_t; 52 using difference_type = ptrdiff_t; 53 54 /*! \brief Compiler generated default constructor 55 */ 56 constexpr span() = default; 57 58 /*! \brief Constructor taking a pointer and the length of the span 59 * \param[in] data Pointer to the underlying data array 60 * \param[in] length The size of the span 61 */ span(uint16_t offset,const size_type length)62 constexpr span(uint16_t offset, const size_type length) 63 : offset{ offset } , length{ length } {} 64 65 /*! \brief Returns an iterator to the begin of the span 66 * \return data 67 */ begin()68 constexpr iterator begin() noexcept { 69 return (pointer)((uintptr_t)this + offset); 70 } 71 72 /*! \brief Returns a const_iterator to the begin of the span 73 * \return data 74 */ begin()75 constexpr const_iterator begin() const noexcept { 76 return (const_pointer)((uintptr_t)this + offset); 77 } 78 79 /*! \brief Returns an iterator to the end of the span 80 * \return data + length 81 */ end()82 constexpr iterator end() noexcept { 83 return std::next(begin(), length); 84 } 85 86 /*! \brief Returns a const_iterator to the end of the span 87 * \return data + length 88 */ end()89 constexpr const_iterator end() const noexcept { 90 return std::next(begin(), length); 91 } 92 93 /*! \brief Returns a const_iterator to the begin of the span 94 * \return data 95 */ cbegin()96 constexpr const_iterator cbegin() const noexcept { 97 return begin(); 98 } 99 100 /*! \brief Returns a const_iterator to the end of the span 101 * \return data + length 102 */ cend()103 constexpr const_iterator cend() const noexcept { 104 return std::next(begin(), length); 105 } 106 107 /*! \brief Returns a reverse_iterator to the end of the span 108 * \return reverse_iterator(end()) 109 */ rbegin()110 constexpr reverse_iterator rbegin() noexcept { 111 return reverse_iterator(end()); 112 } 113 114 /*! \brief Returns a const_reverse_iterator to the end of the span 115 * \return reverse_iterator(end()) 116 */ rbegin()117 constexpr const_reverse_iterator rbegin() const noexcept { 118 return const_reverse_iterator(end()); 119 } 120 121 /*! \brief Returns a reverse_iterator to the begin of the span 122 * \return reverse_iterator(begin()) 123 */ rend()124 constexpr reverse_iterator rend() noexcept { 125 return reverse_iterator(begin()); 126 } 127 128 /*! \brief Returns a const_reverse_iterator to the begin of the span 129 * \return reverse_iterator(begin()) 130 */ rend()131 constexpr const_reverse_iterator rend() const noexcept { 132 return const_reverse_iterator(begin()); 133 } 134 135 /*! \brief Returns a const_reverse_iterator to the end of the span 136 * \return rbegin() 137 */ crbegin()138 constexpr const_reverse_iterator crbegin() const noexcept { 139 return const_reverse_iterator(cend()); 140 } 141 142 /*! \brief Returns a const_reverse_iterator to the begin of the span 143 * \return rend() 144 */ crend()145 constexpr const_reverse_iterator crend() const noexcept { 146 return const_reverse_iterator(cbegin()); 147 } 148 149 /*! \brief Unchecked access operator 150 * \param[in] index Index of the element we want to access 151 * \return *(std::next(data, index)) 152 */ 153 constexpr reference operator[](const size_type index) noexcept { 154 assert(length > index); 155 return *(std::next(begin(), index)); 156 } 157 158 /*! \brief Unchecked const access operator 159 * \param[in] index Index of the element we want to access 160 * \return *(std::next(data, index)) 161 */ 162 constexpr const_reference operator[](const size_type index) const noexcept { 163 assert(length > index); 164 return *(std::next(begin(), index)); 165 } 166 167 /*! \brief Returns a reference to the last element of the span 168 * \return *(std::next(data, length - 1)) 169 */ back()170 constexpr reference back() noexcept { 171 assert(length > 0); 172 return *(std::next(begin(), length - 1)); 173 } 174 175 /*! \brief Returns a const_reference to the last element of the span 176 * \return *(std::next(data, length - 1)) 177 */ back()178 constexpr const_reference back() const noexcept { 179 assert(length > 0); 180 return *(std::next(begin(), length - 1)); 181 } 182 183 /*! \brief Returns a reference to the first element of the span 184 * \return *begin() 185 */ front()186 constexpr reference front() noexcept { 187 assert(length > 0); 188 return *begin(); 189 } 190 191 /*! \brief Returns a const_reference to the first element of the span 192 * \return *cbegin() 193 */ front()194 constexpr const_reference front() const noexcept { 195 assert(length > 0); 196 return *cbegin(); 197 } 198 199 /*! \brief Returns true if the span is empty 200 * \return length == 0 201 */ empty()202 constexpr bool empty() const noexcept { 203 return length == 0; 204 } 205 206 /*! \brief Returns the size of the span 207 * \return length == 0 208 */ size()209 constexpr size_type size() const noexcept { 210 return length; 211 } 212 213 /*! \brief Decreases the size of the span by 1 214 */ pop_back()215 constexpr void pop_back() noexcept { 216 assert(length > 0); 217 --length; 218 } 219 220 /*! \brief Adds an element to the end of the span 221 */ push_back(const_reference val)222 constexpr void push_back(const_reference val) noexcept { 223 *std::next(begin(), length++) = val; 224 } 225 226 /*! \brief Clears the span 227 */ clear()228 constexpr void clear() noexcept { 229 offset = 0; 230 length = 0; 231 } 232 233 private: 234 uint16_t offset{ 0 }; //!> Byte offset from span to data 235 size_type length{ 0 }; //!> Size of the span 236 }; 237 238 /* 239 * Cache-friendly set of 32-bit IDs with O(1) insert/erase/lookup and 240 * the ability to efficiently iterate over contained elements. 241 * 242 * Internally implemented as a bit vector: If the set contains an ID, the 243 * corresponding bit is set. It doesn't use std::vector<bool> since we then 244 * couldn't efficiently iterate over the elements. 245 * 246 * The interface resembles a subset of std::set/std::unordered_set. 247 */ 248 struct IDSet { 249 struct Iterator { 250 const IDSet *set; 251 union { 252 struct { 253 uint32_t bit:6; 254 uint32_t word:26; 255 }; 256 uint32_t id; 257 }; 258 259 Iterator& operator ++(); 260 261 bool operator != (const Iterator& other) const; 262 263 uint32_t operator * () const; 264 }; 265 countIDSet266 size_t count(uint32_t id) const { 267 if (id >= words.size() * 64) 268 return 0; 269 270 return words[id / 64u] & (1ull << (id % 64u)) ? 1 : 0; 271 } 272 findIDSet273 Iterator find(uint32_t id) const { 274 if (!count(id)) 275 return end(); 276 277 Iterator it; 278 it.set = this; 279 it.bit = id % 64u; 280 it.word = id / 64u; 281 return it; 282 } 283 insertIDSet284 std::pair<Iterator, bool> insert(uint32_t id) { 285 if (words.size() * 64u <= id) 286 words.resize(DIV_ROUND_UP(id + 1, 64u)); 287 288 Iterator it; 289 it.set = this; 290 it.bit = id % 64u; 291 it.word = id / 64u; 292 293 uint64_t mask = 1ull << it.bit; 294 if (words[it.word] & mask) 295 return std::make_pair(it, false); 296 297 words[it.word] |= mask; 298 bits_set++; 299 return std::make_pair(it, true); 300 } 301 eraseIDSet302 size_t erase(uint32_t id) { 303 if (!count(id)) 304 return 0; 305 306 words[id / 64u] ^= 1ull << (id % 64u); 307 bits_set--; 308 return 1; 309 } 310 cbeginIDSet311 Iterator cbegin() const { 312 Iterator it; 313 it.set = this; 314 for (size_t i = 0; i < words.size(); i++) { 315 if (words[i]) { 316 it.word = i; 317 it.bit = ffsll(words[i]) - 1; 318 return it; 319 } 320 } 321 return end(); 322 } 323 cendIDSet324 Iterator cend() const { 325 Iterator it; 326 it.set = this; 327 it.word = words.size(); 328 it.bit = 0; 329 return it; 330 } 331 beginIDSet332 Iterator begin() const { 333 return cbegin(); 334 } 335 endIDSet336 Iterator end() const { 337 return cend(); 338 } 339 emptyIDSet340 bool empty() const { 341 return bits_set == 0; 342 } 343 sizeIDSet344 size_t size() const { 345 return bits_set; 346 } 347 348 std::vector<uint64_t> words; 349 uint32_t bits_set; 350 }; 351 352 inline IDSet::Iterator& IDSet::Iterator::operator ++() { 353 uint64_t m = set->words[word]; 354 m &= ~((2ull << bit) - 1ull); 355 if (!m) { 356 /* don't continue past the end */ 357 if (word == set->words.size()) 358 return *this; 359 360 word++; 361 for (; word < set->words.size(); word++) { 362 if (set->words[word]) { 363 bit = ffsll(set->words[word]) - 1; 364 return *this; 365 } 366 } 367 bit = 0; 368 } else { 369 bit = ffsll(m) - 1; 370 } 371 return *this; 372 } 373 374 inline bool IDSet::Iterator::operator != (const IDSet::Iterator& other) const { 375 assert(set == other.set); 376 return id != other.id; 377 } 378 379 inline uint32_t IDSet::Iterator::operator * () const { 380 return (word << 6) | bit; 381 } 382 383 } // namespace aco 384 385 #endif // ACO_UTIL_H 386