blob: fe8155fb6680267adb618b2af5a6c534a8992fbb [file] [log] [blame]
Theodore Ts'o3839e651997-04-26 13:21:57 +00001/*
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
Theodore Ts'o3839e651997-04-26 13:21:57 +00008#include "e2fsck.h"
9
Theodore Ts'o3839e651997-04-26 13:21:57 +000010/*
Theodore Ts'o21c84b71997-04-29 16:15:03 +000011 * This subroutine is called during pass1 to create a directory info
12 * entry. During pass1, the passed-in parent is 0; it will get filled
13 * in during pass2.
Theodore Ts'o3839e651997-04-26 13:21:57 +000014 */
Theodore Ts'o08b21301997-11-03 19:42:40 +000015void e2fsck_add_dir_info(e2fsck_t ctx, ino_t ino, ino_t parent)
Theodore Ts'o3839e651997-04-26 13:21:57 +000016{
17 struct dir_info *dir;
Theodore Ts'o08b21301997-11-03 19:42:40 +000018 int i, j;
Theodore Ts'o5be8dc21997-12-01 18:24:10 +000019 ino_t num_dirs;
Theodore Ts'o08b21301997-11-03 19:42:40 +000020 errcode_t retval;
Theodore Ts'o76f875d1998-04-27 01:41:13 +000021 unsigned long old_size;
Theodore Ts'o3839e651997-04-26 13:21:57 +000022
23#if 0
Theodore Ts'of3db3561997-04-26 13:34:30 +000024 printf("add_dir_info for inode %lu...\n", ino);
Theodore Ts'o3839e651997-04-26 13:21:57 +000025#endif
Theodore Ts'o08b21301997-11-03 19:42:40 +000026 if (!ctx->dir_info) {
27 ctx->dir_info_count = 0;
Theodore Ts'o5be8dc21997-12-01 18:24:10 +000028 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;
Theodore Ts'o54dc7ca1998-01-19 14:50:49 +000032 ctx->dir_info = (struct dir_info *)
33 e2fsck_allocate_memory(ctx, ctx->dir_info_size
34 * sizeof (struct dir_info),
35 "directory map");
Theodore Ts'o3839e651997-04-26 13:21:57 +000036 }
37
Theodore Ts'o08b21301997-11-03 19:42:40 +000038 if (ctx->dir_info_count >= ctx->dir_info_size) {
Theodore Ts'o76f875d1998-04-27 01:41:13 +000039 old_size = ctx->dir_info_size * sizeof(struct dir_info);
Theodore Ts'o08b21301997-11-03 19:42:40 +000040 ctx->dir_info_size += 10;
Theodore Ts'o76f875d1998-04-27 01:41:13 +000041 retval = ext2fs_resize_mem(old_size, ctx->dir_info_size *
Theodore Ts'o08b21301997-11-03 19:42:40 +000042 sizeof(struct dir_info),
43 (void **) &ctx->dir_info);
44 if (retval) {
45 ctx->dir_info_size -= 10;
46 return;
47 }
Theodore Ts'o3839e651997-04-26 13:21:57 +000048 }
49
50 /*
51 * Normally, add_dir_info is called with each inode in
52 * sequential order; but once in a while (like when pass 3
53 * needs to recreate the root directory or lost+found
54 * directory) it is called out of order. In those cases, we
55 * need to move the dir_info entries down to make room, since
56 * the dir_info array needs to be sorted by inode number for
57 * get_dir_info()'s sake.
58 */
Theodore Ts'o08b21301997-11-03 19:42:40 +000059 if (ctx->dir_info_count &&
60 ctx->dir_info[ctx->dir_info_count-1].ino >= ino) {
61 for (i = ctx->dir_info_count-1; i > 0; i--)
62 if (ctx->dir_info[i-1].ino < ino)
Theodore Ts'o3839e651997-04-26 13:21:57 +000063 break;
Theodore Ts'o08b21301997-11-03 19:42:40 +000064 dir = &ctx->dir_info[i];
Theodore Ts'o3839e651997-04-26 13:21:57 +000065 if (dir->ino != ino)
Theodore Ts'o08b21301997-11-03 19:42:40 +000066 for (j = ctx->dir_info_count++; j > i; j--)
67 ctx->dir_info[j] = ctx->dir_info[j-1];
Theodore Ts'o3839e651997-04-26 13:21:57 +000068 } else
Theodore Ts'o08b21301997-11-03 19:42:40 +000069 dir = &ctx->dir_info[ctx->dir_info_count++];
Theodore Ts'o3839e651997-04-26 13:21:57 +000070
71 dir->ino = ino;
72 dir->dotdot = parent;
73 dir->parent = parent;
74}
75
76/*
77 * get_dir_info() --- given an inode number, try to find the directory
78 * information entry for it.
79 */
Theodore Ts'o08b21301997-11-03 19:42:40 +000080struct dir_info *e2fsck_get_dir_info(e2fsck_t ctx, ino_t ino)
Theodore Ts'o3839e651997-04-26 13:21:57 +000081{
82 int low, high, mid;
83
84 low = 0;
Theodore Ts'o08b21301997-11-03 19:42:40 +000085 high = ctx->dir_info_count-1;
86 if (!ctx->dir_info)
Theodore Ts'o21c84b71997-04-29 16:15:03 +000087 return 0;
Theodore Ts'o08b21301997-11-03 19:42:40 +000088 if (ino == ctx->dir_info[low].ino)
89 return &ctx->dir_info[low];
90 if (ino == ctx->dir_info[high].ino)
91 return &ctx->dir_info[high];
Theodore Ts'o3839e651997-04-26 13:21:57 +000092
93 while (low < high) {
94 mid = (low+high)/2;
95 if (mid == low || mid == high)
96 break;
Theodore Ts'o08b21301997-11-03 19:42:40 +000097 if (ino == ctx->dir_info[mid].ino)
98 return &ctx->dir_info[mid];
99 if (ino < ctx->dir_info[mid].ino)
Theodore Ts'o3839e651997-04-26 13:21:57 +0000100 high = mid;
101 else
102 low = mid;
103 }
104 return 0;
105}
106
107/*
108 * Free the dir_info structure when it isn't needed any more.
109 */
Theodore Ts'o08b21301997-11-03 19:42:40 +0000110void e2fsck_free_dir_info(e2fsck_t ctx)
Theodore Ts'o3839e651997-04-26 13:21:57 +0000111{
Theodore Ts'o08b21301997-11-03 19:42:40 +0000112 if (ctx->dir_info) {
113 ext2fs_free_mem((void **) &ctx->dir_info);
114 ctx->dir_info = 0;
Theodore Ts'o3839e651997-04-26 13:21:57 +0000115 }
Theodore Ts'o08b21301997-11-03 19:42:40 +0000116 ctx->dir_info_size = 0;
117 ctx->dir_info_count = 0;
Theodore Ts'o3839e651997-04-26 13:21:57 +0000118}
Theodore Ts'o21c84b71997-04-29 16:15:03 +0000119
120/*
Theodore Ts'of8188ff1997-11-14 05:23:04 +0000121 * Return the count of number of directories in the dir_info structure
122 */
123int e2fsck_get_num_dirinfo(e2fsck_t ctx)
124{
125 return ctx->dir_info_count;
126}
127
128/*
Theodore Ts'o21c84b71997-04-29 16:15:03 +0000129 * A simple interator function
130 */
Theodore Ts'o08b21301997-11-03 19:42:40 +0000131struct dir_info *e2fsck_dir_info_iter(e2fsck_t ctx, int *control)
Theodore Ts'o21c84b71997-04-29 16:15:03 +0000132{
Theodore Ts'o08b21301997-11-03 19:42:40 +0000133 if (*control >= ctx->dir_info_count)
Theodore Ts'o21c84b71997-04-29 16:15:03 +0000134 return 0;
135
Theodore Ts'o08b21301997-11-03 19:42:40 +0000136 return(ctx->dir_info + (*control)++);
Theodore Ts'o21c84b71997-04-29 16:15:03 +0000137}