NS-3 based Named Data Networking (NDN) simulator
ndnSIM: NDN, CCN, CCNx, content centric networks
API Documentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
exclude.cc
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
2 /*
3  * Copyright (c) 2013, Regents of the University of California
4  * Alexander Afanasyev
5  *
6  * BSD license, See the LICENSE file for more information
7  *
8  * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
9  */
10 
11 #include "exclude.h"
12 
13 #include "detail/error.h"
14 
15 NDN_NAMESPACE_BEGIN
16 
17 Exclude::Exclude ()
18 {
19 }
20 
21 // example: ANY /b /d ANY /f
22 //
23 // ordered in map as:
24 //
25 // /f (false); /d (true); /b (false); / (true)
26 //
27 // lower_bound (/) -> / (true) <-- excluded (equal)
28 // lower_bound (/a) -> / (true) <-- excluded (any)
29 // lower_bound (/b) -> /b (false) <--- excluded (equal)
30 // lower_bound (/c) -> /b (false) <--- not excluded (not equal and no ANY)
31 // lower_bound (/d) -> /d (true) <- excluded
32 // lower_bound (/e) -> /d (true) <- excluded
33 bool
34 Exclude::isExcluded (const name::Component &comp) const
35 {
36  const_iterator lowerBound = m_exclude.lower_bound (comp);
37  if (lowerBound == end ())
38  return false;
39 
40  if (lowerBound->second)
41  return true;
42  else
43  return lowerBound->first == comp;
44 
45  return false;
46 }
47 
48 Exclude &
49 Exclude::excludeOne (const name::Component &comp)
50 {
51  if (!isExcluded (comp))
52  {
53  m_exclude.insert (std::make_pair (comp, false));
54  }
55  return *this;
56 }
57 
58 
59 // example: ANY /b0 /d0 ANY /f0
60 //
61 // ordered in map as:
62 //
63 // /f0 (false); /d0 (true); /b0 (false); / (true)
64 //
65 // lower_bound (/) -> / (true) <-- excluded (equal)
66 // lower_bound (/a0) -> / (true) <-- excluded (any)
67 // lower_bound (/b0) -> /b0 (false) <--- excluded (equal)
68 // lower_bound (/c0) -> /b0 (false) <--- not excluded (not equal and no ANY)
69 // lower_bound (/d0) -> /d0 (true) <- excluded
70 // lower_bound (/e0) -> /d0 (true) <- excluded
71 
72 
73 // examples with desired outcomes
74 // excludeRange (/, /f0) -> ANY /f0
75 // /f0 (false); / (true)
76 // excludeRange (/, /f1) -> ANY /f1
77 // /f1 (false); / (true)
78 // excludeRange (/a0, /e0) -> ANY /f0
79 // /f0 (false); / (true)
80 // excludeRange (/a0, /e0) -> ANY /f0
81 // /f0 (false); / (true)
82 
83 // excludeRange (/b1, /c0) -> ANY /b0 /b1 ANY /c0 /d0 ANY /f0
84 // /f0 (false); /d0 (true); /c0 (false); /b1 (true); /b0 (false); / (true)
85 
86 Exclude &
87 Exclude::excludeRange (const name::Component &from, const name::Component &to)
88 {
89  if (from >= to)
90  {
91  BOOST_THROW_EXCEPTION (error::Exclude ()
92  << error::msg ("Invalid exclude range (for single name exclude use Exclude::excludeOne)")
93  << error::msg (from.toUri ())
94  << error::msg (to.toUri ()));
95  }
96 
97  iterator newFrom = m_exclude.lower_bound (from);
98  if (newFrom == end () || !newFrom->second /*without ANY*/)
99  {
100  std::pair<iterator, bool> fromResult = m_exclude.insert (std::make_pair (from, true));
101  newFrom = fromResult.first;
102  if (!fromResult.second)
103  {
104  // this means that the lower bound is equal to the item itself. So, just update ANY flag
105  newFrom->second = true;
106  }
107  }
108  // else
109  // nothing special if start of the range already exists with ANY flag set
110 
111  iterator newTo = m_exclude.lower_bound (to); // !newTo cannot be end ()
112  if (newTo == newFrom || !newTo->second)
113  {
114  std::pair<iterator, bool> toResult = m_exclude.insert (std::make_pair (to, false));
115  newTo = toResult.first;
116  ++ newTo;
117  }
118  else
119  {
120  // nothing to do really
121  }
122 
123  m_exclude.erase (newTo, newFrom); // remove any intermediate node, since all of the are excluded
124 
125  return *this;
126 }
127 
128 Exclude &
129 Exclude::excludeAfter (const name::Component &from)
130 {
131  iterator newFrom = m_exclude.lower_bound (from);
132  if (newFrom == end () || !newFrom->second /*without ANY*/)
133  {
134  std::pair<iterator, bool> fromResult = m_exclude.insert (std::make_pair (from, true));
135  newFrom = fromResult.first;
136  if (!fromResult.second)
137  {
138  // this means that the lower bound is equal to the item itself. So, just update ANY flag
139  newFrom->second = true;
140  }
141  }
142  // else
143  // nothing special if start of the range already exists with ANY flag set
144 
145  if (newFrom != m_exclude.begin ())
146  {
147  m_exclude.erase (m_exclude.begin (), newFrom); // remove any intermediate node, since all of the are excluded
148  }
149 
150  return *this;
151 }
152 
153 void
154 Exclude::appendExclude (const name::Component &name, bool any)
155 {
156  m_exclude.insert (std::make_pair (name, any));
157 }
158 
159 std::ostream&
160 operator << (std::ostream &os, const Exclude &exclude)
161 {
162  for (Exclude::const_reverse_iterator i = exclude.rbegin (); i != exclude.rend (); i++)
163  {
164  os << i->first.toUri () << " ";
165  if (i->second)
166  os << "----> ";
167  }
168  return os;
169 }
170 
171 NDN_NAMESPACE_END
An error with Exclude.
Definition: error.h:52
const_reverse_iterator rbegin() const
Get begin iterator of the exclude terms.
Definition: exclude.h:160
std::string toUri() const
Convert binary blob name component to std::string, escaping all non-printable characters in URI forma...
Class to represent Exclude component in NDN interests.
Definition: exclude.h:25
boost::error_info< struct tag_msg, std::string > msg
Free-formatted text message explaining the error.
Definition: error.h:75
This file defines basic elements for the library reporting.
const_reverse_iterator rend() const
Get end iterator of the exclude terms.
Definition: exclude.h:166
Class to representing binary blob of NDN name component.