156ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi/* 256ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi * Doubly-linked list 356ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi * Copyright (c) 2009, Jouni Malinen <j@w1.fi> 456ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi * 556ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi * This software may be distributed under the terms of the BSD license. 656ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi * See README for more details. 756ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi */ 856ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi 956ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi#ifndef LIST_H 1056ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi#define LIST_H 1156ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi 1256ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi/** 1356ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi * struct dl_list - Doubly-linked list 1456ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi */ 1556ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivistruct dl_list { 1656ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi struct dl_list *next; 1756ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi struct dl_list *prev; 1856ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi}; 1956ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi 20c75307b73d324d590d0dbc05b44bce9aa89b7145Eric Laurent#define DL_LIST_HEAD_INIT(l) { &(l), &(l) } 21ad3183e2d4cecd02f6261270a7ea1c68be0efa0fFrançois Gaffie 22ad3183e2d4cecd02f6261270a7ea1c68be0efa0fFrançois Gaffiestatic inline void dl_list_init(struct dl_list *list) 2398cc191247388132b6fd8a4ecd07abd6e4c5a0edFrançois Gaffie{ 24ad3183e2d4cecd02f6261270a7ea1c68be0efa0fFrançois Gaffie list->next = list; 25ad3183e2d4cecd02f6261270a7ea1c68be0efa0fFrançois Gaffie list->prev = list; 2656ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi} 2753615e29c99c5e9d2ca77aaefd7bf5c770513120François Gaffie 2853615e29c99c5e9d2ca77aaefd7bf5c770513120François Gaffiestatic inline void dl_list_add(struct dl_list *list, struct dl_list *item) 2953615e29c99c5e9d2ca77aaefd7bf5c770513120François Gaffie{ 3053615e29c99c5e9d2ca77aaefd7bf5c770513120François Gaffie item->next = list->next; 3156ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi item->prev = list; 3256ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi list->next->prev = item; 33c75307b73d324d590d0dbc05b44bce9aa89b7145Eric Laurent list->next = item; 34c75307b73d324d590d0dbc05b44bce9aa89b7145Eric Laurent} 35c75307b73d324d590d0dbc05b44bce9aa89b7145Eric Laurent 36c75307b73d324d590d0dbc05b44bce9aa89b7145Eric Laurentstatic inline void dl_list_add_tail(struct dl_list *list, struct dl_list *item) 3756ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi{ 3856ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi dl_list_add(list->prev, item); 3956ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi} 4056ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi 4156ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivistatic inline void dl_list_del(struct dl_list *item) 4256ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi{ 4356ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi item->next->prev = item->prev; 4456ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi item->prev->next = item->next; 4556ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi item->next = NULL; 4656ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi item->prev = NULL; 4756ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi} 48c75307b73d324d590d0dbc05b44bce9aa89b7145Eric Laurent 49c75307b73d324d590d0dbc05b44bce9aa89b7145Eric Laurentstatic inline int dl_list_empty(struct dl_list *list) 50c75307b73d324d590d0dbc05b44bce9aa89b7145Eric Laurent{ 51c75307b73d324d590d0dbc05b44bce9aa89b7145Eric Laurent return list->next == list; 52c75307b73d324d590d0dbc05b44bce9aa89b7145Eric Laurent} 53c75307b73d324d590d0dbc05b44bce9aa89b7145Eric Laurent 5456ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivistatic inline unsigned int dl_list_len(struct dl_list *list) 5556ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi{ 5656ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi struct dl_list *item; 5756ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi int count = 0; 5853615e29c99c5e9d2ca77aaefd7bf5c770513120François Gaffie for (item = list->next; item != list; item = item->next) 5953615e29c99c5e9d2ca77aaefd7bf5c770513120François Gaffie count++; 60c75307b73d324d590d0dbc05b44bce9aa89b7145Eric Laurent return count; 6153615e29c99c5e9d2ca77aaefd7bf5c770513120François Gaffie} 6253615e29c99c5e9d2ca77aaefd7bf5c770513120François Gaffie 63322b4d25387a04c9afebe998326d005bbdf17edeEric Laurent#ifndef offsetof 64322b4d25387a04c9afebe998326d005bbdf17edeEric Laurent#define offsetof(type, member) ((long) &((type *) 0)->member) 65322b4d25387a04c9afebe998326d005bbdf17edeEric Laurent#endif 66322b4d25387a04c9afebe998326d005bbdf17edeEric Laurent 67322b4d25387a04c9afebe998326d005bbdf17edeEric Laurent#define dl_list_entry(item, type, member) \ 6856ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi ((type *) ((char *) item - offsetof(type, member))) 6956ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi 70c75307b73d324d590d0dbc05b44bce9aa89b7145Eric Laurent#define dl_list_first(list, type, member) \ 7156ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi (dl_list_empty((list)) ? NULL : \ 7256ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi dl_list_entry((list)->next, type, member)) 73c75307b73d324d590d0dbc05b44bce9aa89b7145Eric Laurent 7456ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi#define dl_list_last(list, type, member) \ 75c75307b73d324d590d0dbc05b44bce9aa89b7145Eric Laurent (dl_list_empty((list)) ? NULL : \ 7656ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi dl_list_entry((list)->prev, type, member)) 7756ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi 7856ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi#define dl_list_for_each(item, list, type, member) \ 7956ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi for (item = dl_list_entry((list)->next, type, member); \ 8056ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi &item->member != (list); \ 81c75307b73d324d590d0dbc05b44bce9aa89b7145Eric Laurent item = dl_list_entry(item->member.next, type, member)) 82c75307b73d324d590d0dbc05b44bce9aa89b7145Eric Laurent 83c75307b73d324d590d0dbc05b44bce9aa89b7145Eric Laurent#define dl_list_for_each_safe(item, n, list, type, member) \ 8456ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi for (item = dl_list_entry((list)->next, type, member), \ 85322b4d25387a04c9afebe998326d005bbdf17edeEric Laurent n = dl_list_entry(item->member.next, type, member); \ 8656ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi &item->member != (list); \ 8756ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi item = n, n = dl_list_entry(n->member.next, type, member)) 8856ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi 8956ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi#define dl_list_for_each_reverse(item, list, type, member) \ 9056ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi for (item = dl_list_entry((list)->prev, type, member); \ 9156ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi &item->member != (list); \ 9256ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi item = dl_list_entry(item->member.prev, type, member)) 9356ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi 9456ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi#define DEFINE_DL_LIST(name) \ 9556ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi struct dl_list name = { &(name), &(name) } 9656ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi 9756ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi#endif /* LIST_H */ 9856ec4ffcbae8aeac6c5245fc7b825d02e2e6cefdJean-Michel Trivi