FD.io VPP  v17.01.1-3-gc6833f8
Vector Packet Processing
slist.h
Go to the documentation of this file.
1 /*
2  Copyright (c) 2012 Cisco and/or its affiliates.
3 
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
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_slist_h
18 #define included_slist_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 
29  (void *key, u32 elt_pool_index);
30 
31 typedef enum
32 {
36 
37 typedef struct
38 {
39  /* Vector of next elements. Every valid instance has at least one */
40  union
41  {
42  u32 next0[2];
44  } n;
45 
46  /* Index of item in user's pool */
48  /* $$$ pad to even divisor of cache line */
50 
51 static inline u32
53 {
54  if (elt->n.next0[0] & 1)
55  {
56  ASSERT (level < 2);
57  if (level == 1)
58  return elt->n.next0[1];
59  /* preserve ~0 (end of list) */
60  return (elt->n.next0[0] == (u32) ~ 0) ? elt->n.next0[0] :
61  (elt->n.next0[0] >> 1);
62  }
63  else
64  {
65  ASSERT (level < vec_len (elt->n.nexts));
66  return elt->n.nexts[level];
67  }
68 }
69 
70 static inline void
72 {
73  u32 old_level0_value[2];
74  /* level0 and not a vector */
75  if (level < 2 && (elt->n.next0[0] == 0 || elt->n.next0[0] & 1))
76  {
77  if (level == 0)
78  {
79  elt->n.next0[0] = (index << 1) | 1;
80  return;
81  }
82  elt->n.next0[1] = index;
83  return;
84  }
85  /* have to save old level0 values? */
86  if (elt->n.next0[0] & 1)
87  {
88  old_level0_value[0] = (elt->n.next0[0] == (u32) ~ 0) ?
89  elt->n.next0[0] : elt->n.next0[0] >> 1;
90  old_level0_value[1] = elt->n.next0[1];
91  elt->n.nexts = 0;
92  vec_add1 (elt->n.nexts, old_level0_value[0]);
93  vec_add1 (elt->n.nexts, old_level0_value[1]);
94  }
95  vec_validate (elt->n.nexts, level);
96  elt->n.nexts[level] = index;
97 }
98 
99 
100 typedef struct
101 {
102  /* pool of skip-list elements */
104 
105  /* last search path */
107 
108  /* last search number of compares */
110 
111  /* occupancy stats */
113 
114  /* Comparison function */
116 
117  /* Format function */
119 
120  /* items appear in successive plies with Pr (1 / branching_factor) */
122 
123  /* random seed */
125 } clib_slist_t;
126 
127 clib_error_t *clib_slist_init (clib_slist_t * sp, f64 branching_factor,
129  format_function_t format_user_element);
130 
132 
133 void clib_slist_add (clib_slist_t * sp, void *key, u32 user_pool_index);
135 u32 clib_slist_search (clib_slist_t * sp, void *key, u32 * ncompares);
136 
137 #endif /* included_slist_h */
138 
139 /*
140  * fd.io coding-style-patch-verification: ON
141  *
142  * Local Variables:
143  * eval: (c-set-style "gnu")
144  * End:
145  */
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:396
word( clib_slist_key_compare_function_t)(void *key, u32 elt_pool_index)
Definition: slist.h:29
Fixed length block allocator.
f64 branching_factor
Definition: slist.h:121
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:482
clib_slist_search_result_t clib_slist_del(clib_slist_t *sp, void *key)
Definition: slist.c:250
void clib_slist_add(clib_slist_t *sp, void *key, u32 user_pool_index)
Definition: slist.c:191
clib_slist_key_compare_function_t * compare
Definition: slist.h:115
u32 * occupancy
Definition: slist.h:112
clib_slist_elt_t * elts
Definition: slist.h:103
clib_slist_search_result_t
Definition: slist.h:31
format_function_t format_slist
Definition: slist.h:131
u32 next0[2]
Definition: slist.h:42
static u32 clib_slist_get_next_at_level(clib_slist_elt_t *elt, int level)
Definition: slist.h:52
u32 clib_slist_search(clib_slist_t *sp, void *key, u32 *ncompares)
Definition: slist.c:174
format_function_t * format_user_element
Definition: slist.h:118
u32 * nexts
Definition: slist.h:43
#define ASSERT(truth)
unsigned int u32
Definition: types.h:88
static void clib_slist_set_next_at_level(clib_slist_elt_t *elt, u32 index, int level)
Definition: slist.h:71
u32 * path
Definition: slist.h:106
u32 user_pool_index
Definition: slist.h:47
u8 *( format_function_t)(u8 *s, va_list *args)
Definition: format.h:48
i64 word
Definition: types.h:111
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
double f64
Definition: types.h:142
u32 ncompares
Definition: slist.h:109
u32 seed
Definition: slist.h:124
union clib_slist_elt_t::@21 n
clib_error_t * clib_slist_init(clib_slist_t *sp, f64 branching_factor, clib_slist_key_compare_function_t compare, format_function_t format_user_element)
Definition: slist.c:52
CLIB vectors are ubiquitous dynamically resized arrays with by user defined "headers".