94 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_LIBC_SRC___SUPPORT_HASHTABLE_BITMASK_H10#define LLVM_LIBC_SRC___SUPPORT_HASHTABLE_BITMASK_H11 12#include "hdr/stdint_proxy.h" // uint8_t, uint64_t13#include "src/__support/CPP/bit.h"14#include "src/__support/macros/config.h"15#include "src/__support/macros/properties/cpu_features.h"16#include <stddef.h> // size_t17 18namespace LIBC_NAMESPACE_DECL {19namespace 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 integer24// 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 highest28// bit is set or not:29// =============================30// | Slot Status | Bitmask |31// =============================32// | Available | 0b1xxx'xxxx |33// | Occupied | 0b0xxx'xxxx |34// =============================35template <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.42 LIBC_INLINE constexpr bool any_bit_set() const { return word != 0; }43 44 // Count trailing zeros with respect to stride. (Assume the bitmask is none45 // zero.)46 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 each52// lane. Hence, we make the types nomially different to distinguish them.53template <class BitMask> struct IteratableBitMaskAdaptor : public BitMask {54 // Use the bitmask as an iterator. Update the state and return current lowest55 // set bit. To make the bitmask iterable, each stride must contain 0 or exact56 // 1 set bit.57 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 }74 LIBC_INLINE IteratableBitMaskAdaptor begin() { return *this; }75 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 internal85} // namespace LIBC_NAMESPACE_DECL86 87#if defined(LIBC_TARGET_CPU_HAS_SSE2) && defined(__LIBC_EXPLICIT_SIMD_OPT)88#include "sse2/bitmask_impl.inc"89#else90#include "generic/bitmask_impl.inc"91#endif92 93#endif // LLVM_LIBC_SRC___SUPPORT_HASHTABLE_BITMASK_H94