X-Git-Url: https://git.whamcloud.com/?a=blobdiff_plain;f=lib%2Fext2fs%2Fdblist.c;h=ca1446b9f1afd536c5aa3365bc2b953a3bdb8654;hb=d1154eb460efe588eaed3d439c1caaca149fa362;hp=7c83c69c2b5eaf933eefb7d297c8d26a36f249e1;hpb=3cb6c5021d722e17b7105d1bc090880671f6fc6d;p=tools%2Fe2fsprogs.git diff --git a/lib/ext2fs/dblist.c b/lib/ext2fs/dblist.c index 7c83c69..ca1446b 100644 --- a/lib/ext2fs/dblist.c +++ b/lib/ext2fs/dblist.c @@ -1,47 +1,51 @@ /* * 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 Public - * License. + * 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 -#ifdef HAVE_ERRNO_H -#include -#endif - -#include +#include "ext2_fs.h" #include "ext2fsP.h" -static int dir_block_cmp(const void *a, const void *b); +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, ino_t *ret_num_dirs) +errcode_t ext2fs_get_num_dirs(ext2_filsys fs, ext2_ino_t *ret_num_dirs) { - int i; - ino_t num_dirs; + dgrp_t i; + ext2_ino_t num_dirs, max_dirs; EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS); - + num_dirs = 0; - for (i = 0; i < fs->group_desc_count; i++) - num_dirs += fs->group_desc[i].bg_used_dirs_count; + 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; @@ -52,12 +56,14 @@ errcode_t ext2fs_get_num_dirs(ext2_filsys fs, ino_t *ret_num_dirs) * helper function for making a new directory block list (for * initialize and copy). */ -static errcode_t make_dblist(ext2_filsys fs, ino_t size, ino_t count, - struct ext2_db_entry *list, +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); @@ -66,9 +72,9 @@ static errcode_t make_dblist(ext2_filsys fs, ino_t size, ino_t count, (fs->dblist->magic == EXT2_ET_MAGIC_DBLIST)) return 0; - dblist = malloc(sizeof(struct ext2_struct_dblist)); - if (!dblist) - return ENOMEM; + 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; @@ -76,27 +82,30 @@ static errcode_t make_dblist(ext2_filsys fs, ino_t size, ino_t count, if (size) dblist->size = size; else { - retval = ext2fs_get_num_dirs(fs, &dblist->size); + retval = ext2fs_get_num_dirs(fs, &num_dirs); if (retval) goto cleanup; - dblist->size = (dblist->size * 2) + 12; + dblist->size = (num_dirs * 2) + 12; } - len = (size_t) sizeof(struct ext2_db_entry) * dblist->size; + len = (size_t) sizeof(struct ext2_db_entry2) * dblist->size; dblist->count = count; - dblist->list = malloc(len); - if (dblist->list == NULL) { - retval = ENOMEM; + 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); - *ret_dblist = dblist; + if (ret_dblist) + *ret_dblist = dblist; + else + fs->dblist = dblist; return 0; cleanup: if (dblist) - free(dblist); + ext2fs_free_mem(&dblist); return retval; } @@ -148,27 +157,30 @@ errcode_t ext2fs_copy_dblist(ext2_dblist src, ext2_dblist *dest) /* * Add a directory block to the directory block list */ -errcode_t ext2fs_add_dir_block(ext2_dblist dblist, ino_t ino, blk_t blk, - int blockcnt) +errcode_t ext2fs_add_dir_block2(ext2_dblist dblist, ext2_ino_t ino, + blk64_t blk, e2_blkcnt_t blockcnt) { - struct ext2_db_entry *nlist, *new; - + 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) { - dblist->size += 100; - nlist = realloc(dblist->list, (size_t) dblist->size * - sizeof(struct ext2_db_entry)); - if (nlist == 0) { - dblist->size -= 100; - return ENOMEM; + 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; } - dblist->list = nlist; } - new = dblist->list + ( (int) dblist->count++); - new->blk = blk; - new->ino = ino; - new->blockcnt = blockcnt; + new_entry = dblist->list + ( dblist->count++); + new_entry->blk = blk; + new_entry->ino = ino; + new_entry->blockcnt = blockcnt; dblist->sorted = 0; @@ -178,11 +190,11 @@ errcode_t ext2fs_add_dir_block(ext2_dblist dblist, ino_t ino, blk_t blk, /* * Change the directory block to the directory block list */ -errcode_t ext2fs_set_dir_block(ext2_dblist dblist, ino_t ino, blk_t blk, - int blockcnt) +errcode_t ext2fs_set_dir_block2(ext2_dblist dblist, ext2_ino_t ino, + blk64_t blk, e2_blkcnt_t blockcnt) { - int i; - + dgrp_t i; + EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST); for (i=0; i < dblist->count; i++) { @@ -193,54 +205,211 @@ errcode_t ext2fs_set_dir_block(ext2_dblist dblist, ino_t ino, blk_t blk, dblist->sorted = 0; return 0; } - return ENOENT; + 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_iterate(ext2_dblist dblist, - int (*func)(ext2_filsys fs, - struct ext2_db_entry *db_info, - void *private), - void *private) +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) { - ino_t i; - int ret; - + unsigned long long i; + int ret; + EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST); - if (!dblist->sorted) { - qsort(dblist->list, (size_t) dblist->count, - sizeof(struct ext2_db_entry), dir_block_cmp); - dblist->sorted = 1; - } + if (!dblist->sorted) + ext2fs_dblist_sort2(dblist, 0); for (i=0; i < dblist->count; i++) { - ret = (*func)(dblist->fs, &dblist->list[(int)i], private); + ret = (*func)(dblist->fs, &dblist->list[i], priv_data); if (ret & DBLIST_ABORT) return 0; } return 0; } - -static int dir_block_cmp(const void *a, const void *b) +static EXT2_QSORT_TYPE dir_block_cmp2(const void *a, const void *b) { - const struct ext2_db_entry *db_a = - (const struct ext2_db_entry *) a; - const struct ext2_db_entry *db_b = - (const struct ext2_db_entry *) 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 (int) (db_a->blockcnt - db_b->blockcnt); + 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 (int) dblist->count; + 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; +} +