Home | History | Annotate | Download | only in e2fsck 
      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 					   &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++,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  */
    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 */
    151