From 336a05a544ea8773653faa9a9d5078afaa839ff2 Mon Sep 17 00:00:00 2001 From: David Oberhollenzer Date: Thu, 19 Sep 2019 18:28:48 +0200 Subject: Move "optimize unpack order" to from fstree to rdsquashfs Signed-off-by: David Oberhollenzer --- lib/fstree/Makemodule.am | 1 - lib/fstree/optimize_unpack_order.c | 119 ------------------------------------- 2 files changed, 120 deletions(-) delete mode 100644 lib/fstree/optimize_unpack_order.c (limited to 'lib') diff --git a/lib/fstree/Makemodule.am b/lib/fstree/Makemodule.am index c3c56fb..00150fd 100644 --- a/lib/fstree/Makemodule.am +++ b/lib/fstree/Makemodule.am @@ -5,7 +5,6 @@ libfstree_a_SOURCES += lib/fstree/node_stat.c lib/fstree/mknode.c libfstree_a_SOURCES += lib/fstree/add_by_path.c lib/fstree/xattr.c libfstree_a_SOURCES += lib/fstree/node_from_path.c include/fstree.h libfstree_a_SOURCES += lib/fstree/gen_file_list.c -libfstree_a_SOURCES += lib/fstree/optimize_unpack_order.c libfstree_a_SOURCES += lib/fstree/canonicalize_name.c libfstree_a_SOURCES += lib/fstree/source_date_epoch.c libfstree_a_CFLAGS = $(AM_CFLAGS) $(LIBSELINUX_CFLAGS) diff --git a/lib/fstree/optimize_unpack_order.c b/lib/fstree/optimize_unpack_order.c deleted file mode 100644 index 972d4b3..0000000 --- a/lib/fstree/optimize_unpack_order.c +++ /dev/null @@ -1,119 +0,0 @@ -/* SPDX-License-Identifier: GPL-3.0-or-later */ -/* - * optimize_unpack_order.c - * - * Copyright (C) 2019 David Oberhollenzer - */ -#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; -} -- cgit v1.2.3