org.jgroups.util
Class RetransmitTable

java.lang.Object
  org.jgroups.util.RetransmitTable

public class RetransmitTable
extends java.lang.Object

A store for messages to be retransmitted or delivered. Used on sender and receiver side, as a replacement for HashMap. RetransmitTable should use less memory than HashMap, as HashMap.Entry has 4 fields, plus arrays for storage.

RetransmitTable maintains a matrix (an array of arrays) of messages. Messages are stored in the matrix by mapping their seqno to an index. E.g. when we have 10 rows of 1000 messages each, and first_seqno is 3000, then a message with seqno=5600, will be stored in the 3rd row, at index 600.

Rows are removed when all messages in that row have been received.

This class in not synchronized; the caller has to make sure access to it is synchronized

Author:

Bela Ban

Field Summary

protected boolean	automatic_purging By default, rows are only nulled and highest_seqno_purged is adjusted when purge(long) is called.
protected static long	DEFAULT_MAX_COMPACTION_TIME
protected static double	DEFAULT_RESIZE_FACTOR
protected long	highest_seqno The highest seqno in the table
protected long	highest_seqno_purged The highest seqno purged
protected long	last_compaction_timestamp The time when the last compaction took place.
protected static Log	log
protected Message[][]	matrix
protected long	max_compaction_time Time (in ms) after which a compaction should take place.
protected int	msgs_per_row
protected int	num_rows
protected long	offset The first seqno, at matrix[0][0]
protected double	resize_factor
protected int	size

Constructor Summary

RetransmitTable()

RetransmitTable(int num_rows, int msgs_per_row, long offset)

RetransmitTable(int num_rows, int msgs_per_row, long offset, double resize_factor)

RetransmitTable(int num_rows, int msgs_per_row, long offset, double resize_factor, long max_compaction_time, boolean automatic_purging)

Method Summary

int	capacity() Returns the total capacity in the matrix
void	clear() Removes all elements.
void	compact() Moves the contents of matrix down by the number of purged rows and resizes the matrix accordingly.
protected int	computeIndex(long seqno) Computes and returns the index within a row for seqno
protected int	computeRow(long seqno) Computes and returns the row index for seqno
int	computeSize() Iterate from highest_seqno_purged to highest_seqno and add up non-null values
java.lang.String	dump() Dumps the seqnos in the table as a list
java.lang.String	dumpMatrix() Dumps the non-null in the table in a pseudo graphic way
Message	get(long seqno)
java.util.List<Message>	get(long from, long to)
double	getFillFactor() Returns the ratio between size and capacity, as a percentage
long	getHighest()
long	getHighestPurged()
long	getMaxCompactionTime()
int	getNullMessages(long from, long to) Returns the number of null elements in the range [from ..
long	getOffset()
protected Message[]	getRow(int index) Returns a row.
boolean	isAutomaticPurging()
boolean	isEmpty()
protected void	move(int num_rows) Moves contents of matrix num_rows down.
void	purge(long seqno) Removes all messages less than or equal to seqno from the table.
boolean	put(long seqno, Message msg) Adds a new message to the index computed as a function of seqno
Message	putIfAbsent(long seqno, Message msg) Adds a message if the element at the given index is null.
Message	remove(long seqno) Removes the message with seqno from the table, nulls the index
protected void	resize(long seqno) Moves rows down the matrix, by removing purged rows.
void	setAutomaticPurging(boolean automatic_purging)
void	setMaxCompactionTime(long max_compaction_time)
int	size() Returns the numbers of messages in the table
long	sizeOfAllMessages(boolean include_headers) Computes the size of all messages currently in the table.
java.lang.String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

num_rows

protected final int num_rows

msgs_per_row

protected final int msgs_per_row

resize_factor

protected final double resize_factor

matrix

protected Message[][] matrix

offset

protected long offset

The first seqno, at matrix[0][0]

size

protected int size

highest_seqno_purged

protected long highest_seqno_purged

The highest seqno purged

highest_seqno

protected long highest_seqno

The highest seqno in the table

max_compaction_time

protected long max_compaction_time

Time (in ms) after which a compaction should take place. 0 disables compaction

last_compaction_timestamp

protected long last_compaction_timestamp

The time when the last compaction took place. If a compact() takes place and sees that the last compaction is more than max_compaction_time ms ago, a compaction will take place

automatic_purging

protected boolean automatic_purging

By default, rows are only nulled and highest_seqno_purged is adjusted when purge(long) is called. When automatic_purging is enabled (default is off), rows are purged and highest_seqno_purged is adjusted on remove(long)

DEFAULT_MAX_COMPACTION_TIME

protected static final long DEFAULT_MAX_COMPACTION_TIME

See Also:

Constant Field Values

DEFAULT_RESIZE_FACTOR

protected static final double DEFAULT_RESIZE_FACTOR

See Also:

Constant Field Values

log

protected static final Log log

Constructor Detail

RetransmitTable

public RetransmitTable()

RetransmitTable

public RetransmitTable(int num_rows,
                       int msgs_per_row,
                       long offset)

RetransmitTable

public RetransmitTable(int num_rows,
                       int msgs_per_row,
                       long offset,
                       double resize_factor)

RetransmitTable

public RetransmitTable(int num_rows,
                       int msgs_per_row,
                       long offset,
                       double resize_factor,
                       long max_compaction_time,
                       boolean automatic_purging)

Method Detail

getOffset

public long getOffset()

capacity

public int capacity()

Returns the total capacity in the matrix

size

public int size()

Returns the numbers of messages in the table

isEmpty

public boolean isEmpty()

getHighest

public long getHighest()

getHighestPurged

public long getHighestPurged()

getMaxCompactionTime

public long getMaxCompactionTime()

setMaxCompactionTime

public void setMaxCompactionTime(long max_compaction_time)

isAutomaticPurging

public boolean isAutomaticPurging()

setAutomaticPurging

public void setAutomaticPurging(boolean automatic_purging)

getFillFactor

public double getFillFactor()

Returns the ratio between size and capacity, as a percentage

put

public boolean put(long seqno,
                   Message msg)

Adds a new message to the index computed as a function of seqno

Parameters:

seqno -

msg -

Returns:

True if the element at the computed index was null, else false

putIfAbsent

public Message putIfAbsent(long seqno,
                           Message msg)

Adds a message if the element at the given index is null. Returns null if no message existed at the given index, else returns the existing message and doesn't set the element.

Parameters:

seqno -

msg -

Returns:

The existing message, or null if there wasn't any

get

public Message get(long seqno)

get

public java.util.List<Message> get(long from,
                                   long to)

remove

public Message remove(long seqno)

Removes the message with seqno from the table, nulls the index

clear

public void clear()

Removes all elements. This method is usually called just before removing a retransmit table, so typically it is not used anymore after returning

purge

public void purge(long seqno)

Removes all messages less than or equal to seqno from the table. Does this by nulling entire rows in the matrix and nulling all elements < index(seqno) of the first row that cannot be removed

Parameters:

seqno -

resize

protected void resize(long seqno)

Moves rows down the matrix, by removing purged rows. If resizing to accommodate seqno is still needed, computes a new size. Then either moves existing rows down, or copies them into a new array (if resizing took place)

move

protected void move(int num_rows)

Moves contents of matrix num_rows down. Avoids a System.arraycopy()

compact

public void compact()

Moves the contents of matrix down by the number of purged rows and resizes the matrix accordingly. The capacity of the matrix should be size * resize_factor

computeSize

public int computeSize()

Iterate from highest_seqno_purged to highest_seqno and add up non-null values

getNullMessages

public int getNullMessages(long from,
                           long to)

Returns the number of null elements in the range [from .. to], excluding 'from' and 'to'

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

dump

public java.lang.String dump()

Dumps the seqnos in the table as a list

dumpMatrix

public java.lang.String dumpMatrix()

Dumps the non-null in the table in a pseudo graphic way

sizeOfAllMessages

public long sizeOfAllMessages(boolean include_headers)

Computes the size of all messages currently in the table. This includes messages that haven't been purged or compacted yet.

Parameters:

include_headers - If true, Message.size() is used, which will include the size of all headers and the dest and src addresses. Else Message.getLength() is used to compute. Note that the latter is way more efficient.

Returns:

Number of bytes of all messages.

getRow

protected Message[] getRow(int index)

Returns a row. Creates a new row and inserts it at index if the row at index doesn't exist

Parameters:

index -

Returns:

A row

computeRow

protected int computeRow(long seqno)

Computes and returns the row index for seqno

computeIndex

protected int computeIndex(long seqno)

Computes and returns the index within a row for seqno