BinaryMap (Coherence API)

Overview

Package

Class

Tree

Index

Help

Coherence^TM v3.3
Copyright^© 2000-2007 by Oracle Corporation

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

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
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
`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.

Field Summary
`protected static int[]`	`BUCKET_COUNTS` These are potential bucket counts.
`static 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 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 byte[]`	`FILL_BUFFER` Byte array used for wiping the buffer.
`protected static 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 int`	`MAX_OPEN_BLOCKS` Maximum number of simultaneously open blocks to support.
`protected static int`	`MAX_SIZE_CODES` Number of size codes for free blocks.
`protected static boolean`	`MODE_DEBUG` True to enable debug mode.
`protected static int`	`NIL` Offset reserved for the "does-not-exist" block.
`protected static int`	`SIZE_COPY_BUFFER` Copy buffer size.

Constructor Summary
`protected`	`BinaryMap()` Construct a BinaryMap.
	`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.
	`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.

Method Summary
`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`

Field Detail

MODE_DEBUG

protected static final boolean MODE_DEBUG

True to enable debug mode.

See Also:: Constant Field Values

FILL_BYTE

protected static final byte FILL_BYTE

Byte used as a fill byte.

See Also:: Constant Field Values

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:: Constant Field Values

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:: Constant Field Values

NIL

protected static final int NIL

Offset reserved for the "does-not-exist" block.

See Also:: Constant Field Values

MAX_OPEN_BLOCKS

protected static final int MAX_OPEN_BLOCKS

Maximum number of simultaneously open blocks to support.

See Also:: Constant Field Values

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:: Constant Field Values

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:: Constant Field Values

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 Detail

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 Detail

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 "" 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

Overview

Package

Class

Tree

Index

Help

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

com.tangosol.io.nio Class BinaryMap

MODE_DEBUG

FILL_BYTE

FILL_BUFFER

MAX_SIZE_CODES

BUCKET_COUNTS

SIZE_COPY_BUFFER

NIL

MAX_OPEN_BLOCKS

DEFAULT_MAXLOADFACTOR

DEFAULT_MINLOADFACTOR

m_set

m_setKeys

m_colValues

BinaryMap

BinaryMap

BinaryMap

BinaryMap

BinaryMap

size

isEmpty

containsKey

get

put

remove

clear

entrySet

keySet

values

getEntryBlockCount

findEntryBlock

toArray

validateKey

validateEntry

reportOutOfMemory

instantiateEntrySet

instantiateKeySet

instantiateValuesCollection

instantiateEntry

getBufferManager

setBufferManager

checkBufferGrow

checkBufferShrink

getBuffer

setBuffer

getCapacity

getFreeCapacity

getUsedCapacity

getLastBlockOffset

setLastBlockOffset

isStrict

setStrict

clearBuffer

getBufferInput

getBufferOutput

wipe

check

main

dump

formatIndex

formatOffset

formatOffsetArray

bin

str

initializeFreeLists

clearFreeLists

getFreeListCount

getFreeBlockOffset

setFreeBlockOffset

initializeBuckets

getBucketLevel

setBucketLevel

getBucketCount

setBucketCount

getBucketOffset

setBucketOffset

getMaxLoadFactor

setMaxLoadFactor

getMinLoadFactor

setMinLoadFactor

com.tangosol.io.nio
Class BinaryMap