/* List Utilities -- header * Copyright (C) 2009 Chris Hall (GMCH), Highwayman * * This file is part of GNU Zebra. * * GNU Zebra is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License as published by the * Free Software Foundation; either version 2, or (at your option) any * later version. * * GNU Zebra is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * * You should have received a copy of the GNU General Public License * along with GNU Zebra; see the file COPYING. If not, write to the Free * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA * 02111-1307, USA. */ #ifndef _ZEBRA_LIST_UTIL_H #define _ZEBRA_LIST_UTIL_H #include /* Macro in case there are particular compiler issues. */ #ifndef Inline #define Inline static inline #endif /*------------------------------------------------------------------------------ * Note that the following fell foul of "strict-aliasing": * * #define ssl_del_head(base, next) \ * ssl_del_head_func_i((void**)&(base), _lu_off(base, next)) * * Inline void* * ssl_del_head_func_i(void** p_base, size_t link_offset) * { * void* item = *p_base ; * * if (item != NULL) * *p_base = _sl_next(item, link_offset) ; * * return item ; * } ; * * the assignment to *p_base is, apparently, unacceptable. This works * perfectly well as am ordinary function. Using a GNUC extension it is * possible to avoid the function call... hence the ugly skips. */ #ifdef __GNUC__ #define __GNUC__LIST_UTIL #endif /*============================================================================== * These utilities provide for linked lists of items, where the list pointers * are fields in the items. * * This is a little less general that the linklist stuff, but carries less * overhead. * * The items will be structures of some sort, and are described here as being * of type "struct item". Pointers to those items will be of type * "struct item*". * * Most of these utilities are implemented as macros. * *------------------------------------------------------------------------------ * Links and Bases. * * For a singly linked list, the item declaration is straightforward: * * struct item * { * .... * struct item* foo_next ; * .... * } * * The item can live on more than one list, all that is required is that each * list has its next pointer. * * For double linked lists, the item may be declared: * * struct item * { * .... * struct dl_list_pair(struct item*) foo_list ; * .... * } ; * * A single base is straighforward: * * struct item* foo_base ; * * and that may be a variable or a structure field. * * A double base may be declared: * * struct dl_base_pair(struct item*) foo_base ; * * Various ways to construct structures or structure types: * * typedef struct dl_list_pair(struct foo*) foo_list ; * * struct foo_list dl_list_pair(struct foo*) ; * * struct foo_base dl_base_pair(struct foo*) ; */ #define dl_list_pair(ptr_t) { ptr_t next ; ptr_t prev ; } #define dl_base_pair(ptr_t) { ptr_t head ; ptr_t tail ; } struct dl_void_list_pair list_pair(void*) ; struct dl_void_base_pair base_pair(void*) ; #define _lu_off(obj, field) ((char*)&((obj)->field) - (char*)(obj)) /*============================================================================== * Single Base, Single Link * * To delete entry must chase down list to find it. * * Supports: * * ssl_init(base) -- initialise base * * An empty list has a NULL base. * * ssl_push(base, item, next) -- add at head of list * * Treat as void function. The item may *not* be NULL. * * Undefined if item is already on any list (including this one). * * ssl_del(base, item, next) -- delete from list * * Treat as function returning int. Does nothing if the item is NULL. * * Returns: 0 => OK -- removed item from list (OR item == NULL) * -1 => item not found on list * * ssl_del_head(base, next) -- delete head of list * * Treat as void function. Does nothing if the list is empty. * * ssl_pop(&dst, base, next) -- pop head of list, if any * * Treat as function returning void*. * * Returns old head in dst and as return from "function". * * Returns NULL and sets dst == NULL if list is empty. * * ssl_head(base) -- return head of list * * Treat as function returning void*. * * ssl_next(item, next) -- step to next item, if any * * Treat as function returning void*. Returns NULL if item is NULL. * * Note that ssl_del() and ssl_pop() do NOT affect the item->next pointer. * * Where: * * "base" to be an r-value of type struct item* * * "item" to be an l-value of type struct item* * * "dst" to be an r-value of type struct item* * * "next" to be the name of a field in struct item, with type struct item* * *------------------------------------------------------------------------------ * For example: * * struct item // definition for list items * { * ... * struct item* bar_next ; * ... * } ; * * static struct item* bar_base ; // declaration of the list base * * // create item and add to list (adds at front) * struct item* q = calloc(1, sizeof(struct item)) ; * ssl_push(bar_base, q, bar_next) ; * * // remove item from list * ssl_del(bar_base, q, bar_next) ; * * // walk a list * struct item* t = ssl_head(bar_base) ; * while (t != NULL) * { * .... * t = ssl_next(t, bar_next) ; * } * * // walk and empty out a list -- removing item before processing * struct item* t ; * while (ssl_pop(&t, bar_base, bar_next) != NULL) * { * .... // t points to old head of list * } * * // walk and empty out a list -- removing after processing * struct item* t ; * while ((t = ssl_head(bar_base) != NULL) * { * .... * ssl_del_head(bar_base, bar_next) ; * } * * And for example: * * struct parent_item // parent structure containing list * { * .... * struct item* bar_base ; * .... * } * * void footle(struct parent_item* parent, struct item* item) * { * .... * ssl_push(parent->bar_base, item, bar_next) ; * .... * } */ #define ssl_init(base) \ ((base) = NULL) #define ssl_push(base, item, next) \ do { (item)->next = (base) ; \ (base) = item ; \ } while (0) extern int ssl_del_func(void* p_this, void* obj, size_t link_offset) __attribute__((noinline)) ; #define ssl_del(base, item, next) \ ssl_del_func((void*)(&base), item, _lu_off(item, next)) #define ssl_del_head(base, next) \ do { if ((base) != NULL) \ (base) = (base)->next ; \ } while (0) #define ssl_pop(dst, base, next) \ ((*(dst) = (base)) != NULL ? ((base) = (base)->next, *(dst)) : NULL) #define ssl_head(base) (base) #define ssl_next(item, next) \ ((item) != NULL ? (item)->next : NULL) /* _sl_p_next(item, off) -- pointer to next pointer at given offset * _sl_next(item, off) -- contents of next pointer at given offset */ #define _sl_p_next(item, off) \ ( (char*)(item) + (off) ) #define _sl_next(item, off) \ *(void**)_sl_p_next(item, off) /*============================================================================== * Single Base, Double Link * * Can delete entry directly. * * Supports: * * sdl_init(base) -- initialise base * * An empty list has a NULL base. * * sdl_push(base, item, list) -- add at head of list * * Treat as void function. The item may *not* be NULL. * * Undefined if item is already on any list (including this one). * * sdl_del(base, item, list) -- delete from list * * Treat as void function. Does nothing if the item is NULL. * * Undefined if item is not on the list. * * sdl_del_head(base, next) -- delete head of list * * Treat as void function. Does nothing if the list is empty. * * sdl_pop(&dst, base, next) -- pop head of list, if any * * Treat as function returning void*. * * Returns old head in dst and as return from "function". * * Returns NULL and sets dst == NULL if list is empty. * * sdl_head(base) -- return head of list * * Treat as function returning void*. * * sdl_next(item, next) -- step to next item, if any * * Treat as function returning void*. Returns NULL if the item is NULL. * * sdl_prev(item, next) -- step to prev item, if any * * Treat as function returning void*. Returns NULL if the item is NULL. * * Note that sdl_del() and sdl_pop() do NOT affect the item->list.next * or item->list.prev pointers. * * Where: * * "base" to be an r-value of type: struct base_pair(struct item*)* * * That is... a variable or field which is a pointer to * * "item" to be an l-value of type struct item* * * "dst" to be an r-value of type struct item* * * "list" to be the name of a field in struct item * of type: struct list_pair(struct item*) * *------------------------------------------------------------------------------ * For example: * * struct item // definition for list items * { * ... * struct list_pair(struct item*) bar_list ; * ... * } ; * * static struct base_pair(struct item*) bar_base ; * // declaration of the list base * * // create item and add to list (adds at front) * struct item* q = calloc(1, sizeof(struct item)) ; * sdl_push(bar_base, q, bar_list) ; * * // remove item from list * sdl_del(bar_base, q, bar_list) ; * * // walk a list * struct item* t = sdl_head(bar_base) ; * while (t != NULL) * { * .... * t = sdl_next(t, bar_list) ; * } * * // walk and empty out a list -- removing item before processing * struct item* t ; * while (sdl_pop(&t, bar_base, bar_list) != NULL) * { * .... // t points to old head of list * } * * // walk and empty out a list -- removing after processing * struct item* t ; * while ((t = sdl_head(bar_base) != NULL) * { * .... * sdl_del_head(bar_base, bar_list) ; * } * * And for example: * * struct parent_item // parent structure containing list * { * .... * struct base_pair(struct item*) bar_base ; * .... * } * * void footle(struct parent_item* parent, struct item* item) * { * .... * sdl_push(parent->bar_base, item, bar_list) ; * .... * } */ #define sdl_init(base) \ ((base) = NULL) #define sdl_push(base, item, list) \ do { confirm(_lu_off(base, list.next) == _lu_off(item, list.next)) ; \ confirm(_lu_off(base, list.prev) == _lu_off(item, list.prev)) ; \ (item)->list.next = (base) ; \ (item)->list.prev = NULL ; \ if ((base) != NULL) \ (base)->list.prev = (item) ; \ (base) = (item) ; \ } while (0) #define sdl_del(base, item, list) \ do { confirm(_lu_off(base, list.next) == _lu_off(item, list.next)) ; \ confirm(_lu_off(base, list.prev) == _lu_off(item, list.prev)) ; \ if ((item) != NULL) \ { \ if ((item)->list.next != NULL) \ (item)->list.next->list.prev = (item)->list.prev ; \ if ((item)->list.prev != NULL) \ (item)->list.prev->list.next = (item)->list.next ; \ else \ (base) = (item)->list.next ; \ } ; \ } while (0) #define sdl_del_head(base, list) \ do { if ((base) != NULL) \ { \ (base) = (base)->list.next ; \ if ((base) != NULL) \ (base)->list.prev = NULL ; \ } \ } while (0) #define sdl_pop(dst, base, list) \ ((*(dst) = (base)) != NULL \ ? ( ((base) = (base)->list.next) != NULL \ ? ( (base)->list.prev = NULL, *(dst) ) : *(dst) ) : NULL) #define sdl_head(base) (base) #define sdl_next(item, list) \ ((item) != NULL ? (item)->list.next : NULL) #define sdl_prev(item, list) \ ((item) != NULL ? (item)->list.prev : NULL) /* _dl_p_next(obj, off) -- pointer to next pointer at given offset * _dl_next(obj, off) -- contents of next pointer at given offset * _dl_p_prev(obj, off) -- pointer to prev pointer at given offset * _dl_prev(obj, off) -- contents of prev pointer at given offset */ #define _dl_p_next(obj, off) \ ( (void**)( (char*)(obj) + (off) + 0 ) ) #define _dl_next(obj, off) \ *_dl_p_next(obj, off) #define _dl_p_prev(obj, off) \ ( (void**)( (char*)(obj) + (off) _ sizeof(void*) ) ) #define _dl_prev(obj, off) \ *_dl_p_next(obj, off) /*============================================================================== * Double Base, Double Link * * Can delete entry directly. Can insert and remove at tail. * * Supports: * * ddl_init(base) -- initialise base * * An empty list has *both* head and tail pointers NULL. * * NB: confusion will arise if only one of these pointers is NULL. * * ddl_push(base, item, list) -- insert at head of list * * Treat as void function. The item may *not* be NULL. * * Undefined if item is already on any list (including this one). * * ddl_append(base, item, list) -- insert at tail of list * * Treat as void function. The item may *not* be NULL. * * Undefined if item is already on any list (including this one). * * ddl_in_after(after, base, item, list) -- insert after * * Treat as void function. The after & item may *not* be NULL. * * Undefined if item is already on any list (including this one), or if * after is not on the list. * * ddl_in_before(before, base, item, list) -- insert before * * Treat as void function. The before & item may *not* be NULL. * * Undefined if item is already on any list (including this one), or if * before is not on the list. * * ddl_pop(&dst, base, next) -- pop head of list, if any * * Treat as function returning void*. * * Returns old head in dst and as return from "function". * * Returns NULL and sets dst == NULL if list is empty. * * ddl_crop(&dst, base, next) -- crop tail of list, if any * * Treat as function returning void*. * * Returns old head in dst and as return from "function". * * Returns NULL and sets dst == NULL if list is empty. * * ddl_del(base, item, list) -- delete from list * * Treat as void function. Does nothing if the item is NULL. * * Undefined if item is not on the list. * * ddl_del_head(base, next) -- delete head of list * * Treat as void function. Does nothing if the list is empty. * * ddl_del_tail(base, next) -- delete tail of list * * Treat as void function. Does nothing if the list is empty. * * ddl_head(base) -- return head of list * * Treat as function returning void*. * * ddl_tail(base) -- return tail of list * * Treat as function returning void*. * * ddl_next(item, next) -- step to next item, if any * * Treat as function returning void*. Returns NULL if the item is NULL. * * ddl_prev(item, next) -- step to prev item, if any * * Treat as function returning void*. Returns NULL if the item is NULL. * * Note that ddl_del() and ddl_pop() do NOT affect the item->list.next * or item->list.prev pointers. * * Where: * * "base" to be an r-value of type: struct base_pair(struct item*)* * * That is... a variable or field which is a pointer to * * "item" to be an l-value of type struct item* * * "dst" to be an r-value of type struct item* * * "list" to be the name of a field in struct item * of type: struct list_pair(struct item*) * * * *------------------------------------------------------------------------------ * For example: * * struct item // definition for list items * { * ... * struct list_pair(struct item*) bar_list ; * ... * } ; * * static struct base_pair(struct item*) bar_base ; * // declaration of the list base * * // create item and add to list (adds at front) * struct item* q = calloc(1, sizeof(struct item)) ; * ddl_push(bar_base, q, bar_list) ; * * // remove item from list * ddl_del(bar_base, q, bar_list) ; * * // walk a list * struct item* t = ddl_head(bar_base) ; * while (t != NULL) * { * .... * t = ddl_next(t, bar_list) ; * } * * // walk and empty out a list -- removing item before processing * struct item* t ; * while (ddl_pop(&t, bar_base, bar_list) != NULL) * { * .... // t points to old head of list * } * * // walk and empty out a list -- removing after processing * struct item* t ; * while ((t = ddl_head(bar_base) != NULL) * { * .... * ddl_del_head(bar_base, bar_list) ; * } * * And for example: * * struct parent_item // parent structure containing list * { * .... * struct base_pair(struct item*) bar_base ; * .... * } * * void footle(struct parent_item* parent, struct item* item) * { * .... * ddl_push(parent->bar_base, item, bar_list) ; * .... * } */ #define ddl_init(base) \ ((base).head = (base).tail = NULL) #define ddl_push(base, item, list) \ do { (item)->list.next = (base).head ; \ (item)->list.prev = NULL ; \ if ((base).head != NULL) \ (base).head->list.prev = (item) ; \ else \ (base).tail = (item) ; \ (base).head = (item) ; \ } while (0) #define ddl_append(base, item, list) \ do { (item)->list.next = NULL ; \ (item)->list.prev = (base).tail ; \ if ((base).tail != NULL) \ (base).tail->list.next = (item) ; \ else \ (base).head = (item) ; \ (base).tail = (item) ; \ } while (0) #define ddl_in_after(after, base, item, list) \ do { (item)->list.next = (after)->list.next ; \ (item)->list.prev = (after) ; \ if ((after)->list.next != NULL) \ (after)->list.next->list.prev = (item) ; \ else \ (base).tail = (item) ; \ (after)->list.next = (item) ; \ } while (0) #define ddl_in_before(before, base, item, list) \ do { (item)->list.next = (before) ; \ (item)->list.prev = (before)->list.prev ; \ if ((before)->list.prev != NULL) \ (before)->list.prev->list.next = (item) ; \ else \ (base).head = (item) ; \ (before)->list.prev = (item) ; \ } while (0) #define ddl_del(base, item, list) \ do { if ((item) != NULL) \ { \ if ((item)->list.next != NULL) \ (item)->list.next->list.prev = (item)->list.prev ; \ else \ (base).tail = (item)->list.prev ; \ if ((item)->list.prev != NULL) \ (item)->list.prev->list.next = (item)->list.next ; \ else \ (base).head = (item)->list.next ; \ } ; \ } while (0) #define ddl_del_head(base, list) \ do { if ((base).head != NULL) \ { \ (base).head = (base).head->list.next ; \ if ((base).head != NULL) \ (base).head->list.prev = NULL ; \ else \ (base).tail = NULL ; \ } \ } while (0) #define ddl_del_tail(base, list) \ do { if ((base).tail != NULL) \ { \ (base).tail = (base).tail->list.prev ; \ if ((base).tail != NULL) \ (base).tail->list.next = NULL ; \ else \ (base).head = NULL ; \ } \ } while (0) #define ddl_pop(dst, base, list) \ ((*(dst) = (base).head) != NULL \ ? ( ((base).head = (base).head->list.next) != NULL \ ? ( (base).head->list.prev = NULL, *(dst) ) \ : ( (base).tail = NULL, *(dst) ) ) \ : NULL) #define ddl_crop(dst, base, list) \ ((*(dst) = (base).tail) != NULL \ ? ( ((base).tail = (base).tail->list.prev) != NULL \ ? ( (base).tail->list.next = NULL, *(dst) ) \ : ( (base).head = NULL, *(dst) ) ) \ : NULL) #define ddl_head(base) ((base).head) #define ddl_tail(base) ((base).tail) #define ddl_next(item, list) \ ((item) != NULL ? (item)->list.next : NULL) #define ddl_prev(item, list) \ ((item) != NULL ? (item)->list.prev : NULL) #endif /* _ZEBRA_LIST_UTIL_H */