| 508 | |
| 509 | #if !defined(TORQUE_DISABLE_MEMORY_MANAGER) |
| 510 | static void treeInsert(FreeHeader *fhdr) |
| 511 | { |
| 512 | #ifdef TORQUE_DEBUG_GUARD |
| 513 | checkGuard((Header *) fhdr, true); // check to see that it's got allocated guards |
| 514 | setGuard((Header *) fhdr, false); |
| 515 | #endif |
| 516 | //gInsertCount++; |
| 517 | |
| 518 | TreeNode *newParent = NIL; |
| 519 | TreeNode *walk = gFreeTreeRoot; |
| 520 | while(walk != NIL) |
| 521 | { |
| 522 | newParent = walk; |
| 523 | if(fhdr->size < walk->size) |
| 524 | walk = walk->left; |
| 525 | else if(fhdr->size > walk->size) |
| 526 | walk = walk->right; |
| 527 | else // tag it on the end of the queue... |
| 528 | { |
| 529 | // insert it on this header... |
| 530 | walk->queueTail->nextQueue = fhdr; |
| 531 | fhdr->prevQueue = walk->queueTail; |
| 532 | walk->queueTail = fhdr; |
| 533 | fhdr->nextQueue = NULL; |
| 534 | fhdr->treeNode = walk; |
| 535 | return; |
| 536 | } |
| 537 | } |
| 538 | TreeNode *hdr = allocTreeNode(); |
| 539 | hdr->size = fhdr->size; |
| 540 | hdr->queueHead = hdr->queueTail = fhdr; |
| 541 | fhdr->nextQueue = fhdr->prevQueue = NULL; |
| 542 | fhdr->treeNode = hdr; |
| 543 | |
| 544 | hdr->left = NIL; |
| 545 | hdr->right = NIL; |
| 546 | |
| 547 | hdr->parent = newParent; |
| 548 | |
| 549 | if(newParent == NIL) |
| 550 | gFreeTreeRoot = hdr; |
| 551 | else if(hdr->size < newParent->size) |
| 552 | newParent->left = hdr; |
| 553 | else |
| 554 | newParent->right = hdr; |
| 555 | |
| 556 | // do red/black rotations |
| 557 | hdr->color = Red; |
| 558 | while(hdr != gFreeTreeRoot && (hdr->parent->color == Red)) |
| 559 | { |
| 560 | TreeNode *parent = hdr->parent; |
| 561 | TreeNode *pparent = hdr->parent->parent; |
| 562 | |
| 563 | if(parent == pparent->left) |
| 564 | { |
| 565 | TreeNode *temp = pparent->right; |
| 566 | if(temp->color == Red) |
| 567 | { |
no test coverage detected