Line data    Source code

       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       23463 : clib_dlist_init (dlist_elt_t * pool, u32 index)
      37             : {
      38       23463 :   dlist_elt_t *head = pool_elt_at_index (pool, index);
      39       23463 :   clib_memset (head, 0xFF, sizeof (*head));
      40       23463 : }
      41             : 
      42             : static inline void
      43       52580 : clib_dlist_addtail (dlist_elt_t * pool, u32 head_index, u32 new_index)
      44             : {
      45       52580 :   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       52578 :   ASSERT (head->value == ~0);
      51             : 
      52       52578 :   new = pool_elt_at_index (pool, new_index);
      53             : 
      54       52578 :   if (PREDICT_FALSE (head->next == ~0))
      55             :     {
      56       10564 :       head->next = head->prev = new_index;
      57       10564 :       new->next = new->prev = head_index;
      58       10564 :       return;
      59             :     }
      60             : 
      61       42014 :   old_last_index = head->prev;
      62       42014 :   old_last = pool_elt_at_index (pool, old_last_index);
      63             : 
      64       42013 :   new->next = old_last->next;
      65       42013 :   new->prev = old_last_index;
      66       42013 :   old_last->next = new_index;
      67       42013 :   head->prev = new_index;
      68             : }
      69             : 
      70             : static inline void
      71       37911 : clib_dlist_addhead (dlist_elt_t * pool, u32 head_index, u32 new_index)
      72             : {
      73       37911 :   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       37911 :   ASSERT (head->value == ~0);
      79             : 
      80       37911 :   new = pool_elt_at_index (pool, new_index);
      81             : 
      82       37910 :   if (PREDICT_FALSE (head->next == ~0))
      83             :     {
      84           2 :       head->next = head->prev = new_index;
      85           2 :       new->next = new->prev = head_index;
      86           2 :       return;
      87             :     }
      88             : 
      89       37908 :   old_first_index = head->next;
      90       37908 :   old_first = pool_elt_at_index (pool, old_first_index);
      91             : 
      92       37909 :   new->next = old_first_index;
      93       37909 :   new->prev = old_first->prev;
      94       37909 :   old_first->prev = new_index;
      95       37909 :   head->next = new_index;
      96             : }
      97             : 
      98             : static inline void
      99       90233 : clib_dlist_remove (dlist_elt_t * pool, u32 index)
     100             : {
     101       90233 :   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       90232 :   ASSERT (elt->value != ~0);
     106             : 
     107       90232 :   next_elt = pool_elt_at_index (pool, elt->next);
     108       90234 :   prev_elt = pool_elt_at_index (pool, elt->prev);
     109             : 
     110       90232 :   next_elt->prev = elt->prev;
     111       90232 :   prev_elt->next = elt->next;
     112             : 
     113       90232 :   elt->prev = elt->next = ~0;
     114       90232 : }
     115             : 
     116             : static inline u32
     117      128477 : clib_dlist_remove_head (dlist_elt_t * pool, u32 head_index)
     118             : {
     119      128477 :   dlist_elt_t *head = pool_elt_at_index (pool, head_index);
     120             :   u32 rv;
     121             : 
     122      128475 :   ASSERT (head->value == ~0);
     123             : 
     124      128484 :   if (head->next == ~0 || (head->next == head_index))
     125       85578 :     return ~0;
     126             : 
     127       42906 :   rv = head->next;
     128       42906 :   clib_dlist_remove (pool, rv);
     129       42905 :   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             :  */