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