[thirdparty/e2fsprogs.git] / e2fsck / dx_dirinfo.c

/*
 * 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"
#ifdef ENABLE_HTREE

/*
 * 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_dx_dir(e2fsck_t ctx, ext2_ino_t ino, int num_blocks)
{
	struct dx_dir_info *dir;
	int		i, j;
	errcode_t	retval;
	unsigned long	old_size;

#if 0
	printf("add_dx_dir_info for inode %lu...\n", ino);
#endif
	if (!ctx->dx_dir_info) {
		ctx->dx_dir_info_count = 0;
		ctx->dx_dir_info_size = 100; /* Guess */
		ctx->dx_dir_info  = (struct dx_dir_info *)
			e2fsck_allocate_memory(ctx, ctx->dx_dir_info_size
					       * sizeof (struct dx_dir_info),
					       "directory map");
	}
	
	if (ctx->dx_dir_info_count >= ctx->dx_dir_info_size) {
		old_size = ctx->dx_dir_info_size * sizeof(struct dx_dir_info);
		ctx->dx_dir_info_size += 10;
		retval = ext2fs_resize_mem(old_size, ctx->dx_dir_info_size *
					   sizeof(struct dx_dir_info),
					   (void **) &ctx->dx_dir_info);
		if (retval) {
			ctx->dx_dir_info_size -= 10;
			return;
		}
	}

	/*
	 * Normally, add_dx_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 dx_dir_info entries down to make room, since
	 * the dx_dir_info array needs to be sorted by inode number for
	 * get_dx_dir_info()'s sake.
	 */
	if (ctx->dx_dir_info_count &&
	    ctx->dx_dir_info[ctx->dx_dir_info_count-1].ino >= ino) {
		for (i = ctx->dx_dir_info_count-1; i > 0; i--)
			if (ctx->dx_dir_info[i-1].ino < ino)
				break;
		dir = &ctx->dx_dir_info[i];
		if (dir->ino != ino) 
			for (j = ctx->dx_dir_info_count++; j > i; j--)
				ctx->dx_dir_info[j] = ctx->dx_dir_info[j-1];
	} else
		dir = &ctx->dx_dir_info[ctx->dx_dir_info_count++];
	
	dir->ino = ino;
	dir->numblocks = num_blocks;
	dir->hashversion = 0;
	dir->dx_block = e2fsck_allocate_memory(ctx, num_blocks
				       * sizeof (struct dx_dirblock_info),
				       "dx_block info array");

}

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

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

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

/*
 * Free the dx_dir_info structure when it isn't needed any more.
 */
void e2fsck_free_dx_dir_info(e2fsck_t ctx)
{
	int	i;
	struct dx_dir_info *dir;
	
	if (ctx->dx_dir_info) {
		dir = ctx->dx_dir_info;
		for (i=0; i < ctx->dx_dir_info_count; i++) {
			if (dir->dx_block) {
				ext2fs_free_mem((void **) &dir->dx_block);
				dir->dx_block = 0;
			}
		}
		ext2fs_free_mem((void **) &ctx->dx_dir_info);
		ctx->dx_dir_info = 0;
	}
	ctx->dx_dir_info_size = 0;
	ctx->dx_dir_info_count = 0;
}

/*
 * Return the count of number of directories in the dx_dir_info structure
 */
int e2fsck_get_num_dx_dirinfo(e2fsck_t ctx)
{
	return ctx->dx_dir_info_count;
}

/*
 * A simple interator function
 */
struct dx_dir_info *e2fsck_dx_dir_info_iter(e2fsck_t ctx, int *control)
{
	if (*control >= ctx->dx_dir_info_count)
		return 0;

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

#endif /* ENABLE_HTREE */
Commit	Line	Data
8fdc9985 TT	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	*/
	16	void 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	(void **) &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	*/
81	struct 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	*/
111	void 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++) {
119	if (dir->dx_block) {
120	ext2fs_free_mem((void **) &dir->dx_block);
121	dir->dx_block = 0;
122	}
123	}
124	ext2fs_free_mem((void **) &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	*/
134	int 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	*/
142	struct 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 */