← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to storage/innobase/fut/fut0lst.c

Tags: innodb-plugin-1.0.1
Imported 1.0.1 with clean - with no changes.

Show diffs side-by-side

added added

removed removed

Lines of Context:
storage/innobase/fut/fut0lst.c
 
1
/**********************************************************************
 
2
File-based list utilities
 
3
 
 
4
(c) 1995 Innobase Oy
 
5
 
 
6
Created 11/28/1995 Heikki Tuuri
 
7
***********************************************************************/
 
8
 
 
9
#include "fut0lst.h"
 
10
 
 
11
#ifdef UNIV_NONINL
 
12
#include "fut0lst.ic"
 
13
#endif
 
14
 
 
15
#include "buf0buf.h"
 
16
#include "page0page.h"
 
17
 
 
18
/************************************************************************
 
19
Adds a node to an empty list. */
 
20
static
 
21
void
 
22
flst_add_to_empty(
 
23
/*==============*/
 
24
        flst_base_node_t*       base,   /* in: pointer to base node of
 
25
                                        empty list */
 
26
        flst_node_t*            node,   /* in: node to add */
 
27
        mtr_t*                  mtr)    /* in: mini-transaction handle */
 
28
{
 
29
        ulint           space;
 
30
        fil_addr_t      node_addr;
 
31
        ulint           len;
 
32
 
 
33
        ut_ad(mtr && base && node);
 
34
        ut_ad(base != node);
 
35
        ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
 
36
        ut_ad(mtr_memo_contains_page(mtr, node, MTR_MEMO_PAGE_X_FIX));
 
37
        len = flst_get_len(base, mtr);
 
38
        ut_a(len == 0);
 
39
 
 
40
        buf_ptr_get_fsp_addr(node, &space, &node_addr);
 
41
 
 
42
        /* Update first and last fields of base node */
 
43
        flst_write_addr(base + FLST_FIRST, node_addr, mtr);
 
44
        flst_write_addr(base + FLST_LAST, node_addr, mtr);
 
45
 
 
46
        /* Set prev and next fields of node to add */
 
47
        flst_write_addr(node + FLST_PREV, fil_addr_null, mtr);
 
48
        flst_write_addr(node + FLST_NEXT, fil_addr_null, mtr);
 
49
 
 
50
        /* Update len of base node */
 
51
        mlog_write_ulint(base + FLST_LEN, len + 1, MLOG_4BYTES, mtr);
 
52
}
 
53
 
 
54
/************************************************************************
 
55
Adds a node as the last node in a list. */
 
56
UNIV_INTERN
 
57
void
 
58
flst_add_last(
 
59
/*==========*/
 
60
        flst_base_node_t*       base,   /* in: pointer to base node of list */
 
61
        flst_node_t*            node,   /* in: node to add */
 
62
        mtr_t*                  mtr)    /* in: mini-transaction handle */
 
63
{
 
64
        ulint           space;
 
65
        fil_addr_t      node_addr;
 
66
        ulint           len;
 
67
        fil_addr_t      last_addr;
 
68
        flst_node_t*    last_node;
 
69
 
 
70
        ut_ad(mtr && base && node);
 
71
        ut_ad(base != node);
 
72
        ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
 
73
        ut_ad(mtr_memo_contains_page(mtr, node, MTR_MEMO_PAGE_X_FIX));
 
74
        len = flst_get_len(base, mtr);
 
75
        last_addr = flst_get_last(base, mtr);
 
76
 
 
77
        buf_ptr_get_fsp_addr(node, &space, &node_addr);
 
78
 
 
79
        /* If the list is not empty, call flst_insert_after */
 
80
        if (len != 0) {
 
81
                if (last_addr.page == node_addr.page) {
 
82
                        last_node = page_align(node) + last_addr.boffset;
 
83
                } else {
 
84
                        ulint   zip_size = fil_space_get_zip_size(space);
 
85
 
 
86
                        last_node = fut_get_ptr(space, zip_size, last_addr,
 
87
                                                RW_X_LATCH, mtr);
 
88
                }
 
89
 
 
90
                flst_insert_after(base, last_node, node, mtr);
 
91
        } else {
 
92
                /* else call flst_add_to_empty */
 
93
                flst_add_to_empty(base, node, mtr);
 
94
        }
 
95
}
 
96
 
 
97
/************************************************************************
 
98
Adds a node as the first node in a list. */
 
99
UNIV_INTERN
 
100
void
 
101
flst_add_first(
 
102
/*===========*/
 
103
        flst_base_node_t*       base,   /* in: pointer to base node of list */
 
104
        flst_node_t*            node,   /* in: node to add */
 
105
        mtr_t*                  mtr)    /* in: mini-transaction handle */
 
106
{
 
107
        ulint           space;
 
108
        fil_addr_t      node_addr;
 
109
        ulint           len;
 
110
        fil_addr_t      first_addr;
 
111
        flst_node_t*    first_node;
 
112
 
 
113
        ut_ad(mtr && base && node);
 
114
        ut_ad(base != node);
 
115
        ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
 
116
        ut_ad(mtr_memo_contains_page(mtr, node, MTR_MEMO_PAGE_X_FIX));
 
117
        len = flst_get_len(base, mtr);
 
118
        first_addr = flst_get_first(base, mtr);
 
119
 
 
120
        buf_ptr_get_fsp_addr(node, &space, &node_addr);
 
121
 
 
122
        /* If the list is not empty, call flst_insert_before */
 
123
        if (len != 0) {
 
124
                if (first_addr.page == node_addr.page) {
 
125
                        first_node = page_align(node) + first_addr.boffset;
 
126
                } else {
 
127
                        ulint   zip_size = fil_space_get_zip_size(space);
 
128
 
 
129
                        first_node = fut_get_ptr(space, zip_size, first_addr,
 
130
                                                 RW_X_LATCH, mtr);
 
131
                }
 
132
 
 
133
                flst_insert_before(base, node, first_node, mtr);
 
134
        } else {
 
135
                /* else call flst_add_to_empty */
 
136
                flst_add_to_empty(base, node, mtr);
 
137
        }
 
138
}
 
139
 
 
140
/************************************************************************
 
141
Inserts a node after another in a list. */
 
142
UNIV_INTERN
 
143
void
 
144
flst_insert_after(
 
145
/*==============*/
 
146
        flst_base_node_t*       base,   /* in: pointer to base node of list */
 
147
        flst_node_t*            node1,  /* in: node to insert after */
 
148
        flst_node_t*            node2,  /* in: node to add */
 
149
        mtr_t*                  mtr)    /* in: mini-transaction handle */
 
150
{
 
151
        ulint           space;
 
152
        fil_addr_t      node1_addr;
 
153
        fil_addr_t      node2_addr;
 
154
        flst_node_t*    node3;
 
155
        fil_addr_t      node3_addr;
 
156
        ulint           len;
 
157
 
 
158
        ut_ad(mtr && node1 && node2 && base);
 
159
        ut_ad(base != node1);
 
160
        ut_ad(base != node2);
 
161
        ut_ad(node2 != node1);
 
162
        ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
 
163
        ut_ad(mtr_memo_contains_page(mtr, node1, MTR_MEMO_PAGE_X_FIX));
 
164
        ut_ad(mtr_memo_contains_page(mtr, node2, MTR_MEMO_PAGE_X_FIX));
 
165
 
 
166
        buf_ptr_get_fsp_addr(node1, &space, &node1_addr);
 
167
        buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
 
168
 
 
169
        node3_addr = flst_get_next_addr(node1, mtr);
 
170
 
 
171
        /* Set prev and next fields of node2 */
 
172
        flst_write_addr(node2 + FLST_PREV, node1_addr, mtr);
 
173
        flst_write_addr(node2 + FLST_NEXT, node3_addr, mtr);
 
174
 
 
175
        if (!fil_addr_is_null(node3_addr)) {
 
176
                /* Update prev field of node3 */
 
177
                ulint   zip_size = fil_space_get_zip_size(space);
 
178
 
 
179
                node3 = fut_get_ptr(space, zip_size,
 
180
                                    node3_addr, RW_X_LATCH, mtr);
 
181
                flst_write_addr(node3 + FLST_PREV, node2_addr, mtr);
 
182
        } else {
 
183
                /* node1 was last in list: update last field in base */
 
184
                flst_write_addr(base + FLST_LAST, node2_addr, mtr);
 
185
        }
 
186
 
 
187
        /* Set next field of node1 */
 
188
        flst_write_addr(node1 + FLST_NEXT, node2_addr, mtr);
 
189
 
 
190
        /* Update len of base node */
 
191
        len = flst_get_len(base, mtr);
 
192
        mlog_write_ulint(base + FLST_LEN, len + 1, MLOG_4BYTES, mtr);
 
193
}
 
194
 
 
195
/************************************************************************
 
196
Inserts a node before another in a list. */
 
197
UNIV_INTERN
 
198
void
 
199
flst_insert_before(
 
200
/*===============*/
 
201
        flst_base_node_t*       base,   /* in: pointer to base node of list */
 
202
        flst_node_t*            node2,  /* in: node to insert */
 
203
        flst_node_t*            node3,  /* in: node to insert before */
 
204
        mtr_t*                  mtr)    /* in: mini-transaction handle */
 
205
{
 
206
        ulint           space;
 
207
        flst_node_t*    node1;
 
208
        fil_addr_t      node1_addr;
 
209
        fil_addr_t      node2_addr;
 
210
        fil_addr_t      node3_addr;
 
211
        ulint           len;
 
212
 
 
213
        ut_ad(mtr && node2 && node3 && base);
 
214
        ut_ad(base != node2);
 
215
        ut_ad(base != node3);
 
216
        ut_ad(node2 != node3);
 
217
        ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
 
218
        ut_ad(mtr_memo_contains_page(mtr, node2, MTR_MEMO_PAGE_X_FIX));
 
219
        ut_ad(mtr_memo_contains_page(mtr, node3, MTR_MEMO_PAGE_X_FIX));
 
220
 
 
221
        buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
 
222
        buf_ptr_get_fsp_addr(node3, &space, &node3_addr);
 
223
 
 
224
        node1_addr = flst_get_prev_addr(node3, mtr);
 
225
 
 
226
        /* Set prev and next fields of node2 */
 
227
        flst_write_addr(node2 + FLST_PREV, node1_addr, mtr);
 
228
        flst_write_addr(node2 + FLST_NEXT, node3_addr, mtr);
 
229
 
 
230
        if (!fil_addr_is_null(node1_addr)) {
 
231
                ulint   zip_size = fil_space_get_zip_size(space);
 
232
                /* Update next field of node1 */
 
233
                node1 = fut_get_ptr(space, zip_size, node1_addr,
 
234
                                    RW_X_LATCH, mtr);
 
235
                flst_write_addr(node1 + FLST_NEXT, node2_addr, mtr);
 
236
        } else {
 
237
                /* node3 was first in list: update first field in base */
 
238
                flst_write_addr(base + FLST_FIRST, node2_addr, mtr);
 
239
        }
 
240
 
 
241
        /* Set prev field of node3 */
 
242
        flst_write_addr(node3 + FLST_PREV, node2_addr, mtr);
 
243
 
 
244
        /* Update len of base node */
 
245
        len = flst_get_len(base, mtr);
 
246
        mlog_write_ulint(base + FLST_LEN, len + 1, MLOG_4BYTES, mtr);
 
247
}
 
248
 
 
249
/************************************************************************
 
250
Removes a node. */
 
251
UNIV_INTERN
 
252
void
 
253
flst_remove(
 
254
/*========*/
 
255
        flst_base_node_t*       base,   /* in: pointer to base node of list */
 
256
        flst_node_t*            node2,  /* in: node to remove */
 
257
        mtr_t*                  mtr)    /* in: mini-transaction handle */
 
258
{
 
259
        ulint           space;
 
260
        ulint           zip_size;
 
261
        flst_node_t*    node1;
 
262
        fil_addr_t      node1_addr;
 
263
        fil_addr_t      node2_addr;
 
264
        flst_node_t*    node3;
 
265
        fil_addr_t      node3_addr;
 
266
        ulint           len;
 
267
 
 
268
        ut_ad(mtr && node2 && base);
 
269
        ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
 
270
        ut_ad(mtr_memo_contains_page(mtr, node2, MTR_MEMO_PAGE_X_FIX));
 
271
 
 
272
        buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
 
273
        zip_size = fil_space_get_zip_size(space);
 
274
 
 
275
        node1_addr = flst_get_prev_addr(node2, mtr);
 
276
        node3_addr = flst_get_next_addr(node2, mtr);
 
277
 
 
278
        if (!fil_addr_is_null(node1_addr)) {
 
279
 
 
280
                /* Update next field of node1 */
 
281
 
 
282
                if (node1_addr.page == node2_addr.page) {
 
283
 
 
284
                        node1 = page_align(node2) + node1_addr.boffset;
 
285
                } else {
 
286
                        node1 = fut_get_ptr(space, zip_size,
 
287
                                            node1_addr, RW_X_LATCH, mtr);
 
288
                }
 
289
 
 
290
                ut_ad(node1 != node2);
 
291
 
 
292
                flst_write_addr(node1 + FLST_NEXT, node3_addr, mtr);
 
293
        } else {
 
294
                /* node2 was first in list: update first field in base */
 
295
                flst_write_addr(base + FLST_FIRST, node3_addr, mtr);
 
296
        }
 
297
 
 
298
        if (!fil_addr_is_null(node3_addr)) {
 
299
                /* Update prev field of node3 */
 
300
 
 
301
                if (node3_addr.page == node2_addr.page) {
 
302
 
 
303
                        node3 = page_align(node2) + node3_addr.boffset;
 
304
                } else {
 
305
                        node3 = fut_get_ptr(space, zip_size,
 
306
                                            node3_addr, RW_X_LATCH, mtr);
 
307
                }
 
308
 
 
309
                ut_ad(node2 != node3);
 
310
 
 
311
                flst_write_addr(node3 + FLST_PREV, node1_addr, mtr);
 
312
        } else {
 
313
                /* node2 was last in list: update last field in base */
 
314
                flst_write_addr(base + FLST_LAST, node1_addr, mtr);
 
315
        }
 
316
 
 
317
        /* Update len of base node */
 
318
        len = flst_get_len(base, mtr);
 
319
        ut_ad(len > 0);
 
320
 
 
321
        mlog_write_ulint(base + FLST_LEN, len - 1, MLOG_4BYTES, mtr);
 
322
}
 
323
 
 
324
/************************************************************************
 
325
Cuts off the tail of the list, including the node given. The number of
 
326
nodes which will be removed must be provided by the caller, as this function
 
327
does not measure the length of the tail. */
 
328
UNIV_INTERN
 
329
void
 
330
flst_cut_end(
 
331
/*=========*/
 
332
        flst_base_node_t*       base,   /* in: pointer to base node of list */
 
333
        flst_node_t*            node2,  /* in: first node to remove */
 
334
        ulint                   n_nodes,/* in: number of nodes to remove,
 
335
                                        must be >= 1 */
 
336
        mtr_t*                  mtr)    /* in: mini-transaction handle */
 
337
{
 
338
        ulint           space;
 
339
        flst_node_t*    node1;
 
340
        fil_addr_t      node1_addr;
 
341
        fil_addr_t      node2_addr;
 
342
        ulint           len;
 
343
 
 
344
        ut_ad(mtr && node2 && base);
 
345
        ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
 
346
        ut_ad(mtr_memo_contains_page(mtr, node2, MTR_MEMO_PAGE_X_FIX));
 
347
        ut_ad(n_nodes > 0);
 
348
 
 
349
        buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
 
350
 
 
351
        node1_addr = flst_get_prev_addr(node2, mtr);
 
352
 
 
353
        if (!fil_addr_is_null(node1_addr)) {
 
354
 
 
355
                /* Update next field of node1 */
 
356
 
 
357
                if (node1_addr.page == node2_addr.page) {
 
358
 
 
359
                        node1 = page_align(node2) + node1_addr.boffset;
 
360
                } else {
 
361
                        node1 = fut_get_ptr(space,
 
362
                                            fil_space_get_zip_size(space),
 
363
                                            node1_addr, RW_X_LATCH, mtr);
 
364
                }
 
365
 
 
366
                flst_write_addr(node1 + FLST_NEXT, fil_addr_null, mtr);
 
367
        } else {
 
368
                /* node2 was first in list: update the field in base */
 
369
                flst_write_addr(base + FLST_FIRST, fil_addr_null, mtr);
 
370
        }
 
371
 
 
372
        flst_write_addr(base + FLST_LAST, node1_addr, mtr);
 
373
 
 
374
        /* Update len of base node */
 
375
        len = flst_get_len(base, mtr);
 
376
        ut_ad(len >= n_nodes);
 
377
 
 
378
        mlog_write_ulint(base + FLST_LEN, len - n_nodes, MLOG_4BYTES, mtr);
 
379
}
 
380
 
 
381
/************************************************************************
 
382
Cuts off the tail of the list, not including the given node. The number of
 
383
nodes which will be removed must be provided by the caller, as this function
 
384
does not measure the length of the tail. */
 
385
UNIV_INTERN
 
386
void
 
387
flst_truncate_end(
 
388
/*==============*/
 
389
        flst_base_node_t*       base,   /* in: pointer to base node of list */
 
390
        flst_node_t*            node2,  /* in: first node not to remove */
 
391
        ulint                   n_nodes,/* in: number of nodes to remove */
 
392
        mtr_t*                  mtr)    /* in: mini-transaction handle */
 
393
{
 
394
        fil_addr_t      node2_addr;
 
395
        ulint           len;
 
396
        ulint           space;
 
397
 
 
398
        ut_ad(mtr && node2 && base);
 
399
        ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
 
400
        ut_ad(mtr_memo_contains_page(mtr, node2, MTR_MEMO_PAGE_X_FIX));
 
401
        if (n_nodes == 0) {
 
402
 
 
403
                ut_ad(fil_addr_is_null(flst_get_next_addr(node2, mtr)));
 
404
 
 
405
                return;
 
406
        }
 
407
 
 
408
        buf_ptr_get_fsp_addr(node2, &space, &node2_addr);
 
409
 
 
410
        /* Update next field of node2 */
 
411
        flst_write_addr(node2 + FLST_NEXT, fil_addr_null, mtr);
 
412
 
 
413
        flst_write_addr(base + FLST_LAST, node2_addr, mtr);
 
414
 
 
415
        /* Update len of base node */
 
416
        len = flst_get_len(base, mtr);
 
417
        ut_ad(len >= n_nodes);
 
418
 
 
419
        mlog_write_ulint(base + FLST_LEN, len - n_nodes, MLOG_4BYTES, mtr);
 
420
}
 
421
 
 
422
/************************************************************************
 
423
Validates a file-based list. */
 
424
UNIV_INTERN
 
425
ibool
 
426
flst_validate(
 
427
/*==========*/
 
428
                                        /* out: TRUE if ok */
 
429
        const flst_base_node_t* base,   /* in: pointer to base node of list */
 
430
        mtr_t*                  mtr1)   /* in: mtr */
 
431
{
 
432
        ulint                   space;
 
433
        ulint                   zip_size;
 
434
        const flst_node_t*      node;
 
435
        fil_addr_t              node_addr;
 
436
        fil_addr_t              base_addr;
 
437
        ulint                   len;
 
438
        ulint                   i;
 
439
        mtr_t                   mtr2;
 
440
 
 
441
        ut_ad(base);
 
442
        ut_ad(mtr_memo_contains_page(mtr1, base, MTR_MEMO_PAGE_X_FIX));
 
443
 
 
444
        /* We use two mini-transaction handles: the first is used to
 
445
        lock the base node, and prevent other threads from modifying the
 
446
        list. The second is used to traverse the list. We cannot run the
 
447
        second mtr without committing it at times, because if the list
 
448
        is long, then the x-locked pages could fill the buffer resulting
 
449
        in a deadlock. */
 
450
 
 
451
        /* Find out the space id */
 
452
        buf_ptr_get_fsp_addr(base, &space, &base_addr);
 
453
        zip_size = fil_space_get_zip_size(space);
 
454
 
 
455
        len = flst_get_len(base, mtr1);
 
456
        node_addr = flst_get_first(base, mtr1);
 
457
 
 
458
        for (i = 0; i < len; i++) {
 
459
                mtr_start(&mtr2);
 
460
 
 
461
                node = fut_get_ptr(space, zip_size,
 
462
                                   node_addr, RW_X_LATCH, &mtr2);
 
463
                node_addr = flst_get_next_addr(node, &mtr2);
 
464
 
 
465
                mtr_commit(&mtr2); /* Commit mtr2 each round to prevent buffer
 
466
                                   becoming full */
 
467
        }
 
468
 
 
469
        ut_a(fil_addr_is_null(node_addr));
 
470
 
 
471
        node_addr = flst_get_last(base, mtr1);
 
472
 
 
473
        for (i = 0; i < len; i++) {
 
474
                mtr_start(&mtr2);
 
475
 
 
476
                node = fut_get_ptr(space, zip_size,
 
477
                                   node_addr, RW_X_LATCH, &mtr2);
 
478
                node_addr = flst_get_prev_addr(node, &mtr2);
 
479
 
 
480
                mtr_commit(&mtr2); /* Commit mtr2 each round to prevent buffer
 
481
                                   becoming full */
 
482
        }
 
483
 
 
484
        ut_a(fil_addr_is_null(node_addr));
 
485
 
 
486
        return(TRUE);
 
487
}
 
488
 
 
489
/************************************************************************
 
490
Prints info of a file-based list. */
 
491
UNIV_INTERN
 
492
void
 
493
flst_print(
 
494
/*=======*/
 
495
        const flst_base_node_t* base,   /* in: pointer to base node of list */
 
496
        mtr_t*                  mtr)    /* in: mtr */
 
497
{
 
498
        const buf_frame_t*      frame;
 
499
        ulint                   len;
 
500
 
 
501
        ut_ad(base && mtr);
 
502
        ut_ad(mtr_memo_contains_page(mtr, base, MTR_MEMO_PAGE_X_FIX));
 
503
        frame = page_align((byte*) base);
 
504
 
 
505
        len = flst_get_len(base, mtr);
 
506
 
 
507
        fprintf(stderr,
 
508
                "FILE-BASED LIST:\n"
 
509
                "Base node in space %lu page %lu byte offset %lu; len %lu\n",
 
510
                (ulong) page_get_space_id(frame),
 
511
                (ulong) page_get_page_no(frame),
 
512
                (ulong) page_offset(base), (ulong) len);
 
513
}