lib/linklist.h

   1 /* Generic linked list
   2  * Copyright (C) 1997, 2000 Kunihiro Ishiguro
   3  *
   4  * This file is part of GNU Zebra.
   5  *
   6  * GNU Zebra is free software; you can redistribute it and/or modify it
   7  * under the terms of the GNU General Public License as published by the
   8  * Free Software Foundation; either version 2, or (at your option) any
   9  * later version.
  10  *
  11  * GNU Zebra is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with GNU Zebra; see the file COPYING.  If not, write to the Free
  18  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  19  * 02111-1307, USA.
  20  */
  21
  22 #ifndef _ZEBRA_LINKLIST_H
  23 #define _ZEBRA_LINKLIST_H
  24
  25 /* listnodes must always contain data to be valid. Adding an empty node
  26  * to a list is invalid
  27  */
  28 struct listnode
  29 {
  30   struct listnode *next;
  31   struct listnode *prev;
  32
  33   /* private member, use getdata() to retrieve, do not access directly */
  34   void *data;
  35 };
  36
  37 struct list
  38 {
  39   struct listnode *head;
  40   struct listnode *tail;
  41
  42   /* invariant: count is the number of listnodes in the list */
  43   unsigned int count;
  44
  45   /*
  46    * Returns -1 if val1 < val2, 0 if equal?, 1 if val1 > val2.
  47    * Used as definition of sorted for listnode_add_sort
  48    */
  49   int (*cmp) (void *val1, void *val2);
  50
  51   /* callback to free user-owned data when listnode is deleted. supplying
  52    * this callback is very much encouraged!
  53    */
  54   void (*del) (void *val);
  55 };
  56
  57 #define listnextnode(X) ((X) ? ((X)->next) : NULL)
  58 #define listhead(X) ((X) ? ((X)->head) : NULL)
  59 #define listtail(X) ((X) ? ((X)->tail) : NULL)
  60 #define listcount(X) ((X)->count)
  61 #define list_isempty(X) ((X)->head == NULL && (X)->tail == NULL)
  62 #define listgetdata(X) (assert((X)->data != NULL), (X)->data)
  63
  64 /* Prototypes. */
  65 extern struct list *list_new(void); /* encouraged: set list.del callback on new lists */
  66 extern void list_free (struct list *);
  67
  68 extern void listnode_add (struct list *, void *);
  69 extern void listnode_add_sort (struct list *, void *);
  70 extern void listnode_add_after (struct list *, struct listnode *, void *);
  71 extern struct listnode *listnode_add_before (struct list *, struct listnode *, void *);
  72 extern void listnode_move_to_tail (struct list *, struct listnode *);
  73 extern void listnode_delete (struct list *, void *);
  74 extern struct listnode *listnode_lookup (struct list *, void *);
  75 extern void *listnode_head (struct list *);
  76
  77 extern void list_delete (struct list *);
  78 extern void list_delete_all_node (struct list *);
  79
  80 /* For ospfd and ospf6d. */
  81 extern void list_delete_node (struct list *, struct listnode *);
  82
  83 /* For ospf_spf.c */
  84 extern void list_add_node_prev (struct list *, struct listnode *, void *);
  85 extern void list_add_node_next (struct list *, struct listnode *, void *);
  86 extern void list_add_list (struct list *, struct list *);
  87
  88 /* List iteration macro.
  89  * Usage: for (ALL_LIST_ELEMENTS (...) { ... }
  90  * It is safe to delete the listnode using this macro.
  91  */
  92 #define ALL_LIST_ELEMENTS(list,node,nextnode,data) \
  93   (node) = listhead(list), ((data) = NULL); \
  94   (node) != NULL && \
  95     ((data) = listgetdata(node),(nextnode) = node->next, 1); \
  96   (node) = (nextnode), ((data) = NULL)
  97
  98 /* read-only list iteration macro.
  99  * Usage: as per ALL_LIST_ELEMENTS, but not safe to delete the listnode Only
 100  * use this macro when it is *immediately obvious* the listnode is not
 101  * deleted in the body of the loop. Does not have forward-reference overhead
 102  * of previous macro.
 103  */
 104 #define ALL_LIST_ELEMENTS_RO(list,node,data) \
 105   (node) = listhead(list), ((data) = NULL);\
 106   (node) != NULL && ((data) = listgetdata(node), 1); \
 107   (node) = listnextnode(node), ((data) = NULL)
 108
 109 /* these *do not* cleanup list nodes and referenced data, as the functions
 110  * do - these macros simply {de,at}tach a listnode from/to a list.
 111  */
 112
 113 /* List node attach macro.  */
 114 #define LISTNODE_ATTACH(L,N) \
 115   do { \
 116     (N)->prev = (L)->tail; \
 117     (N)->next = NULL; \
 118     if ((L)->head == NULL) \
 119       (L)->head = (N); \
 120     else \
 121       (L)->tail->next = (N); \
 122     (L)->tail = (N); \
 123     (L)->count++; \
 124   } while (0)
 125
 126 /* List node detach macro.  */
 127 #define LISTNODE_DETACH(L,N) \
 128   do { \
 129     if ((N)->prev) \
 130       (N)->prev->next = (N)->next; \
 131     else \
 132       (L)->head = (N)->next; \
 133     if ((N)->next) \
 134       (N)->next->prev = (N)->prev; \
 135     else \
 136       (L)->tail = (N)->prev; \
 137     (L)->count--; \
 138   } while (0)
 139
 140 /* Deprecated: 20050406 */
 141 #if !defined(QUAGGA_NO_DEPRECATED_INTERFACES)
 142 #warning "Using deprecated libzebra interfaces"
 143 #define LISTNODE_ADD(L,N) LISTNODE_ATTACH(L,N)
 144 #define LISTNODE_DELETE(L,N) LISTNODE_DETACH(L,N)
 145 #define nextnode(X) ((X) = (X)->next)
 146 #define getdata(X) listgetdata(X)
 147 #define LIST_LOOP(L,V,N) \
 148   for (ALL_LIST_ELEMENTS_RO (L,N,V))
 149 #endif /* QUAGGA_NO_DEPRECATED_INTERFACES */
 150
 151 #endif /* _ZEBRA_LINKLIST_H */