How do you design FIFO queue with variable data size?

Question

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

Scampi

It doesn't quite make sense for me - how do you know the type of the data youre reading from the queue? Ie in your example you push (4 character) ansistring and int - both are 4 bytes, when reading back, how do you know is it int or str or set or whatever what fits into 4 bytes? Oh, and instead of ListItem := AllocMem(SizeOf(TListItem)); I would use New(Listitem); mutch "cleaner" IMO... – Colocynth

@Colocynth - thanks for the New(Listitem); about the data types, I forgot to mention that I will know, what data type comes in and what comes out. I will have several queues and each of them will handle only one data type. Anyway it might be saved to the TListItem. – Scampi

If you have dedicated queue for each type then my advise would be to write a typesafe queue class for each type you need. Or use some thirdparty lib, ie DeHL. BTW don't forget to switch to Dispose() to free the mem allocated with New. – Colocynth

@Colocynth - know about Dispose, I'm just editing the question right now. About 3rd party libraries I don't think it's necessary for this kind of stuff. Now I finally pass the stream to this queue, surely you have to SetSize of the stream before you pass it to the Push, so I will create also some data size getter. – Scampi

Well, I think the code might be efficient. I'll accept Wim ten Brink's answer because he mentioned linked lists, what is more efficient than TList itself. Thanks anyway for all answers to this ambiguous question. – Scampi

Answer 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!

Bracknell

Very good point with the pointer to the next data entry. This will allow me to get off the whole TList. – Scampi

It's not very object-oriented, though. I used these lists back in 1986 already, in Turbo Pascal 3.0 when OO was still something new, and unknown. I would advise that you wrap all related code within a new class, with a push and pop method and Root/LastItem as fields for this class. When using Delphi 2007, you can even use a nested record for this internal list, hiding much of it's logic to the outside. And to make it a bit more OO. – Bracknell

the fact that it's not so object-oriented is irrelevant for me and as you said it can be simply wrapped into the class. What I'm looking for at this question is the efficiency and your answer seems to me like the lowest level from the Pascal point of view. – Scampi

Answer 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.

Vambrace

I was thinking about TQueue for a long time; it's just wrapped TList with the FIFO functionality. I've made something similar except that I'm copying the pushed data. That's probably the point of my question; is that efficient ? – Scampi

Answer 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;

Strophanthin

It is efficient, but deeply inside TMemoryStream uses GetMem or ReallocMem with subsequent Move for writing and again Move for reading. I'd like to have it as simple as possible so I was considering also one big memory stream and the list of records where the size and the positions will be saved, but I don't know how would I delete the beginning of the stream after pop. – Scampi

How many items will you be pushing into the queue and in what environment will it be used? Are you optimizing code before you know it will be a bottle neck? I have often found that the simplest and easiest to implement answer is often not far off the most efficient when you end up profiling your code. I have also often hand optimized code when there is a bottleneck somewhere else that completely swamps any optimization I have done... For instance, when I was sending data over a network or into a database. – Strophanthin

It's for a network buffer. I'd like to store several data types and send them using Synapse's SendBuffer; the TMemory is the pointer to the data. My aim is to remove some data if necessary (using the Pop method) and some of them send through the socket (by a separate method). – Scampi

If you use the approach of putting it all into one stream, you will end up having to copy all the data from the end of the stream to the beginning, which wont be very quick at all. I would test the simple to implement method first and see what sort of performance you get. Then code a more complex implementation if it is a bottle neck. – Strophanthin

+1 for a competent implementation. However if the OP's result is going to Synapse's SendBuffer, then what you really probably want is a TRawByteStringList, and a critical section. Is there a rawbytestring list in delphi? Nope. Methinks we need one. :-) – Maure

@Warren - yeah, with critical sections you're right; that's what I've dropped from my code here. About TRawByteStringList I think it's enough to have an ANSI string list, because in Synapse's SendBuffer author iterates through the Buffer by increasing typecasted PAnsiChar pointer and finally send data using Winsock send function. But I won't to store e.g. record structures or streams as strings even if Synapse send it this way. – Scampi

@Warren - here I'm trying to build FIFO queue the most efficient way. And with the list (if it will be the TList, TQueue or just a pointer to the item which is to be popped) I can easily get the pointer to the current data and pass it to the SendBuffer; and the rest is on Synapse. The advantage of this queue for me is that I can also pop these data into the variable in the exact form as were saved if I know what data type they are. – Scampi

I see. It would be very ugly to put it into a rawbytestring and then try to figure out if it's a record or something else, if you wanted to look through and dump the items in the queue, after you've flattened it. – Maure

Answer 4

Eventually, I chose the TStringList for reaching this goal, it seems working pretty-well, but it is not designed for multi-threading.

  // 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;

Engineering