org.apache.ignite.internal.processors.cache.persistence.tree.io

## Class AbstractDataPageIO<T extends Storable>

- java.lang.Object
- - org.apache.ignite.internal.processors.cache.persistence.tree.io.PageIO
  - - org.apache.ignite.internal.processors.cache.persistence.tree.io.AbstractDataPageIO<T>

All Implemented Interfaces:
  CompactablePageIO

Direct Known Subclasses:
  DataPageIO, SimpleDataPageIO

    public abstract class AbstractDataPageIO<T extends Storable>
    extends PageIO
    implements CompactablePageIO

Data pages IO. Rows in a data page are organized into two arrays growing toward each other: items table and row data.

Items table contains direct or indirect items which locate a row within the page. Items table is stored at the beginning of a page. Each item has an item ID which serves as an external item reference (see `PageIdUtils.link(long, int)`) and can be either direct or indirect. The size of any item in the items table is 2 bytes. ID of a direct item is always the same as its index in items table so it is not stored in the item itself. ID of an indirect item may differ from its index (see example below) so it is stored it the item along with ID (index) of direct item.

Direct and indirect items are always placed in the items table in such a way that direct items are stored first, and indirect items are always stored after direct items. A data page explicitly stores both direct and indirect items count (see `getDirectCount(long)` and `getIndirectCount(long)`), so that the item type can be easily determined: items with indexes `[0, directCnt)` are always direct and items with indexes `[directCnt, directCnt + indirectCnt)` are always indirect. Having both direct and indirect items in a page allows page defragmentation without breaking external links. Total number of rows stored in a page is equal to the number of direct items.

The row data is stored at the end of the page; newer rows are stored closer to the end of the items table.

### Direct Items

Direct items refer a stored row directly by offset in the page:

         +-----------------------------------------------------------------------------+
         | Direct Items             ..... (rows data)                                  |
         | (4000), (3800), (3600)   ..... row_2_cccc  row_1_bbbb   row_0_aaaa          |
         |  |       |       |_____________^           ^            ^                   |
         |  |       |_________________________________|            |                   |
         |  |______________________________________________________|                   |
         | directCnt: 3                                                                |
         | indirectCnt: 0                                                              |
         +-----------------------------------------------------------------------------+

Direct item ID always matches it's index in the items table. The value of a direct item in the table is an offset of the row data within the page.

### Indirect Items

An indirect item explicitly stores the indirect item ID (1 byte) and the index of the direct item it refers to (1 byte). The referred direct item (referrent) stores the actual offset of the row in the data page:

         +-----------------------------------------------------------------------------+
         |  Direct Items .. Indirect items .... (rows data)                            |
         |   ____________________                                                      |
         |  ⌄                    |                                                     |
         | (3600), (3800), (3 -> 0)        ....   row_2_cccc  row_1_bbbb               |
         |  |       |_____________________________^___________^                        |
         |  |_____________________________________|                                    |
         | directCnt: 2                                                                |
         | indirectCount: 1                                                            |
         +-----------------------------------------------------------------------------+

An indirect item can only be created as a result of row deletion. Note that indirect item ID does not necessarily match the item index in the items table, however, indirect item IDs are always stored in sorted order by construction. In the picture above, the page contains two rows which are referred by two items:

- `1` is a direct item which is stored at index 1 in the items table
- `3` is an indirect item which is stored at index 2 in the items table and refers to the direct item `0`

## Items insertion and deletion

When rows are added to an empty page or a page with only direct items, the items table grows naturally:

         +---------------------------------------------------------------+
         | Table index | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 |
         +---------------------------------------------------------------+
         | Item        |  a |  b |  c |  d |  e |  f |  g |  h |  i |  j |
         +---------------------------------------------------------------+

When an item is removed, the items table is modified in such a way, that:

- Item of deleted row is modified to point to the row of the last direct item
- The last direct item is converted to an indirect item, pointing to the deleted item

         remove(itemId=07)
         +-----------------------------------------------------------------------+
         | Table index | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 |         09 |
         +-----------------------------------------------------------------------+
         | Item        |  a |  b |  c |  d |  e |  f |  g |  j |  i | (09 -> 07) |
         +-----------------------------------------------------------------------+

          remove(itemId=02)
         +--------------------------------------------------------------------------------+
         | Table index | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 |          08 |         09 |
         +--------------------------------------------------------------------------------+
         | Item        |  a |  b |  i |  d |  e |  f |  g |  j |  (08 -> 02) | (09 -> 07) |
         +--------------------------------------------------------------------------------+

If the last direct item is already referred by an indirect item, that indirect item is updated and all indirect items are shifted to the left by 1 effectively dropping last direct item:

          remove(itemId=00)
         +--------------------------------------------------------------------------------+
         | Table index | 00 | 01 | 02 | 03 | 04 | 05 | 06 |          07 |         08 | 09 |
         +--------------------------------------------------------------------------------+
         | Item        |  j |  b |  i |  d |  e |  f |  g |  (08 -> 02) | (09 -> 00) |    |
         +--------------------------------------------------------------------------------+

When adding a row to a page with indirect items, the item is added to the end of direct items in the table and indirect items are shifted to the right:

          add(k)
         +-------------------------------------------------------------------------------+
         | Table index | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 |         08 |         09 |
         +-------------------------------------------------------------------------------+
         | Item        |  j |  b |  i |  d |  e |  f |  g |  k | (08 -> 02) | (09 -> 00) |
         +-------------------------------------------------------------------------------+

If during an insert a newly added direct item ID matches with an existing indirect item ID, the corresponding indirect item is converted to a direct item, and the row being inserted is represented by a direct item with the referrent ID:

          add(l)
         +-----------------------------------------------------------------------+
         | Table index | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 |         09 |
         +-----------------------------------------------------------------------+
         | Item        |  j |  b |  l |  d |  e |  f |  g |  k |  i | (09 -> 00) |
         +-----------------------------------------------------------------------+

### Nested Class Summary

Nested Classes
`static interface` `AbstractDataPageIO.CC<T>` Defines closure interface for applying computations to data page items.

### Field Summary

Fields
`static int` `ITEMS_OFF`
`static int` `MIN_DATA_PAGE_OVERHEAD`

### Fields inherited from class org.apache.ignite.internal.processors.cache.persistence.tree.io.PageIO

`COMMON_HEADER_END, CRC_OFF, MAX_PAYLOAD_SIZE, PAGE_ID_OFF, ROTATED_ID_PART_OFF, T_BPLUS_META, T_CACHE_ID_AWARE_DATA_REF_INNER, T_CACHE_ID_AWARE_DATA_REF_LEAF, T_CACHE_ID_AWARE_PENDING_REF_INNER, T_CACHE_ID_AWARE_PENDING_REF_LEAF, T_CACHE_ID_DATA_REF_MVCC_INNER, T_CACHE_ID_DATA_REF_MVCC_LEAF, T_DATA, T_DATA_METASTORAGE, T_DATA_PART, T_DATA_REF_INNER, T_DATA_REF_LEAF, T_DATA_REF_METASTORAGE_INNER, T_DATA_REF_METASTORAGE_LEAF, T_DATA_REF_MVCC_INNER, T_DATA_REF_MVCC_LEAF, T_DEFRAG_LINK_MAPPING_INNER, T_DEFRAG_LINK_MAPPING_LEAF, T_H2_EX_REF_INNER_END, T_H2_EX_REF_INNER_START, T_H2_EX_REF_LEAF_END, T_H2_EX_REF_LEAF_START, T_H2_EX_REF_MVCC_INNER_END, T_H2_EX_REF_MVCC_INNER_START, T_H2_EX_REF_MVCC_LEAF_END, T_H2_EX_REF_MVCC_LEAF_START, T_H2_MVCC_REF_INNER, T_H2_MVCC_REF_LEAF, T_H2_REF_INNER, T_H2_REF_LEAF, T_MARKER_PAGE, T_META, T_METASTORE_INNER, T_METASTORE_LEAF, T_PAGE_LIST_META, T_PAGE_LIST_NODE, T_PAGE_UPDATE_TRACKING, T_PART_CNTRS, T_PART_META, T_PENDING_REF_INNER, T_PENDING_REF_LEAF, T_TX_LOG_INNER, T_TX_LOG_LEAF, TYPE_OFF, VER_OFF`

### Constructor Summary

Constructors
`protected` `AbstractDataPageIO(int type, int ver)`

### Method Summary

All Methods Instance Methods Abstract Methods Concrete Methods
`int` `addRow(long pageAddr, byte[] payload, int pageSize)` Adds row to this data page and sets respective link to the given row object.
`void` `addRow(long pageId, long pageAddr, T row, int rowSize, int pageSize)` Adds row to this data page and sets respective link to the given row object.
`void` `addRowFragment(long pageId, long pageAddr, byte[] payload, long lastLink, int pageSize)` Adds this payload as a fragment to this data page.
`int` `addRowFragment(PageMemory pageMem, long pageId, long pageAddr, T row, int written, int rowSize, int pageSize)` Adds maximum possible fragment of the given row to this data page and sets respective link to the row.
`protected boolean` `checkIndex(int idx)`
`void` `compactPage(ByteBuffer page, ByteBuffer out, int pageSize)` Compacts page contents to the output buffer.
`<U> List<U>` `forAllItems(long pageAddr, AbstractDataPageIO.CC<U> c)`
`protected int` `getDataOffset(long pageAddr, int itemId, int pageSize)`
`int` `getDirectCount(long pageAddr)`
`long` `getFreeListPageId(long pageAddr)`
`int` `getFreeSpace(long pageAddr)` Free space refers to a "max row size (without any data page specific overhead) which is guaranteed to fit into this data page".
`int` `getPayloadOffset(long pageAddr, int itemId, int pageSize, int reqLen)`
`int` `getRealFreeSpace(long pageAddr)` Equivalent for `actualFreeSpace(long, int)` but reads saved value.
`int` `getRowsCount(long pageAddr)`
`void` `initNewPage(long pageAddr, long pageId, int pageSize, PageMetrics metrics)`
`boolean` `isEmpty(long pageAddr)`
`protected boolean` `isFragmented(long pageAddr, int dataOff)`
`protected void` `printPageLayout(long pageAddr, int pageSize, GridStringBuilder b)`
`DataPagePayload` `readPayload(long pageAddr, int itemId, int pageSize)` Sets position to start of actual fragment data and limit to it's end.
`long` `removeRow(long pageAddr, int itemId, int pageSize)`
`void` `restorePage(ByteBuffer page, int pageSize)` Restores the original page in place.
`void` `setFreeListPageId(long pageAddr, long freeListPageId)`
`boolean` `updateRow(long pageAddr, int itemId, int pageSize, @Nullable byte[] payload, T row, int rowSize)`
`protected abstract void` `writeFragmentData(T row, ByteBuffer buf, int rowOff, int payloadSize)` Write row data fragment.
`protected void` `writeRowData(long pageAddr, int dataOff, byte[] payload)`
`protected abstract void` `writeRowData(long pageAddr, int dataOff, int payloadSize, T row, boolean newRow)`

### Methods inherited from class org.apache.ignite.internal.processors.cache.persistence.tree.io.PageIO

`assertPageType, assertPageType, copyPage, deriveIndexPageType, getBPlusIO, getBPlusIO, getCompactedSize, getCompactedSize, getCompressedSize, getCompressedSize, getCompressionType, getCompressionType, getCrc, getCrc, getInnerVersions, getLeafVersions, getPageId, getPageId, getPageIO, getPageIO, getPageIO, getRotatedIdPart, getType, getType, getType, getVersion, getVersion, getVersion, isDataPageType, isIndexPage, printPage, printPage, registerH2, registerH2ExtraInner, registerH2ExtraLeaf, registerTest, registerTest, setCompactedSize, setCompressedSize, setCompressionType, setCrc, setCrc, setPageId, setRotatedIdPart, setType, setVersion, toString`

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

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

### Field Detail

#### ITEMS_OFF

    public static final int ITEMS_OFF

See Also:
  Constant Field Values

#### MIN_DATA_PAGE_OVERHEAD

    public static final int MIN_DATA_PAGE_OVERHEAD

See Also:
  Constant Field Values

### Constructor Detail

#### AbstractDataPageIO

    protected AbstractDataPageIO(int type,
                                 int ver)

Parameters:
  `type` - Page type.
  `ver` - Page format version.

### Method Detail

#### initNewPage

    public void initNewPage(long pageAddr,
                            long pageId,
                            int pageSize,
                            PageMetrics metrics)

Overrides:
  `initNewPage` in class `PageIO`
Parameters:
  `pageAddr` - Page address.
  `pageId` - Page ID.
  `pageSize` - Page size.
  `metrics` - Page metrics for tracking page allocation. Can be `null` if no tracking is required.
See Also:
  `EncryptionSpi.encryptedSize(int)`

#### setFreeListPageId

    public void setFreeListPageId(long pageAddr,
                                  long freeListPageId)

Parameters:
  `pageAddr` - Page address.
  `freeListPageId` - Free list page ID.

#### getFreeListPageId

    public long getFreeListPageId(long pageAddr)

Parameters:
  `pageAddr` - Page address.
Returns:
  Free list page ID.

#### getFreeSpace

    public int getFreeSpace(long pageAddr)

Free space refers to a "max row size (without any data page specific overhead) which is guaranteed to fit into this data page".

Parameters:
  `pageAddr` - Page address.
Returns:
  Free space.

#### isEmpty

    public boolean isEmpty(long pageAddr)

Parameters:
  `pageAddr` - Page address.
Returns:
  `true` If there is no useful data in this page.

#### getRealFreeSpace

    public int getRealFreeSpace(long pageAddr)

Equivalent for `actualFreeSpace(long, int)` but reads saved value.

Parameters:
  `pageAddr` - Page address.
Returns:
  Free space.

#### getDirectCount

    public int getDirectCount(long pageAddr)

Parameters:
  `pageAddr` - Page address.
Returns:
  Direct count.

#### getRowsCount

    public int getRowsCount(long pageAddr)

Parameters:
  `pageAddr` - Page address.
Returns:
  Rows number in the given data page.

#### forAllItems

    public <U> List<U> forAllItems(long pageAddr,
                                   AbstractDataPageIO.CC<U> c)
                            throws IgniteCheckedException

Type Parameters:
  `U` - Closure return type.
Parameters:
  `pageAddr` - Page address.
  `c` - Closure.
Returns:
  Collection of closure results for all items in page.
Throws:
  `IgniteCheckedException` - In case of error in closure body.

#### checkIndex

    protected boolean checkIndex(int idx)

Parameters:
  `idx` - Index.
Returns:
  `true` If the index is valid.

#### printPageLayout

    protected void printPageLayout(long pageAddr,
                                   int pageSize,
                                   GridStringBuilder b)

Parameters:
  `pageAddr` - Page address.
  `pageSize` - Page size.
  `b` - B.

#### getDataOffset

    protected int getDataOffset(long pageAddr,
                                int itemId,
                                int pageSize)

Parameters:
  `pageAddr` - Page address.
  `itemId` - Fixed item ID (the index used for referencing an entry from the outside).
  `pageSize` - Page size.
Returns:
  Data entry offset in bytes.

#### isFragmented

    protected boolean isFragmented(long pageAddr,
                                   int dataOff)

Parameters:
  `pageAddr` - Page address.
  `dataOff` - Data offset.
Returns:
  `true` If the data row is fragmented across multiple pages.

#### readPayload

    public DataPagePayload readPayload(long pageAddr,
                                       int itemId,
                                       int pageSize)

Sets position to start of actual fragment data and limit to it's end.

Parameters:
  `pageAddr` - Page address.
  `itemId` - Item to position on.
  `pageSize` - Page size.
Returns:
  `DataPagePayload` object.

#### getPayloadOffset

    public int getPayloadOffset(long pageAddr,
                                int itemId,
                                int pageSize,
                                int reqLen)

Parameters:
  `pageAddr` - Page address.
  `itemId` - Item to position on.
  `pageSize` - Page size.
  `reqLen` - Required payload length.
Returns:
  Offset to start of actual fragment data.

#### updateRow

    public boolean updateRow(long pageAddr,
                             int itemId,
                             int pageSize,
                             @Nullable
                             @Nullable byte[] payload,
                             @Nullable
                             T row,
                             int rowSize)
                      throws IgniteCheckedException

Parameters:
  `pageAddr` - Page address.
  `itemId` - Item ID.
  `pageSize` - Page size.
  `payload` - Row data.
  `row` - Row.
  `rowSize` - Row size.
Returns:
  `True` if entry is not fragmented.
Throws:
  `IgniteCheckedException` - If failed.

#### removeRow

    public long removeRow(long pageAddr,
                          int itemId,
                          int pageSize)
                   throws IgniteCheckedException

Parameters:
  `pageAddr` - Page address.
  `itemId` - Fixed item ID (the index used for referencing an entry from the outside).
  `pageSize` - Page size.
Returns:
  Next link for fragmented entries or `0` if none.
Throws:
  `IgniteCheckedException` - If failed.

#### addRow

    public void addRow(long pageId,
                       long pageAddr,
                       T row,
                       int rowSize,
                       int pageSize)
                throws IgniteCheckedException

Adds row to this data page and sets respective link to the given row object.

Parameters:
  `pageAddr` - Page address.
  `row` - Data row.
  `rowSize` - Row size.
  `pageSize` - Page size.
Throws:
  `IgniteCheckedException` - If failed.

#### addRow

    public int addRow(long pageAddr,
                      byte[] payload,
                      int pageSize)
               throws IgniteCheckedException

Adds row to this data page and sets respective link to the given row object.

Parameters:
  `pageAddr` - Page address.
  `payload` - Payload.
  `pageSize` - Page size.
Returns:
  Item ID.
Throws:
  `IgniteCheckedException` - If failed.

#### addRowFragment

    public int addRowFragment(PageMemory pageMem,
                              long pageId,
                              long pageAddr,
                              T row,
                              int written,
                              int rowSize,
                              int pageSize)
                       throws IgniteCheckedException

Adds maximum possible fragment of the given row to this data page and sets respective link to the row.

Parameters:
  `pageMem` - Page memory.
  `pageId` - Page ID to use to construct a link.
  `pageAddr` - Page address.
  `row` - Data row.
  `written` - Number of bytes of row size that was already written.
  `rowSize` - Row size.
  `pageSize` - Page size.
Returns:
  Written payload size.
Throws:
  `IgniteCheckedException` - If failed.

#### addRowFragment

    public void addRowFragment(long pageId,
                               long pageAddr,
                               byte[] payload,
                               long lastLink,
                               int pageSize)
                        throws IgniteCheckedException

Adds this payload as a fragment to this data page.

Parameters:
  `pageId` - Page ID to use to construct a link.
  `pageAddr` - Page address.
  `payload` - Payload bytes.
  `lastLink` - Link to the previous written fragment (link to the tail).
  `pageSize` - Page size.
Throws:
  `IgniteCheckedException` - If failed.

#### writeFragmentData

    protected abstract void writeFragmentData(T row,
                                              ByteBuffer buf,
                                              int rowOff,
                                              int payloadSize)
                                       throws IgniteCheckedException

Write row data fragment.

Parameters:
  `row` - Row.
  `buf` - Byte buffer.
  `rowOff` - Offset in row data bytes.
  `payloadSize` - Data length that should be written in a fragment.
Throws:
  `IgniteCheckedException` - If failed.

#### compactPage

    public void compactPage(ByteBuffer page,
                            ByteBuffer out,
                            int pageSize)

Compacts page contents to the output buffer. Implementation must not change contents, position and limit of the original page buffer.

Specified by:
  `compactPage` in interface `CompactablePageIO`
Parameters:
  `page` - Page buffer.
  `out` - Output buffer.
  `pageSize` - Page size.

#### restorePage

    public void restorePage(ByteBuffer page,
                            int pageSize)

Restores the original page in place.

Specified by:
  `restorePage` in interface `CompactablePageIO`
Parameters:
  `page` - Compact page.
  `pageSize` - Page size.

#### writeRowData

    protected abstract void writeRowData(long pageAddr,
                                         int dataOff,
                                         int payloadSize,
                                         T row,
                                         boolean newRow)
                                  throws IgniteCheckedException

Parameters:
  `pageAddr` - Page address.
  `dataOff` - Data offset.
  `payloadSize` - Payload size.
  `row` - Data row.
  `newRow` - `False` if existing cache entry is updated, in this case skip key data write.
Throws:
  `IgniteCheckedException` - If failed.

#### writeRowData

    protected void writeRowData(long pageAddr,
                                int dataOff,
                                byte[] payload)

Parameters:
  `pageAddr` - Page address.
  `dataOff` - Data offset.
  `payload` - Payload

${current.year} Copyright © Apache Software Foundation

Follow @ApacheIgnite

Ignite Database and Caching Platform | : ver. 2.13.0
Release Date | : April 20 2022