00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #ifndef WIFI_FRAME_FILTER_INTERSECTOR_HXX_
00023 # define WIFI_FRAME_FILTER_INTERSECTOR_HXX_
00024
00025 # include <iostream>
00026
00027 # include "intersector.hh"
00028
00029 # include <wipal/wifi/frame/filter/non_noisy_prism.hh>
00030 # include <wipal/wifi/frame/filter/uniquely_identifiable.hh>
00031
00032 namespace wifi
00033 {
00034 namespace frame
00035 {
00036 namespace filter
00037 {
00038
00039 namespace internals
00040 {
00041
00042 template <class I1, class I2, class B1, class B2>
00043 intersector_iterator<I1, I2, B1, B2>::
00044 intersector_iterator(const iterable_type& i, bool end):
00045 super_type (),
00046 iterable_ (&i),
00047 next1_ (end ? i.last1_ : i.first1_),
00048 next2_ (end ? i.last2_ : i.first2_)
00049 # ifndef DONT_USE_HASH
00050 ,
00051 arrivals1_ (hash_bucket_count),
00052 arrivals2_ (hash_bucket_count)
00053 # endif
00054 {
00055 if (not end)
00056 increment();
00057 }
00058
00059 template <class I1, class I2, class B1, class B2>
00060 bool
00061 intersector_iterator<I1, I2, B1, B2>::
00062 equal(const intersector_iterator& rhs) const
00063 {
00064 if (not rhs.value())
00065 return not this->value();
00066 return next1_ == rhs.next1_ and next2_ == rhs.next2_;
00067 }
00068
00069 template <class I1, class I2, class B1, class B2>
00070 void
00071 intersector_iterator<I1, I2, B1, B2>::increment()
00072 {
00073 const I1& last1 = this->iterable_->last1_;
00074 const I2& last2 = this->iterable_->last2_;
00075
00076 while (next1_ != last1 or next2_ != last2)
00077 if ((next1_ != last1 and check<false>(next1_, arrivals1_,
00078 arrivals2_))
00079 or
00080 (next2_ != last2 and check<true>(next2_, arrivals2_,
00081 arrivals1_)))
00082 return;
00083 arrivals1_.clear();
00084 arrivals2_.clear();
00085 this->value() = boost::none_t ();
00086 }
00087
00088 template <class I1, class I2, class B1, class B2>
00089 template <bool SwapResult, class ArrType, class RHSArrType>
00090 bool
00091 intersector_iterator<I1, I2, B1, B2>::
00092 check(I1& frm,
00093 ArrType& frm_arrivals,
00094 RHSArrType& rhs_arrivals)
00095 {
00096 typename RHSArrType::iterator i = rhs_arrivals.find(*frm);
00097
00098 if (i == rhs_arrivals.end())
00099 {
00100 frm_arrivals.insert(*frm);
00101 ++frm;
00102 return false;
00103 }
00104
00105
00106
00107
00108 {
00109 const tool::microseconds& t = i->microseconds();
00110 const size_t lhs = SwapResult;
00111 const size_t rhs = not SwapResult;
00112
00113 if (t < last_arrival_[rhs])
00114 {
00115 std::cerr << "WARNING: Unique frame " << i->frame_id()
00116 << " (" << t << " us) anterior to previous unique "
00117 "frame (" << last_arrival_[rhs] << " us), "
00118 "ignoring.\n"
00119 "WARNING: Probably this frame is not really "
00120 "unique inside its trace." << std::endl;
00121 rhs_arrivals.erase(i);
00122 frm_arrivals.insert(*frm);
00123 ++frm;
00124 return false;
00125 }
00126 last_arrival_[lhs] = frm->microseconds();
00127 last_arrival_[rhs] = t;
00128 }
00129
00130 this->value() =
00131 SwapResult ? value_type (*i, *frm) : value_type (*frm, *i);
00132
00133
00134
00135
00136
00137
00138
00139 if (rhs_arrivals.size() > arrivals_max_size)
00140 cleanup_arrivals(i, rhs_arrivals);
00141
00142 frm_arrivals.clear();
00143 rhs_arrivals.erase(i);
00144 ++frm;
00145 return true;
00146 }
00147
00148 template <class I1, class I2, class B1, class B2>
00149 template <class ArrType>
00150 void
00151 intersector_iterator<I1, I2, B1, B2>::
00152 cleanup_arrivals(const typename ArrType::iterator& frame,
00153 ArrType& arrivals)
00154 {
00155 typedef typename ArrType::iterator iterator;
00156
00157 const tool::microseconds m = frame->microseconds();
00158 iterator i = arrivals.begin();
00159 const iterator e = arrivals.end();
00160
00161 while (i != e)
00162 {
00163 if (i->microseconds() < m)
00164 arrivals.erase(i++);
00165 else
00166 ++i;
00167 }
00168 }
00169
00170 }
00171
00172
00173 template <class I1, class I2, class B>
00174 intersector<I1, I2, B>::intersector(const I1& first1, const I1& last1,
00175 const I2& first2, const I2& last2):
00176 first1_ (first1),
00177 last1_ (last1),
00178 first2_ (first2),
00179 last2_ (last2)
00180 {
00181 }
00182
00183 template <class U, class HT, template <class, class, class> class Int,
00184 class I1, class I2, class F>
00185 void
00186 provide_intersector(const I1& first1, const I1& last1,
00187 const I2& first2, const I2& last2,
00188 addr_mapping& mapping,
00189 F& func,
00190 bool filter_prism,
00191 tool::endian::endianness phy_end)
00192 {
00193 if (filter_prism)
00194 {
00195 typedef non_noisy_prism<I1> nnp1;
00196 typedef non_noisy_prism<I2> nnp2;
00197 typedef typename nnp1::const_iterator nnp1_i;
00198 typedef typename nnp2::const_iterator nnp2_i;
00199 typedef uniquely_identifiable<U, nnp1_i, HT> ui1;
00200 typedef uniquely_identifiable<U, nnp2_i, HT> ui2;
00201 typedef typename ui1::const_iterator ui1_i;
00202 typedef typename ui2::const_iterator ui2_i;
00203 typedef Int<ui1_i, ui2_i, tool::bottom> intersector;
00204
00205 nnp1 n1 (first1, last1);
00206 nnp2 n2 (first2, last2);
00207 ui1 u1 (n1.begin(), n1.end(), mapping, phy_end);
00208 ui2 u2 (n2.begin(), n2.end(), mapping, phy_end);
00209 intersector i (u1.begin(), u1.end(), u2.begin(), u2.end());
00210
00211 func(i);
00212 }
00213 else
00214 {
00215 typedef uniquely_identifiable<U, I1, HT> ui1;
00216 typedef uniquely_identifiable<U, I2, HT> ui2;
00217 typedef typename ui1::const_iterator ui1_i;
00218 typedef typename ui2::const_iterator ui2_i;
00219 typedef Int<ui1_i, ui2_i, tool::bottom> intersector;
00220
00221 ui1 u1 (first1, last1, mapping, phy_end);
00222 ui2 u2 (first2, last2, mapping, phy_end);
00223 intersector i (u1.begin(), u1.end(), u2.begin(), u2.end());
00224
00225 func(i);
00226 }
00227 }
00228
00229 }
00230
00231 }
00232
00233 }
00234
00235 #endif // ! WIFI_FRAME_FILTER_INTERSECTOR_HXX_