Package com.tangosol.io.nio

Class BinaryMap

java.lang.Object
java.util.AbstractMap
com.tangosol.io.nio.BinaryMap
All Implemented Interfaces:
Map
public class BinaryMap extends AbstractMap
Implements the Map interface to store Binary objects using Java's NIO buffers. 
 The Buffer is used to hold blocks, which are either Entry or free blocks.
 Both share a common header:

   byte    length      type     description
   ------  ----------  -------  -------------------------------------------
        0           1  integer  type
        1           4  integer  offset of the next block in the Buffer
        5           4  integer  offset of the prev block in the Buffer
        9           4  integer  offset of the next entry in the list or -1=tail
       13           4  integer  offset of the prev entry in the list or -1=head

 The offset of the next block in the buffer provides the "length overall"
 (also known as LOA) of the block, such that a block located at offset
 "oCur" with a next block offset of "oNext" will have an LOA "l" of:

       l = oNext - oCur

 The additional structure for an Entry block is as follows:

   byte    length      type     description
   ------  ----------  -------  -------------------------------------------
       17           4  integer  hash code
       21           4  integer  key length (m)
       25           m  byte[]   key
     25+m           4  integer  value length (n)
     29+m           n  byte[]   value
   29+m+n  l-(29+m+n)  byte[]   fill

 The reason for supporting "fill" is to allow an entry to shrink and grow
 a little bit in place, for example since a free block has a minimum size
 and if the entry is followed immediately by another entry and shrinks, it
 would have to be moved if it doesn't shrink at least 17 bytes. Similarly,
 an entry could be padded to allow it to grow slightly.

 The additional structure for a free block is as follows:

   byte    length      type     description
   ------  ----------  -------  -------------------------------------------
       17        l-17  byte[]   fill

 The Buffer is a packed list of blocks, and each block is either an Entry or
 a free block. Contiguous free blocks are automatically merged so that there
 are never any contiguous free blocks at the end of an operation. Entries
 are expected to be contiguously allocated; compaction is the act of copying
 Entry blocks so that they are contiguous.

 The BinaryMap manages an array of hash buckets that hold the offsets of the
 first Entry in the linked list of entries stored in the Buffer. The offset
 will be NIL (-1) if there are no entries in that bucket since 0 is a valid
 offset into the Buffer.

 Incremental compaction occurs only on modifications (puts and removes).
 For a put, the compaction occurs before the put is processed, and for a
 remove, it occurs after the remove is processed, to make it slightly more
 likely that a put will have adequate free space and that the removed entry
 would not have been relocated by compaction.

 The BinaryMap categorizes empty blocks based on their size:

   code  free block size
   ----  -----------------------------------
      0  63 bytes or smaller
      1  64 to 127 bytes
      2  128 to 255 bytes
      3  256 to 511 bytes
      4  512 to 1023 bytes
      5  1024 to 2047 bytes
      6  2048 to 4095 bytes
      7  4096 to 8191 bytes
      8  8192 to 16383 bytes
      9  16384 to 32767 bytes
     10  32768 to 65535 bytes
     11  65536 to 131071 bytes
     12  131072 to 262143 bytes
     13  262144 to 524287 bytes
     14  524288 to 1048575 bytes
     15  1048576 to 2097151 bytes
     16  2097152 to 4194303 bytes
     17  4194304 to 8388607 bytes
     18  8388608 to 16777215 bytes
     19  16777216 to 33554431 bytes
     20  33554432 to 67108863 bytes
     21  67108864 to 134217727 bytes
     22  134217728 to 268435455 bytes
     23  268435456 to 536870911 bytes
     24  536870912 to 1073741823 bytes
     25  1073741824 to 2147483647 bytes

 For each category of free blocks, the BinaryMap maintains a linked list of
 free blocks that fit that category.

 To determine the size of a block in bytes, use the length() method. To
 calculate the code of a block, use the getSizeCode() method, or the static
 calculateSizeCode(int) method of BinaryMap.

 To open an existing block at a certain offset, use the method
 openBlock(int). To create and open a block at a certain offset, use the
 method initBlock(int). To allocate and open a free block of a certain size,
 use the method allocateBlock(int). An opened block should always be closed
 using the method Block.close(), which commits pending changes to the
 underlying buffer. The only time that a block should not be closed is when
 the block is being destroyed (e.g. when a free block is merged with another
 free block); in this case, use the method Block.discard().

 To merge free blocks that occur before and/or after a specific free block,
 use the method Block.merge(). To split a free block into two contiguous
 free blocks, use the method Block.split(int).

 To remove a block from its linked list, use Block.unlink(). Unless the
 block is being destroyed, it should be re-linked using the Block.link()
 method.
Since:
Coherence 2.2
Version:
1.00, 2002-09-06
Author:
cp

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    class 
    BinaryMap.Block
    A Block is the unit of storage within a Buffer.
    static class 
    BinaryMap.Entry
    A map entry (key-value pair).
    class 
    BinaryMap.EntrySet
    A set of entries backed by this map.
    protected class 
    BinaryMap.KeySet
    A set of entries backed by this map.
    protected class 
    BinaryMap.ValuesCollection
    A collection of values backed by this map.

    Nested classes/interfaces inherited from class java.util.AbstractMap

    AbstractMap.SimpleEntry<K,V>, AbstractMap.SimpleImmutableEntry<K,V>

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected static final int[]
    BUCKET_COUNTS
    These are potential bucket counts.
    static final double
    DEFAULT_MAXLOADFACTOR
    Default value for the percentage of the modulo that the entry count must reach before going to the next bucket level.
    static final double
    DEFAULT_MINLOADFACTOR
    Default value for the percentage of the next lower bucket level's modulo that the entry count must drop to before reverting to the next lower bucket level.
    protected static final byte[]
    FILL_BUFFER
    Byte array used for wiping the buffer.
    protected static final byte
    FILL_BYTE
    Byte used as a fill byte.
    protected BinaryMap.ValuesCollection
    m_colValues
    The collection of values backed by this map.
    protected BinaryMap.EntrySet
    m_set
    The set of entries backed by this map.
    protected BinaryMap.KeySet
    m_setKeys
    The set of keys backed by this map.
    protected static final int
    MAX_OPEN_BLOCKS
    Maximum number of simultaneously open blocks to support.
    protected static final int
    MAX_SIZE_CODES
    Number of size codes for free blocks.
    protected static final boolean
    MODE_DEBUG
    True to enable debug mode.
    protected static final int
    NIL
    Offset reserved for the "does-not-exist" block.
    protected static final int
    SIZE_COPY_BUFFER
    Copy buffer size.

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    BinaryMap()
    Construct a BinaryMap.
     
    BinaryMap(ByteBufferManager bufmgr)
    Construct a BinaryMap using a buffer from the specified ByteBufferManager, and using the default modulo growth and shrinkage (load factor) settings.
     
    BinaryMap(ByteBufferManager bufmgr, double dflMaxLoadFactor, double dflMinLoadFactor, boolean fStrict)
    Construct a BinaryMap using a buffer from the specified ByteBufferManager, and using the specified modulo growth and shrinkage (load factor) settings.
     
    BinaryMap(ByteBuffer buffer)
    Construct a BinaryMap on a specific buffer with the default modulo growth and shrinkage (load factor) settings.
     
    BinaryMap(ByteBuffer buffer, double dflMaxLoadFactor, double dflMinLoadFactor, boolean fStrict)
    Construct a BinaryMap on a specific buffer with the specified modulo growth and shrinkage (load factor) settings.

  • Method Summary

    Modifier and Type
    Method
    Description
    protected void
    adjustOpenBlockOffset(int ofOld, int ofNew)
    When an open block changes position in the buffer, this method is invoked to adjust the cache of open blocks.
    protected BinaryMap.Block
    allocateBlock(int cb)
    Allocate a free Block object of at least a certain size.
    protected static Binary
    bin(String s)
    Internal debugging support: Turn a String into a Binary.
    protected static void
    buffercopy(ByteBuffer buffer, int ofCopyFrom, int ofCopyTo, int cbCopy, byte[] abBuf)
    Copy from one part of the buffer to another.
    protected int
    calculateBucket(int nHash)
    Calculate the bucket for the specified hash code.
    protected int
    calculatePreviousBucket(int nHash)
    Calculate the old bucket for the specified hash code.
    protected static int
    calculateSizeCode(int cbBlock)
    Determine which "free bucket" a block of a particular size would go into.
    void
    check(String sDesc)
    Debugging support: Validate the buffer's data structures, the hash buckets, free lists, etc.
    protected void
    checkBufferGrow(int cbAdditional)
    If there is a buffer manager, check if the current buffer should be grown.
    protected void
    checkBufferShrink()
    If there is a buffer manager, check if the current buffer should be shrunk.
    protected void
    checkModulo()
    Determine if the modulo should be changed.
    void
    clear()
    Removes all mappings from this map.
    protected void
    clearBucketOffsets()
    Clear out all references in the array of hash buckets.
    protected void
    clearBucketOffsets(int nBucket)
    Clear out all references in the array of hash buckets starting with the specified bucket.
    protected void
    clearBuffer()
    Create one big free block in the buffer.
    protected void
    clearFreeLists()
    Clear out all references in the array of free lists.
    protected void
    compactAll()
    Full linear compaction of the buffer.
    protected void
    compactBegin()
    Configure the incremental compact.
    protected void
    compactComplete()
    Complete the incremental compact.
    protected void
    compactNext()
    Perform an incremental compaction of the next block.
    protected void
    compactUntil(int cbReqFree)
    Perform an an incremental compact at the specified block.
    boolean
    containsKey(Object oKey)
    Returns true if this map contains a mapping for the specified key.
    void
    dump()
    Debugging support: Dump the inner structures of the BinaryMap to stdout.
    Set
    entrySet()
    Returns a set view of the mappings contained in this map.
    protected BinaryMap.Block
    findEntryBlock(Binary binKey)
    Find the Entry block with the specified key.
    protected static String
    formatIndex(int n)
    Format an index to a String.
    protected static String
    formatOffset(int of)
    Format an offset to a String.
    protected static String
    formatOffsetArray(int[] an)
    Format an array of offsets to be readable in a dump.
    Object
    get(Object oKey)
    Returns the value to which this map maps the specified key.
    protected int
    getBucketCount()
    Determine the number of hash buckets.
    protected int
    getBucketLevel()
    Determine the hash bucket level.
    protected int
    getBucketOffset(int nBucket)
    Get the first Entry block in the linked list of Entry blocks that fall into a certain hash bucket.
    protected ByteBuffer
    getBuffer()
    Obtain the ByteBuffer that the BinaryMap is backed by.
    protected DataInputStream
    getBufferInput()
    Get the DataInputStream that maps to the underlying ByteBuffer.
    ByteBufferManager
    getBufferManager()
    Obtain the ByteBufferManager that provides the ByteBuffer objects.
    protected DataOutputStream
    getBufferOutput()
    Get the DataOutputStream that maps to the underlying ByteBuffer.
    protected int
    getCapacity()
    Determine the capacity of the map in bytes.
    int
    getEntryBlockCount()
    Returns the number of entry blocks.
    protected int
    getFreeBlockOffset(int nCode)
    Get the first free block in the linked list of free blocks that have a certain size code.
    protected int
    getFreeCapacity()
    Determine the free capacity of the map in bytes.
    protected int
    getFreeListCount()
    Determine the number of free lists (ie the number of size codes).
    protected int
    getGrowthCount()
    Determine the level at which the modulo will increase.
    protected int
    getLastBlockOffset()
    Get the offset of the last block in the buffer.
    protected double
    getMaxLoadFactor()
    Determine the load factor for the map.
    protected double
    getMinLoadFactor()
    Determine the "unload factor" for the map.
    protected int
    getModulo()
    Determine the current modulo.
    protected int
    getNextCompactBlock()
    Determine the next block to compact.
    protected int
    getNextRehashBucket()
    Determine the next bucket to rehash.
    protected int
    getPreviousModulo()
    Determine the previous modulo.
    protected int
    getShrinkageCount()
    Determine the level at which the modulo will decrease.
    protected int
    getUsedCapacity()
    Determine the number of types in the buffer that are in use by Entry blocks.
    protected BinaryMap.Block
    grabBlock(int ofBlock)
    Grab a block object for the specified offset.
    protected BinaryMap.Block
    initBlock(int of)
    Obtain a Block object for a new block that will be located at the specified offset in the ByteBuffer.
    protected void
    initializeBuckets()
    Create an initial array of hash buckets.
    protected void
    initializeFreeLists()
    Create an array of references to lists of free blocks indexed by size code.
    protected BinaryMap.Block
    instantiateBlock()
    Factory method: Create a Block object.
    protected BinaryMap.Entry
    instantiateEntry(Binary binKey, Binary binValue)
    Factory pattern: Instantiate an Entry object.
    protected BinaryMap.EntrySet
    instantiateEntrySet()
    Factory pattern.
    protected BinaryMap.KeySet
    instantiateKeySet()
    Factory pattern.
    protected BinaryMap.ValuesCollection
    instantiateValuesCollection()
    Factory pattern.
    protected boolean
    isCompacting()
    Determine if the map is incrementally compacting.
    boolean
    isEmpty()
    Returns true if this map contains no key-value mappings.
    protected boolean
    isRehashing()
    Determine if the map is incrementally rehashing.
    protected boolean
    isStrict()
    Determine if the buffer should be initialized and if blocks should be cleared when not in use.
    Set
    keySet()
    Returns a Set view of the keys contained in this map.
    static void
    main(String[] asArg)
    Debugging support: Command line test.
    protected BinaryMap.Block
    openBlock(int of)
    Obtain a Block object for the block located at the specified offset in the ByteBuffer.
    Object
    put(Object oKey, Object oValue)
    Associates the specified value with the specified key in this map.
    protected void
    recycleBlock(BinaryMap.Block block)
    Release (recycle) the specified Block object.
    protected void
    rehash(int nBucket)
    Rehash the specified bucket such that, when done, it will only contain keys that hash to it with the current modulo.
    protected void
    rehashAll()
    Rehash all blocks such that no block will be linked into the wrong bucket.
    protected void
    rehashBegin()
    Configure the incremental rehash.
    protected void
    rehashComplete()
    Complete the incremental rehash.
    protected void
    rehashNext()
    Rehash the next incremental rehash block.
    Object
    remove(Object oKey)
    Removes the mapping for this key from this map if present.
    protected RuntimeException
    reportOutOfMemory(int cbRequired)
    Report on an insufficient memory problem.
    protected void
    setBucketCount(int cBuckets)
    Configure the number of hash buckets.
    protected void
    setBucketLevel(int nLevel)
    Configure the hash bucket level.
    protected void
    setBucketOffset(int nBucket, int ofBlock)
    Set the head of the hash bucket linked list for a certain bucket.
    protected void
    setBuffer(ByteBuffer buffer)
    Specify the ByteBuffer that the BinaryMap will be backed by.
    protected void
    setBufferManager(ByteBufferManager bufmgr)
    Specify the ByteBufferManager for this map.
    protected void
    setFreeBlockOffset(int nCode, int ofBlock)
    Set the head of the free block linked list for a certain size code.
    protected void
    setGrowthCount(int cEntries)
    Set the level at which the modulo will increase.
    protected void
    setLastBlockOffset(int ofBlock)
    Set the offset of the last block in the buffer.
    protected void
    setMaxLoadFactor(double dflPercent)
    Set the load factor.
    protected void
    setMinLoadFactor(double dflPercent)
    Set the "unload factor".
    protected void
    setModulo(int nModulo)
    Set the new modulo.
    protected void
    setNextCompactBlock(int ofBlock)
    Set the next block to compact.
    protected void
    setNextRehashBucket(int nBucket)
    Set the next bucket to rehash.
    protected void
    setPreviousModulo(int nModulo)
    Set the old modulo.
    protected void
    setShrinkageCount(int cEntries)
    Set the level at which the modulo will decrease.
    protected void
    setStrict(boolean fStrict)
    Specify if the buffer should be initialized and if blocks should be cleared when not in use.
    int
    size()
    Returns the number of key-value mappings in this map.
    protected static String
    str(Object bin)
    Internal debugging support: Turn a Binary into a String.
    protected Object[]
    toArray(Object[] ao, Converter conv)
    Returns an array with a runtime type is that of the specified array and that contains data from all of the entries in this Map.
    protected RuntimeException
    validateEntry(Object key, Object value, RuntimeException e)
    If the passed key and/or value is not a Binary object, then throw an exception to specify that the key is not Binary, otherwise throw the original exception.
    protected RuntimeException
    validateKey(Object key, RuntimeException e)
    If the passed key is not Binary, then throw an exception to specify that the key is not Binary, otherwise throw the original exception.
    Collection
    values()
    Returns a collection view of the values contained in this map.
    protected void
    wipe(int of, int cb)
    Wipe a portion of the buffer.

    Methods inherited from class java.util.AbstractMap

    clone, containsValue, equals, hashCode, putAll, toString

    Methods inherited from class java.lang.Object

    finalize, getClass, notify, notifyAll, wait, wait, wait

    Methods inherited from interface java.util.Map

    compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, putIfAbsent, remove, replace, replace, replaceAll

  • Field Details

    • MODE_DEBUG

      protected static final boolean MODE_DEBUG
      True to enable debug mode.
      See Also:

    • FILL_BYTE

      protected static final byte FILL_BYTE
      Byte used as a fill byte.
      See Also:

    • FILL_BUFFER

      protected static final byte[] FILL_BUFFER
      Byte array used for wiping the buffer.

    • MAX_SIZE_CODES

      protected static final int MAX_SIZE_CODES
      Number of size codes for free blocks.
      See Also:

    • BUCKET_COUNTS

      protected static final int[] BUCKET_COUNTS
      These are potential bucket counts.

    • SIZE_COPY_BUFFER

      protected static final int SIZE_COPY_BUFFER
      Copy buffer size.
      See Also:

    • NIL

      protected static final int NIL
      Offset reserved for the "does-not-exist" block.
      See Also:

    • MAX_OPEN_BLOCKS

      protected static final int MAX_OPEN_BLOCKS
      Maximum number of simultaneously open blocks to support.
      See Also:

    • DEFAULT_MAXLOADFACTOR

      public static final double DEFAULT_MAXLOADFACTOR
      Default value for the percentage of the modulo that the entry count must reach before going to the next bucket level.
      See Also:

    • DEFAULT_MINLOADFACTOR

      public static final double DEFAULT_MINLOADFACTOR
      Default value for the percentage of the next lower bucket level's modulo that the entry count must drop to before reverting to the next lower bucket level.
      See Also:

    • m_set

      protected transient BinaryMap.EntrySet m_set
      The set of entries backed by this map.

    • m_setKeys

      protected transient BinaryMap.KeySet m_setKeys
      The set of keys backed by this map.

    • m_colValues

      protected transient BinaryMap.ValuesCollection m_colValues
      The collection of values backed by this map.

  • Constructor Details

    • BinaryMap

      public BinaryMap(ByteBuffer buffer)
      Construct a BinaryMap on a specific buffer with the default modulo growth and shrinkage (load factor) settings.
      Parameters:
      buffer - the ByteBuffer that the map will store its data in

    • BinaryMap

      public BinaryMap(ByteBuffer buffer, double dflMaxLoadFactor, double dflMinLoadFactor, boolean fStrict)
      Construct a BinaryMap on a specific buffer with the specified modulo growth and shrinkage (load factor) settings.
      Parameters:
      buffer - the ByteBuffer that the map will store its data in
      dflMaxLoadFactor - the percentage of the ratio of keys to the modulo at which the modulo will increase; for example, 0.9 implies that the modulo will grow when the number of keys reaches 90% of the modulo value
      dflMinLoadFactor - the percentage of the ratio of keys to the next lower modulo at which the modulo will decrease; this value must be less than the maximum load factor value
      fStrict - true to enable the strict (clean buffer) option, which will degrade performance slightly

    • BinaryMap

      public BinaryMap(ByteBufferManager bufmgr)
      Construct a BinaryMap using a buffer from the specified ByteBufferManager, and using the default modulo growth and shrinkage (load factor) settings.
      Parameters:
      bufmgr - the ByteBufferManager that is responsible for providing and managing the ByteBuffer

    • BinaryMap

      public BinaryMap(ByteBufferManager bufmgr, double dflMaxLoadFactor, double dflMinLoadFactor, boolean fStrict)
      Construct a BinaryMap using a buffer from the specified ByteBufferManager, and using the specified modulo growth and shrinkage (load factor) settings.
      Parameters:
      bufmgr - the ByteBufferManager that is responsible for providing and managing the ByteBuffer
      dflMaxLoadFactor - the percentage of the ratio of keys to the modulo at which the modulo will increase; for example, 0.9 implies that the modulo will grow when the number of keys reaches 90% of the modulo value
      dflMinLoadFactor - the percentage of the ratio of keys to the next lower modulo at which the modulo will decrease; this value must be less than the maximum load factor value
      fStrict - true to enable the strict (clean buffer) option, which will degrade performance slightly

    • BinaryMap

      protected BinaryMap()
      Construct a BinaryMap. This constructor is provided solely for inheriting implementations to avoid the requirements imposed by the public constructors.

  • Method Details

    • size

      public int size()
      Returns the number of key-value mappings in this map.
      Specified by:
      size in interface Map
      Overrides:
      size in class AbstractMap
      Returns:
      the number of entries in this map

    • isEmpty

      public boolean isEmpty()
      Returns true if this map contains no key-value mappings.
      Specified by:
      isEmpty in interface Map
      Overrides:
      isEmpty in class AbstractMap
      Returns:
      true if this map contains no key-value mappings

    • containsKey

      public boolean containsKey(Object oKey)
      Returns true if this map contains a mapping for the specified key.
      Specified by:
      containsKey in interface Map
      Overrides:
      containsKey in class AbstractMap
      Parameters:
      oKey - key whose presence in this map is to be tested
      Returns:
      true if this map contains a mapping for the specified key

    • get

      public Object get(Object oKey)
      Returns the value to which this map maps the specified key. Returns null if the map contains no mapping for this key.
      Specified by:
      get in interface Map
      Overrides:
      get in class AbstractMap
      Parameters:
      oKey - key whose associated value is to be returned
      Returns:
      the value to which this map maps the specified key, or null if the map contains no mapping for this key

    • put

      public Object put(Object oKey, Object oValue)
      Associates the specified value with the specified key in this map.
      Specified by:
      put in interface Map
      Overrides:
      put in class AbstractMap
      Parameters:
      oKey - key with which the specified value is to be associated
      oValue - value to be associated with the specified key
      Returns:
      previous value associated with specified key, or null if there was no mapping for key

    • remove

      public Object remove(Object oKey)
      Removes the mapping for this key from this map if present.
      Specified by:
      remove in interface Map
      Overrides:
      remove in class AbstractMap
      Parameters:
      oKey - key whose mapping is to be removed from the map
      Returns:
      previous value associated with specified key, or null if there was no mapping for key. A null return can also indicate that the map previously associated null with the specified key, if the implementation supports null values

    • clear

      public void clear()
      Removes all mappings from this map.
      Specified by:
      clear in interface Map
      Overrides:
      clear in class AbstractMap

    • entrySet

      public Set entrySet()
      Returns a set view of the mappings contained in this map. Each element in the returned set is a Map.Entry. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is modified while an iteration over the set is in progress, the results of the iteration are undefined. The set supports element removal, which removes the corresponding mapping from the map, via the Iterator.remove, Set.remove, removeAll, retainAll and clear operations. It does not support the add or addAll operations.
      Specified by:
      entrySet in interface Map
      Specified by:
      entrySet in class AbstractMap
      Returns:
      a set view of the mappings contained in this map.

    • keySet

      public Set keySet()
      Returns a Set view of the keys contained in this map. The Set is backed by the map, so changes to the map are reflected in the Set, and vice-versa. (If the map is modified while an iteration over the Set is in progress, the results of the iteration are undefined.) The Set supports element removal, which removes the corresponding entry from the map, via the Iterator.remove, Set.remove, removeAll retainAll, and clear operations. It does not support the add or addAll operations.

      Specified by:
      keySet in interface Map
      Overrides:
      keySet in class AbstractMap
      Returns:
      a Set view of the keys contained in this map

    • values

      public Collection values()
      Returns a collection view of the values contained in this map. The collection is backed by the map, so changes to the map are reflected in the collection, and vice-versa. If the map is modified while an iteration over the collection is in progress, the results of the iteration are undefined. The collection supports element removal, which removes the corresponding mapping from the map, via the Iterator.remove, Collection.remove, removeAll, retainAll and clear operations. It does not support the add or addAll operations.
      Specified by:
      values in interface Map
      Overrides:
      values in class AbstractMap
      Returns:
      a collection view of the values contained in this map

    • getEntryBlockCount

      public int getEntryBlockCount()
      Returns the number of entry blocks.
      Returns:
      the number of entry blocks

    • findEntryBlock

      protected BinaryMap.Block findEntryBlock(Binary binKey)
      Find the Entry block with the specified key.
      Parameters:
      binKey - the Binary key object
      Returns:
      a matching Entry block or null if that key is not in the map

    • toArray

      protected Object[] toArray(Object[] ao, Converter conv)
      Returns an array with a runtime type is that of the specified array and that contains data from all of the entries in this Map. See the documentation for toArray for the key set, entry set and values collection of the map.
      Parameters:
      ao - the array into which the data from the map entires are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose
      conv - an object that converts a Block object into either a key, entry or value, depending on the collection which is delegating to this method
      Returns:
      an array containing the entry data (key, entry or value)
      Throws:
      ArrayStoreException - if the runtime type of the specified array is not a supertype of the runtime type required to hold the keys, entries or values

    • validateKey

      protected RuntimeException validateKey(Object key, RuntimeException e)
      If the passed key is not Binary, then throw an exception to specify that the key is not Binary, otherwise throw the original exception.
      Parameters:
      key - the object that should be of type Binary
      e - the original RuntimeException
      Throws:
      RuntimeException - this method always throws some form of RuntimeException

    • validateEntry

      protected RuntimeException validateEntry(Object key, Object value, RuntimeException e)
      If the passed key and/or value is not a Binary object, then throw an exception to specify that the key is not Binary, otherwise throw the original exception.
      Parameters:
      key - the key object that should be of type Binary
      value - the value object that should be of type Binary
      e - the original RuntimeException
      Throws:
      RuntimeException - this method always throws some form of RuntimeException

    • reportOutOfMemory

      protected RuntimeException reportOutOfMemory(int cbRequired)
      Report on an insufficient memory problem.
      Parameters:
      cbRequired - the amount of space required
      Throws:
      RuntimeException - this method always throws some form of RuntimeException

    • instantiateEntrySet

      protected BinaryMap.EntrySet instantiateEntrySet()
      Factory pattern.
      Returns:
      a new instance of the EntrySet class (or a subclass thereof)

    • instantiateKeySet

      protected BinaryMap.KeySet instantiateKeySet()
      Factory pattern.
      Returns:
      a new instance of the KeySet class (or subclass thereof)

    • instantiateValuesCollection

      protected BinaryMap.ValuesCollection instantiateValuesCollection()
      Factory pattern.
      Returns:
      a new instance of the ValuesCollection class (or subclass thereof)

    • instantiateEntry

      protected BinaryMap.Entry instantiateEntry(Binary binKey, Binary binValue)
      Factory pattern: Instantiate an Entry object.
      Parameters:
      binKey - a Binary object for the key
      binValue - a Binary object for the value
      Returns:
      a new instance of the Entry class (or a subclass thereof)

    • getBufferManager

      public ByteBufferManager getBufferManager()
      Obtain the ByteBufferManager that provides the ByteBuffer objects.
      Returns:
      the ByteBufferManager object or null if there is none

    • setBufferManager

      protected void setBufferManager(ByteBufferManager bufmgr)
      Specify the ByteBufferManager for this map.
      Parameters:
      bufmgr - the ByteBufferManager object (or null)

    • checkBufferGrow

      protected void checkBufferGrow(int cbAdditional)
      If there is a buffer manager, check if the current buffer should be grown.
      Parameters:
      cbAdditional - the number of bytes pending to be allocated in addition to the bytes currently used

    • checkBufferShrink

      protected void checkBufferShrink()
      If there is a buffer manager, check if the current buffer should be shrunk.

    • getBuffer

      protected ByteBuffer getBuffer()
      Obtain the ByteBuffer that the BinaryMap is backed by.
      Returns:
      the ByteBuffer object (never null)

    • setBuffer

      protected void setBuffer(ByteBuffer buffer)
      Specify the ByteBuffer that the BinaryMap will be backed by.
      Parameters:
      buffer - the new ByteBuffer object

    • getCapacity

      protected int getCapacity()
      Determine the capacity of the map in bytes.
      Returns:
      the number of bytes that the buffer can hold

    • getFreeCapacity

      protected int getFreeCapacity()
      Determine the free capacity of the map in bytes.
      Returns:
      the number of bytes in the buffer that are free

    • getUsedCapacity

      protected int getUsedCapacity()
      Determine the number of types in the buffer that are in use by Entry blocks.
      Returns:
      the number of bytes in the buffer that are used

    • getLastBlockOffset

      protected int getLastBlockOffset()
      Get the offset of the last block in the buffer.
      Returns:
      the offset of the last block in the buffer

    • setLastBlockOffset

      protected void setLastBlockOffset(int ofBlock)
      Set the offset of the last block in the buffer.
      Parameters:
      ofBlock - the offset of the last block in the buffer

    • isStrict

      protected boolean isStrict()
      Determine if the buffer should be initialized and if blocks should be cleared when not in use.
      Returns:
      true if freed parts of the buffer should be initialized

    • setStrict

      protected void setStrict(boolean fStrict)
      Specify if the buffer should be initialized and if blocks should be cleared when not in use.
      Parameters:
      fStrict - pass true to always initialize unused portions of the buffer (which is slower but hides unused data)

    • clearBuffer

      protected void clearBuffer()
      Create one big free block in the buffer.

    • getBufferInput

      protected DataInputStream getBufferInput()
      Get the DataInputStream that maps to the underlying ByteBuffer.
      Returns:
      the DataInputStream that reads from the underlying ByteBuffer

    • getBufferOutput

      protected DataOutputStream getBufferOutput()
      Get the DataOutputStream that maps to the underlying ByteBuffer.
      Returns:
      the DataOutputStream that writes to the underlying ByteBuffer

    • wipe

      protected void wipe(int of, int cb)
      Wipe a portion of the buffer.
      Parameters:
      of - the offset into the buffer to wipe at
      cb - the number of bytes to wipe

    • check

      public void check(String sDesc)
      Debugging support: Validate the buffer's data structures, the hash buckets, free lists, etc.
      Parameters:
      sDesc - a description of what is going on when this is called

    • main

      public static void main(String[] asArg)
      Debugging support: Command line test.
      Parameters:
      asArg - command line arguments

    • dump

      public void dump()
      Debugging support: Dump the inner structures of the BinaryMap to stdout.

    • formatIndex

      protected static String formatIndex(int n)
      Format an index to a String.
      Parameters:
      n - the index that (may be NIL)
      Returns:
      a decimal String (or "nil") containing the index in a readable form

    • formatOffset

      protected static String formatOffset(int of)
      Format an offset to a String.
      Parameters:
      of - the offset that (may be NIL)
      Returns:
      a hex String (or "nil") containing the offset in a readable form

    • formatOffsetArray

      protected static String formatOffsetArray(int[] an)
      Format an array of offsets to be readable in a dump.
      Parameters:
      an - the array of offsets
      Returns:
      a String containing the offsets in a readable fashion

    • bin

      protected static Binary bin(String s)
      Internal debugging support: Turn a String into a Binary.
      Parameters:
      s - a String (not null)
      Returns:
      a Binary containing the String's value (kind of like ASCII)

    • str

      protected static String str(Object bin)
      Internal debugging support: Turn a Binary into a String.
      Parameters:
      bin - a Binary object or null
      Returns:
      a String with the Binary's contents unicode-extended or "<null>" if the passed Binary is null

    • initializeFreeLists

      protected void initializeFreeLists()
      Create an array of references to lists of free blocks indexed by size code.

    • clearFreeLists

      protected void clearFreeLists()
      Clear out all references in the array of free lists.

    • getFreeListCount

      protected int getFreeListCount()
      Determine the number of free lists (ie the number of size codes).
      Returns:
      the number of free lists

    • getFreeBlockOffset

      protected int getFreeBlockOffset(int nCode)
      Get the first free block in the linked list of free blocks that have a certain size code.
      Parameters:
      nCode - the free block size code
      Returns:
      the offset of the first free block of that size code or NIL

    • setFreeBlockOffset

      protected void setFreeBlockOffset(int nCode, int ofBlock)
      Set the head of the free block linked list for a certain size code.
      Parameters:
      nCode - the free block size code
      ofBlock - the offset of the first free block of that size code or NIL

    • initializeBuckets

      protected void initializeBuckets()
      Create an initial array of hash buckets.

    • getBucketLevel

      protected int getBucketLevel()
      Determine the hash bucket level. Each level is associated with a specific pre-selected modulo.
      Returns:
      the current hash bucket level

    • setBucketLevel

      protected void setBucketLevel(int nLevel)
      Configure the hash bucket level. Each level is associated with a specific pre-selected modulo. This mutator also sets the Modulo, GrowthCount and ShrinkageCount properties.
      Parameters:
      nLevel - the new hash bucket level

    • getBucketCount

      protected int getBucketCount()
      Determine the number of hash buckets. This is not necessarily the modulo.
      Returns:
      the number of hash buckets

    • setBucketCount

      protected void setBucketCount(int cBuckets)
      Configure the number of hash buckets. This does not change any offset values that are stored in the hash buckets; any additional buckets are initialized to NIL.
      Parameters:
      cBuckets - the new number of hash buckets

    • getBucketOffset

      protected int getBucketOffset(int nBucket)
      Get the first Entry block in the linked list of Entry blocks that fall into a certain hash bucket.
      Parameters:
      nBucket - the bucket number
      Returns:
      the offset of the first Entry block in that bucket, or NIL

    • setBucketOffset

      protected void setBucketOffset(int nBucket, int ofBlock)
      Set the head of the hash bucket linked list for a certain bucket.
      Parameters:
      nBucket - the bucket number
      ofBlock - the offset of the first Entry block in that bucket, or NIL

    • getMaxLoadFactor

      protected double getMaxLoadFactor()
      Determine the load factor for the map. This is a value typically greater than zero and less than one, although technically it can be greater than one. This value, multiplied by the current modulo, provides the number of entries that will force growth of the map's modulo.
      Returns:
      the load factor (aka the growth threshold)

    • setMaxLoadFactor

      protected void setMaxLoadFactor(double dflPercent)
      Set the load factor.
      Parameters:
      dflPercent - the new load factor

    • getMinLoadFactor

      protected double getMinLoadFactor()
      Determine the "unload factor" for the map. This is a value typically greater than zero and less than one, although technically it can be greater than one. In any case, it must be smaller than the growth threshold (load factor). This value, multiplied by the next smaller modulo than the current modulo (i.e. the next lower bucket level), provides the number of entries that will force shrinkage of the map's modulo.
      Returns:
      the "unload factor" (aka the shrinkage threshold)

    • setMinLoadFactor

      protected void setMinLoadFactor(double dflPercent)
      Set the "unload factor".
      Parameters:
      dflPercent - the new "unload factor"

    • getGrowthCount

      protected int getGrowthCount()
      Determine the level at which the modulo will increase.
      Returns:
      the number of entries at which the modulo will grow

    • setGrowthCount

      protected void setGrowthCount(int cEntries)
      Set the level at which the modulo will increase.
      Parameters:
      cEntries - the number of entries at which the modulo will grow

    • getShrinkageCount

      protected int getShrinkageCount()
      Determine the level at which the modulo will decrease.
      Returns:
      the number of entries at which the modulo will shrink

    • setShrinkageCount

      protected void setShrinkageCount(int cEntries)
      Set the level at which the modulo will decrease.
      Parameters:
      cEntries - the number of entries at which the modulo will shrink

    • getModulo

      protected int getModulo()
      Determine the current modulo.
      Returns:
      the current modulo

    • setModulo

      protected void setModulo(int nModulo)
      Set the new modulo.
      Parameters:
      nModulo - the new modulo

    • getPreviousModulo

      protected int getPreviousModulo()
      Determine the previous modulo. If a hash bucket resize is still being processed, the previous modulo will be different from the current modulo.
      Returns:
      the previous modulo

    • setPreviousModulo

      protected void setPreviousModulo(int nModulo)
      Set the old modulo.
      Parameters:
      nModulo - the previous modulo

    • calculateBucket

      protected int calculateBucket(int nHash)
      Calculate the bucket for the specified hash code.
      Parameters:
      nHash - the hash code for the key
      Returns:
      the bucket index

    • calculatePreviousBucket

      protected int calculatePreviousBucket(int nHash)
      Calculate the old bucket for the specified hash code.
      Parameters:
      nHash - the hash code for the key
      Returns:
      the bucket index using the previous modulo

    • clearBucketOffsets

      protected void clearBucketOffsets()
      Clear out all references in the array of hash buckets.

    • clearBucketOffsets

      protected void clearBucketOffsets(int nBucket)
      Clear out all references in the array of hash buckets starting with the specified bucket. int nBucket the first bucket to clear

    • checkModulo

      protected void checkModulo()
      Determine if the modulo should be changed. This should only be checked when the map is growing to avoid problems with iterators when removing all entries (don't want the map to rehash then).

    • isRehashing

      protected boolean isRehashing()
      Determine if the map is incrementally rehashing.
      Returns:
      true if the map is incrementally rehashing

    • getNextRehashBucket

      protected int getNextRehashBucket()
      Determine the next bucket to rehash.
      Returns:
      the next bucket to rehash

    • setNextRehashBucket

      protected void setNextRehashBucket(int nBucket)
      Set the next bucket to rehash.
      Parameters:
      nBucket - the next bucket to rehash

    • rehashBegin

      protected void rehashBegin()
      Configure the incremental rehash.

    • rehash

      protected void rehash(int nBucket)
      Rehash the specified bucket such that, when done, it will only contain keys that hash to it with the current modulo. Blocks can be in the "wrong" bucket because they are still hashed by the previous modulo; this is the result of incremental rehashing of buckets that allows a modulo change in a huge BinaryMap to occur instantly with the actual associated processing (rehashing) occuring gradually as the map is further used.
      Parameters:
      nBucket - the bucket index to rehash

    • rehashNext

      protected void rehashNext()
      Rehash the next incremental rehash block.

    • rehashAll

      protected void rehashAll()
      Rehash all blocks such that no block will be linked into the wrong bucket. This is a no-op if a there is no re-hashing to do. Blocks can be in the "wrong" bucket because they are still hashed by the previous modulo; this is the result of incremental rehashing of buckets that allows a modulo change in a huge BinaryMap to occur instantly with the actual associated processing (rehashing) occuring gradually as the map is further used.

    • rehashComplete

      protected void rehashComplete()
      Complete the incremental rehash.

    • initBlock

      protected BinaryMap.Block initBlock(int of)
      Obtain a Block object for a new block that will be located at the specified offset in the ByteBuffer. The returned block is in an open state.
      Returns:
      the Block object for the new block located at the specified offset

    • openBlock

      protected BinaryMap.Block openBlock(int of)
      Obtain a Block object for the block located at the specified offset in the ByteBuffer. The returned block is in an open state.
      Returns:
      the Block object for the block located at the specified offset

    • allocateBlock

      protected BinaryMap.Block allocateBlock(int cb)
      Allocate a free Block object of at least a certain size. Note that the returned block is both open and unlinked.
      Parameters:
      cb - the required block size
      Returns:
      a Block object of the required size

    • isCompacting

      protected boolean isCompacting()
      Determine if the map is incrementally compacting.
      Returns:
      true if the map is incrementally compacting

    • getNextCompactBlock

      protected int getNextCompactBlock()
      Determine the next block to compact.
      Returns:
      the next block to compact

    • setNextCompactBlock

      protected void setNextCompactBlock(int ofBlock)
      Set the next block to compact.
      Parameters:
      ofBlock - the next block to compact

    • compactBegin

      protected void compactBegin()
      Configure the incremental compact.

    • compactUntil

      protected void compactUntil(int cbReqFree)
      Perform an an incremental compact at the specified block.
      Parameters:
      cbReqFree - the number of bytes required to be free

    • compactNext

      protected void compactNext()
      Perform an incremental compaction of the next block.

    • compactAll

      protected void compactAll()
      Full linear compaction of the buffer.

    • compactComplete

      protected void compactComplete()
      Complete the incremental compact.

    • grabBlock

      protected BinaryMap.Block grabBlock(int ofBlock)
      Grab a block object for the specified offset. This method returns an open block if one is open for that offset, or uses a recycled block if one is not already open for that offset.
      Parameters:
      ofBlock - the offset of the block to grab
      Returns:
      a block for the specified offset

    • adjustOpenBlockOffset

      protected void adjustOpenBlockOffset(int ofOld, int ofNew)
      When an open block changes position in the buffer, this method is invoked to adjust the cache of open blocks.
      Parameters:
      ofOld - the old offset of the block
      ofNew - the new offset of the block

    • recycleBlock

      protected void recycleBlock(BinaryMap.Block block)
      Release (recycle) the specified Block object. This method should not be called directly; instead, call block.close().
      Parameters:
      block - the Block object to release

    • buffercopy

      protected static void buffercopy(ByteBuffer buffer, int ofCopyFrom, int ofCopyTo, int cbCopy, byte[] abBuf)
      Copy from one part of the buffer to another. This method only supports copying from a latter part of the buffer to an earlier part of the buffer.
      Parameters:
      buffer - the ByteBuffer containing the data to copy
      ofCopyFrom - the source offset into the ByteBuffer
      ofCopyTo - the destination offset into the ByteBuffer
      cbCopy - the number of bytes to copy
      abBuf - a temporary byte array available for use

    • calculateSizeCode

      protected static int calculateSizeCode(int cbBlock)
      Determine which "free bucket" a block of a particular size would go into.
      Parameters:
      cbBlock - the size of the block
      Returns:
      the size code for a block of the specified size

    • instantiateBlock

      protected BinaryMap.Block instantiateBlock()
      Factory method: Create a Block object.
      Returns:
      a new instance of the Block class or subclass thereof