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