com.bigdata.htree

Class HTreeUtil

java.lang.Object

com.bigdata.htree.HTreeUtil

public class HTreeUtil
extends Object

Static utility methods and data for an HTree.

Version:

$Id$

Author:

Bryan Thompson

Constructor Summary

Constructors

Constructor and Description
HTreeUtil()

Method Summary

Methods

Modifier and Type	Method and Description
static int	getBuddyOffset(int hashBits, int globalDepth, int localDepth) Find the offset of the buddy hash table or buddy bucket in the child.
static int	getLocalDepth(int addressBits, int globalDepth, int npointers) Return the local depth of a child page having npointers to that page in the parent node.
static int	getSlotsOnPage(int globalDepth, int localDepth) Return the #of entries in the address map for a page having the given local depth.
static boolean	isPowerOf2(int v) Return true if the argument is a power of TWO (2).

Methods inherited from class java.lang.Object

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

Constructor Detail

HTreeUtil

public HTreeUtil()

Method Detail

isPowerOf2

public static boolean isPowerOf2(int v)

Return true if the argument is a power of TWO (2).

Parameters:

v - The argument.

Returns:

true if the argument is a power of TWO (2).

getSlotsOnPage

public static int getSlotsOnPage(int globalDepth,
                 int localDepth)

Return the #of entries in the address map for a page having the given local depth. This is 2^(globalHashBits - localHashBits). The following table shows the relationship between the global hash bits (gb), the local hash bits (lb) for a page, and the #of directory entries for that page (nentries).

 gb  lb   nentries
 1    0   2
 1    1   1
 2    0   4
 2    1   2
 2    2   1
 3    0   8
 3    1   4
 3    2   2
 3    3   1
 4    0   16
 4    1   8
 4    2   4
 4    3   2
 4    4   1
 

Parameters:

globalDepth - The global depth of the parent.

localDepth - The local depth of the child.

Returns:

The #of directory entries for that child page.

Throws:

IllegalArgumentException - if either argument is less than ZERO (0).

IllegalArgumentException - if localHashBits is greater than globalHashBits.

getLocalDepth

public static int getLocalDepth(int addressBits,
                int globalDepth,
                int npointers)

Return the local depth of a child page having npointers to that page in the parent node. This method is based on the relationship 2^(n-i) = npointers where n is the global depth of the parent and i is the local depth of the child. The value of i is the MSB of (npointers / (2^n)). That equation always evaluates to a power of two since npointers is a power of two. The MSB is the index of the highest (and only) ONE (1) bit in the result for that equation.

Parameters:

addressBits - The #of address bits for the hash tree. This is set when the tree is configured and is immutable. addressBits is not required for the computation, but is used to validate the other arguments.

globalDepth - The global depth of the parent node.

npointers - The #of pointers to that child in the parent node. All of those pointers will be within a single buddy hash table in the parent. The maximum value for npointers is 2^globalDepth for a given globalDepth. (The maximum value of globalDepth is the configured value of addressBits for the hash tree.)

Returns:

The local depth of that child node.

Throws:

IllegalArgumentException - if addressBits is LT ONE (1).

IllegalArgumentException - if globalDepth is LT ZERO (0).

IllegalArgumentException - if globalDepth is GT 2^addressBits.

IllegalArgumentException - if npointers is LT ONE (1).

IllegalArgumentException - if npointers is greater than 2^globalDepth.

IllegalArgumentException - if npointers is not a power of 2.

getBuddyOffset

public static int getBuddyOffset(int hashBits,
                 int globalDepth,
                 int localDepth)

Find the offset of the buddy hash table or buddy bucket in the child. Each page of the hash tree is logically an ordered array of "buddies" sharing the same physical page. When the page is a directory page, the buddies are buddy hash tables. When the page is a bucket page, the buddies are buddy hash buckets. The returned value is the offset required to index into the appropriate buddy hash table or buddy hash bucket in the child page.

Parameters:

hashBits - The relevant bits of the hash code used to lookup the child within the parent.

globalDepth - The global depth of the parent.

localDepth - The local depth of the child page within the parent.

Returns:

The offset of the start of the buddy hash table or buddy hash bucket within the child. This is an index into the slots of the child. There are m:=(2^addressBits)-1 slots in the child, so the returned index is in the half open range [0:m).

Throws:

IllegalArgumentException - if the globalDepth is negative.

IllegalArgumentException - if the localDepth is greater than the globalDepth.