jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2022, the SerenityOS developers.
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include "Tree.h"
8#include <AK/Function.h>
9#include <AK/HashMap.h>
10#include <AK/Queue.h>
11#include <AK/QuickSort.h>
12#include <LibCore/DirIterator.h>
13
14#include <fcntl.h>
15#include <sys/stat.h>
16
17static constexpr size_t FILES_ENCOUNTERED_UPDATE_STEP_SIZE = 25;
18
19long long int TreeNode::update_totals()
20{
21 long long int result = 0;
22 if (m_children) {
23 for (auto& child : *m_children) {
24 result += child.update_totals();
25 }
26 m_area = result;
27 } else {
28 result = m_area;
29 }
30 return result;
31}
32
33void TreeNode::sort_children_by_area() const
34{
35 if (m_children) {
36 Vector<TreeNode>* children = const_cast<Vector<TreeNode>*>(m_children.ptr());
37 quick_sort(*children, [](auto& a, auto& b) { return b.m_area < a.m_area; });
38 }
39}
40
41struct QueueEntry {
42 QueueEntry(DeprecatedString path, TreeNode* node)
43 : path(move(path))
44 , node(node) {};
45 DeprecatedString path;
46 TreeNode* node { nullptr };
47};
48
49static MountInfo* find_mount_for_path(DeprecatedString path, Vector<MountInfo>& mounts)
50{
51 MountInfo* result = nullptr;
52 size_t length = 0;
53 for (auto& mount_info : mounts) {
54 DeprecatedString& mount_point = mount_info.mount_point;
55 if (path.starts_with(mount_point)) {
56 if (!result || mount_point.length() > length) {
57 result = &mount_info;
58 length = mount_point.length();
59 }
60 }
61 }
62 return result;
63}
64
65HashMap<int, int> TreeNode::populate_filesize_tree(Vector<MountInfo>& mounts, Function<void(size_t)> on_progress)
66{
67 VERIFY(!m_name.ends_with('/'));
68
69 Queue<QueueEntry> queue;
70 queue.enqueue(QueueEntry(m_name, this));
71 size_t files_encountered_count = 0;
72 HashMap<int, int> error_accumulator;
73
74 StringBuilder builder = StringBuilder();
75 builder.append(m_name);
76 builder.append('/');
77 MountInfo* root_mount_info = find_mount_for_path(builder.to_deprecated_string(), mounts);
78 if (!root_mount_info) {
79 return error_accumulator;
80 }
81 while (!queue.is_empty()) {
82 QueueEntry queue_entry = queue.dequeue();
83
84 builder.clear();
85 builder.append(queue_entry.path);
86 builder.append('/');
87
88 MountInfo* mount_info = find_mount_for_path(builder.to_deprecated_string(), mounts);
89 if (!mount_info || (mount_info != root_mount_info && mount_info->source != root_mount_info->source)) {
90 continue;
91 }
92
93 Core::DirIterator dir_iterator(builder.to_deprecated_string(), Core::DirIterator::SkipParentAndBaseDir);
94 if (dir_iterator.has_error()) {
95 auto error_code = dir_iterator.error().code();
96 int error_sum = error_accumulator.get(error_code).value_or(0);
97 error_accumulator.set(error_code, error_sum + 1);
98 } else {
99 queue_entry.node->m_children = make<Vector<TreeNode>>();
100 while (dir_iterator.has_next()) {
101 queue_entry.node->m_children->append(TreeNode(dir_iterator.next_path()));
102 }
103 for (auto& child : *queue_entry.node->m_children) {
104 files_encountered_count += 1;
105 if (!(files_encountered_count % FILES_ENCOUNTERED_UPDATE_STEP_SIZE))
106 on_progress(files_encountered_count);
107
108 DeprecatedString& name = child.m_name;
109 int name_len = name.length();
110 builder.append(name);
111 struct stat st;
112 int stat_result = fstatat(dir_iterator.fd(), name.characters(), &st, AT_SYMLINK_NOFOLLOW);
113 if (stat_result < 0) {
114 int error_sum = error_accumulator.get(errno).value_or(0);
115 error_accumulator.set(errno, error_sum + 1);
116 } else {
117 if (S_ISDIR(st.st_mode)) {
118 queue.enqueue(QueueEntry(builder.to_deprecated_string(), &child));
119 } else {
120 child.m_area = st.st_size;
121 }
122 }
123 builder.trim(name_len);
124 }
125 }
126 }
127
128 update_totals();
129 return error_accumulator;
130}
131
132Optional<TreeNode const&> TreeNode::child_with_name(DeprecatedString name) const
133{
134 for (auto& child : *m_children) {
135 if (child.name() == name)
136 return child;
137 }
138
139 return {};
140}