2 Copyright (c) 2012 Cisco and/or its affiliates.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #ifndef included_slist_h
18 #define included_slist_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>
28 typedef word (clib_slist_key_compare_function_t)
29 (void *key, u32 elt_pool_index);
35 } clib_slist_search_result_t;
39 /* Vector of next elements. Every valid instance has at least one */
46 /* Index of item in user's pool */
48 /* $$$ pad to even divisor of cache line */
52 clib_slist_get_next_at_level (clib_slist_elt_t * elt, int level)
54 if (elt->n.next0[0] & 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);
65 ASSERT (level < vec_len (elt->n.nexts));
66 return elt->n.nexts[level];
71 clib_slist_set_next_at_level (clib_slist_elt_t * elt, u32 index, int level)
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))
79 elt->n.next0[0] = (index << 1) | 1;
82 elt->n.next0[1] = index;
85 /* have to save old level0 values? */
86 if (elt->n.next0[0] & 1)
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];
92 vec_add1 (elt->n.nexts, old_level0_value[0]);
93 vec_add1 (elt->n.nexts, old_level0_value[1]);
95 vec_validate (elt->n.nexts, level);
96 elt->n.nexts[level] = index;
102 /* pool of skip-list elements */
103 clib_slist_elt_t *elts;
105 /* last search path */
108 /* last search number of compares */
111 /* occupancy stats */
114 /* Comparison function */
115 clib_slist_key_compare_function_t *compare;
117 /* Format function */
118 format_function_t *format_user_element;
120 /* items appear in successive plies with Pr (1 / branching_factor) */
121 f64 branching_factor;
127 clib_error_t *clib_slist_init (clib_slist_t * sp, f64 branching_factor,
128 clib_slist_key_compare_function_t compare,
129 format_function_t format_user_element);
131 format_function_t format_slist;
133 void clib_slist_add (clib_slist_t * sp, void *key, u32 user_pool_index);
134 clib_slist_search_result_t clib_slist_del (clib_slist_t * sp, void *key);
135 u32 clib_slist_search (clib_slist_t * sp, void *key, u32 * ncompares);
137 #endif /* included_slist_h */
140 * fd.io coding-style-patch-verification: ON
143 * eval: (c-set-style "gnu")