1 //===-- HashTable BitMasks --------------------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef LLVM_LIBC_SRC___SUPPORT_HASHTABLE_BITMASK_H 10 #define LLVM_LIBC_SRC___SUPPORT_HASHTABLE_BITMASK_H 11 12 #include "src/__support/CPP/bit.h" 13 #include "src/__support/macros/config.h" 14 #include "src/__support/macros/properties/cpu_features.h" 15 #include <stddef.h> // size_t 16 #include <stdint.h> // uint8_t, uint64_t 17 18 namespace LIBC_NAMESPACE_DECL { 19 namespace internal { 20 21 // Implementations of the bitmask. 22 // The backend word type may vary depending on different microarchitectures. 23 // For example, with X86 SSE2, the bitmask is just the 16bit unsigned integer 24 // corresponding to lanes in a SIMD register. 25 // 26 // Notice that this implementation is simplified from traditional swisstable: 27 // since we do not support deletion, we only need to care about if the highest 28 // bit is set or not: 29 // ============================= 30 // | Slot Status | Bitmask | 31 // ============================= 32 // | Available | 0b1xxx'xxxx | 33 // | Occupied | 0b0xxx'xxxx | 34 // ============================= 35 template <typename T, size_t WORD_STRIDE> struct BitMaskAdaptor { 36 // A stride in the bitmask may use multiple bits. 37 LIBC_INLINE_VAR constexpr static size_t STRIDE = WORD_STRIDE; 38 39 T word; 40 41 // Check if any bit is set inside the word. any_bit_setBitMaskAdaptor42 LIBC_INLINE constexpr bool any_bit_set() const { return word != 0; } 43 44 // Count trailing zeros with respect to stride. (Assume the bitmask is none 45 // zero.) lowest_set_bit_nonzeroBitMaskAdaptor46 LIBC_INLINE constexpr size_t lowest_set_bit_nonzero() const { 47 return cpp::countr_zero<T>(word) / WORD_STRIDE; 48 } 49 }; 50 51 // Not all bitmasks are iterable --- only those who has only MSB set in each 52 // lane. Hence, we make the types nomially different to distinguish them. 53 template <class BitMask> struct IteratableBitMaskAdaptor : public BitMask { 54 // Use the bitmask as an iterator. Update the state and return current lowest 55 // set bit. To make the bitmask iterable, each stride must contain 0 or exact 56 // 1 set bit. remove_lowest_bitIteratableBitMaskAdaptor57 LIBC_INLINE void remove_lowest_bit() { 58 // Remove the last set bit inside the word: 59 // word = 011110100 (original value) 60 // word - 1 = 011110011 (invert all bits up to the last set bit) 61 // word & (word - 1) = 011110000 (value with the last bit cleared) 62 this->word = this->word & (this->word - 1); 63 } 64 using value_type = size_t; 65 using iterator = BitMask; 66 using const_iterator = BitMask; 67 LIBC_INLINE size_t operator*() const { 68 return this->lowest_set_bit_nonzero(); 69 } 70 LIBC_INLINE IteratableBitMaskAdaptor &operator++() { 71 this->remove_lowest_bit(); 72 return *this; 73 } beginIteratableBitMaskAdaptor74 LIBC_INLINE IteratableBitMaskAdaptor begin() { return *this; } endIteratableBitMaskAdaptor75 LIBC_INLINE IteratableBitMaskAdaptor end() { return {BitMask{0}}; } 76 LIBC_INLINE bool operator==(const IteratableBitMaskAdaptor &other) { 77 return this->word == other.word; 78 } 79 LIBC_INLINE bool operator!=(const IteratableBitMaskAdaptor &other) { 80 return this->word != other.word; 81 } 82 }; 83 84 } // namespace internal 85 } // namespace LIBC_NAMESPACE_DECL 86 87 #if defined(LIBC_TARGET_CPU_HAS_SSE2) && defined(__LIBC_EXPLICIT_SIMD_OPT) 88 #include "sse2/bitmask_impl.inc" 89 #else 90 #include "generic/bitmask_impl.inc" 91 #endif 92 93 #endif // LLVM_LIBC_SRC___SUPPORT_HASHTABLE_BITMASK_H 94