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
00143 unordered_warn_threshold = 106
00144 };
00145
00146
00147 bool check();
00148 bool check_drift(const tool::microseconds& dt1,
00149 const tool::microseconds& dt2,
00150 const typename I1::value_type& frame1,
00151 const typename I2::value_type& frame2);
00152 void check_consistency(const tool::microseconds& dt1,
00153 const tool::microseconds& dt2,
00154 const typename I1::value_type& frame1,
00155 const typename I2::value_type& frame2) const;
00156
00157 void ignore(const typename I1::value_type& frame1,
00158 const typename I2::value_type& frame2);
00159 void dont_ignore(const typename I1::value_type& frame1,
00160 const typename I2::value_type& frame2);
00161
00163 struct ignore_info
00164 {
00165 ignore_info(const tool::microseconds& stamp_rhs,
00166 const tool::microseconds& stamp_lhs,
00167 const unsigned total_rhs,
00168 const unsigned total_lhs);
00169
00171 tool::microseconds stamp1_;
00172
00174 tool::microseconds stamp2_;
00175
00177 unsigned total1_;
00178
00180 unsigned total2_;
00181 };
00182
00183 const iterable_type* iterable_;
00184 I2 next_;
00185 boost::optional<ignore_info> ign_;
00186
00187
00188
00189
00190 typename super_type::optional_value lookahead_;
00191
00192 # ifdef WP_ENABLE_INFO
00193 unsigned rhs_total_;
00194 unsigned ref_total_;
00195 # endif // WP_ENABLE_INFO
00196 };
00197
00198 }
00199
00200
00201 template <class InputIterator1,
00202 class InputIterator2,
00203 class Bottom = tool::bottom>
00204 struct fast_intersector:
00205 WP_INHERIT(public tool::iterable, fast_intersector<InputIterator1,
00206 InputIterator2,
00207 Bottom>)
00208 {
00209 fast_intersector(const InputIterator1& first1,
00210 const InputIterator1& last1,
00211 const InputIterator2& first2,
00212 const InputIterator2& last2);
00213
00214 void
00215 reset_lhs(const InputIterator1& first1,
00216 const InputIterator1& last1);
00217
00218 void
00219 reset_rhs(const InputIterator2& first2,
00220 const InputIterator2& last2);
00221
00222
00223 # ifdef WP_DONT_USE_HASH
00224 typedef std::set<typename InputIterator1::value_type> arrivals_type;
00225 # else
00226 typedef
00227 tool::hash_set<typename InputIterator1::value_type> arrivals_type;
00228
00229 enum
00230 {
00240 hash_bucket_count = 1 << 25
00241 };
00242 # endif
00243
00244 private:
00245 InputIterator2 first_;
00246 InputIterator2 last_;
00247 arrivals_type arrivals_;
00248
00249 friend
00250 class internals::fast_intersector_iterator<InputIterator1,
00251 InputIterator2,
00252 Bottom,
00253 tool::bottom>;
00254 };
00255
00256 }
00257
00258 }
00259
00260 }
00261
00262 # include "fast_intersector.hxx"
00263
00264 #endif