net.i2p.kademlia
Class KBucketSet<T extends SimpleDataStructure>

java.lang.Object
  extended by net.i2p.kademlia.KBucketSet<T>

public class KBucketSet<T extends SimpleDataStructure>
extends Object

In-memory storage of buckets sorted by the XOR metric from the base (us) passed in via the constructor. This starts with one bucket covering the whole key space, and may eventually be split to a max of the number of bits in the data type (160 for SHA1Hash or 256 for Hash), times 2**(B-1) for Kademlia value B. Refactored from net.i2p.router.networkdb.kademlia

Since:
0.9.2 in i2psnark, moved to core in 0.9.10

Constructor Summary
KBucketSet(I2PAppContext context, T us, int max, int b)
          Use the default trim strategy, which removes a random entry.
KBucketSet(I2PAppContext context, T us, int max, int b, KBucketTrimmer<T> trimmer)
          Use the supplied trim strategy.
 
Method Summary
 boolean add(T peer)
           
 void clear()
           
(package private)  T generateRandomKey(KBucket<T> bucket)
          Generate a random key to go within this bucket Package private for testing only.
 Set<T> getAll()
           
 void getAll(SelectionCollector<T> collector)
           
 Set<T> getAll(Set<T> toIgnore)
           
(package private)  List<KBucket<T>> getBuckets()
          Returned list is a copy of the bucket list, closest first, with the actual buckets (not a copy).
 List<T> getClosest(int max)
          The keys closest to us.
 List<T> getClosest(int max, Collection<T> toIgnore)
          The keys closest to us.
 List<T> getClosest(T key, int max)
          The keys closest to the key.
 List<T> getClosest(T key, int max, Collection<T> toIgnore)
          The keys closest to the key.
 List<T> getExploreKeys(long age)
          For every bucket that hasn't been updated in this long, or isn't close to full, generate a random key that would be a member of that bucket.
(package private)  int getRange(T key)
          The number of bits minus 1 (range number) for the xor of the key.
 boolean remove(T entry)
           
 int size()
          The current number of entries.
 String toString()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

KBucketSet

public KBucketSet(I2PAppContext context,
                  T us,
                  int max,
                  int b)
Use the default trim strategy, which removes a random entry.

Parameters:
us - the local identity (typically a SHA1Hash or Hash) The class must have a zero-argument constructor.
max - the Kademlia value "k", the max per bucket, k >= 4
b - the Kademlia value "b", split buckets an extra 2**(b-1) times, b > 0, use 1 for bittorrent, Kademlia paper recommends 5

KBucketSet

public KBucketSet(I2PAppContext context,
                  T us,
                  int max,
                  int b,
                  KBucketTrimmer<T> trimmer)
Use the supplied trim strategy.

Method Detail

add

public boolean add(T peer)
Returns:
true if the peer is new to the bucket it goes in, or false if it was already in it. Always returns false on an attempt to add ourselves.

size

public int size()
The current number of entries.


remove

public boolean remove(T entry)

clear

public void clear()
Since:
0.8.8

getAll

public Set<T> getAll()
Returns:
a copy in a new set

getAll

public Set<T> getAll(Set<T> toIgnore)
Returns:
a copy in a new set

getAll

public void getAll(SelectionCollector<T> collector)

getClosest

public List<T> getClosest(int max)
The keys closest to us. Returned list will never contain us.

Returns:
non-null, closest first

getClosest

public List<T> getClosest(int max,
                          Collection<T> toIgnore)
The keys closest to us. Returned list will never contain us.

Returns:
non-null, closest first

getClosest

public List<T> getClosest(T key,
                          int max)
The keys closest to the key. Returned list will never contain us.

Returns:
non-null, closest first

getClosest

public List<T> getClosest(T key,
                          int max,
                          Collection<T> toIgnore)
The keys closest to the key. Returned list will never contain us.

Returns:
non-null, closest first

getBuckets

List<KBucket<T>> getBuckets()
Returned list is a copy of the bucket list, closest first, with the actual buckets (not a copy). Primarily for testing. You shouldn't ever need to get all the buckets. Use getClosest() or getAll() instead to get the keys.

Returns:
non-null

getRange

int getRange(T key)
The number of bits minus 1 (range number) for the xor of the key. Package private for testing only. Others shouldn't need this.

Returns:
0 to max-1 or -1 for us

getExploreKeys

public List<T> getExploreKeys(long age)
For every bucket that hasn't been updated in this long, or isn't close to full, generate a random key that would be a member of that bucket. The returned keys may be searched for to "refresh" the buckets.

Returns:
non-null, closest first

generateRandomKey

T generateRandomKey(KBucket<T> bucket)
Generate a random key to go within this bucket Package private for testing only. Others shouldn't need this.


toString

public String toString()
Overrides:
toString in class Object