如何设计具有可变数据大小的 FIFO 队列? [英] How do you design FIFO queue with variable data size?

问题描述

我只是在处理具有可变数据大小的 FIFO 队列(简单的队列，即首先推送的内容，首先弹出)，但我不确定我的设计方式.我将存储在那里的数据类型将提前知道，假设对于此类的每个实例都是相同的.我正在考虑使用 TList 来存储具有以下定义的记录(@David - 它适用于 D2007，所以我没有 Generics.Collections 可用 :)

I'm just working on the FIFO queue (the simple one, just what's pushed first, pops at first) with the variable data size but I'm not sure with the way I'm designing it. The data types I will store there will be known in advance and let's say will be the same for each instance of this class. I was thinking about using TList where the records with the following definition will be stored (@David - it's for D2007, so I have no Generics.Collections available :)

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;

使用这样的实现(我在这里假装一切正常，所以没有使用异常处理)

with the implementation like this (I'm pretending here that everything works fine, so no exception handling is used)

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;

我的问题是:

这是如何制作大小从几个字节到大约 1MB(如果是流)的 FIFO 队列(对于字符串、流、记录等数据类型)的有效方法吗?

My question is:

Is this the efficient way how to make FIFO queue (for data types like strings, streams, records) with size from several bytes to about 1MB (in case of stream) ?

非常感谢

推荐答案

为什么不用:

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

You would also need a var Root: PListItem = nil; and allocate/deallocate items with New() and Dispose(). You might want to add a var LastItem: PListItem = nil; which contains the last item in your list so you don't have to walk through the whole list every time when you want to add an item.
While still primitive compared to modern "object-based solutions", a single linked-list is still very efficient for a FIFO solution. Not too elegant but hey, it works well enough. If you want more elegance, build a class around this all!

这篇关于如何设计具有可变数据大小的 FIFO 队列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！