OpenDDS::DCPS::DisjointSequence Class Reference

#include <DisjointSequence.h>

List of all members.

Public Member Functions
	DisjointSequence ()
void	reset ()
bool	empty () const
SequenceNumber	low () const
SequenceNumber	high () const
SequenceNumber	cumulative_ack () const
SequenceNumber	last_ack () const
bool	disjoint () const
bool	contains (SequenceNumber value) const
bool	insert (const SequenceRange &range, OPENDDS_VECTOR(SequenceRange)&added)
bool	insert (const SequenceRange &range)
	Insert all numbers between range.first and range.second (both inclusive).
bool	insert (SequenceNumber value)
	Shorthand for "insert(SequenceRange(value, value))".
bool	insert (SequenceNumber value, CORBA::ULong num_bits, const CORBA::Long bits[])
bool	to_bitmap (CORBA::Long bitmap[], CORBA::ULong length, CORBA::ULong &num_bits, bool invert=false) const
	OPENDDS_VECTOR (SequenceRange) missing_sequence_ranges() const
	Returns missing ranges of SequenceNumbers (internal gaps in the sequence).
	OPENDDS_VECTOR (SequenceRange) present_sequence_ranges() const
void	dump () const
Static Public Member Functions
static bool	fill_bitmap_range (CORBA::ULong low, CORBA::ULong high, CORBA::Long bitmap[], CORBA::ULong length, CORBA::ULong &num_bits)
	Set the bits in range [low, high] in the bitmap, updating num_bits.
Private Types
typedef bool(*)	SRCompare (const SequenceRange &, const SequenceRange &)
Private Member Functions
typedef	OPENDDS_SET_CMP (SequenceRange, SRCompare) RangeSet
bool	insert_i (const SequenceRange &range, OPENDDS_VECTOR(SequenceRange)*gaps=0)
bool	insert_bitmap_range (RangeSet::iterator &iter, const SequenceRange &sr)
Static Private Member Functions
static void	validate (const SequenceRange &range)
static bool	SequenceRange_LessThan (const SequenceRange &lhs, const SequenceRange &rhs)
Private Attributes
RangeSet	sequences_

---

Detailed Description

Data structure for a set of SequenceNumbers. Sequence numbers can be inserted as single numbers, ranges, or RTPS-style bitmaps. The DisjointSequence can then be queried for contiguous ranges and internal gaps.

Definition at line 23 of file DisjointSequence.h.

---

Member Typedef Documentation

typedef bool(*) OpenDDS::DCPS::DisjointSequence::SRCompare(const SequenceRange &, const SequenceRange &) [private]

Definition at line 115 of file DisjointSequence.h.

---

Constructor & Destructor Documentation

ACE_INLINE OpenDDS::DCPS::DisjointSequence::DisjointSequence

(

)

Definition at line 52 of file DisjointSequence.inl.

  : sequences_(SequenceRange_LessThan)
{
}

---

Member Function Documentation

bool OpenDDS::DCPS::DisjointSequence::contains

(

SequenceNumber

value

)

const

Definition at line 326 of file DisjointSequence.cpp.

{
  RangeSet::const_iterator iter =
    sequences_.lower_bound(SequenceRange(0 /*ignored*/, value));
  return iter != sequences_.end() && iter->first <= value;
}

ACE_INLINE SequenceNumber OpenDDS::DCPS::DisjointSequence::cumulative_ack

(

)

const

Gets the high end of the lowest contiguous range. Named after the use case of tracking received messages (which may be received out-of-order) and then determining the largest value that the receiver is allowed to acknowledge (under a cumulative-acking protocol). If empty(), returns SEQUENCENUMBER_UNKNOWN.

Definition at line 24 of file DisjointSequence.inl.

References OpenDDS::RTPS::SEQUENCENUMBER_UNKNOWN, and sequences_.

Referenced by OpenDDS::DCPS::WriterInfo::ack_sequence(), OpenDDS::DCPS::WriteDataContainer::data_delivered(), OpenDDS::DCPS::RtpsUdpDataLink::deliver_held_data(), OpenDDS::DCPS::ReliableSession::deliver_held_data(), OpenDDS::DCPS::RtpsUdpDataLink::generate_nack_frags(), OpenDDS::DCPS::RtpsUdpDataLink::marshal_gaps(), OpenDDS::DCPS::ReliableSession::ready_to_deliver(), OpenDDS::DCPS::ReliableSession::send_naks(), OpenDDS::DCPS::WriteDataContainer::sequence_acknowledged(), OpenDDS::DCPS::RtpsUdpDataLink::WriterInfo::should_nack(), and to_bitmap().

{
  return sequences_.empty()
    ? SequenceNumber::SEQUENCENUMBER_UNKNOWN()
    : sequences_.begin()->second;
}

ACE_INLINE bool OpenDDS::DCPS::DisjointSequence::disjoint

(

)

const

Objects with the disjoint() property have an internal gap in the inserted SequenceNumbers.

Definition at line 46 of file DisjointSequence.inl.

References sequences_.

Referenced by OpenDDS::DCPS::RtpsUdpDataLink::marshal_gaps(), OpenDDS::DCPS::ReliableSession::ready_to_deliver(), OpenDDS::DCPS::ReliableSession::send_naks(), OpenDDS::DCPS::RtpsUdpDataLink::WriterInfo::should_nack(), and to_bitmap().

{
  return sequences_.size() > 1;
}

void OpenDDS::DCPS::DisjointSequence::dump

(

)

const

Definition at line 343 of file DisjointSequence.cpp.

References sequences_.

Referenced by OpenDDS::DCPS::RtpsUdpDataLink::received(), OpenDDS::DCPS::RtpsUdpDataLink::send_nack_replies(), and OpenDDS::DCPS::ReliableSession::send_naks().

{
  ACE_DEBUG((LM_DEBUG, "(%P|%t) DisjointSequence[%X]::dump Ranges of seen "
                       "SequenceNumbers:\n", this));
  for (RangeSet::const_iterator iter = sequences_.begin();
       iter != sequences_.end(); ++iter) {
    ACE_DEBUG((LM_DEBUG, "(%P|%t) DisjointSequence[%X]::dump\t%q-%q\n",
               this, iter->first.getValue(), iter->second.getValue()));
  }
}

ACE_INLINE bool OpenDDS::DCPS::DisjointSequence::empty

(

)

const

Definition at line 40 of file DisjointSequence.inl.

References sequences_.

Referenced by OpenDDS::DCPS::RtpsUdpDataLink::deliver_held_data(), OpenDDS::DCPS::ReliableSession::deliver_held_data(), OpenDDS::DCPS::RtpsUdpDataLink::generate_nack_frags(), OpenDDS::DCPS::RtpsUdpDataLink::RtpsReader::nack_durable(), OpenDDS::DCPS::RtpsUdpDataLink::process_heartbeat_i(), OpenDDS::DCPS::ReliableSession::ready_to_deliver(), OpenDDS::DCPS::RtpsUdpDataLink::received(), OpenDDS::DCPS::SingleSendBuffer::resend_fragments_i(), OpenDDS::DCPS::RtpsUdpDataLink::send_nack_replies(), and OpenDDS::DCPS::RtpsUdpDataLink::WriterInfo::should_nack().

{
  return sequences_.empty();
}

bool OpenDDS::DCPS::DisjointSequence::fill_bitmap_range	(	CORBA::ULong	low,
		CORBA::ULong	high,
		CORBA::Long	bitmap[],
		CORBA::ULong	length,
		CORBA::ULong &	num_bits
	)			[static]

Set the bits in range [low, high] in the bitmap, updating num_bits.

Definition at line 232 of file DisjointSequence.cpp.

Referenced by OpenDDS::DCPS::RtpsUdpDataLink::extend_bitmap_range(), OpenDDS::DCPS::TransportReassembly::get_gaps(), OpenDDS::DCPS::RtpsUdpDataLink::send_ack_nacks(), and to_bitmap().

{
  bool clamped = false;
  CORBA::ULong idx_low = low / 32, bit_low = low % 32,
               idx_high = high / 32, bit_high = high % 32;

  if (idx_low >= length) {
    return false;
  }
  if (idx_high >= length) {
    // clamp to largest number we can represent
    high = length * 32 - 1;
    idx_high = length - 1;
    bit_high = high % 32;
    clamped = true;
  }

  // clear any full Longs between the last bit we wrote and idx_low
  for (CORBA::ULong i = (num_bits + 31) / 32; i < idx_low; ++i) {
    bitmap[i] = 0;
  }

  // write the Long at idx_low, preserving bits that may already be there
  CORBA::ULong x = bitmap[idx_low]; // use unsigned for bitwise operators
  //    clear the bits in x in the range [bit_last, bit_low)
  if (num_bits > 0) {
    const size_t bit_last = ((num_bits - 1) / 32 == idx_low)
                            ? ((num_bits - 1) % 32 + 1) : 0;
    for (size_t m = bit_last; m < bit_low; ++m) {
      x &= ~(1 << (31 - m));
    }
  } else {
    x = 0;
  }
  //    set the bits in x in the range [bit_low, limit)
  const size_t limit = (idx_high == idx_low) ? bit_high : 31;
  for (size_t b = bit_low; b <= limit; ++b) {
    x |= (1 << (31 - b));
  }
  bitmap[idx_low] = x;

  // any full Longs inside the current range are set to all 1's
  for (CORBA::ULong elt = idx_low + 1; elt < idx_high; ++elt) {
    bitmap[elt] = 0xFFFFFFFF;
  }

  if (idx_high > idx_low) {
    // write the Long at idx_high, no need to preserve bits since this is
    // the first iteration that's writing it
    x = 0;
    for (size_t b = 0; b <= bit_high; ++b) {
      x |= (1 << (31 - b));
    }
    bitmap[idx_high] = x;
  }

  num_bits = high + 1;
  return !clamped;
}

ACE_INLINE SequenceNumber OpenDDS::DCPS::DisjointSequence::high

(

)

const

Highest SequenceNumber in the set. Precondition: !empty()

Definition at line 18 of file DisjointSequence.inl.

References sequences_.

Referenced by OpenDDS::DCPS::WriterInfo::coherent_change_received(), OpenDDS::DCPS::RtpsUdpDataLink::generate_nack_frags(), insert_bitmap_range(), OpenDDS::DCPS::RtpsUdpDataLink::marshal_gaps(), OpenDDS::DCPS::RtpsUdpDataLink::received(), OpenDDS::DCPS::RtpsUdpDataLink::WriterInfo::should_nack(), and to_bitmap().

{
  return sequences_.rbegin()->second;
}

bool OpenDDS::DCPS::DisjointSequence::insert	(	SequenceNumber	value,
		CORBA::ULong	num_bits,
		const CORBA::Long	bits[]
	)

Insert using the RTPS compact representation of a set. The three parameters, taken together, describe a set with each 1 bit starting at the msb of bits[0] and extending through num_bits (which are located at the next least significant bits of bits[0] followed by the msb of bits[1], etc.) indicating presence of the number (value + bit_index) in the set. bit_index is 0-based. Precondition: the array 'bits' has at least ceil(num_bits / 32) entries.

Definition at line 87 of file DisjointSequence.cpp.

References OpenDDS::DCPS::SequenceNumber::getValue(), insert_bitmap_range(), and sequences_.

{
  bool inserted = false;
  RangeSet::iterator iter = sequences_.end();
  SequenceNumber::Value range_start = 0;
  const SequenceNumber::Value val = value.getValue();

  // See RTPS v2.1 section 9.4.2.6 SequenceNumberSet
  for (CORBA::ULong i = 0, x = 0, bit = 0; i < num_bits; ++i, ++bit) {

    if (bit == 32) bit = 0;

    if (bit == 0) {
      x = static_cast<CORBA::ULong>(bits[i / 32]);
      if (x == 0) {
        // skip an entire Long if it's all 0's (adds 32 due to ++i)
        i += 31;
        bit = 31;
        //FUTURE: this could be generalized with something like the x86 "bsr"
        //        instruction using compiler intrinsics, VC++ _BitScanReverse()
        //        and GCC __builtin_clz()
        continue;
      }
    }

    if (x & (1 << (31 - bit))) {
      if (range_start == 0) {
        range_start = val + i;
      }

    } else if (range_start != 0) {
      // this is a "0" bit and we've previously seen a "1": insert a range
      const SequenceNumber::Value to_insert = val + i - 1;
      if (insert_bitmap_range(iter, SequenceRange(range_start, to_insert))) {
        inserted = true;
      }
      range_start = 0;

      if (iter != sequences_.end() && iter->second.getValue() != to_insert) {
        // skip ahead: next gap in sequence must be past iter->second
        CORBA::ULong next_i = CORBA::ULong(iter->second.getValue() - val);
        bit = next_i % 32;
        if (next_i / 32 != i / 32) {
          x = static_cast<CORBA::ULong>(bits[next_i / 32]);
        }
        i = next_i;
      }
    }
  }

  if (range_start != 0) {
    // iteration finished before we saw a "0" (inside a range)
    SequenceNumber range_end = (value + num_bits).previous();
    if (insert_bitmap_range(iter, SequenceRange(range_start, range_end))) {
      return true;
    }
  }
  return inserted;
}

ACE_INLINE bool OpenDDS::DCPS::DisjointSequence::insert

(

SequenceNumber

value

)

Shorthand for "insert(SequenceRange(value, value))".

Definition at line 64 of file DisjointSequence.inl.

References insert_i().

{
  return insert_i(SequenceRange(value, value));
}

ACE_INLINE bool OpenDDS::DCPS::DisjointSequence::insert

(

const SequenceRange &

range

)

Insert all numbers between range.first and range.second (both inclusive).

Definition at line 70 of file DisjointSequence.inl.

References insert_i().

{
  return insert_i(range);
}

ACE_INLINE bool OpenDDS::DCPS::DisjointSequence::insert	(	const SequenceRange &	range,
		OPENDDS_VECTOR(SequenceRange)&	added
	)

All insert() methods return true upon modifying the set and false if the set already contained the SequenceNumber(s) that were to be inserted. This is the general form of insert() whereby the caller receives a list of sub-ranges of 'range' that were not already in the DisjointSequence. For example, given a DisjointSequence 'seq' containing (1, 2, 5, 9), calling seq.insert(SequenceRange(4, 12), v) returns true and yields v = [(4, 4), (6, 8), (10, 12)] and seq = (1, 2, 4, ..., 12).

Definition at line 76 of file DisjointSequence.inl.

References insert_i().

Referenced by OpenDDS::DCPS::WriterInfo::ack_sequence(), OpenDDS::DCPS::ReliableSession::check_header(), OpenDDS::DCPS::WriteDataContainer::data_delivered(), OpenDDS::DCPS::ReliableSession::nakack_received(), OpenDDS::DCPS::RtpsUdpDataLink::process_heartbeat_i(), OpenDDS::DCPS::RtpsUdpDataLink::received(), OpenDDS::DCPS::ReliableSession::record_header_received(), OpenDDS::DCPS::RtpsUdpDataLink::send_nack_replies(), OpenDDS::DCPS::RtpsUdpDataLink::send_nackfrag_replies(), OpenDDS::DCPS::ReliableSession::send_naks(), and OpenDDS::DCPS::ReliableSession::syn_hook().

{
  return insert_i(range, &gaps);
}

bool OpenDDS::DCPS::DisjointSequence::insert_bitmap_range	(	RangeSet::iterator &	iter,
		const SequenceRange &	sr
	)			[private]

Definition at line 149 of file DisjointSequence.cpp.

References high(), low(), and sequences_.

Referenced by insert().

{
  // This is similar to insert_i(), except it doesn't need an O(log(n)) search
  // of sequences_ every time to find the starting point, and it doesn't
  // compute the 'gaps'.

  const SequenceNumber::Value previous = range.first.getValue() - 1,
    next = range.second.getValue() + 1;

  if (!sequences_.empty()) {
    if (iter == sequences_.end()) {
      iter = sequences_.lower_bound(SequenceRange(1 /*ignored*/, previous));
    } else {
      // start where we left off last time and get the lower_bound(previous)
      for (; iter != sequences_.end() && iter->second < previous; ++iter) ;
    }
  }

  if (iter == sequences_.end() || iter->first > next) {
    // can't combine on either side, insert a new range
    iter = sequences_.insert(iter, range);
    return true;
  }

  if (iter->first <= range.first && iter->second >= range.second) {
    // range is already covered by this DisjointSet
    return false;
  }

  // find the right-most (highest) range we can use
  RangeSet::iterator right = iter;
  for (; right != sequences_.end() && right->second < next; ++right) ;

  SequenceNumber high = range.second;
  if (right != sequences_.end()
      && right->first <= next && right->first > range.first) {
    high = right->second;
    ++right;
  }

  const SequenceNumber low = std::min(iter->first, range.first);
  sequences_.erase(iter, right);

  iter = sequences_.insert(SequenceRange(low, high)).first;
  return true;
}

bool OpenDDS::DCPS::DisjointSequence::insert_i	(	const SequenceRange &	range,
		OPENDDS_VECTOR(SequenceRange)*	gaps = 0
	)			[private]

Definition at line 26 of file DisjointSequence.cpp.

References sequences_, validate(), and OpenDDS::DCPS::SequenceNumber::ZERO().

Referenced by insert().

{
  validate(range);

  RangeSet::iterator range_above = sequences_.lower_bound(range);
  if (range_above != sequences_.end()
      && range_above->first <= range.first) {
    return false; // already have this range, nothing to insert
  }

  SequenceRange newRange = range;
  if (range_above != sequences_.end()
      && ++SequenceNumber(newRange.second) >= range_above->first) {
    // newRange overlaps range_above, replace range_above with modified newRange
    newRange.second = range_above->second;
    // move to just past this iterator for the erase
    ++range_above;
  }

  const SequenceNumber::Value previous = range.first.getValue() - 1;
  // find the lower_bound for the SequenceNumber just before this range
  // to see if any ranges need to combine
  const RangeSet::iterator range_below =
    sequences_.lower_bound(SequenceRange(1 /*ignored*/,
                                         (previous > 0) ? previous
                                         : SequenceNumber::ZERO()));
  if (range_below != sequences_.end()) {
    // if low end falls inside of the range_below range
    // then combine
    if (newRange.first > range_below->first) {
      newRange.first = range_below->first;
    }

    if (gaps) {
      RangeSet::iterator gap_iter = range_below;
      if (range.first < gap_iter->second) {
        gaps->push_back(SequenceRange(range.first,
                                      gap_iter->second.previous()));
      }
      SequenceNumber last_gap = gap_iter++->second;
      for (; gap_iter != range_above; ++gap_iter) {
        const SequenceNumber in_range =
          std::min(gap_iter->first.previous().getValue(),
                   range.second.getValue());
        gaps->push_back(SequenceRange(++last_gap, in_range));
        last_gap = gap_iter->second;
      }
      if (last_gap < range.second) {
        gaps->push_back(SequenceRange(++last_gap, range.second));
      }
    }

    sequences_.erase(range_below, range_above);
  }

  sequences_.insert(newRange);
  return true;
}

ACE_INLINE SequenceNumber OpenDDS::DCPS::DisjointSequence::last_ack

(

)

const

Gets the low end of the highest contiguous range, may be thought of as the inverse of cumulative_ack(). If empty(), returns SEQUENCENUMBER_UNKNOWN.

Definition at line 32 of file DisjointSequence.inl.

References OpenDDS::RTPS::SEQUENCENUMBER_UNKNOWN, and sequences_.

Referenced by OpenDDS::DCPS::RtpsUdpDataLink::generate_nack_frags().

{
  return sequences_.empty()
    ? SequenceNumber::SEQUENCENUMBER_UNKNOWN()
    : sequences_.rbegin()->first;
}

ACE_INLINE SequenceNumber OpenDDS::DCPS::DisjointSequence::low

(

)

const

Lowest SequenceNumber in the set. Precondition: !empty()

Definition at line 12 of file DisjointSequence.inl.

References sequences_.

Referenced by OpenDDS::DCPS::RtpsUdpDataLink::deliver_held_data(), OpenDDS::DCPS::ReliableSession::deliver_held_data(), insert_bitmap_range(), OpenDDS::DCPS::RtpsUdpDataLink::marshal_gaps(), OpenDDS::DCPS::RtpsUdpDataLink::RtpsReader::nack_durable(), OpenDDS::DCPS::RtpsUdpDataLink::process_heartbeat_i(), OpenDDS::DCPS::ReliableSession::ready_to_deliver(), OpenDDS::DCPS::RtpsUdpDataLink::received(), OpenDDS::DCPS::ReliableSession::send_naks(), and to_bitmap().

{
  return sequences_.begin()->first;
}

typedef OpenDDS::DCPS::DisjointSequence::OPENDDS_SET_CMP	(	SequenceRange	,
		SRCompare
	)			[private]

OpenDDS::DCPS::DisjointSequence::OPENDDS_VECTOR

(

SequenceRange

)

const

Returns a representation of the members of the sequence as a list of contiguous ranges (each Range is inclusive on both sides).

OpenDDS::DCPS::DisjointSequence::OPENDDS_VECTOR

(

SequenceRange

)

const

Returns missing ranges of SequenceNumbers (internal gaps in the sequence).

ACE_INLINE void OpenDDS::DCPS::DisjointSequence::reset

(

)

Definition at line 58 of file DisjointSequence.inl.

References sequences_.

Referenced by OpenDDS::DCPS::WriterInfo::reset_coherent_info(), and OpenDDS::DCPS::ReliableSession::syn_hook().

{
  sequences_.clear();
}

static bool OpenDDS::DCPS::DisjointSequence::SequenceRange_LessThan	(	const SequenceRange &	lhs,
		const SequenceRange &	rhs
	)			[inline, static, private]

Definition at line 109 of file DisjointSequence.h.

  {
    return lhs.second < rhs.second;
  }

bool OpenDDS::DCPS::DisjointSequence::to_bitmap	(	CORBA::Long	bitmap[],
		CORBA::ULong	length,
		CORBA::ULong &	num_bits,
		bool	invert = false
	)			const

Inverse of insert(value, num_bits, bits). Populates array of bitmap[length] with the bitmap of ranges above the cumulative_ack() value. Sets the number of significant (used) bits in num_bits. The 'base' of the bitmap is one larger than cumulative_ack(). Returns true if the entire DisjointSequence was able to fit in bitmap[]. Returning false is not an error, it's just that the higher-valued ranges didn't fit. If invert is true, the 1's in the bitmap represent the missing_sequence_ranges() instead of the present_sequence_ranges(). Precondition: the array 'bits' has 'length' entries allocated.

Definition at line 198 of file DisjointSequence.cpp.

References cumulative_ack(), disjoint(), fill_bitmap_range(), OpenDDS::DCPS::SequenceNumber::getValue(), high(), low(), and sequences_.

Referenced by OpenDDS::DCPS::RtpsUdpDataLink::marshal_gaps().

{
  // num_bits will be 1 more than the index of the last bit we wrote
  num_bits = 0;
  if (!disjoint()) {
    return true;
  }

  const SequenceNumber base = ++SequenceNumber(cumulative_ack());

  for (RangeSet::const_iterator iter = sequences_.begin(), prev = iter++;
       iter != sequences_.end(); ++iter, ++prev) {

    CORBA::ULong low = 0, high = 0;

    if (invert) {
      low = CORBA::ULong(prev->second.getValue() + 1 - base.getValue());
      high = CORBA::ULong(iter->first.getValue() - 1 - base.getValue());

    } else {
      low = CORBA::ULong(iter->first.getValue() - base.getValue());
      high = CORBA::ULong(iter->second.getValue() - base.getValue());
    }

    if (!fill_bitmap_range(low, high, bitmap, length, num_bits)) {
      return false;
    }
  }

  return true;
}

void OpenDDS::DCPS::DisjointSequence::validate

(

const SequenceRange &

range

)

[static, private]

Definition at line 334 of file DisjointSequence.cpp.

Referenced by insert_i().

{
  if (range.first > range.second) {
    throw std::runtime_error("SequenceNumber range invalid, range must "
                             "be ascending.");
  }
}

---

Member Data Documentation

RangeSet OpenDDS::DCPS::DisjointSequence::sequences_ [private]

Definition at line 117 of file DisjointSequence.h.

Referenced by cumulative_ack(), disjoint(), dump(), empty(), high(), insert(), insert_bitmap_range(), insert_i(), last_ack(), low(), reset(), and to_bitmap().

---

The documentation for this class was generated from the following files:

• DisjointSequence.h
• DisjointSequence.cpp
• DisjointSequence.inl

---