src/vppinfra/dlist.h

   1 /*
   2  * Copyright (c) 2016 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  *
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15 */
  16
  17 #ifndef included_dlist_h
  18 #define included_dlist_h
  19
  20 #include <stdarg.h>
  21 #include <vppinfra/clib.h>
  22 #include <vppinfra/vec.h>
  23 #include <vppinfra/pool.h>
  24 #include <vppinfra/error.h>
  25 #include <vppinfra/format.h>
  26 #include <vppinfra/cache.h>
  27
  28 typedef struct
  29 {
  30   u32 next;
  31   u32 prev;
  32   u32 value;
  33 } dlist_elt_t;
  34
  35 static inline void
  36 clib_dlist_init (dlist_elt_t * pool, u32 index)
  37 {
  38   dlist_elt_t *head = pool_elt_at_index (pool, index);
  39   memset (head, 0xFF, sizeof (*head));
  40 }
  41
  42 static inline void
  43 clib_dlist_addtail (dlist_elt_t * pool, u32 head_index, u32 new_index)
  44 {
  45   dlist_elt_t *head = pool_elt_at_index (pool, head_index);
  46   u32 old_last_index;
  47   dlist_elt_t *old_last;
  48   dlist_elt_t *new;
  49
  50   ASSERT (head->value == ~0);
  51
  52   new = pool_elt_at_index (pool, new_index);
  53
  54   if (PREDICT_FALSE (head->next == ~0))
  55     {
  56       head->next = head->prev = new_index;
  57       new->next = new->prev = head_index;
  58       return;
  59     }
  60
  61   old_last_index = head->prev;
  62   old_last = pool_elt_at_index (pool, old_last_index);
  63
  64   new->next = old_last->next;
  65   new->prev = old_last_index;
  66   old_last->next = new_index;
  67   head->prev = new_index;
  68 }
  69
  70 static inline void
  71 clib_dlist_addhead (dlist_elt_t * pool, u32 head_index, u32 new_index)
  72 {
  73   dlist_elt_t *head = pool_elt_at_index (pool, head_index);
  74   dlist_elt_t *old_first;
  75   u32 old_first_index;
  76   dlist_elt_t *new;
  77
  78   ASSERT (head->value == ~0);
  79
  80   new = pool_elt_at_index (pool, new_index);
  81
  82   if (PREDICT_FALSE (head->next == ~0))
  83     {
  84       head->next = head->prev = new_index;
  85       new->next = new->prev = head_index;
  86       return;
  87     }
  88
  89   old_first_index = head->next;
  90   old_first = pool_elt_at_index (pool, old_first_index);
  91
  92   new->next = old_first_index;
  93   new->prev = old_first->prev;
  94   old_first->prev = new_index;
  95   head->next = new_index;
  96 }
  97
  98 static inline void
  99 clib_dlist_remove (dlist_elt_t * pool, u32 index)
 100 {
 101   dlist_elt_t *elt = pool_elt_at_index (pool, index);
 102   dlist_elt_t *next_elt, *prev_elt;
 103
 104   /* listhead, not so much */
 105   ASSERT (elt->value != ~0);
 106
 107   next_elt = pool_elt_at_index (pool, elt->next);
 108   prev_elt = pool_elt_at_index (pool, elt->prev);
 109
 110   next_elt->prev = elt->prev;
 111   prev_elt->next = elt->next;
 112
 113   elt->prev = elt->next = ~0;
 114 }
 115
 116 static inline u32
 117 clib_dlist_remove_head (dlist_elt_t * pool, u32 head_index)
 118 {
 119   dlist_elt_t *head = pool_elt_at_index (pool, head_index);
 120   u32 rv;
 121
 122   ASSERT (head->value == ~0);
 123
 124   if (head->next == ~0)
 125     return ~0;
 126
 127   rv = head->next;
 128   clib_dlist_remove (pool, rv);
 129   return rv;
 130 }
 131
 132 static inline u32
 133 clib_dlist_remove_tail (dlist_elt_t * pool, u32 head_index)
 134 {
 135   dlist_elt_t *head = pool_elt_at_index (pool, head_index);
 136   u32 rv;
 137
 138   ASSERT (head->value == ~0);
 139
 140   if (head->prev == ~0)
 141     return ~0;
 142
 143   rv = head->prev;
 144   clib_dlist_remove (pool, rv);
 145   return rv;
 146 }
 147
 148 #endif /* included_dlist_h */
 149
 150 /*
 151  * fd.io coding-style-patch-verification: ON
 152  *
 153  * Local Variables:
 154  * eval: (c-set-style "gnu")
 155  * End:
 156  */