How do you design FIFO queue with variable data si

问题:

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;

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) ?

Thanks a lot

回答1:

Why not use:

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;

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!

回答2:

I suggest to use the built in TQueue and/or TObjectQueue located in Contnrs.pas. With the lack of Generics one can derive a special TQueue for each datatype used. That would give you type safety inside the rest of your program, while all the casting and pointer related stuff is bundled inside the queue class.

回答3:

I would use memory streams and a TObjectQueue (as Uwe suggested).

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;

回答4:

http://writeulearn.com/design-byte-queue/

FIFO Queues In Fixed Memory

Solution Requirements

Your solution should compile and be capable of managing a variable number of FIFO byte queues, each with variable length, in a small, fixed amount of memory.

You should provide implementations of the five functions within QueueManager.cpp.

!! DO NOT MODIFY QueueManager.h !!

You can define additioanl functions within QueueManger.cpp as necessary, but do not change the QueueManager interface.

Memory Restrictions

• No memory dynamically allocated during program execution (new, malloc, etc.).
• All queues must share a single storage space of MAX_DATA_SIZE for their data.
• You may statically allocate as much additional memory as you choose, but remember that efficiency is important and that any tradeoffs associated with allocating additional storage should be explained.
• You should statically allocate whatever memory you're going to use within the QueueManager namespace in QueueManager.cpp