Doubly-linked lists -all data structures that have back pointers- are really difficult to mutate thread-safely.
Intrusive linked lists (2019)
61–70 of 80 posts
Re: Intrusive linked lists (2019)
#62Re: Intrusive linked lists (2019)
#63I was surprised to see the main benefit of intrusive linking mentioned as a bit of a side note: The ability to move data around between lists (and within a list) without copying. You also get O(1) removal from the middle of the list, assuming you have a pointer to the object somewhere else. As a result, when you have large state structs and you don't do a lot of list scans, intrusive linking makes things a lot faster…
You can do this with non intrusive lists too. See c++’s merge/splice/etc. You can store the iterators in some other place as you do this, making it quite handy on occasion.
Re: Intrusive linked lists (2019)
#64Earlier quoted context omitted.
> Now you have a naming problem. You need a naming convention that every user of the list library must follow, or else their types will be incompatible. Oh, that's simple: just have empty struct tags. > And what about typedefs? The names introduced by the typedefs are irrelevant. > A and B are typedef-related (their normal forms, obtained by following all typedefs, are the same), lists of A and B will be incompatible…
No, any tagless type is unique, so neither A and B nor list_of_A and list_of_B are compatible. This is what I like to fix in C2y outside of typedefs (and it would really help if you file wishlist bugs with compilers if you agree).
Wait, seriously? They are unique, sure, but the 6.2.7.1 quite explicitly states they are compatible as long as they're in separate files:
Moreover, two structure,
union, or enumerated types declared in separate translation units are compatible if their
tags and members satisfy the following requirements: If one is declared with a tag, the
other shall be declared with the same tag. If both are completed anywhere within their
respective translation units, then the following additional requirements apply: there shall
be a one-to-one correspondence between their members such that each pair of
corresponding members are declared with compatible types; if one member of the pair is
declared with an alignment specifier, the other is declared with an equivalent alignment
specifier; and if one member of the pair is declared with a name, the other is declared
with the same name. For two structures, corresponding members shall be declared in the
same order. For two structures or unions, corresponding bit-fields shall have the same
widths. For two enumerations, corresponding members shall have the same values.
Re: Intrusive linked lists (2019)
#65Earlier quoted context omitted.
> It is awkward in C, where the implementation has to be macro-generated. You can avoid having the implementation be macro-generated by "hiding" the list pointers before a char payload[0]. See https://pastebin.com/DE69mbJD for an example. The same technique is used by glibc's malloc to store metadata about the allocation right next to your data, and then recover it when you call realloc/free, without needing a separa…
Zero-sized arrays are not standard. Accessing an array out of bounds is UB. At the very least, you should use a flexible array member instead (char payload[];). But even if you did that, strict aliasing implies that 'payload' can only be accessed as an array of character type. It is correct to memcpy between 'payload' and another object of arbitrary type T of the appropriate size (as list_push_ does in your example),…
I'm curious, what would be the point of having a zero-sized array if you can't access it?
Re: Intrusive linked lists (2019)
#66Earlier quoted context omitted.
It depends what is meant by "compatible." Is the memory layout the same? Yes. Can I memcpy between them? Yes...
We mean compatible as defined by the C language standard. It is much more restrictive than having the same layout. In particular, you may not pass a pointer to a type where a pointer to an incompatible type is expected, even if the types have the same layout, which prevents the sort of sharing between two libraries that is being discussed. Moreover, there is no guarantee that two distinct structure types with the sam…
Furthermore, two structure, union, or enumerated types declared in separate translation units are
compatible in the following cases:
— both are declared without tags and they fulfill the preceding requirements;
— there shall be a one-to-one correspondence between their members such that each pair of
corresponding members are declared with compatible types;
— if one member of the pair is declared with an alignment specifier, the other is declared with an
equivalent alignment specifier;
— and, if one member of the pair is declared with a name, the other is declared with the same
name.
For two structures, corresponding members shall be declared in the same order. For two unions
declared in the same translation unit, corresponding members shall be declared in the same order. For
two structures or unions, corresponding bit-fields shall have the same widths. For two enumerations,
corresponding members shall have the same values; if one has a fixed underlying type, then the
other shall have a compatible fixed underlying type. For determining type compatibility, anonymous
structures and unions are considered a regular member of the containing structure or union type,
and the type of an anonymous structure or union is considered compatible with the type of another
anonymous structure or union, respectively, if their members fulfill the preceding requirements.
Re: Intrusive linked lists (2019)
#67Earlier quoted context omitted.
> It does not matter that storage happens to be allocated beyond the end of said array. It does matter, for malloc-returned storage. You can put whatever objects you want into that storage as long as it fits and the pointer is properly aligned. > Strict aliasing ...is not violated; memcpy takes a void pointer as its destination, sets the effective type of the storage behind it, and the treats it as an array of unsign…
> It does matter, for malloc-returned storage. You can put whatever objects you want into that storage as long as it fits and the pointer is properly aligned. You can certainly store an object of arbitrary type, but here it is done through a pointer to an object with pointer arithmetic going beyond the allowed bounds. > memcpy takes a void pointer as its destination, sets the effective type of the storage behind it A…
> but here it is done through a pointer to an object with pointer arithmetic going beyond the allowed bounds.
When you do "void *x = malloc(sizeof(struct node))", the returned storage doesn't have struct node object in it, it has an object of no effective type in it, with size "sizeof(struct node)". Taking the pointer to payload[] field is in no way different from doing "(char*) x + offsetof(struct node, payload)" — it takes a char pointer into the object storage, adds a number (less than the object's size) and so produces another char pointer that points somewhere inside into the object storage — and no, since there has been no actual referencing of the object's value, constructing such a pointer does not set the effective type of that object; and a char pointer is explicitly allowed to alias whatever storage. Then the memcpy sets the effective type, done. No UB anywhere.
Re: Intrusive linked lists (2019)
#68Earlier quoted context omitted.
No, any tagless type is unique, so neither A and B nor list_of_A and list_of_B are compatible. This is what I like to fix in C2y outside of typedefs (and it would really help if you file wishlist bugs with compilers if you agree).
Wait, seriously? They are unique, sure, but the 6.2.7.1 quite explicitly states they are compatible as long as they're in separate files: Moreover, two structure, union, or enumerated types declared in separate translation units are compatible if their tags and members satisfy the following requirements: If one is declared with a tag, the other shall be declared with the same tag. If both are completed anywhere withi…
No, you are right, but it is not "in separate files" but "translation units". Two distinct list(int) from two different libraries need to be compatible when used together, which means you would include the header of those two libraries and then both end up in the same translation unit.
C23 relaxed requirements for types with tag, this works for structures with tag, but for type generic structures you then need to synthesize a tag that depends on the type, e.g. list_int, list_float, etc.. so that differently parametrized types do not collide. This works quite well in practice, but is not perfect.
Re: Intrusive linked lists (2019)
#69Earlier quoted context omitted.
Wait, seriously? They are unique, sure, but the 6.2.7.1 quite explicitly states they are compatible as long as they're in separate files: Moreover, two structure, union, or enumerated types declared in separate translation units are compatible if their tags and members satisfy the following requirements: If one is declared with a tag, the other shall be declared with the same tag. If both are completed anywhere withi…
No, you are right, but it is not "in separate files" but "translation units". Two distinct list(int) from two different libraries need to be compatible when used together, which means you would include the header of those two libraries and then both end up in the same translation unit. C23 relaxed requirements for types with tag, this works for structures with tag, but for type generic structures you then need to syn…
I don't think that's the scenario the other commenter was talking about:
> there is no centralized monomorphization. If an application uses two libraries, each of which handles lists of int, each library will have to independently macro-generate its separate list implementation, and because C's type system is nominal, the generated types will be isomorphic but incompatible.
So, lib_a.c includes header_only_list.h, and lib_b.c also includes the same header_only_list.h, but they can't they pass the list structures between each other because those structs would be incompatible even though they're textually identical ("the generated types will be isomorphic but incompatible"). To which I replied that no, they would not, no C program would be able to work if this were true.
Otherwise, the mentioning of monomorphization doesn't make any sense: of course two completely different implementations of lists will be incompatible.
Re: Intrusive linked lists (2019)
#70Is this sort of thing no longer part of a standard computer science or software engineering undergrad curriculum?
When did you last encounter or use a linked list ? :)
Linked lists fell out of fashion once the cpu/memory latency gap opened up towards the end of the 1990s. For most use cases it's simply better to use a tightly packed array, even use cases where linked lists would intuitively make more sense.