linklist.h 4.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152
  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. #ifndef _ZEBRA_LINKLIST_H
  22. #define _ZEBRA_LINKLIST_H
  23. /* listnodes must always contain data to be valid. Adding an empty node
  24. * to a list is invalid
  25. */
  26. struct listnode
  27. {
  28. struct listnode *next;
  29. struct listnode *prev;
  30. /* private member, use getdata() to retrieve, do not access directly */
  31. void *data;
  32. };
  33. struct list
  34. {
  35. struct listnode *head;
  36. struct listnode *tail;
  37. /* invariant: count is the number of listnodes in the list */
  38. unsigned int count;
  39. /*
  40. * Returns -1 if val1 < val2, 0 if equal?, 1 if val1 > val2.
  41. * Used as definition of sorted for listnode_add_sort
  42. */
  43. int (*cmp) (void *val1, void *val2);
  44. /* callback to free user-owned data when listnode is deleted. supplying
  45. * this callback is very much encouraged!
  46. */
  47. void (*del) (void *val);
  48. };
  49. #define listnextnode(X) ((X) ? ((X)->next) : NULL)
  50. #define listhead(X) ((X) ? ((X)->head) : NULL)
  51. #define listtail(X) ((X) ? ((X)->tail) : NULL)
  52. #define listcount(X) ((X)->count)
  53. #define list_isempty(X) ((X)->head == NULL && (X)->tail == NULL)
  54. #define listgetdata(X) (assert((X)->data != NULL), (X)->data)
  55. /* Prototypes. */
  56. extern struct list *list_new(void); /* encouraged: set list.del callback on new lists */
  57. extern void list_free (struct list *);
  58. extern void listnode_add (struct list *, void *);
  59. extern void listnode_add_sort (struct list *, void *);
  60. extern void listnode_add_after (struct list *, struct listnode *, void *);
  61. extern struct listnode *listnode_add_before (struct list *, struct listnode *, void *);
  62. extern void listnode_move_to_tail (struct list *, struct listnode *);
  63. extern void listnode_delete (struct list *, void *);
  64. extern struct listnode *listnode_lookup (struct list *, void *);
  65. extern void *listnode_head (struct list *);
  66. extern void list_delete (struct list *);
  67. extern void list_delete_all_node (struct list *);
  68. /* For ospfd and ospf6d. */
  69. extern void list_delete_node (struct list *, struct listnode *);
  70. /* For ospf_spf.c */
  71. extern void list_add_node_prev (struct list *, struct listnode *, void *);
  72. extern void list_add_node_next (struct list *, struct listnode *, void *);
  73. extern void list_add_list (struct list *, struct list *);
  74. /* List iteration macro.
  75. * Usage: for (ALL_LIST_ELEMENTS (...) { ... }
  76. * It is safe to delete the listnode using this macro.
  77. */
  78. #define ALL_LIST_ELEMENTS(list,node,nextnode,data) \
  79. (node) = listhead(list), ((data) = NULL); \
  80. (node) != NULL && \
  81. ((data) = listgetdata(node),(nextnode) = node->next, 1); \
  82. (node) = (nextnode), ((data) = NULL)
  83. /* read-only list iteration macro.
  84. * Usage: as per ALL_LIST_ELEMENTS, but not safe to delete the listnode Only
  85. * use this macro when it is *immediately obvious* the listnode is not
  86. * deleted in the body of the loop. Does not have forward-reference overhead
  87. * of previous macro.
  88. */
  89. #define ALL_LIST_ELEMENTS_RO(list,node,data) \
  90. (node) = listhead(list), ((data) = NULL);\
  91. (node) != NULL && ((data) = listgetdata(node), 1); \
  92. (node) = listnextnode(node), ((data) = NULL)
  93. /* these *do not* cleanup list nodes and referenced data, as the functions
  94. * do - these macros simply {de,at}tach a listnode from/to a list.
  95. */
  96. /* List node attach macro. */
  97. #define LISTNODE_ATTACH(L,N) \
  98. do { \
  99. (N)->prev = (L)->tail; \
  100. (N)->next = NULL; \
  101. if ((L)->head == NULL) \
  102. (L)->head = (N); \
  103. else \
  104. (L)->tail->next = (N); \
  105. (L)->tail = (N); \
  106. (L)->count++; \
  107. } while (0)
  108. /* List node detach macro. */
  109. #define LISTNODE_DETACH(L,N) \
  110. do { \
  111. if ((N)->prev) \
  112. (N)->prev->next = (N)->next; \
  113. else \
  114. (L)->head = (N)->next; \
  115. if ((N)->next) \
  116. (N)->next->prev = (N)->prev; \
  117. else \
  118. (L)->tail = (N)->prev; \
  119. (L)->count--; \
  120. } while (0)
  121. /* Deprecated: 20050406 */
  122. #if !defined(QUAGGA_NO_DEPRECATED_INTERFACES)
  123. #warning "Using deprecated libzebra interfaces"
  124. #define LISTNODE_ADD(L,N) LISTNODE_ATTACH(L,N)
  125. #define LISTNODE_DELETE(L,N) LISTNODE_DETACH(L,N)
  126. #define nextnode(X) ((X) = (X)->next)
  127. #define getdata(X) listgetdata(X)
  128. #define LIST_LOOP(L,V,N) \
  129. for (ALL_LIST_ELEMENTS_RO (L,N,V))
  130. #endif /* QUAGGA_NO_DEPRECATED_INTERFACES */
  131. #endif /* _ZEBRA_LINKLIST_H */