intrusive type just means you put add the fields required to support a collection type (like next pointer for a linked list or parent, left, and right child pointers for a tree) into data itself (which is a often a complex struct)
const Coord = struct {
x: u32,
y: u32,
next: ?*Coord,
};
You want that next pointer the first in the struct for hardware reasons (there’s fast and slow paths for pointer chasing you can take advantage of), but zig doesn’t let you control that unless you make the struct extern and now we’re getting off topic.
If your language has the correct compile time semantics you can invert that a little and use encapsulation to do:
const Coord = struct { x: u32, y: u32};
pub fn LinkedNode(Data: type) type {
return struct {
const This = @This();
d: Data,
next: ?*This,
};
}
const LinkedCoord = LinkedNode(Coord);
the c++ version if that is easiest to understand would be
template<typename Data>
struct LinkedNode {
Data d;
next: *This;
};
using LinkedCoord = LinkedNode<Coord>;
This lets you still treat the linked list somewhat as its own structure and making it more reusable. The second way isn’t possible in many language without some ugly hackery (like it can be done in C with heavy macro use, but it just easier to do the first way).
I don’t know if this second way is tecnically invasive, but it shares most of the same characteristics. with some addition posiitives and negatives (eg, having multiple invasive structures – fairly common – can get really ugly, and the next pointer isn’t repurposed nearly as easily – think of a an object with a next pointer being used to chain in a hashtable put then used for a free list when not in the table).
The alternative non-intrusive way would be keeping the as an opaque pointer void pointer (generic Object reference in Java,
const LinkedListNode = struct {
data: *anyopaque, // void* in C
next: ?*LinkedListNode,
};
you two pointer hops to get to your data now. linked lists are slow enough that doubling the pointer chases is way painful.
They are a good example of expedience over pureness - usually hallmarks of system languages.
I actually have something like this in some code, 3 invasive structs on a single node and some of those values (the two next pointers) carry double duty depending on the current state of the object (and I use a hack to make the pointers nullable). Doing this in non-intrinsics code would be a monstrosity.:
const TradeReq = struct {
// ... a bunch of fields for reconsiling some events
const This = @This();
fl_next: *This,
tr_parent: *This,
tr_childred: *This,
oob_next: *This,
};
)