e2fsck/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 <et/com_err.h>
   9 #include "e2fsck.h"
  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_dir_info(e2fsck_t ctx, ino_t ino, ino_t parent)
  17 {
  18         struct dir_info *dir;
  19         int             i, j;
  20         ino_t           num_dirs;
  21         errcode_t       retval;
  22
  23 #if 0
  24         printf("add_dir_info for inode %lu...\n", ino);
  25 #endif
  26         if (!ctx->dir_info) {
  27                 ctx->dir_info_count = 0;
  28                 retval = ext2fs_get_num_dirs(ctx->fs, &num_dirs);
  29                 if (retval)
  30                         num_dirs = 1024;        /* Guess */
  31                 ctx->dir_info_size = num_dirs + 10;
  32                 ctx->dir_info  = e2fsck_allocate_memory(ctx,
  33                         ctx->dir_info_size * sizeof (struct dir_info),
  34                         "directory map");
  35         }
  36
  37         if (ctx->dir_info_count >= ctx->dir_info_size) {
  38                 ctx->dir_info_size += 10;
  39                 retval = ext2fs_resize_mem(ctx->dir_info_size *
  40                                            sizeof(struct dir_info),
  41                                            (void **) &ctx->dir_info);
  42                 if (retval) {
  43                         ctx->dir_info_size -= 10;
  44                         return;
  45                 }
  46         }
  47
  48         /*
  49          * Normally, add_dir_info is called with each inode in
  50          * sequential order; but once in a while (like when pass 3
  51          * needs to recreate the root directory or lost+found
  52          * directory) it is called out of order.  In those cases, we
  53          * need to move the dir_info entries down to make room, since
  54          * the dir_info array needs to be sorted by inode number for
  55          * get_dir_info()'s sake.
  56          */
  57         if (ctx->dir_info_count &&
  58             ctx->dir_info[ctx->dir_info_count-1].ino >= ino) {
  59                 for (i = ctx->dir_info_count-1; i > 0; i--)
  60                         if (ctx->dir_info[i-1].ino < ino)
  61                                 break;
  62                 dir = &ctx->dir_info[i];
  63                 if (dir->ino != ino)
  64                         for (j = ctx->dir_info_count++; j > i; j--)
  65                                 ctx->dir_info[j] = ctx->dir_info[j-1];
  66         } else
  67                 dir = &ctx->dir_info[ctx->dir_info_count++];
  68
  69         dir->ino = ino;
  70         dir->dotdot = parent;
  71         dir->parent = parent;
  72 }
  73
  74 /*
  75  * get_dir_info() --- given an inode number, try to find the directory
  76  * information entry for it.
  77  */
  78 struct dir_info *e2fsck_get_dir_info(e2fsck_t ctx, ino_t ino)
  79 {
  80         int     low, high, mid;
  81
  82         low = 0;
  83         high = ctx->dir_info_count-1;
  84         if (!ctx->dir_info)
  85                 return 0;
  86         if (ino == ctx->dir_info[low].ino)
  87                 return &ctx->dir_info[low];
  88         if  (ino == ctx->dir_info[high].ino)
  89                 return &ctx->dir_info[high];
  90
  91         while (low < high) {
  92                 mid = (low+high)/2;
  93                 if (mid == low || mid == high)
  94                         break;
  95                 if (ino == ctx->dir_info[mid].ino)
  96                         return &ctx->dir_info[mid];
  97                 if (ino < ctx->dir_info[mid].ino)
  98                         high = mid;
  99                 else
 100                         low = mid;
 101         }
 102         return 0;
 103 }
 104
 105 /*
 106  * Free the dir_info structure when it isn't needed any more.
 107  */
 108 void e2fsck_free_dir_info(e2fsck_t ctx)
 109 {
 110         if (ctx->dir_info) {
 111                 ext2fs_free_mem((void **) &ctx->dir_info);
 112                 ctx->dir_info = 0;
 113         }
 114         ctx->dir_info_size = 0;
 115         ctx->dir_info_count = 0;
 116 }
 117
 118 /*
 119  * Return the count of number of directories in the dir_info structure
 120  */
 121 int e2fsck_get_num_dirinfo(e2fsck_t ctx)
 122 {
 123         return ctx->dir_info_count;
 124 }
 125
 126 /*
 127  * A simple interator function
 128  */
 129 struct dir_info *e2fsck_dir_info_iter(e2fsck_t ctx, int *control)
 130 {
 131         if (*control >= ctx->dir_info_count)
 132                 return 0;
 133
 134         return(ctx->dir_info + (*control)++);
 135 }