org.apache.ignite.internal.processors.cache.persistence.pagemem

## Class RobinHoodBackwardShiftHashMap

- java.lang.Object
- - org.apache.ignite.internal.processors.cache.persistence.pagemem.RobinHoodBackwardShiftHashMap

All Implemented Interfaces:
  LoadedPagesMap

    public class RobinHoodBackwardShiftHashMap
    extends Object
    implements LoadedPagesMap

Loaded pages mapping to relative pointer based on Robin Hood hashing: backward shift deletion algorithm.
Performance of initial Robin Hood hashing could be greatly improved with only a little change to the removal method.
Instead of replacing entries with 'Removed' fake entries on deletion, backward shift deletion variant for the Robin Hood hashing algorithm does shift backward all the entries following the entry to delete until either an empty bucket, or a bucket with a DIB of 0 (distance to initial bucket).
Every deletion will shift backwards entries and therefore decrease their respective DIBs by 1 (all their initial DIB values would be >= 1)
This implementation stores ideal bucket with entry value itself.

### Nested Class Summary

### Nested classes/interfaces inherited from interface org.apache.ignite.internal.processors.cache.persistence.pagemem.LoadedPagesMap

`LoadedPagesMap.KeyPredicate`

### Constructor Summary

Constructors
Constructor and Description
`RobinHoodBackwardShiftHashMap(long baseAddr, long size)` Creates map in preallocated unsafe memory segment.

### Method Summary

All Methods Static Methods Instance Methods Concrete Methods
`int` `capacity()`
`String` `dump()`
`void` `forEach(BiConsumer<FullPageId,Long> act)` Scans all the elements in this table.
`long` `get(int grpId, long pageId, int reqVer, long absent, long outdated)` Gets value associated with the given key.
`ReplaceCandidate` `getNearestAt(int idxStart)` Find nearest presented value from specified position to the right.
`void` `put(int grpId, long pageId, long val, int ver)` Associates the given key with the given value.
`long` `refresh(int grpId, long pageId, int ver)` Refresh outdated value.
`boolean` `remove(int grpId, long pageId)` Removes key-value association for the given key.
`GridLongList` `removeIf(int startIdxToClear, int endIdxToClear, LoadedPagesMap.KeyPredicate keyPred)` Removes entities matching provided predicate at specified mapping range.
`static long` `requiredMemory(long elementsCnt)`
`int` `size()`

### Methods inherited from class java.lang.Object

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

### Methods inherited from interface org.apache.ignite.internal.processors.cache.persistence.pagemem.LoadedPagesMap

`removeIf`

### Constructor Detail

#### RobinHoodBackwardShiftHashMap

    public RobinHoodBackwardShiftHashMap(long baseAddr,
                                         long size)

Creates map in preallocated unsafe memory segment.

Parameters:
  `baseAddr` - Base buffer address.
  `size` - Size available for map, number of buckets (cells) to store will be determined accordingly.

### Method Detail

#### requiredMemory

    public static long requiredMemory(long elementsCnt)

Parameters:
  `elementsCnt` - Maximum elements can be stored in map, its maximum size.
Returns:
  Estimated memory size required for this map to store the given number of elements.

#### get

    public long get(int grpId,
                    long pageId,
                    int reqVer,
                    long absent,
                    long outdated)

Gets value associated with the given key.

Specified by:
  `get` in interface `LoadedPagesMap`
Parameters:
  `grpId` - Cache Group ID. First part of the key.
  `pageId` - Page ID. Second part of the key.
  `reqVer` - Requested entry version, counter associated with value.
  `absent` - return if provided page is not presented in map.
  `outdated` - return if provided `reqVer` version is greater than value in map (was used for put).
Returns:
  A value associated with the given key.

#### put

    public void put(int grpId,
                    long pageId,
                    long val,
                    int ver)

Associates the given key with the given value.

Specified by:
  `put` in interface `LoadedPagesMap`
Parameters:
  `grpId` - Cache Group ID. First part of the key.
  `pageId` - Page ID. Second part of the key.
  `val` - Value to set.
  `ver` - Version/counter associated with value, can be used to check if value is outdated.

#### remove

    public boolean remove(int grpId,
                          long pageId)

Removes key-value association for the given key.

Specified by:
  `remove` in interface `LoadedPagesMap`
Parameters:
  `grpId` - First part of the key. Cache Group ID.
  `pageId` - Second part of the key. Page ID.
Returns:
  `True` if value was actually found and removed.

#### getNearestAt

    public ReplaceCandidate getNearestAt(int idxStart)

Find nearest presented value from specified position to the right.

Specified by:
  `getNearestAt` in interface `LoadedPagesMap`
Parameters:
  `idxStart` - Index to start searching from. Bounded with `LoadedPagesMap.capacity()`.
Returns:
  Closest value to the index and it's partition tag or `null` value that will be returned if no values present.

#### refresh

    public long refresh(int grpId,
                        long pageId,
                        int ver)

Refresh outdated value. Sets provided version to value associated with cache and page. Method should be called only for key present and only if version was outdated. Method may be called in case `LoadedPagesMap.get(int, long, int, long, long)` returned `outdated` return value.

Specified by:
  `refresh` in interface `LoadedPagesMap`
Parameters:
  `grpId` - First part of the key. Cache Group ID.
  `pageId` - Second part of the key. Page ID.
  `ver` - Partition tag.
Returns:
  A value associated with the given key.

#### removeIf

    public GridLongList removeIf(int startIdxToClear,
                                 int endIdxToClear,
                                 LoadedPagesMap.KeyPredicate keyPred)

Removes entities matching provided predicate at specified mapping range.

Specified by:
  `removeIf` in interface `LoadedPagesMap`
Parameters:
  `startIdxToClear` - Index to clear value at, inclusive. Bounded with `LoadedPagesMap.capacity()`.
  `endIdxToClear` - Index to clear value at, inclusive. Bounded with `LoadedPagesMap.capacity()`.
  `keyPred` - Test predicate for (cache group ID, page ID).
Returns:
  List with removed values, value is not added to list for empty cell or if key is not matching to predicate.

#### capacity

    public int capacity()

Specified by:
  `capacity` in interface `LoadedPagesMap`
Returns:
  Maximum number of entries in the map. This maximum can not be always reached.

#### dump

    public String dump()

Returns:
  printable dump with all buckets state.

#### size

    public final int size()

Specified by:
  `size` in interface `LoadedPagesMap`
Returns:
  Current number of entries in the map.

#### forEach

    public void forEach(BiConsumer<FullPageId,Long> act)

Scans all the elements in this table.

Specified by:
  `forEach` in interface `LoadedPagesMap`
Parameters:
  `act` - Visitor/action to be applied to each not empty cell.

${current.year} Copyright © Apache Software Foundation

Follow @ApacheIgnite

Ignite Database and Caching Platform | : ver. 2.12.0
Release Date | : January 10 2022