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