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
14using LIBC_NAMESPACE::Block;
15using LIBC_NAMESPACE::FreeTrie;
16using LIBC_NAMESPACE::cpp::byte;
17using LIBC_NAMESPACE::cpp::optional;
18
19TEST(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
38TEST(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
54TEST(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
72TEST(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
96TEST(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

source code of libc/test/src/__support/freetrie_test.cpp