A Discrete-Event Network Simulator
API
packet-tag-list.cc
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2006 INRIA
4  *
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
7  * published by the Free Software Foundation;
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
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
16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17  *
18  * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
19  */
20 
26 #include "packet-tag-list.h"
27 #include "tag-buffer.h"
28 #include "tag.h"
29 #include "ns3/fatal-error.h"
30 #include "ns3/log.h"
31 #include <cstring>
32 
33 namespace ns3 {
34 
35 NS_LOG_COMPONENT_DEFINE ("PacketTagList");
36 
37 PacketTagList::TagData *
39 {
40  NS_ASSERT_MSG (dataSize
41  < std::numeric_limits<decltype(TagData::size)>::max (),
42  "Requested TagData size " << dataSize
43  << " exceeds maximum "
44  << std::numeric_limits<decltype(TagData::size)>::max () );
45 
46  void * p = std::malloc (sizeof (TagData) + dataSize - 1);
47  // The matching frees are in RemoveAll and RemoveWriter
48 
49  TagData * tag = new (p) TagData;
50  tag->size = dataSize;
51  return tag;
52 }
53 
54 bool
56 {
57  TypeId tid = tag.GetInstanceTypeId ();
58  NS_LOG_FUNCTION (this << tid);
59  NS_LOG_INFO ("looking for " << tid);
60 
61  // trivial case when list is empty
62  if (m_next == 0)
63  {
64  return false;
65  }
66 
67  bool found = false;
68 
69  struct TagData ** prevNext = &m_next; // previous node's next pointer
70  struct TagData * cur = m_next; // cursor to current node
71  struct TagData * it = 0; // utility
72 
73  // Search from the head of the list until we find tid or a merge
74  while (cur != 0)
75  {
76  if (cur->count > 1)
77  {
78  // found merge
79  NS_LOG_INFO ("found initial merge before tid");
80  break;
81  }
82  else if (cur->tid == tid)
83  {
84  NS_LOG_INFO ("found tid before initial merge, calling writer");
85  found = (this->*Writer)(tag, true, cur, prevNext);
86  break;
87  }
88  else
89  {
90  // no merge or tid found yet, move on
91  prevNext = &cur->next;
92  cur = cur->next;
93  }
94  } // while !found && !cow
95 
96  // did we find it or run out of tags?
97  if (cur == 0 || found)
98  {
99  NS_LOG_INFO ("returning after header with found: " << found);
100  return found;
101  }
102 
103  // From here on out, we have to copy the list
104  // until we find tid, then link past it
105 
106  // Before we do all that work, let's make sure tid really exists
107  for (it = cur; it != 0; it = it->next)
108  {
109  if (it->tid == tid)
110  {
111  break;
112  }
113  }
114  if (it == 0)
115  {
116  // got to end of list without finding tid
117  NS_LOG_INFO ("tid not found after first merge");
118  return found;
119  }
120 
121  // At this point cur is a merge, but untested for tid
122  NS_ASSERT (cur != 0);
123  NS_ASSERT (cur->count > 1);
124 
125  /*
126  Walk the remainder of the list, copying, until we find tid
127  As we put a copy of the cur node onto our list,
128  we move the merge point down the list.
129 
130  Starting position End position
131  T1 is a merge T1.count decremented
132  T2 is a merge
133  T1' is a copy of T1
134 
135  other other
136  \ \
137  Prev -> T1 -> T2 -> ... T1 -> T2 -> ...
138  / / /|
139  pNext cur Prev -> T1' --/ |
140  / |
141  pNext cur
142 
143  When we reach tid, we link past it, decrement count, and we're done.
144  */
145 
146  // Should normally check for null cur pointer,
147  // but since we know tid exists, we'll skip this test
148  while ( /* cur && */ cur->tid != tid)
149  {
150  NS_ASSERT (cur != 0);
151  NS_ASSERT (cur->count > 1);
152  cur->count--; // unmerge cur
153  struct TagData * copy = CreateTagData (cur->size);
154  copy->tid = cur->tid;
155  copy->count = 1;
156  copy->size = cur->size;
157  memcpy (copy->data, cur->data, copy->size);
158  copy->next = cur->next; // merge into tail
159  copy->next->count++; // mark new merge
160  *prevNext = copy; // point prior list at copy
161  prevNext = &copy->next; // advance
162  cur = copy->next;
163  }
164  // Sanity check:
165  NS_ASSERT (cur != 0); // cur should be non-zero
166  NS_ASSERT (cur->tid == tid); // cur->tid should be tid
167  NS_ASSERT (cur->count > 1); // cur should be a merge
168 
169  // link around tid, removing it from our list
170  found = (this->*Writer)(tag, false, cur, prevNext);
171  return found;
172 
173 }
174 
175 bool
177 {
179 }
180 
181 // COWWriter implementing Remove
182 bool
183 PacketTagList::RemoveWriter (Tag & tag, bool preMerge,
184  struct PacketTagList::TagData * cur,
185  struct PacketTagList::TagData ** prevNext)
186 {
188 
189  // found tid
190  bool found = true;
191  tag.Deserialize (TagBuffer (cur->data, cur->data + cur->size));
192  *prevNext = cur->next; // link around cur
193 
194  if (preMerge)
195  {
196  // found tid before first merge, so delete cur
197  cur->~TagData ();
198  std::free (cur);
199  }
200  else
201  {
202  // cur is always a merge at this point
203  // unmerge cur, since we linked around it already
204  cur->count--;
205  if (cur->next != 0)
206  {
207  // there's a next, so make it a merge
208  cur->next->count++;
209  }
210  }
211  return found;
212 }
213 
214 bool
216 {
217  bool found = COWTraverse (tag, &PacketTagList::ReplaceWriter);
218  if (!found)
219  {
220  Add (tag);
221  }
222  return found;
223 }
224 
225 // COWWriter implementing Replace
226 bool
227 PacketTagList::ReplaceWriter (Tag & tag, bool preMerge,
228  struct PacketTagList::TagData * cur,
229  struct PacketTagList::TagData ** prevNext)
230 {
232 
233  // found tid
234  bool found = true;
235  if (preMerge)
236  {
237  // found tid before first merge, so just rewrite
238  tag.Serialize (TagBuffer (cur->data, cur->data + cur->size));
239  }
240  else
241  {
242  // cur is always a merge at this point
243  // need to copy, replace, and link past cur
244  cur->count--; // unmerge cur
245  struct TagData * copy = CreateTagData (tag.GetSerializedSize ());
246  copy->tid = tag.GetInstanceTypeId ();
247  copy->count = 1;
248  tag.Serialize (TagBuffer (copy->data, copy->data + copy->size));
249  copy->next = cur->next; // merge into tail
250  if (copy->next != 0)
251  {
252  copy->next->count++; // mark new merge
253  }
254  *prevNext = copy; // point prior list at copy
255  }
256  return found;
257 }
258 
259 void
260 PacketTagList::Add (const Tag &tag) const
261 {
262  NS_LOG_FUNCTION (this << tag.GetInstanceTypeId ());
263  // ensure this id was not yet added
264  for (struct TagData *cur = m_next; cur != 0; cur = cur->next)
265  {
266  NS_ASSERT_MSG (cur->tid != tag.GetInstanceTypeId (),
267  "Error: cannot add the same kind of tag twice.");
268  }
269  struct TagData * head = CreateTagData (tag.GetSerializedSize ());
270  head->count = 1;
271  head->next = 0;
272  head->tid = tag.GetInstanceTypeId ();
273  head->next = m_next;
274  tag.Serialize (TagBuffer (head->data, head->data + head->size));
275 
276  const_cast<PacketTagList *> (this)->m_next = head;
277 }
278 
279 bool
281 {
282  NS_LOG_FUNCTION (this << tag.GetInstanceTypeId ());
283  TypeId tid = tag.GetInstanceTypeId ();
284  for (struct TagData *cur = m_next; cur != 0; cur = cur->next)
285  {
286  if (cur->tid == tid)
287  {
288  /* found tag */
289  tag.Deserialize (TagBuffer (cur->data, cur->data + cur->size));
290  return true;
291  }
292  }
293  /* no tag found */
294  return false;
295 }
296 
297 const struct PacketTagList::TagData *
299 {
300  return m_next;
301 }
302 
303 } /* namespace ns3 */
304 
bool Remove(Tag &tag)
Remove (the first instance of) tag from the list.
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by "...
struct TagData * next
Pointer to next in list.
NS_ASSERT_MSG(false, "Ipv4AddressGenerator::MaskToIndex(): Impossible")
virtual uint32_t GetSerializedSize(void) const =0
List of the packet tags stored in a packet.
#define NS_ASSERT(condition)
At runtime, in debugging builds, if this condition is not true, the program prints the source file...
Definition: assert.h:67
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:205
#define NS_LOG_INFO(msg)
Use NS_LOG to output a message of level LOG_INFO.
Definition: log.h:281
#define NS_LOG_FUNCTION_NOARGS()
Output the name of the function.
const struct PacketTagList::TagData * Head(void) const
static TagData * CreateTagData(size_t dataSize)
Allocate and construct a TagData struct, sizing the data area large enough to serialize dataSize byte...
bool ReplaceWriter(Tag &tag, bool preMerge, struct TagData *cur, struct TagData **prevNext)
Copy-on-write implementing Replace.
Tree node for sharing serialized tags.
bool(PacketTagList::* COWWriter)(Tag &tag, bool preMerge, struct TagData *cur, struct TagData **prevNext)
Typedef of method function pointer for copy-on-write operations.
bool Replace(Tag &tag)
Replace the value of a tag.
bool RemoveWriter(Tag &tag, bool preMerge, struct TagData *cur, struct TagData **prevNext)
Copy-on-write implementing Remove.
uint32_t size
Size of the data buffer.
Defines a linked list of Packet tags, including copy-on-write semantics.
uint8_t data[1]
Serialization buffer.
virtual void Serialize(TagBuffer i) const =0
tag a set of bytes in a packet
Definition: tag.h:36
bool COWTraverse(Tag &tag, PacketTagList::COWWriter Writer)
Traverse the list implementing copy-on-write, using Writer.
struct TagData * m_next
Pointer to first TagData on the list.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
virtual void Deserialize(TagBuffer i)=0
bool Peek(Tag &tag) const
Find a tag and return its value.
void Add(Tag const &tag) const
Add a tag to the head of this branch.
double max(double x, double y)
read and write tag data
Definition: tag-buffer.h:51
virtual TypeId GetInstanceTypeId(void) const =0
Get the most derived TypeId for this Object.
TypeId tid
Type of the tag serialized into data.
a unique identifier for an interface.
Definition: type-id.h:58
uint32_t count
Number of incoming links.