Line data    Source code

       1             : /*
       2             :  *
       3             :  *
       4             :  * Distributed under the OpenDDS License.
       5             :  * See: http://www.opendds.org/license.html
       6             :  */
       7             : 
       8             : #include "DCPS/DdsDcps_pch.h" //Only the _pch include should start with DCPS/
       9             : 
      10             : #include "DisjointSequence.h"
      11             : 
      12             : #include "ace/Log_Msg.h"
      13             : 
      14             : #include <stdexcept>
      15             : #include <algorithm>
      16             : #include <iterator>
      17             : 
      18             : #ifndef __ACE_INLINE__
      19             : # include "DisjointSequence.inl"
      20             : #endif /* __ACE_INLINE__ */
      21             : 
      22             : OPENDDS_BEGIN_VERSIONED_NAMESPACE_DECL
      23             : 
      24             : namespace OpenDDS {
      25             : namespace DCPS {
      26             : 
      27             : bool
      28         484 : DisjointSequence::insert_i(const SequenceRange& range,
      29             :                            OPENDDS_VECTOR(SequenceRange)* gaps /* = 0 */)
      30             : {
      31         484 :   OPENDDS_ASSERT(range.first <= range.second);
      32             : 
      33             :   typedef RangeSet::Container::iterator iter_t;
      34             : 
      35         484 :   iter_t range_above = sequences_.ranges_.lower_bound(range);
      36         484 :   if (range_above != sequences_.ranges_.end()
      37         484 :       && range_above->first <= range.first) {
      38           0 :     return false; // already have this range, nothing to insert
      39             :   }
      40             : 
      41         484 :   SequenceRange newRange = range;
      42         484 :   if (range_above != sequences_.ranges_.end()
      43         484 :       && ++SequenceNumber(newRange.second) >= range_above->first) {
      44             :     // newRange overlaps range_above, replace range_above with modified newRange
      45           8 :     newRange.second = range_above->second;
      46             :     // move to just past this iterator for the erase
      47           8 :     ++range_above;
      48             :   }
      49             : 
      50         484 :   const SequenceNumber::Value previous = range.first.getValue() - 1;
      51             :   // find the lower_bound for the SequenceNumber just before this range
      52             :   // to see if any ranges need to combine
      53             :   const iter_t range_below =
      54         484 :     sequences_.ranges_.lower_bound(SequenceRange(1 /*ignored*/,
      55         484 :                                                  (previous > 0) ? previous
      56          52 :                                                  : SequenceNumber::ZERO()));
      57         484 :   if (range_below != sequences_.ranges_.end()) {
      58             :     // if low end falls inside of the range_below range
      59             :     // then combine
      60          53 :     if (newRange.first > range_below->first) {
      61          45 :       newRange.first = range_below->first;
      62             :     }
      63             : 
      64          53 :     if (gaps) {
      65           5 :       iter_t gap_iter = range_below;
      66           5 :       if (range.first < gap_iter->second) {
      67           1 :         gaps->push_back(SequenceRange(range.first,
      68           2 :                                       gap_iter->second.previous()));
      69             :       }
      70           5 :       SequenceNumber last_gap = gap_iter++->second;
      71          12 :       for (; gap_iter != range_above; ++gap_iter) {
      72             :         const SequenceNumber in_range =
      73           7 :           std::min(gap_iter->first.previous().getValue(),
      74          14 :                    range.second.getValue());
      75           7 :         gaps->push_back(SequenceRange(++last_gap, in_range));
      76           7 :         last_gap = gap_iter->second;
      77             :       }
      78           5 :       if (last_gap < range.second) {
      79           3 :         gaps->push_back(SequenceRange(++last_gap, range.second));
      80             :       }
      81             :     }
      82             : 
      83          53 :     sequences_.ranges_.erase(range_below, range_above);
      84             :   }
      85             : 
      86         484 :   sequences_.ranges_.insert(newRange);
      87         484 :   return true;
      88             : }
      89             : 
      90             : bool
      91          13 : DisjointSequence::insert(SequenceNumber value, ACE_CDR::ULong num_bits,
      92             :                          const ACE_CDR::Long bits[])
      93             : {
      94          13 :   bool inserted = false;
      95          13 :   RangeSet::Container::iterator iter = sequences_.ranges_.end();
      96          13 :   bool range_start_is_valid = false;
      97          13 :   SequenceNumber::Value range_start = 0;
      98          13 :   const SequenceNumber::Value val = value.getValue();
      99             : 
     100             :   // See RTPS v2.1 section 9.4.2.6 SequenceNumberSet
     101         131 :   for (ACE_CDR::ULong i = 0, x = 0, bit = 0; i < num_bits; ++i, ++bit) {
     102             : 
     103         118 :     if (bit == 32) bit = 0;
     104             : 
     105         118 :     if (bit == 0) {
     106          14 :       x = static_cast<ACE_CDR::ULong>(bits[i / 32]);
     107          14 :       if (x == 0) {
     108             :         // skip an entire Long if it's all 0's (adds 32 due to ++i)
     109           1 :         i += 31;
     110           1 :         bit = 31;
     111             :         //FUTURE: this could be generalized with something like the x86 "bsr"
     112             :         //        instruction using compiler intrinsics, VC++ _BitScanReverse()
     113             :         //        and GCC __builtin_clz()
     114           1 :         continue;
     115             :       }
     116             :     }
     117             : 
     118         117 :     if (x & (1 << (31 - bit))) {
     119          33 :       if (!range_start_is_valid) {
     120          17 :         range_start = val + i;
     121          17 :         range_start_is_valid = true;
     122             :       }
     123          84 :     } else if (range_start_is_valid) {
     124             :       // this is a "0" bit and we've previously seen a "1": insert a range
     125           7 :       const SequenceNumber::Value to_insert = val + i - 1;
     126           7 :       if (insert_bitmap_range(iter, SequenceRange(range_start, to_insert))) {
     127           7 :         inserted = true;
     128             :       }
     129           7 :       range_start = 0;
     130           7 :       range_start_is_valid = false;
     131             : 
     132           7 :       if (iter != sequences_.ranges_.end() && iter->second.getValue() != to_insert) {
     133             :         // skip ahead: next gap in sequence must be past iter->second
     134           2 :         ACE_CDR::ULong next_i = ACE_CDR::ULong(iter->second.getValue() - val);
     135           2 :         bit = next_i % 32;
     136           2 :         if (next_i / 32 != i / 32 && next_i < num_bits) {
     137           1 :           x = static_cast<ACE_CDR::ULong>(bits[next_i / 32]);
     138             :         }
     139           2 :         i = next_i;
     140             :       }
     141             :     }
     142             :   }
     143             : 
     144          13 :   if (range_start_is_valid) {
     145             :     // iteration finished before we saw a "0" (inside a range)
     146          10 :     SequenceNumber range_end = (value + num_bits).previous();
     147          10 :     if (insert_bitmap_range(iter, SequenceRange(range_start, range_end))) {
     148          10 :       return true;
     149             :     }
     150             :   }
     151           3 :   return inserted;
     152             : }
     153             : 
     154             : bool
     155          17 : DisjointSequence::insert_bitmap_range(RangeSet::Container::iterator& iter,
     156             :                                       const SequenceRange& range)
     157             : {
     158             :   // This is similar to insert_i(), except it doesn't need an O(log(n)) search
     159             :   // of sequences_ every time to find the starting point, and it doesn't
     160             :   // compute the 'gaps'.
     161             : 
     162          17 :   const SequenceNumber::Value previous = range.first.getValue() - 1,
     163          17 :     next = range.second.getValue() + 1;
     164             : 
     165          17 :   if (!sequences_.empty()) {
     166          14 :     if (iter == sequences_.ranges_.end()) {
     167          10 :       iter = sequences_.ranges_.lower_bound(SequenceRange(0 /*ignored*/, previous));
     168             :     } else {
     169             :       // start where we left off last time and get the lower_bound(previous)
     170           7 :       for (; iter != sequences_.ranges_.end() && iter->second < previous; ++iter) ;
     171             :     }
     172             :   }
     173             : 
     174          17 :   if (iter == sequences_.ranges_.end() || iter->first > next) {
     175             :     // can't combine on either side, insert a new range
     176           9 :     iter = sequences_.ranges_.insert(iter, range);
     177           9 :     return true;
     178             :   }
     179             : 
     180           8 :   if (iter->first <= range.first && iter->second >= range.second) {
     181             :     // range is already covered by this DisjointSet
     182           0 :     return false;
     183             :   }
     184             : 
     185             :   // find the right-most (highest) range we can use
     186           8 :   RangeSet::Container::iterator right = iter;
     187          15 :   for (; right != sequences_.ranges_.end() && right->second < next; ++right) ;
     188             : 
     189           8 :   SequenceNumber high = range.second;
     190           8 :   if (right != sequences_.ranges_.end()
     191           8 :       && right->first <= next && right->first > range.first) {
     192           4 :     high = right->second;
     193           4 :     ++right;
     194             :   }
     195             : 
     196           8 :   const SequenceNumber low = std::min(iter->first, range.first);
     197           8 :   sequences_.ranges_.erase(iter, right);
     198             : 
     199           8 :   iter = sequences_.ranges_.insert(SequenceRange(low, high)).first;
     200           8 :   return true;
     201             : }
     202             : 
     203             : bool
     204          34 : DisjointSequence::to_bitmap(ACE_CDR::Long bitmap[], ACE_CDR::ULong length,
     205             :                             ACE_CDR::ULong& num_bits, ACE_CDR::ULong& cumulative_bits_added, bool invert) const
     206             : {
     207             :   // num_bits will be 1 more than the index of the last bit we wrote
     208          34 :   num_bits = 0;
     209          34 :   if (!disjoint()) {
     210           1 :     return true;
     211             :   }
     212             : 
     213          33 :   const SequenceNumber base = ++SequenceNumber(cumulative_ack());
     214             : 
     215          33 :   for (RangeSet::const_iterator iter = sequences_.begin(), prev = iter++;
     216         297 :        iter != sequences_.end(); ++iter, ++prev) {
     217             : 
     218         267 :     ACE_CDR::ULong low = 0, high = 0;
     219             : 
     220         267 :     if (invert) {
     221          70 :       low = ACE_CDR::ULong(prev->second.getValue() + 1 - base.getValue());
     222          70 :       high = ACE_CDR::ULong(iter->first.getValue() - 1 - base.getValue());
     223             : 
     224             :     } else {
     225         197 :       low = ACE_CDR::ULong(iter->first.getValue() - base.getValue());
     226         197 :       high = ACE_CDR::ULong(iter->second.getValue() - base.getValue());
     227             :     }
     228             : 
     229         267 :     if (!fill_bitmap_range(low, high, bitmap, length, num_bits, cumulative_bits_added)) {
     230           3 :       return false;
     231             :     }
     232             :   }
     233             : 
     234          30 :   return true;
     235             : }
     236             : 
     237             : bool
     238         279 : DisjointSequence::fill_bitmap_range(ACE_CDR::ULong low, ACE_CDR::ULong high,
     239             :                                     ACE_CDR::Long bitmap[], ACE_CDR::ULong length,
     240             :                                     ACE_CDR::ULong& num_bits, ACE_CDR::ULong& cumulative_bits_added)
     241             : {
     242         279 :   bool clamped = false;
     243         279 :   if ((low / 32) >= length) {
     244           1 :     return false;
     245             :   }
     246         278 :   if ((high / 32) >= length) {
     247           2 :     high = length * 32 - 1;
     248           2 :     clamped = true;
     249             :   }
     250             : 
     251         278 :   const ACE_CDR::ULong idx_nb = num_bits / 32, bit_nb = num_bits % 32,
     252         278 :                      idx_low = low / 32, bit_low = low % 32,
     253         278 :                      idx_high = high / 32, bit_high = high % 32;
     254             : 
     255             :   // handle idx_nb zeros
     256         278 :   if (bit_nb) {
     257         230 :     bitmap[idx_nb] &= ~((0x1u << (32 - bit_nb)) - 1);
     258             :   } else {
     259          48 :     bitmap[idx_nb] = 0;
     260             :   }
     261             : 
     262             :   // handle zeros between idx_nb and idx_low (if gap exists)
     263         279 :   for (ACE_CDR::ULong i = idx_nb + 1; i < idx_low; ++i) {
     264           1 :     bitmap[i] = 0;
     265             :   }
     266             : 
     267             :   // handle idx_nb ones
     268         278 :   if (bit_low) {
     269         251 :     if (idx_low > idx_nb) {
     270           6 :       bitmap[idx_low] = (0x1u << (32 - bit_low)) - 1;
     271             :     } else {
     272         245 :       bitmap[idx_low] |= (0x1u << (32 - bit_low)) - 1;
     273             :     }
     274             :   } else {
     275          27 :     bitmap[idx_low] = 0xFFFFFFFF;
     276             :   }
     277             : 
     278             :   // handle ones between idx_low and idx_high (if gap exists)
     279         285 :   for (ACE_CDR::ULong i = idx_low + 1; i < idx_high; ++i) {
     280           7 :     bitmap[i] = 0xFFFFFFFF;
     281             :   }
     282             : 
     283             :   // handle idx_high
     284         278 :   if (idx_high > idx_low) {
     285          10 :     bitmap[idx_high] = ~((0x1u << (31 - bit_high)) - 1);
     286         268 :   } else if (bit_high < 31) {
     287         257 :     bitmap[idx_high] &= ~((0x1u << (31 - bit_high)) - 1);
     288             :   }
     289             : 
     290         278 :   num_bits = high + 1;
     291         278 :   cumulative_bits_added += high - low + 1;
     292         278 :   return !clamped;
     293             : }
     294             : 
     295             : OPENDDS_VECTOR(SequenceRange)
     296           5 : DisjointSequence::missing_sequence_ranges() const
     297             : {
     298           5 :   OPENDDS_VECTOR(SequenceRange) missing;
     299           5 :   if (!disjoint()) {
     300           0 :     return missing;
     301             :   }
     302             : 
     303           5 :   RangeSet::const_iterator secondIter = sequences_.begin();
     304           5 :   for (RangeSet::const_iterator firstIter = secondIter++;
     305          14 :        secondIter != sequences_.end(); ++firstIter, ++secondIter) {
     306             : 
     307           9 :     const SequenceNumber missingLow = ++SequenceNumber(firstIter->second),
     308           9 :                          missingHigh = secondIter->first.previous();
     309             : 
     310           9 :     if (missingLow <= missingHigh) {
     311           9 :       missing.push_back(SequenceRange(missingLow, missingHigh));
     312             :     }
     313             :   }
     314             : 
     315           5 :   return missing;
     316           0 : }
     317             : 
     318             : void
     319           0 : DisjointSequence::dump() const
     320             : {
     321           0 :   ACE_DEBUG((LM_DEBUG, "(%P|%t) DisjointSequence[%X]::dump included ranges of "
     322             :                        "SequenceNumbers:\n", this));
     323           0 :   for (RangeSet::const_iterator iter = sequences_.begin();
     324           0 :        iter != sequences_.end(); ++iter) {
     325           0 :     ACE_DEBUG((LM_DEBUG, "(%P|%t) DisjointSequence[%X]::dump\t%q-%q\n",
     326             :                this, iter->first.getValue(), iter->second.getValue()));
     327             :   }
     328           0 : }
     329             : 
     330             : ACE_CDR::ULong
     331           0 : DisjointSequence::bitmap_num_longs(const SequenceNumber& low, const SequenceNumber& high)
     332             : {
     333           0 :   return high < low ? 0u : std::min(8u, unsigned((high.getValue() - low.getValue() + 32) / 32));
     334             : }
     335             : 
     336             : void
     337           7 : DisjointSequence::erase(const SequenceNumber value)
     338             : {
     339             :   RangeSet::Container::iterator iter =
     340           7 :     sequences_.ranges_.lower_bound(SequenceRange(0 /*ignored*/, value));
     341           7 :   if (iter != sequences_.ranges_.end()) {
     342          10 :     if (iter->first == value &&
     343           3 :         iter->second == value) {
     344           0 :       sequences_.ranges_.erase(iter);
     345           7 :     } else if (iter->first == value) {
     346           3 :       SequenceRange x(value + 1, iter->second);
     347           3 :       sequences_.ranges_.erase(iter);
     348           3 :       sequences_.ranges_.insert(x);
     349           4 :     } else if (iter->second == value) {
     350           3 :       SequenceRange x(iter->first, value.previous());
     351           3 :       sequences_.ranges_.erase(iter);
     352           3 :       sequences_.ranges_.insert(x);
     353             :     } else {
     354           1 :       SequenceRange x(iter->first, value.previous());
     355           1 :       SequenceRange y(value + 1, iter->second);
     356           1 :       sequences_.ranges_.erase(iter);
     357           1 :       sequences_.ranges_.insert(x);
     358           1 :       sequences_.ranges_.insert(y);
     359             :     }
     360             :   }
     361           7 : }
     362             : 
     363             : } // namespace DCPS
     364             : } // namespace OpenDDS
     365             : 
     366             : OPENDDS_END_VERSIONED_NAMESPACE_DECL