allocate a large request from the best fitting chunk in a treebin */
| 4518 | |
| 4519 | /* allocate a large request from the best fitting chunk in a treebin */ |
| 4520 | static void* tmalloc_large(mstate m, size_t nb) { |
| 4521 | tchunkptr v = 0; |
| 4522 | size_t rsize = -nb; /* Unsigned negation */ |
| 4523 | tchunkptr t; |
| 4524 | bindex_t idx; |
| 4525 | compute_tree_index(nb, idx); |
| 4526 | if ((t = *treebin_at(m, idx)) != 0) { |
| 4527 | /* Traverse tree for this bin looking for node with size == nb */ |
| 4528 | size_t sizebits = nb << leftshift_for_tree_index(idx); |
| 4529 | tchunkptr rst = 0; /* The deepest untaken right subtree */ |
| 4530 | for (;;) { |
| 4531 | tchunkptr rt; |
| 4532 | size_t trem = chunksize(t) - nb; |
| 4533 | if (trem < rsize) { |
| 4534 | v = t; |
| 4535 | if ((rsize = trem) == 0) |
| 4536 | break; |
| 4537 | } |
| 4538 | rt = t->child[1]; |
| 4539 | t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1]; |
| 4540 | if (rt != 0 && rt != t) |
| 4541 | rst = rt; |
| 4542 | if (t == 0) { |
| 4543 | t = rst; /* set t to least subtree holding sizes > nb */ |
| 4544 | break; |
| 4545 | } |
| 4546 | sizebits <<= 1; |
| 4547 | } |
| 4548 | } |
| 4549 | if (t == 0 && v == 0) { /* set t to root of next non-empty treebin */ |
| 4550 | binmap_t leftbits = left_bits(idx2bit(idx)) & m->treemap; |
| 4551 | if (leftbits != 0) { |
| 4552 | bindex_t i; |
| 4553 | binmap_t leastbit = least_bit(leftbits); |
| 4554 | compute_bit2idx(leastbit, i); |
| 4555 | t = *treebin_at(m, i); |
| 4556 | } |
| 4557 | } |
| 4558 | |
| 4559 | while (t != 0) { /* find smallest of tree or subtree */ |
| 4560 | size_t trem = chunksize(t) - nb; |
| 4561 | if (trem < rsize) { |
| 4562 | rsize = trem; |
| 4563 | v = t; |
| 4564 | } |
| 4565 | t = leftmost_child(t); |
| 4566 | } |
| 4567 | |
| 4568 | /* If dv is a better fit, return 0 so malloc will use it */ |
| 4569 | if (v != 0 && rsize < (size_t)(m->dvsize - nb)) { |
| 4570 | if (RTCHECK(ok_address(m, v))) { /* split */ |
| 4571 | mchunkptr r = chunk_plus_offset(v, nb); |
| 4572 | assert(chunksize(v) == rsize + nb); |
| 4573 | if (RTCHECK(ok_next(v, r))) { |
| 4574 | unlink_large_chunk(m, v); |
| 4575 | if (rsize < MIN_CHUNK_SIZE) |
| 4576 | set_inuse_and_pinuse(m, v, (rsize + nb)); |
| 4577 | else { |
no test coverage detected