Recent

Author Topic: [SOLVED] Linux Kernel Linked List  (Read 636 times)

julkas

  • Full Member
  • ***
  • Posts: 150
  • KISS principle
[SOLVED] Linux Kernel Linked List
« on: May 18, 2019, 03:03:27 pm »
How implement intrusive data structures, e.g - Linux kernel linked list in Pascal?

Thanks.
« Last Edit: May 22, 2019, 08:02:10 pm by julkas »
Lazarus 2.0.0 / FPC 3.0.4
----------------------------
procedure mulu64(a, b: QWORD; out clo, chi: QWORD); assembler;
asm
  mov rax, a
  mov rdx, b
  mul rdx
  mov [clo], rax
  mov [chi], rdx
end;

Martin_fr

  • Administrator
  • Hero Member
  • *
  • Posts: 5454
    • wiki
Re: [WANTED] Intrusive data structures
« Reply #1 on: May 18, 2019, 06:01:38 pm »
Intrusive => Recursive ?

Code: Pascal  [Select]
  1. type
  2.   PMyLinkedList = ^TMyLinkedList;  // Forward declaration pointer to the record
  3.   TMyLinkedList = record
  4.     Prev, Next: PMyLinkedList;
  5.     YourData: TYourType;
  6.   end;

You need to allocate nodes with New(), and free them later.

You can use classes (then you need no pointer). But if you want to call some c based functions, then records, or packed records are what you need.

julkas

  • Full Member
  • ***
  • Posts: 150
  • KISS principle
Re: [WANTED] Intrusive data structures
« Reply #2 on: May 18, 2019, 08:21:39 pm »
Lazarus 2.0.0 / FPC 3.0.4
----------------------------
procedure mulu64(a, b: QWORD; out clo, chi: QWORD); assembler;
asm
  mov rax, a
  mov rdx, b
  mul rdx
  mov [clo], rax
  mov [chi], rdx
end;

Martin_fr

  • Administrator
  • Hero Member
  • *
  • Posts: 5454
    • wiki
Re: [WANTED] Intrusive data structures
« Reply #3 on: May 19, 2019, 01:49:31 pm »
The link does not load from where I live. Google cache works....

You can put fields or references (pointers) into that record (the record I gave you is a blueprint for the header)

You can nest records, too.

Code: Pascal  [Select]
  1.     type
  2.       PMyLinkedHead = ^TMyLinkedHead;  // Forward declaration pointer to the record
  3.       TMyLinkedHead = record
  4.         Prev, Next: PMyLinkedHead;
  5.       end;
  6.  
  7.   TData = record
  8.     // ...
  9.   end;
  10.  
  11.   TListEntry = record
  12.      Head: TMyLinkedHead;
  13.      Data: TData;
  14.   end;
  15.  
Note you must then write

ListEntry.Head.Next^
or
ListEntry.Data.Foo...


I do not know what you want to do on top of that.

Also there is one point I do not know the exact answer, so you may need to google it.

Compilers "align" they fields (the add padding).

record a: byte; b: int64; end;
will create a structure that may have 3 or 7 empty bytes after "a".

I do not know what gcc does...
You can change that by using "packed", or changing compiler settings.
But I do not have the details...

The point is, if you call a c-library, it does not care how your code looks. It cares where in memory each bit of the data is.


you should change the "title" of your post.
Edit your first post in this thread, and change the title: "Linked lists" or "self referring structures" ....



« Last Edit: May 19, 2019, 01:53:32 pm by Martin_fr »

julkas

  • Full Member
  • ***
  • Posts: 150
  • KISS principle
Re: [WANTED] Intrusive data structures
« Reply #4 on: May 19, 2019, 03:38:02 pm »
Another Intrusive Linked List example in C - https://www.cs.helsinki.fi/group/cpro/harj5_13.pdf.
It's based on C offsetof, container_of macros (https://en.wikipedia.org/wiki/Offsetof).

How to program this example in pure Pascal?

Thanks.

BTW. Boost.Intrusive - https://theboostcpplibraries.com/boost.intrusive.
« Last Edit: May 19, 2019, 03:57:27 pm by julkas »
Lazarus 2.0.0 / FPC 3.0.4
----------------------------
procedure mulu64(a, b: QWORD; out clo, chi: QWORD); assembler;
asm
  mov rax, a
  mov rdx, b
  mul rdx
  mov [clo], rax
  mov [chi], rdx
end;

marcov

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 7216
Re: [WANTED] Intrusive data structures
« Reply #5 on: May 19, 2019, 05:37:49 pm »
How to program this example in pure Pascal?

Same as C, (ab)use a preprocessor.

julkas

  • Full Member
  • ***
  • Posts: 150
  • KISS principle
Re: [WANTED] Intrusive data structures
« Reply #6 on: May 19, 2019, 06:06:58 pm »
Same as C, (ab)use a preprocessor.
@marcov thanks. I will try your advice.
Lazarus 2.0.0 / FPC 3.0.4
----------------------------
procedure mulu64(a, b: QWORD; out clo, chi: QWORD); assembler;
asm
  mov rax, a
  mov rdx, b
  mul rdx
  mov [clo], rax
  mov [chi], rdx
end;