Generic circular buffer library released

[Fr0sT.Brutal 900]

25 minutes ago, Stefan Glienke said:

I admit - it's not common but good luck storing something like this in your list then:

I have no experience with weak refs. Could you describe possible issues?

[Stefan Glienke 2002]

1 hour ago, Fr0sT.Brutal said:

I have no experience with weak refs. Could you describe possible issues?

Simple: pointers stored in the weakref table in System don't match those after using Move

[Anders Melander 1783]

3 hours ago, Stefan Glienke said:

Leave implementing generic collections to people experienced with it

...and how did these people get their experience?

[Stefan Glienke 2002]

57 minutes ago, Anders Melander said:

...and how did these people get their experience?

Keep in mind this was addressed at Uwes comment that he did not publish something similar because he did not make the effort to make it work not only for his but as a general purpose thing.

 

I cannot speak for others but for me it was reading a lof of collection library code (not only Delphi) - the Delphi specific things (can/cannot use System.Move and such) comes from general core runtime (RTL) knowledge.

And sometimes after years it dawns on you that naive usage of generics in large OOP architectures is not the greatest thing and you start refactoring stuff.

Edited August 24, 2020 by Stefan Glienke

[TurboMagic 92]

On 8/23/2020 at 4:31 PM, TurboMagic said:

Uwe Raabe is already working on this 😉

But others than MVPs and the usual folks could contribiute as well...

Often such easy things or even parts of those would help the community!

Since I didn't hear from him with a ull request or any other "delivery" yet I guess he got stuck translating the comments...

[TurboMagic 92]

9 hours ago, Anders Melander said:

I can't see why using Move would be a problem as long as it just moves entries within the buffer array (which it does as far as I can tell).

However there does seem to be a problem with not clearing empty slots in the array. E.g. by assigning Default(T) to them.

Why would those have to be cleared? One shoukdn't be able to read those out and I don't remember but if the buffer has to free any instances contained in it when the buffer is freed it will only free the instances still in the buffer.

[TurboMagic 92]

9 hours ago, Stefan Glienke said:

No, yes

 

For managed types you can System.Move them in the internal array - however it also does it when peeking x items into the result array.

For types containing weak reference System.Move does not work even for the internal array.

Ok, I think I see what you're after. In case of the peek one would have to use the assignment operator then (if the type is a managed one) in order to increase the reference counter. Am I right? But how to find out whether the type is managed?

[Anders Melander 1783]

2 minutes ago, TurboMagic said:

Why would those have to be cleared?

Because otherwise the buffer will still hold a reference to the T instance. For any managed type this will be a problem.

 

For example what happens if T is an interface?

 

Maybe some unit testing is in order...

[TurboMagic 92]

4 minutes ago, Anders Melander said:

Because otherwise the buffer will still hold a reference to the T instance. For any managed type this will be a problem.

 

For example what happens if T is an interface?

 

Maybe some unit testing is in order...

Thanks! That could be fixed at the place where items get taken out of the list. I guess one would have to make a distinction of cases via

IsManagedType(T) so one can keep using Move for non manages types and assignment operator for managed ones. Would that be correct?

 

[TurboMagic 92]

19 minutes ago, Anders Melander said:

Because otherwise the buffer will still hold a reference to the T instance. For any managed type this will be a problem.

 

For example what happens if T is an interface?

 

Maybe some unit testing is in order...

Yes, unit tests for managed types would still have to be created. And yes one would have to do some for strings and interfaces as well as tey're of course managed as well.

I contributed this to the public because it will not help the community if one always consumes only without giving. That also means, if there's interest in this library others should contribute fixes etc. as well. My main open source commitment currently is DEC (Delphi Encryption Compendium) and that's enough work.

Edited August 24, 2020 by TurboMagic

[Anders Melander 1783]

2 minutes ago, TurboMagic said:

Would that be correct?

Move isn't the problem in this particular case. The problem is that once you logically remove an entry from the array then you need to finalize that entry in the array to clear the reference. You can do that by assigning Default(T) to the entry.

[TurboMagic 92]

1 minute ago, Anders Melander said:

Move isn't the problem in this particular case. The problem is that once you logically remove an entry from the array then you need to finalize that entry in the array to clear the reference. You can do that by assigning Default(T) to the entry.

Ok, thanks for this hint.

[Uwe Raabe 2057]

1 hour ago, TurboMagic said:

Since I didn't hear from him with a ull request or any other "delivery" yet I guess he got stuck translating the comments...

Some things just need their time...

[TurboMagic 92]

Ok, besides accepting Uwe's pull request I did some changes to the Peek method in order to make it more compatible with managed types. Feel free to look at it and critisise where necessary, I admit that I didn't test it yet (need to create unit tests) but it's getting late enough already. I can only learn from it.

And if somebody wants to contribute: feel free. As far as I understood Stefan, one could get rid of the 2nd class implemented for managed types altogether by using IsManaged and calling the appropriate code to release the items where necessary.

[TurboMagic 92]

Access violation, but I don't know why.

Ok, I started to write some further unit tests now as a start to fix the issues this implementation has in order to learn some things.

I copied the integer unit tests which run fine and reworked those into string ones. so <T> is string now.

 

One of the tests calls this method:

 

function TRingbuffer<T>.Peek(Index: UInt32): T;
var
  reminder : UInt32;
begin
  if (Index < Count) then
  begin
    // Puffer läuft derzeit nicht über seine obere Grenze hinaus
    if ((FStart+Index) < Size) then
      result := FItems[FStart+Index]
    else
    begin
      // um wieviel geht es über die obere Grenze hinaus?
      reminder := (FStart+Index)-Size;
      result   := FItems[reminder];
    end;
  end
  else
    raise EArgumentOutOfRangeException.Create('Invalid Index: '+Index.ToString+
                                              ' Max. Index: '+Count.ToString);
end;

FItems at that point contains 5 items, FStart is 1 and Index is 1 as well.

It crashes with EInvalidPointer at this line:

 

result := FItems[FStart+Index]

 

When debugging the asm I see some call to freemem.

I would have expected that Peek would simply return a string with the contents of FItems[FStart+Index] and that it would increase the
reference counter of the string stored in FItems[FStart+Index].

 

This Peek method is called in a loop over the complete ringbuffer to check if its contents is the expected one.

For Index = 0 it doesn't crash.

 

What is wrong on my assumption?

And the other question would be: should peek increase reference counter of reference counted types (string, interface...) or return
a copy which is not reference counted and thus completely detached from the buffer inside the ring buffer class?

And if "detached" should be preferred, how to do the copying properly?

[Stefan Glienke 2002]

Defect is somewhere else and you messed up the string reference counting, if the error occurs on not the first call to Peek then obviously Result contains a prior string reference which the UStrAsg call that is generated for the assignment clears.

 

Did you fix procedure Add(Items:TRingbufferArray); already? Because that must not use Move for managed types

Edited September 4, 2020 by Stefan Glienke

[TurboMagic 92]

I fixed the Add(Items:TRingbufferArray) now, it might need further test coverage for managed types, but that at least fixed some of the failed string test cases now.

Peek no longer crashes and while working on that I had see that Peek had already a value in Result at the beginning of the method. Trying to set that to Default(T)

there crashed immediately. So fixing add was the right thing.

 

One thing which still puzzles me and maybe is not even possible:

I can have such a generic ringbuffer class which works for non managed types and for reference counted types at the same time.

But I don't seem to be able to make it work with objects and OwnsObject semantics, as I cannot call free. I can only call free if I introduce a class constraint.

Is this assumption correct and my initial attempt with a class for objects inheriting from the first one is the right one?

 

I already tried to find out how TObjectList<T> from Generics.Collections does it, but I failed to find the free of the items in it...

[Stefan Glienke 2002]

if GetTypeKind(T) = tkClass then
  PObject(@item)^.Free;

RTL still uses DisposeOf (which you also need to if you want to support ARC before 10.4) - look into TObjectList<T>.Notify

Edited September 5, 2020 by Stefan Glienke

[TurboMagic 92]

Small status update: it looks I have fixed all non object related issues. At least the unit tests for those do run and the same unit tests as implemented for unmanaged types have ben implemented for strings as well and they do run.

What's left now is the OwnsObjects semantics and tests for interfaces and regular classes. That's the state of the development branch.

[TurboMagic 92]

I added unit tests for usage with objects now, testing the OwnsObjects semantics. After fixing a bug in destructor, where I tried to free one object too much (which even got the IDE into trouble)
it seems to work as it should.

 

But: I have a memory leak problem with two of the unit tests which I don't know how to fix.

These are unit tests testing exceptions and the program flow doesn't seem to get to the point in the test method after the exception has been raised.

So the code I put there for cleaning up seems not to be run.

 

The circular buffer doesn't free the objects in such an exception case either.

I thought that the user wouldn't expect me to do this. Or would a user expect me freeing

objects the user tried to add but couldn't because the buffer is full and my implementation has no "overwrite the oldest items in such a case" semantics?

(if I would be thinking about adding this I'd make it configurable)

[pmcgee 10]

On 8/24/2020 at 8:08 PM, Stefan Glienke said:

Leave implementing generic collections to people experienced with it (which I in no way claim to have monopoly on)

To be fair, there's a Catch-22 in that idea.   ie don't implement Generics until you have experience implementing Generics.

 

(and the same would apply for trying to use a c++ like move feature)

 

If someone publishes open source ... not part of a (reasonably big) commercial product like RAD ... and it is useful to maybe 80% of people, then sure it's valuable to point out edge cases - but it doesn't mean it should be discouraged.  We need *more* Delphi out there.  And more understanding of these elements that weren't even part of Delphi in say 2005.

[TurboMagic 92]

So have you looked at my newest commit? Did you find any failure in it? I'm asking because I'm tempted to "do a release"...

[TurboMagic 92]

Today I fixed a few bugs regarding use for storing objects in the buffer in the Remove and Delete methods

and I fixed all memory leaks in the unit tests.

 

The GitHub repository is up to date. Does anybody spot any bugs I have missed?

Or is the source now "ok" so that the public should be "safe" when using it?