dblist.c revision 00eb0eee0addfd3b7ede98b85e00dff1547838a0
1/* 2 * dblist.c -- directory block list functions 3 * 4 * Copyright 1997 by Theodore Ts'o 5 * 6 * %Begin-Header% 7 * This file may be redistributed under the terms of the GNU Library 8 * General Public License, version 2. 9 * %End-Header% 10 */ 11 12#include "config.h" 13#include <stdio.h> 14#if HAVE_UNISTD_H 15#include <unistd.h> 16#endif 17#include <string.h> 18#include <time.h> 19 20#include "ext2_fs.h" 21#include "ext2fsP.h" 22 23static EXT2_QSORT_TYPE dir_block_cmp(const void *a, const void *b); 24static EXT2_QSORT_TYPE dir_block_cmp2(const void *a, const void *b); 25static EXT2_QSORT_TYPE (*sortfunc32)(const void *a, const void *b); 26 27/* 28 * Returns the number of directories in the filesystem as reported by 29 * the group descriptors. Of course, the group descriptors could be 30 * wrong! 31 */ 32errcode_t ext2fs_get_num_dirs(ext2_filsys fs, ext2_ino_t *ret_num_dirs) 33{ 34 dgrp_t i; 35 ext2_ino_t num_dirs, max_dirs; 36 37 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS); 38 39 num_dirs = 0; 40 max_dirs = fs->super->s_inodes_per_group; 41 for (i = 0; i < fs->group_desc_count; i++) { 42 if (ext2fs_bg_used_dirs_count(fs, i) > max_dirs) 43 num_dirs += max_dirs / 8; 44 else 45 num_dirs += ext2fs_bg_used_dirs_count(fs, i); 46 } 47 if (num_dirs > fs->super->s_inodes_count) 48 num_dirs = fs->super->s_inodes_count; 49 50 *ret_num_dirs = num_dirs; 51 52 return 0; 53} 54 55/* 56 * helper function for making a new directory block list (for 57 * initialize and copy). 58 */ 59static errcode_t make_dblist(ext2_filsys fs, ext2_ino_t size, 60 ext2_ino_t count, 61 struct ext2_db_entry2 *list, 62 ext2_dblist *ret_dblist) 63{ 64 ext2_dblist dblist = NULL; 65 errcode_t retval; 66 ext2_ino_t num_dirs; 67 size_t len; 68 69 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS); 70 71 if ((ret_dblist == 0) && fs->dblist && 72 (fs->dblist->magic == EXT2_ET_MAGIC_DBLIST)) 73 return 0; 74 75 retval = ext2fs_get_mem(sizeof(struct ext2_struct_dblist), &dblist); 76 if (retval) 77 goto cleanup; 78 memset(dblist, 0, sizeof(struct ext2_struct_dblist)); 79 80 dblist->magic = EXT2_ET_MAGIC_DBLIST; 81 dblist->fs = fs; 82 if (size) 83 dblist->size = size; 84 else { 85 retval = ext2fs_get_num_dirs(fs, &num_dirs); 86 if (retval) 87 goto cleanup; 88 dblist->size = (num_dirs * 2) + 12; 89 } 90 len = (size_t) sizeof(struct ext2_db_entry2) * dblist->size; 91 dblist->count = count; 92 retval = ext2fs_get_array(dblist->size, sizeof(struct ext2_db_entry2), 93 &dblist->list); 94 if (retval) 95 goto cleanup; 96 97 if (list) 98 memcpy(dblist->list, list, len); 99 else 100 memset(dblist->list, 0, len); 101 if (ret_dblist) 102 *ret_dblist = dblist; 103 else 104 fs->dblist = dblist; 105 return 0; 106cleanup: 107 if (dblist) 108 ext2fs_free_mem(&dblist); 109 return retval; 110} 111 112/* 113 * Initialize a directory block list 114 */ 115errcode_t ext2fs_init_dblist(ext2_filsys fs, ext2_dblist *ret_dblist) 116{ 117 ext2_dblist dblist; 118 errcode_t retval; 119 120 retval = make_dblist(fs, 0, 0, 0, &dblist); 121 if (retval) 122 return retval; 123 124 dblist->sorted = 1; 125 if (ret_dblist) 126 *ret_dblist = dblist; 127 else 128 fs->dblist = dblist; 129 130 return 0; 131} 132 133/* 134 * Copy a directory block list 135 */ 136errcode_t ext2fs_copy_dblist(ext2_dblist src, ext2_dblist *dest) 137{ 138 ext2_dblist dblist; 139 errcode_t retval; 140 141 retval = make_dblist(src->fs, src->size, src->count, src->list, 142 &dblist); 143 if (retval) 144 return retval; 145 dblist->sorted = src->sorted; 146 *dest = dblist; 147 return 0; 148} 149 150/* 151 * Close a directory block list 152 * 153 * (moved to closefs.c) 154 */ 155 156 157/* 158 * Add a directory block to the directory block list 159 */ 160errcode_t ext2fs_add_dir_block2(ext2_dblist dblist, ext2_ino_t ino, 161 blk64_t blk, e2_blkcnt_t blockcnt) 162{ 163 struct ext2_db_entry2 *new_entry; 164 errcode_t retval; 165 unsigned long old_size; 166 167 EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST); 168 169 if (dblist->count >= dblist->size) { 170 old_size = dblist->size * sizeof(struct ext2_db_entry2); 171 dblist->size += dblist->size > 200 ? dblist->size / 2 : 100; 172 retval = ext2fs_resize_mem(old_size, (size_t) dblist->size * 173 sizeof(struct ext2_db_entry2), 174 &dblist->list); 175 if (retval) { 176 dblist->size = old_size / sizeof(struct ext2_db_entry2); 177 return retval; 178 } 179 } 180 new_entry = dblist->list + ( dblist->count++); 181 new_entry->blk = blk; 182 new_entry->ino = ino; 183 new_entry->blockcnt = blockcnt; 184 185 dblist->sorted = 0; 186 187 return 0; 188} 189 190/* 191 * Change the directory block to the directory block list 192 */ 193errcode_t ext2fs_set_dir_block2(ext2_dblist dblist, ext2_ino_t ino, 194 blk64_t blk, e2_blkcnt_t blockcnt) 195{ 196 dgrp_t i; 197 198 EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST); 199 200 for (i=0; i < dblist->count; i++) { 201 if ((dblist->list[i].ino != ino) || 202 (dblist->list[i].blockcnt != blockcnt)) 203 continue; 204 dblist->list[i].blk = blk; 205 dblist->sorted = 0; 206 return 0; 207 } 208 return EXT2_ET_DB_NOT_FOUND; 209} 210 211void ext2fs_dblist_sort2(ext2_dblist dblist, 212 EXT2_QSORT_TYPE (*sortfunc)(const void *, 213 const void *)) 214{ 215 if (!sortfunc) 216 sortfunc = dir_block_cmp2; 217 qsort(dblist->list, (size_t) dblist->count, 218 sizeof(struct ext2_db_entry2), sortfunc); 219 dblist->sorted = 1; 220} 221 222/* 223 * This function iterates over the directory block list 224 */ 225errcode_t ext2fs_dblist_iterate2(ext2_dblist dblist, 226 int (*func)(ext2_filsys fs, 227 struct ext2_db_entry2 *db_info, 228 void *priv_data), 229 void *priv_data) 230{ 231 unsigned long long i; 232 int ret; 233 234 EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST); 235 236 if (!dblist->sorted) 237 ext2fs_dblist_sort2(dblist, 0); 238 for (i=0; i < dblist->count; i++) { 239 ret = (*func)(dblist->fs, &dblist->list[i], priv_data); 240 if (ret & DBLIST_ABORT) 241 return 0; 242 } 243 return 0; 244} 245 246static EXT2_QSORT_TYPE dir_block_cmp2(const void *a, const void *b) 247{ 248 const struct ext2_db_entry2 *db_a = 249 (const struct ext2_db_entry2 *) a; 250 const struct ext2_db_entry2 *db_b = 251 (const struct ext2_db_entry2 *) b; 252 253 if (db_a->blk != db_b->blk) 254 return (int) (db_a->blk - db_b->blk); 255 256 if (db_a->ino != db_b->ino) 257 return (int) (db_a->ino - db_b->ino); 258 259 return (db_a->blockcnt - db_b->blockcnt); 260} 261 262blk64_t ext2fs_dblist_count2(ext2_dblist dblist) 263{ 264 return dblist->count; 265} 266 267errcode_t ext2fs_dblist_get_last2(ext2_dblist dblist, 268 struct ext2_db_entry2 **entry) 269{ 270 EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST); 271 272 if (dblist->count == 0) 273 return EXT2_ET_DBLIST_EMPTY; 274 275 if (entry) 276 *entry = dblist->list + ( dblist->count-1); 277 return 0; 278} 279 280errcode_t ext2fs_dblist_drop_last(ext2_dblist dblist) 281{ 282 EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST); 283 284 if (dblist->count == 0) 285 return EXT2_ET_DBLIST_EMPTY; 286 287 dblist->count--; 288 return 0; 289} 290 291/* 292 * Legacy 32-bit versions 293 */ 294 295/* 296 * Add a directory block to the directory block list 297 */ 298errcode_t ext2fs_add_dir_block(ext2_dblist dblist, ext2_ino_t ino, blk_t blk, 299 int blockcnt) 300{ 301 return ext2fs_add_dir_block2(dblist, ino, blk, blockcnt); 302} 303 304/* 305 * Change the directory block to the directory block list 306 */ 307errcode_t ext2fs_set_dir_block(ext2_dblist dblist, ext2_ino_t ino, blk_t blk, 308 int blockcnt) 309{ 310 return ext2fs_set_dir_block2(dblist, ino, blk, blockcnt); 311} 312 313void ext2fs_dblist_sort(ext2_dblist dblist, 314 EXT2_QSORT_TYPE (*sortfunc)(const void *, 315 const void *)) 316{ 317 if (sortfunc) { 318 sortfunc32 = sortfunc; 319 sortfunc = dir_block_cmp; 320 } else 321 sortfunc = dir_block_cmp2; 322 qsort(dblist->list, (size_t) dblist->count, 323 sizeof(struct ext2_db_entry2), sortfunc); 324 dblist->sorted = 1; 325} 326 327/* 328 * This function iterates over the directory block list 329 */ 330struct iterate_passthrough { 331 int (*func)(ext2_filsys fs, 332 struct ext2_db_entry *db_info, 333 void *priv_data); 334 void *priv_data; 335}; 336 337static int passthrough_func(ext2_filsys fs, 338 struct ext2_db_entry2 *db_info, 339 void *priv_data) 340{ 341 struct iterate_passthrough *p = priv_data; 342 struct ext2_db_entry db; 343 int ret; 344 345 db.ino = db_info->ino; 346 db.blk = (blk_t) db_info->blk; 347 db.blockcnt = (int) db_info->blockcnt; 348 ret = (p->func)(fs, &db, p->priv_data); 349 db_info->ino = db.ino; 350 db_info->blk = db.blk; 351 db_info->blockcnt = db.blockcnt; 352 return ret; 353} 354 355errcode_t ext2fs_dblist_iterate(ext2_dblist dblist, 356 int (*func)(ext2_filsys fs, 357 struct ext2_db_entry *db_info, 358 void *priv_data), 359 void *priv_data) 360{ 361 struct iterate_passthrough pass; 362 363 EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST); 364 pass.func = func; 365 pass.priv_data = priv_data; 366 367 return ext2fs_dblist_iterate2(dblist, passthrough_func, &pass); 368} 369 370static EXT2_QSORT_TYPE dir_block_cmp(const void *a, const void *b) 371{ 372 const struct ext2_db_entry2 *db_a = 373 (const struct ext2_db_entry2 *) a; 374 const struct ext2_db_entry2 *db_b = 375 (const struct ext2_db_entry2 *) b; 376 377 struct ext2_db_entry a32, b32; 378 379 a32.ino = db_a->ino; a32.blk = db_a->blk; 380 a32.blockcnt = db_a->blockcnt; 381 382 b32.ino = db_b->ino; b32.blk = db_b->blk; 383 b32.blockcnt = db_b->blockcnt; 384 385 return sortfunc32(&a32, &b32); 386} 387 388int ext2fs_dblist_count(ext2_dblist dblist) 389{ 390 return dblist->count; 391} 392 393errcode_t ext2fs_dblist_get_last(ext2_dblist dblist, 394 struct ext2_db_entry **entry) 395{ 396 EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST); 397 static struct ext2_db_entry ret_entry; 398 struct ext2_db_entry2 *last; 399 400 if (dblist->count == 0) 401 return EXT2_ET_DBLIST_EMPTY; 402 403 if (!entry) 404 return 0; 405 406 last = dblist->list + dblist->count -1; 407 408 ret_entry.ino = last->ino; 409 ret_entry.blk = last->blk; 410 ret_entry.blockcnt = last->blockcnt; 411 *entry = &ret_entry; 412 413 return 0; 414} 415 416