libc/test/src/__support/HashTable/group_test.cpp

   1 //===-- Unittests for control group ---------------------------------------===//
   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 #include "src/__support/HashTable/bitmask.h"
  10
  11 #include "src/__support/CPP/bit.h"
  12 #include "src/__support/macros/config.h"
  13 #include "src/stdlib/rand.h"
  14 #include "test/UnitTest/Test.h"
  15 #include <stdint.h>
  16
  17 namespace LIBC_NAMESPACE_DECL {
  18 namespace internal {
  19
  20 struct ByteArray {
  21   alignas(Group) uint8_t data[sizeof(Group) + 1]{};
  22 };
  23
  24 TEST(LlvmLibcHashTableBitMaskTest, Match) {
  25   // Any pair of targets have bit differences not only at the lowest bit.
  26   // No False positive.
  27   uint8_t targets[4] = {0x00, 0x11, 0xFF, 0x0F};
  28   size_t count[4] = {0, 0, 0, 0};
  29   size_t appearance[4][sizeof(Group)];
  30   ByteArray array{};
  31
  32   int data[sizeof(uintptr_t) / sizeof(int)];
  33
  34   for (int &i : data)
  35     i = rand();
  36
  37   uintptr_t random = cpp::bit_cast<uintptr_t>(data);
  38
  39   for (size_t i = 0; i < sizeof(Group); ++i) {
  40     size_t choice = random % 4;
  41     random /= 4;
  42     array.data[i] = targets[choice];
  43     appearance[choice][count[choice]++] = i;
  44   }
  45
  46   for (size_t t = 0; t < sizeof(targets); ++t) {
  47     auto bitmask = Group::load(array.data).match_byte(targets[t]);
  48     for (size_t i = 0; i < count[t]; ++i) {
  49       size_t iterated = 0;
  50       for (size_t position : bitmask) {
  51         ASSERT_EQ(appearance[t][iterated], position);
  52         iterated++;
  53       }
  54       ASSERT_EQ(count[t], iterated);
  55     }
  56   }
  57 }
  58
  59 TEST(LlvmLibcHashTableBitMaskTest, MaskAvailable) {
  60   uint8_t values[3] = {0x00, 0x0F, 0x80};
  61
  62   for (size_t i = 0; i < sizeof(Group); ++i) {
  63     ByteArray array{};
  64
  65     int data[sizeof(uintptr_t) / sizeof(int)];
  66
  67     for (int &j : data)
  68       j = rand();
  69
  70     uintptr_t random = cpp::bit_cast<uintptr_t>(data);
  71
  72     ASSERT_FALSE(Group::load(array.data).mask_available().any_bit_set());
  73
  74     array.data[i] = 0x80;
  75     for (size_t j = 0; j < sizeof(Group); ++j) {
  76       if (i == j)
  77         continue;
  78       size_t sample_space = 2 + (j > i);
  79       size_t choice = random % sample_space;
  80       random /= sizeof(values);
  81       array.data[j] = values[choice];
  82     }
  83
  84     auto mask = Group::load(array.data).mask_available();
  85     ASSERT_TRUE(mask.any_bit_set());
  86     ASSERT_EQ(mask.lowest_set_bit_nonzero(), i);
  87   }
  88 }
  89 } // namespace internal
  90 } // namespace LIBC_NAMESPACE_DECL