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