如何设计可变数据大小的 FIFO 队列？

Question

我正在研究具有可变数据大小的 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 队列（对于字符串、流、记录等数据类型）的大小从几个字节到大约 1MB（如果是流）的有效方法吗？

多谢

Answer 1

我建议使用位于 Contnrs.pas 中的内置 TQueue 和/或 TObjectQueue。由于缺乏泛型，我们可以为所使用的每种数据类型派生一个特殊的 TQueue。这将为您的程序的其余部分提供类型安全性，而所有与转换和指针相关的内容都捆绑在队列类中。

Answer 2

为什么不使用：

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 解决方案仍然非常有效。不太优雅，但是嘿，它工作得很好。如果您想要更优雅，请围绕这一切创建一个类！

Answer 3

我会使用内存流和 TObjectQueue （正如 Uwe 建议的那样）。

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;

Answer 4

最终，我选择了 TStringList 来实现这个目标，它看起来工作得很好，但它不是为多线程设计的。

  // First in first out/Last in first out (FIFO by default)
  TStringQueueType = (FIFO, LIFO);
  TStringQueue = class
    private
      QList: TStringList;
      QType: TStringQueueType;
    public
      constructor Create(); overload;
      procedure Push(str: String);
      function Pop(): String;
      procedure Clear();
  end;

  constructor TStringQueue.Create();
  begin
    inherited Create();
    QList := TStringList.Create();
    QType := FIFO;
  end;
  procedure TStringQueue.Push(str: String);
  begin
    QList.Add(str);
  end;
  function TStringQueue.Pop(): String;
  begin
    if QList.Count > 0 then
    begin
      case QType of
        FIFO:
        begin
          Result := QList.Strings[0];
          QList.Delete(0);
        end;
        LIFO:
        begin
          Result := QList.Strings[QList.Count - 1];
          QList.Delete(QList.Count - 1);
        end;
        else
          Result := '';
      end;
    end;
  end;
  procedure TStringQueue.Clear();
  begin
    QList.Clear();
  end;