36 #include "udefrag-internals.h"
51 ULONGLONG min_lcn,ULONGLONG min_length,ULONGLONG *max_length)
53 winx_volume_region *rgn;
54 ULONGLONG time = winx_xtime();
56 if(max_length) *max_length = 0;
57 for(rgn = jp->free_regions; rgn; rgn = rgn->next){
58 if(jp->termination_router((
void *)jp))
break;
59 if(rgn->lcn >= min_lcn){
61 if(rgn->length > *max_length)
62 *max_length = rgn->length;
64 if(rgn->length >= min_length){
65 jp->p_counters.searching_time += winx_xtime() - time;
69 if(rgn->next == jp->free_regions)
break;
71 jp->p_counters.searching_time += winx_xtime() - time;
84 ULONGLONG min_lcn,ULONGLONG min_length,ULONGLONG *max_length)
86 winx_volume_region *rgn;
87 ULONGLONG time = winx_xtime();
89 if(max_length) *max_length = 0;
91 for(rgn = jp->free_regions->prev; rgn; rgn = rgn->prev){
92 if(jp->termination_router((
void *)jp))
break;
93 if(rgn->lcn < min_lcn)
break;
95 if(rgn->length > *max_length)
96 *max_length = rgn->length;
98 if(rgn->length >= min_length){
99 jp->p_counters.searching_time += winx_xtime() - time;
102 if(rgn->prev == jp->free_regions->prev)
break;
105 jp->p_counters.searching_time += winx_xtime() - time;
123 ULONGLONG start_lcn, ULONGLONG min_length,
int preferred_position)
125 winx_volume_region *rgn, *rgn_matching;
127 ULONGLONG time = winx_xtime();
129 rgn_matching = NULL, length = 0;
130 for(rgn = jp->free_regions; rgn; rgn = rgn->next){
131 if(jp->termination_router((
void *)jp)){
132 jp->p_counters.searching_time += winx_xtime() - time;
135 if(preferred_position == FIND_MATCHING_RGN_BACKWARD \
136 && rgn->lcn > start_lcn)
137 if(rgn_matching != NULL)
139 if(rgn->length >= min_length){
140 if(length == 0 || rgn->length < length){
142 length = rgn->length;
143 if(length == min_length \
144 && preferred_position != FIND_MATCHING_RGN_FORWARD)
148 if(rgn->next == jp->free_regions)
break;
150 jp->p_counters.searching_time += winx_xtime() - time;
162 winx_volume_region *rgn, *rgn_largest;
164 ULONGLONG time = winx_xtime();
166 rgn_largest = NULL, length = 0;
167 for(rgn = jp->free_regions; rgn; rgn = rgn->next){
168 if(jp->termination_router((
void *)jp)){
169 jp->p_counters.searching_time += winx_xtime() - time;
172 if(rgn->length > length){
174 length = rgn->length;
176 if(rgn->next == jp->free_regions)
break;
178 jp->p_counters.searching_time += winx_xtime() - time;
190 winx_file_info *file;
191 winx_blockmap *block;
197 static int blocks_compare(
const void *prb_a,
const void *prb_b,
void *prb_param)
199 struct file_block *a, *b;
201 a = (
struct file_block *)prb_a;
202 b = (
struct file_block *)prb_b;
204 if(a->block->lcn < b->block->lcn)
206 if(a->block->lcn == b->block->lcn)
214 static void free_item (
void *prb_item,
void *prb_param)
216 struct file_block *item = (
struct file_block *)prb_item;
232 trace(I
"create_file_blocks_tree called");
240 jp->file_blocks = prb_create(blocks_compare,NULL,NULL);
241 if(jp->file_blocks == NULL){
242 etrace(
"tree creation failed");
257 struct file_block *fb;
260 if(jp == NULL || file == NULL || block == NULL)
263 if(jp->file_blocks == NULL)
266 fb = winx_malloc(
sizeof *fb);
269 return UDEFRAG_NO_MEM;
274 p = prb_probe(jp->file_blocks,(
void *)fb);
278 return UDEFRAG_NO_MEM;
282 etrace(
"a duplicate found");
296 struct file_block *fb;
299 if(jp == NULL || block == NULL)
302 if(jp->file_blocks == NULL)
307 fb = prb_delete(jp->file_blocks,&b);
311 etrace(
"failed for %p: VCN = %I64u, LCN = %I64u, LEN = %I64u",
312 block, block->vcn, block->lcn, block->length);
326 trace(I
"destroy_file_blocks_tree called");
329 prb_destroy(jp->file_blocks,free_item);
330 jp->file_blocks = NULL;
351 ULONGLONG *min_lcn,
int flags, winx_file_info **first_file)
353 winx_file_info *found_file, *file;
354 winx_blockmap *first_block, *block;
356 struct file_block fb, *item;
357 struct prb_traverser t;
360 ULONGLONG tm = winx_xtime();
362 if(jp == NULL || min_lcn == NULL || first_file == NULL)
366 if(jp->file_blocks == NULL)
goto slow_search;
367 found_file = NULL; first_block = NULL;
368 b.lcn = *min_lcn; fb.block = &b;
369 prb_t_init(&t,jp->file_blocks);
370 item = prb_t_insert(&t,jp->file_blocks,&fb);
373 itrace(
"slow search will be used");
378 item = prb_t_next(&t);
379 if(prb_delete(jp->file_blocks,&fb) == NULL){
381 itrace(
"slow search will be used");
386 found_file = item->file;
387 first_block = item->block;
389 while(!jp->termination_router((
void *)jp)){
390 if(found_file == NULL)
break;
391 if(flags & SKIP_PARTIALLY_MOVABLE_FILES){
392 movable_file = can_move_entirely(found_file,jp);
394 movable_file = can_move(found_file,jp);
396 if(is_file_locked(found_file,jp)) movable_file = 0;
398 if(jp->is_fat && is_directory(found_file) && first_block == found_file->disp.blockmap){
402 *min_lcn = first_block->lcn + 1;
403 *first_file = found_file;
404 jp->p_counters.searching_time += winx_xtime() - tm;
410 *min_lcn = *min_lcn + 1;
412 item = prb_t_next(&t);
413 if(item == NULL)
break;
414 found_file = item->file;
415 first_block = item->block;
418 jp->p_counters.searching_time += winx_xtime() - tm;
423 while(!jp->termination_router((
void *)jp)){
424 found_file = NULL; first_block = NULL; lcn = jp->v_info.total_clusters;
425 for(file = jp->filelist; file; file = file->next){
426 if(flags & SKIP_PARTIALLY_MOVABLE_FILES){
427 movable_file = can_move_entirely(file,jp);
429 movable_file = can_move(file,jp);
432 for(block = file->disp.blockmap; block; block = block->next){
433 if(block->lcn >= *min_lcn && block->lcn < lcn && block->length){
435 if(!jp->is_fat || !is_directory(file) || block != file->disp.blockmap){
441 if(block->next == file->disp.blockmap)
break;
444 if(file->next == jp->filelist)
break;
446 if(found_file == NULL)
break;
447 if(is_file_locked(found_file,jp))
continue;
450 *min_lcn = first_block->lcn + 1;
451 *first_file = found_file;
452 jp->p_counters.searching_time += winx_xtime() - tm;
456 jp->p_counters.searching_time += winx_xtime() - tm;