javolution.util.internal.map.FractalMapImpl Class Reference

Collaboration diagram for javolution.util.internal.map.FractalMapImpl:

Public Member Functions
	FractalMapImpl ()
	FractalMapImpl (int shift)
MapEntryImpl	addEntry (MapEntryImpl newEntry, Object key, int hash)
void	clear ()
MapEntryImpl	getEntry (Object key, int hash)
MapEntryImpl	removeEntry (Object key, int hash)

Static Package Attributes
static final int	EMPTINESS_LEVEL = 2
static final int	INITIAL_BLOCK_CAPACITY = 2 << EMPTINESS_LEVEL
static final int	SHIFT = 10

Private Member Functions
int	indexOfKey (Object key, int hash)
void	resize (int newCapacity)

Private Attributes
int	count
MapEntryImpl[]	entries = new MapEntryImpl[INITIAL_BLOCK_CAPACITY]
final int	shift

Detailed Description

A fractal-based map with rehash performed only on limited size maps. It is based on a fractal structure with self-similar patterns at any scale (maps holding submaps). At each depth only a part of the hashcode is used starting by the last bits.

Definition at line 18 of file FractalMapImpl.java.

Constructor & Destructor Documentation

FractalMapImpl() [1/2]

javolution.util.internal.map.FractalMapImpl.FractalMapImpl

(

)

Definition at line 28 of file FractalMapImpl.java.

                            {
        this.shift = 0;
    }

FractalMapImpl() [2/2]

javolution.util.internal.map.FractalMapImpl.FractalMapImpl

(

int

shift

)

Definition at line 32 of file FractalMapImpl.java.

                                     {
        this.shift = shift;
    }

Member Function Documentation

addEntry()

MapEntryImpl javolution.util.internal.map.FractalMapImpl.addEntry	(	MapEntryImpl	newEntry,
		Object	key,
		int	hash
	)

Adds the specified entry if not already present; returns either the specified entry or an existing entry for the specified key.

Definition at line 39 of file FractalMapImpl.java.

                                                                              {
        int i = indexOfKey(key, hash);
        MapEntryImpl entry = entries[i];
        if (entry != null) return entry; // Entry exists
        entries[i] = newEntry;
        newEntry.key = key;
        newEntry.hash = hash;
        // Check if we need to resize.
        if ((++count << EMPTINESS_LEVEL) > entries.length) {
            resize(entries.length << 1);
        }
        return newEntry;
    }

References javolution.util.internal.map.MapEntryImpl< K, V >.key.

Referenced by javolution.util.internal.map.FastMapImpl< K, V >.put(), and javolution.util.internal.map.FastMapImpl< K, V >.putIfAbsent().

Here is the caller graph for this function:

clear()

void javolution.util.internal.map.FractalMapImpl.clear

(

)

Definition at line 53 of file FractalMapImpl.java.

                        {
        entries = new MapEntryImpl[INITIAL_BLOCK_CAPACITY];
        count = 0;
    }

getEntry()

MapEntryImpl javolution.util.internal.map.FractalMapImpl.getEntry	(	Object	key,
		int	hash
	)

Returns null if no entry with specified key

Definition at line 59 of file FractalMapImpl.java.

                                                       {
        return entries[indexOfKey(key, hash)];
    }

Referenced by javolution.util.internal.map.FastMapImpl< K, V >.containsKey(), javolution.util.internal.map.FastMapImpl< K, V >.get(), javolution.util.internal.map.FastMapImpl< K, V >.remove(), and javolution.util.internal.map.FastMapImpl< K, V >.replace().

Here is the caller graph for this function:

indexOfKey()

int javolution.util.internal.map.FractalMapImpl.indexOfKey ( Object  key, int  hash  )

private

Returns the index of the specified key in the map (points to a null key if key not present).

Definition at line 91 of file FractalMapImpl.java.

                                                 {
        int mask = entries.length - 1;
        int i = (hash >> shift) & mask;
        while (true) {
            MapEntryImpl entry = entries[i];
            if (entry == null) return i;
            if ((entry.hash == hash) && key.equals(entry.key)) return i;
            i = (i + 1) & mask;
        }
    }

References javolution.util.internal.map.MapEntryImpl< K, V >.hash, and javolution.util.internal.map.MapEntryImpl< K, V >.key.

removeEntry()

MapEntryImpl javolution.util.internal.map.FractalMapImpl.removeEntry	(	Object	key,
		int	hash
	)

Returns the entry removed or null if none.

Definition at line 64 of file FractalMapImpl.java.

                                                          {
        int i = indexOfKey(key, hash);
        MapEntryImpl oldEntry = entries[i];
        if (oldEntry == null) return null; // Entry does not exist.
        entries[i] = null;
        // Since we have made a hole, adjacent keys might have to shift.
        for (;;) {
            // We use a step of 1 (improve caching through memory locality).
            i = (i + 1) & (entries.length - 1);
            MapEntryImpl entry = entries[i];
            if (entry == null) break; // Done.
            int correctIndex = indexOfKey(entry.key, entry.hash);
            if (correctIndex != i) { // Misplaced.
                entries[correctIndex] = entries[i];
                entries[i] = null;
            }
        }
        // Check if we need to resize.
        if (((--count << (EMPTINESS_LEVEL + 1)) <= entries.length)
                && (entries.length > INITIAL_BLOCK_CAPACITY)) {
            resize(entries.length >> 1);
        }
        return oldEntry;
    }

References javolution.util.internal.map.MapEntryImpl< K, V >.hash, and javolution.util.internal.map.MapEntryImpl< K, V >.key.

Referenced by javolution.util.internal.map.FastMapImpl< K, V >.iterator(), and javolution.util.internal.map.FastMapImpl< K, V >.remove().

Here is the caller graph for this function:

resize()

void javolution.util.internal.map.FractalMapImpl.resize ( int  newCapacity )

private

Definition at line 105 of file FractalMapImpl.java.

                                         {
        MapEntryImpl[] newEntries = new MapEntryImpl[newCapacity];
        int newMask = newEntries.length - 1;
        for (int i = 0, n = entries.length; i < n; i++) {
            MapEntryImpl entry = entries[i];
            if (entry == null) continue;
            int newIndex = entry.hash & newMask;
            while (newEntries[newIndex] != null) { // Find empty slot.
                newIndex = (newIndex + 1) & newMask;
            }
            newEntries[newIndex] = entry;
        }
        entries = newEntries;
    }

References javolution.util.internal.map.MapEntryImpl< K, V >.hash.

Member Data Documentation

count

int javolution.util.internal.map.FractalMapImpl.count

private

Definition at line 24 of file FractalMapImpl.java.

EMPTINESS_LEVEL

final int javolution.util.internal.map.FractalMapImpl.EMPTINESS_LEVEL = 2

staticpackage

Definition at line 20 of file FractalMapImpl.java.

entries

MapEntryImpl [] javolution.util.internal.map.FractalMapImpl.entries = new MapEntryImpl[INITIAL_BLOCK_CAPACITY]

private

Definition at line 25 of file FractalMapImpl.java.

INITIAL_BLOCK_CAPACITY

final int javolution.util.internal.map.FractalMapImpl.INITIAL_BLOCK_CAPACITY = 2 << EMPTINESS_LEVEL

staticpackage

Definition at line 21 of file FractalMapImpl.java.

SHIFT

final int javolution.util.internal.map.FractalMapImpl.SHIFT = 10

staticpackage

Definition at line 22 of file FractalMapImpl.java.

shift

final int javolution.util.internal.map.FractalMapImpl.shift

private

Definition at line 26 of file FractalMapImpl.java.

---

The documentation for this class was generated from the following file:

• FractalMapImpl.java