以前のノードを指していないTAILQのtqe_prevの目的を熟考

Question

sys/queue.hには、データ構造TAILQが定義されています。 Linuxカーネル全体で広く普及しています。その定義は、このようなものです：

私は少し、このコードで困惑しています

#define TAILQ_ENTRY(type)            \ 
struct {                \ 
     struct type *tqe_next; /* next element */      \ 
     struct type **tqe_prev; /* address of previous next element */ \ 
} 

：前のノードのtqe_nextを指しtqe_prev持つことの利点は何ですか？それが私だったら、次のノードを指すtqe_nextと同様に、直前のノードを直接指し示すtqe_prevを持っていました。

私はノードを挿入するときにポインタを直接操作して更新することを考えているので、最初にノードを所有する必要はありません。しかし、それは？その他の利点は？

私はキューの後ろをどのように移動できるのでしょうか？ノードへのポインタがある場合、そのtqe_prevは前のノードを指していないので、先頭までキューを通過する方法はありません。または、そのような後方移動はTAILQによってサポートされていない設計によるものですか？

Answer 1

ああ、面白いです。このテクニックが他のユーザーを抱えていることはわかりませんでした。

このようにする理由は、「前のノード」が存在しない可能性があるということです。最初の要素には前任者がなく、それを指すポインターがあります。

これは、いくつかの操作を簡略化します。たとえば、あなたはそれへのポインタのみ与えられたノードを削除したい場合は、あなたがこれを行うことができます：

：あなたは前のノードへのポインタを持っていた場合

void delete(struct node *p) { 
    *p->tqe_prev = p->tqe_next; 
    if (p->tqe_next) { 
     p->tqe_next->tqe_prev = p->tqe_prev; 
    } 
    free(p); 
} 

、あなたはこれを書く必要があるだろう

void delete(struct node *p) { 
    if (p->tqe_prev) { 
     p->tqe_prev->tqe_next = p->tqe_next; 
    } else { 
     ??? 
    } 
    if (p->tqe_next) { 
     p->tqe_next->tqe_prev = p->tqe_prev; 
    } 
    free(p); 
} 

...しかし、あなたは固まっています：???の部分は、リストのルートがわからなくても書き込めません。

同様の議論がinsert操作に適用されます。

---

逆方向のトラバースは実際にこの種の構造にとって優先順位ではありません。

#include <stddef.h> 

struct node *prev(struct node *p) { 
    return (struct node *)((unsigned char *)p->tqe_prev - offsetof(struct node, tqe_next)); 
} 

我々はp->tqe_prevがのアドレスであることを知っている：しかし、それは（しかし、あなたがルートではないことを確実に知る場合にのみ、あなたが実際に前のノードがある知っているIE）でなければならない場合に行うことができますstruct node内の.tqe_nextスロット。このアドレスを(unsigned char *)にキャストするので、バイステップポインタ演算を実行できます。我々は、struct node構造（offsetofマクロの礼儀<stddef.h>）内の.tqe_nextの（バイト）オフセットを引く。これにより、struct node構造体の先頭のアドレスが与えられ、最終的に正しい型にキャストされます。