Jak używać listy z sys / queue.h?

Question

Jak używać listy z sys / queue.h?

Obecnie zaimplementowałem pojedynczo linkowaną listę, tak:

struct PeerNode {
     struct Peer* cargo;
     struct PeerNode* next;
};

...i mam strukturę, która zawiera kilka tych połączonych list, jak tak:

struct Torrent {
     ...
     struct PeerNode* peer_list;
     struct PeerNode* unchoked_peers;
     ...
}

Chciałbym zastąpić to za pomocą makr dostarczonych przez sys/queue.h. Domyślam się, że mógłbym zastąpić mój kod czymś takim:

struct Torrent {
     ...
     LIST_ENTRY(PeerNode, Peer) peer_list;
     struct PeerNode* unchoked_peers;
     ...
}

Potem, patrząc na man queue, myślę, że zainicjalizowałbym listy robiąc coś takiego:

LIST_INIT(&peer_list);
LIST_INIT(unchoked_peers);

Jednak nie rozumiem jak LIST_ENTRY czynniki do wykorzystania listy. Ze strony man jest napisane: "makro LIST_ENTRY deklaruje strukturę, która łączy elementy na liście", ale nie bardzo rozumiem, co to oznacza.

Dlaczego chciałbym zadeklarować strukturę do łączenia elementów na liście? Czy każdy węzeł nie powinien być połączony z następnym węzłem za pomocą wskaźnika, tak jak moja początkowa implementacja listy połączonej? Jak zastąpić moje listy połączone implementacją dostarczoną przez sys/queue.h? Jak wstawić element do listy?

20

linux c list bsd

Author: rps, 2011-10-02

Source

1 answers

score 29 · Accepted Answer

LIST_ENTRY tworzy pola do umieszczenia w Twojej strukturze, które są odpowiednie do łączenia elementów, więc nie musisz się martwić o specyfikę tych wskaźników.

struct foo {
    int a, b, c;
    /* This is instead of "struct foo *next" */
    LIST_ENTRY(foo) pointers;
};

Aby utworzyć listę należy użyć LIST_HEAD ():

struct Torrent {
    LIST_HEAD(foo_list, foo) bar;
};

Możesz zainicjować nagłówek listy używając LIST_INIT ():

struct Torrent t;
LIST_INIT(&t.bar);

Możesz wstawiać elementy używając makr LIST_INSERT_* ():

struct foo *item = malloc(sizeof(struct foo));
LIST_INSERT_HEAD(&t.bar, item, pointers);

To wszystko zostało wzięte z przykładu listy na stronach podręcznika w http://www.manpagez.com/man/3/queue/

Dla pełnego przykładu: http://www.ideone.com/T1EID