diff options
Diffstat (limited to 'innobase/fut/fut0lst.c')
| -rw-r--r-- | innobase/fut/fut0lst.c | 518 |
1 files changed, 0 insertions, 518 deletions
diff --git a/innobase/fut/fut0lst.c b/innobase/fut/fut0lst.c deleted file mode 100644 index 8deaa8adb3f..00000000000 --- a/innobase/fut/fut0lst.c +++ /dev/null @@ -1,518 +0,0 @@ -/********************************************************************** -File-based list utilities - -(c) 1995 Innobase Oy - -Created 11/28/1995 Heikki Tuuri -***********************************************************************/ - -#include "fut0lst.h" - -#ifdef UNIV_NONINL -#include "fut0lst.ic" -#endif - -#include "buf0buf.h" - - -/************************************************************************ -Adds a node to an empty list. */ -static -void -flst_add_to_empty( -/*==============*/ - flst_base_node_t* base, /* in: pointer to base node of - empty list */ - flst_node_t* node, /* in: node to add */ - mtr_t* mtr) /* in: mini-transaction handle */ -{ - ulint space; - fil_addr_t node_addr; - ulint len; - - ut_ad(mtr && base && node); - ut_ad(base != node); - ut_ad(mtr_memo_contains(mtr, buf_block_align(base), - MTR_MEMO_PAGE_X_FIX)); - ut_ad(mtr_memo_contains(mtr, buf_block_align(node), - MTR_MEMO_PAGE_X_FIX)); - len = flst_get_len(base, mtr); - ut_a(len == 0); - - buf_ptr_get_fsp_addr(node, &space, &node_addr); - - /* Update first and last fields of base node */ - flst_write_addr(base + FLST_FIRST, node_addr, mtr); - flst_write_addr(base + FLST_LAST, node_addr, mtr); - - /* Set prev and next fields of node to add */ - flst_write_addr(node + FLST_PREV, fil_addr_null, mtr); - flst_write_addr(node + FLST_NEXT, fil_addr_null, mtr); - - /* Update len of base node */ - mlog_write_ulint(base + FLST_LEN, len + 1, MLOG_4BYTES, mtr); -} - -/************************************************************************ -Adds a node as the last node in a list. */ - -void -flst_add_last( -/*==========*/ - flst_base_node_t* base, /* in: pointer to base node of list */ - flst_node_t* node, /* in: node to add */ - mtr_t* mtr) /* in: mini-transaction handle */ -{ - ulint space; - fil_addr_t node_addr; - ulint len; - fil_addr_t last_addr; - flst_node_t* last_node; - - ut_ad(mtr && base && node); - ut_ad(base != node); - ut_ad(mtr_memo_contains(mtr, buf_block_align(base), - MTR_MEMO_PAGE_X_FIX)); - ut_ad(mtr_memo_contains(mtr, buf_block_align(node), - MTR_MEMO_PAGE_X_FIX)); - len = flst_get_len(base, mtr); - last_addr = flst_get_last(base, mtr); - - buf_ptr_get_fsp_addr(node, &space, &node_addr); - - /* If the list is not empty, call flst_insert_after */ - if (len != 0) { - if (last_addr.page == node_addr.page) { - last_node = buf_frame_align(node) + last_addr.boffset; - } else { - last_node = fut_get_ptr(space, last_addr, RW_X_LATCH, - mtr); - } - - flst_insert_after(base, last_node, node, mtr); - } else { - /* else call flst_add_to_empty */ - flst_add_to_empty(base, node, mtr); - } -} - -/************************************************************************ -Adds a node as the first node in a list. */ - -void -flst_add_first( -/*===========*/ - flst_base_node_t* base, /* in: pointer to base node of list */ - flst_node_t* node, /* in: node to add */ - mtr_t* mtr) /* in: mini-transaction handle */ -{ - ulint space; - fil_addr_t node_addr; - ulint len; - fil_addr_t first_addr; - flst_node_t* first_node; - - ut_ad(mtr && base && node); - ut_ad(base != node); - ut_ad(mtr_memo_contains(mtr, buf_block_align(base), - MTR_MEMO_PAGE_X_FIX)); - ut_ad(mtr_memo_contains(mtr, buf_block_align(node), - MTR_MEMO_PAGE_X_FIX)); - len = flst_get_len(base, mtr); - first_addr = flst_get_first(base, mtr); - - buf_ptr_get_fsp_addr(node, &space, &node_addr); - - /* If the list is not empty, call flst_insert_before */ - if (len != 0) { - if (first_addr.page == node_addr.page) { - first_node = buf_frame_align(node) - + first_addr.boffset; - } else { - first_node = fut_get_ptr(space, first_addr, - RW_X_LATCH, mtr); - } - - flst_insert_before(base, node, first_node, mtr); - } else { - /* else call flst_add_to_empty */ - flst_add_to_empty(base, node, mtr); - } -} - -/************************************************************************ -Inserts a node after another in a list. */ - -void -flst_insert_after( -/*==============*/ - flst_base_node_t* base, /* in: pointer to base node of list */ - flst_node_t* node1, /* in: node to insert after */ - flst_node_t* node2, /* in: node to add */ - mtr_t* mtr) /* in: mini-transaction handle */ -{ - ulint space; - fil_addr_t node1_addr; - fil_addr_t node2_addr; - flst_node_t* node3; - fil_addr_t node3_addr; - ulint len; - - ut_ad(mtr && node1 && node2 && base); - ut_ad(base != node1); - ut_ad(base != node2); - ut_ad(node2 != node1); - ut_ad(mtr_memo_contains(mtr, buf_block_align(base), - MTR_MEMO_PAGE_X_FIX)); - ut_ad(mtr_memo_contains(mtr, buf_block_align(node1), - MTR_MEMO_PAGE_X_FIX)); - ut_ad(mtr_memo_contains(mtr, buf_block_align(node2), - MTR_MEMO_PAGE_X_FIX)); - - buf_ptr_get_fsp_addr(node1, &space, &node1_addr); - buf_ptr_get_fsp_addr(node2, &space, &node2_addr); - - node3_addr = flst_get_next_addr(node1, mtr); - - /* Set prev and next fields of node2 */ - flst_write_addr(node2 + FLST_PREV, node1_addr, mtr); - flst_write_addr(node2 + FLST_NEXT, node3_addr, mtr); - - if (!fil_addr_is_null(node3_addr)) { - /* Update prev field of node3 */ - node3 = fut_get_ptr(space, node3_addr, RW_X_LATCH, mtr); - flst_write_addr(node3 + FLST_PREV, node2_addr, mtr); - } else { - /* node1 was last in list: update last field in base */ - flst_write_addr(base + FLST_LAST, node2_addr, mtr); - } - - /* Set next field of node1 */ - flst_write_addr(node1 + FLST_NEXT, node2_addr, mtr); - - /* Update len of base node */ - len = flst_get_len(base, mtr); - mlog_write_ulint(base + FLST_LEN, len + 1, MLOG_4BYTES, mtr); -} - -/************************************************************************ -Inserts a node before another in a list. */ - -void -flst_insert_before( -/*===============*/ - flst_base_node_t* base, /* in: pointer to base node of list */ - flst_node_t* node2, /* in: node to insert */ - flst_node_t* node3, /* in: node to insert before */ - mtr_t* mtr) /* in: mini-transaction handle */ -{ - ulint space; - flst_node_t* node1; - fil_addr_t node1_addr; - fil_addr_t node2_addr; - fil_addr_t node3_addr; - ulint len; - - ut_ad(mtr && node2 && node3 && base); - ut_ad(base != node2); - ut_ad(base != node3); - ut_ad(node2 != node3); - ut_ad(mtr_memo_contains(mtr, buf_block_align(base), - MTR_MEMO_PAGE_X_FIX)); - ut_ad(mtr_memo_contains(mtr, buf_block_align(node2), - MTR_MEMO_PAGE_X_FIX)); - ut_ad(mtr_memo_contains(mtr, buf_block_align(node3), - MTR_MEMO_PAGE_X_FIX)); - - buf_ptr_get_fsp_addr(node2, &space, &node2_addr); - buf_ptr_get_fsp_addr(node3, &space, &node3_addr); - - node1_addr = flst_get_prev_addr(node3, mtr); - - /* Set prev and next fields of node2 */ - flst_write_addr(node2 + FLST_PREV, node1_addr, mtr); - flst_write_addr(node2 + FLST_NEXT, node3_addr, mtr); - - if (!fil_addr_is_null(node1_addr)) { - /* Update next field of node1 */ - node1 = fut_get_ptr(space, node1_addr, RW_X_LATCH, mtr); - flst_write_addr(node1 + FLST_NEXT, node2_addr, mtr); - } else { - /* node3 was first in list: update first field in base */ - flst_write_addr(base + FLST_FIRST, node2_addr, mtr); - } - - /* Set prev field of node3 */ - flst_write_addr(node3 + FLST_PREV, node2_addr, mtr); - - /* Update len of base node */ - len = flst_get_len(base, mtr); - mlog_write_ulint(base + FLST_LEN, len + 1, MLOG_4BYTES, mtr); -} - -/************************************************************************ -Removes a node. */ - -void -flst_remove( -/*========*/ - flst_base_node_t* base, /* in: pointer to base node of list */ - flst_node_t* node2, /* in: node to remove */ - mtr_t* mtr) /* in: mini-transaction handle */ -{ - ulint space; - flst_node_t* node1; - fil_addr_t node1_addr; - fil_addr_t node2_addr; - flst_node_t* node3; - fil_addr_t node3_addr; - ulint len; - - ut_ad(mtr && node2 && base); - ut_ad(mtr_memo_contains(mtr, buf_block_align(base), - MTR_MEMO_PAGE_X_FIX)); - ut_ad(mtr_memo_contains(mtr, buf_block_align(node2), - MTR_MEMO_PAGE_X_FIX)); - - buf_ptr_get_fsp_addr(node2, &space, &node2_addr); - - node1_addr = flst_get_prev_addr(node2, mtr); - node3_addr = flst_get_next_addr(node2, mtr); - - if (!fil_addr_is_null(node1_addr)) { - - /* Update next field of node1 */ - - if (node1_addr.page == node2_addr.page) { - - node1 = buf_frame_align(node2) + node1_addr.boffset; - } else { - node1 = fut_get_ptr(space, node1_addr, RW_X_LATCH, - mtr); - } - - ut_ad(node1 != node2); - - flst_write_addr(node1 + FLST_NEXT, node3_addr, mtr); - } else { - /* node2 was first in list: update first field in base */ - flst_write_addr(base + FLST_FIRST, node3_addr, mtr); - } - - if (!fil_addr_is_null(node3_addr)) { - /* Update prev field of node3 */ - - if (node3_addr.page == node2_addr.page) { - - node3 = buf_frame_align(node2) + node3_addr.boffset; - } else { - node3 = fut_get_ptr(space, node3_addr, RW_X_LATCH, - mtr); - } - - ut_ad(node2 != node3); - - flst_write_addr(node3 + FLST_PREV, node1_addr, mtr); - } else { - /* node2 was last in list: update last field in base */ - flst_write_addr(base + FLST_LAST, node1_addr, mtr); - } - - /* Update len of base node */ - len = flst_get_len(base, mtr); - ut_ad(len > 0); - - mlog_write_ulint(base + FLST_LEN, len - 1, MLOG_4BYTES, mtr); -} - -/************************************************************************ -Cuts off the tail of the list, including the node given. The number of -nodes which will be removed must be provided by the caller, as this function -does not measure the length of the tail. */ - -void -flst_cut_end( -/*=========*/ - flst_base_node_t* base, /* in: pointer to base node of list */ - flst_node_t* node2, /* in: first node to remove */ - ulint n_nodes,/* in: number of nodes to remove, - must be >= 1 */ - mtr_t* mtr) /* in: mini-transaction handle */ -{ - ulint space; - flst_node_t* node1; - fil_addr_t node1_addr; - fil_addr_t node2_addr; - ulint len; - - ut_ad(mtr && node2 && base); - ut_ad(mtr_memo_contains(mtr, buf_block_align(base), - MTR_MEMO_PAGE_X_FIX)); - ut_ad(mtr_memo_contains(mtr, buf_block_align(node2), - MTR_MEMO_PAGE_X_FIX)); - ut_ad(n_nodes > 0); - - buf_ptr_get_fsp_addr(node2, &space, &node2_addr); - - node1_addr = flst_get_prev_addr(node2, mtr); - - if (!fil_addr_is_null(node1_addr)) { - - /* Update next field of node1 */ - - if (node1_addr.page == node2_addr.page) { - - node1 = buf_frame_align(node2) + node1_addr.boffset; - } else { - node1 = fut_get_ptr(space, node1_addr, RW_X_LATCH, - mtr); - } - - flst_write_addr(node1 + FLST_NEXT, fil_addr_null, mtr); - } else { - /* node2 was first in list: update the field in base */ - flst_write_addr(base + FLST_FIRST, fil_addr_null, mtr); - } - - flst_write_addr(base + FLST_LAST, node1_addr, mtr); - - /* Update len of base node */ - len = flst_get_len(base, mtr); - ut_ad(len >= n_nodes); - - mlog_write_ulint(base + FLST_LEN, len - n_nodes, MLOG_4BYTES, mtr); -} - -/************************************************************************ -Cuts off the tail of the list, not including the given node. The number of -nodes which will be removed must be provided by the caller, as this function -does not measure the length of the tail. */ - -void -flst_truncate_end( -/*==============*/ - flst_base_node_t* base, /* in: pointer to base node of list */ - flst_node_t* node2, /* in: first node not to remove */ - ulint n_nodes,/* in: number of nodes to remove */ - mtr_t* mtr) /* in: mini-transaction handle */ -{ - fil_addr_t node2_addr; - ulint len; - ulint space; - - ut_ad(mtr && node2 && base); - ut_ad(mtr_memo_contains(mtr, buf_block_align(base), - MTR_MEMO_PAGE_X_FIX)); - ut_ad(mtr_memo_contains(mtr, buf_block_align(node2), - MTR_MEMO_PAGE_X_FIX)); - if (n_nodes == 0) { - - ut_ad(fil_addr_is_null(flst_get_next_addr(node2, mtr))); - - return; - } - - buf_ptr_get_fsp_addr(node2, &space, &node2_addr); - - /* Update next field of node2 */ - flst_write_addr(node2 + FLST_NEXT, fil_addr_null, mtr); - - flst_write_addr(base + FLST_LAST, node2_addr, mtr); - - /* Update len of base node */ - len = flst_get_len(base, mtr); - ut_ad(len >= n_nodes); - - mlog_write_ulint(base + FLST_LEN, len - n_nodes, MLOG_4BYTES, mtr); -} - -/************************************************************************ -Validates a file-based list. */ - -ibool -flst_validate( -/*==========*/ - /* out: TRUE if ok */ - flst_base_node_t* base, /* in: pointer to base node of list */ - mtr_t* mtr1) /* in: mtr */ -{ - ulint space; - flst_node_t* node; - fil_addr_t node_addr; - fil_addr_t base_addr; - ulint len; - ulint i; - mtr_t mtr2; - - ut_ad(base); - ut_ad(mtr_memo_contains(mtr1, buf_block_align(base), - MTR_MEMO_PAGE_X_FIX)); - - /* We use two mini-transaction handles: the first is used to - lock the base node, and prevent other threads from modifying the - list. The second is used to traverse the list. We cannot run the - second mtr without committing it at times, because if the list - is long, then the x-locked pages could fill the buffer resulting - in a deadlock. */ - - /* Find out the space id */ - buf_ptr_get_fsp_addr(base, &space, &base_addr); - - len = flst_get_len(base, mtr1); - node_addr = flst_get_first(base, mtr1); - - for (i = 0; i < len; i++) { - mtr_start(&mtr2); - - node = fut_get_ptr(space, node_addr, RW_X_LATCH, &mtr2); - node_addr = flst_get_next_addr(node, &mtr2); - - mtr_commit(&mtr2); /* Commit mtr2 each round to prevent buffer - becoming full */ - } - - ut_a(fil_addr_is_null(node_addr)); - - node_addr = flst_get_last(base, mtr1); - - for (i = 0; i < len; i++) { - mtr_start(&mtr2); - - node = fut_get_ptr(space, node_addr, RW_X_LATCH, &mtr2); - node_addr = flst_get_prev_addr(node, &mtr2); - - mtr_commit(&mtr2); /* Commit mtr2 each round to prevent buffer - becoming full */ - } - - ut_a(fil_addr_is_null(node_addr)); - - return(TRUE); -} - -/************************************************************************ -Prints info of a file-based list. */ - -void -flst_print( -/*=======*/ - flst_base_node_t* base, /* in: pointer to base node of list */ - mtr_t* mtr) /* in: mtr */ -{ - buf_frame_t* frame; - ulint len; - - ut_ad(base && mtr); - ut_ad(mtr_memo_contains(mtr, buf_block_align(base), - MTR_MEMO_PAGE_X_FIX)); - frame = buf_frame_align(base); - - len = flst_get_len(base, mtr); - - fprintf(stderr, - "FILE-BASED LIST:\n" - "Base node in space %lu page %lu byte offset %lu; len %lu\n", - (ulong) buf_frame_get_space_id(frame), - (ulong) buf_frame_get_page_no(frame), - (ulong) (base - frame), (ulong) len); -} |