linklist.c 5.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316
  1. /* Generic linked list routine.
  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. #include <zebra.h>
  22. #include "linklist.h"
  23. #include "memory.h"
  24. /* Allocate new list. */
  25. struct list *
  26. list_new (void)
  27. {
  28. return XCALLOC (MTYPE_LINK_LIST, sizeof (struct list));
  29. }
  30. /* Free list. */
  31. void
  32. list_free (struct list *l)
  33. {
  34. XFREE (MTYPE_LINK_LIST, l);
  35. }
  36. /* Allocate new listnode. Internal use only. */
  37. static struct listnode *
  38. listnode_new (void)
  39. {
  40. return XCALLOC (MTYPE_LINK_NODE, sizeof (struct listnode));
  41. }
  42. /* Free listnode. */
  43. static void
  44. listnode_free (struct listnode *node)
  45. {
  46. XFREE (MTYPE_LINK_NODE, node);
  47. }
  48. /* Add new data to the list. */
  49. void
  50. listnode_add (struct list *list, void *val)
  51. {
  52. struct listnode *node;
  53. assert (val != NULL);
  54. node = listnode_new ();
  55. node->prev = list->tail;
  56. node->data = val;
  57. if (list->head == NULL)
  58. list->head = node;
  59. else
  60. list->tail->next = node;
  61. list->tail = node;
  62. list->count++;
  63. }
  64. /*
  65. * Add a node to the list. If the list was sorted according to the
  66. * cmp function, insert a new node with the given val such that the
  67. * list remains sorted. The new node is always inserted; there is no
  68. * notion of omitting duplicates.
  69. */
  70. void
  71. listnode_add_sort (struct list *list, void *val)
  72. {
  73. struct listnode *n;
  74. struct listnode *new;
  75. assert (val != NULL);
  76. new = listnode_new ();
  77. new->data = val;
  78. if (list->cmp)
  79. {
  80. for (n = list->head; n; n = n->next)
  81. {
  82. if ((*list->cmp) (val, n->data) < 0)
  83. {
  84. new->next = n;
  85. new->prev = n->prev;
  86. if (n->prev)
  87. n->prev->next = new;
  88. else
  89. list->head = new;
  90. n->prev = new;
  91. list->count++;
  92. return;
  93. }
  94. }
  95. }
  96. new->prev = list->tail;
  97. if (list->tail)
  98. list->tail->next = new;
  99. else
  100. list->head = new;
  101. list->tail = new;
  102. list->count++;
  103. }
  104. void
  105. listnode_add_after (struct list *list, struct listnode *pp, void *val)
  106. {
  107. struct listnode *nn;
  108. assert (val != NULL);
  109. nn = listnode_new ();
  110. nn->data = val;
  111. if (pp == NULL)
  112. {
  113. if (list->head)
  114. list->head->prev = nn;
  115. else
  116. list->tail = nn;
  117. nn->next = list->head;
  118. nn->prev = pp;
  119. list->head = nn;
  120. }
  121. else
  122. {
  123. if (pp->next)
  124. pp->next->prev = nn;
  125. else
  126. list->tail = nn;
  127. nn->next = pp->next;
  128. nn->prev = pp;
  129. pp->next = nn;
  130. }
  131. list->count++;
  132. }
  133. /* Delete specific date pointer from the list. */
  134. void
  135. listnode_delete (struct list *list, void *val)
  136. {
  137. struct listnode *node;
  138. assert(list);
  139. for (node = list->head; node; node = node->next)
  140. {
  141. if (node->data == val)
  142. {
  143. if (node->prev)
  144. node->prev->next = node->next;
  145. else
  146. list->head = node->next;
  147. if (node->next)
  148. node->next->prev = node->prev;
  149. else
  150. list->tail = node->prev;
  151. list->count--;
  152. listnode_free (node);
  153. return;
  154. }
  155. }
  156. }
  157. /* Return first node's data if it is there. */
  158. void *
  159. listnode_head (struct list *list)
  160. {
  161. struct listnode *node;
  162. assert(list);
  163. node = list->head;
  164. if (node)
  165. return node->data;
  166. return NULL;
  167. }
  168. /* Delete all listnode from the list. */
  169. void
  170. list_delete_all_node (struct list *list)
  171. {
  172. struct listnode *node;
  173. struct listnode *next;
  174. assert(list);
  175. for (node = list->head; node; node = next)
  176. {
  177. next = node->next;
  178. if (list->del)
  179. (*list->del) (node->data);
  180. listnode_free (node);
  181. }
  182. list->head = list->tail = NULL;
  183. list->count = 0;
  184. }
  185. /* Delete all listnode then free list itself. */
  186. void
  187. list_delete (struct list *list)
  188. {
  189. assert(list);
  190. list_delete_all_node (list);
  191. list_free (list);
  192. }
  193. /* Lookup the node which has given data. */
  194. struct listnode *
  195. listnode_lookup (struct list *list, void *data)
  196. {
  197. struct listnode *node;
  198. assert(list);
  199. for (node = listhead(list); node; node = listnextnode (node))
  200. if (data == listgetdata (node))
  201. return node;
  202. return NULL;
  203. }
  204. /* Delete the node from list. For ospfd and ospf6d. */
  205. void
  206. list_delete_node (struct list *list, struct listnode *node)
  207. {
  208. if (node->prev)
  209. node->prev->next = node->next;
  210. else
  211. list->head = node->next;
  212. if (node->next)
  213. node->next->prev = node->prev;
  214. else
  215. list->tail = node->prev;
  216. list->count--;
  217. listnode_free (node);
  218. }
  219. /* ospf_spf.c */
  220. void
  221. list_add_node_prev (struct list *list, struct listnode *current, void *val)
  222. {
  223. struct listnode *node;
  224. assert (val != NULL);
  225. node = listnode_new ();
  226. node->next = current;
  227. node->data = val;
  228. if (current->prev == NULL)
  229. list->head = node;
  230. else
  231. current->prev->next = node;
  232. node->prev = current->prev;
  233. current->prev = node;
  234. list->count++;
  235. }
  236. /* ospf_spf.c */
  237. void
  238. list_add_node_next (struct list *list, struct listnode *current, void *val)
  239. {
  240. struct listnode *node;
  241. assert (val != NULL);
  242. node = listnode_new ();
  243. node->prev = current;
  244. node->data = val;
  245. if (current->next == NULL)
  246. list->tail = node;
  247. else
  248. current->next->prev = node;
  249. node->next = current->next;
  250. current->next = node;
  251. list->count++;
  252. }
  253. /* ospf_spf.c */
  254. void
  255. list_add_list (struct list *l, struct list *m)
  256. {
  257. struct listnode *n;
  258. for (n = listhead (m); n; n = listnextnode (n))
  259. listnode_add (l, n->data);
  260. }