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

source code of libc/src/__support/HashTable/bitmask.h