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 } 126