如何通过将最后一位设置为 1 来“标记”指针？

Question

我正在尝试标记和取消标记指针，以便我可以实现非阻塞链表。我检查过在我的体系结构上从未使用过最后一位，因此我尝试使用更改它来标记/取消标记指针。

我正在尝试执行 OR 将最后一位设置为 1，执行 AND 来取消设置它，执行 AND 来检查它是否设置为 1。问题是，当我对指针执行按位（注释的宏）操作时，我无法取消引用它。即使指针的整数值是正确的，取消引用它也会导致分段错误。

更具体地说，这#define unmark(x) (x & (uintptr_t) 0xfffffffe)就是导致分段错误的原因。如果我不使用它（而是使用它#define unmark(x) x - 1），程序就可以工作。

递增和递减指针似乎有效，但它可能会使解决方案架构变得特定。这是因为在我的架构上，指针总是以 8 结尾，最后一位设置为 0。如果不是这种情况，我的解决方案将不是很可移植。

我知道操作指针可能无论如何都不可移植，但这是该算法所必需的。如果有人知道导致问题的原因，那就太棒了。

这是我用来测试解决方案的代码：

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

//This produces segfault, for some reason
//#define unmark(x)     (x & (uintptr_t) 0xfffffffe)
//#define mark(x)   (x | (uintptr_t) 0x00000001)
#define is_marked(x)    ((long) x & 0x00000001)

#define mark(x)     x + 1
#define unmark(x)   x - 1

struct Example {
     long x;
     long y;
};

int main() {
    struct Example *x = malloc(sizeof(struct Example));
    x->x = 10;
    x->y = 20;
    uintptr_t p = (uintptr_t)(void*) x;

    printf("%ld\n", ((struct Example *) (void*) p)->y);

    printf("%04x\n", p);
    printf("Is marked: %d\n", is_marked(p));

    p = mark(p);
    printf("%04x\n", p);
    printf("Is marked: %d\n", is_marked(p));

    p = unmark(p);
    printf("%04x\n", p);
    printf("Is marked: %d\n", is_marked(p));

    printf("%ld\n", ((struct Example *) (void*) p)->y);

    return 0;
}

Answer 1

代码有很多问题

不只清除最低有效位

x & (uintptr_t) 0xfffffffe假设uintptr_t是32位。更好的是

 #define unmark(x)  ((x) & ~(uintptr_t)1)
 // or 
 #define unmark(x)  (((x) | 1) ^ 1)

假设指针的位操作是可以的

说明符不匹配

// printf("%04x\n", p);
printf("%04jx\n", (uintmax_t) p);

// printf("Is marked: %d\n", is_marked(p));
// Unclear correct specifier.

更好的是

// #define is_marked(x)    ((long) x & 0x00000001)
#define is_marked(x)    (!!((x) & 1))

不需要的演员表

//#define mark(x)   (x | (uintptr_t) 0x00000001)
#define mark(x)   ((x) | 1)