lib/ext2fs/dblist.c

   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  * Merge a directory block list @src to @dest
 124  */
 125 errcode_t ext2fs_merge_dblist(ext2_dblist src, ext2_dblist dest)
 126 {
 127         unsigned long long src_count = src->count;
 128         unsigned long long dest_count = dest->count;
 129         unsigned long long size = src_count + dest_count;
 130         size_t size_entry = sizeof(struct ext2_db_entry2);
 131         struct ext2_db_entry2 *array, *array2;
 132         errcode_t retval;
 133
 134         if (src_count == 0)
 135                 return 0;
 136
 137         if (src->sorted || (dest->sorted && dest_count != 0))
 138                 return EINVAL;
 139
 140         retval = ext2fs_get_array(size, size_entry, &array);
 141         if (retval)
 142                 return retval;
 143
 144         array2 = array;
 145         memcpy(array, src->list, src_count * size_entry);
 146         array += src_count;
 147         memcpy(array, dest->list, dest_count * size_entry);
 148         ext2fs_free_mem(&dest->list);
 149
 150         dest->list = array2;
 151         dest->count = src_count + dest_count;
 152         dest->size = size;
 153         dest->sorted = 0;
 154
 155         return 0;
 156 }
 157
 158 /*
 159  * Close a directory block list
 160  *
 161  * (moved to closefs.c)
 162  */
 163
 164
 165 /*
 166  * Add a directory block to the directory block list
 167  */
 168 errcode_t ext2fs_add_dir_block2(ext2_dblist dblist, ext2_ino_t ino,
 169                                 blk64_t blk, e2_blkcnt_t blockcnt)
 170 {
 171         struct ext2_db_entry2   *new_entry;
 172         errcode_t               retval;
 173         unsigned long           old_size;
 174
 175         EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
 176
 177         if (dblist->count >= dblist->size) {
 178                 old_size = dblist->size * sizeof(struct ext2_db_entry2);
 179                 dblist->size += dblist->size > 200 ? dblist->size / 2 : 100;
 180                 retval = ext2fs_resize_mem(old_size, (size_t) dblist->size *
 181                                            sizeof(struct ext2_db_entry2),
 182                                            &dblist->list);
 183                 if (retval) {
 184                         dblist->size = old_size / sizeof(struct ext2_db_entry2);
 185                         return retval;
 186                 }
 187         }
 188         new_entry = dblist->list + ( dblist->count++);
 189         new_entry->blk = blk;
 190         new_entry->ino = ino;
 191         new_entry->blockcnt = blockcnt;
 192
 193         dblist->sorted = 0;
 194
 195         return 0;
 196 }
 197
 198 /*
 199  * Change the directory block to the directory block list
 200  */
 201 errcode_t ext2fs_set_dir_block2(ext2_dblist dblist, ext2_ino_t ino,
 202                                 blk64_t blk, e2_blkcnt_t blockcnt)
 203 {
 204         dgrp_t                  i;
 205
 206         EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
 207
 208         for (i=0; i < dblist->count; i++) {
 209                 if ((dblist->list[i].ino != ino) ||
 210                     (dblist->list[i].blockcnt != blockcnt))
 211                         continue;
 212                 dblist->list[i].blk = blk;
 213                 dblist->sorted = 0;
 214                 return 0;
 215         }
 216         return EXT2_ET_DB_NOT_FOUND;
 217 }
 218
 219 void ext2fs_dblist_sort2(ext2_dblist dblist,
 220                          EXT2_QSORT_TYPE (*sortfunc)(const void *,
 221                                                      const void *))
 222 {
 223         if (!sortfunc)
 224                 sortfunc = dir_block_cmp2;
 225         qsort(dblist->list, (size_t) dblist->count,
 226               sizeof(struct ext2_db_entry2), sortfunc);
 227         dblist->sorted = 1;
 228 }
 229
 230 /*
 231  * This function iterates over the directory block list
 232  */
 233 errcode_t ext2fs_dblist_iterate3(ext2_dblist dblist,
 234                                  int (*func)(ext2_filsys fs,
 235                                              struct ext2_db_entry2 *db_info,
 236                                              void       *priv_data),
 237                                  unsigned long long start,
 238                                  unsigned long long count,
 239                                  void *priv_data)
 240 {
 241         unsigned long long      i, end;
 242         int             ret;
 243
 244         EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
 245
 246         end = start + count;
 247         if (!dblist->sorted)
 248                 ext2fs_dblist_sort2(dblist, 0);
 249         if (end > dblist->count)
 250                 end = dblist->count;
 251         for (i = start; i < end; i++) {
 252                 ret = (*func)(dblist->fs, &dblist->list[i], priv_data);
 253                 if (ret & DBLIST_ABORT)
 254                         return 0;
 255         }
 256         return 0;
 257 }
 258
 259 errcode_t ext2fs_dblist_iterate2(ext2_dblist dblist,
 260                                  int (*func)(ext2_filsys fs,
 261                                              struct ext2_db_entry2 *db_info,
 262                                              void       *priv_data),
 263                                  void *priv_data)
 264 {
 265         return ext2fs_dblist_iterate3(dblist, func, 0, dblist->count,
 266                                       priv_data);
 267 }
 268
 269 static EXT2_QSORT_TYPE dir_block_cmp2(const void *a, const void *b)
 270 {
 271         const struct ext2_db_entry2 *db_a =
 272                 (const struct ext2_db_entry2 *) a;
 273         const struct ext2_db_entry2 *db_b =
 274                 (const struct ext2_db_entry2 *) b;
 275
 276         if (db_a->blk != db_b->blk)
 277                 return (int) (db_a->blk - db_b->blk);
 278
 279         if (db_a->ino != db_b->ino)
 280                 return (int) (db_a->ino - db_b->ino);
 281
 282         return (db_a->blockcnt - db_b->blockcnt);
 283 }
 284
 285 blk64_t ext2fs_dblist_count2(ext2_dblist dblist)
 286 {
 287         return dblist->count;
 288 }
 289
 290 errcode_t ext2fs_dblist_get_last2(ext2_dblist dblist,
 291                                   struct ext2_db_entry2 **entry)
 292 {
 293         EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
 294
 295         if (dblist->count == 0)
 296                 return EXT2_ET_DBLIST_EMPTY;
 297
 298         if (entry)
 299                 *entry = dblist->list + ( dblist->count-1);
 300         return 0;
 301 }
 302
 303 errcode_t ext2fs_dblist_drop_last(ext2_dblist dblist)
 304 {
 305         EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
 306
 307         if (dblist->count == 0)
 308                 return EXT2_ET_DBLIST_EMPTY;
 309
 310         dblist->count--;
 311         return 0;
 312 }
 313
 314 /*
 315  * Legacy 32-bit versions
 316  */
 317
 318 /*
 319  * Add a directory block to the directory block list
 320  */
 321 errcode_t ext2fs_add_dir_block(ext2_dblist dblist, ext2_ino_t ino, blk_t blk,
 322                                int blockcnt)
 323 {
 324         return ext2fs_add_dir_block2(dblist, ino, blk, blockcnt);
 325 }
 326
 327 /*
 328  * Change the directory block to the directory block list
 329  */
 330 errcode_t ext2fs_set_dir_block(ext2_dblist dblist, ext2_ino_t ino, blk_t blk,
 331                                int blockcnt)
 332 {
 333         return ext2fs_set_dir_block2(dblist, ino, blk, blockcnt);
 334 }
 335
 336 void ext2fs_dblist_sort(ext2_dblist dblist,
 337                         EXT2_QSORT_TYPE (*sortfunc)(const void *,
 338                                                     const void *))
 339 {
 340         if (sortfunc) {
 341                 sortfunc32 = sortfunc;
 342                 sortfunc = dir_block_cmp;
 343         } else
 344                 sortfunc = dir_block_cmp2;
 345         qsort(dblist->list, (size_t) dblist->count,
 346               sizeof(struct ext2_db_entry2), sortfunc);
 347         dblist->sorted = 1;
 348 }
 349
 350 /*
 351  * This function iterates over the directory block list
 352  */
 353 struct iterate_passthrough {
 354         int (*func)(ext2_filsys fs,
 355                     struct ext2_db_entry *db_info,
 356                     void        *priv_data);
 357         void *priv_data;
 358 };
 359
 360 static int passthrough_func(ext2_filsys fs,
 361                             struct ext2_db_entry2 *db_info,
 362                             void        *priv_data)
 363 {
 364         struct iterate_passthrough *p = priv_data;
 365         struct ext2_db_entry db;
 366         int ret;
 367
 368         db.ino = db_info->ino;
 369         db.blk = (blk_t) db_info->blk;
 370         db.blockcnt = (int) db_info->blockcnt;
 371         ret = (p->func)(fs, &db, p->priv_data);
 372         db_info->ino = db.ino;
 373         db_info->blk = db.blk;
 374         db_info->blockcnt = db.blockcnt;
 375         return ret;
 376 }
 377
 378 errcode_t ext2fs_dblist_iterate(ext2_dblist dblist,
 379                                 int (*func)(ext2_filsys fs,
 380                                             struct ext2_db_entry *db_info,
 381                                             void        *priv_data),
 382                                 void *priv_data)
 383 {
 384         struct iterate_passthrough pass;
 385
 386         EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
 387         pass.func = func;
 388         pass.priv_data = priv_data;
 389
 390         return ext2fs_dblist_iterate2(dblist, passthrough_func, &pass);
 391 }
 392
 393 static EXT2_QSORT_TYPE dir_block_cmp(const void *a, const void *b)
 394 {
 395         const struct ext2_db_entry2 *db_a =
 396                 (const struct ext2_db_entry2 *) a;
 397         const struct ext2_db_entry2 *db_b =
 398                 (const struct ext2_db_entry2 *) b;
 399
 400         struct ext2_db_entry a32, b32;
 401
 402         a32.ino = db_a->ino;  a32.blk = db_a->blk;
 403         a32.blockcnt = db_a->blockcnt;
 404
 405         b32.ino = db_b->ino;  b32.blk = db_b->blk;
 406         b32.blockcnt = db_b->blockcnt;
 407
 408         return sortfunc32(&a32, &b32);
 409 }
 410
 411 int ext2fs_dblist_count(ext2_dblist dblist)
 412 {
 413         return dblist->count;
 414 }
 415
 416 errcode_t ext2fs_dblist_get_last(ext2_dblist dblist,
 417                                  struct ext2_db_entry **entry)
 418 {
 419         static struct ext2_db_entry ret_entry;
 420         struct ext2_db_entry2 *last;
 421
 422         EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
 423
 424         if (dblist->count == 0)
 425                 return EXT2_ET_DBLIST_EMPTY;
 426
 427         if (!entry)
 428                 return 0;
 429
 430         last = dblist->list + dblist->count -1;
 431
 432         ret_entry.ino = last->ino;
 433         ret_entry.blk = last->blk;
 434         ret_entry.blockcnt = last->blockcnt;
 435         *entry = &ret_entry;
 436
 437         return 0;
 438 }
 439