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
|
/* SPDX-License-Identifier: GPL-3.0-or-later */
/*
* optimize_unpack_order.c
*
* Copyright (C) 2019 David Oberhollenzer <goliath@infraroot.at>
*/
#include "config.h"
#include "fstree.h"
static bool has_fragment(const fstree_t *fs, const file_info_t *file)
{
if (file->size % fs->block_size == 0)
return false;
return file->fragment_offset < fs->block_size &&
(file->fragment != 0xFFFFFFFF);
}
static int compare_files(const fstree_t *fs, const file_info_t *lhs,
const file_info_t *rhs)
{
/* NOOP < everything else */
if (lhs->input_file == NULL)
return rhs->input_file == NULL ? 0 : -1;
if (rhs->input_file == NULL)
return 1;
/* Files with fragments come first, ordered by ID.
In case of tie, files without data blocks come first,
and the others are ordered by start block. */
if (has_fragment(fs, lhs)) {
if (!(has_fragment(fs, rhs)))
return -1;
if (lhs->fragment < rhs->fragment)
return -1;
if (lhs->fragment > rhs->fragment)
return 1;
if (lhs->size < fs->block_size)
return (rhs->size < fs->block_size) ? 0 : -1;
if (rhs->size < fs->block_size)
return 1;
goto order_by_start;
}
if (has_fragment(fs, rhs))
return 1;
/* order the rest by start block */
order_by_start:
return lhs->startblock < rhs->startblock ? -1 :
lhs->startblock > rhs->startblock ? 1 : 0;
}
/* TODO: unify ad-hoc merge sort with the one in fstree_sort */
static file_info_t *merge(const fstree_t *fs, file_info_t *lhs,
file_info_t *rhs)
{
file_info_t *it;
file_info_t *head = NULL;
file_info_t **next_ptr = &head;
while (lhs != NULL && rhs != NULL) {
if (compare_files(fs, lhs, rhs) <= 0) {
it = lhs;
lhs = lhs->next;
} else {
it = rhs;
rhs = rhs->next;
}
*next_ptr = it;
next_ptr = &it->next;
}
it = (lhs != NULL ? lhs : rhs);
*next_ptr = it;
return head;
}
static file_info_t *list_sort(const fstree_t *fs, file_info_t *head)
{
file_info_t *it, *half, *prev;
it = half = prev = head;
while (it != NULL) {
prev = half;
half = half->next;
it = it->next;
if (it != NULL) {
it = it->next;
}
}
// half refers to the (count/2)'th element ROUNDED UP.
// It will be null therefore only in the empty and the
// single element list
if (half == NULL) {
return head;
}
prev->next = NULL;
return merge(fs, list_sort(fs, head), list_sort(fs, half));
}
file_info_t *optimize_unpack_order(fstree_t *fs)
{
file_info_t *file_list;
file_list = list_sort(fs, fs->files);
while (file_list != NULL && file_list->input_file == NULL)
file_list = file_list->next;
fs->files = NULL;
return file_list;
}
|
