| /* |
| * 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 <stdio.h> |
| #if HAVE_UNISTD_H |
| #include <unistd.h> |
| #endif |
| #include <string.h> |
| #include <time.h> |
| |
| #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); |
| |
| /* |
| * Returns the number of directories in the filesystem as reported by |
| * the group descriptors. Of course, the group descriptors could be |
| * wrong! |
| */ |
| errcode_t ext2fs_get_num_dirs(ext2_filsys fs, ext2_ino_t *ret_num_dirs) |
| { |
| dgrp_t i; |
| ext2_ino_t num_dirs, max_dirs; |
| |
| EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS); |
| |
| num_dirs = 0; |
| max_dirs = fs->super->s_inodes_per_group; |
| for (i = 0; i < fs->group_desc_count; i++) { |
| if (ext2fs_bg_used_dirs_count(fs, i) > max_dirs) |
| num_dirs += max_dirs / 8; |
| else |
| num_dirs += ext2fs_bg_used_dirs_count(fs, i); |
| } |
| if (num_dirs > fs->super->s_inodes_count) |
| num_dirs = fs->super->s_inodes_count; |
| |
| *ret_num_dirs = num_dirs; |
| |
| return 0; |
| } |
| |
| /* |
| * 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; |
| 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_iterate2(ext2_dblist dblist, |
| int (*func)(ext2_filsys fs, |
| struct ext2_db_entry2 *db_info, |
| void *priv_data), |
| void *priv_data) |
| { |
| unsigned long long i; |
| int ret; |
| |
| EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST); |
| |
| if (!dblist->sorted) |
| ext2fs_dblist_sort2(dblist, 0); |
| for (i=0; i < dblist->count; i++) { |
| ret = (*func)(dblist->fs, &dblist->list[i], priv_data); |
| if (ret & DBLIST_ABORT) |
| return 0; |
| } |
| return 0; |
| } |
| |
| 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) |
| { |
| EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST); |
| static struct ext2_db_entry ret_entry; |
| struct ext2_db_entry2 *last; |
| |
| 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; |
| } |
| |