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 bool
39 {
40  TypeId tid = tag.GetInstanceTypeId ();
41  NS_LOG_FUNCTION (this << tid);
42  NS_LOG_INFO ("looking for " << tid);
43 
44  // trivial case when list is empty
45  if (m_next == 0)
46  {
47  return false;
48  }
49 
50  bool found = false;
51 
52  struct TagData ** prevNext = &m_next; // previous node's next pointer
53  struct TagData * cur = m_next; // cursor to current node
54  struct TagData * it = 0; // utility
55 
56  // Search from the head of the list until we find tid or a merge
57  while (cur != 0)
58  {
59  if (cur->count > 1)
60  {
61  // found merge
62  NS_LOG_INFO ("found initial merge before tid");
63  break;
64  }
65  else if (cur->tid == tid)
66  {
67  NS_LOG_INFO ("found tid before initial merge, calling writer");
68  found = (this->*Writer)(tag, true, cur, prevNext);
69  break;
70  }
71  else
72  {
73  // no merge or tid found yet, move on
74  prevNext = &cur->next;
75  cur = cur->next;
76  }
77  } // while !found && !cow
78 
79  // did we find it or run out of tags?
80  if (cur == 0 || found)
81  {
82  NS_LOG_INFO ("returning after header with found: " << found);
83  return found;
84  }
85 
86  // From here on out, we have to copy the list
87  // until we find tid, then link past it
88 
89  // Before we do all that work, let's make sure tid really exists
90  for (it = cur; it != 0; it = it->next)
91  {
92  if (it->tid == tid)
93  {
94  break;
95  }
96  }
97  if (it == 0)
98  {
99  // got to end of list without finding tid
100  NS_LOG_INFO ("tid not found after first merge");
101  return found;
102  }
103 
104  // At this point cur is a merge, but untested for tid
105  NS_ASSERT (cur != 0);
106  NS_ASSERT (cur->count > 1);
107 
108  /*
109  Walk the remainder of the list, copying, until we find tid
110  As we put a copy of the cur node onto our list,
111  we move the merge point down the list.
112 
113  Starting position End position
114  T1 is a merge T1.count decremented
115  T2 is a merge
116  T1' is a copy of T1
117 
118  other other
119  \ \
120  Prev -> T1 -> T2 -> ... T1 -> T2 -> ...
121  / / /|
122  pNext cur Prev -> T1' --/ |
123  / |
124  pNext cur
125 
126  When we reach tid, we link past it, decrement count, and we're done.
127  */
128 
129  // Should normally check for null cur pointer,
130  // but since we know tid exists, we'll skip this test
131  while ( /* cur && */ cur->tid != tid)
132  {
133  NS_ASSERT (cur != 0);
134  NS_ASSERT (cur->count > 1);
135  cur->count--; // unmerge cur
136  struct TagData * copy = new struct TagData ();
137  copy->tid = cur->tid;
138  copy->count = 1;
139  memcpy (copy->data, cur->data, TagData::MAX_SIZE);
140  copy->next = cur->next; // merge into tail
141  copy->next->count++; // mark new merge
142  *prevNext = copy; // point prior list at copy
143  prevNext = &copy->next; // advance
144  cur = copy->next;
145  }
146  // Sanity check:
147  NS_ASSERT (cur != 0); // cur should be non-zero
148  NS_ASSERT (cur->tid == tid); // cur->tid should be tid
149  NS_ASSERT (cur->count > 1); // cur should be a merge
150 
151  // link around tid, removing it from our list
152  found = (this->*Writer)(tag, false, cur, prevNext);
153  return found;
154 
155 }
156 
157 bool
159 {
161 }
162 
163 // COWWriter implementing Remove
164 bool
165 PacketTagList::RemoveWriter (Tag & tag, bool preMerge,
166  struct PacketTagList::TagData * cur,
167  struct PacketTagList::TagData ** prevNext)
168 {
170 
171  // found tid
172  bool found = true;
173  tag.Deserialize (TagBuffer (cur->data,
174  cur->data + TagData::MAX_SIZE));
175  *prevNext = cur->next; // link around cur
176 
177  if (preMerge)
178  {
179  // found tid before first merge, so delete cur
180  delete cur;
181  }
182  else
183  {
184  // cur is always a merge at this point
185  // unmerge cur, since we linked around it already
186  cur->count--;
187  if (cur->next != 0)
188  {
189  // there's a next, so make it a merge
190  cur->next->count++;
191  }
192  }
193  return found;
194 }
195 
196 bool
198 {
199  bool found = COWTraverse (tag, &PacketTagList::ReplaceWriter);
200  if (!found)
201  {
202  Add (tag);
203  }
204  return found;
205 }
206 
207 // COWWriter implementing Replace
208 bool
209 PacketTagList::ReplaceWriter (Tag & tag, bool preMerge,
210  struct PacketTagList::TagData * cur,
211  struct PacketTagList::TagData ** prevNext)
212 {
214 
215  // found tid
216  bool found = true;
217  if (preMerge)
218  {
219  // found tid before first merge, so just rewrite
220  tag.Serialize (TagBuffer (cur->data,
221  cur->data + tag.GetSerializedSize ()));
222  }
223  else
224  {
225  // cur is always a merge at this point
226  // need to copy, replace, and link past cur
227  cur->count--; // unmerge cur
228  struct TagData * copy = new struct TagData ();
229  copy->tid = tag.GetInstanceTypeId ();
230  copy->count = 1;
231  tag.Serialize (TagBuffer (copy->data,
232  copy->data + tag.GetSerializedSize ()));
233  copy->next = cur->next; // merge into tail
234  if (copy->next != 0)
235  {
236  copy->next->count++; // mark new merge
237  }
238  *prevNext = copy; // point prior list at copy
239  }
240  return found;
241 }
242 
243 void
244 PacketTagList::Add (const Tag &tag) const
245 {
246  NS_LOG_FUNCTION (this << tag.GetInstanceTypeId ());
247  // ensure this id was not yet added
248  for (struct TagData *cur = m_next; cur != 0; cur = cur->next)
249  {
250  NS_ASSERT_MSG (cur->tid != tag.GetInstanceTypeId (), "Error: cannot add the same kind of tag twice.");
251  }
252  struct TagData * head = new struct TagData ();
253  head->count = 1;
254  head->next = 0;
255  head->tid = tag.GetInstanceTypeId ();
256  head->next = m_next;
258  tag.Serialize (TagBuffer (head->data, head->data + tag.GetSerializedSize ()));
259 
260  const_cast<PacketTagList *> (this)->m_next = head;
261 }
262 
263 bool
265 {
266  NS_LOG_FUNCTION (this << tag.GetInstanceTypeId ());
267  TypeId tid = tag.GetInstanceTypeId ();
268  for (struct TagData *cur = m_next; cur != 0; cur = cur->next)
269  {
270  if (cur->tid == tid)
271  {
272  /* found tag */
273  tag.Deserialize (TagBuffer (cur->data, cur->data + TagData::MAX_SIZE));
274  return true;
275  }
276  }
277  /* no tag found */
278  return false;
279 }
280 
281 const struct PacketTagList::TagData *
283 {
284  return m_next;
285 }
286 
287 } /* namespace ns3 */
288 
uint8_t data[MAX_SIZE]
Serialization buffer.
bool Remove(Tag &tag)
Remove (the first instance of) tag from the list.
Size of serialization buffer data.
#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.
virtual uint32_t GetSerializedSize(void) const =0
const struct PacketTagList::TagData * Head(void) const
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:201
#define NS_LOG_INFO(msg)
Use NS_LOG to output a message of level LOG_INFO.
Definition: log.h:244
#define NS_LOG_FUNCTION_NOARGS()
Output the name of the function.
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.
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.
Defines a linked list of Packet tags, including copy-on-write semantics.
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
#define NS_ASSERT_MSG(condition, message)
At runtime, in debugging builds, if this condition is not true, the program prints the message to out...
Definition: assert.h:90
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.