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 "config.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 */
16void e2fsck_add_dx_dir(e2fsck_t ctx, ext2_ino_t ino, int num_blocks)
17{
18	struct dx_dir_info *dir;
19	int		i, j;
20	errcode_t	retval;
21	unsigned long	old_size;
22
23#if 0
24	printf("add_dx_dir_info for inode %lu...\n", ino);
25#endif
26	if (!ctx->dx_dir_info) {
27		ctx->dx_dir_info_count = 0;
28		ctx->dx_dir_info_size = 100; /* Guess */
29		ctx->dx_dir_info  = (struct dx_dir_info *)
30			e2fsck_allocate_memory(ctx, ctx->dx_dir_info_size
31					       * sizeof (struct dx_dir_info),
32					       "directory map");
33	}
34
35	if (ctx->dx_dir_info_count >= ctx->dx_dir_info_size) {
36		old_size = ctx->dx_dir_info_size * sizeof(struct dx_dir_info);
37		ctx->dx_dir_info_size += 10;
38		retval = ext2fs_resize_mem(old_size, ctx->dx_dir_info_size *
39					   sizeof(struct dx_dir_info),
40					   &ctx->dx_dir_info);
41		if (retval) {
42			fprintf(stderr, "Couldn't reallocate dx_dir_info "
43				"structure to %d entries\n",
44				ctx->dx_dir_info_size);
45			fatal_error(ctx, 0);
46			ctx->dx_dir_info_size -= 10;
47			return;
48		}
49	}
50
51	/*
52	 * Normally, add_dx_dir_info is called with each inode in
53	 * sequential order; but once in a while (like when pass 3
54	 * needs to recreate the root directory or lost+found
55	 * directory) it is called out of order.  In those cases, we
56	 * need to move the dx_dir_info entries down to make room, since
57	 * the dx_dir_info array needs to be sorted by inode number for
58	 * get_dx_dir_info()'s sake.
59	 */
60	if (ctx->dx_dir_info_count &&
61	    ctx->dx_dir_info[ctx->dx_dir_info_count-1].ino >= ino) {
62		for (i = ctx->dx_dir_info_count-1; i > 0; i--)
63			if (ctx->dx_dir_info[i-1].ino < ino)
64				break;
65		dir = &ctx->dx_dir_info[i];
66		if (dir->ino != ino)
67			for (j = ctx->dx_dir_info_count++; j > i; j--)
68				ctx->dx_dir_info[j] = ctx->dx_dir_info[j-1];
69	} else
70		dir = &ctx->dx_dir_info[ctx->dx_dir_info_count++];
71
72	dir->ino = ino;
73	dir->numblocks = num_blocks;
74	dir->hashversion = 0;
75	dir->dx_block = e2fsck_allocate_memory(ctx, num_blocks
76				       * sizeof (struct dx_dirblock_info),
77				       "dx_block info array");
78
79}
80
81/*
82 * get_dx_dir_info() --- given an inode number, try to find the directory
83 * information entry for it.
84 */
85struct dx_dir_info *e2fsck_get_dx_dir_info(e2fsck_t ctx, ext2_ino_t ino)
86{
87	int	low, high, mid;
88
89	low = 0;
90	high = ctx->dx_dir_info_count-1;
91	if (!ctx->dx_dir_info)
92		return 0;
93	if (ino == ctx->dx_dir_info[low].ino)
94		return &ctx->dx_dir_info[low];
95	if  (ino == ctx->dx_dir_info[high].ino)
96		return &ctx->dx_dir_info[high];
97
98	while (low < high) {
99		mid = (low+high)/2;
100		if (mid == low || mid == high)
101			break;
102		if (ino == ctx->dx_dir_info[mid].ino)
103			return &ctx->dx_dir_info[mid];
104		if (ino < ctx->dx_dir_info[mid].ino)
105			high = mid;
106		else
107			low = mid;
108	}
109	return 0;
110}
111
112/*
113 * Free the dx_dir_info structure when it isn't needed any more.
114 */
115void e2fsck_free_dx_dir_info(e2fsck_t ctx)
116{
117	int	i;
118	struct dx_dir_info *dir;
119
120	if (ctx->dx_dir_info) {
121		dir = ctx->dx_dir_info;
122		for (i=0; i < ctx->dx_dir_info_count; i++,dir++) {
123			if (dir->dx_block) {
124				ext2fs_free_mem(&dir->dx_block);
125				dir->dx_block = 0;
126			}
127		}
128		ext2fs_free_mem(&ctx->dx_dir_info);
129		ctx->dx_dir_info = 0;
130	}
131	ctx->dx_dir_info_size = 0;
132	ctx->dx_dir_info_count = 0;
133}
134
135/*
136 * Return the count of number of directories in the dx_dir_info structure
137 */
138int e2fsck_get_num_dx_dirinfo(e2fsck_t ctx)
139{
140	return ctx->dx_dir_info_count;
141}
142
143/*
144 * A simple interator function
145 */
146struct dx_dir_info *e2fsck_dx_dir_info_iter(e2fsck_t ctx, int *control)
147{
148	if (*control >= ctx->dx_dir_info_count)
149		return 0;
150
151	return(ctx->dx_dir_info + (*control)++);
152}
153