如何设计具有可变数据大小的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（在流的情况下）？

非常感谢。

- user532231

---

对我来说有点不太明白——你怎么知道从队列中读取的数据类型是什么？例如，在你的示例中，你推入了一个（4个字符）ansistring和int——两者都是4字节，那么在读回时，你怎么知道它是int还是str或set或其他适合4字节的内容？哦，而且我会使用New(Listitem);而不是ListItem := AllocMem(SizeOf(TListItem));，在我看来更加“简洁”... - ain

@ain - 感谢你提供关于数据类型的 New(Listitem);，我忘记提到了我会知道输入和输出的数据类型。我将有几个队列，每个队列只处理一种数据类型。无论如何，这可能会保存到 TListItem 中。 - user532231

如果您为每种类型都有专用队列，那么我的建议是为您需要的每种类型编写一个类型安全的队列类。或者使用一些第三方库，例如DeHL。顺便提一下，请不要忘记切换到Dispose()以释放使用New分配的内存。 - ain

@ain - 我知道Dispose，我现在正在编辑问题。关于第三方库，我认为这种东西不是必要的。现在我终于将流传递到了这个队列，当然，在将其传递给Push之前，您必须设置流的SetSize，因此我还将创建一些数据大小获取器。 - user532231

我认为这段代码可能是高效的。我会接受Wim ten Brink的答案，因为他提到了链表，比TList本身更高效。无论如何，感谢所有对这个模糊问题的回答。 - user532231

Answer 1

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

- Uwe Raabe

---

我长期以来一直在考虑TQueue；它只是用FIFO功能包装了TList。我做了类似的东西，只不过我复制了推送的数据。这可能就是我的问题所在；这样做是否高效？ - user532231

Answer 2

我会使用内存流和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;

- Nat

---

它很高效，但TMemoryStream深层内部使用GetMem或ReallocMem，随后使用Move进行写入，再次使用Move进行读取。我希望它尽可能简单，所以我考虑使用一个大的内存流和记录列表来保存大小和位置，但我不知道如何在弹出后删除流的开头。 - user532231

你将推入队列多少项，它将在什么环境中使用？你是否在知道它会成为瓶颈之前优化代码？我经常发现，当你最终对代码进行分析时，最简单和最容易实现的答案通常与最有效率的答案相差不远。我也经常手动优化代码，当其他地方存在瓶颈完全淹没了我所做的任何优化时...例如，当我发送数据到网络或数据库时。 - Nat

如果您采用将所有内容放入一个流的方法，最终您将不得不将所有数据从流的末尾复制到开头，这样做速度并不快。我建议先测试实现简单的方法，并查看性能表现如何。如果它成为瓶颈，则编写更复杂的实现。 - Nat

@Warren - 是的，关于临界区你说得对；这是我在代码中删除的部分。至于TRawByteStringList，我认为拥有一个ANSI字符串列表就足够了，因为在Synapse的SendBuffer中，作者通过增加类型转换后的PAnsiChar指针来迭代缓冲区，并最终使用Winsock send函数发送数据。但即使Synapse以这种方式发送数据，我也不想将记录结构或流存储为字符串。 - user532231

我明白了。如果你想要查看并转储队列中的项目，那么将其放入原始字节字符串中，然后尝试确定它是否为记录或其他内容，会非常丑陋。 - Warren P

Answer 3

为什么不使用：

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解决方案仍非常有效。虽然不太优雅，但它足够好用。如果您想要更加优雅的解决方案，请围绕此构建一个类！

- Wim ten Brink

---

指向下一个数据条目的指针非常好。这将使我摆脱整个TList。 - user532231

虽然不是很面向对象。我早在1986年就在Turbo Pascal 3.0中使用了这些列表，当时OO还是个新鲜事物，无人问津。我建议将所有相关代码封装到一个新类中，使用push和pop方法以及Root/LastItem字段作为该类的属性。如果使用Delphi 2007，甚至可以在这个内部列表中使用嵌套记录，将其大部分逻辑隐藏起来。这样可以使其更加面向对象一些。 - Wim ten Brink

对我来说，它不太面向对象并不重要，正如你所说，它可以简单地包装到类中。我在这个问题上寻找的是效率，而你的答案在我看来是从Pascal的角度来看最低级别的。 - user532231

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;

- Cary Yu