libc/test/src/__support/freetrie_test.cpp

   1 //===-- Unittests for a freetrie --------------------------------*- 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 #include <stddef.h>
  10
  11 #include "src/__support/freetrie.h"
  12 #include "test/UnitTest/Test.h"
  13
  14 using LIBC_NAMESPACE::Block;
  15 using LIBC_NAMESPACE::FreeTrie;
  16 using LIBC_NAMESPACE::cpp::byte;
  17 using LIBC_NAMESPACE::cpp::optional;
  18
  19 TEST(LlvmLibcFreeTrie, FindBestFitRoot) {
  20   FreeTrie trie({0, 4096});
  21   EXPECT_EQ(trie.find_best_fit(123), static_cast<FreeTrie::Node *>(nullptr));
  22
  23   byte mem[1024];
  24   optional<Block *> maybeBlock = Block::init(mem);
  25   ASSERT_TRUE(maybeBlock.has_value());
  26   Block *block = *maybeBlock;
  27   trie.push(block);
  28
  29   FreeTrie::Node *root = trie.find_best_fit(0);
  30   ASSERT_EQ(root->block(), block);
  31   EXPECT_EQ(trie.find_best_fit(block->inner_size() - 1), root);
  32   EXPECT_EQ(trie.find_best_fit(block->inner_size()), root);
  33   EXPECT_EQ(trie.find_best_fit(block->inner_size() + 1),
  34             static_cast<FreeTrie::Node *>(nullptr));
  35   EXPECT_EQ(trie.find_best_fit(4095), static_cast<FreeTrie::Node *>(nullptr));
  36 }
  37
  38 TEST(LlvmLibcFreeTrie, FindBestFitLower) {
  39   byte mem[4096];
  40   optional<Block *> maybeBlock = Block::init(mem);
  41   ASSERT_TRUE(maybeBlock.has_value());
  42   Block *lower = *maybeBlock;
  43   maybeBlock = lower->split(512);
  44   ASSERT_TRUE(maybeBlock.has_value());
  45   Block *root = *maybeBlock;
  46
  47   FreeTrie trie({0, 4096});
  48   trie.push(root);
  49   trie.push(lower);
  50
  51   EXPECT_EQ(trie.find_best_fit(0)->block(), lower);
  52 }
  53
  54 TEST(LlvmLibcFreeTrie, FindBestFitUpper) {
  55   byte mem[4096];
  56   optional<Block *> maybeBlock = Block::init(mem);
  57   ASSERT_TRUE(maybeBlock.has_value());
  58   Block *root = *maybeBlock;
  59   maybeBlock = root->split(512);
  60   ASSERT_TRUE(maybeBlock.has_value());
  61   Block *upper = *maybeBlock;
  62
  63   FreeTrie trie({0, 4096});
  64   trie.push(root);
  65   trie.push(upper);
  66
  67   EXPECT_EQ(trie.find_best_fit(root->inner_size() + 1)->block(), upper);
  68   // The upper subtrie should be skipped if it could not contain a better fit.
  69   EXPECT_EQ(trie.find_best_fit(root->inner_size() - 1)->block(), root);
  70 }
  71
  72 TEST(LlvmLibcFreeTrie, FindBestFitLowerAndUpper) {
  73   byte mem[4096];
  74   optional<Block *> maybeBlock = Block::init(mem);
  75   ASSERT_TRUE(maybeBlock.has_value());
  76   Block *root = *maybeBlock;
  77   maybeBlock = root->split(1024);
  78   ASSERT_TRUE(maybeBlock.has_value());
  79   Block *lower = *maybeBlock;
  80   maybeBlock = lower->split(128);
  81   ASSERT_TRUE(maybeBlock.has_value());
  82   Block *upper = *maybeBlock;
  83
  84   FreeTrie trie({0, 4096});
  85   trie.push(root);
  86   trie.push(lower);
  87   trie.push(upper);
  88
  89   // The lower subtrie is examined first.
  90   EXPECT_EQ(trie.find_best_fit(0)->block(), lower);
  91   // The upper subtrie is examined if there are no fits found in the upper
  92   // subtrie.
  93   EXPECT_EQ(trie.find_best_fit(2048)->block(), upper);
  94 }
  95
  96 TEST(LlvmLibcFreeTrie, Remove) {
  97   byte mem[4096];
  98   optional<Block *> maybeBlock = Block::init(mem);
  99   ASSERT_TRUE(maybeBlock.has_value());
 100   Block *small1 = *maybeBlock;
 101   maybeBlock = small1->split(512);
 102   ASSERT_TRUE(maybeBlock.has_value());
 103   Block *small2 = *maybeBlock;
 104   maybeBlock = small2->split(512);
 105   ASSERT_TRUE(maybeBlock.has_value());
 106   ASSERT_EQ(small1->inner_size(), small2->inner_size());
 107   Block *large = *maybeBlock;
 108
 109   // Removing the root empties the trie.
 110   FreeTrie trie({0, 4096});
 111   trie.push(large);
 112   FreeTrie::Node *large_node = trie.find_best_fit(0);
 113   ASSERT_EQ(large_node->block(), large);
 114   trie.remove(large_node);
 115   ASSERT_TRUE(trie.empty());
 116
 117   // Removing the head of a trie list preserves the trie structure.
 118   trie.push(small1);
 119   trie.push(small2);
 120   trie.push(large);
 121   trie.remove(trie.find_best_fit(small1->inner_size()));
 122   EXPECT_EQ(trie.find_best_fit(large->inner_size())->block(), large);
 123   trie.remove(trie.find_best_fit(small1->inner_size()));
 124   EXPECT_EQ(trie.find_best_fit(large->inner_size())->block(), large);
 125 }