Как вы проектируете очередь FIFO с переменным размером данных? - PullRequest
Новая
       27

Как вы проектируете очередь FIFO с переменным размером данных?

3 голосов
/ 01 августа 2011

Я просто работаю над очередью FIFO (простой, только то, что выдвигается первым, появляется сначала) с переменным размером данных, но я не уверен в том, как я его проектирую.Типы данных, которые я буду там хранить, будут известны заранее, и скажем, они будут одинаковыми для каждого экземпляра этого класса.Я думал об использовании TList, где будут храниться записи со следующим определением (@David - это для D2007, поэтому у меня нет Generics.Collections доступны:) 

type
  PListItem = ^TListItem;
  TListItem = record
    Size: Integer; // size of the data pointed by the following member
    Data: Pointer; // pointer to the target data reserved in memory
  end;

среализация, подобная этой (я делаю вид, что все работает нормально, поэтому обработка исключений не используется) 

type
  TListQueue = class
private
  FList: TList;
public
  constructor Create;
  destructor Destroy; override;
  procedure Clear;
  procedure Push(const Value; const Size: Integer);
  procedure Pop(var Value; var Size: Integer);
end;

constructor TListQueue.Create;
begin
  inherited;
  FList := TList.Create;
end;

destructor TListQueue.Destroy;
begin
  Clear;
  FList.Free;
  inherited;
end;

procedure TListQueue.Push(const Value; const Size: Integer);
var ListItem: PListItem;
begin
  New(ListItem);
  ListItem.Size := Size;
  ListItem.Data := AllocMem(Size);
  Move(Value, ListItem.Data^, Size);
  FList.Add(ListItem);
end;

procedure TListQueue.Pop(var Value; var Size: Integer);
var ListItem: PListItem;
begin
  if FList.Count > 0 then
  begin
    ListItem := FList.Items[0];
    Size := ListItem^.Size;
    Move(ListItem.Data^, Value, ListItem.Size);
    FreeMem(ListItem.Data, ListItem.Size);
    Dispose(ListItem);
    FList.Delete(0);
  end;
end;

procedure TListQueue.Clear;
var I: Integer;
    ListItem: PListItem;
begin
  for I := 0 to FList.Count - 1 do
  begin
    ListItem := FList.Items[I];
    FreeMem(ListItem.Data, ListItem.Size);
    Dispose(ListItem);
  end;
  FList.Clear;
end;

Мой вопрос:

Это эффективный способ сделать FIFOочередь (для типов данных, таких как строки, потоки, записи) размером от нескольких байтов до 1 МБ (в случае потока)?

Большое спасибо

Ответы [ 3 ]

4 голосов
/ 01 августа 2011

Я предлагаю использовать встроенные TQueue и / или TObjectQueue, расположенные в Contnrs.pas. С отсутствием обобщенных типов можно получить особый TQueue для каждого используемого типа данных. Это обеспечит безопасность типов внутри остальной части вашей программы, в то время как все, что связано с приведением типов и указателями, связано внутри класса очереди.

3 голосов
/ 01 августа 2011

Почему бы не использовать: 

type
  PListItem = ^TListItem;
  TListItem = record
    Size: Integer; // size of the data pointed by the following member
    Data: Pointer; // pointer to the target data reserved in memory
    Next: PListItem; // pointer to the next data entry, or nil for the last one.
  end;

Вам также понадобится var Root: PListItem = nil; и выделение / освобождение предметов с помощью New () и Dispose (). Возможно, вы захотите добавить var LastItem: PListItem = nil;, который содержит последний элемент в вашем списке, чтобы вам не приходилось просматривать весь список каждый раз, когда вы хотите добавить элемент.
Несмотря на примитивность по сравнению с современными «объектно-ориентированными решениями», единый связанный список все еще очень эффективен для решения FIFO. Не слишком элегантно, но эй, это работает достаточно хорошо. Если вы хотите больше элегантности, создайте класс вокруг этого всего!

3 голосов
/ 01 августа 2011

Я бы использовал потоки памяти и TObjectQueue (как предложил Уве). 

type
  TListQueue = class
  private
    FList: TObjectQueue;
  public
    constructor Create;
    destructor Destroy; override;
    procedure Push(const Value; const Size: Integer);
    procedure Pop(var Value; var Size: Integer);
  end;

implementation

constructor TListQueue.Create;
begin
  inherited;
  FList := TObjectQueue.Create;
end;

destructor TListQueue.Destroy;
begin
  while FList.Count > 0 do
    TMemoryStream(FList.Pop).Free;
  FreeAndNil(FList);
  inherited;
end;

procedure TListQueue.Push(const Value; const Size: Integer);
var
  LStream: TMemoryStream;
begin
  LStream := TMemoryStream.Create;
  LStream.Write(Value, Size);
  FList.Push(LStream);
end;

procedure TListQueue.Pop(var Value; var Size: Integer);
var
  LStream: TMemoryStream;
begin
  if FList.Count > 0 then
  begin
    LStream := TMemoryStream(FList.Pop);
    Size := LStream.Size;
    LStream.Position := 0;
    LStream.Read(Value, Size);
    LStream.Free;
  end;
end;
...