[SOLVED] Generic Linked List in Free Pascal lazarus / 21-General ---------------------------------------------------------------------- skepta · 2025-08-03 17:24 Hi, After some trial and error I finally implemented generic linked list in Pascal (objfpc). Please take a look at the attachment for the full code. Ideally I would like to make the TNode definition like so: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i   generic TNode<_T> = record    Value: _T;    Next: ^TNode<_T>;  end; Is there any way to achieve this? I prefer to use objfpc if possible. ---------------------------------------------------------------------- ASerge · 2025-08-03 17:48 There is the GLinkedList unit. ---------------------------------------------------------------------- Thaddy · 2025-08-04 05:35 In mode Delphi the code compiles fine (3.2.2 and 3.3.1) This usually means there should be an equivalent in mode objfpc but I can't find it. In most cases it is the other way around. Anyway, you can still use it like so: * one unit with the type declaration in {$mode delphi} Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i unit nodedecl;{$mode Delphi}interfaceuses  Classes, SysUtils;type  TNode<_T> = record    Value: _T;    Next: ^TNode<_T>;  end; implementationend.* Your prorgram and other units can now use it in {$mode objfpc} like so:Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program nodedeclaration;{$mode objfpc}uses nodedecl;type  TIntegerNode = specialize TNode;// orvar  node:specialize TNode;  // or node:TIntegerNode;beginend.But I really think there must be another way. Anyway, this works. ---------------------------------------------------------------------- dbannon · 2025-08-04 11:42 skepta, some time ago I bench marked a Linked List against TFPList, both using the same record (a fairly large one). That was a LL of my construction, not a generic on (they are very easy to write). To my surprise, the TFPList was faster, not by a huge margin but well beyond experimental error. I very much doubt a generic LL would be much faster, probably a touch slower. I had no reliable means to compare memory consumption but, as I said, my record was largish so swamped any difference. Not as sexy as using generics but easier to understand, write and debug.  Davo ---------------------------------------------------------------------- Warfley · 2025-08-04 15:48 There are two reasons why TFPList is so fast, the first one is cache locality. Chasing pointers is expensive. The second and more interesting one is geometric growth. Normally expanding an array requires allocating new memory and copying everything over. Meaning n insertions require O(n²) operations. When using geometric growth you always double the number of allocated elements. So let's say you have an empty list, you add the first element, it starts by allocating space for 4 elements. When adding the 5th element, the space will be doubled to 8 elements, then to 16, etc. Looking at the runtime, you only need to copy the elements when you do the expansion, in all other cases the runtime is just O(1). So most allocations are practically free. You only have the cost of copying n elements on expansion, which happens every log2(n) steps, which is expensive for that step. But looking at the average runtime over the whole lifetime (Armortized Analysis) you can do the math and end up at O(n). So looking at each insertion individually, you have a high likelyhood that it is basically free because the memory is already allocated (probability of n/log2(n)). If you have an algorithm doing a lot of insertions in sequence, the total runtime is just O(n). An additional thing is the warmup, if you have an algorithm that adds a bunch of stuff, removes some, and adds more, most likely it will run into a stable state, where the size of the list does not change anymore, because not enough elements are removed or no more are added. At this point the operations are basically in O(1). Compared to Linked Lists, where all operations are in O(n), geometricly growing lists have no disadvantage ---------------------------------------------------------------------- Thaddy · 2025-08-04 16:22 That said, generics of this type have as such no influence on speed if properly aligned. It is slightly more than a template, but is a replay. That would lead - theoretically - to the same speed as a manual declaration of a singly linked list as above. Because the generated code should be the same. ---------------------------------------------------------------------- dbannon · 2025-08-04 23:43 Quote from: Thaddy on August 04, 2025, 06:22:41 pmIt is slightly more than a template, but is a replay. But Thaddy, and I'd like you to be able to tell me I am wrong, that "replay" happens at run time, not at compile time. So, a small  delay at startup every time it runs. I know each one is insignificant but they add up. Coding a LL is a first year prac, if you want something richer (or faster) TFPList rocks ! (Maybe, just maybe, if there was more concentration on a release program instead of things like generics, we'd look just a bit more credible ?) Davo ---------------------------------------------------------------------- Thaddy · 2025-08-05 05:45 @dbannon Nope, replay occurs at compile time. It is not an rtti based feature if you thought so. I will add some assembler output later. The generated code is identical:Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program intvsgeneric;{$mode delphi}{$I-}type  TNode<_T> = record    Value: _T;    Next: ^TNode<_T>;  end;    TGenericIntegerNode = TNode; //compile time specialization as type    TPureIntegerNode = record    value:integer;    Next:PInteger;  end; var  a:TGenericIntegerNode;  b:TPureIntegerNode;    c:TNode // compile time spec as varbegin  a.value := 100;  b.value := 200;  c.value := 300;  writeln(a.value);  writeln(b.value);  writeln(c.value);end.Renders:Code: ASM  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i # [20] a.value := 100;        movl    $100,U_$P$INTVSGENERIC_$$_A(%rip).Ll3:# [21] b.value := 200;        movl    $200,U_$P$INTVSGENERIC_$$_B(%rip).Ll4:# [22] c.value := 300;        movl    $300,U_$P$INTVSGENERIC_$$_C(%rip).Ll5:# [23] writeln(a.value);        call    fpc_get_output        movq    %rax,%rbx        movslq  U_$P$INTVSGENERIC_$$_A(%rip),%r8        movq    %rax,%rdx        xorl    %ecx,%ecx        call    fpc_write_text_sint        movq    %rbx,%rcx        call    fpc_writeln_end.Ll6:# [24] writeln(b.value);        call    fpc_get_output        movq    %rax,%rbx        movslq  U_$P$INTVSGENERIC_$$_B(%rip),%r8        movq    %rax,%rdx        xorl    %ecx,%ecx        call    fpc_write_text_sint        movq    %rbx,%rcx        call    fpc_writeln_end.Ll7:# [25] writeln(c.value);        call    fpc_get_output        movq    %rax,%rbx        movslq  U_$P$INTVSGENERIC_$$_C(%rip),%r8        movq    %rax,%rdx        xorl    %ecx,%ecx        call    fpc_write_text_sint        movq    %rbx,%rcx        call    fpc_writeln_end.Ll8:# [26] end.        call  fpc_do_exit.seh_endproc.Lc1:.Lt1:.Ll9: .section .fpc.n_links,"aw"      .quad   DEBUGSTART_$P$INTVSGENERIC        .quad   DEBUGEND_$P$INTVSGENERIC# End asmlist al_procedures# Begin asmlist al_globals .section .bss,"aw"        .balign 8# [16] a:TGenericIntegerNode;        .globl U_$P$INTVSGENERIC_$$_AU_$P$INTVSGENERIC_$$_A:        .zero 16 .section .bss,"aw"        .balign 8# [17] b:TPureIntegerNode;        .globl U_$P$INTVSGENERIC_$$_BU_$P$INTVSGENERIC_$$_B:        .zero 16 .section .bss,"aw"        .balign 8# [18] c:TNode;        .globl U_$P$INTVSGENERIC_$$_CU_$P$INTVSGENERIC_$$_C:        .zero 16  And that confirms my statement that generics code can be just as fast as normal code and more often than not even generates the exact same code. Well written generics code has no speed penalty. This is a simple example, but only for brevity. More complex examples behave the same, though. E.g. a completed example of a generic singly linked list. Seems you misunderstood the way it works, hope this enlightens you. ---------------------------------------------------------------------- d2010 · 2025-08-05 15:21 Quote from: skepta on August 03, 2025, 07:24:15 pmHi, After some trial and error I finally implemented generic linked list in Pascal (objfpc). Please take a look at the attachment for the full code. My solution, I tested, but  iose   my sense , of too many variabiles in , after the public. You can replace i,j:word with string, shortstring, double, comp or Other. Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i Type _ct2word=record i,j:word;end;{implementarea stivelor pentru 2 word}   _ct_wordlist=^_ct_wordlist_noP;     _ct_wordlist_noP=record                  c:_ct2word;                    pred,urm:_ct_wordlist;                 end;     _cstack_2word=object {implemetarea stivei pentru C,elementul de baza este 2 words}   Function  find(c1:_ct2word):_ct_wordlist;   Procedure append(c:_ct2word);   Function  appendifnot(c:_ct2word):integer;   Procedure insert(mode:_tAi_insert_mode;c,c2:_ct2word);   function  delete(c:_ct2word):integer;   procedure view;{dela inceput la sfarsit}   procedure view2;{dela sfarsit la inceput}   Procedure init;   Procedure delete_all;   Function  update(c,c2:_ct2word):integer;   Public  ms1,ms2,mp,mq:_ct_wordlist;           p1,p2:word;           End; For testing I create a small Menu Begin clrscr; Code: [Select]  {$X+} Uses cstack,crt,strings; Var c:char;a1,a2:_ct2word;     ai:_cstack_2word; Function menu:char; Begin clrscr;       writeln('  ***  Test Stack/List 2Words: ***');       writeln('      1=insert before 2words');       writeln('      2=insert after 2words');       writeln('      3=append list');       writeln('      4=delete 2words');       writeln('      5=delete all 2words');       writeln('      6=view top-bottom list');       writeln('      7=view bottom-top list');       writeln('      8=update 2words');       writeln('      9=append if');       writeln('      0=exit');       Writeln;       Writeln;       Writeln('sizeof(ai)=',sizeof(ai));       Writeln('sizeof(p1)=',sizeof(a1));       repeat c:=readkey;until c in ['0'..'A'];       write(c);       menu:=c; End; Begin        ai.init;        repeat        menu;clrscr;        case c of        '1'..'2':Begin write('Insert ');                       if c='1' then write('before') else write('after');                       write(' words:');read(a1.i);read(a1.j);                       write(#13#10,'What insert?:');read(a2.i);read(a2.j);                       if c='1' then ai.insert(before,a1,a2)                                else ai.insert(after,a1,a2);                End;{1.2}       '3':Begin clrscr;                 Writeln('Input "0,0"=exit');                 repeat                    Write(#13#10,'Append:');read(a1.i);read(a1.j);                    if (a1.i<>0)and(a1.j<>0) then ai.append(a1);                 until (a1.i=0)and(a1.j=0) ;            End;{3}       '4':Begin write(#13#10,'Deleting words :');                 read(a1.i);read(a1.j);                 if ai.delete(a1)=-1 then writeln('Not Found ');            end;       '5':Begin writeln('Delete all..');ai.delete_all;end;       '6':Begin writeln('View top->bottom');ai.view;end;       '7':Begin writeln('View bottom->top');ai.view2;end;       '8':Begin writeln('Update words:');read(a1.i);write(',');read(a1.j);                 write('With words:');read(a2.i);write(',');read(a2.j);                 if ai.update(a1,a2)=-1 then begin writeln('Not Found ');end;           End;{8}       '9':Begin write(#13#10,'Append if not:');read(a1.i);write(',');read(a1.j);                 if ai.appendifnot(a1)=-1 then  writeln('-1 already Found ')                                           else writeln('0  append')           End;{8}       end;{case}      readkey;      until c='0'; {     dispose(a1);      dispose(a2);} End. Unit cstack; Interface Type _ct2word=record i,j:word;end;{implementarea stivelor pentru 2 word}      _ct_wordlist=^_ct_wordlist_noP;      _ct_wordlist_noP=record                     c:_ct2word;                     pred,urm:_ct_wordlist;                    end;     _cstack_2word=object {implemetarea stivei pentru C,elementul de baza este 2 words}    Function  find(c1:_ct2word):_ct_wordlist;    Procedure append(c:_ct2word);    Function  appendifnot(c:_ct2word):integer;    Procedure insert(mode:_tAi_insert_mode;c,c2:_ct2word);    function  delete(c:_ct2word):integer;    procedure view;{dela inceput la sfarsit}    procedure view2;{dela sfarsit la inceput}    Procedure init;    Procedure delete_all;    Function  update(c,c2:_ct2word):integer;    Public  ms1,ms2,mp,mq:_ct_wordlist;            p1,p2:word;            End; Implementation Function _cstack_2word.find(c1:_ct2word):_ct_wordlist; Var p:_ct_wordlist; Begin ms2^.c:=c1;       p:=ms1^.urm;       While not((p^.c.i=c1.i)and(p^.c.j=c1.j)) do       Begin  p:=p^.urm;      End;       find:=p; End; Procedure _cstack_2word.append(c:_ct2word); Begin mp:=ms2;       new(ms2);       mp^.urm:=ms2;mp^.c:=c;       ms2^.pred:=mp; End; {returneaza 0 ok             -1 already exist} Function _cstack_2word.appendifnot(c:_ct2word):integer; Begin if find(c)=ms2 then begin append(c);appendifnot:=0;end                       else appendifnot:=-1; End; Procedure _cstack_2word.insert(mode:_tAi_insert_mode;c,c2:_ct2word); Begin  case mode of    after:Begin mp:=find(c);                if mp=ms2 then append(c2)                          else begin new(mq);with mq^ do begin                                     c:=c2;urm:=mp^.urm;pred:=mp;end;                                     mp^.urm^.pred:=mq;                                     mp^.urm:=mq;                               end;{else}          End;{..after}   before:Begin mp:=find(c);                if mp=ms2 then append(c2)                          else begin new(mq);with mq^ do begin c:=c2;pred:=mp^.pred;urm:=mp;end;                                     mp^.pred^.urm:=mq;                                     mp^.pred:=mq;                              end;{else}          End;{..after}         end;{case} End; {returneaza -1 not found             0 found} Function _cstack_2word.delete(c:_ct2word):integer; Begin mp:=find(c);       if mp=ms2 then delete:=-1                 else begin mp^.pred^.urm:=mp^.urm;                            mp^.urm^.pred:=mp^.pred;                            dispose(mp);                      end;{else} {    dispose(c);} End; Procedure _cstack_2word.init; Begin new(ms2);new(ms1);ms1^.urm:=ms2;ms2^.pred:=ms1; End; procedure _cstack_2word.view; Begin mp:=ms1^.urm;       if mp=ms2 then writeln('Lista Vida')                 else begin repeat writeln(mp^.c.i,',',mp^.c.j);                                    mp:=mp^.urm;until mp=ms2;                      end; End; procedure _cstack_2word.view2; Begin mp:=ms2^.pred;       if mp=ms1 then writeln('Lista Vida')                 else begin repeat writeln(mp^.c.i,',',mp^.c.j);mp:=mp^.pred;until mp=ms1;                      end; End; Procedure _cstack_2word.delete_all; Begin mp:=ms1^.urm;       if mp<>ms2 then        Begin   repeat dispose(mp^.pred);{dispose(mp^.c);}                       mp:=mp^.urm;                until mp=ms2;                _cstack_2word.init;         End; End; Function  _cstack_2word.update(c,c2:_ct2word):integer; Begin mp:=find(c);       if mp=ms2 then update:=-1                 else begin mp^.c:=c2;update:=0;end; End; Begin End. ---------------------------------------------------------------------- marcov · 2025-08-05 15:25 Quote from: Warfley on August 04, 2025, 05:48:10 pmCompared to Linked Lists, where all operations are in O(n), geometricly growing lists have no disadvantage Make them ordered and retest :-) ---------------------------------------------------------------------- PascalDragon · 2025-08-05 19:32 Quote from: skepta on August 03, 2025, 07:24:15 pmIdeally I would like to make the TNode definition like so: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i   generic TNode<_T> = record    Value: _T;    Next: ^TNode<_T>;  end; Is there any way to achieve this? I prefer to use objfpc if possible. Just use specialize where it belongs? Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i type  generic TNode = record    Value: T;    Next: ^specialize TNode;  end; ---------------------------------------------------------------------- avk · 2025-08-06 04:49 Quote from: PascalDragon on August 05, 2025, 09:32:39 pmQuote from: skepta on August 03, 2025, 07:24:15 pmIdeally I would like to make the TNode definition like so: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i   generic TNode<_T> = record    Value: _T;    Next: ^TNode<_T>;  end; Is there any way to achieve this? I prefer to use objfpc if possible. Just use specialize where it belongs? Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i type  generic TNode = record    Value: T;    Next: ^specialize TNode;  end; But why not just Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i   generic TNode = record    Value: T;    Next: ^TNode;  end; ? ---------------------------------------------------------------------- Thaddy · 2025-08-06 05:00 With PascalDragon's code in objfpc mode I get an internal error. intvsgeneric.pas(6,28) Fatal: Internal error 2019112401 ---------------------------------------------------------------------- dbannon · 2025-08-06 05:11 Quote from: Thaddy on August 05, 2025, 07:45:57 amNope, replay occurs at compile time. It is not an rtti based feature if you thought so. I will add some assembler output later. The generated code is identical: OK Thaddy, I've told you in the past I have not used assembler since 2nd Year Uni (a long time ago) but even I can see what you show is identical. (Nothing in the "initialise" for lack of a better word, section ?). Anyway, I accept its possibly, even probably as good as hand coded. Mind you, hand coded is always as good as hand coded  Thanks for clarifying my misconceptions ! Davo ---------------------------------------------------------------------- bytebites · 2025-08-06 06:03 Quote from: Thaddy on August 06, 2025, 07:00:39 amWith PascalDragon's code in objfpc mode I get an internal error. intvsgeneric.pas(6,28) Fatal: Internal error 2019112401 It compiles with {$ModeSwitch advancedrecords} ---------------------------------------------------------------------- Thaddy · 2025-08-06 06:29 But it isn't an advanced record, so it is a bug..... Unless it is now specified that a simple generic record has also become an advanced record since 3.2.2. That is because this is a regression. But indeed, same code compiles in 3.2.2, but need the modeswitch added in 3.3.1. for it to compile. Bugs are bugs, regressions are regressions. ---------------------------------------------------------------------- skepta · 2025-08-07 16:50 Hi, thank you for all for your answers. I would like to highlight 2 answers: 1. From PascalDragon + bytebites The answer is great, but we need to add {$ModeSwitch advancedrecords}. For me this means I'm not good at Pascal yet. I actually got confused by the many dialect and many switches of Pascal. Other language seems more standardized. My initial goal is to only use fpc dialect, but nowadays I think I'm also interested objfpc mode. The added benefit of using objfpc is FPC itself is implemented in it, which means a lot to me since I want to learn FPC source code. 2. From avk The answer is great too. This makes me think again, why is ^TNode and Pointer (and ^specialize TNode<_T>) the same? Maybe I shouldn't overthink it and just use the original implementation (Pointer) instead. I will close this thread soon. ---------------------------------------------------------------------- PascalDragon · 2025-08-07 18:22 Quote from: avk on August 06, 2025, 06:49:16 amBut why not just Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i   generic TNode = record    Value: T;    Next: ^TNode;  end; ? That's possible as well, but specialize TNode is the more precise solution, especially once mode ObjFPC supports type overloading as well like mode Delphi does. Quote from: Thaddy on August 06, 2025, 07:00:39 amWith PascalDragon's code in objfpc mode I get an internal error. intvsgeneric.pas(6,28) Fatal: Internal error 2019112401 Huh?! Seems like a regression, cause in 3.2.2 it works. Please report a bug so it isn't forgotten. Quote from: skepta on August 07, 2025, 06:50:05 pm1. From PascalDragon + bytebites The answer is great, but we need to add {$ModeSwitch advancedrecords}. For me this means I'm not good at Pascal yet. I actually got confused by the many dialect and many switches of Pascal. Other language seems more standardized. My initial goal is to only use fpc dialect, but nowadays I think I'm also interested objfpc mode. The added benefit of using objfpc is FPC itself is implemented in it, which means a lot to me since I want to learn FPC source code. $ModeSwitch AdvancedRecords shouldn't be required and in fact in 3.2.2 it isn't, so as said above that's a bug that needs to be fixed (by us). And yes, there are many Pascal dialects, that's simply how it is, because the standardized Pascal dialects (ISO Pascal and ISO Extended Pascal never took really off 🤷‍♀️ ).