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  * 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