common/mpls_list.h

   1
   2 /*
   3  *  Copyright (C) James R. Leu 2002
   4  *  jleu@mindspring.com
   5  *
   6  *  This software is covered under the LGPL, for more
   7  *  info check out http://www.gnu.org/copyleft/lgpl.html
   8  */
   9
  10 #ifndef _MPLS_LIST_H_
  11 #define _MPLS_LIST_H_
  12
  13 #include "mpls_mm_impl.h"
  14
  15 /* Endo list, the prev,next ptrs are part of the element in the list */
  16 /* No addition memory allocations are done when inserting into the list */
  17
  18 #define MPLS_LIST_ROOT(name,type)       \
  19 struct name {                           \
  20   struct type *llh_first;               \
  21   struct type *llh_last;                \
  22   int count;                            \
  23 }
  24
  25 #define MPLS_LIST_ELEM(type)            \
  26 struct {                                \
  27   struct type *lle_next;                \
  28   struct type *lle_prev;                \
  29 }
  30
  31 #define MPLS_LIST_REMOVE(head, elm, field) {                            \
  32   if((elm)->field.lle_next == (void *)(head))                           \
  33     (head)->llh_last = (elm)->field.lle_prev;                           \
  34   else                                                                  \
  35     (elm)->field.lle_next->field.lle_prev = (elm)->field.lle_prev;      \
  36   if((elm)->field.lle_prev == (void *)(head))                           \
  37     (head)->llh_first = (elm)->field.lle_next;                          \
  38   else                                                                  \
  39     (elm)->field.lle_prev->field.lle_next = (elm)->field.lle_next;      \
  40   (head)->count--;                                                      \
  41 }
  42
  43 #define MPLS_LIST_INSERT_BEFORE(head,listelm,elm,field) {       \
  44   (elm)->field.lle_next = (listelm);                            \
  45   (elm)->field.lle_prev = (listelm)->field.lle_prev;            \
  46   if((listelm)->field.lle_prev == (void *)(head))               \
  47     (head)->llh_first = (elm);                                  \
  48   else                                                          \
  49     (listelm)->field.lle_prev->field.lle_next = (elm);          \
  50   (listelm)->field.lle_prev = (elm);                            \
  51   (head)->count++;                                              \
  52 }
  53
  54 #define MPLS_LIST_INIT(head,type) {             \
  55   (head)->llh_first = (struct type *)(head);    \
  56   (head)->llh_last = (struct type *)(head);     \
  57   (head)->count = 0;                            \
  58 }
  59
  60 #define MPLS_LIST_IN_LIST(elm,field) ((elm)->field.lle_next && (elm)->field.lle_prev)
  61
  62 #define MPLS_LIST_ADD_HEAD(head, elm, field, type) {    \
  63   (elm)->field.lle_next = (head)->llh_first;            \
  64   (elm)->field.lle_prev = (struct type *)(head);        \
  65   if ((head)->llh_last == (struct type *)(head))        \
  66     (head)->llh_last = (elm);                           \
  67   else                                                  \
  68     (head)->llh_first->field.lle_prev = (elm);          \
  69   (head)->llh_first = (elm);                            \
  70   (head)->count++;                                      \
  71 }
  72
  73 #define MPLS_LIST_ADD_TAIL(head, elm, field, type) {    \
  74   (elm)->field.lle_next = (struct type *)(head);        \
  75   (elm)->field.lle_prev = (head)->llh_last;             \
  76   if ((head)->llh_first == (struct type *)(head))       \
  77     (head)->llh_first = (elm);                          \
  78   else                                                  \
  79     (head)->llh_last->field.lle_next = (elm);           \
  80   (head)->llh_last = (elm);                             \
  81   (head)->count++;                                      \
  82 }
  83
  84 #define MPLS_LIST_REMOVE_TAIL(root,elem,field) {        \
  85   (elem) = (root)->llh_last;                    \
  86   if((elem) && (elem) != (void*)(root)) {       \
  87     MPLS_LIST_REMOVE(root,elem,field);          \
  88   } else {                                      \
  89     (elem) = NULL;                              \
  90   }                                             \
  91   (root)->count--;                              \
  92 }
  93
  94 #define MPLS_LIST_REMOVE_HEAD(root,elem,field) {        \
  95   (elem) = (root)->llh_first;                   \
  96   if((elem) && (elem) != (void*)(root)) {       \
  97     MPLS_LIST_REMOVE(root,elem,field);          \
  98   } else {                                      \
  99     (elem) = NULL;                              \
 100   }                                             \
 101   (root)->count--;                              \
 102 }
 103
 104 #define MPLS_LIST_ELEM_INIT(elem,field) {       \
 105   (elem)->field.lle_next = NULL;                \
 106   (elem)->field.lle_prev = NULL;                \
 107 }
 108
 109 #define MPLS_LIST_HEAD(root)            (((root)->llh_first == (void*)(root))?(NULL):((root)->llh_first))
 110 #define MPLS_LIST_NEXT(root,elem,field) ((((elem)->field.lle_next) == (void*)(root))?(NULL):((elem)->field.lle_next))
 111 #define MPLS_LIST_PREV(root,elem,field) ((((elem)->field.lle_prev) == (void*)(root))?(NULL):((elem)->field.lle_prev))
 112 #define MPLS_LIST_TAIL(root)            (((root)->llh_last == (void*)(root))?(NULL):((root)->llh_last))
 113
 114 #define MPLS_LIST_EMPTY(root) ((root)->count ? MPLS_BOOL_FALSE : MPLS_BOOL_TRUE)
 115
 116 /* non Endo list, the list node has the next,prev pointers and a pointer to */
 117 /* the data being stored, a memory allocation has to occur for each insert */
 118
 119 typedef struct mpls_link_list_node {
 120   struct mpls_link_list_node *next;
 121   struct mpls_link_list_node *prev;
 122   void *data;
 123 } mpls_link_list_node;
 124
 125 typedef struct mpls_link_list {
 126   struct mpls_link_list_node *head;
 127   struct mpls_link_list_node *tail;
 128   int count;
 129 } mpls_link_list;
 130
 131 #define mpls_link_list_head(X) ((X)->head)
 132 #define mpls_link_list_head_data(X) ((X)->head ? (X)->head->data : NULL)
 133 #define mpls_link_list_tail(X) ((X)->tail)
 134 #define mpls_link_list_tail_data(X) ((X)->tail ? (X)->tail->data : NULL)
 135 #define mpls_link_list_count(X) ((X)->count)
 136 #define mpls_link_list_isempty(X) ((X)->head == NULL && (X)->tail == NULL)
 137
 138 #define MPLS_LINK_LIST_LOOP(LIST,DATA,NODE)                     \
 139   for ((NODE) = (LIST)->head; (NODE); (NODE) = (NODE)->next)    \
 140     if (((DATA) = (NODE)->data) != NULL)
 141
 142 static inline void mpls_link_list_init(struct mpls_link_list *list) {
 143   memset(list, 0, sizeof(*list));
 144 }
 145
 146 static inline struct mpls_link_list *mpls_link_list_create() {
 147   struct mpls_link_list *list;
 148
 149   if ((list = mpls_malloc(sizeof(*list)))) {
 150     mpls_link_list_init(list);
 151   }
 152   return list;
 153 }
 154
 155 static inline void mpls_link_list_delete(struct mpls_link_list *list) {
 156   mpls_free(list);
 157 }
 158
 159 static inline struct mpls_link_list_node *mpls_link_list_node_create(void *data)
 160 {
 161   struct mpls_link_list_node *node;
 162
 163   if ((node = mpls_malloc(sizeof(*node)))) {
 164     memset(node, 0, sizeof(*node));
 165     node->data = data;
 166   }
 167   return node;
 168 }
 169
 170 static inline void mpls_link_list_node_delete(struct mpls_link_list_node *node)
 171 {
 172   mpls_free(node);
 173 }
 174
 175 static inline void mpls_link_list_add_node_head(struct mpls_link_list *list,
 176   struct mpls_link_list_node *node) {
 177   node->next = list->head;
 178
 179   if (list->tail == NULL) {
 180     list->tail = node;
 181   } else {
 182     list->head->prev = node;
 183     node->next = list->head;
 184   }
 185   list->head = node;
 186   list->count++;
 187 }
 188
 189 static inline mpls_return_enum mpls_link_list_add_head(
 190   struct mpls_link_list *list, void * data) {
 191   struct mpls_link_list_node *node;
 192
 193   if ((node = mpls_link_list_node_create(data))) {
 194     mpls_link_list_add_node_head(list,node);
 195     return MPLS_SUCCESS;
 196   }
 197   return MPLS_FATAL;
 198 }
 199
 200 static inline void mpls_link_list_add_node_tail(
 201   struct mpls_link_list *list, struct mpls_link_list_node *node) {
 202   node->prev = list->tail;
 203
 204   if (list->head == NULL) {
 205     list->head = node;
 206   } else {
 207     node->prev = list->tail;
 208     list->tail->next = node;
 209   }
 210   list->tail = node;
 211   list->count++;
 212 }
 213
 214 static inline mpls_return_enum mpls_link_list_add_tail(
 215   struct mpls_link_list *list, void *data) {
 216   struct mpls_link_list_node *node;
 217
 218   if ((node = mpls_link_list_node_create(data))) {
 219     mpls_link_list_add_node_tail(list, node);
 220     return MPLS_SUCCESS;
 221   }
 222   return MPLS_FATAL;
 223 }
 224
 225 static inline void mpls_link_list_add_node_before(struct mpls_link_list *list,
 226   struct mpls_link_list_node *ptr, struct mpls_link_list_node *node) {
 227   if (list->head == ptr) {
 228     node->next = ptr;
 229     ptr->prev = node;
 230     list->head = node;
 231   } else {
 232     node->prev = ptr->prev;
 233     node->next = ptr;
 234     ptr->prev->next = node;
 235     ptr->prev = node;
 236   }
 237   list->count++;
 238 }
 239
 240 static inline mpls_return_enum mpls_link_list_add_data_before(
 241   struct mpls_link_list *list, struct mpls_link_list_node *ptr, void *data) {
 242   struct mpls_link_list_node *node;
 243
 244   if ((node = mpls_link_list_node_create(data))) {
 245     mpls_link_list_add_node_before(list,ptr,node);
 246     return MPLS_SUCCESS;
 247   }
 248   return MPLS_FATAL;
 249 }
 250
 251 static inline void mpls_link_list_add_node_after(struct mpls_link_list *list,
 252   struct mpls_link_list_node *ptr, struct mpls_link_list_node *node) {
 253   if (list->tail == ptr) {
 254     ptr->next = node;
 255     node->prev = ptr;
 256     list->tail = node;
 257   } else {
 258     node->prev = ptr;
 259     node->next = ptr->next;
 260     ptr->next = node;
 261     ptr->next->prev = node;
 262   }
 263   list->count++;
 264 }
 265
 266 static inline mpls_return_enum mpls_link_list_add_data_after(
 267   struct mpls_link_list *list, struct mpls_link_list_node *ptr, void *data) {
 268   struct mpls_link_list_node *node;
 269
 270   if ((node = mpls_link_list_node_create(data))) {
 271     mpls_link_list_add_node_after(list, ptr, node);
 272     return MPLS_SUCCESS;
 273   }
 274   return MPLS_FATAL;
 275 }
 276
 277 static inline void mpls_link_list_remove_node(struct mpls_link_list *list,
 278   struct mpls_link_list_node *node) {
 279
 280   if (node->prev) {
 281     node->prev->next = node->next;
 282   } else {
 283     list->head = node->next;
 284   }
 285
 286   if (node->next) {
 287     node->next->prev = node->prev;
 288   } else {
 289     list->tail = node->prev;
 290   }
 291
 292   list->count--;
 293 }
 294
 295 static inline void mpls_link_list_remove_data(struct mpls_link_list* list,
 296   void *val)
 297 {
 298   struct mpls_link_list_node *node;
 299
 300   for (node = list->head; node; node = node->next) {
 301     if (node->data == val) {
 302       mpls_link_list_remove_node(list,node);
 303       mpls_link_list_node_delete(node);
 304       break;
 305     }
 306   }
 307 }
 308
 309 #endif