3 ms·

It looks fun and all, but I really wonder about the implementation and practicality of it in C. But once again, it does look really cool.

by Vlaix 14y ago

nknight 14y ago
It's technically undefined behavior, but in practice it will work perfectly well on almost all C implementations, and in the infinitesimal number of cases where this structure is actually useful, portability isn't a major concern.
- mzl 14y ago
  Just curious, what part of an XOR-linked list is undefined? AFAIK, casting to and from sufficiently wide integers is ok.
  - zurn 14y ago
    I remember hearing claims that a C++ implementation would be allowed to use conservative GC (and nop out free/delete). I wonder what the language lawyers make of this.
    - nuje 14y ago
      What about destructors? I guess only using the GC on destructorless objects could work.
    - nknight 14y ago
      C++ is a lot stricter about a lot of things, and C++11 added some explicit GC-related language, but I have little desire to parse that particular 10MB document. Bjarne covers it in his FAQ, at least: http://www2.research.att.com/~bs/C++0xFAQ.html#gc-abi http://www2.research.att.com/~bs/C++0xFAQ.html#gc-abi
  - nknight 14y ago
    Actually, the behavior is a combination of undefined and implementation defined. To the extent that it's implementation defined, it may still result in nasal demons, but they have to be documented nasal demons. Point is, it's strictly non-portable according to the standard, but when done carefully is unlikely to break on a general-purpose architecture. This is from C99, I don't have a copy of C11: 6.3.2.3 Pointers [...] 5) An integer may be converted to any pointer type. Except as previously specified, the result is implementation-defined, might not be correctly aligned, might not point to an entity of the referenced type, and might be a trap representation.[56]) 6) Any pointer type may be converted to an integer type. Except as previously specified, the result is implementation-defined. If the result cannot be represented in the integer type, the behavior is undefined. The result need not be in the range of values of any integer type. [...] And footnote [56]: The mapping functions for converting a pointer to an integer or an integer to a pointer are intended to be consistent with the addressing structure of the execution environment.

It looks fun and all, but I really wonder about the implementation and practicality of it in C. But once again, it does look really cool.

by Vlaix 14y ago

It looks fun and all, but I really wonder about the implementation and practicality of it in C. But once again, it does look really cool.

nknight 14y ago

It's technically undefined behavior, but in practice it will work perfectly well on almost all C implementations, and in the infinitesimal number of cases where this structure is actually useful, portability isn't a major concern.

mzl 14y ago
Just curious, what part of an XOR-linked list is undefined? AFAIK, casting to and from sufficiently wide integers is ok.
- zurn 14y ago
  I remember hearing claims that a C++ implementation would be allowed to use conservative GC (and nop out free/delete). I wonder what the language lawyers make of this.
  - nuje 14y ago
    What about destructors? I guess only using the GC on destructorless objects could work.
  - nknight 14y ago
    C++ is a lot stricter about a lot of things, and C++11 added some explicit GC-related language, but I have little desire to parse that particular 10MB document. Bjarne covers it in his FAQ, at least: http://www2.research.att.com/~bs/C++0xFAQ.html#gc-abi http://www2.research.att.com/~bs/C++0xFAQ.html#gc-abi
- nknight 14y ago
  Actually, the behavior is a combination of undefined and implementation defined. To the extent that it's implementation defined, it may still result in nasal demons, but they have to be documented nasal demons. Point is, it's strictly non-portable according to the standard, but when done carefully is unlikely to break on a general-purpose architecture. This is from C99, I don't have a copy of C11: 6.3.2.3 Pointers [...] 5) An integer may be converted to any pointer type. Except as previously specified, the result is implementation-defined, might not be correctly aligned, might not point to an entity of the referenced type, and might be a trap representation.[56]) 6) Any pointer type may be converted to an integer type. Except as previously specified, the result is implementation-defined. If the result cannot be represented in the integer type, the behavior is undefined. The result need not be in the range of values of any integer type. [...] And footnote [56]: The mapping functions for converting a pointer to an integer or an integer to a pointer are intended to be consistent with the addressing structure of the execution environment.