2

我正在实现一个不需要内存分配的堆栈，只要它嵌入一个特殊的结构就可以采用任何结构。类似于GNU 的 List实现。

任何结构必须嵌入才能在堆栈中工作的结构是：

struct stack_elem {
  struct stack_elem *next;
};

我想与堆栈一起使用的结构是：

struct node {
  double number;
  char character;
  int isNumber;
  struct stack_elem elem;
};

所以堆栈看起来像这样：

node:            node:
+---------+      +---------+
|number   |      |number   |
+---------+      +---------+
|character|      |character|
+---------+      +---------+
|isNumber |      |isNumber |
+---------+      +---------+
|elem     |      |elem     |
| *next   |----->| *next   |     
+---------+      +---------+ etc....

我正在编写一个宏stack_entry，用于将嵌入式elem结构转换为其容器node结构。这是我到目前为止所尝试的。stack_entry将按如下方式使用：

struct stack_elem *top = peek(&stack);
struct node *converted_node = stack_entry(top, struct node, elem);

stack_entry将采用指向 的指针，stack_elem要转换为的节点的类型以及该节点中元素的成员字段的名称。我尝试了几种方法来做到这一点，但都没有奏效。我意识到这STACK_ELEM指向该next项目，因此我尝试仅减去elemfrom的偏移量struct node，但这不起作用。以下是我尝试过的一些也不起作用的事情：

#define stack_entry(STACK_ELEM, STRUCT, MEMBER)       \
         ((STRUCT *) &(STACK_ELEM) - offsetof (STRUCT, MEMBER))

#define stack_entry(STACK_ELEM, STRUCT, MEMBER)       \
         ((STRUCT *) ((uint8_t *) &(STACK_ELEM)->next \
         - offsetof (STRUCT, MEMBER)))

什么是正确的算术？如果它是结构中的最后一个元素，为什么不减去 的偏移量，从而产生节点next的偏移量？elem

GNU Listlist_entry宏定义为：

#define list_entry(LIST_ELEM, STRUCT, MEMBER)           \
        ((STRUCT *) ((uint8_t *) &(LIST_ELEM)->next     \
                     - offsetof (STRUCT, MEMBER.next)))

这是如何运作的？next当它应该在同一个节点而不是那个节点中获取容器结构时，为什么会涉及到这里next？

4

2 回答 2

3

GNU 的工作原理是从字段的地址中list_entry减去从结构开头到字段的偏移量。它实际上并没有取消引用指针。在 Linux 源代码中有一个用于此的通用宏，称为，您可能会发现它很有帮助。链接的文章信息量很大。nextnextnextcontainer_of

在您第二次尝试定义stack_entry时，您减去了错误的偏移量（将其与 GNUlist_entry宏进行比较）。

于 2012-07-10T18:59:32.980 回答
1

您的实现实际上不是堆栈，而是单链表或向量，具体取决于您的数据结构是否可以具有任意大小。

仅供您参考：

  • why do you need a next pointer if your elements are the same size. shouldn't they all be in the same offset to each other? Assume your structure is of size 16 bytes. the first element will be at address base and the next will be at address base + 16 and the n-th element will be at base + (n-1) * 16 (Then you call it a vector)

  • if your data structures have arbitrary size you need two things: some magic to find out which object it is and a fixed offset to where your next pointer will be. two good hints:

And the best thing for you: it has already been implemented by someone else: you can use #include <sys/queue.h> the SLIST then you just have to take care of on where to put your data.

于 2012-07-11T01:44:05.540 回答