Drizzled Public API Documentation

fut0lst.cc
00001 /*****************************************************************************
00002 
00003 Copyright (C) 1995, 2009, Innobase Oy. All Rights Reserved.
00004 
00005 This program is free software; you can redistribute it and/or modify it under
00006 the terms of the GNU General Public License as published by the Free Software
00007 Foundation; version 2 of the License.
00008 
00009 This program is distributed in the hope that it will be useful, but WITHOUT
00010 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
00011 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
00012 
00013 You should have received a copy of the GNU General Public License along with
00014 this program; if not, write to the Free Software Foundation, Inc., 51 Franklin
00015 St, Fifth Floor, Boston, MA 02110-1301 USA
00016 
00017 *****************************************************************************/
00018 
00019 /******************************************************************/
00026 #include "fut0lst.h"
00027 
00028 #ifdef UNIV_NONINL
00029 #include "fut0lst.ic"
00030 #endif
00031 
00032 #include "buf0buf.h"
00033 #include "page0page.h"
00034 
00035 /********************************************************************/
00037 static
00038 void
00039 flst_add_to_empty(
00040 /*==============*/
00041   flst_base_node_t* base, 
00043   flst_node_t*    node, 
00044   mtr_t*      mtr)  
00045 {
00046   ulint   space;
00047   fil_addr_t  node_addr;
00048   ulint   len;
00049 
00050   ut_ad(mtr && base && node);
00051   ut_ad(base != node);
00052   ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
00053   ut_ad(mtr_memo_contains_page(mtr, node, MTR_MEMO_PAGE_X_FIX));
00054   len = flst_get_len(base, mtr);
00055   ut_a(len == 0);
00056 
00057   buf_ptr_get_fsp_addr(node, &space, &node_addr);
00058 
00059   /* Update first and last fields of base node */
00060   flst_write_addr(base + FLST_FIRST, node_addr, mtr);
00061   flst_write_addr(base + FLST_LAST, node_addr, mtr);
00062 
00063   /* Set prev and next fields of node to add */
00064   flst_write_addr(node + FLST_PREV, fil_addr_null, mtr);
00065   flst_write_addr(node + FLST_NEXT, fil_addr_null, mtr);
00066 
00067   /* Update len of base node */
00068   mlog_write_ulint(base + FLST_LEN, len + 1, MLOG_4BYTES, mtr);
00069 }
00070 
00071 /********************************************************************/
00073 UNIV_INTERN
00074 void
00075 flst_add_last(
00076 /*==========*/
00077   flst_base_node_t* base, 
00078   flst_node_t*    node, 
00079   mtr_t*      mtr)  
00080 {
00081   ulint   space;
00082   fil_addr_t  node_addr;
00083   ulint   len;
00084   fil_addr_t  last_addr;
00085   flst_node_t*  last_node;
00086 
00087   ut_ad(mtr && base && node);
00088   ut_ad(base != node);
00089   ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
00090   ut_ad(mtr_memo_contains_page(mtr, node, MTR_MEMO_PAGE_X_FIX));
00091   len = flst_get_len(base, mtr);
00092   last_addr = flst_get_last(base, mtr);
00093 
00094   buf_ptr_get_fsp_addr(node, &space, &node_addr);
00095 
00096   /* If the list is not empty, call flst_insert_after */
00097   if (len != 0) {
00098     if (last_addr.page == node_addr.page) {
00099       last_node = page_align(node) + last_addr.boffset;
00100     } else {
00101       ulint zip_size = fil_space_get_zip_size(space);
00102 
00103       last_node = fut_get_ptr(space, zip_size, last_addr,
00104             RW_X_LATCH, mtr);
00105     }
00106 
00107     flst_insert_after(base, last_node, node, mtr);
00108   } else {
00109     /* else call flst_add_to_empty */
00110     flst_add_to_empty(base, node, mtr);
00111   }
00112 }
00113 
00114 /********************************************************************/
00116 UNIV_INTERN
00117 void
00118 flst_add_first(
00119 /*===========*/
00120   flst_base_node_t* base, 
00121   flst_node_t*    node, 
00122   mtr_t*      mtr)  
00123 {
00124   ulint   space;
00125   fil_addr_t  node_addr;
00126   ulint   len;
00127   fil_addr_t  first_addr;
00128   flst_node_t*  first_node;
00129 
00130   ut_ad(mtr && base && node);
00131   ut_ad(base != node);
00132   ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
00133   ut_ad(mtr_memo_contains_page(mtr, node, MTR_MEMO_PAGE_X_FIX));
00134   len = flst_get_len(base, mtr);
00135   first_addr = flst_get_first(base, mtr);
00136 
00137   buf_ptr_get_fsp_addr(node, &space, &node_addr);
00138 
00139   /* If the list is not empty, call flst_insert_before */
00140   if (len != 0) {
00141     if (first_addr.page == node_addr.page) {
00142       first_node = page_align(node) + first_addr.boffset;
00143     } else {
00144       ulint zip_size = fil_space_get_zip_size(space);
00145 
00146       first_node = fut_get_ptr(space, zip_size, first_addr,
00147              RW_X_LATCH, mtr);
00148     }
00149 
00150     flst_insert_before(base, node, first_node, mtr);
00151   } else {
00152     /* else call flst_add_to_empty */
00153     flst_add_to_empty(base, node, mtr);
00154   }
00155 }
00156 
00157 /********************************************************************/
00159 UNIV_INTERN
00160 void
00161 flst_insert_after(
00162 /*==============*/
00163   flst_base_node_t* base, 
00164   flst_node_t*    node1,  
00165   flst_node_t*    node2,  
00166   mtr_t*      mtr)  
00167 {
00168   ulint   space;
00169   fil_addr_t  node1_addr;
00170   fil_addr_t  node2_addr;
00171   flst_node_t*  node3;
00172   fil_addr_t  node3_addr;
00173   ulint   len;
00174 
00175   ut_ad(mtr && node1 && node2 && base);
00176   ut_ad(base != node1);
00177   ut_ad(base != node2);
00178   ut_ad(node2 != node1);
00179   ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
00180   ut_ad(mtr_memo_contains_page(mtr, node1, MTR_MEMO_PAGE_X_FIX));
00181   ut_ad(mtr_memo_contains_page(mtr, node2, MTR_MEMO_PAGE_X_FIX));
00182 
00183   buf_ptr_get_fsp_addr(node1, &space, &node1_addr);
00184   buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
00185 
00186   node3_addr = flst_get_next_addr(node1, mtr);
00187 
00188   /* Set prev and next fields of node2 */
00189   flst_write_addr(node2 + FLST_PREV, node1_addr, mtr);
00190   flst_write_addr(node2 + FLST_NEXT, node3_addr, mtr);
00191 
00192   if (!fil_addr_is_null(node3_addr)) {
00193     /* Update prev field of node3 */
00194     ulint zip_size = fil_space_get_zip_size(space);
00195 
00196     node3 = fut_get_ptr(space, zip_size,
00197             node3_addr, RW_X_LATCH, mtr);
00198     flst_write_addr(node3 + FLST_PREV, node2_addr, mtr);
00199   } else {
00200     /* node1 was last in list: update last field in base */
00201     flst_write_addr(base + FLST_LAST, node2_addr, mtr);
00202   }
00203 
00204   /* Set next field of node1 */
00205   flst_write_addr(node1 + FLST_NEXT, node2_addr, mtr);
00206 
00207   /* Update len of base node */
00208   len = flst_get_len(base, mtr);
00209   mlog_write_ulint(base + FLST_LEN, len + 1, MLOG_4BYTES, mtr);
00210 }
00211 
00212 /********************************************************************/
00214 UNIV_INTERN
00215 void
00216 flst_insert_before(
00217 /*===============*/
00218   flst_base_node_t* base, 
00219   flst_node_t*    node2,  
00220   flst_node_t*    node3,  
00221   mtr_t*      mtr)  
00222 {
00223   ulint   space;
00224   flst_node_t*  node1;
00225   fil_addr_t  node1_addr;
00226   fil_addr_t  node2_addr;
00227   fil_addr_t  node3_addr;
00228   ulint   len;
00229 
00230   ut_ad(mtr && node2 && node3 && base);
00231   ut_ad(base != node2);
00232   ut_ad(base != node3);
00233   ut_ad(node2 != node3);
00234   ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
00235   ut_ad(mtr_memo_contains_page(mtr, node2, MTR_MEMO_PAGE_X_FIX));
00236   ut_ad(mtr_memo_contains_page(mtr, node3, MTR_MEMO_PAGE_X_FIX));
00237 
00238   buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
00239   buf_ptr_get_fsp_addr(node3, &space, &node3_addr);
00240 
00241   node1_addr = flst_get_prev_addr(node3, mtr);
00242 
00243   /* Set prev and next fields of node2 */
00244   flst_write_addr(node2 + FLST_PREV, node1_addr, mtr);
00245   flst_write_addr(node2 + FLST_NEXT, node3_addr, mtr);
00246 
00247   if (!fil_addr_is_null(node1_addr)) {
00248     ulint zip_size = fil_space_get_zip_size(space);
00249     /* Update next field of node1 */
00250     node1 = fut_get_ptr(space, zip_size, node1_addr,
00251             RW_X_LATCH, mtr);
00252     flst_write_addr(node1 + FLST_NEXT, node2_addr, mtr);
00253   } else {
00254     /* node3 was first in list: update first field in base */
00255     flst_write_addr(base + FLST_FIRST, node2_addr, mtr);
00256   }
00257 
00258   /* Set prev field of node3 */
00259   flst_write_addr(node3 + FLST_PREV, node2_addr, mtr);
00260 
00261   /* Update len of base node */
00262   len = flst_get_len(base, mtr);
00263   mlog_write_ulint(base + FLST_LEN, len + 1, MLOG_4BYTES, mtr);
00264 }
00265 
00266 /********************************************************************/
00268 UNIV_INTERN
00269 void
00270 flst_remove(
00271 /*========*/
00272   flst_base_node_t* base, 
00273   flst_node_t*    node2,  
00274   mtr_t*      mtr)  
00275 {
00276   ulint   space;
00277   ulint   zip_size;
00278   flst_node_t*  node1;
00279   fil_addr_t  node1_addr;
00280   fil_addr_t  node2_addr;
00281   flst_node_t*  node3;
00282   fil_addr_t  node3_addr;
00283   ulint   len;
00284 
00285   ut_ad(mtr && node2 && base);
00286   ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
00287   ut_ad(mtr_memo_contains_page(mtr, node2, MTR_MEMO_PAGE_X_FIX));
00288 
00289   buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
00290   zip_size = fil_space_get_zip_size(space);
00291 
00292   node1_addr = flst_get_prev_addr(node2, mtr);
00293   node3_addr = flst_get_next_addr(node2, mtr);
00294 
00295   if (!fil_addr_is_null(node1_addr)) {
00296 
00297     /* Update next field of node1 */
00298 
00299     if (node1_addr.page == node2_addr.page) {
00300 
00301       node1 = page_align(node2) + node1_addr.boffset;
00302     } else {
00303       node1 = fut_get_ptr(space, zip_size,
00304               node1_addr, RW_X_LATCH, mtr);
00305     }
00306 
00307     ut_ad(node1 != node2);
00308 
00309     flst_write_addr(node1 + FLST_NEXT, node3_addr, mtr);
00310   } else {
00311     /* node2 was first in list: update first field in base */
00312     flst_write_addr(base + FLST_FIRST, node3_addr, mtr);
00313   }
00314 
00315   if (!fil_addr_is_null(node3_addr)) {
00316     /* Update prev field of node3 */
00317 
00318     if (node3_addr.page == node2_addr.page) {
00319 
00320       node3 = page_align(node2) + node3_addr.boffset;
00321     } else {
00322       node3 = fut_get_ptr(space, zip_size,
00323               node3_addr, RW_X_LATCH, mtr);
00324     }
00325 
00326     ut_ad(node2 != node3);
00327 
00328     flst_write_addr(node3 + FLST_PREV, node1_addr, mtr);
00329   } else {
00330     /* node2 was last in list: update last field in base */
00331     flst_write_addr(base + FLST_LAST, node1_addr, mtr);
00332   }
00333 
00334   /* Update len of base node */
00335   len = flst_get_len(base, mtr);
00336   ut_ad(len > 0);
00337 
00338   mlog_write_ulint(base + FLST_LEN, len - 1, MLOG_4BYTES, mtr);
00339 }
00340 
00341 /********************************************************************/
00345 UNIV_INTERN
00346 void
00347 flst_cut_end(
00348 /*=========*/
00349   flst_base_node_t* base, 
00350   flst_node_t*    node2,  
00351   ulint     n_nodes,
00353   mtr_t*      mtr)  
00354 {
00355   ulint   space;
00356   flst_node_t*  node1;
00357   fil_addr_t  node1_addr;
00358   fil_addr_t  node2_addr;
00359   ulint   len;
00360 
00361   ut_ad(mtr && node2 && base);
00362   ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
00363   ut_ad(mtr_memo_contains_page(mtr, node2, MTR_MEMO_PAGE_X_FIX));
00364   ut_ad(n_nodes > 0);
00365 
00366   buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
00367 
00368   node1_addr = flst_get_prev_addr(node2, mtr);
00369 
00370   if (!fil_addr_is_null(node1_addr)) {
00371 
00372     /* Update next field of node1 */
00373 
00374     if (node1_addr.page == node2_addr.page) {
00375 
00376       node1 = page_align(node2) + node1_addr.boffset;
00377     } else {
00378       node1 = fut_get_ptr(space,
00379               fil_space_get_zip_size(space),
00380               node1_addr, RW_X_LATCH, mtr);
00381     }
00382 
00383     flst_write_addr(node1 + FLST_NEXT, fil_addr_null, mtr);
00384   } else {
00385     /* node2 was first in list: update the field in base */
00386     flst_write_addr(base + FLST_FIRST, fil_addr_null, mtr);
00387   }
00388 
00389   flst_write_addr(base + FLST_LAST, node1_addr, mtr);
00390 
00391   /* Update len of base node */
00392   len = flst_get_len(base, mtr);
00393   ut_ad(len >= n_nodes);
00394 
00395   mlog_write_ulint(base + FLST_LEN, len - n_nodes, MLOG_4BYTES, mtr);
00396 }
00397 
00398 /********************************************************************/
00402 UNIV_INTERN
00403 void
00404 flst_truncate_end(
00405 /*==============*/
00406   flst_base_node_t* base, 
00407   flst_node_t*    node2,  
00408   ulint     n_nodes,
00409   mtr_t*      mtr)  
00410 {
00411   fil_addr_t  node2_addr;
00412   ulint   len;
00413   ulint   space;
00414 
00415   ut_ad(mtr && node2 && base);
00416   ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
00417   ut_ad(mtr_memo_contains_page(mtr, node2, MTR_MEMO_PAGE_X_FIX));
00418   if (n_nodes == 0) {
00419 
00420     ut_ad(fil_addr_is_null(flst_get_next_addr(node2, mtr)));
00421 
00422     return;
00423   }
00424 
00425   buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
00426 
00427   /* Update next field of node2 */
00428   flst_write_addr(node2 + FLST_NEXT, fil_addr_null, mtr);
00429 
00430   flst_write_addr(base + FLST_LAST, node2_addr, mtr);
00431 
00432   /* Update len of base node */
00433   len = flst_get_len(base, mtr);
00434   ut_ad(len >= n_nodes);
00435 
00436   mlog_write_ulint(base + FLST_LEN, len - n_nodes, MLOG_4BYTES, mtr);
00437 }
00438 
00439 /********************************************************************/
00442 UNIV_INTERN
00443 ibool
00444 flst_validate(
00445 /*==========*/
00446   const flst_base_node_t* base, 
00447   mtr_t*      mtr1) 
00448 {
00449   ulint     space;
00450   ulint     zip_size;
00451   const flst_node_t*  node;
00452   fil_addr_t    node_addr;
00453   fil_addr_t    base_addr;
00454   ulint     len;
00455   ulint     i;
00456   mtr_t     mtr2;
00457 
00458   ut_ad(base);
00459   ut_ad(mtr_memo_contains_page(mtr1, base, MTR_MEMO_PAGE_X_FIX));
00460 
00461   /* We use two mini-transaction handles: the first is used to
00462   lock the base node, and prevent other threads from modifying the
00463   list. The second is used to traverse the list. We cannot run the
00464   second mtr without committing it at times, because if the list
00465   is long, then the x-locked pages could fill the buffer resulting
00466   in a deadlock. */
00467 
00468   /* Find out the space id */
00469   buf_ptr_get_fsp_addr(base, &space, &base_addr);
00470   zip_size = fil_space_get_zip_size(space);
00471 
00472   len = flst_get_len(base, mtr1);
00473   node_addr = flst_get_first(base, mtr1);
00474 
00475   for (i = 0; i < len; i++) {
00476     mtr_start(&mtr2);
00477 
00478     node = fut_get_ptr(space, zip_size,
00479            node_addr, RW_X_LATCH, &mtr2);
00480     node_addr = flst_get_next_addr(node, &mtr2);
00481 
00482     mtr_commit(&mtr2); /* Commit mtr2 each round to prevent buffer
00483            becoming full */
00484   }
00485 
00486   ut_a(fil_addr_is_null(node_addr));
00487 
00488   node_addr = flst_get_last(base, mtr1);
00489 
00490   for (i = 0; i < len; i++) {
00491     mtr_start(&mtr2);
00492 
00493     node = fut_get_ptr(space, zip_size,
00494            node_addr, RW_X_LATCH, &mtr2);
00495     node_addr = flst_get_prev_addr(node, &mtr2);
00496 
00497     mtr_commit(&mtr2); /* Commit mtr2 each round to prevent buffer
00498            becoming full */
00499   }
00500 
00501   ut_a(fil_addr_is_null(node_addr));
00502 
00503   return(TRUE);
00504 }
00505 
00506 /********************************************************************/
00508 UNIV_INTERN
00509 void
00510 flst_print(
00511 /*=======*/
00512   const flst_base_node_t* base, 
00513   mtr_t*      mtr)  
00514 {
00515   const buf_frame_t*  frame;
00516   ulint     len;
00517 
00518   ut_ad(base && mtr);
00519   ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
00520   frame = page_align((byte*) base);
00521 
00522   len = flst_get_len(base, mtr);
00523 
00524   fprintf(stderr,
00525     "FILE-BASED LIST:\n"
00526     "Base node in space %lu page %lu byte offset %lu; len %lu\n",
00527     (ulong) page_get_space_id(frame),
00528     (ulong) page_get_page_no(frame),
00529     (ulong) page_offset(base), (ulong) len);
00530 }