dirinfo.c revision 86c627ec1136446409a0170d439e60c148e6eb48 
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, ext2_ino_t ino, ext2_ino_t parent)
16{
17	struct dir_info *dir;
18	int		i, j;
19	ext2_ino_t	num_dirs;
20	errcode_t	retval;
21	unsigned long	old_size;
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  = (struct dir_info *)
33			e2fsck_allocate_memory(ctx, ctx->dir_info_size
34					       * sizeof (struct dir_info),
35					       "directory map");
36	}
37
38	if (ctx->dir_info_count >= ctx->dir_info_size) {
39		old_size = ctx->dir_info_size * sizeof(struct dir_info);
40		ctx->dir_info_size += 10;
41		retval = ext2fs_resize_mem(old_size, ctx->dir_info_size *
42					   sizeof(struct dir_info),
43					   (void **) &ctx->dir_info);
44		if (retval) {
45			ctx->dir_info_size -= 10;
46			return;
47		}
48	}
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	 */
59	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)
63				break;
64		dir = &ctx->dir_info[i];
65		if (dir->ino != ino)
66			for (j = ctx->dir_info_count++; j > i; j--)
67				ctx->dir_info[j] = ctx->dir_info[j-1];
68	} else
69		dir = &ctx->dir_info[ctx->dir_info_count++];
70
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 */
80struct dir_info *e2fsck_get_dir_info(e2fsck_t ctx, ext2_ino_t ino)
81{
82	int	low, high, mid;
83
84	low = 0;
85	high = ctx->dir_info_count-1;
86	if (!ctx->dir_info)
87		return 0;
88	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];
92
93	while (low < high) {
94		mid = (low+high)/2;
95		if (mid == low || mid == high)
96			break;
97		if (ino == ctx->dir_info[mid].ino)
98			return &ctx->dir_info[mid];
99		if (ino < ctx->dir_info[mid].ino)
100			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 */
110void e2fsck_free_dir_info(e2fsck_t ctx)
111{
112	if (ctx->dir_info) {
113		ext2fs_free_mem((void **) &ctx->dir_info);
114		ctx->dir_info = 0;
115	}
116	ctx->dir_info_size = 0;
117	ctx->dir_info_count = 0;
118}
119
120/*
121 * 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/*
129 * A simple interator function
130 */
131struct dir_info *e2fsck_dir_info_iter(e2fsck_t ctx, int *control)
132{
133	if (*control >= ctx->dir_info_count)
134		return 0;
135
136	return(ctx->dir_info + (*control)++);
137}
138