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
TEST(LlvmLibcFreeTrie,FindBestFitRoot)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
TEST(LlvmLibcFreeTrie,FindBestFitLower)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
TEST(LlvmLibcFreeTrie,FindBestFitUpper)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
TEST(LlvmLibcFreeTrie,FindBestFitLowerAndUpper)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
TEST(LlvmLibcFreeTrie,Remove)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