dirinfo.c revision 54be2ccc2251784fd771590a5e72827afd82df40 
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
10/*
11 * 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.
14 */
15void e2fsck_add_dir_info(e2fsck_t ctx, ino_t ino, ino_t parent)
16{
17	struct dir_info *dir;
18	int		i, j;
19	ino_t		num_dirs;
20	errcode_t	retval;
21
22#if 0
23	printf("add_dir_info for inode %lu...\n", ino);
24#endif
25	if (!ctx->dir_info) {
26		ctx->dir_info_count = 0;
27		retval = ext2fs_get_num_dirs(ctx->fs, &num_dirs);
28		if (retval)
29			num_dirs = 1024;	/* Guess */
30		ctx->dir_info_size = num_dirs + 10;
31		ctx->dir_info  = (struct dir_info *)
32			e2fsck_allocate_memory(ctx, ctx->dir_info_size
33					       * 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 */
78struct 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 */
108void 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 */
121int e2fsck_get_num_dirinfo(e2fsck_t ctx)
122{
123	return ctx->dir_info_count;
124}
125
126/*
127 * A simple interator function
128 */
129struct 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}
136