5 ms·

I can't figure out how the linked list is used. Where is the per-element data? I thought there would be a usage example in the tests, but there wasn't.

DSMan195276 7y ago
These structures are intended to be used like the Linux Kernel's data structures, via `container_of` (Though in the library the macro is called `c7_baseof`. But it does the exact same thing as `container_of`). They have somewhat of an example usage of the list in the `deque.c` file: https://github.com/codr7/libcodr7/blob/2b598e3d89d878ef53e05161ef0fd83320e1e19f/source/codr7/deque.c#L20 https://github.com/codr7/libcodr7/blob/2b598e3d89d878ef53e05... If you don't know about `container_of`, the idea is that it allows you to take a pointer to an inner field, and transform it into a pointer to an outer 'container'. For the linked-list, this means that if you want to make a list of `struct car` objects, you simply embed a `struct c7_list` into `struct car`, pass the address of that internal `struct c7_list` object to the list manipulation functions provided here, and then use `container_of` (Or `c7_baseof`) to transform the pointer to the `struct c7_list` into a pointer to the containing `struct car`. In general, I think `container_of` is one of the best things for writing C code, and it provides a surprising amount of flexibility and nice patterns you can use. It does have the obvious issue of type checking (You could have a `struct wheel` that also has a `struct c7_list` on it, and accidentally add ti to the same `struct c7_list` that has `struct car`), and if your `struct car` needs to be on more than one list at a time it can get confusing knowing which `struct c7_list` entries belong to which list, but in general I'd call it a big net positive. It's also possibly worth noting, you can use this to implement a non-intrusive list if you want, just simply make an object that wraps a `struct c7_list` and a void pointer (Or a typed pointer, if you want), and then write some extra logic around it for allocating nodes and such.
- thestoicattack 7y ago
  Okay, I'm getting it. Not a knock on the author, but looking at this macro'd, pointer-to-void'd stuff certainly makes me appreciate the STL. Edit: aha, I see "intrusive" was the keyword I was missing to learn all about this different style.
  - codr7 7y ago
    It's all about control and flexibility. If you don't need it you shouldn't pay the price. Having spent quite some time trying to bend the STL to my exact requirements, I don't mind so much.
  - DSMan195276 7y ago
    Using `container_of` lets you avoid having to use void pointers. And the macros like foreach are surprisingly readable once you give them a shot, and they're simple enough they don't really have any big gotchas in how they work. Not every `container_of` data structure is perfect, but in general I'd say they're just as nice to use as any other language's data structures (Though `container_of` is flexible in different ways). The only big downside is that it not part of the C standard, leading to more than a few implementations, some more featureful than others. This one is probably the "least featureful" version I've seen, which may be intentional. The Linux Kernel's implementation has a lot more utility things like looping in different ways and different types of list manipulations. Some are highly useful, others not at much.
  - rafa1981 7y ago
    Intrusive lists are very different beasts than lists by value. There are less allocations involved (perf and points of failure), values can be inserted on different lists without new allocations, deletion is O(1), elements can be heterogeneous (different sizes and types), etc etc I seldomly use linked lists, but most of the time i prefer them to be intrusive. There of course are intrusive list implementations on C++.
    - jcheng 7y ago
      > values can be inserted on different lists without new allocations Not multiple lists at the same time, surely...?
      - DSMan195276 7y ago
        They were talking about taking a value off of one list and adding it to a different one, which doesn't require an allocation, but the entity is never on more than one list at a time in that scenario. That said, you can add an entity onto multiple lists if it contains multiple nodes embedded inside. You have to keep track of which nodes are attached to which lists though (Which generally just means being consistent on which you use where). If you give them decent names, then it's not usually a problem, but it can sometimes get a little confusing if you're not careful.
- PCChris23 7y ago
  Also sometimes referred to as "intrusive containers." Related SO post: https://stackoverflow.com/q/5004162/9287029 https://stackoverflow.com/q/5004162/9287029 Also provided for C++ by Boost.Intrusive
- bertr4nd 7y ago
  What a neat trick for creating a fairly generic intrusive data structure. I’d love to have (or put together) a little compendium of clever, non-obvious programming tricks like this.
- kats 7y ago
  Thanks for explaining that.
- juped 7y ago
  Back when I independently invented this due to being self-taught, I didn't know about offsetof(), and I just put the collection at the start and cast the pointer. Learning C is surprisingly obscure even today.
  - DSMan195276 7y ago
    Yeah, even just 'upcasting' is surprisingly effective as well, it's really just inheritance. The lack of being able to embed more than one 'thing' is painful though. And if you're not careful you can run into ugly strict aliasing issues like `struct sockaddr` has (Though a quick `-fno-strict-aliasing` can make all your problems go away...) And I would agree, I find a surprising number of people think C is 'easy' because it doesn't contain that many built-in constructs, and then get completely stuck when they try to use it. To get really good at C, you need a very solid understanding of common and effective patterns you can use. You can still write C without such things, but it quickly becomes a mess of random patterns and inconsistencies. And unfortunately, I can't really think of one source you can really point to for learning them (though admittedly I haven't really looked into it tons).
    - juped 7y ago
      Casting around between the type of the first struct member and the type of the overall struct is okay under strict aliasing, but unfortunately sockaddr violates it because sockaddr isn't a member of sockaddr_in. Not that I knew this at the time, it was just a mysterious rule.
  - codr7 7y ago
    Yeah, I used to spend a lot of time reinventing OOP in C back in the days. Part of the problem is I learned C++ long before I took a serious look at C. These days I definitely prefer embedding/baseof since it's more explicit. When I need polymorphism, stuffing some function pointers in a struct usually works well enough.
codr7 7y ago
Sorry, didn't get around to that yet as it's trivial and used enough internally that I figured it has enough test coverage for now. The c7_list struct is embedded in the items, rbpool [0] uses it to keep track of nodes [1] and slabs [2] for example. Note that the same structure is used as root. [0] https://github.com/codr7/libcodr7/blob/master/source/codr7/rbpool.h https://github.com/codr7/libcodr7/blob/master/source/codr7/r... [1] https://github.com/codr7/libcodr7/blob/master/source/codr7/rbnode.h https://github.com/codr7/libcodr7/blob/master/source/codr7/r... [2] https://github.com/codr7/libcodr7/blob/master/source/codr7/rbslab.h https://github.com/codr7/libcodr7/blob/master/source/codr7/r...

DSMan195276 7y ago

These structures are intended to be used like the Linux Kernel's data structures, via `container_of` (Though in the library the macro is called `c7_baseof`. But it does the exact same thing as `container_of`). They have somewhat of an example usage of the list in the `deque.c` file: https://github.com/codr7/libcodr7/blob/2b598e3d89d878ef53e05161ef0fd83320e1e19f/source/codr7/deque.c#L20 https://github.com/codr7/libcodr7/blob/2b598e3d89d878ef53e05... If you don't know about `container_of`, the idea is that it allows you to take a pointer to an inner field, and transform it into a pointer to an outer 'container'. For the linked-list, this means that if you want to make a list of `struct car` objects, you simply embed a `struct c7_list` into `struct car`, pass the address of that internal `struct c7_list` object to the list manipulation functions provided here, and then use `container_of` (Or `c7_baseof`) to transform the pointer to the `struct c7_list` into a pointer to the containing `struct car`. In general, I think `container_of` is one of the best things for writing C code, and it provides a surprising amount of flexibility and nice patterns you can use. It does have the obvious issue of type checking (You could have a `struct wheel` that also has a `struct c7_list` on it, and accidentally add ti to the same `struct c7_list` that has `struct car`), and if your `struct car` needs to be on more than one list at a time it can get confusing knowing which `struct c7_list` entries belong to which list, but in general I'd call it a big net positive. It's also possibly worth noting, you can use this to implement a non-intrusive list if you want, just simply make an object that wraps a `struct c7_list` and a void pointer (Or a typed pointer, if you want), and then write some extra logic around it for allocating nodes and such.

thestoicattack 7y ago
Okay, I'm getting it. Not a knock on the author, but looking at this macro'd, pointer-to-void'd stuff certainly makes me appreciate the STL. Edit: aha, I see "intrusive" was the keyword I was missing to learn all about this different style.
- codr7 7y ago
  It's all about control and flexibility. If you don't need it you shouldn't pay the price. Having spent quite some time trying to bend the STL to my exact requirements, I don't mind so much.
- DSMan195276 7y ago
  Using `container_of` lets you avoid having to use void pointers. And the macros like foreach are surprisingly readable once you give them a shot, and they're simple enough they don't really have any big gotchas in how they work. Not every `container_of` data structure is perfect, but in general I'd say they're just as nice to use as any other language's data structures (Though `container_of` is flexible in different ways). The only big downside is that it not part of the C standard, leading to more than a few implementations, some more featureful than others. This one is probably the "least featureful" version I've seen, which may be intentional. The Linux Kernel's implementation has a lot more utility things like looping in different ways and different types of list manipulations. Some are highly useful, others not at much.
- rafa1981 7y ago
  Intrusive lists are very different beasts than lists by value. There are less allocations involved (perf and points of failure), values can be inserted on different lists without new allocations, deletion is O(1), elements can be heterogeneous (different sizes and types), etc etc I seldomly use linked lists, but most of the time i prefer them to be intrusive. There of course are intrusive list implementations on C++.
  - jcheng 7y ago
    > values can be inserted on different lists without new allocations Not multiple lists at the same time, surely...?
    - DSMan195276 7y ago
      They were talking about taking a value off of one list and adding it to a different one, which doesn't require an allocation, but the entity is never on more than one list at a time in that scenario. That said, you can add an entity onto multiple lists if it contains multiple nodes embedded inside. You have to keep track of which nodes are attached to which lists though (Which generally just means being consistent on which you use where). If you give them decent names, then it's not usually a problem, but it can sometimes get a little confusing if you're not careful.
PCChris23 7y ago
Also sometimes referred to as "intrusive containers." Related SO post: https://stackoverflow.com/q/5004162/9287029 https://stackoverflow.com/q/5004162/9287029 Also provided for C++ by Boost.Intrusive
bertr4nd 7y ago
What a neat trick for creating a fairly generic intrusive data structure. I’d love to have (or put together) a little compendium of clever, non-obvious programming tricks like this.
kats 7y ago
Thanks for explaining that.
juped 7y ago
Back when I independently invented this due to being self-taught, I didn't know about offsetof(), and I just put the collection at the start and cast the pointer. Learning C is surprisingly obscure even today.
- DSMan195276 7y ago
  Yeah, even just 'upcasting' is surprisingly effective as well, it's really just inheritance. The lack of being able to embed more than one 'thing' is painful though. And if you're not careful you can run into ugly strict aliasing issues like `struct sockaddr` has (Though a quick `-fno-strict-aliasing` can make all your problems go away...) And I would agree, I find a surprising number of people think C is 'easy' because it doesn't contain that many built-in constructs, and then get completely stuck when they try to use it. To get really good at C, you need a very solid understanding of common and effective patterns you can use. You can still write C without such things, but it quickly becomes a mess of random patterns and inconsistencies. And unfortunately, I can't really think of one source you can really point to for learning them (though admittedly I haven't really looked into it tons).
  - juped 7y ago
    Casting around between the type of the first struct member and the type of the overall struct is okay under strict aliasing, but unfortunately sockaddr violates it because sockaddr isn't a member of sockaddr_in. Not that I knew this at the time, it was just a mysterious rule.
- codr7 7y ago
  Yeah, I used to spend a lot of time reinventing OOP in C back in the days. Part of the problem is I learned C++ long before I took a serious look at C. These days I definitely prefer embedding/baseof since it's more explicit. When I need polymorphism, stuffing some function pointers in a struct usually works well enough.

codr7 7y ago

Sorry, didn't get around to that yet as it's trivial and used enough internally that I figured it has enough test coverage for now. The c7_list struct is embedded in the items, rbpool [0] uses it to keep track of nodes [1] and slabs [2] for example. Note that the same structure is used as root. [0] https://github.com/codr7/libcodr7/blob/master/source/codr7/rbpool.h https://github.com/codr7/libcodr7/blob/master/source/codr7/r... [1] https://github.com/codr7/libcodr7/blob/master/source/codr7/rbnode.h https://github.com/codr7/libcodr7/blob/master/source/codr7/r... [2] https://github.com/codr7/libcodr7/blob/master/source/codr7/rbslab.h https://github.com/codr7/libcodr7/blob/master/source/codr7/r...