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