java.lang.Object
net.i2p.kademlia.KBucketImpl<T>
Type Parameters:
T - type of SimpleDataStructure objects stored in this bucket
All Implemented Interfaces:
KBucket<T>
class KBucketImpl<T extends SimpleDataStructure>extends Object implements KBucket<T>
A concurrent implementation using ConcurrentHashSet. The max size (K) may be temporarily exceeded due to concurrency, a pending split, or the behavior of the supplied trimmer, as explained below. The creator is responsible for splits.

This class has no knowledge of the DHT base used for XORing, and thus there are no validity checks in add/remove.

The begin and end values are immutable. All entries in this bucket will have at least one bit different from us in the range [begin, end] inclusive. Splits must be implemented by creating two new buckets and discarding this one.

The keys are kept in a Set and are NOT sorted by last-seen. Per-key last-seen-time, failures, etc. must be tracked elsewhere.

If this bucket is full (i.e. begin == end && size >= max) then add() will call KBucketTrimmer.trim(KBucket, K) do (possibly) remove older entries, and indicate whether to add the new entry. If the trimmer returns true without removing entries, this KBucket will exceed the max size.

A newcomer rejected by a full bucket is not thrown away but held in a small Kademlia replacement cache and promoted into the bucket when a slot frees up, so live candidates survive transient bucket pressure instead of needing to be re-discovered.

Refactored from net.i2p.router.networkdb.kademlia.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private final int
    _begin
    Include if any bits equal or higher to this bit (in big endian order).
    private final I2PAppContext
    _context
    Supplies the clock and the random.
    private final int
    _end
    Include if no bits higher than this bit (inclusive) are set.
    private final Set<T>
    _entries
    The peers in the kbucket, stored in a set.
    private long
    _lastChanged
    When did we last shake things up.
    private final int
    _max
    Contacts the bucket holds before splitting.
    private final int
    _replacementMax
    Replacement cache capacity, bounded so 2048 buckets stay cheap.
    private final LinkedHashSet<T>
    _replacements
    Kademlia replacement cache — newcomers rejected by a full bucket, insertion-ordered, oldest dropped when over capacity.
    private final KBucketTrimmer<T>
    _trimmer
    Chooses which contact to drop when the bucket is full.

  • Constructor Summary

    Constructors
    Constructor
    Description
    KBucketImpl(I2PAppContext context, int begin, int end, int max, KBucketTrimmer<T> trimmer)
    All entries in this bucket will have at least one bit different from us in the range [begin, end] inclusive.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    add(T peer)
    Updates last-changed if rv is true OR if the peer is already present.
    void
    clear()
    Remove all entries from this bucket.
    Set<T>
    getEntries()
    Unmodifiable view of the entries in this bucket.
    void
    getEntries(SelectionCollector<T> collector)
    Add all entries in this bucket to the provided collector.
    int
    getKeyCount()
    Number of keys already contained in this kbucket.
    long
    getLastChanged()
    The last-changed timestamp, which actually indicates last-added or last-seen.
    int
    getRangeBegin()
    Lowest order high bit for difference keys.
    int
    getRangeEnd()
    Highest high bit for the difference keys.
    (package private) int
    getReplacementCount()
    Number of held replacement candidates.
    private void
    offerReplacement(T peer)
    Hold a rejected newcomer as a future slot-filler, dropping the oldest candidate when over capacity.
    private T
    pollReplacement()
    Take the newest replacement candidate, or null if the cache is empty.
    boolean
    remove(T peer)
    Remove the peer from this bucket.
    void
    setLastChanged()
    Update the last-changed timestamp to now.
    String
    toString()
     

    Methods inherited from class Object

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

  • Field Details

    • _entries

      private final Set<T extends SimpleDataStructure> _entries
      The peers in the kbucket, stored in a set.

    • _begin

      private final int _begin
      Include if any bits equal or higher to this bit (in big endian order).

    • _end

      private final int _end
      Include if no bits higher than this bit (inclusive) are set.

    • _max

      private final int _max
      Contacts the bucket holds before splitting.

    • _trimmer

      private final KBucketTrimmer<T extends SimpleDataStructure> _trimmer
      Chooses which contact to drop when the bucket is full.

    • _replacements

      private final LinkedHashSet<T extends SimpleDataStructure> _replacements
      Kademlia replacement cache — newcomers rejected by a full bucket, insertion-ordered, oldest dropped when over capacity. Guarded by its own monitor; never exposed outside this class except for the test hook.

    • _replacementMax

      private final int _replacementMax
      Replacement cache capacity, bounded so 2048 buckets stay cheap.

    • _lastChanged

      private long _lastChanged
      When did we last shake things up.

    • _context

      private final I2PAppContext _context
      Supplies the clock and the random.

  • Constructor Details

    • KBucketImpl

      public KBucketImpl(I2PAppContext context, int begin, int end, int max, KBucketTrimmer<T> trimmer)
      All entries in this bucket will have at least one bit different from us in the range [begin, end] inclusive.
      Parameters:
      context - the router context
      begin - the range begin
      end - the range end
      max - the maximum entries per bucket
      trimmer - the trim strategy

  • Method Details

    • getRangeBegin

      public int getRangeBegin()
      Description copied from interface: KBucket
      Lowest order high bit for difference keys. The lower-bounds distance of this bucket is 2**begin. If begin == 0, this is the closest bucket.
      Specified by:
      getRangeBegin in interface KBucket<T extends SimpleDataStructure>
      Returns:
      the beginning of this bucket's range

    • getRangeEnd

      public int getRangeEnd()
      Description copied from interface: KBucket
      Highest high bit for the difference keys. The upper-bounds distance of this bucket is (2**(end+1)) - 1. If begin == end, the bucket cannot be split further. If end == (numbits - 1), this is the furthest bucket.
      Specified by:
      getRangeEnd in interface KBucket<T extends SimpleDataStructure>
      Returns:
      the end of this bucket's range

    • getKeyCount

      public int getKeyCount()
      Description copied from interface: KBucket
      Number of keys already contained in this kbucket.
      Specified by:
      getKeyCount in interface KBucket<T extends SimpleDataStructure>
      Returns:
      the number of entries in this bucket

    • getEntries

      public Set<T> getEntries()
      Unmodifiable view of the entries in this bucket.
      Specified by:
      getEntries in interface KBucket<T extends SimpleDataStructure>
      Returns:
      an unmodifiable view; not a copy

    • getEntries

      public void getEntries(SelectionCollector<T> collector)
      Description copied from interface: KBucket
      Add all entries in this bucket to the provided collector.
      Specified by:
      getEntries in interface KBucket<T extends SimpleDataStructure>
      Parameters:
      collector - the collector to add entries to

    • clear

      public void clear()
      Description copied from interface: KBucket
      Remove all entries from this bucket.
      Specified by:
      clear in interface KBucket<T extends SimpleDataStructure>

    • add

      public boolean add(T peer)
      Updates last-changed if rv is true OR if the peer is already present. Calls the trimmer if begin == end and we are full. If the trimmer rejects the newcomer it is kept in the replacement cache for promotion when a slot frees up. If begin != end then add it and caller must do bucket splitting.
      Specified by:
      add in interface KBucket<T extends SimpleDataStructure>
      Parameters:
      peer - the key to store; a full bucket may still accept it if the trimmer makes room
      Returns:
      true if added

    • remove

      public boolean remove(T peer)
      Remove the peer from this bucket. If a slot frees up, the newest replacement candidate (if any) is promoted into the bucket.
      Specified by:
      remove in interface KBucket<T extends SimpleDataStructure>
      Parameters:
      peer - the key to evict from this bucket
      Returns:
      if removed. Does NOT set lastChanged.

    • offerReplacement

      private void offerReplacement(T peer)
      Hold a rejected newcomer as a future slot-filler, dropping the oldest candidate when over capacity.
      Parameters:
      peer - the rejected newcomer to hold for a future free slot

    • pollReplacement

      private T pollReplacement()
      Take the newest replacement candidate, or null if the cache is empty.
      Returns:
      the most recently held candidate, removed from the cache, or null if it was empty

    • getReplacementCount

      int getReplacementCount()
      Number of held replacement candidates. Package private for testing.
      Returns:
      the count of candidates currently in the replacement cache

    • setLastChanged

      public void setLastChanged()
      Update the last-changed timestamp to now.
      Specified by:
      setLastChanged in interface KBucket<T extends SimpleDataStructure>

    • getLastChanged

      public long getLastChanged()
      The last-changed timestamp, which actually indicates last-added or last-seen.
      Specified by:
      getLastChanged in interface KBucket<T extends SimpleDataStructure>
      Returns:
      the last changed

    • toString

      public String toString()
      Overrides:
      toString in class Object