Annotation of embedaddon/quagga/lib/linklist.c, revision 1.1
1.1 ! misho 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. */
! 28: struct list *
! 29: list_new (void)
! 30: {
! 31: return XCALLOC (MTYPE_LINK_LIST, sizeof (struct list));
! 32: }
! 33:
! 34: /* Free list. */
! 35: void
! 36: list_free (struct list *l)
! 37: {
! 38: XFREE (MTYPE_LINK_LIST, l);
! 39: }
! 40:
! 41: /* Allocate new listnode. Internal use only. */
! 42: static struct listnode *
! 43: listnode_new (void)
! 44: {
! 45: return XCALLOC (MTYPE_LINK_NODE, sizeof (struct listnode));
! 46: }
! 47:
! 48: /* Free listnode. */
! 49: static void
! 50: listnode_free (struct listnode *node)
! 51: {
! 52: XFREE (MTYPE_LINK_NODE, node);
! 53: }
! 54:
! 55: /* Add new data to the list. */
! 56: void
! 57: listnode_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: */
! 83: void
! 84: listnode_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:
! 125: void
! 126: listnode_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:
! 163: /* Delete specific date pointer from the list. */
! 164: void
! 165: listnode_delete (struct list *list, void *val)
! 166: {
! 167: struct listnode *node;
! 168:
! 169: assert(list);
! 170: for (node = list->head; node; node = node->next)
! 171: {
! 172: if (node->data == val)
! 173: {
! 174: if (node->prev)
! 175: node->prev->next = node->next;
! 176: else
! 177: list->head = node->next;
! 178:
! 179: if (node->next)
! 180: node->next->prev = node->prev;
! 181: else
! 182: list->tail = node->prev;
! 183:
! 184: list->count--;
! 185: listnode_free (node);
! 186: return;
! 187: }
! 188: }
! 189: }
! 190:
! 191: /* Return first node's data if it is there. */
! 192: void *
! 193: listnode_head (struct list *list)
! 194: {
! 195: struct listnode *node;
! 196:
! 197: assert(list);
! 198: node = list->head;
! 199:
! 200: if (node)
! 201: return node->data;
! 202: return NULL;
! 203: }
! 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:
! 212: assert(list);
! 213: for (node = list->head; node; node = next)
! 214: {
! 215: next = node->next;
! 216: if (list->del)
! 217: (*list->del) (node->data);
! 218: listnode_free (node);
! 219: }
! 220: list->head = list->tail = NULL;
! 221: list->count = 0;
! 222: }
! 223:
! 224: /* Delete all listnode then free list itself. */
! 225: void
! 226: list_delete (struct list *list)
! 227: {
! 228: assert(list);
! 229: list_delete_all_node (list);
! 230: list_free (list);
! 231: }
! 232:
! 233: /* Lookup the node which has given data. */
! 234: struct listnode *
! 235: listnode_lookup (struct list *list, void *data)
! 236: {
! 237: struct listnode *node;
! 238:
! 239: assert(list);
! 240: for (node = listhead(list); node; node = listnextnode (node))
! 241: if (data == listgetdata (node))
! 242: return node;
! 243: return NULL;
! 244: }
! 245:
! 246: /* Delete the node from list. For ospfd and ospf6d. */
! 247: void
! 248: list_delete_node (struct list *list, struct 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 */
! 263: void
! 264: list_add_node_prev (struct list *list, struct listnode *current, void *val)
! 265: {
! 266: struct listnode *node;
! 267:
! 268: assert (val != NULL);
! 269:
! 270: node = listnode_new ();
! 271: node->next = current;
! 272: node->data = val;
! 273:
! 274: if (current->prev == NULL)
! 275: list->head = node;
! 276: else
! 277: current->prev->next = node;
! 278:
! 279: node->prev = current->prev;
! 280: current->prev = node;
! 281:
! 282: list->count++;
! 283: }
! 284:
! 285: /* ospf_spf.c */
! 286: void
! 287: list_add_node_next (struct list *list, struct listnode *current, void *val)
! 288: {
! 289: struct listnode *node;
! 290:
! 291: assert (val != NULL);
! 292:
! 293: node = listnode_new ();
! 294: node->prev = current;
! 295: node->data = val;
! 296:
! 297: if (current->next == NULL)
! 298: list->tail = node;
! 299: else
! 300: current->next->prev = node;
! 301:
! 302: node->next = current->next;
! 303: current->next = node;
! 304:
! 305: list->count++;
! 306: }
! 307:
! 308: /* ospf_spf.c */
! 309: void
! 310: list_add_list (struct list *l, struct list *m)
! 311: {
! 312: struct listnode *n;
! 313:
! 314: for (n = listhead (m); n; n = listnextnode (n))
! 315: listnode_add (l, n->data);
! 316: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>