Lazarus

Free Pascal => Beginners => Topic started by: julkas on May 18, 2019, 03:03:27 pm

Title: [SOLVED] Linux Kernel Linked List
Post by: julkas on May 18, 2019, 03:03:27 pm
How implement intrusive data structures, e.g - Linux kernel linked list in Pascal?

Thanks.
Title: Re: [WANTED] Intrusive data structures
Post by: Martin_fr 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.
Title: Re: [WANTED] Intrusive data structures
Post by: julkas on May 18, 2019, 08:21:39 pm
Explanation in C - https://isis.poly.edu/kulesh/stuff/src/klist/.
Title: Re: [WANTED] Intrusive data structures
Post by: Martin_fr 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" ....



Title: Re: [WANTED] Intrusive data structures
Post by: julkas 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.
Title: Re: [WANTED] Intrusive data structures
Post by: marcov on May 19, 2019, 05:37:49 pm
How to program this example in pure Pascal?

Same as C, (ab)use a preprocessor.
Title: Re: [WANTED] Intrusive data structures
Post by: julkas on May 19, 2019, 06:06:58 pm
Same as C, (ab)use a preprocessor.
@marcov thanks. I will try your advice.