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_FAST_INTERSECTOR_HH_
00023 # define WIFI_FRAME_FILTER_FAST_INTERSECTOR_HH_
00024
00025 # include <utility>
00026
00027 # include <wipal/tool/hash.hh>
00028 # include <wipal/tool/valued_iterator.hh>
00029 # include <wipal/tool/microseconds.hh>
00030 # include <wipal/tool/iterable.hh>
00031 # include <wipal/wifi/addr_mapping.hh>
00032
00033 # include "fast_intersector_fwd.hh"
00034
00035 namespace tool
00036 {
00037
00038 template <class I1, class I2, class B1, class B2>
00039 struct types< wifi::frame::filter::internals::
00040 fast_intersector_iterator<I1, I2, B1, B2> >
00041 {
00042 typedef
00043 std::pair<typename I1::value_type, typename I2::value_type>
00044 value_type;
00045
00046 typedef
00047 wifi::frame::filter::fast_intersector<I1, I2, B1>
00048 iterable_type;
00049 };
00050
00051 template <class I1, class I2, class B>
00052 struct types< wifi::frame::filter::fast_intersector<I1, I2, B> >
00053 {
00054 typedef wifi::frame::filter::internals::
00055 fast_intersector_iterator<I1, I2, B, bottom>
00056 iterator;
00057 };
00058
00059 }
00060
00061 namespace wifi
00062 {
00063 namespace frame
00064 {
00065 namespace filter
00066 {
00067
00068 namespace internals
00069 {
00070 template <class I1, class I2, class B, class Bottom = tool::bottom>
00071 struct fast_intersector_iterator:
00072 WP_INHERIT(public tool::valued_iterator,
00073 fast_intersector_iterator<I1, I2, B, Bottom>)
00074 {
00075
00077
00078 typedef WP_GET_EXACT(Bottom,
00079 fast_intersector_iterator<I1, I2, B, Bottom>)
00080 exact_type;
00081 typedef tool::valued_iterator<exact_type> super_type;
00082 typedef WP_TYPE(value_type, exact_type) value_type;
00083 typedef WP_TYPE(iterable_type, exact_type) iterable_type;
00084 typedef typename iterable_type::arrivals_type arrivals_type;
00085 typedef typename arrivals_type::const_iterator arrivals_iterator;
00087
00089 fast_intersector_iterator(const iterable_type& i, bool end);
00090
00092
00093 bool equal(const fast_intersector_iterator& rhs) const;
00094 void increment();
00096
00098 unsigned rhs_frame_count() const;
00099
00101 unsigned rhs_uframe_count() const;
00102
00103 private:
00104 enum
00105 {
00113 dt_warn_threshold = 15 * 60 * 1000 * 1000,
00114
00131 drift_warn_threshold = 20 * 1000,
00132 };
00133
00134
00135 bool check();
00136 bool check_drift(const tool::microseconds& dt1,
00137 const tool::microseconds& dt2,
00138 const typename I1::value_type& frame1,
00139 const typename I2::value_type& frame2);
00140 void check_consistency(const tool::microseconds& dt1,
00141 const tool::microseconds& dt2,
00142 const typename I1::value_type& frame1,
00143 const typename I2::value_type& frame2) const;
00144
00145 void ignore(const typename I1::value_type& frame1,
00146 const typename I2::value_type& frame2);
00147 void dont_ignore(const typename I1::value_type& frame1,
00148 const typename I2::value_type& frame2);
00149
00151 struct ignore_info
00152 {
00153 ignore_info(const tool::microseconds& stamp_rhs,
00154 const tool::microseconds& stamp_lhs,
00155 const unsigned total_rhs,
00156 const unsigned total_lhs);
00157
00159 tool::microseconds stamp1_;
00160
00162 tool::microseconds stamp2_;
00163
00165 unsigned total1_;
00166
00168 unsigned total2_;
00169 };
00170
00171 const iterable_type* iterable_;
00172 I2 next_;
00173 boost::optional<ignore_info> ign_;
00174
00175
00176
00177
00178 typename super_type::optional_value lookahead_;
00179
00180 # ifdef WP_ENABLE_INFO
00181 unsigned rhs_total_;
00182 unsigned ref_total_;
00183 # endif // WP_ENABLE_INFO
00184 };
00185
00186 }
00187
00188
00189 template <class InputIterator1,
00190 class InputIterator2,
00191 class Bottom = tool::bottom>
00192 struct fast_intersector:
00193 WP_INHERIT(public tool::iterable, fast_intersector<InputIterator1,
00194 InputIterator2,
00195 Bottom>)
00196 {
00197 fast_intersector(const InputIterator1& first1,
00198 const InputIterator1& last1,
00199 const InputIterator2& first2,
00200 const InputIterator2& last2,
00201 const unsigned precision);
00202
00203 void
00204 reset_lhs(const InputIterator1& first1,
00205 const InputIterator1& last1);
00206
00207 void
00208 reset_rhs(const InputIterator2& first2,
00209 const InputIterator2& last2);
00210
00211
00212 # ifdef WP_DONT_USE_HASH
00213 typedef std::set<typename InputIterator1::value_type> arrivals_type;
00214 # else
00215 typedef
00216 tool::hash_set<typename InputIterator1::value_type> arrivals_type;
00217
00218 enum
00219 {
00229 hash_bucket_count = 1 << 25
00230 };
00231 # endif
00232
00233 private:
00234 InputIterator2 first_;
00235 InputIterator2 last_;
00236 arrivals_type arrivals_;
00237 unsigned precision_;
00238
00239 friend
00240 class internals::fast_intersector_iterator<InputIterator1,
00241 InputIterator2,
00242 Bottom,
00243 tool::bottom>;
00244 };
00245
00246 }
00247
00248 }
00249
00250 }
00251
00252 # include "fast_intersector.hxx"
00253
00254 #endif