e2fsck/dx_dirinfo.c

   1 /*
   2  * dirinfo.c --- maintains the directory information table for e2fsck.
   3  *
   4  * Copyright (C) 1993 Theodore Ts'o.  This file may be redistributed
   5  * under the terms of the GNU Public License.
   6  */
   7
   8 #include "e2fsck.h"
   9 #ifdef ENABLE_HTREE
  10
  11 /*
  12  * This subroutine is called during pass1 to create a directory info
  13  * entry.  During pass1, the passed-in parent is 0; it will get filled
  14  * in during pass2.
  15  */
  16 void e2fsck_add_dx_dir(e2fsck_t ctx, ext2_ino_t ino, int num_blocks)
  17 {
  18         struct dx_dir_info *dir;
  19         int             i, j;
  20         errcode_t       retval;
  21         unsigned long   old_size;
  22
  23 #if 0
  24         printf("add_dx_dir_info for inode %lu...\n", ino);
  25 #endif
  26         if (!ctx->dx_dir_info) {
  27                 ctx->dx_dir_info_count = 0;
  28                 ctx->dx_dir_info_size = 100; /* Guess */
  29                 ctx->dx_dir_info  = (struct dx_dir_info *)
  30                         e2fsck_allocate_memory(ctx, ctx->dx_dir_info_size
  31                                                * sizeof (struct dx_dir_info),
  32                                                "directory map");
  33         }
  34
  35         if (ctx->dx_dir_info_count >= ctx->dx_dir_info_size) {
  36                 old_size = ctx->dx_dir_info_size * sizeof(struct dx_dir_info);
  37                 ctx->dx_dir_info_size += 10;
  38                 retval = ext2fs_resize_mem(old_size, ctx->dx_dir_info_size *
  39                                            sizeof(struct dx_dir_info),
  40                                            &ctx->dx_dir_info);
  41                 if (retval) {
  42                         ctx->dx_dir_info_size -= 10;
  43                         return;
  44                 }
  45         }
  46
  47         /*
  48          * Normally, add_dx_dir_info is called with each inode in
  49          * sequential order; but once in a while (like when pass 3
  50          * needs to recreate the root directory or lost+found
  51          * directory) it is called out of order.  In those cases, we
  52          * need to move the dx_dir_info entries down to make room, since
  53          * the dx_dir_info array needs to be sorted by inode number for
  54          * get_dx_dir_info()'s sake.
  55          */
  56         if (ctx->dx_dir_info_count &&
  57             ctx->dx_dir_info[ctx->dx_dir_info_count-1].ino >= ino) {
  58                 for (i = ctx->dx_dir_info_count-1; i > 0; i--)
  59                         if (ctx->dx_dir_info[i-1].ino < ino)
  60                                 break;
  61                 dir = &ctx->dx_dir_info[i];
  62                 if (dir->ino != ino)
  63                         for (j = ctx->dx_dir_info_count++; j > i; j--)
  64                                 ctx->dx_dir_info[j] = ctx->dx_dir_info[j-1];
  65         } else
  66                 dir = &ctx->dx_dir_info[ctx->dx_dir_info_count++];
  67
  68         dir->ino = ino;
  69         dir->numblocks = num_blocks;
  70         dir->hashversion = 0;
  71         dir->dx_block = e2fsck_allocate_memory(ctx, num_blocks
  72                                        * sizeof (struct dx_dirblock_info),
  73                                        "dx_block info array");
  74
  75 }
  76
  77 /*
  78  * get_dx_dir_info() --- given an inode number, try to find the directory
  79  * information entry for it.
  80  */
  81 struct dx_dir_info *e2fsck_get_dx_dir_info(e2fsck_t ctx, ext2_ino_t ino)
  82 {
  83         int     low, high, mid;
  84
  85         low = 0;
  86         high = ctx->dx_dir_info_count-1;
  87         if (!ctx->dx_dir_info)
  88                 return 0;
  89         if (ino == ctx->dx_dir_info[low].ino)
  90                 return &ctx->dx_dir_info[low];
  91         if  (ino == ctx->dx_dir_info[high].ino)
  92                 return &ctx->dx_dir_info[high];
  93
  94         while (low < high) {
  95                 mid = (low+high)/2;
  96                 if (mid == low || mid == high)
  97                         break;
  98                 if (ino == ctx->dx_dir_info[mid].ino)
  99                         return &ctx->dx_dir_info[mid];
 100                 if (ino < ctx->dx_dir_info[mid].ino)
 101                         high = mid;
 102                 else
 103                         low = mid;
 104         }
 105         return 0;
 106 }
 107
 108 /*
 109  * Free the dx_dir_info structure when it isn't needed any more.
 110  */
 111 void e2fsck_free_dx_dir_info(e2fsck_t ctx)
 112 {
 113         int     i;
 114         struct dx_dir_info *dir;
 115
 116         if (ctx->dx_dir_info) {
 117                 dir = ctx->dx_dir_info;
 118                 for (i=0; i < ctx->dx_dir_info_count; i++,dir++) {
 119                         if (dir->dx_block) {
 120                                 ext2fs_free_mem(&dir->dx_block);
 121                                 dir->dx_block = 0;
 122                         }
 123                 }
 124                 ext2fs_free_mem(&ctx->dx_dir_info);
 125                 ctx->dx_dir_info = 0;
 126         }
 127         ctx->dx_dir_info_size = 0;
 128         ctx->dx_dir_info_count = 0;
 129 }
 130
 131 /*
 132  * Return the count of number of directories in the dx_dir_info structure
 133  */
 134 int e2fsck_get_num_dx_dirinfo(e2fsck_t ctx)
 135 {
 136         return ctx->dx_dir_info_count;
 137 }
 138
 139 /*
 140  * A simple interator function
 141  */
 142 struct dx_dir_info *e2fsck_dx_dir_info_iter(e2fsck_t ctx, int *control)
 143 {
 144         if (*control >= ctx->dx_dir_info_count)
 145                 return 0;
 146
 147         return(ctx->dx_dir_info + (*control)++);
 148 }
 149
 150 #endif /* ENABLE_HTREE */