1
/************************************************************************
4
(c) 1994-1996 Innobase Oy
6
Created 10/4/1994 Heikki Tuuri
7
*************************************************************************/
11
#include "page0cur.ic"
21
static ulint page_rnd = 976722341;
24
# ifdef UNIV_SEARCH_PERF_STAT
25
ulint page_cur_short_succ = 0;
26
# endif /* UNIV_SEARCH_PERF_STAT */
28
/***********************************************************************
29
This is a linear congruential generator PRNG. Returns a pseudo random
30
number between 0 and 2^64-1 inclusive. The formula and the constants
32
X[n+1] = (a * X[n] + c) mod m
35
a = 1103515245 (3^5 * 5 * 7 * 129749)
36
c = 12345 (3 * 5 * 823)
37
m = 18446744073709551616 (2^64)
39
#define LCG_a 1103515245
45
/* out: number between 0 and 2^64-1 */
47
static unsigned long long lcg_current = 0;
48
static ibool initialized = FALSE;
53
ut_usectime(&time_sec, &time_ms);
54
lcg_current = (unsigned long long) (time_sec * 1000000
59
/* no need to "% 2^64" explicitly because lcg_current is
60
64 bit and this will be done anyway */
61
lcg_current = LCG_a * lcg_current + LCG_c;
66
/********************************************************************
67
Tries a search shortcut based on the last insert. */
70
page_cur_try_search_shortcut(
71
/*=========================*/
72
/* out: TRUE on success */
73
page_t* page, /* in: index page */
74
dict_index_t* index, /* in: record descriptor */
75
dtuple_t* tuple, /* in: data tuple */
76
ulint* iup_matched_fields,
77
/* in/out: already matched fields in upper
79
ulint* iup_matched_bytes,
80
/* in/out: already matched bytes in a field
81
not yet completely matched */
82
ulint* ilow_matched_fields,
83
/* in/out: already matched fields in lower
85
ulint* ilow_matched_bytes,
86
/* in/out: already matched bytes in a field
87
not yet completely matched */
88
page_cur_t* cursor) /* out: page cursor */
96
#ifdef UNIV_SEARCH_DEBUG
99
ibool success = FALSE;
100
mem_heap_t* heap = NULL;
101
ulint offsets_[REC_OFFS_NORMAL_SIZE];
102
ulint* offsets = offsets_;
103
*offsets_ = (sizeof offsets_) / sizeof *offsets_;
105
ut_ad(dtuple_check_typed(tuple));
107
rec = page_header_get_ptr(page, PAGE_LAST_INSERT);
108
offsets = rec_get_offsets(rec, index, offsets,
109
dtuple_get_n_fields(tuple), &heap);
112
ut_ad(page_rec_is_user_rec(rec));
114
ut_pair_min(&low_match, &low_bytes,
115
*ilow_matched_fields, *ilow_matched_bytes,
116
*iup_matched_fields, *iup_matched_bytes);
118
up_match = low_match;
119
up_bytes = low_bytes;
121
if (page_cmp_dtuple_rec_with_match(tuple, rec, offsets,
122
&low_match, &low_bytes) < 0) {
126
next_rec = page_rec_get_next(rec);
127
offsets = rec_get_offsets(next_rec, index, offsets,
128
dtuple_get_n_fields(tuple), &heap);
130
if (page_cmp_dtuple_rec_with_match(tuple, next_rec, offsets,
131
&up_match, &up_bytes) >= 0) {
137
#ifdef UNIV_SEARCH_DEBUG
138
page_cur_search_with_match(page, index, tuple, PAGE_CUR_DBG,
144
ut_a(cursor2.rec == cursor->rec);
146
if (next_rec != page_get_supremum_rec(page)) {
148
ut_a(*iup_matched_fields == up_match);
149
ut_a(*iup_matched_bytes == up_bytes);
152
ut_a(*ilow_matched_fields == low_match);
153
ut_a(*ilow_matched_bytes == low_bytes);
155
if (!page_rec_is_supremum(next_rec)) {
157
*iup_matched_fields = up_match;
158
*iup_matched_bytes = up_bytes;
161
*ilow_matched_fields = low_match;
162
*ilow_matched_bytes = low_bytes;
164
#ifdef UNIV_SEARCH_PERF_STAT
165
page_cur_short_succ++;
169
if (UNIV_LIKELY_NULL(heap)) {
177
#ifdef PAGE_CUR_LE_OR_EXTENDS
178
/********************************************************************
179
Checks if the nth field in a record is a character type field which extends
180
the nth field in tuple, i.e., the field is longer or equal in length and has
181
common first characters. */
184
page_cur_rec_field_extends(
185
/*=======================*/
186
/* out: TRUE if rec field
187
extends tuple field */
188
dtuple_t* tuple, /* in: data tuple */
189
rec_t* rec, /* in: record */
190
const ulint* offsets,/* in: array returned by rec_get_offsets() */
191
ulint n) /* in: compare nth field */
198
ut_ad(rec_offs_validate(rec, NULL, offsets));
199
dfield = dtuple_get_nth_field(tuple, n);
201
type = dfield_get_type(dfield);
203
rec_f = rec_get_nth_field(rec, offsets, n, &rec_f_len);
205
if (type->mtype == DATA_VARCHAR
206
|| type->mtype == DATA_CHAR
207
|| type->mtype == DATA_FIXBINARY
208
|| type->mtype == DATA_BINARY
209
|| type->mtype == DATA_BLOB
210
|| type->mtype == DATA_VARMYSQL
211
|| type->mtype == DATA_MYSQL) {
213
if (dfield_get_len(dfield) != UNIV_SQL_NULL
214
&& rec_f_len != UNIV_SQL_NULL
215
&& rec_f_len >= dfield_get_len(dfield)
216
&& !cmp_data_data_slow(type,
217
dfield_get_data(dfield),
218
dfield_get_len(dfield),
219
rec_f, dfield_get_len(dfield))) {
227
#endif /* PAGE_CUR_LE_OR_EXTENDS */
229
/********************************************************************
230
Searches the right position for a page cursor. */
233
page_cur_search_with_match(
234
/*=======================*/
235
page_t* page, /* in: index page */
236
dict_index_t* index, /* in: record descriptor */
237
dtuple_t* tuple, /* in: data tuple */
238
ulint mode, /* in: PAGE_CUR_L, PAGE_CUR_LE, PAGE_CUR_G,
240
ulint* iup_matched_fields,
241
/* in/out: already matched fields in upper
243
ulint* iup_matched_bytes,
244
/* in/out: already matched bytes in a field
245
not yet completely matched */
246
ulint* ilow_matched_fields,
247
/* in/out: already matched fields in lower
249
ulint* ilow_matched_bytes,
250
/* in/out: already matched bytes in a field
251
not yet completely matched */
252
page_cur_t* cursor) /* out: page cursor */
257
page_dir_slot_t* slot;
261
ulint up_matched_fields;
262
ulint up_matched_bytes;
263
ulint low_matched_fields;
264
ulint low_matched_bytes;
265
ulint cur_matched_fields;
266
ulint cur_matched_bytes;
268
#ifdef UNIV_SEARCH_DEBUG
270
ulint dbg_matched_fields;
271
ulint dbg_matched_bytes;
273
mem_heap_t* heap = NULL;
274
ulint offsets_[REC_OFFS_NORMAL_SIZE];
275
ulint* offsets = offsets_;
276
*offsets_ = (sizeof offsets_) / sizeof *offsets_;
278
ut_ad(page && tuple && iup_matched_fields && iup_matched_bytes
279
&& ilow_matched_fields && ilow_matched_bytes && cursor);
280
ut_ad(dtuple_validate(tuple));
281
ut_ad(dtuple_check_typed(tuple));
284
if (mode != PAGE_CUR_DBG)
285
# endif /* PAGE_CUR_DBG */
286
# ifdef PAGE_CUR_LE_OR_EXTENDS
287
if (mode != PAGE_CUR_LE_OR_EXTENDS)
288
# endif /* PAGE_CUR_LE_OR_EXTENDS */
289
ut_ad(mode == PAGE_CUR_L || mode == PAGE_CUR_LE
290
|| mode == PAGE_CUR_G || mode == PAGE_CUR_GE);
291
#endif /* UNIV_DEBUG */
293
page_check_dir(page);
295
#ifdef PAGE_CUR_ADAPT
296
if ((page_header_get_field(page, PAGE_LEVEL) == 0)
297
&& (mode == PAGE_CUR_LE)
298
&& (page_header_get_field(page, PAGE_N_DIRECTION) > 3)
299
&& (page_header_get_ptr(page, PAGE_LAST_INSERT))
300
&& (page_header_get_field(page, PAGE_DIRECTION) == PAGE_RIGHT)) {
302
if (page_cur_try_search_shortcut(
304
iup_matched_fields, iup_matched_bytes,
305
ilow_matched_fields, ilow_matched_bytes,
311
if (mode == PAGE_CUR_DBG) {
317
/* The following flag does not work for non-latin1 char sets because
318
cmp_full_field does not tell how many bytes matched */
319
#ifdef PAGE_CUR_LE_OR_EXTENDS
320
ut_a(mode != PAGE_CUR_LE_OR_EXTENDS);
321
#endif /* PAGE_CUR_LE_OR_EXTENDS */
323
/* If mode PAGE_CUR_G is specified, we are trying to position the
324
cursor to answer a query of the form "tuple < X", where tuple is
325
the input parameter, and X denotes an arbitrary physical record on
326
the page. We want to position the cursor on the first X which
327
satisfies the condition. */
329
up_matched_fields = *iup_matched_fields;
330
up_matched_bytes = *iup_matched_bytes;
331
low_matched_fields = *ilow_matched_fields;
332
low_matched_bytes = *ilow_matched_bytes;
334
/* Perform binary search. First the search is done through the page
335
directory, after that as a linear search in the list of records
336
owned by the upper limit directory slot. */
339
up = page_dir_get_n_slots(page) - 1;
341
/* Perform binary search until the lower and upper limit directory
342
slots come to the distance 1 of each other */
344
while (up - low > 1) {
345
mid = (low + up) / 2;
346
slot = page_dir_get_nth_slot(page, mid);
347
mid_rec = page_dir_slot_get_rec(slot);
349
ut_pair_min(&cur_matched_fields, &cur_matched_bytes,
350
low_matched_fields, low_matched_bytes,
351
up_matched_fields, up_matched_bytes);
353
offsets = rec_get_offsets(mid_rec, index, offsets,
354
dtuple_get_n_fields_cmp(tuple),
357
cmp = cmp_dtuple_rec_with_match(tuple, mid_rec, offsets,
360
if (UNIV_LIKELY(cmp > 0)) {
363
low_matched_fields = cur_matched_fields;
364
low_matched_bytes = cur_matched_bytes;
366
} else if (UNIV_EXPECT(cmp, -1)) {
367
#ifdef PAGE_CUR_LE_OR_EXTENDS
368
if (mode == PAGE_CUR_LE_OR_EXTENDS
369
&& page_cur_rec_field_extends(
370
tuple, mid_rec, offsets,
371
cur_matched_fields)) {
375
#endif /* PAGE_CUR_LE_OR_EXTENDS */
378
up_matched_fields = cur_matched_fields;
379
up_matched_bytes = cur_matched_bytes;
381
} else if (mode == PAGE_CUR_G || mode == PAGE_CUR_LE
382
#ifdef PAGE_CUR_LE_OR_EXTENDS
383
|| mode == PAGE_CUR_LE_OR_EXTENDS
384
#endif /* PAGE_CUR_LE_OR_EXTENDS */
394
slot = page_dir_get_nth_slot(page, low);
395
low_rec = page_dir_slot_get_rec(slot);
396
slot = page_dir_get_nth_slot(page, up);
397
up_rec = page_dir_slot_get_rec(slot);
399
/* Perform linear search until the upper and lower records come to
400
distance 1 of each other. */
402
while (page_rec_get_next(low_rec) != up_rec) {
404
mid_rec = page_rec_get_next(low_rec);
406
ut_pair_min(&cur_matched_fields, &cur_matched_bytes,
407
low_matched_fields, low_matched_bytes,
408
up_matched_fields, up_matched_bytes);
410
offsets = rec_get_offsets(mid_rec, index, offsets,
411
dtuple_get_n_fields_cmp(tuple),
414
cmp = cmp_dtuple_rec_with_match(tuple, mid_rec, offsets,
417
if (UNIV_LIKELY(cmp > 0)) {
420
low_matched_fields = cur_matched_fields;
421
low_matched_bytes = cur_matched_bytes;
423
} else if (UNIV_EXPECT(cmp, -1)) {
424
#ifdef PAGE_CUR_LE_OR_EXTENDS
425
if (mode == PAGE_CUR_LE_OR_EXTENDS
426
&& page_cur_rec_field_extends(
427
tuple, mid_rec, offsets,
428
cur_matched_fields)) {
432
#endif /* PAGE_CUR_LE_OR_EXTENDS */
435
up_matched_fields = cur_matched_fields;
436
up_matched_bytes = cur_matched_bytes;
437
} else if (mode == PAGE_CUR_G || mode == PAGE_CUR_LE
438
#ifdef PAGE_CUR_LE_OR_EXTENDS
439
|| mode == PAGE_CUR_LE_OR_EXTENDS
440
#endif /* PAGE_CUR_LE_OR_EXTENDS */
450
#ifdef UNIV_SEARCH_DEBUG
452
/* Check that the lower and upper limit records have the
453
right alphabetical order compared to tuple. */
454
dbg_matched_fields = 0;
455
dbg_matched_bytes = 0;
457
offsets = rec_get_offsets(low_rec, index, offsets,
458
ULINT_UNDEFINED, &heap);
459
dbg_cmp = page_cmp_dtuple_rec_with_match(tuple, low_rec, offsets,
462
if (mode == PAGE_CUR_G) {
464
} else if (mode == PAGE_CUR_GE) {
466
} else if (mode == PAGE_CUR_L) {
468
} else if (mode == PAGE_CUR_LE) {
472
if (low_rec != page_get_infimum_rec(page)) {
474
ut_a(low_matched_fields == dbg_matched_fields);
475
ut_a(low_matched_bytes == dbg_matched_bytes);
478
dbg_matched_fields = 0;
479
dbg_matched_bytes = 0;
481
offsets = rec_get_offsets(up_rec, index, offsets,
482
ULINT_UNDEFINED, &heap);
483
dbg_cmp = page_cmp_dtuple_rec_with_match(tuple, up_rec, offsets,
486
if (mode == PAGE_CUR_G) {
488
} else if (mode == PAGE_CUR_GE) {
490
} else if (mode == PAGE_CUR_L) {
492
} else if (mode == PAGE_CUR_LE) {
496
if (up_rec != page_get_supremum_rec(page)) {
498
ut_a(up_matched_fields == dbg_matched_fields);
499
ut_a(up_matched_bytes == dbg_matched_bytes);
502
if (mode <= PAGE_CUR_GE) {
503
cursor->rec = up_rec;
505
cursor->rec = low_rec;
508
*iup_matched_fields = up_matched_fields;
509
*iup_matched_bytes = up_matched_bytes;
510
*ilow_matched_fields = low_matched_fields;
511
*ilow_matched_bytes = low_matched_bytes;
512
if (UNIV_LIKELY_NULL(heap)) {
517
/***************************************************************
518
Positions a page cursor on a randomly chosen user record on a page. If there
519
are no user records, sets the cursor on the infimum record. */
522
page_cur_open_on_rnd_user_rec(
523
/*==========================*/
524
page_t* page, /* in: page */
525
page_cur_t* cursor) /* in/out: page cursor */
530
if (page_get_n_recs(page) == 0) {
531
page_cur_position(page_get_infimum_rec(page), cursor);
536
if (srv_use_legacy_cardinality_algorithm) {
537
page_rnd += 87584577;
539
rnd = page_rnd % page_get_n_recs(page);
541
rnd = (ulint) (page_cur_lcg_prng() % page_get_n_recs(page));
544
rec = page_get_infimum_rec(page);
546
rec = page_rec_get_next(rec);
549
rec = page_rec_get_next(rec);
554
page_cur_position(rec, cursor);
557
/***************************************************************
558
Writes the log record of a record insert on a page. */
561
page_cur_insert_rec_write_log(
562
/*==========================*/
563
rec_t* insert_rec, /* in: inserted physical record */
564
ulint rec_size, /* in: insert_rec size */
565
rec_t* cursor_rec, /* in: record the
566
cursor is pointing to */
567
dict_index_t* index, /* in: record descriptor */
568
mtr_t* mtr) /* in: mini-transaction handle */
572
ulint cur_extra_size;
576
ulint extra_info_yes;
582
ut_a(rec_size < UNIV_PAGE_SIZE);
583
ut_ad(buf_frame_align(insert_rec) == buf_frame_align(cursor_rec));
584
ut_ad(!page_rec_is_comp(insert_rec)
585
== !dict_table_is_comp(index->table));
586
comp = page_rec_is_comp(insert_rec);
589
mem_heap_t* heap = NULL;
590
ulint cur_offs_[REC_OFFS_NORMAL_SIZE];
591
ulint ins_offs_[REC_OFFS_NORMAL_SIZE];
596
*cur_offs_ = (sizeof cur_offs_) / sizeof *cur_offs_;
597
*ins_offs_ = (sizeof ins_offs_) / sizeof *ins_offs_;
599
cur_offs = rec_get_offsets(cursor_rec, index, cur_offs_,
600
ULINT_UNDEFINED, &heap);
601
ins_offs = rec_get_offsets(insert_rec, index, ins_offs_,
602
ULINT_UNDEFINED, &heap);
604
extra_size = rec_offs_extra_size(ins_offs);
605
cur_extra_size = rec_offs_extra_size(cur_offs);
606
ut_ad(rec_size == rec_offs_size(ins_offs));
607
cur_rec_size = rec_offs_size(cur_offs);
609
if (UNIV_LIKELY_NULL(heap)) {
614
ins_ptr = insert_rec - extra_size;
618
if (cur_extra_size == extra_size) {
619
min_rec_size = ut_min(cur_rec_size, rec_size);
621
cur_ptr = cursor_rec - cur_extra_size;
623
/* Find out the first byte in insert_rec which differs from
624
cursor_rec; skip the bytes in the record info */
627
if (i >= min_rec_size) {
630
} else if (*ins_ptr == *cur_ptr) {
634
} else if ((i < extra_size)
637
? REC_N_NEW_EXTRA_BYTES
638
: REC_N_OLD_EXTRA_BYTES))) {
640
ins_ptr = insert_rec;
641
cur_ptr = cursor_rec;
648
if (mtr_get_log_mode(mtr) != MTR_LOG_SHORT_INSERTS) {
650
log_ptr = mlog_open_and_write_index(mtr, insert_rec, index,
652
? MLOG_COMP_REC_INSERT
658
/* Logging in mtr is switched off during crash
659
recovery: in that case mlog_open returns NULL */
663
log_end = &log_ptr[2 + 5 + 1 + 5 + 5 + MLOG_BUF_MARGIN];
664
/* Write the cursor rec offset as a 2-byte ulint */
665
mach_write_to_2(log_ptr, cursor_rec
666
- buf_frame_align(cursor_rec));
669
log_ptr = mlog_open(mtr, 5 + 1 + 5 + 5 + MLOG_BUF_MARGIN);
671
/* Logging in mtr is switched off during crash
672
recovery: in that case mlog_open returns NULL */
675
log_end = &log_ptr[5 + 1 + 5 + 5 + MLOG_BUF_MARGIN];
678
if ((rec_get_info_and_status_bits(insert_rec, comp)
679
!= rec_get_info_and_status_bits(cursor_rec, comp))
680
|| (extra_size != cur_extra_size)
681
|| (rec_size != cur_rec_size)) {
688
/* Write the record end segment length and the extra info storage
690
log_ptr += mach_write_compressed(log_ptr, 2 * (rec_size - i)
692
if (extra_info_yes) {
693
/* Write the info bits */
694
mach_write_to_1(log_ptr,
695
rec_get_info_and_status_bits(insert_rec,
699
/* Write the record origin offset */
700
log_ptr += mach_write_compressed(log_ptr, extra_size);
702
/* Write the mismatch index */
703
log_ptr += mach_write_compressed(log_ptr, i);
705
ut_a(i < UNIV_PAGE_SIZE);
706
ut_a(extra_size < UNIV_PAGE_SIZE);
709
/* Write to the log the inserted index record end segment which
710
differs from the cursor record */
714
if (log_ptr + rec_size <= log_end) {
715
memcpy(log_ptr, ins_ptr, rec_size);
716
mlog_close(mtr, log_ptr + rec_size);
718
mlog_close(mtr, log_ptr);
719
ut_a(rec_size < UNIV_PAGE_SIZE);
720
mlog_catenate_string(mtr, ins_ptr, rec_size);
724
/***************************************************************
725
Parses a log record of a record insert on a page. */
728
page_cur_parse_insert_rec(
729
/*======================*/
730
/* out: end of log record or NULL */
731
ibool is_short,/* in: TRUE if short inserts */
732
byte* ptr, /* in: buffer */
733
byte* end_ptr,/* in: buffer end */
734
dict_index_t* index, /* in: record descriptor */
735
page_t* page, /* in: page or NULL */
736
mtr_t* mtr) /* in: mtr or NULL */
738
ulint extra_info_yes;
739
ulint offset = 0; /* remove warning */
742
ulint mismatch_index;
747
ulint info_and_status_bits = 0; /* remove warning */
749
mem_heap_t* heap = NULL;
750
ulint offsets_[REC_OFFS_NORMAL_SIZE];
751
ulint* offsets = offsets_;
752
*offsets_ = (sizeof offsets_) / sizeof *offsets_;
755
/* Read the cursor rec offset as a 2-byte ulint */
757
if (end_ptr < ptr + 2) {
762
offset = mach_read_from_2(ptr);
764
if (offset >= UNIV_PAGE_SIZE) {
766
recv_sys->found_corrupt_log = TRUE;
774
ptr = mach_parse_compressed(ptr, end_ptr, &end_seg_len);
781
extra_info_yes = end_seg_len & 0x1UL;
784
if (end_seg_len >= UNIV_PAGE_SIZE) {
785
recv_sys->found_corrupt_log = TRUE;
790
if (extra_info_yes) {
791
/* Read the info bits */
793
if (end_ptr < ptr + 1) {
798
info_and_status_bits = mach_read_from_1(ptr);
801
ptr = mach_parse_compressed(ptr, end_ptr, &origin_offset);
808
ut_a(origin_offset < UNIV_PAGE_SIZE);
810
ptr = mach_parse_compressed(ptr, end_ptr, &mismatch_index);
817
ut_a(mismatch_index < UNIV_PAGE_SIZE);
820
if (end_ptr < ptr + end_seg_len) {
827
return(ptr + end_seg_len);
830
ut_ad(!!page_is_comp(page) == dict_table_is_comp(index->table));
832
/* Read from the log the inserted index record end segment which
833
differs from the cursor record */
836
cursor_rec = page_rec_get_prev(page_get_supremum_rec(page));
838
cursor_rec = page + offset;
841
offsets = rec_get_offsets(cursor_rec, index, offsets,
842
ULINT_UNDEFINED, &heap);
844
if (extra_info_yes == 0) {
845
info_and_status_bits = rec_get_info_and_status_bits(
846
cursor_rec, page_is_comp(page));
847
origin_offset = rec_offs_extra_size(offsets);
848
mismatch_index = rec_offs_size(offsets) - end_seg_len;
851
if (mismatch_index + end_seg_len < sizeof buf1) {
854
buf = mem_alloc(mismatch_index + end_seg_len);
857
/* Build the inserted record to buf */
859
if (mismatch_index >= UNIV_PAGE_SIZE) {
861
"Is short %lu, info_and_status_bits %lu, offset %lu, "
863
"mismatch index %lu, end_seg_len %lu\n"
865
(ulong) is_short, (ulong) info_and_status_bits,
867
(ulong) origin_offset,
868
(ulong) mismatch_index, (ulong) end_seg_len,
869
(ulong) (ptr - ptr2));
871
fputs("Dump of 300 bytes of log:\n", stderr);
872
ut_print_buf(stderr, ptr2, 300);
874
buf_page_print(page);
879
ut_memcpy(buf, rec_get_start(cursor_rec, offsets), mismatch_index);
880
ut_memcpy(buf + mismatch_index, ptr, end_seg_len);
882
rec_set_info_and_status_bits(buf + origin_offset, page_is_comp(page),
883
info_and_status_bits);
885
page_cur_position(cursor_rec, &cursor);
887
offsets = rec_get_offsets(buf + origin_offset, index, offsets,
888
ULINT_UNDEFINED, &heap);
889
page_cur_rec_insert(&cursor, buf + origin_offset, index, offsets, mtr);
896
if (UNIV_LIKELY_NULL(heap)) {
900
return(ptr + end_seg_len);
903
/***************************************************************
904
Inserts a record next to page cursor. Returns pointer to inserted record if
905
succeed, i.e., enough space available, NULL otherwise. The record to be
906
inserted can be in a data tuple or as a physical record. The other parameter
907
must then be NULL. The cursor stays at the same position. */
910
page_cur_insert_rec_low(
911
/*====================*/
912
/* out: pointer to record if succeed, NULL
914
page_cur_t* cursor, /* in: a page cursor */
915
dtuple_t* tuple, /* in: pointer to a data tuple or NULL */
916
dict_index_t* index, /* in: record descriptor */
917
rec_t* rec, /* in: pointer to a physical record or NULL */
918
ulint* offsets,/* in: rec_get_offsets(rec, index) or NULL */
919
mtr_t* mtr) /* in: mini-transaction handle */
921
byte* insert_buf = NULL;
923
byte* page; /* the relevant page */
924
rec_t* last_insert; /* cursor position at previous
926
rec_t* insert_rec; /* inserted record */
927
ulint heap_no; /* heap number of the inserted
929
rec_t* current_rec; /* current record after which the
930
new record is inserted */
931
rec_t* next_rec; /* next record after current before
933
ulint owner_slot; /* the slot which owns the
937
mem_heap_t* heap = NULL;
940
ut_ad(cursor && mtr);
942
ut_ad(!(tuple && rec));
943
ut_ad(rec || dtuple_check_typed(tuple));
945
page = page_cur_get_page(cursor);
946
comp = page_is_comp(page);
947
ut_ad(dict_table_is_comp(index->table) == !!comp);
949
ut_ad(cursor->rec != page_get_supremum_rec(page));
951
/* 1. Get the size of the physical record in the page */
953
rec_size = rec_get_converted_size(index, tuple);
956
offsets = rec_get_offsets(rec, index, offsets,
957
ULINT_UNDEFINED, &heap);
959
ut_ad(rec_offs_validate(rec, index, offsets));
960
rec_size = rec_offs_size(offsets);
963
/* 2. Try to find suitable space from page memory management */
964
insert_buf = page_mem_alloc(page, rec_size, index, &heap_no);
966
if (insert_buf == NULL) {
967
if (UNIV_LIKELY_NULL(heap)) {
973
/* 3. Create the record */
975
insert_rec = rec_convert_dtuple_to_rec(insert_buf,
977
offsets = rec_get_offsets(insert_rec, index, offsets,
978
ULINT_UNDEFINED, &heap);
980
insert_rec = rec_copy(insert_buf, rec, offsets);
981
ut_ad(rec_offs_validate(rec, index, offsets));
982
rec_offs_make_valid(insert_rec, index, offsets);
986
ut_ad(rec_size == rec_offs_size(offsets));
988
/* 4. Insert the record in the linked list of records */
989
current_rec = cursor->rec;
991
ut_ad(!comp || rec_get_status(current_rec) <= REC_STATUS_INFIMUM);
992
ut_ad(!comp || rec_get_status(insert_rec) < REC_STATUS_INFIMUM);
994
next_rec = page_rec_get_next(current_rec);
995
ut_ad(!comp || rec_get_status(next_rec) != REC_STATUS_INFIMUM);
996
page_rec_set_next(insert_rec, next_rec);
997
page_rec_set_next(current_rec, insert_rec);
999
page_header_set_field(page, PAGE_N_RECS, 1 + page_get_n_recs(page));
1001
/* 5. Set the n_owned field in the inserted record to zero,
1002
and set the heap_no field */
1004
rec_set_n_owned(insert_rec, comp, 0);
1005
rec_set_heap_no(insert_rec, comp, heap_no);
1007
/* 6. Update the last insertion info in page header */
1009
last_insert = page_header_get_ptr(page, PAGE_LAST_INSERT);
1010
ut_ad(!last_insert || !comp
1011
|| rec_get_node_ptr_flag(last_insert)
1012
== rec_get_node_ptr_flag(insert_rec));
1014
if (last_insert == NULL) {
1015
page_header_set_field(page, PAGE_DIRECTION, PAGE_NO_DIRECTION);
1016
page_header_set_field(page, PAGE_N_DIRECTION, 0);
1018
} else if ((last_insert == current_rec)
1019
&& (page_header_get_field(page, PAGE_DIRECTION)
1022
page_header_set_field(page, PAGE_DIRECTION, PAGE_RIGHT);
1023
page_header_set_field(page, PAGE_N_DIRECTION,
1024
page_header_get_field(
1025
page, PAGE_N_DIRECTION) + 1);
1027
} else if ((page_rec_get_next(insert_rec) == last_insert)
1028
&& (page_header_get_field(page, PAGE_DIRECTION)
1031
page_header_set_field(page, PAGE_DIRECTION, PAGE_LEFT);
1032
page_header_set_field(page, PAGE_N_DIRECTION,
1033
page_header_get_field(
1034
page, PAGE_N_DIRECTION) + 1);
1036
page_header_set_field(page, PAGE_DIRECTION, PAGE_NO_DIRECTION);
1037
page_header_set_field(page, PAGE_N_DIRECTION, 0);
1040
page_header_set_ptr(page, PAGE_LAST_INSERT, insert_rec);
1042
/* 7. It remains to update the owner record. */
1044
owner_rec = page_rec_find_owner_rec(insert_rec);
1045
n_owned = rec_get_n_owned(owner_rec, comp);
1046
rec_set_n_owned(owner_rec, comp, n_owned + 1);
1048
/* 8. Now we have incremented the n_owned field of the owner
1049
record. If the number exceeds PAGE_DIR_SLOT_MAX_N_OWNED,
1050
we have to split the corresponding directory slot in two. */
1052
if (n_owned == PAGE_DIR_SLOT_MAX_N_OWNED) {
1053
owner_slot = page_dir_find_owner_slot(owner_rec);
1054
page_dir_split_slot(page, owner_slot);
1057
/* 9. Write log record of the insert */
1058
page_cur_insert_rec_write_log(insert_rec, rec_size, current_rec,
1061
if (UNIV_LIKELY_NULL(heap)) {
1062
mem_heap_free(heap);
1067
/**************************************************************
1068
Writes a log record of copying a record list end to a new created page. */
1071
page_copy_rec_list_to_created_page_write_log(
1072
/*=========================================*/
1073
/* out: 4-byte field where to
1074
write the log data length */
1075
page_t* page, /* in: index page */
1076
dict_index_t* index, /* in: record descriptor */
1077
mtr_t* mtr) /* in: mtr */
1081
ut_ad(!!page_is_comp(page) == dict_table_is_comp(index->table));
1083
log_ptr = mlog_open_and_write_index(mtr, page, index,
1085
? MLOG_COMP_LIST_END_COPY_CREATED
1086
: MLOG_LIST_END_COPY_CREATED, 4);
1088
mlog_close(mtr, log_ptr + 4);
1093
/**************************************************************
1094
Parses a log record of copying a record list end to a new created page. */
1097
page_parse_copy_rec_list_to_created_page(
1098
/*=====================================*/
1099
/* out: end of log record or NULL */
1100
byte* ptr, /* in: buffer */
1101
byte* end_ptr,/* in: buffer end */
1102
dict_index_t* index, /* in: record descriptor */
1103
page_t* page, /* in: page or NULL */
1104
mtr_t* mtr) /* in: mtr or NULL */
1109
if (ptr + 4 > end_ptr) {
1114
log_data_len = mach_read_from_4(ptr);
1117
rec_end = ptr + log_data_len;
1119
if (rec_end > end_ptr) {
1129
while (ptr < rec_end) {
1130
ptr = page_cur_parse_insert_rec(TRUE, ptr, end_ptr,
1134
ut_a(ptr == rec_end);
1136
page_header_set_ptr(page, PAGE_LAST_INSERT, NULL);
1137
page_header_set_field(page, PAGE_DIRECTION, PAGE_NO_DIRECTION);
1138
page_header_set_field(page, PAGE_N_DIRECTION, 0);
1143
/*****************************************************************
1144
Copies records from page to a newly created page, from a given record onward,
1145
including that record. Infimum and supremum records are not copied. */
1148
page_copy_rec_list_end_to_created_page(
1149
/*===================================*/
1150
page_t* new_page, /* in: index page to copy to */
1151
page_t* page, /* in: index page */
1152
rec_t* rec, /* in: first record to copy */
1153
dict_index_t* index, /* in: record descriptor */
1154
mtr_t* mtr) /* in: mtr */
1156
page_dir_slot_t* slot = 0; /* remove warning */
1158
rec_t* insert_rec = 0; /* remove warning */
1167
ulint comp = page_is_comp(page);
1168
mem_heap_t* heap = NULL;
1169
ulint offsets_[REC_OFFS_NORMAL_SIZE];
1170
ulint* offsets = offsets_;
1171
*offsets_ = (sizeof offsets_) / sizeof *offsets_;
1173
ut_ad(page_dir_get_n_heap(new_page) == 2);
1174
ut_ad(page != new_page);
1175
ut_ad(comp == page_is_comp(new_page));
1177
if (rec == page_get_infimum_rec(page)) {
1179
rec = page_rec_get_next(rec);
1182
if (rec == page_get_supremum_rec(page)) {
1188
/* To pass the debug tests we have to set these dummy values
1189
in the debug version */
1190
page_dir_set_n_slots(new_page, UNIV_PAGE_SIZE / 2);
1191
page_header_set_ptr(new_page, PAGE_HEAP_TOP,
1192
new_page + UNIV_PAGE_SIZE - 1);
1195
log_ptr = page_copy_rec_list_to_created_page_write_log(new_page,
1198
log_data_len = dyn_array_get_data_size(&(mtr->log));
1200
/* Individual inserts are logged in a shorter form */
1202
log_mode = mtr_set_log_mode(mtr, MTR_LOG_SHORT_INSERTS);
1204
prev_rec = page_get_infimum_rec(new_page);
1206
heap_top = new_page + PAGE_NEW_SUPREMUM_END;
1208
heap_top = new_page + PAGE_OLD_SUPREMUM_END;
1214
/* should be do ... until, comment by Jani */
1215
while (rec != page_get_supremum_rec(page)) {
1216
offsets = rec_get_offsets(rec, index, offsets,
1217
ULINT_UNDEFINED, &heap);
1218
insert_rec = rec_copy(heap_top, rec, offsets);
1220
rec_set_next_offs(prev_rec, comp, insert_rec - new_page);
1222
rec_set_n_owned(insert_rec, comp, 0);
1223
rec_set_heap_no(insert_rec, comp, 2 + n_recs);
1225
rec_size = rec_offs_size(offsets);
1227
heap_top = heap_top + rec_size;
1229
ut_ad(heap_top < new_page + UNIV_PAGE_SIZE);
1234
if (count == (PAGE_DIR_SLOT_MAX_N_OWNED + 1) / 2) {
1238
slot = page_dir_get_nth_slot(new_page, slot_index);
1240
page_dir_slot_set_rec(slot, insert_rec);
1241
page_dir_slot_set_n_owned(slot, count);
1246
page_cur_insert_rec_write_log(insert_rec, rec_size, prev_rec,
1248
prev_rec = insert_rec;
1249
rec = page_rec_get_next(rec);
1252
if ((slot_index > 0) && (count + 1
1253
+ (PAGE_DIR_SLOT_MAX_N_OWNED + 1) / 2
1254
<= PAGE_DIR_SLOT_MAX_N_OWNED)) {
1255
/* We can merge the two last dir slots. This operation is
1256
here to make this function imitate exactly the equivalent
1257
task made using page_cur_insert_rec, which we use in database
1258
recovery to reproduce the task performed by this function.
1259
To be able to check the correctness of recovery, it is good
1260
that it imitates exactly. */
1262
count += (PAGE_DIR_SLOT_MAX_N_OWNED + 1) / 2;
1264
page_dir_slot_set_n_owned(slot, 0);
1269
if (UNIV_LIKELY_NULL(heap)) {
1270
mem_heap_free(heap);
1273
log_data_len = dyn_array_get_data_size(&(mtr->log)) - log_data_len;
1275
ut_a(log_data_len < 100 * UNIV_PAGE_SIZE);
1277
mach_write_to_4(log_ptr, log_data_len);
1279
rec_set_next_offs(insert_rec, comp,
1280
comp ? PAGE_NEW_SUPREMUM : PAGE_OLD_SUPREMUM);
1282
slot = page_dir_get_nth_slot(new_page, 1 + slot_index);
1284
page_dir_slot_set_rec(slot, page_get_supremum_rec(new_page));
1285
page_dir_slot_set_n_owned(slot, count + 1);
1287
page_dir_set_n_slots(new_page, 2 + slot_index);
1288
page_header_set_ptr(new_page, PAGE_HEAP_TOP, heap_top);
1289
page_dir_set_n_heap(new_page, 2 + n_recs);
1290
page_header_set_field(new_page, PAGE_N_RECS, n_recs);
1292
page_header_set_ptr(new_page, PAGE_LAST_INSERT, NULL);
1293
page_header_set_field(new_page, PAGE_DIRECTION, PAGE_NO_DIRECTION);
1294
page_header_set_field(new_page, PAGE_N_DIRECTION, 0);
1296
/* Restore the log mode */
1298
mtr_set_log_mode(mtr, log_mode);
1301
/***************************************************************
1302
Writes log record of a record delete on a page. */
1305
page_cur_delete_rec_write_log(
1306
/*==========================*/
1307
rec_t* rec, /* in: record to be deleted */
1308
dict_index_t* index, /* in: record descriptor */
1309
mtr_t* mtr) /* in: mini-transaction handle */
1313
ut_ad(!!page_rec_is_comp(rec) == dict_table_is_comp(index->table));
1315
log_ptr = mlog_open_and_write_index(mtr, rec, index,
1316
page_rec_is_comp(rec)
1317
? MLOG_COMP_REC_DELETE
1318
: MLOG_REC_DELETE, 2);
1321
/* Logging in mtr is switched off during crash recovery:
1322
in that case mlog_open returns NULL */
1326
/* Write the cursor rec offset as a 2-byte ulint */
1327
mach_write_to_2(log_ptr, page_offset(rec));
1329
mlog_close(mtr, log_ptr + 2);
1332
/***************************************************************
1333
Parses log record of a record delete on a page. */
1336
page_cur_parse_delete_rec(
1337
/*======================*/
1338
/* out: pointer to record end or NULL */
1339
byte* ptr, /* in: buffer */
1340
byte* end_ptr,/* in: buffer end */
1341
dict_index_t* index, /* in: record descriptor */
1342
page_t* page, /* in: page or NULL */
1343
mtr_t* mtr) /* in: mtr or NULL */
1348
if (end_ptr < ptr + 2) {
1353
/* Read the cursor rec offset as a 2-byte ulint */
1354
offset = mach_read_from_2(ptr);
1357
ut_a(offset <= UNIV_PAGE_SIZE);
1360
mem_heap_t* heap = NULL;
1361
ulint offsets_[REC_OFFS_NORMAL_SIZE];
1362
rec_t* rec = page + offset;
1363
*offsets_ = (sizeof offsets_) / sizeof *offsets_;
1365
page_cur_position(rec, &cursor);
1367
page_cur_delete_rec(&cursor, index,
1368
rec_get_offsets(rec, index, offsets_,
1369
ULINT_UNDEFINED, &heap),
1371
if (UNIV_LIKELY_NULL(heap)) {
1372
mem_heap_free(heap);
1379
/***************************************************************
1380
Deletes a record at the page cursor. The cursor is moved to the next
1381
record after the deleted one. */
1384
page_cur_delete_rec(
1385
/*================*/
1386
page_cur_t* cursor, /* in: a page cursor */
1387
dict_index_t* index, /* in: record descriptor */
1388
const ulint* offsets,/* in: rec_get_offsets(cursor->rec, index) */
1389
mtr_t* mtr) /* in: mini-transaction handle */
1391
page_dir_slot_t* cur_dir_slot;
1392
page_dir_slot_t* prev_slot;
1395
rec_t* prev_rec = NULL;
1401
ut_ad(cursor && mtr);
1403
page = page_cur_get_page(cursor);
1404
current_rec = cursor->rec;
1405
ut_ad(rec_offs_validate(current_rec, index, offsets));
1406
ut_ad(!!page_is_comp(page) == dict_table_is_comp(index->table));
1408
/* The record must not be the supremum or infimum record. */
1409
ut_ad(current_rec != page_get_supremum_rec(page));
1410
ut_ad(current_rec != page_get_infimum_rec(page));
1412
/* Save to local variables some data associated with current_rec */
1413
cur_slot_no = page_dir_find_owner_slot(current_rec);
1414
cur_dir_slot = page_dir_get_nth_slot(page, cur_slot_no);
1415
cur_n_owned = page_dir_slot_get_n_owned(cur_dir_slot);
1417
/* 0. Write the log record */
1418
page_cur_delete_rec_write_log(current_rec, index, mtr);
1420
/* 1. Reset the last insert info in the page header and increment
1421
the modify clock for the frame */
1423
page_header_set_ptr(page, PAGE_LAST_INSERT, NULL);
1425
/* The page gets invalid for optimistic searches: increment the
1426
frame modify clock */
1428
buf_frame_modify_clock_inc(page);
1430
/* 2. Find the next and the previous record. Note that the cursor is
1431
left at the next record. */
1433
ut_ad(cur_slot_no > 0);
1434
prev_slot = page_dir_get_nth_slot(page, cur_slot_no - 1);
1436
rec = page_dir_slot_get_rec(prev_slot);
1438
/* rec now points to the record of the previous directory slot. Look
1439
for the immediate predecessor of current_rec in a loop. */
1441
while(current_rec != rec) {
1443
rec = page_rec_get_next(rec);
1446
page_cur_move_to_next(cursor);
1447
next_rec = cursor->rec;
1449
/* 3. Remove the record from the linked list of records */
1451
page_rec_set_next(prev_rec, next_rec);
1452
page_header_set_field(page, PAGE_N_RECS,
1453
(ulint)(page_get_n_recs(page) - 1));
1455
/* 4. If the deleted record is pointed to by a dir slot, update the
1456
record pointer in slot. In the following if-clause we assume that
1457
prev_rec is owned by the same slot, i.e., PAGE_DIR_SLOT_MIN_N_OWNED
1460
#if PAGE_DIR_SLOT_MIN_N_OWNED < 2
1461
# error "PAGE_DIR_SLOT_MIN_N_OWNED < 2"
1463
ut_ad(cur_n_owned > 1);
1465
if (current_rec == page_dir_slot_get_rec(cur_dir_slot)) {
1466
page_dir_slot_set_rec(cur_dir_slot, prev_rec);
1469
/* 5. Update the number of owned records of the slot */
1471
page_dir_slot_set_n_owned(cur_dir_slot, cur_n_owned - 1);
1473
/* 6. Free the memory occupied by the record */
1474
page_mem_free(page, current_rec, offsets);
1476
/* 7. Now we have decremented the number of owned records of the slot.
1477
If the number drops below PAGE_DIR_SLOT_MIN_N_OWNED, we balance the
1480
if (cur_n_owned <= PAGE_DIR_SLOT_MIN_N_OWNED) {
1481
page_dir_balance_slot(page, cur_slot_no);
1485
#ifdef UNIV_COMPILE_TEST_FUNCS
1487
/***********************************************************************
1488
Print the first n numbers, generated by page_cur_lcg_prng() to make sure
1489
(visually) that it works properly. */
1491
test_page_cur_lcg_prng(
1492
/*===================*/
1493
int n) /* in: print first n numbers */
1496
unsigned long long rnd;
1498
for (i = 0; i < n; i++) {
1499
rnd = page_cur_lcg_prng();
1500
printf("%llu\t%%2=%llu %%3=%llu %%5=%llu %%7=%llu %%11=%llu\n",
1510
#endif /* UNIV_COMPILE_TEST_FUNCS */
added
removed
storage/innobase/page/page0cur.c
