Recent

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

julkas

  • Guest
[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 »

Martin_fr

  • Administrator
  • Hero Member
  • *
  • Posts: 9791
  • Debugger - SynEdit - and more
    • 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

  • Guest
Re: [WANTED] Intrusive data structures
« Reply #2 on: May 18, 2019, 08:21:39 pm »

Martin_fr

  • Administrator
  • Hero Member
  • *
  • Posts: 9791
  • Debugger - SynEdit - and more
    • 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

  • Guest
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 »

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11382
  • FPC developer.
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

  • Guest
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.

 

TinyPortal © 2005-2018