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_iterate2(ext2_dblist dblist,
 198                                  int (*func)(ext2_filsys fs,
 199                                              struct ext2_db_entry2 *db_info,
 200                                              void       *priv_data),
 201                                  void *priv_data)
 202 {
 203         unsigned long long      i;
 204         int             ret;
 205
 206         EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
 207
 208         if (!dblist->sorted)
 209                 ext2fs_dblist_sort2(dblist, 0);
 210         for (i=0; i < dblist->count; i++) {
 211                 ret = (*func)(dblist->fs, &dblist->list[i], priv_data);
 212                 if (ret & DBLIST_ABORT)
 213                         return 0;
 214         }
 215         return 0;
 216 }
 217
 218 static EXT2_QSORT_TYPE dir_block_cmp2(const void *a, const void *b)
 219 {
 220         const struct ext2_db_entry2 *db_a =
 221                 (const struct ext2_db_entry2 *) a;
 222         const struct ext2_db_entry2 *db_b =
 223                 (const struct ext2_db_entry2 *) b;
 224
 225         if (db_a->blk != db_b->blk)
 226                 return (int) (db_a->blk - db_b->blk);
 227
 228         if (db_a->ino != db_b->ino)
 229                 return (int) (db_a->ino - db_b->ino);
 230
 231         return (db_a->blockcnt - db_b->blockcnt);
 232 }
 233
 234 blk64_t ext2fs_dblist_count2(ext2_dblist dblist)
 235 {
 236         return dblist->count;
 237 }
 238
 239 errcode_t ext2fs_dblist_get_last2(ext2_dblist dblist,
 240                                   struct ext2_db_entry2 **entry)
 241 {
 242         EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
 243
 244         if (dblist->count == 0)
 245                 return EXT2_ET_DBLIST_EMPTY;
 246
 247         if (entry)
 248                 *entry = dblist->list + ( dblist->count-1);
 249         return 0;
 250 }
 251
 252 errcode_t ext2fs_dblist_drop_last(ext2_dblist dblist)
 253 {
 254         EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
 255
 256         if (dblist->count == 0)
 257                 return EXT2_ET_DBLIST_EMPTY;
 258
 259         dblist->count--;
 260         return 0;
 261 }
 262
 263 /*
 264  * Legacy 32-bit versions
 265  */
 266
 267 /*
 268  * Add a directory block to the directory block list
 269  */
 270 errcode_t ext2fs_add_dir_block(ext2_dblist dblist, ext2_ino_t ino, blk_t blk,
 271                                int blockcnt)
 272 {
 273         return ext2fs_add_dir_block2(dblist, ino, blk, blockcnt);
 274 }
 275
 276 /*
 277  * Change the directory block to the directory block list
 278  */
 279 errcode_t ext2fs_set_dir_block(ext2_dblist dblist, ext2_ino_t ino, blk_t blk,
 280                                int blockcnt)
 281 {
 282         return ext2fs_set_dir_block2(dblist, ino, blk, blockcnt);
 283 }
 284
 285 void ext2fs_dblist_sort(ext2_dblist dblist,
 286                         EXT2_QSORT_TYPE (*sortfunc)(const void *,
 287                                                     const void *))
 288 {
 289         if (sortfunc) {
 290                 sortfunc32 = sortfunc;
 291                 sortfunc = dir_block_cmp;
 292         } else
 293                 sortfunc = dir_block_cmp2;
 294         qsort(dblist->list, (size_t) dblist->count,
 295               sizeof(struct ext2_db_entry2), sortfunc);
 296         dblist->sorted = 1;
 297 }
 298
 299 /*
 300  * This function iterates over the directory block list
 301  */
 302 struct iterate_passthrough {
 303         int (*func)(ext2_filsys fs,
 304                     struct ext2_db_entry *db_info,
 305                     void        *priv_data);
 306         void *priv_data;
 307 };
 308
 309 static int passthrough_func(ext2_filsys fs,
 310                             struct ext2_db_entry2 *db_info,
 311                             void        *priv_data)
 312 {
 313         struct iterate_passthrough *p = priv_data;
 314         struct ext2_db_entry db;
 315         int ret;
 316
 317         db.ino = db_info->ino;
 318         db.blk = (blk_t) db_info->blk;
 319         db.blockcnt = (int) db_info->blockcnt;
 320         ret = (p->func)(fs, &db, p->priv_data);
 321         db_info->ino = db.ino;
 322         db_info->blk = db.blk;
 323         db_info->blockcnt = db.blockcnt;
 324         return ret;
 325 }
 326
 327 errcode_t ext2fs_dblist_iterate(ext2_dblist dblist,
 328                                 int (*func)(ext2_filsys fs,
 329                                             struct ext2_db_entry *db_info,
 330                                             void        *priv_data),
 331                                 void *priv_data)
 332 {
 333         struct iterate_passthrough pass;
 334
 335         EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
 336         pass.func = func;
 337         pass.priv_data = priv_data;
 338
 339         return ext2fs_dblist_iterate2(dblist, passthrough_func, &pass);
 340 }
 341
 342 static EXT2_QSORT_TYPE dir_block_cmp(const void *a, const void *b)
 343 {
 344         const struct ext2_db_entry2 *db_a =
 345                 (const struct ext2_db_entry2 *) a;
 346         const struct ext2_db_entry2 *db_b =
 347                 (const struct ext2_db_entry2 *) b;
 348
 349         struct ext2_db_entry a32, b32;
 350
 351         a32.ino = db_a->ino;  a32.blk = db_a->blk;
 352         a32.blockcnt = db_a->blockcnt;
 353
 354         b32.ino = db_b->ino;  b32.blk = db_b->blk;
 355         b32.blockcnt = db_b->blockcnt;
 356
 357         return sortfunc32(&a32, &b32);
 358 }
 359
 360 int ext2fs_dblist_count(ext2_dblist dblist)
 361 {
 362         return dblist->count;
 363 }
 364
 365 errcode_t ext2fs_dblist_get_last(ext2_dblist dblist,
 366                                  struct ext2_db_entry **entry)
 367 {
 368         static struct ext2_db_entry ret_entry;
 369         struct ext2_db_entry2 *last;
 370
 371         EXT2_CHECK_MAGIC(dblist, EXT2_ET_MAGIC_DBLIST);
 372
 373         if (dblist->count == 0)
 374                 return EXT2_ET_DBLIST_EMPTY;
 375
 376         if (!entry)
 377                 return 0;
 378
 379         last = dblist->list + dblist->count -1;
 380
 381         ret_entry.ino = last->ino;
 382         ret_entry.blk = last->blk;
 383         ret_entry.blockcnt = last->blockcnt;
 384         *entry = &ret_entry;
 385
 386         return 0;
 387 }
 388