lib/linklist.c

   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 along
  17  * with this program; see the file COPYING; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  19  */
  20
  21 #include <zebra.h>
  22 #include <stdlib.h>
  23
  24 #include "linklist.h"
  25 #include "memory.h"
  26
  27 DEFINE_MTYPE_STATIC(LIB, LINK_LIST, "Link List")
  28 DEFINE_MTYPE_STATIC(LIB, LINK_NODE, "Link Node")
  29
  30 struct list *list_new(void)
  31 {
  32         return XCALLOC(MTYPE_LINK_LIST, sizeof(struct list));
  33 }
  34
  35 /* Free list. */
  36 static void list_free_internal(struct list *l)
  37 {
  38         XFREE(MTYPE_LINK_LIST, l);
  39 }
  40
  41 /* Allocate new listnode.  Internal use only. */
  42 static struct listnode *listnode_new(void)
  43 {
  44         return XCALLOC(MTYPE_LINK_NODE, sizeof(struct listnode));
  45 }
  46
  47 /* Free listnode. */
  48 static void listnode_free(struct listnode *node)
  49 {
  50         XFREE(MTYPE_LINK_NODE, node);
  51 }
  52
  53 struct listnode *listnode_add(struct list *list, void *val)
  54 {
  55         struct listnode *node;
  56
  57         assert(val != NULL);
  58
  59         node = listnode_new();
  60
  61         node->prev = list->tail;
  62         node->data = val;
  63
  64         if (list->head == NULL)
  65                 list->head = node;
  66         else
  67                 list->tail->next = node;
  68         list->tail = node;
  69
  70         list->count++;
  71
  72         return node;
  73 }
  74
  75 void listnode_add_head(struct list *list, void *val)
  76 {
  77         struct listnode *node;
  78
  79         assert(val != NULL);
  80
  81         node = listnode_new();
  82
  83         node->next = list->head;
  84         node->data = val;
  85
  86         if (list->head == NULL)
  87                 list->head = node;
  88         else
  89                 list->head->prev = node;
  90         list->head = node;
  91
  92         list->count++;
  93 }
  94
  95 bool listnode_add_sort_nodup(struct list *list, void *val)
  96 {
  97         struct listnode *n;
  98         struct listnode *new;
  99         int ret;
 100
 101         assert(val != NULL);
 102
 103         if (list->cmp) {
 104                 for (n = list->head; n; n = n->next) {
 105                         ret = (*list->cmp)(val, n->data);
 106                         if (ret < 0) {
 107                                 new = listnode_new();
 108                                 new->data = val;
 109
 110                                 new->next = n;
 111                                 new->prev = n->prev;
 112
 113                                 if (n->prev)
 114                                         n->prev->next = new;
 115                                 else
 116                                         list->head = new;
 117                                 n->prev = new;
 118                                 list->count++;
 119                                 return true;
 120                         }
 121                         /* found duplicate return false */
 122                         if (ret == 0)
 123                                 return false;
 124                 }
 125         }
 126
 127         new = listnode_new();
 128         new->data = val;
 129
 130         LISTNODE_ATTACH(list, new);
 131
 132         return true;
 133 }
 134
 135 void listnode_add_sort(struct list *list, void *val)
 136 {
 137         struct listnode *n;
 138         struct listnode *new;
 139
 140         assert(val != NULL);
 141
 142         new = listnode_new();
 143         new->data = val;
 144
 145         if (list->cmp) {
 146                 for (n = list->head; n; n = n->next) {
 147                         if ((*list->cmp)(val, n->data) < 0) {
 148                                 new->next = n;
 149                                 new->prev = n->prev;
 150
 151                                 if (n->prev)
 152                                         n->prev->next = new;
 153                                 else
 154                                         list->head = new;
 155                                 n->prev = new;
 156                                 list->count++;
 157                                 return;
 158                         }
 159                 }
 160         }
 161
 162         new->prev = list->tail;
 163
 164         if (list->tail)
 165                 list->tail->next = new;
 166         else
 167                 list->head = new;
 168
 169         list->tail = new;
 170         list->count++;
 171 }
 172
 173 struct listnode *listnode_add_after(struct list *list, struct listnode *pp,
 174                                     void *val)
 175 {
 176         struct listnode *nn;
 177
 178         assert(val != NULL);
 179
 180         nn = listnode_new();
 181         nn->data = val;
 182
 183         if (pp == NULL) {
 184                 if (list->head)
 185                         list->head->prev = nn;
 186                 else
 187                         list->tail = nn;
 188
 189                 nn->next = list->head;
 190                 nn->prev = pp;
 191
 192                 list->head = nn;
 193         } else {
 194                 if (pp->next)
 195                         pp->next->prev = nn;
 196                 else
 197                         list->tail = nn;
 198
 199                 nn->next = pp->next;
 200                 nn->prev = pp;
 201
 202                 pp->next = nn;
 203         }
 204         list->count++;
 205         return nn;
 206 }
 207
 208 struct listnode *listnode_add_before(struct list *list, struct listnode *pp,
 209                                      void *val)
 210 {
 211         struct listnode *nn;
 212
 213         assert(val != NULL);
 214
 215         nn = listnode_new();
 216         nn->data = val;
 217
 218         if (pp == NULL) {
 219                 if (list->tail)
 220                         list->tail->next = nn;
 221                 else
 222                         list->head = nn;
 223
 224                 nn->prev = list->tail;
 225                 nn->next = pp;
 226
 227                 list->tail = nn;
 228         } else {
 229                 if (pp->prev)
 230                         pp->prev->next = nn;
 231                 else
 232                         list->head = nn;
 233
 234                 nn->prev = pp->prev;
 235                 nn->next = pp;
 236
 237                 pp->prev = nn;
 238         }
 239         list->count++;
 240         return nn;
 241 }
 242
 243 void listnode_move_to_tail(struct list *l, struct listnode *n)
 244 {
 245         LISTNODE_DETACH(l, n);
 246         LISTNODE_ATTACH(l, n);
 247 }
 248
 249 void listnode_delete(struct list *list, const void *val)
 250 {
 251         struct listnode *node = listnode_lookup(list, val);
 252
 253         if (node)
 254                 list_delete_node(list, node);
 255 }
 256
 257 void *listnode_head(struct list *list)
 258 {
 259         struct listnode *node;
 260
 261         assert(list);
 262         node = list->head;
 263
 264         if (node)
 265                 return node->data;
 266         return NULL;
 267 }
 268
 269 void list_delete_all_node(struct list *list)
 270 {
 271         struct listnode *node;
 272         struct listnode *next;
 273
 274         assert(list);
 275         for (node = list->head; node; node = next) {
 276                 next = node->next;
 277                 if (*list->del)
 278                         (*list->del)(node->data);
 279                 listnode_free(node);
 280         }
 281         list->head = list->tail = NULL;
 282         list->count = 0;
 283 }
 284
 285 void list_filter_out_nodes(struct list *list, bool (*cond)(void *data))
 286 {
 287         struct listnode *node;
 288         struct listnode *next;
 289         void *data;
 290
 291         assert(list);
 292
 293         for (ALL_LIST_ELEMENTS(list, node, next, data)) {
 294                 if ((cond && cond(data)) || (!cond)) {
 295                         if (*list->del)
 296                                 (*list->del)(data);
 297                         list_delete_node(list, node);
 298                 }
 299         }
 300 }
 301
 302 void list_delete(struct list **list)
 303 {
 304         assert(*list);
 305         list_delete_all_node(*list);
 306         list_free_internal(*list);
 307         *list = NULL;
 308 }
 309
 310 struct listnode *listnode_lookup(struct list *list, const void *data)
 311 {
 312         struct listnode *node;
 313
 314         assert(list);
 315         for (node = listhead(list); node; node = listnextnode(node))
 316                 if (data == listgetdata(node))
 317                         return node;
 318         return NULL;
 319 }
 320
 321 struct listnode *listnode_lookup_nocheck(struct list *list, void *data)
 322 {
 323         if (!list)
 324                 return NULL;
 325         return listnode_lookup(list, data);
 326 }
 327
 328 void list_delete_node(struct list *list, struct listnode *node)
 329 {
 330         if (node->prev)
 331                 node->prev->next = node->next;
 332         else
 333                 list->head = node->next;
 334         if (node->next)
 335                 node->next->prev = node->prev;
 336         else
 337                 list->tail = node->prev;
 338         list->count--;
 339         listnode_free(node);
 340 }
 341
 342 void list_sort(struct list *list, int (*cmp)(const void **, const void **))
 343 {
 344         struct listnode *ln, *nn;
 345         int i = -1;
 346         void *data;
 347         size_t n = list->count;
 348         void **items = XCALLOC(MTYPE_TMP, (sizeof(void *)) * n);
 349         int (*realcmp)(const void *, const void *) =
 350                 (int (*)(const void *, const void *))cmp;
 351
 352         for (ALL_LIST_ELEMENTS(list, ln, nn, data)) {
 353                 items[++i] = data;
 354                 list_delete_node(list, ln);
 355         }
 356
 357         qsort(items, n, sizeof(void *), realcmp);
 358
 359         for (unsigned int j = 0; j < n; ++j)
 360                 listnode_add(list, items[j]);
 361
 362         XFREE(MTYPE_TMP, items);
 363 }
 364
 365 struct listnode *listnode_add_force(struct list **list, void *val)
 366 {
 367         if (*list == NULL)
 368                 *list = list_new();
 369         return listnode_add(*list, val);
 370 }
 371
 372 void **list_to_array(struct list *list, void **arr, size_t arrlen)
 373 {
 374         struct listnode *ln;
 375         void *vp;
 376         size_t idx = 0;
 377
 378         for (ALL_LIST_ELEMENTS_RO(list, ln, vp)) {
 379                 arr[idx++] = vp;
 380                 if (idx == arrlen)
 381                         break;
 382         }
 383
 384         return arr;
 385 }