Задумываясь о цели tqe_prev TAILQ, не указывая на предыдущий узел

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_prev указывая tqe_next предыдущего узла? Если бы это был я, я бы имел tqe_prev, непосредственно указывающий на предыдущий узел, похожий на tqe_next, указывающий на следующий узел.

Одна из причин, по которой я буду думать, когда мы вставляем узел, мы непосредственно работаем над обновляемым указателем, нам не нужно сначала проходить через его собственный узел. Но так ли это? Любые другие преимущества?

Мне интересно, как мы можем путешествовать в обратном направлении от очереди? Когда у нас есть указатель на узел, поскольку его 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 это адрес a .tqe_next слот в пределах struct node. Мы передаем этот адрес (unsigned char *), чтобы мы могли выполнить арифметику указателя по очереди. Мы вычтем смещение (байт) .tqe_next в структуре struct node (offsetof с макросъемкой <stddef.h>). Это дает нам адрес начала структуры struct node, который мы, наконец, приводим в нужный тип.