linklist.c 6.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362
  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. struct listnode *
  134. listnode_add_before (struct list *list, struct listnode *pp, void *val)
  135. {
  136. struct listnode *nn;
  137. assert (val != NULL);
  138. nn = listnode_new ();
  139. nn->data = val;
  140. if (pp == NULL)
  141. {
  142. if (list->tail)
  143. list->tail->next = nn;
  144. else
  145. list->head = nn;
  146. nn->prev = list->tail;
  147. nn->next = pp;
  148. list->tail = nn;
  149. }
  150. else
  151. {
  152. if (pp->prev)
  153. pp->prev->next = nn;
  154. else
  155. list->head = nn;
  156. nn->prev = pp->prev;
  157. nn->next = pp;
  158. pp->prev = nn;
  159. }
  160. list->count++;
  161. return nn;
  162. }
  163. /* Move given listnode to tail of the list */
  164. void
  165. listnode_move_to_tail (struct list *l, struct listnode *n)
  166. {
  167. LISTNODE_DETACH(l,n);
  168. LISTNODE_ATTACH(l,n);
  169. }
  170. /* Delete specific date pointer from the list. */
  171. void
  172. listnode_delete (struct list *list, void *val)
  173. {
  174. struct listnode *node;
  175. assert(list);
  176. for (node = list->head; node; node = node->next)
  177. {
  178. if (node->data == val)
  179. {
  180. if (node->prev)
  181. node->prev->next = node->next;
  182. else
  183. list->head = node->next;
  184. if (node->next)
  185. node->next->prev = node->prev;
  186. else
  187. list->tail = node->prev;
  188. list->count--;
  189. listnode_free (node);
  190. return;
  191. }
  192. }
  193. }
  194. /* Return first node's data if it is there. */
  195. void *
  196. listnode_head (struct list *list)
  197. {
  198. struct listnode *node;
  199. assert(list);
  200. node = list->head;
  201. if (node)
  202. return node->data;
  203. return NULL;
  204. }
  205. /* Delete all listnode from the list. */
  206. void
  207. list_delete_all_node (struct list *list)
  208. {
  209. struct listnode *node;
  210. struct listnode *next;
  211. assert(list);
  212. for (node = list->head; node; node = next)
  213. {
  214. next = node->next;
  215. if (list->del)
  216. (*list->del) (node->data);
  217. listnode_free (node);
  218. }
  219. list->head = list->tail = NULL;
  220. list->count = 0;
  221. }
  222. /* Delete all listnode then free list itself. */
  223. void
  224. list_delete (struct list *list)
  225. {
  226. assert(list);
  227. list_delete_all_node (list);
  228. list_free (list);
  229. }
  230. /* Lookup the node which has given data. */
  231. struct listnode *
  232. listnode_lookup (struct list *list, void *data)
  233. {
  234. struct listnode *node;
  235. assert(list);
  236. for (node = listhead(list); node; node = listnextnode (node))
  237. if (data == listgetdata (node))
  238. return node;
  239. return NULL;
  240. }
  241. /* Delete the node from list. For ospfd and ospf6d. */
  242. void
  243. list_delete_node (struct list *list, struct listnode *node)
  244. {
  245. if (node->prev)
  246. node->prev->next = node->next;
  247. else
  248. list->head = node->next;
  249. if (node->next)
  250. node->next->prev = node->prev;
  251. else
  252. list->tail = node->prev;
  253. list->count--;
  254. listnode_free (node);
  255. }
  256. /* ospf_spf.c */
  257. void
  258. list_add_node_prev (struct list *list, struct listnode *current, void *val)
  259. {
  260. struct listnode *node;
  261. assert (val != NULL);
  262. node = listnode_new ();
  263. node->next = current;
  264. node->data = val;
  265. if (current->prev == NULL)
  266. list->head = node;
  267. else
  268. current->prev->next = node;
  269. node->prev = current->prev;
  270. current->prev = node;
  271. list->count++;
  272. }
  273. /* ospf_spf.c */
  274. void
  275. list_add_node_next (struct list *list, struct listnode *current, void *val)
  276. {
  277. struct listnode *node;
  278. assert (val != NULL);
  279. node = listnode_new ();
  280. node->prev = current;
  281. node->data = val;
  282. if (current->next == NULL)
  283. list->tail = node;
  284. else
  285. current->next->prev = node;
  286. node->next = current->next;
  287. current->next = node;
  288. list->count++;
  289. }
  290. /* ospf_spf.c */
  291. void
  292. list_add_list (struct list *l, struct list *m)
  293. {
  294. struct listnode *n;
  295. for (n = listhead (m); n; n = listnextnode (n))
  296. listnode_add (l, n->data);
  297. }