Goal

Goal of this post is to show the learnings specifically the generics programming in C, and the other C related techniques that I really liked.

Target Readers

The targeted readers are the folks interested in C Programming languages and know the language in begineer and intermediate stages, but interested to learn new techniques.

Blog

I recently read the linux kernel by Robert Love, It was a nice book, but became sligthly more dry for me once it came to end, as it was too much code definition after the VFS chapter.

I wantedo to share two techniques that I noticed in the book used in the linux kernel to implement the generics linked list data structure.

Usually I thought that if you required two data structures in C, you would have two different data structure, and you would re-implement all the functionlity for the new data structure.

The technique goes something like this:

  1. Implement linked list and its helper without and data part.
  2. Create the data structure, which you want to use in the linked list, for exapmle int_linked_list, float linked list, etc.
  3. embed the linkedlist in the said structure, like this: struct int_linked_list {int data, linked_list list};
  4. While using any of the linked list specific functionality, pass the nested linked list to the functions, and the result will be given as a pointer of linked_list.
  5. use offset_of gcc functionality to retrieve the parent object pointer.

The interesting part is #5, it works because the C ABI is stable, and after compiling the order of the field of list in the parent data structure is always fixed, that’s why these pointer manipulations works. These things won’t work with languages, whose ABI is not fixed like Rust, but we don’t require these because they support generics, and monomorphism, that is it will actually generate different linked list impelmentation for different data types at the compile time that’s why the binary size would be bigger in Rust, but that can be changed by passing the rust specific parameter to optimize for the binary size, which might be important for some environment like embedded.

Other interesting thing.

If you want to have a function, but you don’t want to change all the places where that function is used; you can create a struct which contain the function as the first field, which accept the same struct, now the new fields can be added later, without modifying all the functions.