Left: | ||
Right: |
OLD | NEW |
---|---|
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ | 1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ |
2 /* | 2 /* |
3 * Copyright (c) 2006 INRIA | 3 * Copyright (c) 2006 INRIA |
4 * | 4 * |
5 * This program is free software; you can redistribute it and/or modify | 5 * This program is free software; you can redistribute it and/or modify |
6 * it under the terms of the GNU General Public License version 2 as | 6 * it under the terms of the GNU General Public License version 2 as |
7 * published by the Free Software Foundation; | 7 * published by the Free Software Foundation; |
8 * | 8 * |
9 * This program is distributed in the hope that it will be useful, | 9 * This program is distributed in the hope that it will be useful, |
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of | 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
12 * GNU General Public License for more details. | 12 * GNU General Public License for more details. |
13 * | 13 * |
14 * You should have received a copy of the GNU General Public License | 14 * You should have received a copy of the GNU General Public License |
15 * along with this program; if not, write to the Free Software | 15 * along with this program; if not, write to the Free Software |
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | 16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
17 * | 17 * |
18 * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr> | 18 * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr> |
19 */ | 19 */ |
20 #ifndef PACKET_TAG_LIST_H | 20 #ifndef PACKET_TAG_LIST_H |
21 #define PACKET_TAG_LIST_H | 21 #define PACKET_TAG_LIST_H |
22 | 22 |
23 /** | |
24 \file packet-tag-list.h | |
25 \brief Defines a linked list of Packet tags, including copy-on-write semantics. | |
26 */ | |
27 | |
23 #include <stdint.h> | 28 #include <stdint.h> |
24 #include <ostream> | 29 #include <ostream> |
25 #include "ns3/type-id.h" | 30 #include "ns3/type-id.h" |
26 | 31 |
27 namespace ns3 { | 32 namespace ns3 { |
28 | 33 |
29 class Tag; | 34 class Tag; |
30 | 35 |
31 /** | 36 /** |
32 * \ingroup constants | 37 * \ingroup packet |
33 * \brief Tag maximum size | 38 * |
34 * The maximum size (in bytes) of a Tag is stored | 39 * \brief List of the packet tags stored in a packet. |
35 * in this constant. | 40 * |
41 * This class is mostly private to the Packet implementation and users | |
42 * should never have to access it directly. | |
43 * | |
44 * \intern | |
45 * | |
Jeff Y
2012/07/26 17:20:29
This class definitely is tricky to understand, esp
| |
46 * The implementation of this class is a bit tricky. Refer to this | |
47 * diagram in the discussion that follows. | |
48 * | |
49 * \dot | |
50 * digraph { | |
51 * rankdir = "LR"; | |
52 * clusterrank = local; | |
53 * node [ shape = record, fontname="FreeSans", fontsize="10" ]; | |
54 * oth [ label="<l> Other branch | <n> next | <c> ..." ]; | |
55 * PTL1 [ label="<l> PacketTagList A | <n> m_next" , shape=Mrecord]; | |
56 * PTL2 [ label="<l> PacketTagList B | <n> m_next" , shape=Mrecord]; | |
57 * oth:n -> T7:l ; | |
58 * PTL2:n -> T6:l ; | |
59 * PTL1:n -> T5:l ; | |
60 * T1 [ label="<l> T1 | <n> next | <c> count = 1" ]; | |
61 * T2 [ label="<l> T2 | <n> next | <c> count = 1" ]; | |
62 * T3 [ label="<l> T3 | <n> next | <c> count = 2" ]; | |
63 * T4 [ label="<l> T4 | <n> next | <c> count = 1" ]; | |
64 * T5 [ label="<l> T5 | <n> next | <c> count = 2" ]; | |
65 * T6 [ label="<l> T6 | <n> next | <c> count = 1" ]; | |
66 * T7 [ label="<l> T7 | <n> next | <c> count = 1" ]; | |
67 * NULL [ label="0", shape = ellipse ]; | |
68 * subgraph cluster_list { | |
69 * penwidth = 0; | |
70 * T6:n -> T5:l ; | |
71 * T5:n -> T4:l ; | |
72 * T4:n -> T3:l ; | |
73 * T7:n -> T3:l ; | |
74 * T3:n -> T2:l ; | |
75 * T2:n -> T1:l ; | |
76 * T1:n -> NULL ; | |
77 * }; | |
78 * }; | |
79 * \enddot | |
80 * | |
81 * - Tags are stored in serialized form in a tree of TagData | |
82 * structures. (<tt>T1-T7</tt> in the diagram) | |
83 * | |
84 * - Each TagData points (\c next pointers in the diagram) | |
85 * toward the root of the tree, which is a null pointer. | |
86 * | |
87 * - \c count is the number of incoming pointers to this | |
88 * TagData. Branch points, where branches merge or join, have | |
89 * <tt>count \> 1</tt> (\c T3, \c T5); successive links along | |
90 * a branch have <tt>count = 1</tt> (\c T1, \c T2, \c T4, \c T6, \c T7). | |
91 * | |
92 * - Each PacketTagList points to a specific TagData, | |
93 * which is the most recent Tag added to the packet. (<tt>T5-T7</tt>) | |
94 * | |
95 * - Conceptually, therefore, each Packet has a PacketTagList which | |
96 * points to a singly-linked list of TagData. | |
97 * | |
98 * \par <b> Copy-on-write </b> is implemented as follows: | |
99 * | |
100 * - #Add prepends the new tag to the list (growing that branch of the tree, | |
101 * as \c T6). This is a constant time operation, and does not affect | |
102 * any other #PacketTagList's, hence this is a \c const function. | |
103 * | |
104 * - Copy constructor (PacketTagList(const PacketTagList & o)) | |
105 * and assignment (#operator=(const PacketTagList & o) | |
106 * simply join the tree at the same place as the original | |
107 * PacketTagList \c o, incrementing the \c count. | |
108 * For assignment, the old branch is deleted, up to | |
109 * the first branch point, which has its \c count decremented. | |
110 * (PacketTagList \c B started as a copy of PacketTagList \c A, | |
111 * before \c T6 was added to \c B). | |
112 * | |
113 * - #Remove and #Replace are a little tricky, depending on where the | |
114 * target tag is found relative to the first branch point: | |
115 * - \e Target before <em> the first branch point: </em> \n | |
116 * The target is just dealt with in place (linked around and deleted, | |
117 * in the case of #Remove; rewritten in the case of #Replace). | |
118 * - \e Target at or after <em> the first branch point: </em> \n | |
119 * The portion of the list between the first branch and the target is | |
120 * shared. This portion is copied before the #Remove or #Replace is | |
121 * performed. | |
122 * | |
123 * \par <b> Memory Management: </b> | |
124 * \n | |
125 * Packet tags must serialize to a finite maximum size, see TagData | |
126 * | |
127 * This documentation entitles the original author to a free beer. | |
36 */ | 128 */ |
37 #define PACKET_TAG_MAX_SIZE 20 | 129 class PacketTagList |
38 | |
39 class PacketTagList | |
40 { | 130 { |
41 public: | 131 public: |
42 struct TagData { | 132 /** |
43 uint8_t data[PACKET_TAG_MAX_SIZE]; | 133 * Tree node for sharing serialized tags. |
44 struct TagData *next; | 134 * |
45 TypeId tid; | 135 * See PacketTagList for a discussion of the data structure. |
46 uint32_t count; | 136 * |
47 }; | 137 * See TagData::TagData_e for a discussion of the size limit on |
48 | 138 * tag serialization. |
139 */ | |
140 struct TagData | |
141 { | |
142 /** | |
143 * \brief Packet Tag maximum size | |
144 * | |
145 * The maximum size (in bytes) of a Tag is stored | |
146 * in this constant. | |
147 * | |
148 * \intern | |
149 * Ideally, TagData would be 32 bytes in size, so they require | |
150 * no padding on 64-bit architectures. (The architecture | |
151 * affects the size because of the \c #next pointer.) | |
152 * This would leave 18 bytes for \c #data. However, | |
153 * ns3:Ipv6PacketInfoTag needs 19 bytes! The current | |
154 * implementation allows 20 bytes, which gives TagData | |
155 * a size of 30 bytes on 32-byte machines (which gets | |
156 * padded with 2 bytes), and 34 bytes on 64-bit machines, which | |
157 * gets padded to 40 bytes. | |
158 */ | |
159 enum TagData_e | |
160 { | |
161 MAX_SIZE = 20 /**< Size of serialization buffer #data */ | |
162 }; | |
163 | |
164 uint8_t data[MAX_SIZE]; /**< Serialization buffer */ | |
165 struct TagData * next; /**< Pointer to next in list */ | |
166 TypeId tid; /**< Type of the tag serialized into #data */ | |
167 uint32_t count; /**< Number of incoming links */ | |
168 }; /* struct TagData */ | |
169 | |
170 /** | |
171 * Create a new PacketTagList. | |
172 */ | |
49 inline PacketTagList (); | 173 inline PacketTagList (); |
174 /** | |
175 * Copy constructor | |
176 * | |
177 * \param [in] o The PacketTagList to copy. | |
178 * | |
179 * This makes a light-weight copy by #RemoveAll, then | |
180 * pointing to the same #struct TagData as \pname{o}. | |
181 */ | |
50 inline PacketTagList (PacketTagList const &o); | 182 inline PacketTagList (PacketTagList const &o); |
183 /** | |
184 * Assignment | |
185 * | |
186 * \param [in] o The PacketTagList to copy. | |
187 * | |
188 * This makes a light-weight copy by #RemoveAll, then | |
189 * pointing to the same #struct TagData as \pname{o}. | |
190 */ | |
51 inline PacketTagList &operator = (PacketTagList const &o); | 191 inline PacketTagList &operator = (PacketTagList const &o); |
192 /** | |
193 * Destructor | |
194 * | |
195 * #RemoveAll's the tags up to the first merge. | |
196 */ | |
52 inline ~PacketTagList (); | 197 inline ~PacketTagList (); |
53 | 198 |
199 /** | |
200 * Add a tag to the head of this branch. | |
201 * | |
202 * \param [in] tag The tag to add | |
203 */ | |
54 void Add (Tag const&tag) const; | 204 void Add (Tag const&tag) const; |
205 /** | |
206 * Remove (the first instance of) tag from the list. | |
207 * | |
208 * \param [in,out] tag The tag type to remove. If found, | |
209 * \pname{tag} is set to the value of the tag found. | |
210 * \returns True if \pname{tag} is found, false otherwise. | |
211 */ | |
55 bool Remove (Tag &tag); | 212 bool Remove (Tag &tag); |
213 /** | |
214 * Replace the value of a tag. | |
215 * | |
216 * \param [in] tag The tag type to replace. To get the old | |
217 * value of the tag, use #Peek first. | |
218 * \returns True if \pname{tag} is found, false otherwise. | |
219 * If \pname{tag} wasn't found, Add is performed instead (so | |
220 * the list is guaranteed to have the new tag value either way). | |
221 */ | |
222 bool Replace (Tag &tag); | |
223 /** | |
224 * Find a tag and return its value. | |
225 * | |
226 * \param [in,out] tag The tag type to find. If found, | |
227 * \pname{tag} is set to the value of the tag found. | |
228 * \returns True if \pname{tag} is found, false otherwise. | |
229 */ | |
56 bool Peek (Tag &tag) const; | 230 bool Peek (Tag &tag) const; |
231 /** | |
232 * Remove all tags from this list (up to the first merge). | |
233 */ | |
57 inline void RemoveAll (void); | 234 inline void RemoveAll (void); |
58 | 235 /** |
236 * \returns pointer to head of tag list | |
237 */ | |
59 const struct PacketTagList::TagData *Head (void) const; | 238 const struct PacketTagList::TagData *Head (void) const; |
60 | 239 |
61 private: | 240 private: |
62 | 241 /** |
63 bool Remove (TypeId tid); | 242 * Typedef of method function pointer for copy-on-write operations |
64 struct PacketTagList::TagData *AllocData (void) const; | 243 * |
65 void FreeData (struct TagData *data) const; | 244 * \param [in] tag The tag type to operate on. |
66 | 245 * \param [in] preMerge True if \pname{tag} was found before the first merge, |
67 static struct PacketTagList::TagData *g_free; | 246 * false otherwise. |
68 static uint32_t g_nfree; | 247 * \param [in] cur Pointer to the tag. |
69 | 248 * \param [in] prevNext Pointer to the struct TagData.next pointer |
249 * pointing to \pname{cur}. | |
250 * \returns True if operation successful, false otherwise | |
251 */ | |
252 typedef bool (PacketTagList::*COWWriter_fp) | |
Mathieu Lacage
2012/07/28 08:01:19
I am not a big fan of the _fp postfix...
| |
253 (Tag & tag, bool preMerge, | |
254 struct TagData * cur, struct TagData ** prevNext); | |
255 /** | |
256 * Traverse the list implementing copy-on-write, using \pname{Writer}. | |
257 * | |
258 * \param [in] tag The tag type to operate on. | |
259 * \param [in] Writer The copy-on-write function to use. | |
260 * \returns True if \pname{tag} found, false otherwise. | |
261 */ | |
262 bool COWTraverse (Tag & tag, PacketTagList::COWWriter_fp Writer); | |
263 /** | |
264 * Copy-on-write implementing Remove. | |
265 * | |
266 * \param [in] tag The target tag type to remove. | |
267 * \param [in] preMerge True if \pname{tag} was found before the first merge, | |
268 * false otherwise. | |
269 * \param [in] cur Pointer to the tag. | |
270 * \param [in] prevNext Pointer to the struct TagData.next pointer | |
271 * pointing to \pname{cur}. | |
272 * \returns True, since tag will definitely be removed. | |
273 */ | |
274 bool RemoveWriter (Tag & tag, bool preMerge, | |
275 struct TagData * cur, struct TagData ** prevNext); | |
276 /** | |
277 * Copy-on-write implementing Replace | |
278 * | |
279 * \param [in] tag The target tag type to replace | |
280 * \param [in] preMerge True if \pname{tag} was found before the first merge, | |
281 * false otherwise. | |
282 * \param [in] cur Pointer to the tag | |
283 * \param [in] prevNext Pointer to the struct TagData.next pointer | |
284 * pointing to \pname{cur}. | |
285 * \returns True, since tag value will definitely be replaced. | |
286 */ | |
287 bool ReplaceWriter (Tag & tag, bool preMerge, struct TagData * cur, struct Tag Data ** prevNext); | |
288 | |
289 /** | |
290 * Pointer to first #struct TagData on the list | |
291 */ | |
70 struct TagData *m_next; | 292 struct TagData *m_next; |
71 }; | 293 }; |
72 | 294 |
73 } // namespace ns3 | 295 } // namespace ns3 |
74 | 296 |
75 /**************************************************** | 297 /**************************************************** |
76 * Implementation of inline methods for performance | 298 * Implementation of inline methods for performance |
77 ****************************************************/ | 299 ****************************************************/ |
78 | 300 |
79 namespace ns3 { | 301 namespace ns3 { |
(...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
120 struct TagData *prev = 0; | 342 struct TagData *prev = 0; |
121 for (struct TagData *cur = m_next; cur != 0; cur = cur->next)· | 343 for (struct TagData *cur = m_next; cur != 0; cur = cur->next)· |
122 { | 344 { |
123 cur->count--; | 345 cur->count--; |
124 if (cur->count > 0)· | 346 if (cur->count > 0)· |
125 { | 347 { |
126 break; | 348 break; |
127 } | 349 } |
128 if (prev != 0)· | 350 if (prev != 0)· |
129 { | 351 { |
130 FreeData (prev); | 352 delete prev; |
131 } | 353 } |
132 prev = cur; | 354 prev = cur; |
133 } | 355 } |
134 if (prev != 0)· | 356 if (prev != 0)· |
135 { | 357 { |
136 FreeData (prev); | 358 delete prev; |
137 } | 359 } |
138 m_next = 0; | 360 m_next = 0; |
139 } | 361 } |
140 | 362 |
141 } // namespace ns3 | 363 } // namespace ns3 |
142 | 364 |
143 #endif /* PACKET_TAG_LIST_H */ | 365 #endif /* PACKET_TAG_LIST_H */ |
OLD | NEW |