1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
/*
Copyright (c) 2012 Cisco and/or its affiliates.
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at:
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef included_slist_h
#define included_slist_h
#include <stdarg.h>
#include <vppinfra/clib.h>
#include <vppinfra/vec.h>
#include <vppinfra/pool.h>
#include <vppinfra/error.h>
#include <vppinfra/format.h>
#include <vppinfra/cache.h>
typedef word (clib_slist_key_compare_function_t)
(void *key, u32 elt_pool_index);
typedef enum
{
CLIB_SLIST_MATCH = 0,
CLIB_SLIST_NO_MATCH
} clib_slist_search_result_t;
typedef struct
{
/* Vector of next elements. Every valid instance has at least one */
union
{
u32 next0[2];
u32 *nexts;
} n;
/* Index of item in user's pool */
u32 user_pool_index;
/* $$$ pad to even divisor of cache line */
} clib_slist_elt_t;
static inline u32
clib_slist_get_next_at_level (clib_slist_elt_t * elt, int level)
{
if (elt->n.next0[0] & 1)
{
ASSERT (level < 2);
if (level == 1)
return elt->n.next0[1];
/* preserve ~0 (end of list) */
return (elt->n.next0[0] == (u32) ~ 0) ? elt->n.next0[0] :
(elt->n.next0[0] >> 1);
}
else
{
ASSERT (level < vec_len (elt->n.nexts));
return elt->n.nexts[level];
}
}
static inline void
clib_slist_set_next_at_level (clib_slist_elt_t * elt, u32 index, int level)
{
u32 old_level0_value[2];
/* level0 and not a vector */
if (level < 2 && (elt->n.next0[0] == 0 || elt->n.next0[0] & 1))
{
if (level == 0)
{
elt->n.next0[0] = (index << 1) | 1;
return;
}
elt->n.next0[1] = index;
return;
}
/* have to save old level0 values? */
if (elt->n.next0[0] & 1)
{
old_level0_value[0] = (elt->n.next0[0] == (u32) ~ 0) ?
elt->n.next0[0] : elt->n.next0[0] >> 1;
old_level0_value[1] = elt->n.next0[1];
elt->n.nexts = 0;
vec_add1 (elt->n.nexts, old_level0_value[0]);
vec_add1 (elt->n.nexts, old_level0_value[1]);
}
vec_validate (elt->n.nexts, level);
elt->n.nexts[level] = index;
}
typedef struct
{
/* pool of skip-list elements */
clib_slist_elt_t *elts;
/* last search path */
u32 *path;
/* last search number of compares */
u32 ncompares;
/* occupancy stats */
u32 *occupancy;
/* Comparison function */
clib_slist_key_compare_function_t *compare;
/* Format function */
format_function_t *format_user_element;
/* items appear in successive plies with Pr (1 / branching_factor) */
f64 branching_factor;
/* random seed */
u32 seed;
} clib_slist_t;
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);
format_function_t format_slist;
void clib_slist_add (clib_slist_t * sp, void *key, u32 user_pool_index);
clib_slist_search_result_t clib_slist_del (clib_slist_t * sp, void *key);
u32 clib_slist_search (clib_slist_t * sp, void *key, u32 * ncompares);
#endif /* included_slist_h */
/*
* fd.io coding-style-patch-verification: ON
*
* Local Variables:
* eval: (c-set-style "gnu")
* End:
*/
|
