Recent

Author Topic: Smart linked list  (Read 3190 times)

soerensen3

  • Full Member
  • ***
  • Posts: 182
Smart linked list
« on: July 25, 2018, 12:31:29 pm »
I've been experimenting with management operators and I was trying to create a linked list with it.
This is what I prototyped so far:
(based on https://github.com/maciej-izak/PascalSmartPointers/blob/master/sources/SmartObj.pas)
Code: Pascal  [Select]
  1. {
  2.     This file is part of the Free Pascal run time library.
  3.     Copyright (c) 1999-2014 by Maciej Izak aka hnb (NewPascal project)
  4.     See the file COPYING.FPC, included in this distribution,
  5.     for details about the copyright.
  6.     This program is distributed in the hope that it will be useful,
  7.     but WITHOUT ANY WARRANTY; without even the implied warranty of
  8.     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  9.  **********************************************************************}
  10.  
  11.  unit SmartLinkedList;
  12.  
  13. {$MODE DELPHI}
  14.  
  15. interface
  16.  
  17. uses
  18.   SysUtils, Classes;
  19.  
  20. type
  21.   TSmartLinkedListItem<T: TObject> = record
  22.   public type
  23.     PSmartLinkedListItem = ^TSmartLinkedListItem < T >;
  24.  
  25.   public
  26.     // similar as overloading [] operators for property x[v: string]: integer read gx write sx; default;
  27.     Instance: T; //default; // default keyword for non property.
  28.     RefCount: PLongint;
  29.     Next: PSmartLinkedListItem;
  30.  
  31.     procedure SmartFinalize();
  32.  
  33.     class operator Initialize(var aRec: TSmartLinkedListItem<T>);
  34.     class operator Finalize(var aRec: TSmartLinkedListItem<T>);
  35.     class operator AddRef(var aRec: TSmartLinkedListItem<T>);
  36.     class operator Copy(constref aSource: TSmartLinkedListItem<T>; var aDest: TSmartLinkedListItem<T>);
  37.     function Append( AItem: T ): PSmartLinkedListItem;
  38.  
  39.     // implicit or explicit operator is used before "default" field
  40.     class operator Implicit(aObj: T): TSmartLinkedListItem<T>;
  41.     procedure Assign(const aValue: T);
  42.   end;
  43.  
  44. implementation
  45.  
  46. procedure TSmartLinkedListItem<T>.SmartFinalize();
  47. begin
  48.   WriteLn( 'Finalizing record.. ' );
  49.   if ( Assigned( Next )) then begin
  50.     Dispose( Next );
  51.     Next:= nil;
  52.   end;
  53.   if RefCount <> nil then
  54.     if InterLockedDecrement(RefCount^)=0 then begin
  55.       FreeMem(RefCount);
  56.       Instance.Free;
  57.     end;
  58. end;
  59.  
  60. class operator TSmartLinkedListItem<T>.Initialize(var aRec: TSmartLinkedListItem<T>);
  61. begin
  62.   WriteLn( 'Initializing record.. ' );
  63.   aRec.RefCount := nil;
  64. end;
  65.  
  66. class operator TSmartLinkedListItem<T>.Finalize(var aRec: TSmartLinkedListItem<T>);
  67. begin
  68.   aRec.SmartFinalize();
  69. end;
  70.  
  71. class operator TSmartLinkedListItem<T>.AddRef(var aRec: TSmartLinkedListItem<T>);
  72. begin
  73.   if aRec.RefCount <> nil then
  74.     InterLockedIncrement(aRec.RefCount^);
  75. end;
  76.  
  77. class operator TSmartLinkedListItem<T>.Copy(constref aSource: TSmartLinkedListItem<T>; var aDest: TSmartLinkedListItem<T>);
  78. begin
  79.   if aDest.RefCount <> nil then
  80.     aDest.SmartFinalize();
  81.   if aSource.RefCount <> nil then
  82.     InterLockedIncrement(aSource.RefCount^);
  83.   aDest.RefCount := aSource.RefCount;
  84.   aDest.Instance := aSource.Instance;
  85. end;
  86.  
  87. class operator TSmartLinkedListItem<T>.Implicit(aObj: T): TSmartLinkedListItem<T>;
  88. begin
  89.   Result.Assign(aObj);
  90. end;
  91.  
  92. procedure TSmartLinkedListItem<T>.Assign(const aValue: T);
  93. begin
  94.   if RefCount <> nil then
  95.     SmartFinalize();
  96.  
  97.   GetMem(RefCount, SizeOf(LongInt));
  98.   RefCount^ := 0;
  99.  
  100.   InterLockedIncrement(RefCount^);
  101.   Instance := aValue;
  102. end;
  103.  
  104. function TSmartLinkedListItem<T>.Append( AItem: T ): PSmartLinkedListItem;
  105. begin
  106.   New( Next );
  107.   Next^.Assign( AItem );
  108.   Result:= Next;
  109. end;
  110.  
  111.  
  112. end.

Each Instance of T can be a member of more than one linked list but is freed when it is not a member of any list anymore. It works as expected if I only have one list, but with a second list I get a SIGSEV with a call stack without any user functions so I presume the problem must be in the finalize code?
Edit: With stepping through the lines I found out that the code is called after "end.". It seems to call the Finalize function for an invalid record and it crashes when he tries to free the invalid Instance. I have no solution yet.

This is my demo code (You can switch between the two lists by activating/deactivating the define):
Code: Pascal  [Select]
  1. program project1;
  2.  
  3. {$MODE delphi}
  4. {.$DEFINE SECONDLIST}
  5. uses SmartLinkedList;
  6.  
  7. type
  8.  
  9.   { TTestClass }
  10.  
  11.   TTestClass = class
  12.   private
  13.     FIndex: Integer;
  14.   public
  15.     constructor Create( AIndex: Integer );
  16.     destructor Destroy; override;
  17.     property Index: Integer read FIndex write FIndex;
  18.   end;
  19.  
  20. var
  21.   TestList: TSmartLinkedListItem < TTestClass >;
  22.   TestList2: TSmartLinkedListItem < TTestClass >;
  23.   Ptr, Ptr2: TSmartLinkedListItem < TTestClass >.PSmartLinkedListItem;
  24.   i: Integer;
  25.  
  26. { TTestClass }
  27.  
  28. constructor TTestClass.Create(AIndex: Integer);
  29. begin
  30.   inherited Create;
  31.   FIndex:= AIndex;
  32.   WriteLn( 'TestClass', Index, ' create' );
  33. end;
  34.  
  35. destructor TTestClass.Destroy;
  36. begin
  37.   WriteLn( 'TestClass', Index, ' destroy' );
  38.   inherited Destroy;
  39. end;
  40.  
  41. begin
  42.   TestList:= TTestClass.Create( 0 );
  43.   Ptr:= @TestList;
  44.   i:= 1;
  45.   while i < 10 do begin
  46.     Ptr:= Ptr^.Append( TTestClass.Create( i ));
  47.     Inc( i );
  48.   end;
  49.   {$IFDEF SECONDLIST}
  50.   Ptr:= @TestList;
  51.   Ptr2:= @TestList2;
  52.   i:= 0;
  53.   while Assigned( Ptr ) do begin
  54.     if ( i mod 2 = 0 ) {even} then begin
  55.       Ptr2:= Ptr2^.Append( Ptr^.Instance );
  56.     end;
  57.     Ptr:= Ptr^.Next;
  58.     Inc( i );
  59.   end;
  60.   {$ENDIF}
  61.   Ptr:= nil;
  62.   Ptr2:= nil;
  63.   WriteLn( 'Now automatic cleanup!' );
  64. end.
  65.  
Any ideas?
« Last Edit: July 25, 2018, 01:29:34 pm by soerensen3 »
Lazarus 1.9 with FPC 3.0.4
Target: Manjaro Linux 64 Bit (4.9.68-1-MANJARO)

Thaddy

  • Hero Member
  • *****
  • Posts: 9436
Re: Smart linked list
« Reply #1 on: July 25, 2018, 01:31:31 pm »
RefCount should be a class var, not a normal field!
also related to equus asinus.

soerensen3

  • Full Member
  • ***
  • Posts: 182
Re: Smart linked list
« Reply #2 on: July 25, 2018, 02:13:12 pm »
RefCount should be a class var, not a normal field!
I didn't write this part of the code but I think it is a shared field between records with the same instance. If it was a class var it wouldn't work I guess. But this may be the problem! I called assign but I think it should be copy in this case in the append function. I think I have to do the copy differently. I try!
Lazarus 1.9 with FPC 3.0.4
Target: Manjaro Linux 64 Bit (4.9.68-1-MANJARO)

Thaddy

  • Hero Member
  • *****
  • Posts: 9436
Re: Smart linked list
« Reply #3 on: July 25, 2018, 02:34:02 pm »
RefCount should be a class var, not a normal field!
I didn't write this part of the code but I think it is a shared field between records with the same instance. If it was a class var it wouldn't work I guess. But this may be the problem! I called assign but I think it should be copy in this case in the append function. I think I have to do the copy differently. I try!
A refcount is a class var. Period.

Ok. Explanation: The refcount counts the number of instances of a class or advanced record. Therefor it needs to be a class var.
Also note Assign() actually makes a copy. An implicit := assigns just the pointer (deep copy vs shallow copy, if you like)

Assign() increases the refcount.

Hope this helps and is clear?
Otherwise refer to : https://en.wikipedia.org/wiki/Object_copying
« Last Edit: July 25, 2018, 03:21:27 pm by Thaddy »
also related to equus asinus.

taazz

  • Hero Member
  • *****
  • Posts: 5363
Re: Smart linked list
« Reply #4 on: July 25, 2018, 09:01:55 pm »
RefCount should be a class var, not a normal field!
I didn't write this part of the code but I think it is a shared field between records with the same instance. If it was a class var it wouldn't work I guess. But this may be the problem! I called assign but I think it should be copy in this case in the append function. I think I have to do the copy differently. I try!
A refcount is a class var. Period.

Ok. Explanation: The refcount counts the number of instances of a class or advanced record. Therefor it needs to be a class var.
Also note Assign() actually makes a copy. An implicit := assigns just the pointer (deep copy vs shallow copy, if you like)
erm no I don't think so. Given the fact that class vars are static and have the same value across instances that would be, well to put it mildly silly. refcount is a simple field of a class usually private so it can't be touched from anything else
Assign() increases the refcount.
it does? boy I'm missing something here. No, assign copies the contents of the class creating a copy in memory, it only touches refcount temporarily, to make sure that the source object is not going to get destroyed before it finishes copying the data. But it must decrease refcount before exiting regardless of the exit state.
Hope this helps and is clear?
Otherwise refer to : https://en.wikipedia.org/wiki/Object_copying
Is everything ok? those are very basic concepts you already know. Did I missed something crucial?
Good judgement is the result of experience … Experience is the result of bad judgement.

OS : Windows 7 64 bit
Laz: Lazarus 1.4.4 FPC 2.6.4 i386-win32-win32/win64

soerensen3

  • Full Member
  • ***
  • Posts: 182
Re: Smart linked list
« Reply #5 on: July 25, 2018, 09:23:56 pm »
But doesn't it depend on what you want to count. RefCount just says you count references of something. If you want to count the instances of a class you have to use a class var, but if you want to count the references for one class object you can't store it in the class itself, can you?

Please also have a look at TInterfacedObject. It does not use a class var for the reference counting because it counts the references of one instance of an object/interface.
from objectpash.inc:
Code: Pascal  [Select]
  1.        TInterfacedObject = class(TObject,IUnknown)
  2.        protected
  3.           frefcount : longint;
  4.           FDestroyCount : longint;
  5.           { implement methods of IUnknown }
  6.           function QueryInterface({$IFDEF FPC_HAS_CONSTREF}constref{$ELSE}const{$ENDIF} iid : tguid;out obj) : longint;{$IFNDEF WINDOWS}cdecl{$ELSE}stdcall{$ENDIF};
  7.           function _AddRef : longint;{$IFNDEF WINDOWS}cdecl{$ELSE}stdcall{$ENDIF};
  8.           function _Release : longint;{$IFNDEF WINDOWS}cdecl{$ELSE}stdcall{$ENDIF};
  9.         public
  10.           destructor destroy; override;
  11.           procedure AfterConstruction;override;
  12.           procedure BeforeDestruction;override;
  13.           class function NewInstance : TObject;override;
  14.           property RefCount : longint read frefcount;
  15.        end;        
In the case of the original SmartObj.pas my code is based on the refcount does not count the references to the record but the references of the record to one specific Instance of the object, stored in the Instance field. So I don't understand why you would use a class var for that. Also note that RefCount is not an integer field here but a Pointer to an integer shared by multiple records.

If I call assign from my append function it calls the assign function defined in the record, which calls getmem for RefCount that does not increase the refcount but allocate memory for a new reference counter. In this case it should however increase the reference counter if it is a copy. I yet have to find a way on how to do that properly. But as I said before most of the code is based on the code of Maciej Izak which implemented the reference counting that way so what I said is of course only my interpretation of the code.
Lazarus 1.9 with FPC 3.0.4
Target: Manjaro Linux 64 Bit (4.9.68-1-MANJARO)

Thaddy

  • Hero Member
  • *****
  • Posts: 9436
Re: Smart linked list
« Reply #6 on: July 26, 2018, 06:37:45 am »
My code and Maciej's are closely related. Only difference being that he uses the management operators and I use an interface.
If you feed your code into a debugger, you will see refcount^ is always one or zero. Maybe the debugger will convince you...
Reference counting over multiple instances can only be done with either a global or a class var. (pointer to int or int does not matter)
also related to equus asinus.

taazz

  • Hero Member
  • *****
  • Posts: 5363
Re: Smart linked list
« Reply #7 on: July 26, 2018, 08:47:17 am »
My code and Maciej's are closely related. Only difference being that he uses the management operators and I use an interface.
If you feed your code into a debugger, you will see refcount^ is always one or zero. Maybe the debugger will convince you...
Reference counting over multiple instances can only be done with either a global or a class var. (pointer to int or int does not matter)
have you seen the implementation of  TAggregatedObject ? it uses no global or class var yet all aggregated objects with the same container increase the container's refcount.
« Last Edit: July 26, 2018, 10:01:44 am by taazz »
Good judgement is the result of experience … Experience is the result of bad judgement.

OS : Windows 7 64 bit
Laz: Lazarus 1.4.4 FPC 2.6.4 i386-win32-win32/win64

Thaddy

  • Hero Member
  • *****
  • Posts: 9436
Re: Smart linked list
« Reply #8 on: July 26, 2018, 11:07:17 am »
have you seen the implementation of  TAggregatedObject ? it uses no global or class var yet all aggregated objects with the same container increase the container's refcount.
That's a half-truth: The controller requires an interface (IUnKnown) and therefor the aggregates are dependent on the refcount of the controller interface: simple delegation.
In fact that illustrates what I mean even better. Somewhere somehow there needs to a a refcount. A refcount is always a member of a managed type (class, record, string, not an instance field. (It can't be.)
Maciej used management operators for that, I used an interface for my smartpointer class. Similar to how aggregated objects are refcounted.

I have a feeling somebody is acting really stubborn.
also related to equus asinus.

taazz

  • Hero Member
  • *****
  • Posts: 5363
Re: Smart linked list
« Reply #9 on: July 26, 2018, 11:34:40 am »
have you seen the implementation of  TAggregatedObject ? it uses no global or class var yet all aggregated objects with the same container increase the container's refcount.
That's a half-truth: The controller requires an interface (IUnKnown) and therefor the aggregates are dependent on the refcount of the controller interface: simple delegation.
that is an implementation detail it could as easily be an abstract class instead of an interface. But you already know that don't you?
In fact that illustrates what I mean even better. Somewhere somehow there needs to a a refcount. A refcount is always a member of a managed type (class, record, string, not an instance field. (It can't be.)
which make no sense an instance field is a member of class or record which by your words is acceptable. Do you care to elaborate what you mean by instance field?
Maciej used management operators for that, I used an interface for my smartpointer class. Similar to how aggregated objects are refcounted.
that is implementation detail again it has nothing to do with the discution in question.
I have a feeling somebody is acting really stubborn.
I'll wait for your answer on the definition of "instance field" for a verdict on that.
Good judgement is the result of experience … Experience is the result of bad judgement.

OS : Windows 7 64 bit
Laz: Lazarus 1.4.4 FPC 2.6.4 i386-win32-win32/win64

PascalDragon

  • Hero Member
  • *****
  • Posts: 899
  • Compiler Developer
Re: Smart linked list
« Reply #10 on: July 26, 2018, 11:38:32 pm »
A refcount is a class var. Period.

Ok. Explanation: The refcount counts the number of instances of a class or advanced record. Therefor it needs to be a class var.

No, the reference count counts the number of references for a specific instance, thus a class variable as reference count is as wrong as it can be.

I've been experimenting with management operators and I was trying to create a linked list with it.

{snip}

Each Instance of T can be a member of more than one linked list but is freed when it is not a member of any list anymore. It works as expected if I only have one list, but with a second list I get a SIGSEV with a call stack without any user functions so I presume the problem must be in the finalize code?
Edit: With stepping through the lines I found out that the code is called after "end.". It seems to call the Finalize function for an invalid record and it crashes when he tries to free the invalid Instance. I have no solution yet.

{snip}

Any ideas?

With what compiler revision, platform and settings did you test? I just tested on x86_64-linux with most current trunk (r39511) and default settings of the compiler (using -n to avoid loading the fpc.cfg, cause I haven't installed my compiler) and got no errors at all.

Edit: ah, okay, on x86_64-win64 I can see the access violation. I'll try to find out what it is when I find the time.
« Last Edit: July 27, 2018, 07:34:02 am by PascalDragon »

soerensen3

  • Full Member
  • ***
  • Posts: 182
Re: Smart linked list
« Reply #11 on: July 27, 2018, 10:49:50 am »
My idea is that the reference count gets messed up because of the pointers. In theory it is possible to get two reference counts for 1 object I think. If one goes below 0 the instance is freed even if there is another reference count not below zero. I still have to understand which operators are called when.
In theory in my example I have to copy the record but first I have to initialize the pointer with New, that might be a problem? I have to think about it again when I have time in the afternoon.
Lazarus 1.9 with FPC 3.0.4
Target: Manjaro Linux 64 Bit (4.9.68-1-MANJARO)

SlightlyOutOfPhase

  • New Member
  • *
  • Posts: 33
Re: Smart linked list
« Reply #12 on: July 29, 2018, 02:52:36 am »
Linked lists are objectively slower than array-based lists in almost all cases, by the way. Obviously this seems like it's just a programming experiment, but in general there's really no reason to actually use them in real programs.

soerensen3

  • Full Member
  • ***
  • Posts: 182
Re: Smart linked list
« Reply #13 on: July 29, 2018, 12:56:27 pm »
This is a programming experiment. But I have I plan where I use them. One case where it is not slower is sorting. For an array you have to move all following records if you insert one. What I have in mind is this:

If you know the ggplot2 library from R this might be familiar to you.

In my 3D Engine I want to simplify drawing calls and have the ability to store them to be rendered repeatedly.
The prototype should look like this:

Code: Pascal  [Select]
  1. DrawCall:= P3DClear([ cfDepthBuffer, cfColorBuffer ], Red ) + P3DSetCamera( CamObj ) + P3DRenderScene( Scene ); // For creating the draw call
  2. Render( DrawCall ); // For rendering
  3.  
But it should also be possible to do this:
Code: Pascal  [Select]
  1. Render( P3DClear([ cfDepthBuffer, cfColorBuffer ], Red ) + P3DSetCamera( CamObj ) + P3DRenderScene( Scene )); // No memleaks
  2.  
Internally the function calls will return linked list with simple commands like SetMaterial, RenderTriangles or RenderLines.
for concatenating the render commands I would like to use a linked list for flexibility. Because then I can sort them easily and optimize them (For example by the distance to the camera). I know there are plenty other ways to implement it  but I wanted to try if it was possible this way and I was also curios about the management operators.
Lazarus 1.9 with FPC 3.0.4
Target: Manjaro Linux 64 Bit (4.9.68-1-MANJARO)