summaryrefslogtreecommitdiff
path: root/e2fsprogs/e2fsck/dirinfo.c
blob: 516c4613504c8c95fe04f64a991390c86863c5bd (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
/*
 * dirinfo.c --- maintains the directory information table for e2fsck.
 *
 * Copyright (C) 1993 Theodore Ts'o.  This file may be redistributed
 * under the terms of the GNU Public License.
 */

#include "e2fsck.h"

/*
 * This subroutine is called during pass1 to create a directory info
 * entry.  During pass1, the passed-in parent is 0; it will get filled
 * in during pass2.  
 */
void e2fsck_add_dir_info(e2fsck_t ctx, ext2_ino_t ino, ext2_ino_t parent)
{
	struct dir_info *dir;
	int		i, j;
	ext2_ino_t	num_dirs;
	errcode_t	retval;
	unsigned long	old_size;

#if 0
	printf("add_dir_info for inode %lu...\n", ino);
#endif
	if (!ctx->dir_info) {
		ctx->dir_info_count = 0;
		retval = ext2fs_get_num_dirs(ctx->fs, &num_dirs);
		if (retval)
			num_dirs = 1024;	/* Guess */
		ctx->dir_info_size = num_dirs + 10;
		ctx->dir_info  = (struct dir_info *)
			e2fsck_allocate_memory(ctx, ctx->dir_info_size
					       * sizeof (struct dir_info),
					       "directory map");
	}
	
	if (ctx->dir_info_count >= ctx->dir_info_size) {
		old_size = ctx->dir_info_size * sizeof(struct dir_info);
		ctx->dir_info_size += 10;
		retval = ext2fs_resize_mem(old_size, ctx->dir_info_size *
					   sizeof(struct dir_info),
					   &ctx->dir_info);
		if (retval) {
			ctx->dir_info_size -= 10;
			return;
		}
	}

	/*
	 * Normally, add_dir_info is called with each inode in
	 * sequential order; but once in a while (like when pass 3
	 * needs to recreate the root directory or lost+found
	 * directory) it is called out of order.  In those cases, we
	 * need to move the dir_info entries down to make room, since
	 * the dir_info array needs to be sorted by inode number for
	 * get_dir_info()'s sake.
	 */
	if (ctx->dir_info_count &&
	    ctx->dir_info[ctx->dir_info_count-1].ino >= ino) {
		for (i = ctx->dir_info_count-1; i > 0; i--)
			if (ctx->dir_info[i-1].ino < ino)
				break;
		dir = &ctx->dir_info[i];
		if (dir->ino != ino) 
			for (j = ctx->dir_info_count++; j > i; j--)
				ctx->dir_info[j] = ctx->dir_info[j-1];
	} else
		dir = &ctx->dir_info[ctx->dir_info_count++];
	
	dir->ino = ino;
	dir->dotdot = parent;
	dir->parent = parent;
}

/*
 * get_dir_info() --- given an inode number, try to find the directory
 * information entry for it.
 */
struct dir_info *e2fsck_get_dir_info(e2fsck_t ctx, ext2_ino_t ino)
{
	int	low, high, mid;

	low = 0;
	high = ctx->dir_info_count-1;
	if (!ctx->dir_info)
		return 0;
	if (ino == ctx->dir_info[low].ino)
		return &ctx->dir_info[low];
	if  (ino == ctx->dir_info[high].ino)
		return &ctx->dir_info[high];

	while (low < high) {
		mid = (low+high)/2;
		if (mid == low || mid == high)
			break;
		if (ino == ctx->dir_info[mid].ino)
			return &ctx->dir_info[mid];
		if (ino < ctx->dir_info[mid].ino)
			high = mid;
		else
			low = mid;
	}
	return 0;
}

/*
 * Free the dir_info structure when it isn't needed any more.
 */
void e2fsck_free_dir_info(e2fsck_t ctx)
{
	if (ctx->dir_info) {
		ext2fs_free_mem(&ctx->dir_info);
		ctx->dir_info = 0;
	}
	ctx->dir_info_size = 0;
	ctx->dir_info_count = 0;
}

/*
 * Return the count of number of directories in the dir_info structure
 */
int e2fsck_get_num_dirinfo(e2fsck_t ctx)
{
	return ctx->dir_info_count;
}

/*
 * A simple interator function
 */
struct dir_info *e2fsck_dir_info_iter(e2fsck_t ctx, int *control)
{
	if (*control >= ctx->dir_info_count)
		return 0;

	return(ctx->dir_info + (*control)++);
}