1 /**************************************************************************** 2 * Copyright (C) 2018 Intel Corporation. All Rights Reserved. 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 * @file tileset.h 24 * 25 * @brief Custom bitset class for managing locked tiles 26 * 27 ******************************************************************************/ 28 #pragma once 29 30 struct TileSet 31 { ~TileSetTileSet32 ~TileSet() 33 { 34 if (m_bits) 35 { 36 AlignedFree(m_bits); 37 } 38 } setTileSet39 INLINE void set(size_t idx) 40 { 41 _grow(idx); 42 size_t& word = _get_word(idx); 43 word |= (size_t(1) << (idx & BITS_OFFSET)); 44 m_maxSet = std::max(m_maxSet, idx + 1); 45 } getTileSet46 INLINE bool get(size_t idx) 47 { 48 if (idx >= m_size) 49 { 50 return false; 51 } 52 size_t word = _get_word(idx); 53 return 0 != (word & (size_t(1) << (idx & BITS_OFFSET))); 54 } 55 clearTileSet56 INLINE void clear() 57 { 58 if (m_maxSet) 59 { 60 size_t num_words = (m_maxSet + BITS_OFFSET) / BITS_PER_WORD; 61 memset(m_bits, 0, sizeof(size_t) * num_words); 62 m_maxSet = 0; 63 } 64 } 65 66 private: 67 static const size_t BITS_PER_WORD = sizeof(size_t) * 8; 68 static const size_t BITS_OFFSET = BITS_PER_WORD - 1; 69 70 size_t m_size = 0; 71 size_t m_maxSet = 0; 72 size_t* m_bits = nullptr; 73 _get_wordTileSet74 INLINE size_t& _get_word(size_t idx) { return m_bits[idx / BITS_PER_WORD]; } 75 _growTileSet76 void _grow(size_t idx) 77 { 78 if (idx < m_size) 79 { 80 return; 81 } 82 83 size_t new_size = (1 + idx + BITS_OFFSET) & ~BITS_OFFSET; 84 size_t num_words = new_size / BITS_PER_WORD; 85 size_t* newBits = (size_t*)AlignedMalloc(sizeof(size_t) * num_words, 64); 86 size_t copy_words = 0; 87 88 if (m_bits) 89 { 90 copy_words = (m_size + BITS_OFFSET) / BITS_PER_WORD; 91 num_words -= copy_words; 92 memcpy(newBits, m_bits, copy_words * sizeof(size_t)); 93 94 AlignedFree(m_bits); 95 } 96 97 m_bits = newBits; 98 m_size = new_size; 99 100 memset(&m_bits[copy_words], 0, sizeof(size_t) * num_words); 101 } 102 }; 103