Обхід дерева каталогів з перериванням і відновленням або “Куди ми йдемо завтра?”, Delphi, Програмування, статті

Паша Звягінцев

Програміст,
прокидаючись вранці з найсильнішого похмілля,
починає з тестування пам’яті …

Нещодавно займаючись цікавою задачкою з написання служби індексації, зіткнувся з цікавим питанням: “А як би нам пошук заморозити і продовжити після (через хвилину, завтра, через місяць)? “. Та звичайно можна сказати – що у тебе за машина така, ось у мене дерево каталогів обходить за 3 хвилини … Згоден, це не питання. Але коли потрібно не просто обходити, а ще й виконувати деякі дії з файлами, та якщо їх на диску 150 тис. і більше, та ще не завантажуючи процесор на 100%, то час може затягнутися до декількох діб, ось тоді – як бути?


Ось цієї теми я і вирішив присвятити статтю. Як виявилося, в Інтернеті інформації з цієї теми немає. Або це занадто просто, або нікому не потрібно. Як з’ясувалося – ні те ні інше.


Зі стандартною процедурою обходу дерева стикалися дуже багато


procedure FileFind(path:string); var sr: Tsearchrec ;/ / Описуємо структуру, яку / / Використовує для пошуку система found: integer; / / знайдено чи ні
begin
found:=FindFirst(path + ‘\*.*’, FaAnyfile, sr); {По команді FindFirst програма створює структуру наступного типу
TsearchRec = record Time: Integer; / / час створення Size: Integer; / / його розмір Attr: Integer ;/ / атрибути Name: TFileName / / = TString; власне ім’я файлу ExcludeAttr: Integer; знайдені атрибути FindHandle: THandle; / /! покажчик на структуру / / Пошуку, яку створює система, а не наша програма. / / Ось для чого обов’язково в кінці пошуку / / Вказувати FindClose – це вивільняє пам’ять FindData: TWin32FindData; / / власне ця структура
end;} 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 / / цей тип майже повністю переписується  / / З стандартного TSearchRec
TMysearchRec = record
Time: Integer;
Size: Integer;
Attr: Integer; Name: string [250] ;/ / ось тут оброблялося невірно при типі TString, як довжина?
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; / / Заганяємо в SEARCHREC все крім FINDHANDLE / / (Він створюється системою)
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; / / ось глобальна змінна / / Вона і управляє пошуком / / True – можна / / False – стоп із запам’ятовуванням стану
…..
procedure FileFind(path:string;resume:boolean); {Сканує диск (вірніше дерево каталогів) при виклику PATH – початковий каталог для обходу RESUME – якщо TRUE – то продовжувати збережений пошук (Тоді значення PATH ігнорується, крім випадку, коли не виявлений файл збереження пошуку) при установці глобальної змінної PROCESS в false зупиняється із запам’ятовуванням попереднього стану, увага – Рекурсія! }
const save_ext = ‘. rec’; / / в каталозі програми / / Створює SAVE файл з ім’ям / / Програми та зазначеним розширенням
mask=’*.*’;
type
TMysearchRec = record / / Довелося написати свій тип SEARCHREC / / З NAME фіксованої довжини
Time: Integer; Size: Integer; Attr: Integer; Name: string [250]; / / ось тут оброблялося / / Невірно при типі TString, / / Як довжина?
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; / / Заганяємо в SEARCHREC все крім FINDHANDLE (Він створюється системою)
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; / / Тут виправляється різниця між C: \ і / / C: \ DOCS – прибираємо / / Останній слеш
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;

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*