llvm/libc/src/__support/HashTable/bitmask.h

//===-- HashTable BitMasks --------------------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_LIBC_SRC___SUPPORT_HASHTABLE_BITMASK_H
#define LLVM_LIBC_SRC___SUPPORT_HASHTABLE_BITMASK_H

#include "src/__support/CPP/bit.h"
#include "src/__support/macros/config.h"
#include "src/__support/macros/properties/cpu_features.h"
#include <stddef.h> // size_t
#include <stdint.h> // uint8_t, uint64_t

namespace LIBC_NAMESPACE_DECL {
namespace internal {

// Implementations of the bitmask.
// The backend word type may vary depending on different microarchitectures.
// For example, with X86 SSE2, the bitmask is just the 16bit unsigned integer
// corresponding to lanes in a SIMD register.
//
// Notice that this implementation is simplified from traditional swisstable:
// since we do not support deletion, we only need to care about if the highest
// bit is set or not:
// =============================
// | Slot Status |   Bitmask   |
// =============================
// |  Available  | 0b1xxx'xxxx |
// |  Occupied   | 0b0xxx'xxxx |
// =============================
template <typename T, size_t WORD_STRIDE> struct BitMaskAdaptor { … };

// Not all bitmasks are iterable --- only those who has only MSB set in each
// lane. Hence, we make the types nomially different to distinguish them.
template <class BitMask> struct IteratableBitMaskAdaptor : public BitMask { … };

} // namespace internal
} // namespace LIBC_NAMESPACE_DECL

#if defined(LIBC_TARGET_CPU_HAS_SSE2) && defined(__LIBC_EXPLICIT_SIMD_OPT)
#include "sse2/bitmask_impl.inc"
#else
#include "generic/bitmask_impl.inc"
#endif

#endif // LLVM_LIBC_SRC___SUPPORT_HASHTABLE_BITMASK_H