2

I am implementing a stack that does not require memory allocation and can take any struct as long as it embeds a special struct. Similar to GNU's List implementation.

The struct that any struct must embed to work in the stack is:

struct stack_elem {
  struct stack_elem *next;
};

The struct that I would like to be used with the stack is:

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

So the stack would look like this:

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

I am writing a macro called stack_entry to convert the embedded elem struct to its container node struct. Here's what I've tried so far. stack_entry will be used as follows:

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

stack_entry will take a pointer to the stack_elem, the type of the node to be converted to and the name of the member field of the element in that node. I tried several ways to do it but none work. I realized that STACK_ELEM points to the next item and so I tried just subtracting the offset of elem from struct node and that did not work. Here are a few things I tried that did not work either:

#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)))

What would be the correct arithmetic? Why isn't subtracting the offset of next, hence the offset of elem, yielding node if its the last element in the struct?

GNU List list_entry macro is defined as:

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

How does this work? Why is next involved in here when its supposed to grab the container struct within the same node, and not the next one?

4

2 に答える 2

3

GNUlist_entryは、構造体の先頭からフィールドまでのオフセットをnextフィールドのアドレスから差し引くことによって機能しnextます。実際にはnextポインターを逆参照しません。Linux ソースには、これに使用される一般的なマクロがありcontainer_of、これが役立つ場合があります。リンクされた記事はかなり有益です。

を定義しようとする 2 回目の試みでstack_entry、間違ったオフセットを差し引いています (GNUlist_entryマクロと比較してください)。

于 2012-07-10T18:59:32.980 に答える
1

あなたの実装は実際にはスタックではなく、データ構造が任意のサイズを持つことができるかどうかに応じて、単一リンクリストまたはベクトルです。

参考までに：

  • 要素が同じサイズの場合、なぜ次のポインターが必要なのですか。それらはすべて互いに同じオフセットにあるべきではありませんか? 構造体のサイズが 16 バイトであるとします。最初の要素はアドレスベースにあり、次の要素はアドレスベース + 16にあり、n番目の要素はベース + (n-1) * 16にあります (それをベクトルと呼びます)

  • データ構造が任意のサイズの場合、次の 2 つのものが必要です。それがどのオブジェクトであるかを見つけるための魔法と、次のポインターがどこにあるのかを示す固定オフセットです。2 つの良いヒント:

そして、あなたにとって最良のこと: それはすでに他の誰かによって実装されています: あなたは を使用することができ#include <sys/queue.h>ますSLIST。

于 2012-07-11T01:44:05.540 に答える