BadVPN – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /**
2 * @file IndexedList.h
3 * @author Ambroz Bizjak <ambrop7@gmail.com>
4 *
5 * @section LICENSE
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * 3. Neither the name of the author nor the
15 * names of its contributors may be used to endorse or promote products
16 * derived from this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
20 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
22 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
23 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
24 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
25 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
27 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 *
29 * @section DESCRIPTION
30 *
31 * A data structure similar to a list, but with efficient index-based access.
32 */
33  
34 #ifndef BADVPN_INDEXEDLIST_H
35 #define BADVPN_INDEXEDLIST_H
36  
37 #include <stddef.h>
38 #include <stdint.h>
39  
40 #include <misc/offset.h>
41 #include <misc/debug.h>
42 #include <structure/CAvl.h>
43  
44 typedef struct IndexedList_s IndexedList;
45 typedef struct IndexedListNode_s IndexedListNode;
46  
47 typedef IndexedListNode *IndexedList__tree_link;
48  
49 #include "IndexedList_tree.h"
50 #include <structure/CAvl_decl.h>
51  
52 struct IndexedList_s {
53 IndexedList__Tree tree;
54 };
55  
56 struct IndexedListNode_s {
57 IndexedListNode *tree_child[2];
58 IndexedListNode *tree_parent;
59 int8_t tree_balance;
60 uint64_t tree_count;
61 };
62  
63 /**
64 * Initializes the indexed list.
65 *
66 * @param o uninitialized list object to initialize
67 */
68 static void IndexedList_Init (IndexedList *o);
69  
70 /**
71 * Inserts a node into the indexed list.
72 *
73 * @param o indexed list to insert into
74 * @param node uninitialized node to insert
75 * @param index index to insert at (starting with zero). Any existing elements
76 * at or after this index will be shifted forward, i.e. their
77 * indices will be incremented by one. Must be <=count.
78 */
79 static void IndexedList_InsertAt (IndexedList *o, IndexedListNode *node, uint64_t index);
80  
81 /**
82 * Removes a nove from the indexed list.
83 *
84 * @param o indexed list to remove from
85 * @param node node in the list to remove
86 */
87 static void IndexedList_Remove (IndexedList *o, IndexedListNode *node);
88  
89 /**
90 * Returns the number of nodes in the indexed list.
91 *
92 * @param o indexed list
93 * @return number of nodes
94 */
95 static uint64_t IndexedList_Count (IndexedList *o);
96  
97 /**
98 * Returns the index of a node in the indexed list.
99 *
100 * @param o indexed list
101 * @param node node in the list to get index of
102 * @return index of the node
103 */
104 static uint64_t IndexedList_IndexOf (IndexedList *o, IndexedListNode *node);
105  
106 /**
107 * Returns the node at the specified index in the indexed list.
108 *
109 * @param o indexed list
110 * @param index index of the node to return. Must be < count.
111 * @return node at the specified index
112 */
113 static IndexedListNode * IndexedList_GetAt (IndexedList *o, uint64_t index);
114  
115 /**
116 * Returns the first node, or NULL if the list is empty.
117 *
118 * @param o indexed list
119 * @return first node, or NULL
120 */
121 static IndexedListNode * IndexedList_GetFirst (IndexedList *o);
122  
123 /**
124 * Returns the last node, or NULL if the list is empty.
125 *
126 * @param o indexed list
127 * @return last node, or NULL
128 */
129 static IndexedListNode * IndexedList_GetLast (IndexedList *o);
130  
131 /**
132 * Returns the next node of a given node, or NULL this is the last node.
133 *
134 * @param o indexed list
135 * @param node existing node
136 * @return next node, or NULL
137 */
138 static IndexedListNode * IndexedList_GetNext (IndexedList *o, IndexedListNode *node);
139  
140 /**
141 * Returns the previous node of a given node, or NULL this is the first node.
142 *
143 * @param o indexed list
144 * @param node existing node
145 * @return previous node, or NULL
146 */
147 static IndexedListNode * IndexedList_GetPrev (IndexedList *o, IndexedListNode *node);
148  
149 #include "IndexedList_tree.h"
150 #include <structure/CAvl_impl.h>
151  
152 static IndexedListNode * IndexedList__deref (IndexedList__TreeRef ref)
153 {
154 return ref.link;
155 }
156  
157 static void IndexedList_Init (IndexedList *o)
158 {
159 IndexedList__Tree_Init(&o->tree);
160 }
161  
162 static void IndexedList_InsertAt (IndexedList *o, IndexedListNode *node, uint64_t index)
163 {
164 ASSERT(index <= IndexedList__Tree_Count(&o->tree, 0))
165 ASSERT(IndexedList__Tree_Count(&o->tree, 0) < UINT64_MAX - 1)
166  
167 uint64_t orig_count = IndexedList__Tree_Count(&o->tree, 0);
168 B_USE(orig_count)
169  
170 IndexedList__Tree_InsertAt(&o->tree, 0, IndexedList__TreeDeref(0, node), index);
171  
172 ASSERT(IndexedList__Tree_IndexOf(&o->tree, 0, IndexedList__TreeDeref(0, node)) == index)
173 ASSERT(IndexedList__Tree_Count(&o->tree, 0) == orig_count + 1)
174 }
175  
176 static void IndexedList_Remove (IndexedList *o, IndexedListNode *node)
177 {
178 IndexedList__Tree_Remove(&o->tree, 0, IndexedList__TreeDeref(0, node));
179 }
180  
181 static uint64_t IndexedList_Count (IndexedList *o)
182 {
183 return IndexedList__Tree_Count(&o->tree, 0);
184 }
185  
186 static uint64_t IndexedList_IndexOf (IndexedList *o, IndexedListNode *node)
187 {
188 return IndexedList__Tree_IndexOf(&o->tree, 0, IndexedList__TreeDeref(0, node));
189 }
190  
191 static IndexedListNode * IndexedList_GetAt (IndexedList *o, uint64_t index)
192 {
193 ASSERT(index < IndexedList__Tree_Count(&o->tree, 0))
194  
195 IndexedList__TreeRef ref = IndexedList__Tree_GetAt(&o->tree, 0, index);
196 ASSERT(!IndexedList__TreeIsNullRef(ref))
197  
198 return ref.ptr;
199 }
200  
201 static IndexedListNode * IndexedList_GetFirst (IndexedList *o)
202 {
203 return IndexedList__deref(IndexedList__Tree_GetFirst(&o->tree, 0));
204 }
205  
206 static IndexedListNode * IndexedList_GetLast (IndexedList *o)
207 {
208 return IndexedList__deref(IndexedList__Tree_GetLast(&o->tree, 0));
209 }
210  
211 static IndexedListNode * IndexedList_GetNext (IndexedList *o, IndexedListNode *node)
212 {
213 ASSERT(node)
214  
215 return IndexedList__deref(IndexedList__Tree_GetNext(&o->tree, 0, IndexedList__TreeDeref(0, node)));
216 }
217  
218 static IndexedListNode * IndexedList_GetPrev (IndexedList *o, IndexedListNode *node)
219 {
220 ASSERT(node)
221  
222 return IndexedList__deref(IndexedList__Tree_GetPrev(&o->tree, 0, IndexedList__TreeDeref(0, node)));
223 }
224  
225 #endif