понедельник, 1 февраля 2010 г.

Использование волокон для упрощения enumerator-ов, часть 1: когда для enumerator-а жизнь проще

Это перевод Using fibers to simplify enumerators, part 1: When life is easier for the enumerator. Автор: Реймонд Чен.

Модель перечисления COM (перечисления объектов) сделана так, чтобы сделать проще жизнь потребителя (вызывающего) и сложнее - жизнь поставщика (вызываемого). Перечисляемый объект (поставщик) должен быть выполнен как автомат с состояниями (state machine), что может быть весьма обременительным для сложных перечислений - например, пробежке по дереву или составного (composite) перечисления.

С другой стороны, модель с обратным вызовом для поставщика (используемая в большинстве функций Win32) склоняется к простой жизни для вызываемого и сложной для потребителя. В этом случае, именно потребителю нужно поддерживать состояния, что только усугубляется, если потребитель делает в своей функции обратного вызова что-то сложное (даже если и нет: вам всё равно нужно создать контекстную структуру, чтобы передавать её от вызывающего через перечислитель в эту функцию обратного вызова).

Например, предположим, что мы хотим написать код, который проходит по структуре каталога, позволяя вызывающему указать, что делать в каждой точке. Давайте сперва спроектируем код с использованием парадигмы обратного вызова:

type
TEnumResult = (
erContinue, // продолжить перечисление
// (если каталог: войти в него)
erSkip, // пропустить этот файл/каталог
erStop // остановить перечисление
);

TEnumOperation = (
eoFile, // нашли файл
eoDir, // нашли каталог
eoLeaveDir // выходим из каталога
);

type
TFileEnumCallback = function(const AOperation: TEnumOperation; const ADir,
APath: String; const ASearchRec: TSearchRec; const AContext: Pointer): TEnumResult;

function EnumDirectoryTree(const ADir: String; const ACallback: TFileEnumCallback;
const AContext: Pointer): TEnumResult;

Здесь дизайн таков: вызывающий вызывает EnumDirectoryTree и передаёт ей функцию обратного вызова, которая уведомляет о каждом найденном файле и каталоге и определяет, что делать дальше.

Такой подход делает жизнь намного проще для реализации EnumDirectoryTree:

function EnumDirectoryTree(const ADir: String; const ACallback: TFileEnumCallback;
const AContext: Pointer): TEnumResult;
var
Path, Name: String;
SR: TSearchRec;
Operation: TEnumOperation;
begin
Result := erContinue;
Path := IncludeTrailingPathDelimiter(ADir);
if FindFirst(Path + '*.*', faAnyFile, SR) = 0 then
try
repeat
if (SR.Name <> '.') and
(SR.Name <> '..') then
begin
if (SR.Attr and faDirectory) <> 0 then
Operation := eoDir
else
Operation := eoFile;
Name := Path + SR.Name;
Result := ACallback(Operation, ADir, Name, SR, AContext);
if Result = erContinue then
begin
if Operation = eoDir then
begin
Result := EnumDirectoryTree(Name + PathDelim, ACallback, AContext);
if Result = erContinue then
Result := ACallback(eoLeaveDir, ADir, Name, SR, AContext);
end;
end
else
if Result = erSkip then
Result := erContinue;
end;
until (FindNext(SR) <> 0) or (Result = erStop);
finally
FindClose(SR);
end;
end;

Примечание: я даже не пытался как-то оптимизировать эту функцию, поскольку смысл статьи не в этом. Например, она очень сильно ест стековую память (что может быть проблемой при перечислении деревьев каталогов с глубокой вложенностью). Также я не забочусь о точках соединения, которые могут вызвать бесконечную рекурсию.

Ну, написать это было не сложно. Но только потому, что мы сделали тяжелее жизнь потребителя (вызывающего). Потребитель будет вынужден поддерживать своё состояние между каждым вызовом callback-а (функции обратного вызова). Например, предположим, что вам нужно построить список каталогов вместе с их размером(с учётом подкаталогов и без).

type
TEnumState = class
public
constructor Create;
destructor Destroy; override;
function Callback(const AOperation: TEnumOperation; const ADir,
APath: String; const ASearchRec: TSearchRec): TEnumResult;
procedure FinishDir(const ADir: String);
private
type
PDirectory = ^TDirectory;
TDirectory = record
Parent: PDirectory;
SizeSelf: UInt64;
SizeAll: UInt64;
end;
var
FDirCur: PDirectory;
function Push: PDirectory;
procedure Pop;
procedure Cleanup;
end;

constructor TEnumState.Create;
begin
inherited;
New(FDirCur);
FillChar(FDirCur^, SizeOf(TDirectory), 0);
end;

destructor TEnumState.Destroy;
begin
Cleanup;
inherited;
end;

function TEnumState.Push: PDirectory;
begin
New(Result);
FillChar(Result^, SizeOf(TDirectory), 0);
Result.Parent := FDirCur;
FDirCur := Result;
end;

procedure TEnumState.Pop;
var
Dir: PDirectory;
begin
Dir := FDirCur.Parent;
Dispose(FDirCur);
FDirCur := Dir;
end;

procedure TEnumState.Cleanup;
begin
while Assigned(FDirCur) do
Pop;
end;

procedure TEnumState.FinishDir(const ADir: String);
begin
FDirCur^.SizeAll := FDirCur^.SizeAll + FDirCur^.SizeSelf;
Form9.Memo1.Lines.Add(Format('Size of %s is %u (%u)', [ADir,
FDirCur^.SizeSelf, FDirCur^.SizeAll]));
end;

function TEnumState.Callback(const AOperation: TEnumOperation; const ADir,
APath: String; const ASearchRec: TSearchRec): TEnumResult;
begin
if not Assigned(FDirCur) then
Exit(erStop);

case AOperation of
eoFile:
begin
FDirCur^.SizeSelf := FDirCur^.SizeSelf + ASearchRec.Size;
Result := erContinue;
end;
eoDir:
begin
Push;
Result := erContinue;
end;
eoLeaveDir:
begin
FinishDir(APath);

// Выталкиваем размер в родителя
FDirCur^.Parent^.SizeAll := FDirCur^.Parent^.SizeAll +
FDirCur^.SizeAll;
Pop;
Result := erContinue;
end
else
Result := erContinue;
end;
end;

function EnumState_Callback(const AOperation: TEnumOperation; const ADir,
APath: String; const ASearchRec: TSearchRec; const AContext: Pointer):
TEnumResult;
begin
Result := TEnumState(AContext).Callback(AOperation, ADir, APath, ASearchRec);
end;

procedure TForm1.Button1Click(Sender: TObject);
var
EnumState: TEnumState;
begin
EnumState := TEnumState.Create;
try
Memo1.Lines.BeginUpdate;
try
if EnumDirectoryTree('.', EnumState_Callback, Pointer(EnumState)) = erContinue then
EnumState.FinishDir('.');
finally
Memo1.Lines.EndUpdate;
end;
finally
FreeAndNil(EnumState);
end;
end;

Мда, не слабо нам тут пришлось печатать. Что еще хуже - вся структура программы скрыта на фоне явного управления состояниями. Я уверен, что тяжело с первого раза сказать, что делает программа, взглянув на этот код. Вместо этого, вам нужно глазеть на класс TEnumState и вкапываться в его код, пытаясь понять, что он делает.

Завтра мы посмотрим, как выглядел бы мир, если бы акценты функции EnumDirectoryTree были смещены в противоположном направлении.

Комментариев нет:

Отправить комментарий

Можно использовать некоторые HTML-теги, например:

<b>Жирный</b>
<i>Курсив</i>
<a href="http://www.example.com/">Ссылка</a>

Вам необязательно регистрироваться для комментирования - для этого просто выберите из списка "Анонимный" (для анонимного комментария) или "Имя/URL" (для указания вашего имени и ссылки на сайт). Все прочие варианты потребуют от вас входа в вашу учётку.

Пожалуйста, по возможности используйте "Имя/URL" вместо "Анонимный". URL можно просто не указывать.

Ваше сообщение может быть помечено как спам спам-фильтром - не волнуйтесь, оно появится после проверки администратором.

Примечание. Отправлять комментарии могут только участники этого блога.