FD.io VPP  v16.12-rc0-308-g931be3a
Vector Packet Processing
index_list.c
Go to the documentation of this file.
1 /*
2  *------------------------------------------------------------------
3  * index_list.c - vector-index-based lists. 64-bit pointers suck.
4  *
5  * Copyright (c) 2008-2009, 2011 Cisco and/or its affiliates.
6  * Licensed under the Apache License, Version 2.0 (the "License");
7  * you may not use this file except in compliance with the License.
8  * You may obtain a copy of the License at:
9  *
10  * http://www.apache.org/licenses/LICENSE-2.0
11  *
12  * Unless required by applicable law or agreed to in writing, software
13  * distributed under the License is distributed on an "AS IS" BASIS,
14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15  * See the License for the specific language governing permissions and
16  * limitations under the License.
17  *------------------------------------------------------------------
18  */
19 
20 #include <stdio.h>
21 #include <string.h>
22 //#include <clib_lite.h>
23 #include <vppinfra/vec.h>
24 #include "index_list.h"
25 
26 /*
27  * index_slist_addhead
28  *
29  * args: headp -- pointer to e.g. a hash bucket
30  * vector -- vector containing the list
31  * elsize -- size of an element in this vector
32  * offset -- offset in each vector element of this list thread
33  * index_to_add -- index in the vector to add to the list
34  *
35  * Adds new items to the head of the list. Try not to screw up the args!
36  */
38  u8 *vector, u32 elsize, u32 offset, u32 index_to_add)
39 {
40  return (index_slist_addhead_inline(headp, vector, elsize, offset,
41  index_to_add));
42 }
43 
44 /*
45  * index_slist_remelem
46  *
47  * args: headp -- pointer to e.g. a hash bucket
48  * vector -- vector containing the list
49  * elsize -- size of an element in this vector
50  * offset -- offset in each vector element of this list thread
51  * index_to_del -- index in the vector to delete from the list
52  *
53  * Try not to screw up the args!
54  */
55 
57  u8 *vector, u32 elsize, u32 offset,
58  u32 index_to_delete)
59 {
60  return (index_slist_remelem_inline(headp, vector, elsize, offset,
61  index_to_delete));
62 }
63 
64 
65 /*
66  * index_dlist_addtail
67  *
68  * Append the indicated vector element to the doubly-linked list
69  * whose first element is pointed to by headp.
70  *
71  * args: head_index -- listhead vector element index.
72  * vector -- vector containing the list
73  * elsize -- size of an element in this vector
74  * offset -- offset in each vector element of this list thread
75  * index_to_add -- index in the vector to add to the list
76  *
77  * Do not call this routine to create the listhead. Simply set
78  * index_dlist->next = index_dlist->prev = index of item.
79  *
80  * Try not to screw up the args.
81  */
82 
83 void index_dlist_addtail (u32 head_index, u8 *vector, u32 elsize,
84  u32 offset, u32 index_to_add)
85 {
86  index_dlist_t *elp;
87  index_dlist_t *elp_next;
88  index_dlist_t *headp;
89 
90  headp = (index_dlist_t *)(vector + offset + elsize*head_index);
91  elp = (index_dlist_t *)(vector + offset + elsize*index_to_add);
92  elp->next = index_to_add;
93  elp->prev = index_to_add;
94 
95  elp->next = headp->next;
96  headp->next = index_to_add;
97 
98  elp_next = (index_dlist_t *)(vector + offset + elsize*elp->next);
99  elp->prev = elp_next->prev;
100  elp_next->prev = index_to_add;
101 }
102 
104  u8 *vector, u32 elsize, u32 offset,
105  u32 index_to_delete)
106 {
107  u32 rv = head_index;
108  index_dlist_t *headp, *elp, *elp_next;
109 
110  elp = (index_dlist_t *)(vector + offset + elsize*index_to_delete);
111 
112  /* Deleting the head index? */
113  if (PREDICT_FALSE(head_index == index_to_delete)) {
114  rv = elp->next;
115  /* The only element on the list? */
116  if (PREDICT_FALSE(rv == head_index))
117  rv = EMPTY;
118  }
119 
120  headp = (index_dlist_t *)(vector + offset + elsize*elp->prev);
121  headp->next = elp->next;
122  elp_next = (index_dlist_t *)(vector + offset + elsize*elp->next);
123  elp_next->prev = elp->prev;
124 
125  elp->next = elp->prev = EMPTY;
126 
127  return rv;
128 }
129 
130 
131 #ifdef TEST_CODE2
132 
133 typedef struct tv_ {
134  char junk[43];
135  index_dlist_t l;
136 } tv_t;
137 
138 
139 void index_list_test_cmd(int argc, unsigned long *argv)
140 {
141  int i, j;
142  u32 head_index;
143  index_dlist_t *headp;
144  tv_t *tp=0;
145 
146  vec_validate(tp, 3);
147  head_index = 3;
148 
149  memset(tp, 0xa, sizeof(tp[0])*vec_len(tp));
150 
151  /* Here's how to set up the head element... */
152  headp = &((tp + head_index)->l);
153  headp->next = headp->prev = head_index;
154 
155  for (i = 0; i < 3; i++) {
156  index_dlist_addtail(head_index, (u8 *)tp, sizeof(tp[0]),
157  STRUCT_OFFSET_OF(tv_t, l), i);
158  printf("headp next %d prev %d\n",
159  headp->next, headp->prev);
160  for (j = 0; j <= 3; j++) {
161  printf ("[%d]: next %d prev %d\n", j,
162  tp[j].l.next, tp[j].l.prev);
163  }
164  printf("---------------\n");
165 
166  }
167 
168  printf("After all adds:\n");
169 
170  printf("headp next %d prev %d\n",
171  headp->next, headp->prev);
172 
173  for (j = 0; j <= 3; j++) {
174  printf ("[%d]: next %d prev %d\n", j,
175  tp[j].l.next, tp[j].l.prev);
176  }
177  printf("---------------\n");
178 
179  head_index = index_dlist_remelem (head_index, (u8 *)tp, sizeof(tp[0]),
180  STRUCT_OFFSET_OF(tv_t, l), 1);
181 
182  printf("after delete 1, head index %d\n", head_index);
183  headp = &((tp + head_index)->l);
184  printf("headp next %d prev %d\n",
185  headp->next, headp->prev);
186  for (j = 0; j <= 3; j++) {
187  printf ("[%d]: next %d prev %d\n", j,
188  tp[j].l.next, tp[j].l.prev);
189  }
190  printf("---------------\n");
191 
192  index_dlist_addtail(head_index, (u8 *)tp, sizeof(tp[0]),
193  STRUCT_OFFSET_OF(tv_t, l), 1);
194 
195  printf("after re-add 1, head index %d\n", head_index);
196  headp = &((tp + head_index)->l);
197  printf("headp next %d prev %d\n",
198  headp->next, headp->prev);
199  for (j = 0; j <= 3; j++) {
200  printf ("[%d]: next %d prev %d\n", j,
201  tp[j].l.next, tp[j].l.prev);
202  }
203  printf("---------------\n");
204 
205  for (i = 3; i >= 0; i--) {
206  head_index = index_dlist_remelem (head_index, (u8 *)tp, sizeof(tp[0]),
207  STRUCT_OFFSET_OF(tv_t, l), i);
208  printf("after delete, head index %d\n", head_index);
209  if (head_index != EMPTY) {
210  headp = &((tp + head_index)->l);
211  printf("headp next %d prev %d\n",
212  headp->next, headp->prev);
213  for (j = 0; j <= 3; j++) {
214  printf ("[%d]: next %d prev %d\n", j,
215  tp[j].l.next, tp[j].l.prev);
216  }
217  } else {
218  printf("empty list\n");
219  }
220  printf("---------------\n");
221  }
222 }
223 #endif /* test code 2 */
224 
225 #ifdef TEST_CODE
226 
227 typedef struct tv_ {
228  char junk[43];
229  index_slist_t l;
230 } tv_t;
231 
232 
233 void index_list_test_cmd(int argc, unsigned long *argv)
234 {
235  int i, j;
236  tv_t *tp = 0;
237  index_slist_t *buckets = 0;
238 
239  vec_add1((u32 *)buckets, EMPTY);
240  vec_validate(tp, 9);
241 
242  for (i = 0; i < 10; i++) {
243  index_slist_addhead(buckets, (u8 *)tp, sizeof(*tp),
244  STRUCT_OFFSET_OF(tv_t, l), i);
245  }
246 
247  printf ("after adds, buckets[0] = %u\n", buckets[0]);
248 
249  for (j = 0; j < 10; j++) {
250  printf("tp[%d] next %u\n", j, tp[j].l);
251 
252  }
253 
254  for (i = 0; i < 10; i++) {
255  if (PREDICT_FALSE(index_slist_remelem(buckets, (u8 *) tp, sizeof(*tp),
256  STRUCT_OFFSET_OF(tv_t, l), i))) {
257  printf("OUCH: remelem failure at index %d\n", i);
258  }
259  if (PREDICT_FALSE(tp[i].l.next != EMPTY)) {
260  printf("OUCH: post-remelem next not EMPTY, index %d\n", i);
261  }
262  }
263 
264  printf ("after deletes, buckets[0] = %x\n", buckets[0]);
265 
266  for (i = 0; i < 10; i++) {
267  index_slist_addhead(buckets, (u8 *)tp, sizeof(*tp),
268  STRUCT_OFFSET_OF(tv_t, l), i);
269  }
270 
271  printf ("after adds, buckets[0] = %u\n", buckets[0]);
272 
273  for (j = 0; j < 10; j++) {
274  printf("tp[%d] next %u\n", j, tp[j].l);
275 
276  }
277 
278  for (i = 9; i >= 0; i--) {
279  if (PREDICT_FALSE(index_slist_remelem(buckets, (u8 *) tp, sizeof(*tp),
280  STRUCT_OFFSET_OF(tv_t, l), i))) {
281  printf("OUCH: remelem failure at index %d\n", i);
282  }
283  if ((tp[i].l.next != EMPTY)) {
284  printf("OUCH: post-remelem next not EMPTY, index %d\n", i);
285  }
286  }
287 
288  printf ("after deletes, buckets[0] = %x\n", buckets[0]);
289 
290  printf("add evens, then odds...\n");
291 
292  for (i = 0; i < 10; i += 2) {
293  index_slist_addhead(buckets, (u8 *)tp, sizeof(*tp),
294  STRUCT_OFFSET_OF(tv_t, l), i);
295 
296  printf ("head = buckets[0].next = %d\n", buckets[0].next);
297  for (j = 0; j < 10; j++) {
298  printf("tp[%d] next %u\n", j, tp[j].l);
299  }
300  printf("-------------\n");
301  }
302 
303  for (i = 1; i < 10; i += 2) {
304  index_slist_addhead(buckets, (u8 *)tp, sizeof(*tp),
305  STRUCT_OFFSET_OF(tv_t, l), i);
306 
307  printf ("head = buckets[0].next = %d\n", buckets[0].next);
308  for (j = 0; j < 10; j++) {
309  printf("tp[%d] next %u\n", j, tp[j].l);
310  }
311  printf("-------------\n");
312  }
313 
314  printf ("after adds, buckets[0] = %u\n", buckets[0]);
315 
316  for (j = 0; j < 10; j++) {
317  printf("tp[%d] next %u\n", j, tp[j].l);
318 
319  }
320 
321  for (i = 9; i >= 0; i--) {
322  if (PREDICT_FALSE(index_slist_remelem(buckets, (u8 *) tp, sizeof(*tp),
323  STRUCT_OFFSET_OF(tv_t, l), i))) {
324  printf("OUCH: remelem failure at index %d\n", i);
325  }
326  if (PREDICT_FALSE(tp[i].l.next != EMPTY)) {
327  printf("OUCH: post-remelem next not EMPTY, index %d\n", i);
328  }
329  }
330 
331  printf ("after deletes, buckets[0] = %x\n", buckets[0]);
332 
333  vec_free(buckets);
334  vec_free(tp);
335 }
336 #endif /* test code */
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:396
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:343
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:482
#define STRUCT_OFFSET_OF(t, f)
Definition: clib.h:62
void index_slist_addhead(index_slist_t *headp, u8 *vector, u32 elsize, u32 offset, u32 index_to_add)
Definition: index_list.c:37
#define PREDICT_FALSE(x)
Definition: clib.h:97
static int index_slist_remelem_inline(index_slist_t *headp, u8 *vector, u32 elsize, u32 offset, u32 index_to_delete)
Definition: index_list.h:73
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:300
unsigned int u32
Definition: types.h:88
int index_slist_remelem(index_slist_t *headp, u8 *vector, u32 elsize, u32 offset, u32 index_to_delete)
Definition: index_list.c:56
void index_dlist_addtail(u32 head_index, u8 *vector, u32 elsize, u32 offset, u32 index_to_add)
Definition: index_list.c:83
template key/value backing page structure
Definition: bihash_doc.h:44
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
unsigned char u8
Definition: types.h:56
static void index_slist_addhead_inline(index_slist_t *headp, u8 *vector, u32 elsize, u32 offset, u32 index_to_add)
Definition: index_list.h:42
#define EMPTY
Definition: index_list.h:24
CLIB vectors are ubiquitous dynamically resized arrays with by user defined "headers".
u32 index_dlist_remelem(u32 head_index, u8 *vector, u32 elsize, u32 offset, u32 index_to_delete)
Definition: index_list.c:103