44 ms·

C Macro Magic

210 points by sagartewari01 8y ago

tokyodude 8y ago
why is this amazing? such macros have been around since the 80s. then we got various implementations of intrusive list in C++ and they became typesafe
- sagartewari01 8y ago
  Yes, I suppose such use cases were the reason 'offsetof' was introduced. It's just that I wasn't taught any uses of macros other than trivial examples like `MIN` and `MAX`. That's why I found it interesting.
- IgorPartola 8y ago
  Because most people haven’t seen it before? For people who program in languages in which this stuff isn’t possible, this pattern isn’t obvious. No need to dismiss it just because it’s obvious to you.
- bsenftner 8y ago
  I remember using it in C in '79...
mmastrac 8y ago
C is surprisingly complex when you dig into it - I have a little example I pull out every once in a while where you can write code that runs one way when a global typedef is defined with a certain name, and other way when the variable isn't defined (compiling just fine both ways).
- IgorPartola 8y ago
  No C is very very simple. That’s why it’s not easy :) No but really, there isn’t anything to it. Just think about how a CPU sees memory and registers and it becomes intuitive. But that doesn’t make it easy to use because it doesn’t give you any guard rails to show you the one true way to accomplish a task.
  - mmastrac 8y ago
    I agree partially - overall C's promise was that it was a light wrapper over top of registers and memory, absolutely. The issues with C are around some of the weirder bits of the parsing process, namely the context-sensitive parser and the "interesting" corner cases of how the C preprocessor works. Edit: Here's a fun example - try it with and without the typedef line commented out: typedef int T1; int main() { const T1 (*T1); printf("%d\n", _Generic((T1), const int *: 1, const int (*)(int *): 2)); }
    - IshKebab 8y ago
      Also the rules around undefined behaviour, type aliasing and so on are definitely not simple.
    - saagarjha 8y ago
      Seems like a "most vexing parse", but for C!
    - acura 8y ago
      Is it expected to compile without the typedef?
      - foldr 8y ago
        Amazingly, it does compile. I believe the declaration that looks as though it shouldn't (because T1 isn't defined) compiles as a function pointer declaration, where the first T1 is the name of the variable defined and the second is, in syntactic terms, the name of the function. With the typedef commented out, you can delete the second T1 on that line. Note that the type of a variable defaults to int in C, so you can write 'const a' instead of 'const int a'. The return type of a function also defaults to int.
        saagarjha 8y ago
        Clang accepts it, but GCC does not. I suspect there's a bug here.
- hevi_jos 8y ago
  C is extremely simple. In fact is one of the few languages that you could manage to understand completely in the sense of knowing exactly what it does. C macros on the other hand, should die. I use C a lot but never ever use c macros, they are evil. Extremely hard to debug, confusing and very weak. When we want macros, we use Lisp, that have proper macros.
  - bitt 8y ago
    I'm not sure of all the valid use cases for macros, but I think they are useful when you need to do something simple. For example, a debug flag to run some code like verbose logging but you don't want to include that in the release binary. C# has preprocessor directives but I wish that java had something similar. I guess this is different than complex micros though.
xtacy 8y ago
FWIW, this magic is how the Linux kernel implements generic linked lists, hash tables, and red-black trees: https://stackoverflow.com/questions/15832301/understanding-container-of-macro-in-the-linux-kernel https://stackoverflow.com/questions/15832301/understanding-c...
- paavoova 8y ago
  So this would be hashing the pointer? In which case it doesn't support keys, like strings, etc. I'm now wondering if this is the more common use case for hash tables, where you just need a reference to a unique object rather than a specific key.
  - taeric 8y ago
    Java has IdentityHashMap for this use. I hesitate to claim it is more common.
  - xtacy 8y ago
    No, that's not true. The insert function (hash, rbtree, etc.) takes a hash node as an argument. So, in the kernel implementation the caller is expected to hash. EDIT: check out some examples to see for yourself: https://elixir.bootlin.com/linux/latest/ident/hlist_add_head https://elixir.bootlin.com/linux/latest/ident/hlist_add_head
eatbitseveryday 8y ago
This is exactly how the list implementation in the Linux kernel works [1]. I've extracted this header file and used it in user-space before, too. The cool trick is in calculating an offset to the start of the struct containing the link. But I do not think this trick or list implementation is newly introduced in Wayland. It existed at least as far back as kernel 2.6.11 [2]. [1] https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/list.h?h=v5.0-rc8 https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin... [2] https://elixir.bootlin.com/linux/v2.6.11/source/include/linux/list.h https://elixir.bootlin.com/linux/v2.6.11/source/include/linu...
- fmela 8y ago
  I've seen this same trick done with macros in BSD kernel code from the 80s!
  - electrum 8y ago
    Here's the code from FreeBSD: https://github.com/freebsd/freebsd/blob/master/sys/sys/queue.h https://github.com/freebsd/freebsd/blob/master/sys/sys/queue...
    - deleted 8y ago
      [deleted]
- eps 8y ago
  This is an exceedingly common way of using containers in C, because how fast and predictable it is during the run-time. It also allows putting a single data item into multiple containers like that. It's used pretty much in every OS kernel, Windows included.
- buserror 8y ago
  I've been using queue.h from bsd for as long as I can remember. It's slightly different syntax, but it's available on linux, from userland, and is not GPL... Note that the one that ships in linux is pretty simple, the one that is in BSD is a lot more complete.
yesenadam 8y ago
Spelling: "it's" should be "its" except when short for "it is" I believe. i.e. >It’s a simple doubly linked list. Here’s it’s definition The first one's right, the second should be its. Though almost most native speakers seem to do this, so I guess it won't be 'wrong' for much longer...
- Foober223 8y ago
  FYI some people were taught to use an apostrophe to imply ownership. It used to be the "official" way, but no longer. The gorilla guards it's bananas.
  - pascal_cuoq 8y ago
    And if we are talking about several gorillas, they guard they're bananas. It makes sense now, thanks.
  - yesenadam 8y ago
    >It used to be the "official" way Oh right, thank you, I didn't know the history. Short version: https://www.merriam-webster.com/words-at-play/the-tangled-history-of-its-and-its https://www.merriam-webster.com/words-at-play/the-tangled-hi... Did you mean, some people now alive were taught that "it's" is right (in "it's definition"), or just ownership generally (Harry's). Well, it's better than using apostrophes for plural's, which seems very common too.
CoolGuySteve 8y ago
2 things concerning wl_list: 1) In C++ you can use struct inheritance to get the same functionality without macros or templates. ie: struct ThingList : wl_list { /* data elements */ } 2) Like in the C++ case above, the next and prev elements should probably be at the top if you plan on iterating a lot since the next/prev pointers will be in the first cacheline that you load when you dereference previous list elem. In this case, it's also worth allocating list nodes with posix_memalign. OTOH, there might be reasons why you want the list buried deep in the struct, like if the other data element access times are more important.
- ploxiln 8y ago
  You can do something similar in C - make struct wl_list the first member of struct data, and just cast the wl_list node pointer to a data pointer (offsetof is zero). I think the most common reason for this generic-location offset-of style is so that the struct data can have multiple list nodes and be on multiple lists (without any extra allocation). This is pretty common in the kernel.
- eps 8y ago
  Re: #1 - Now try and place Thing on two lists, a map and a hash table or a combination of thereof. No way to do this cleanly in C++. At best, it's going to be an iterator galore, at worst some boost-style frankencode.
roel_v 8y ago
Oh but this is only the beginning. With boost MPL, you can do full metaprogramming at preprocessing time (I'm not 100% sure but I think the C++ preprocessor is compatible with that of C? So that would make MPL applicable to C code as well.). You can generate code by iterating over lists of preprocessor 'variables' and do other crazy things that seem impossible the first few times you think about it. It's great, albeit a little bit confusing the next time you come back to it, because it makes you think more about what level you're metaprogramming at.
- jjtheblunt 8y ago
  The C preprocessor wouldn't balk at "char template;" but that of C++ ?
- gpderetta 8y ago
  I think you mean the Boost Preprocessor Library. MPL is template based and quite a bit dated by today's standards. C++ Preprocessor is pretty much the same as C (they might go formally out of sync from o e standard release to another but in practice compilers implement the same features as far as I know).
AJRF 8y ago
From Objective-C, you can make switch statements support strings with 6 lines of macro: ifndef TTD_SWITCH_STRING #define TTD_SWITCH_STRING #define TTD_CASE(str) if ([__s__ isEqualToString:(str)]) #define TTD_SWITCH(s) for (NSString *__s__ = (s); ; ) #define TTD_DEFAULT #endif
- AnaniasAnanas 8y ago
  This is quite cool, that being said, you would need to add a break at least at the end to that, unlike a regular switch. Plus it would not work in the case that you want multiple strings to lead to the same code
- burfog 8y ago
  Somebody, please just fix the language. Extend all the free compilers or, better yet, run the changes through the standards committee. People have been dying for this feature for over half a century. While you're at it, just make the feature generic. Handle arbitrary arrays, structs, unions, and floating-point types. The ... feature supported by gcc is also a huge usability improvement. Don't allow weird sorting order issues with strings. Don't allow it for structs and unions.
  - unwind 8y ago
    None of those types can be compared directly in C, so that's not making the feature "generic", it's making it magically super-powered. Associating comparison intelligence with arbitrary types is not very obvious how to do in C, but I guess the new super-switch could accept a function pointer in addition to the data, or something. Like: const char * s const = "bar"; switch (s, strcmp) { case "foo": printf("I got foo\n"); break; case "bar": printf("nopes, I got bar\n"); break; default: printf("neither foo nor bar :/\n"); } Which would be fine/acceptable, but not exactly how C tends to roll.
    - glouwbug 8y ago
      Why not just use an enum for the switch, and if strings need to reflect the enum, use an xmacro to expand the enum into an array of strings? https://github.com/glouw/andvaranaut/blob/master/src/Theme.c https://github.com/glouw/andvaranaut/blob/master/src/Theme.c
ogoffart 8y ago
> Maybe that’s the reason people who use the C language love it so much. You can’t do that in any other language. But you can't do it in C. __typeof__ is a GNU extension. > Note that wl_list is not a very safe data structure, in the sense that a programmer need to know exactly how to use it. You can do it in C++ with template, and it would be type safe.
- twtw 8y ago
  typeof is a GNU extension, but it (or an equivalent) is implemented in every compiler anyone actually uses. You can do it in C, you just can't do it in the part of C the standards committee has decided to standardize. I'm not sure what the value is of defining C as standard C when loads of software has shipped for decades using this pattern.
  - comex 8y ago
    ...with the notable exception of MSVC.
    - Gibbon1 8y ago
      I wouldn't call MSVC a C compiler until more recently.
      - fdgdfgdfg 8y ago
        Recent studies suggest now happened roughly recently.
  - taneq 8y ago
    And there you have it. Purists claim C or C++ can't do X because it's UBH in the standard. Pragmatists know that C and (especially) C++ aren't languages on their own, while "gcc" and "MSVC++" are complete (and very similar) languages.
    - adrianN 8y ago
AnaniasAnanas 8y ago
> You can’t do that in any other language. Except languages with parametric polymorphism, such as ML and Haskell.
- 0db532a0 8y ago
  Or C++ and Java.
- rkangel 8y ago
  Not quite right, in other languages you (a) can't, and (b) don't have to (thankfully). The compiler doing my offsetting for me using type information is much safer and more reliable.
trulyrandom 8y ago
These sorts of macro tricks are cute, but they quickly become a pain when using an FFI.
openloop 8y ago
I like it.
RustyRussell 8y ago
As others have pointed out, this is also used in the Linux kernel. But unfortunately it shares the kernel error of using the same type for list head and member. That's not good separation, and on particular it means list_add() is ambiguous (the kernel one is member, head, which is backwards). Hence I recommend kernel refugees start with CCAN's list: http://ccodearchive.net/info/list.html http://ccodearchive.net/info/list.html
pdkl95 8y ago
wl_list seems like an incomplete re-implementation of the LIST_ macros in <sys/queue.h>. http://man7.org/linux/man-pages/man3/queue.3.html http://man7.org/linux/man-pages/man3/queue.3.html https://github.com/freebsd/freebsd/blob/master/sys/sys/queue.h https://github.com/freebsd/freebsd/blob/master/sys/sys/queue...
- 0db532a0 8y ago
  It isn’t, at least directly. I am actually really happy to see this alternative, as queue.h uses anonymous structs, which are C11 and not well supported.
okl 8y ago
Macro-based, non-intrusive data structures: https://gitlab.com/oliver117/ucds/tree/master/src https://gitlab.com/oliver117/ucds/tree/master/src
scoutt 8y ago
Could be a catch that while this kind of constructs work OK for local lists, you have to be aware when passing the struct between applications or processes compiled with different packing but using the same struct definition with non-aligned members. struct foo { uint8_t data[3]; struct wl_list link; }; For an application link member may be at offset 3 while for another it would be at offset 4. That may be the reason link should be put as the first member, and a simple cast would let you walk the list.
- AstralStorm 8y ago
  Usually it does not matter as you keep items of the same type or know the type and exact compiler. Unless you want to write them somewhere or put it as part of API and ABI. Which you probably shouldn't.
  - scoutt 8y ago
    It's true that types has something to do with it, but the main issue is padding. While I can keep the same type (i.e. uint8_t), it's the padding following uint8_t var[3] that may vary according on packing options when compiling. http://www.catb.org/esr/structure-packing/#_structure_alignment_and_padding http://www.catb.org/esr/structure-packing/#_structure_alignm...
colinfinck 8y ago
This implementation of doubly linked lists is not even exclusive to Unix-based operating systems, but also known as struct LIST_ENTRY under Windows/ReactOS and heavily used for kernel development there. They also provide a singly linked list version as struct SINGLE_LIST_ENTRY. Check e.g. https://docs.microsoft.com/en-us/windows/desktop/api/ntdef/ns-ntdef-_list_entry https://docs.microsoft.com/en-us/windows/desktop/api/ntdef/n... and https://git.reactos.org/?p=reactos.git&a=search&h=HEAD&st=grep&s=LIST_ENTRY https://git.reactos.org/?p=reactos.git&a=search&h=HEAD&st=gr...
AstralStorm 8y ago
Intrusive lists. A trick probably as old as C itself. Multiple libraries provide an equivalent in C++. The claim that you can only do that unsafely or need C "magic" is completely wrong. The safe implementations are not even slower, as the main gain is node cache locality.
tiehuis 8y ago
A comparable implementation in Zig. Key detail is `@fieldParentPtr` [1], which has the same functionality as `container_of`. const std = @import("std"); const wl_list = struct { prev: *wl_list, next: *wl_list, fn init(list: *wl_list) void { list.prev = list; list.next = list; } fn insert(list: *wl_list, elem: *wl_list) void { elem.prev = list; elem.next = list.next; list.next = elem; elem.next.prev = elem; } }; const Data = struct { data: i32, link: wl_list, fn init(data: i32) Data { return Data{ .data = data, .link = undefined, }; } }; pub fn main() void { var foo_list: wl_list = undefined; foo_list.init(); var e1 = Data.init(1); var e2 = Data.init(2); var e3 = Data.init(3); foo_list.insert(&e1.link); foo_list.insert(&e2.link); e2.link.insert(&e3.link); var entry = @fieldParentPtr(Data, "link", foo_list.next); while (&entry.link != &foo_list) : (entry = @fieldParentPtr(Data, "link", entry.link.next)) { std.debug.warn("{}\n", entry.data); } } [1] https://ziglang.org/documentation/master/#fieldParentPtr https://ziglang.org/documentation/master/#fieldParentPtr
baby 8y ago
I avoid anything magic in C.
antirez 8y ago
An alternative could be to guarantee that the first two elements of the data structure are next and prev pointers. This way the implementation can just assume the first 8 or 16 bytes (depending on sizeof(void*)) are the next/prev addresses. Then the same set of functions can work with everything that looks like a linked list. Another option is to have a "struct list" that contains the information needed, and the API allows, when you initialize the list, to say how much space you want starting at "node->data". This way the node is always over-allocated by the library, and when you want to manipulate the list items you cast node->data to your privata data structure.
- emersion 8y ago
  This approach is less type-safe.
  - antirez 8y ago
    Yep.
- aidenn0 8y ago
  If wl_list was required to be the first member of the struct, the wl_container_of() FLM becomes trivial. This implementation comes from the kernel though, where a single item might be in multiple lists.
floatboth 8y ago
Rust magic: https://github.com/Amanieu/intrusive-rs https://github.com/Amanieu/intrusive-rs
mlthoughts2018 8y ago
C macro magic? Run.
rkangel 8y ago
An alternative implementation is to put the link structure at the beginning of the data structure. Then converting between one and the other is just a cast between the two types. This is a fairly standard technique in C to get some version of inheritance of structs, and how I have implement LLs in the past. I don't see what this extra complexity of sizeof() offset calculations gains you.
- tom_ 8y ago
  It allows the object to be part of multiple lists.
  - rkangel 8y ago
    That's an excellent point, thanks.
- potiuper 8y ago
  More importantly offsetof is an implementation-specific macro. Whatever it does cannot be generalized from its definition for one or many compilers to a language requirement. The use of the offsetof macro in a program may cause undefined behavior when compiled with GCC or Clang. GCC instead provides __builtin_offsetof. If multiple lists are desired, then an array of them should be declared at the head of the struct and the index be fixed to the type of list desired to contain a reference to the struct. Additionally, as rustyrussell wrote in another comment the list head and member structs should be different in order to optimize the list struct as CCAN's list is implemented, but it too uses offsetof, which leads to the same issue of undefined behavior. Ref: https://en.wikipedia.org/wiki/Offsetof https://en.wikipedia.org/wiki/Offsetof https://stackoverflow.com/questions/26906621/does-struct-name-null-b-cause-undefined-behaviour-in-c11 https://stackoverflow.com/questions/26906621/does-struct-nam...
  - rkangel 8y ago
    This is not true. offsetof is defined in the C standard. See http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf, Section 7.17, point 3 on page 254. I prefer not to use it due to the loss of type information and the potential for screwups, but you can write ANSI portable C using it.
magicseth 8y ago
I've used uthash in the past for a similar hash implementation. It certainly has its wrinkles, i.e. you may need to include several if you want to include an object in multiple hashes... but it was fun to use and straightforward! https://troydhanson.github.io/uthash/ https://troydhanson.github.io/uthash/
gowld 8y ago
This is C's version a Ruby-style Mixin. By adding a List link to your datatype, you can use List operations on your data. https://en.wikipedia.org/wiki/Mixin https://en.wikipedia.org/wiki/Mixin Also, is this macro magic, or simply memory layout magic? The macros look like appreviations for readability, not magic required to make the structure work.
sfilargi 8y ago
Just because you can, doesn't mean you should. Unless you are hacking the linux kernel, use a type safe language folks.

210 points by sagartewari01 8y ago

why is this amazing? such macros have been around since the 80s. then we got various implementations of intrusive list in C++ and they became typesafe

sagartewari01 8y ago
Yes, I suppose such use cases were the reason 'offsetof' was introduced. It's just that I wasn't taught any uses of macros other than trivial examples like `MIN` and `MAX`. That's why I found it interesting.
IgorPartola 8y ago
Because most people haven’t seen it before? For people who program in languages in which this stuff isn’t possible, this pattern isn’t obvious. No need to dismiss it just because it’s obvious to you.
bsenftner 8y ago
I remember using it in C in '79...

mmastrac 8y ago

C is surprisingly complex when you dig into it - I have a little example I pull out every once in a while where you can write code that runs one way when a global typedef is defined with a certain name, and other way when the variable isn't defined (compiling just fine both ways).

IgorPartola 8y ago
No C is very very simple. That’s why it’s not easy :) No but really, there isn’t anything to it. Just think about how a CPU sees memory and registers and it becomes intuitive. But that doesn’t make it easy to use because it doesn’t give you any guard rails to show you the one true way to accomplish a task.
- mmastrac 8y ago
  I agree partially - overall C's promise was that it was a light wrapper over top of registers and memory, absolutely. The issues with C are around some of the weirder bits of the parsing process, namely the context-sensitive parser and the "interesting" corner cases of how the C preprocessor works. Edit: Here's a fun example - try it with and without the typedef line commented out: typedef int T1; int main() { const T1 (*T1); printf("%d\n", _Generic((T1), const int *: 1, const int (*)(int *): 2)); }
  - IshKebab 8y ago
    Also the rules around undefined behaviour, type aliasing and so on are definitely not simple.
  - saagarjha 8y ago
    Seems like a "most vexing parse", but for C!
  - acura 8y ago
    Is it expected to compile without the typedef?
    - foldr 8y ago
      Amazingly, it does compile. I believe the declaration that looks as though it shouldn't (because T1 isn't defined) compiles as a function pointer declaration, where the first T1 is the name of the variable defined and the second is, in syntactic terms, the name of the function. With the typedef commented out, you can delete the second T1 on that line. Note that the type of a variable defaults to int in C, so you can write 'const a' instead of 'const int a'. The return type of a function also defaults to int.
      - saagarjha 8y ago
        Clang accepts it, but GCC does not. I suspect there's a bug here.
hevi_jos 8y ago
C is extremely simple. In fact is one of the few languages that you could manage to understand completely in the sense of knowing exactly what it does. C macros on the other hand, should die. I use C a lot but never ever use c macros, they are evil. Extremely hard to debug, confusing and very weak. When we want macros, we use Lisp, that have proper macros.
- bitt 8y ago
  I'm not sure of all the valid use cases for macros, but I think they are useful when you need to do something simple. For example, a debug flag to run some code like verbose logging but you don't want to include that in the release binary. C# has preprocessor directives but I wish that java had something similar. I guess this is different than complex micros though.

xtacy 8y ago

FWIW, this magic is how the Linux kernel implements generic linked lists, hash tables, and red-black trees: https://stackoverflow.com/questions/15832301/understanding-container-of-macro-in-the-linux-kernel https://stackoverflow.com/questions/15832301/understanding-c...

paavoova 8y ago
So this would be hashing the pointer? In which case it doesn't support keys, like strings, etc. I'm now wondering if this is the more common use case for hash tables, where you just need a reference to a unique object rather than a specific key.
- taeric 8y ago
  Java has IdentityHashMap for this use. I hesitate to claim it is more common.
- xtacy 8y ago
  No, that's not true. The insert function (hash, rbtree, etc.) takes a hash node as an argument. So, in the kernel implementation the caller is expected to hash. EDIT: check out some examples to see for yourself: https://elixir.bootlin.com/linux/latest/ident/hlist_add_head https://elixir.bootlin.com/linux/latest/ident/hlist_add_head

eatbitseveryday 8y ago

This is exactly how the list implementation in the Linux kernel works [1]. I've extracted this header file and used it in user-space before, too. The cool trick is in calculating an offset to the start of the struct containing the link. But I do not think this trick or list implementation is newly introduced in Wayland. It existed at least as far back as kernel 2.6.11 [2]. [1] https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/list.h?h=v5.0-rc8 https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin... [2] https://elixir.bootlin.com/linux/v2.6.11/source/include/linux/list.h https://elixir.bootlin.com/linux/v2.6.11/source/include/linu...

fmela 8y ago
I've seen this same trick done with macros in BSD kernel code from the 80s!
- electrum 8y ago
  Here's the code from FreeBSD: https://github.com/freebsd/freebsd/blob/master/sys/sys/queue.h https://github.com/freebsd/freebsd/blob/master/sys/sys/queue...
  - deleted 8y ago
    [deleted]
eps 8y ago
This is an exceedingly common way of using containers in C, because how fast and predictable it is during the run-time. It also allows putting a single data item into multiple containers like that. It's used pretty much in every OS kernel, Windows included.
buserror 8y ago
I've been using queue.h from bsd for as long as I can remember. It's slightly different syntax, but it's available on linux, from userland, and is not GPL... Note that the one that ships in linux is pretty simple, the one that is in BSD is a lot more complete.

yesenadam 8y ago

Spelling: "it's" should be "its" except when short for "it is" I believe. i.e. >It’s a simple doubly linked list. Here’s it’s definition The first one's right, the second should be its. Though almost most native speakers seem to do this, so I guess it won't be 'wrong' for much longer...

Foober223 8y ago
FYI some people were taught to use an apostrophe to imply ownership. It used to be the "official" way, but no longer. The gorilla guards it's bananas.
- pascal_cuoq 8y ago
  And if we are talking about several gorillas, they guard they're bananas. It makes sense now, thanks.
- yesenadam 8y ago
  >It used to be the "official" way Oh right, thank you, I didn't know the history. Short version: https://www.merriam-webster.com/words-at-play/the-tangled-history-of-its-and-its https://www.merriam-webster.com/words-at-play/the-tangled-hi... Did you mean, some people now alive were taught that "it's" is right (in "it's definition"), or just ownership generally (Harry's). Well, it's better than using apostrophes for plural's, which seems very common too.

CoolGuySteve 8y ago

2 things concerning wl_list: 1) In C++ you can use struct inheritance to get the same functionality without macros or templates. ie: struct ThingList : wl_list { /* data elements */ } 2) Like in the C++ case above, the next and prev elements should probably be at the top if you plan on iterating a lot since the next/prev pointers will be in the first cacheline that you load when you dereference previous list elem. In this case, it's also worth allocating list nodes with posix_memalign. OTOH, there might be reasons why you want the list buried deep in the struct, like if the other data element access times are more important.

ploxiln 8y ago
You can do something similar in C - make struct wl_list the first member of struct data, and just cast the wl_list node pointer to a data pointer (offsetof is zero). I think the most common reason for this generic-location offset-of style is so that the struct data can have multiple list nodes and be on multiple lists (without any extra allocation). This is pretty common in the kernel.
eps 8y ago
Re: #1 - Now try and place Thing on two lists, a map and a hash table or a combination of thereof. No way to do this cleanly in C++. At best, it's going to be an iterator galore, at worst some boost-style frankencode.

roel_v 8y ago

Oh but this is only the beginning. With boost MPL, you can do full metaprogramming at preprocessing time (I'm not 100% sure but I think the C++ preprocessor is compatible with that of C? So that would make MPL applicable to C code as well.). You can generate code by iterating over lists of preprocessor 'variables' and do other crazy things that seem impossible the first few times you think about it. It's great, albeit a little bit confusing the next time you come back to it, because it makes you think more about what level you're metaprogramming at.

jjtheblunt 8y ago
The C preprocessor wouldn't balk at "char template;" but that of C++ ?
gpderetta 8y ago
I think you mean the Boost Preprocessor Library. MPL is template based and quite a bit dated by today's standards. C++ Preprocessor is pretty much the same as C (they might go formally out of sync from o e standard release to another but in practice compilers implement the same features as far as I know).

AJRF 8y ago

From Objective-C, you can make switch statements support strings with 6 lines of macro: ifndef TTD_SWITCH_STRING #define TTD_SWITCH_STRING #define TTD_CASE(str) if ([__s__ isEqualToString:(str)]) #define TTD_SWITCH(s) for (NSString *__s__ = (s); ; ) #define TTD_DEFAULT #endif

AnaniasAnanas 8y ago
This is quite cool, that being said, you would need to add a break at least at the end to that, unlike a regular switch. Plus it would not work in the case that you want multiple strings to lead to the same code
burfog 8y ago
Somebody, please just fix the language. Extend all the free compilers or, better yet, run the changes through the standards committee. People have been dying for this feature for over half a century. While you're at it, just make the feature generic. Handle arbitrary arrays, structs, unions, and floating-point types. The ... feature supported by gcc is also a huge usability improvement. Don't allow weird sorting order issues with strings. Don't allow it for structs and unions.
- unwind 8y ago
  None of those types can be compared directly in C, so that's not making the feature "generic", it's making it magically super-powered. Associating comparison intelligence with arbitrary types is not very obvious how to do in C, but I guess the new super-switch could accept a function pointer in addition to the data, or something. Like: const char * s const = "bar"; switch (s, strcmp) { case "foo": printf("I got foo\n"); break; case "bar": printf("nopes, I got bar\n"); break; default: printf("neither foo nor bar :/\n"); } Which would be fine/acceptable, but not exactly how C tends to roll.
  - glouwbug 8y ago
    Why not just use an enum for the switch, and if strings need to reflect the enum, use an xmacro to expand the enum into an array of strings? https://github.com/glouw/andvaranaut/blob/master/src/Theme.c https://github.com/glouw/andvaranaut/blob/master/src/Theme.c

ogoffart 8y ago

> Maybe that’s the reason people who use the C language love it so much. You can’t do that in any other language. But you can't do it in C. __typeof__ is a GNU extension. > Note that wl_list is not a very safe data structure, in the sense that a programmer need to know exactly how to use it. You can do it in C++ with template, and it would be type safe.

twtw 8y ago
typeof is a GNU extension, but it (or an equivalent) is implemented in every compiler anyone actually uses. You can do it in C, you just can't do it in the part of C the standards committee has decided to standardize. I'm not sure what the value is of defining C as standard C when loads of software has shipped for decades using this pattern.
- comex 8y ago
  ...with the notable exception of MSVC.
  - Gibbon1 8y ago
    I wouldn't call MSVC a C compiler until more recently.
    - fdgdfgdfg 8y ago
      Recent studies suggest now happened roughly recently.
- taneq 8y ago
  And there you have it. Purists claim C or C++ can't do X because it's UBH in the standard. Pragmatists know that C and (especially) C++ aren't languages on their own, while "gcc" and "MSVC++" are complete (and very similar) languages.
  - adrianN 8y ago

AnaniasAnanas 8y ago

> You can’t do that in any other language. Except languages with parametric polymorphism, such as ML and Haskell.

0db532a0 8y ago
Or C++ and Java.
rkangel 8y ago
Not quite right, in other languages you (a) can't, and (b) don't have to (thankfully). The compiler doing my offsetting for me using type information is much safer and more reliable.

trulyrandom 8y ago

These sorts of macro tricks are cute, but they quickly become a pain when using an FFI.

openloop 8y ago

I like it.

RustyRussell 8y ago

As others have pointed out, this is also used in the Linux kernel. But unfortunately it shares the kernel error of using the same type for list head and member. That's not good separation, and on particular it means list_add() is ambiguous (the kernel one is member, head, which is backwards). Hence I recommend kernel refugees start with CCAN's list: http://ccodearchive.net/info/list.html http://ccodearchive.net/info/list.html

pdkl95 8y ago

wl_list seems like an incomplete re-implementation of the LIST_ macros in <sys/queue.h>. http://man7.org/linux/man-pages/man3/queue.3.html http://man7.org/linux/man-pages/man3/queue.3.html https://github.com/freebsd/freebsd/blob/master/sys/sys/queue.h https://github.com/freebsd/freebsd/blob/master/sys/sys/queue...

0db532a0 8y ago
It isn’t, at least directly. I am actually really happy to see this alternative, as queue.h uses anonymous structs, which are C11 and not well supported.

okl 8y ago

Macro-based, non-intrusive data structures: https://gitlab.com/oliver117/ucds/tree/master/src https://gitlab.com/oliver117/ucds/tree/master/src

scoutt 8y ago

Could be a catch that while this kind of constructs work OK for local lists, you have to be aware when passing the struct between applications or processes compiled with different packing but using the same struct definition with non-aligned members. struct foo { uint8_t data[3]; struct wl_list link; }; For an application link member may be at offset 3 while for another it would be at offset 4. That may be the reason link should be put as the first member, and a simple cast would let you walk the list.

AstralStorm 8y ago
Usually it does not matter as you keep items of the same type or know the type and exact compiler. Unless you want to write them somewhere or put it as part of API and ABI. Which you probably shouldn't.
- scoutt 8y ago
  It's true that types has something to do with it, but the main issue is padding. While I can keep the same type (i.e. uint8_t), it's the padding following uint8_t var[3] that may vary according on packing options when compiling. http://www.catb.org/esr/structure-packing/#_structure_alignment_and_padding http://www.catb.org/esr/structure-packing/#_structure_alignm...

colinfinck 8y ago

This implementation of doubly linked lists is not even exclusive to Unix-based operating systems, but also known as struct LIST_ENTRY under Windows/ReactOS and heavily used for kernel development there. They also provide a singly linked list version as struct SINGLE_LIST_ENTRY. Check e.g. https://docs.microsoft.com/en-us/windows/desktop/api/ntdef/ns-ntdef-_list_entry https://docs.microsoft.com/en-us/windows/desktop/api/ntdef/n... and https://git.reactos.org/?p=reactos.git&a=search&h=HEAD&st=grep&s=LIST_ENTRY https://git.reactos.org/?p=reactos.git&a=search&h=HEAD&st=gr...

AstralStorm 8y ago

Intrusive lists. A trick probably as old as C itself. Multiple libraries provide an equivalent in C++. The claim that you can only do that unsafely or need C "magic" is completely wrong. The safe implementations are not even slower, as the main gain is node cache locality.

tiehuis 8y ago

A comparable implementation in Zig. Key detail is `@fieldParentPtr` [1], which has the same functionality as `container_of`. const std = @import("std"); const wl_list = struct { prev: *wl_list, next: *wl_list, fn init(list: *wl_list) void { list.prev = list; list.next = list; } fn insert(list: *wl_list, elem: *wl_list) void { elem.prev = list; elem.next = list.next; list.next = elem; elem.next.prev = elem; } }; const Data = struct { data: i32, link: wl_list, fn init(data: i32) Data { return Data{ .data = data, .link = undefined, }; } }; pub fn main() void { var foo_list: wl_list = undefined; foo_list.init(); var e1 = Data.init(1); var e2 = Data.init(2); var e3 = Data.init(3); foo_list.insert(&e1.link); foo_list.insert(&e2.link); e2.link.insert(&e3.link); var entry = @fieldParentPtr(Data, "link", foo_list.next); while (&entry.link != &foo_list) : (entry = @fieldParentPtr(Data, "link", entry.link.next)) { std.debug.warn("{}\n", entry.data); } } [1] https://ziglang.org/documentation/master/#fieldParentPtr https://ziglang.org/documentation/master/#fieldParentPtr

baby 8y ago

I avoid anything magic in C.

antirez 8y ago

An alternative could be to guarantee that the first two elements of the data structure are next and prev pointers. This way the implementation can just assume the first 8 or 16 bytes (depending on sizeof(void*)) are the next/prev addresses. Then the same set of functions can work with everything that looks like a linked list. Another option is to have a "struct list" that contains the information needed, and the API allows, when you initialize the list, to say how much space you want starting at "node->data". This way the node is always over-allocated by the library, and when you want to manipulate the list items you cast node->data to your privata data structure.

emersion 8y ago
This approach is less type-safe.
- antirez 8y ago
  Yep.
aidenn0 8y ago
If wl_list was required to be the first member of the struct, the wl_container_of() FLM becomes trivial. This implementation comes from the kernel though, where a single item might be in multiple lists.

floatboth 8y ago

Rust magic: https://github.com/Amanieu/intrusive-rs https://github.com/Amanieu/intrusive-rs

mlthoughts2018 8y ago

C macro magic? Run.

rkangel 8y ago

An alternative implementation is to put the link structure at the beginning of the data structure. Then converting between one and the other is just a cast between the two types. This is a fairly standard technique in C to get some version of inheritance of structs, and how I have implement LLs in the past. I don't see what this extra complexity of sizeof() offset calculations gains you.

tom_ 8y ago
It allows the object to be part of multiple lists.
- rkangel 8y ago
  That's an excellent point, thanks.
potiuper 8y ago
More importantly offsetof is an implementation-specific macro. Whatever it does cannot be generalized from its definition for one or many compilers to a language requirement. The use of the offsetof macro in a program may cause undefined behavior when compiled with GCC or Clang. GCC instead provides __builtin_offsetof. If multiple lists are desired, then an array of them should be declared at the head of the struct and the index be fixed to the type of list desired to contain a reference to the struct. Additionally, as rustyrussell wrote in another comment the list head and member structs should be different in order to optimize the list struct as CCAN's list is implemented, but it too uses offsetof, which leads to the same issue of undefined behavior. Ref: https://en.wikipedia.org/wiki/Offsetof https://en.wikipedia.org/wiki/Offsetof https://stackoverflow.com/questions/26906621/does-struct-name-null-b-cause-undefined-behaviour-in-c11 https://stackoverflow.com/questions/26906621/does-struct-nam...
- rkangel 8y ago
  This is not true. offsetof is defined in the C standard. See http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf, Section 7.17, point 3 on page 254. I prefer not to use it due to the loss of type information and the potential for screwups, but you can write ANSI portable C using it.

magicseth 8y ago

I've used uthash in the past for a similar hash implementation. It certainly has its wrinkles, i.e. you may need to include several if you want to include an object in multiple hashes... but it was fun to use and straightforward! https://troydhanson.github.io/uthash/ https://troydhanson.github.io/uthash/

gowld 8y ago

This is C's version a Ruby-style Mixin. By adding a List link to your datatype, you can use List operations on your data. https://en.wikipedia.org/wiki/Mixin https://en.wikipedia.org/wiki/Mixin Also, is this macro magic, or simply memory layout magic? The macros look like appreviations for readability, not magic required to make the structure work.

sfilargi 8y ago

Just because you can, doesn't mean you should. Unless you are hacking the linux kernel, use a type safe language folks.