126 lines · 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-exception6//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 upper92 // 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