c - 类型检查标记指针

问题描述

上周我在玩一个带螺纹的后缀树。树太大，无法使用递归进行遍历，我之前已经以各种方式解决了这个问题——使用显式堆栈、延续，你可以命名它——这次我添加了来自所有节点的线程指针，所以我可以遍历树，一路上没有任何额外的分配。

节点的基本结构是

struct node
{
    // more data here...
    struct node *child;
    tagged_ptr sibling;
};

wheretagged_ptr是一个指针，struct node但最低位用于指示它是指向真正的兄弟姐妹还是指向祖先的兄弟姐妹，遍历将在遍历子树后进行。

这个想法是你可以遍历一个（子）树，只需遵循一个child或sibling指针：

static inline struct node *next(struct node *n)
{
    return n->child ? n->child : tp_pointer(n->sibling);
}

...
    struct node *sentinel = tp_pointer(n->sibling);
    for (; n != sentinel; n = next(n))
        // do stuff wit n

（哨兵是您在看到的整个子树后返回的位置n），或者您可以在向下搜索树时仅遍历节点的子节点，使用

static inline struct node *next_sibling(struct node *n)
{
    return tp_is_taggged(n->sibling) ? 0 : tp_pointer(n->sibling);
}

...

    for (struct node *child = n->child;
         child;
         child = next_sibling(child))
        // do something with child...

对于这个想法，我需要能够区分真正的兄弟指针和线程指针。至少我是这么认为的，否则我还没有弄清楚如何通过真正的孩子来识别自己。

这就是标记指针的用武之地。对齐struct node大于一

_Static_assert(_Alignof(struct node) > 1,
               "Nodes must have alignment higher than one.");

所以最低有效位是免费的，我可以利用它。我以前用过几次，得到一个标记指针并不难。它可能是这样的：

typedef uintptr_t tagged_ptr;
static inline tagged_ptr tp_set(tagged_ptr tp)        { return tp | 1; }
static inline tagged_ptr tp_unset(tagged_ptr tp)      { return tp & ~1; }
static inline void *     tp_pointer(tagged_ptr tp)    { return (void *)tp_unset(tp); }
static inline bool       tp_is_taggged(tagged_ptr tp) { return tp & 1; }
static inline tagged_ptr tag_ptr(void *ptr, bool tag) { return (tagged_ptr)ptr | tag; }

只是让我感到困扰的是，我用这种方法丢弃了所有类型信息。我使用类型uintptr_t而不是，struct node *所以我不会意外地跟随带有标签的指针，但就类型安全而言。没有什么能阻止我将标记指针设置为struct node *两个指向int *.

当然，在这个应用程序中，这不是什么大问题。只有一种标记指针，我可以确保转换为正确的类型。无论如何，我需要一些转换来获取指针中的位。但是我想知道如果您想要更多的类型安全性，使用通用标记指针可以走多远。

我可以得到一部分的方式。我可以定义记住它们的类型的标记指针，并且我可以确保您只为它们分配正确类型的指针。使用指针和的联合uintptr_t，我确保您不能分配错误时间的指针：

#define tagged_ptr(T)                                            \
    _Static_assert(sizeof(T *) == sizeof(uintptr_t),             \
                   "Pointer type must match size of uintptr_t"); \
    union {                                                      \
        T *ptr;                                                  \
        uintptr_t bits;                                          \
    }

#define tp_set(TP, P, TAG)      \
    do                          \
    {                           \
        (TP).ptr = P;           \
        (TP).bits |= ((TAG)&1); \
    } while (0)

#define tp_tag(TP) \
    ((TP).bits & 1)

现在您可以声明不同类型的标记指针，并且可以分配给它们并标记它们，但只能使用正确类型的指针。

struct foo
{
    int a, b;
    tagged_ptr(struct foo) t;
};
_Static_assert(_Alignof(struct foo) > 1,
               "Least significant bit must be free for tags.");
_Static_assert(_Alignof(int) > 1,
               "Least significant bit must be free for tags.");

...


    struct foo *x = malloc(sizeof *x);
    tp_set(x->t, x, 1);
    assert(tp_tag(x->t) == 1);

    int i = 42;
    tagged_ptr(int) tip;
    tp_set(tip, &i, 0);
    assert(tp_tag(tip) == 0);

    //tp_set(x->t, &i, 0); // error
    //tp_set(tip, x, 0);   // error

但是，如果不使用编译器扩展，我无法取回指针。

如果我有，__typeof__我可以这样做：

#define tp_ptr(TP) \
    ((__typeof__((TP).ptr))((TP).bits & ~1))

它从标记的指针中获取类型并返回它，从而使类型检查器保持在循环中。

如果我没有__typeof__但我有 GCC 的语句表达式，我可以提供类型，创建一个新的标记指针，我可以在其中屏蔽位，检查指针的类型，屏蔽并返回：

#define tp_ptr(T, TP)                        \
    ({ tagged_ptr(T) tp;                     \
       tp.ptr = (TP).ptr;  /* checks type */ \
       tp.bits &= ~1;                        \
       tp.ptr; })

在提取指针时是否有更便携的方法来保留类型信息，即一种在不完全丢弃类型信息的情况下屏蔽最后一位的方法？当然，我必须强制转换以获得位，但我可以保留类型并使用上述两种方法进行转换。它们只需要编译器扩展，因此它们不符合标准。

我意识到在这里选择标准 C 解决方案有点愚蠢，考虑到第二个我开始摆弄指针中的位，我已经离开了可移植性并输入了实现/未定义的行为，但是以这种方式使用低位很可能比编译器扩展工作更多的地方，我很好奇是否有办法做到这一点。

我并不严格需要它，只是让我烦恼的是我不知道该怎么做。我很想知道它不能完成，或者知道如何去做。两者都同样适合我。不知道困扰着我。

标签： cpointers

c - 类型检查标记指针

问题描述

解决方案

推荐阅读