net.i2p.router.util

## Class DecayingBloomFilter

- java.lang.Object
- - net.i2p.router.util.DecayingBloomFilter

- Direct Known Subclasses:
    DecayingHashSet

      public class DecayingBloomFilter
      extends Object

  Time-decaying Bloom filter series for efficient data management.

  Provides a series of Bloom filters with automatic time-based decay to handle time-sensitive data with minimal false positive rates. Uses fixed-size buffers with periodic switching to maintain consistent memory usage while allowing high-throughput operations.

  Optimized for scenarios requiring hundreds of entries per second with virtually no false positive rate. Memory usage is carefully controlled through configurable filter parameters and buffer sizes.

  Performance characteristics:

  - Configurable m and k parameters for optimal false positive rates
  - Automatic buffer switching and decay operations
  - Thread-safe with read/write lock coordination
  - Comprehensive statistics tracking and performance monitoring

  Suitable for high-throughput applications like message validation, tunnel IV filtering, and router message processing where memory efficiency and low false positive rates are critical.

  See Also:
    `DecayingHashSet`, `BloomFilterIVValidator`

- - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `protected I2PAppContext` | `_context`
    `protected long` | `_currentDuplicates`
    `protected SimpleTimer2.TimedEvent` | `_decayEvent`
    `protected int` | `_durationMs`
    `protected int` | `_entryBytes`
    `protected boolean` | `_keepDecaying`
    `protected Log` | `_log`
    `protected String` | `_name` just for logging
    `protected ReentrantReadWriteLock` | `_reorganizeLock` synchronize against this lock when switching double buffers

  - ### Constructor Summary

    Constructors
    Modifier | Constructor and Description
    --- | ---
    `` | `DecayingBloomFilter(I2PAppContext context, int durationMs, int entryBytes)` Create a bloom filter that will decay its entries over time.
    `` | `DecayingBloomFilter(I2PAppContext context, int durationMs, int entryBytes, String name)` Uses default m of 23, memory usage is 2 MB.
    `` | `DecayingBloomFilter(I2PAppContext context, int durationMs, int entryBytes, String name, int m)` Memory usage is 2 * (2**m) bits or 2**(m-2) bytes.
    `protected` | `DecayingBloomFilter(int durationMs, int entryBytes, String name, I2PAppContext context)` only for extension by DHS

  - ### Method Summary

    All Methods Instance Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `boolean` | `add(byte[] entry)`
    `boolean` | `add(byte[] entry, int off, int len)`
    `boolean` | `add(long entry)`
    `void` | `clear()`
    `protected void` | `decay()`
    `long` | `getCurrentDuplicateCount()`
    `double` | `getFalsePositiveRate()` unsynchronized, only used for logging elsewhere
    `int` | `getInsertedCount()` unsynchronized but only used for logging elsewhere
    `protected void` | `getReadLock()`
    `protected boolean` | `getWriteLock()`
    `boolean` | `isKnown(long entry)`
    `protected void` | `releaseReadLock()`
    `protected void` | `releaseWriteLock()`
    `void` | `stopDecaying()`

    - ### Methods inherited from class java.lang.Object

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

- - ### Field Detail

    - #### _context

          protected final I2PAppContext _context

    - #### _currentDuplicates

          protected long _currentDuplicates

    - #### _decayEvent

          protected final SimpleTimer2.TimedEvent _decayEvent

    - #### _durationMs

          protected final int _durationMs

    - #### _entryBytes

          protected final int _entryBytes

    - #### _keepDecaying

          protected volatile boolean _keepDecaying

    - #### _log

          protected final Log _log

    - #### _name

          protected final String _name

      just for logging

    - #### _reorganizeLock

          protected final ReentrantReadWriteLock _reorganizeLock

      synchronize against this lock when switching double buffers

  - ### Constructor Detail

    - #### DecayingBloomFilter

          public DecayingBloomFilter(I2PAppContext context,
                                     int durationMs,
                                     int entryBytes)

      Create a bloom filter that will decay its entries over time. Uses default m of 23, memory usage is 2 MB.
      Parameters:
        `durationMs` - entries last for at least this long, but no more than twice this long
        `entryBytes` - how large are the entries to be added? if this is less than 32 bytes, the entries added will be expanded by concatenating their XORing against with sufficient random values.

    - #### DecayingBloomFilter

          public DecayingBloomFilter(I2PAppContext context,
                                     int durationMs,
                                     int entryBytes,
                                     String name)

      Uses default m of 23, memory usage is 2 MB.
      Parameters:
        `name` - just for logging / debugging / stats

    - #### DecayingBloomFilter

          public DecayingBloomFilter(I2PAppContext context,
                                     int durationMs,
                                     int entryBytes,
                                     String name,
                                     int m)

      Memory usage is 2 * (2**m) bits or 2**(m-2) bytes.
      Parameters:
        `m` - filter size exponent, max is 29

    - #### DecayingBloomFilter

          protected DecayingBloomFilter(int durationMs,
                                        int entryBytes,
                                        String name,
                                        I2PAppContext context)

      only for extension by DHS

  - ### Method Detail

    - #### add

          public boolean add(byte[] entry)

      Returns:
        true if the entry added is a duplicate

    - #### add

          public boolean add(byte[] entry,
                             int off,
                             int len)

      Returns:
        true if the entry added is a duplicate

    - #### add

          public boolean add(long entry)

      Returns:
        true if the entry added is a duplicate. the number of low order bits used is determined by the entryBytes parameter used on creation of the filter.

    - #### clear

          public void clear()

    - #### decay

          protected void decay()

    - #### getCurrentDuplicateCount

          public long getCurrentDuplicateCount()

    - #### getFalsePositiveRate

          public double getFalsePositiveRate()

      unsynchronized, only used for logging elsewhere

    - #### getInsertedCount

          public int getInsertedCount()

      unsynchronized but only used for logging elsewhere

    - #### getReadLock

          protected void getReadLock()

    - #### getWriteLock

          protected boolean getWriteLock()

      Returns:
        true if the lock was acquired

    - #### isKnown

          public boolean isKnown(long entry)

      Returns:
        true if the entry is already known. this does NOT add the entry however.

    - #### releaseReadLock

          protected void releaseReadLock()

    - #### releaseWriteLock

          protected void releaseWriteLock()

    - #### stopDecaying

          public void stopDecaying()