From 464df1d5e5ab1322e2dd0a7796939fff1aeefa9a Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 17:49:25 +0200 Subject: Adding upstream version 1.47.0. Signed-off-by: Daniel Baumann --- lib/ext2fs/dblist.c | 403 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 403 insertions(+) create mode 100644 lib/ext2fs/dblist.c (limited to 'lib/ext2fs/dblist.c') diff --git a/lib/ext2fs/dblist.c b/lib/ext2fs/dblist.c new file mode 100644 index 0000000..bbdb221 --- /dev/null +++ b/lib/ext2fs/dblist.c @@ -0,0 +1,403 @@ +/* + * dblist.c -- directory block list functions + * + * Copyright 1997 by Theodore Ts'o + * + * %Begin-Header% + * This file may be redistributed under the terms of the GNU Library + * General Public License, version 2. + * %End-Header% + */ + +#include "config.h" +#include +#if HAVE_UNISTD_H +#include +#endif +#include +#include + +#include "ext2_fs.h" +#include "ext2fsP.h" + +static EXT2_QSORT_TYPE dir_block_cmp(const void *a, const void *b); +static EXT2_QSORT_TYPE dir_block_cmp2(const void *a, const void *b); +static EXT2_QSORT_TYPE (*sortfunc32)(const void *a, const void *b); + +/* + * helper function for making a new directory block list (for + * initialize and copy). + */ +static errcode_t make_dblist(ext2_filsys fs, ext2_ino_t size, + ext2_ino_t count, + struct ext2_db_entry2 *list, + ext2_dblist *ret_dblist) +{ + ext2_dblist dblist = NULL; + errcode_t retval; + ext2_ino_t num_dirs; + size_t len; + + EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS); + + if ((ret_dblist == 0) && fs->dblist && + (fs->dblist->magic == EXT2_ET_MAGIC_DBLIST)) + return 0; + + retval = ext2fs_get_mem(sizeof(struct ext2_struct_dblist), &dblist); + if (retval) + goto cleanup; + memset(dblist, 0, sizeof(struct ext2_struct_dblist)); + + dblist->magic = EXT2_ET_MAGIC_DBLIST; + dblist->fs = fs; + if (size) + dblist->size = size; + else { + retval = ext2fs_get_num_dirs(fs, &num_dirs); + if (retval) + goto cleanup; + dblist->size = (num_dirs * 2) + 12; + } + len = (size_t) sizeof(struct ext2_db_entry2) * dblist->size; + dblist->count = count; + retval = ext2fs_get_array(dblist->size, sizeof(struct ext2_db_entry2), + &dblist->list); + if (retval) + goto cleanup; + + if (list) + memcpy(dblist->list, list, len); + else + memset(dblist->list, 0, len); + if (ret_dblist) + *ret_dblist = dblist; + else + fs->dblist = dblist; + return 0; +cleanup: + if (dblist) + ext2fs_free_mem(&dblist); + return retval; +} + +/* + * Initialize a directory block list + */ +errcode_t ext2fs_init_dblist(ext2_filsys fs, ext2_dblist *ret_dblist) +{ + ext2_dblist dblist; + errcode_t retval; + + retval = make_dblist(fs, 0, 0, 0, &dblist); + if (retval) + return retval; + + dblist->sorted = 1; + if (ret_dblist) + *ret_dblist = dblist; + else + fs->dblist = dblist; + + return 0; +} + +/* + * Copy a directory block list + */ +errcode_t ext2fs_copy_dblist(ext2_dblist src, ext2_dblist *dest) +{ + ext2_dblist dblist; + errcode_t retval; + + retval = make_dblist(src->fs, src->size, src->count, src->list, + &dblist); + if (retval) + return retval; + dblist->sorted = src->sorted; + *dest = dblist; + return 0; +} + +/* + * Close a directory block list + * + * (moved to closefs.c) + */ + + +/* + * Add a directory block to the directory block list + */ +errcode_t ext2fs_add_dir_block2(ext2_dblist dblist, ext2_ino_t ino, + blk64_t blk, e2_blkcnt_t blockcnt) +{ + struct ext2_db_entry2 *new_entry; + errcode_t retval; + unsigned long old_size; + + EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST); + + if (dblist->count >= dblist->size) { + old_size = dblist->size * sizeof(struct ext2_db_entry2); + dblist->size += dblist->size > 200 ? dblist->size / 2 : 100; + retval = ext2fs_resize_mem(old_size, (size_t) dblist->size * + sizeof(struct ext2_db_entry2), + &dblist->list); + if (retval) { + dblist->size = old_size / sizeof(struct ext2_db_entry2); + return retval; + } + } + new_entry = dblist->list + ( dblist->count++); + new_entry->blk = blk; + new_entry->ino = ino; + new_entry->blockcnt = blockcnt; + + dblist->sorted = 0; + + return 0; +} + +/* + * Change the directory block to the directory block list + */ +errcode_t ext2fs_set_dir_block2(ext2_dblist dblist, ext2_ino_t ino, + blk64_t blk, e2_blkcnt_t blockcnt) +{ + dgrp_t i; + + EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST); + + for (i=0; i < dblist->count; i++) { + if ((dblist->list[i].ino != ino) || + (dblist->list[i].blockcnt != blockcnt)) + continue; + dblist->list[i].blk = blk; + dblist->sorted = 0; + return 0; + } + return EXT2_ET_DB_NOT_FOUND; +} + +void ext2fs_dblist_sort2(ext2_dblist dblist, + EXT2_QSORT_TYPE (*sortfunc)(const void *, + const void *)) +{ + if (!sortfunc) + sortfunc = dir_block_cmp2; + qsort(dblist->list, (size_t) dblist->count, + sizeof(struct ext2_db_entry2), sortfunc); + dblist->sorted = 1; +} + +/* + * This function iterates over the directory block list + */ +errcode_t ext2fs_dblist_iterate3(ext2_dblist dblist, + int (*func)(ext2_filsys fs, + struct ext2_db_entry2 *db_info, + void *priv_data), + unsigned long long start, + unsigned long long count, + void *priv_data) +{ + unsigned long long i, end; + int ret; + + EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST); + + end = start + count; + if (!dblist->sorted) + ext2fs_dblist_sort2(dblist, 0); + if (end > dblist->count) + end = dblist->count; + for (i = start; i < end; i++) { + ret = (*func)(dblist->fs, &dblist->list[i], priv_data); + if (ret & DBLIST_ABORT) + return 0; + } + return 0; +} + +errcode_t ext2fs_dblist_iterate2(ext2_dblist dblist, + int (*func)(ext2_filsys fs, + struct ext2_db_entry2 *db_info, + void *priv_data), + void *priv_data) +{ + return ext2fs_dblist_iterate3(dblist, func, 0, dblist->count, + priv_data); +} + +static EXT2_QSORT_TYPE dir_block_cmp2(const void *a, const void *b) +{ + const struct ext2_db_entry2 *db_a = + (const struct ext2_db_entry2 *) a; + const struct ext2_db_entry2 *db_b = + (const struct ext2_db_entry2 *) b; + + if (db_a->blk != db_b->blk) + return (int) (db_a->blk - db_b->blk); + + if (db_a->ino != db_b->ino) + return (int) (db_a->ino - db_b->ino); + + return (db_a->blockcnt - db_b->blockcnt); +} + +blk64_t ext2fs_dblist_count2(ext2_dblist dblist) +{ + return dblist->count; +} + +errcode_t ext2fs_dblist_get_last2(ext2_dblist dblist, + struct ext2_db_entry2 **entry) +{ + EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST); + + if (dblist->count == 0) + return EXT2_ET_DBLIST_EMPTY; + + if (entry) + *entry = dblist->list + ( dblist->count-1); + return 0; +} + +errcode_t ext2fs_dblist_drop_last(ext2_dblist dblist) +{ + EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST); + + if (dblist->count == 0) + return EXT2_ET_DBLIST_EMPTY; + + dblist->count--; + return 0; +} + +/* + * Legacy 32-bit versions + */ + +/* + * Add a directory block to the directory block list + */ +errcode_t ext2fs_add_dir_block(ext2_dblist dblist, ext2_ino_t ino, blk_t blk, + int blockcnt) +{ + return ext2fs_add_dir_block2(dblist, ino, blk, blockcnt); +} + +/* + * Change the directory block to the directory block list + */ +errcode_t ext2fs_set_dir_block(ext2_dblist dblist, ext2_ino_t ino, blk_t blk, + int blockcnt) +{ + return ext2fs_set_dir_block2(dblist, ino, blk, blockcnt); +} + +void ext2fs_dblist_sort(ext2_dblist dblist, + EXT2_QSORT_TYPE (*sortfunc)(const void *, + const void *)) +{ + if (sortfunc) { + sortfunc32 = sortfunc; + sortfunc = dir_block_cmp; + } else + sortfunc = dir_block_cmp2; + qsort(dblist->list, (size_t) dblist->count, + sizeof(struct ext2_db_entry2), sortfunc); + dblist->sorted = 1; +} + +/* + * This function iterates over the directory block list + */ +struct iterate_passthrough { + int (*func)(ext2_filsys fs, + struct ext2_db_entry *db_info, + void *priv_data); + void *priv_data; +}; + +static int passthrough_func(ext2_filsys fs, + struct ext2_db_entry2 *db_info, + void *priv_data) +{ + struct iterate_passthrough *p = priv_data; + struct ext2_db_entry db; + int ret; + + db.ino = db_info->ino; + db.blk = (blk_t) db_info->blk; + db.blockcnt = (int) db_info->blockcnt; + ret = (p->func)(fs, &db, p->priv_data); + db_info->ino = db.ino; + db_info->blk = db.blk; + db_info->blockcnt = db.blockcnt; + return ret; +} + +errcode_t ext2fs_dblist_iterate(ext2_dblist dblist, + int (*func)(ext2_filsys fs, + struct ext2_db_entry *db_info, + void *priv_data), + void *priv_data) +{ + struct iterate_passthrough pass; + + EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST); + pass.func = func; + pass.priv_data = priv_data; + + return ext2fs_dblist_iterate2(dblist, passthrough_func, &pass); +} + +static EXT2_QSORT_TYPE dir_block_cmp(const void *a, const void *b) +{ + const struct ext2_db_entry2 *db_a = + (const struct ext2_db_entry2 *) a; + const struct ext2_db_entry2 *db_b = + (const struct ext2_db_entry2 *) b; + + struct ext2_db_entry a32, b32; + + a32.ino = db_a->ino; a32.blk = db_a->blk; + a32.blockcnt = db_a->blockcnt; + + b32.ino = db_b->ino; b32.blk = db_b->blk; + b32.blockcnt = db_b->blockcnt; + + return sortfunc32(&a32, &b32); +} + +int ext2fs_dblist_count(ext2_dblist dblist) +{ + return dblist->count; +} + +errcode_t ext2fs_dblist_get_last(ext2_dblist dblist, + struct ext2_db_entry **entry) +{ + static struct ext2_db_entry ret_entry; + struct ext2_db_entry2 *last; + + EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST); + + if (dblist->count == 0) + return EXT2_ET_DBLIST_EMPTY; + + if (!entry) + return 0; + + last = dblist->list + dblist->count -1; + + ret_entry.ino = last->ino; + ret_entry.blk = last->blk; + ret_entry.blockcnt = last->blockcnt; + *entry = &ret_entry; + + return 0; +} + -- cgit v1.2.3