← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

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

  • Committer: brian
  • Date: 2008-06-25 05:29:13 UTC
  • Revision ID: brian@localhost.localdomain-20080625052913-6upwo0jsrl4lnapl
clean slate

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