diff options
Diffstat (limited to 'lib/list_util.h')
| -rw-r--r-- | lib/list_util.h | 729 |
1 files changed, 729 insertions, 0 deletions
diff --git a/lib/list_util.h b/lib/list_util.h new file mode 100644 index 00000000..b658c7ce --- /dev/null +++ b/lib/list_util.h @@ -0,0 +1,729 @@ +/* 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 <stddef.h> + +/* 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 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 base_pair(struct item*) foo_base ; + * + * Various ways to construct structures or structure types: + * + * typedef struct list_pair(struct foo*) foo_list ; + * + * struct foo_list list_pair(struct foo*) ; + * + * struct foo_base 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 { confirm(_lu_off(base, next) == _lu_off(item, next)) ; \ + (item)->next = (base) ; \ + (base) = item ; \ + } while (0) + +extern int ssl_del_func(void** p_this, void* obj, size_t link_offset) ; + +#define ssl_del(base, item, next) \ + ssl_del_func((void**)&(base), item, _lu_off(base, 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) \ + ( (void**)( (char*)(item) + (off) ) ) + +#define _sl_next(item, off) \ + *_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 */ |