Паша Звягинцев дата публикации 17-12-2004 11:52 Обход дерева каталогов с прерыванием и возобновлением или "Куда мы идем завтра?"Программист, просыпаясь утром с сильнейшего похмелья
начинает с тестирования памяти...
Недавно занимаясь интересной задачкой по написанию службы индексации, столкнулся с интересным вопросом: " А как бы нам поиск заморозить и продолжить после (через минуту, завтра, через месяц)?". Да конечно можно сказать - что у тебя за машина такая, вот у меня дерево каталогов обходит за 3 минуты... Согласен, это не вопрос. Но когда нужно не просто обходить, а еще и выполнять некоторые действия с файлами, да если их на диске 150 тыс. и больше, да еще не загружая процессор на 100%, то время может затянуться до нескольких суток, вот тогда - как быть?
Вот этой теме я и решил посвятить статью. Как оказалось, в Интернете информации по этой теме нет. Либо это слишком просто, либо никому не нужно. Как выяснилось - ни то ни другое.
Со стандартной процедурой обхода дерева сталкивались очень многие
procedure FileFind(path:string);
var sr:Tsearchrec;
found:integer;
begin
found:=FindFirst(path + '\*.*', FaAnyfile, sr);
while (found = 0) do
begin
if (sr.name <> '.') and (sr.name <> '..') then
begin
if (sr.attr and FaDirectory) = FaDirectory then
FileFind(path+'\'+sr.name)
else
begin
......
mainform.memo1.lines.append(path+'\'+sr.name);
end
end;
found:=findnext(sr);
end;
FindClose(sr);
end;
| |
Казалось бы сохранить состояние процедуры поиска просто - достаточно сохранить структуру - sr:TsearchRec, а потом ее восстановить и поиск продолжится.
- Первое
- Однако при даже невнимательном рассмотрении процедуры видно, что она вызывает сама себя - налицо обычная рекурсия. Получается что надо сохранять не одну SearchRec, а несколько. Полдела - сохранить, но ведь нужно и восстановить эти рекурсивные вызовы. Т.е при продолжении поиска построить этакую матрешку из процедур поиска, а потом уже его продолжать.
- Второе
- — сама SearchRec. Казалось бы она находится в области данных нашей программы. Да это наполовину верно. Верхняя половина SearchRec действительно лежит в области данных нашей программы и делать мы с ней можем что душе угодно. Это переменные Time: Integer; Size: Integer; Attr: Integer; Name:TFileName; ExcludeAttr: Integer;. А вот вторая ее половина (FindHandle: THandle; FindData: TWin32FindData;) нам не принадлежит -ее генерирует система по нашему запросу FindFirst(.....) и уничтожает по команде FindClose(....).
- Третий,
- казалось бы, простой вопрос — SearchRec.Name имеет тип TFileName=TString. Какую длину он имеет? Одни скажут 255, другие 65535. Согласен, и то и другое верно, но не тут. Длина действительно 255. А вот с типом нас нагло обманули. Реально в памяти хранится не TString [255], а PChar {Имя файла}+PChar{его расширение}. Для нас с вами это преобразуется в обычную строку при обращении, и до столкновения с данной ситуацией я свято верил что там TString[255]. Кстати в чем разница между Богом и билом гейтсом? Бог не считает себя билом гейтсом ...
И так попробуем решить эти проблемы. Проше всего разбор начать в обратном порядке... (не подумайте превратно, я знаю через что рвут гланды в России...)
Третий вопрос - как сохранить , а потом восстановить SearchRec, если он состоит непонятно из чего. А давайте сделаем свой SearchRec, как нам нужно. А именно так
type
TMysearchRec = record
Time: Integer;
Size: Integer;
Attr: Integer;
Name: string[250];
ExcludeAttr: Integer;
FindHandle: THandle;
FindData: TWin32FindData;
end;
| |
но нам еще требуется сохранять несколько переменных самой программы, а именно Found - найдено чтото или нет и Path - с каким параметром нас вызывали, поэтому на основе этого типа делаем еще один
TMyRec_Sea = record
Rec_Sea:TMySearchRec;
path:String[250];
found:integer;
end;
| |
Второй вопрос после первого решается не очень красиво, но довольно легко. Да система генерит структуру: FindHandle: THandle; FindData: TWin32FindData. FindData - собственно сама структура и FindHandle - указатель на нее. Пусть система генерит что угодно, если с умом, то можно обойти и это. Многие ли помнят такое INT21h->INT 13H. Думаю вспомнили. При восстановлении поиска дадим команду FindFirst, а потом подменим FindData и остальные поля, не трогая FindHandle, иначе сразу после окончания поиска (!!! ???) получим обращение к недопустимому адресу и вылет программы.
......
FindFirst(path+'\'+mask, FaAnyfile, sr);
delfile:=false; found:=buffer.found;
sr.Time:=buffer.rec_sea.Time;
sr.Size:=buffer.rec_sea.Size;
sr.Attr:=buffer.rec_sea.Attr;
sr.Name:=buffer.rec_sea.Name;
sr.ExcludeAttr:=buffer.rec_sea.ExcludeAttr;
sr.FindData:=buffer.rec_sea.FindData;
| |
Первый вопрос - как же сохранять состояние процедуры при рекурсии?. Давайте сохранять SearchRec в файл и используем принцип магазина (не продуктового, а от автомата калашникова) - последний вошел - первый вышел. Вот примерная структура процедуры при выполняющемся поиске ( при нескольких рекурсивных вызовах)
Findfile('c:\')
Findfile('c:\Docs')
FindFile(c:\Docs\Delphi')
......
При получении сигнала на остановку процедуры начинают писать в файл в обратном порядке, а именно - FindFile(c:\Docs\Delphi'),Findfile('c:\Docs'),Findfile('c:\'). Примерно так
Findfile('c:\')------------------------------------+
Findfile('c:\Docs')---------------------+ !
FindFile(c:\Docs\Delphi') ---+ ! !
v v v
[файл сохранений состояния] [rec1] [rec2] [rec3]
Ну а когда нужно восстановить состояние поиска смотрим не пустой ли файл сохранений, и читаем записи начиная с конца, после прочтения их удаляем. Таким образом поиск по дереву автоматом развернется на столько рекурсивных вызовов, сколько надо, и продолжит поиск.
Да, едва не забыл, как мы узнаем что надо приостановить поиск ? Давайте заведем глобальную переменную Process. Как она станет False - пора останавливаться
Ниже приведена часть модуля с использованием описанных алгоритмов
Unit unit1;
......
var
....
process:boolean;
.....
procedure FileFind(path:string;resume:boolean);
const
save_ext='.rec';
mask='*.*';
type
TMysearchRec = record
Time: Integer; Size: Integer; Attr: Integer;
Name: string[250];
ExcludeAttr: Integer; FindHandle: THandle; FindData: TWin32FindData;
end;
TMyRec_Sea = record
Rec_Sea:TMySearchRec;
path:String[250]; found:integer; delfile:boolean;
end;
var
sr:TSearchRec;
RecFile:TFileStream;
buffer:tMyRec_Sea;
sp,save_file_name:string; found:integer; delfile:Boolean;
delfile:Boolean;
begin
if resume then
begin
save_file_name:=ChangeFileExt(ParamStr(0),save_ext);
if FileExists(save_file_name) then
begin
RecFile:=TFileStream.Create(save_file_name,fmOpenReadWrite);
fillchar(buffer,sizeof(buffer),#0);
RecFile.Seek(-1*sizeof(buffer),soFromEnd);
RecFile.Readbuffer(buffer,sizeof(buffer));
path:=buffer.path; sp:=path;
FindFirst(path+'\'+mask, FaAnyfile, sr);
delfile:=false; found:=buffer.found;
sr.Time:=buffer.rec_sea.Time;
sr.Size:=buffer.rec_sea.Size;
sr.Attr:=buffer.rec_sea.Attr;
sr.Name:=buffer.rec_sea.Name;
sr.ExcludeAttr:=buffer.rec_sea.ExcludeAttr;
sr.FindData:=buffer.rec_sea.FindData;
RecFile.Seek(-1*sizeof(buffer),soFromEnd);
recfile.Size:=RecFile.Position;
if RecFile.Size=0 then delfile:=true;
RecFile.Free;
if delfile then sysutils.DeleteFile(save_file_name);
end
else
begin
sp:=path; resume:=false;
if sp[length(sp)]='\' then sp:=copy(sp,1,length(sp)-1);
found:=FindFirst(sp + '\'+mask, FaAnyfile, sr);
end
end
else
begin
save_file_name:=ChangeFileExt(ParamStr(0),save_ext);
if fileExists(save_file_name) then sysutils.DeleteFile(save_file_name) ;
sp:=path;
if sp[length(sp)]='\' then sp:=copy(sp,1,length(sp)-1);
found:=FindFirst(sp + '\'+mask, FaAnyfile, sr);
end;
while (found = 0) and process do
begin
application.ProcessMessages;
if (sr.name <> '.') and (sr.name <> '..') then
begin
if (sr.attr and FaDirectory) = FaDirectory
then
begin
FileFind(sp+'\'+sr.name,resume);
end
else
begin
mainform.label1.caption:=('начат разбор '+sp+'\'+sr.name) ;
................
Application.ProcessMessages;
end;
end;
if process then found:=findnext(sr);
end;
if not process then
begin
save_file_name:=ChangeFileExt(ParamStr(0),save_ext);
if not FileExists(save_file_name) then
RecFile:=TFileStream.Create(save_file_name,fmCreate)
else RecFile:=TFileStream.Create(save_file_name,fmOpenReadWrite);
RecFile.Seek(0,soFromEnd);
buffer.rec_sea.Time :=sr.Time;
buffer.rec_sea.Size :=sr.Size ;
buffer.rec_sea.Attr :=sr.Attr ;
buffer.rec_sea.Name :=sr.Name ;
buffer.rec_sea.ExcludeAttr :=sr.ExcludeAttr ;
buffer.rec_sea.FindHandle :=sr.FindHandle ;
buffer.rec_sea.FindData :=sr.FindData ;
buffer.path:=sp; buffer.found:=found;
RecFile.Writebuffer(buffer,sizeof(buffer));
RecFile.Free;
end;
Application.ProcessMessages;
sysutils.FindClose(sr);
end;
| |
Данная статья не претендует на оригинальность и призвана помочь в разработке своих программ, если есть замечания, усовершенствования, пишите
Звягинцев Павел
[Древовидные структуры] [Файловая система] [Поиск файла]
Обсуждение материала [ 10-07-2009 12:46 ] 9 сообщений |