FD.io VPP  v17.01-9-ge7dcee4
Vector Packet Processing
index_list.h
Go to the documentation of this file.
1 /*
2  *------------------------------------------------------------------
3  * index_list.h - vector-index-based doubly-linked lists
4  *
5  * Copyright (c) 2008-2009 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 #ifndef _INDEX_LIST_H_
21 #define _INDEX_LIST_H_ 1
22 
23 /* An index we can't possibly see in practice... */
24 #define EMPTY ((u32)~0)
25 
26 typedef struct index_slist_ {
29 
30 /*
31  * index_slist_addhead
32  *
33  * args: headp -- pointer to e.g. a hash bucket
34  * vector -- vector containing the list
35  * elsize -- size of an element in this vector
36  * offset -- offset in each vector element of this list thread
37  * index_to_add -- index in the vector to add to the list
38  *
39  * Adds new items to the head of the list. Try not to screw up the args!
40  */
41 static inline void
43  u8 *vector, u32 elsize,
44  u32 offset, u32 index_to_add)
45 {
46  index_slist_t *addme;
47 
48  addme = (index_slist_t *)(vector + offset + elsize*index_to_add);
49  addme->next = EMPTY;
50 
51  if (headp->next == EMPTY) {
52  headp->next = index_to_add;
53  return;
54  } else {
55  addme->next = headp->next;
56  headp->next = index_to_add;
57  }
58 }
59 
60 /*
61  * index_slist_remelem
62  *
63  * args: headp -- pointer to e.g. a hash bucket
64  * vector -- vector containing the list
65  * elsize -- size of an element in this vector
66  * offset -- offset in each vector element of this list thread
67  * index_to_del -- index in the vector to delete from the list
68  *
69  * Try not to screw up the args!
70  */
71 
72 static inline int
74  u8 *vector, u32 elsize,
75  u32 offset, u32 index_to_delete)
76 {
77  index_slist_t *findme;
78  index_slist_t *prev;
79  index_slist_t *cur;
80 
81  findme = (index_slist_t *)(vector + offset + elsize*index_to_delete);
82 
83  if (headp->next == index_to_delete) {
84  headp->next = findme->next;
85  findme->next = EMPTY;
86  return 0;
87  }
88 
89  prev = (index_slist_t *)(vector + offset + elsize*headp->next);
90  cur = (index_slist_t *)(vector + offset + elsize*prev->next);
91  while (cur != findme) {
92  if (cur->next == EMPTY)
93  return (1);
94  prev = cur;
95  cur = (index_slist_t *)(vector + offset + elsize*cur->next);
96  }
97  prev->next = findme->next;
98  findme->next = EMPTY;
99  return 0;
100 }
101 
102 void index_slist_addhead (index_slist_t *headp,
103  u8 *vector, u32 elsize, u32 offset, u32 index);
105  u8 *vector, u32 elsize, u32 offset, u32 index);
106 
107 typedef struct index_dlist_ {
110 } index_dlist_t;
111 
112 void index_dlist_addtail (u32 head_index, u8 *vector, u32 elsize,
113  u32 offset, u32 index_to_add);
114 
115 u32 index_dlist_remelem (u32 head_index,
116  u8 *vector, u32 elsize, u32 offset,
117  u32 index_to_delete);
118 #endif /* _INDEX_LIST_H_ */
struct index_slist_ index_slist_t
struct index_dlist_ index_dlist_t
void index_dlist_addtail(u32 head_index, u8 *vector, u32 elsize, u32 offset, u32 index_to_add)
Definition: index_list.c:83
void index_slist_addhead(index_slist_t *headp, u8 *vector, u32 elsize, u32 offset, u32 index)
Definition: index_list.c:37
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
unsigned int u32
Definition: types.h:88
int index_slist_remelem(index_slist_t *headp, u8 *vector, u32 elsize, u32 offset, u32 index)
Definition: index_list.c:56
template key/value backing page structure
Definition: bihash_doc.h:44
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
u32 index_dlist_remelem(u32 head_index, u8 *vector, u32 elsize, u32 offset, u32 index_to_delete)
Definition: index_list.c:103