1/* 2 * IOFireWireLibCoalesceTree.cpp 3 * IOFireWireFamily 4 * 5 * Created by Niels on Fri Mar 14 2003. 6 * Copyright (c) 2003 Apple Computer, Inc. All rights reserved. 7 * 8 * $ Log:IOFireWireLibCoalesceTree.cpp,v $ 9 */ 10 11#import "IOFireWireLibCoalesceTree.h" 12#import "IOFireWireLibPriv.h" 13 14#import <unistd.h> 15 16namespace IOFireWireLib { 17 18 // ============================================================ 19 // CoalesceTree 20 // ============================================================ 21 22 CoalesceTree::CoalesceTree() 23 { 24 mTop = nil ; 25 } 26 27 CoalesceTree::~CoalesceTree() 28 { 29 DeleteNode(mTop) ; 30 } 31 32 void 33 CoalesceTree::DeleteNode(Node* inNode) 34 { 35 if (inNode) 36 { 37 DeleteNode(inNode->left) ; 38 DeleteNode(inNode->right) ; 39 delete inNode ; 40 } 41 } 42 43 void 44 CoalesceTree::CoalesceRange(const IOVirtualRange& inRange) 45 { 46 if ( inRange.address == 0 or inRange.length == 0) 47 return ; 48 49 // ranges must be page aligned and have lengths in multiples of the vm page size only: 50 IOVirtualRange range = { trunc_page(inRange.address), round_page( (inRange.address & getpagesize() - 1) + inRange.length - 1) } ; 51 52 if (mTop) 53 CoalesceRange(range, mTop) ; 54 else 55 { 56 mTop = new Node ; 57 mTop->left = nil ; 58 mTop->right = nil ; 59 mTop->range.address = range.address ; 60 mTop->range.length = range.length ; 61 } 62 } 63 64 void 65 CoalesceTree::CoalesceRange(const IOVirtualRange& inRange, Node* inNode) 66 { 67 if (inRange.address > inNode->range.address) 68 { 69 if ( (inRange.address - inNode->range.address) <= inNode->range.length) 70 { 71 // merge 72 inNode->range.length = MAX( inNode->range.length, ( inRange.address + inRange.length - inNode->range.address) ) ; 73 } 74 else 75 if (inNode->right) 76 CoalesceRange(inRange, inNode->right) ; 77 else 78 { 79 inNode->right = new Node ; 80 inNode->right->left = nil ; 81 inNode->right->right = nil ; 82 83 inNode->right->range.address = inRange.address ; 84 inNode->right->range.length = inRange.length ; 85 } 86 } 87 else 88 { 89 if ((inNode->range.address - inRange.address) <= inRange.length) 90 { 91 // merge 92 inNode->range.length = MAX( inRange.length, ( inNode->range.address + inNode->range.length - inRange.address) ) ; 93 inNode->range.address = inRange.address ; 94 } 95 else 96 if (inNode->left) 97 CoalesceRange(inRange, inNode->left) ; 98 else 99 { 100 inNode->left = new Node ; 101 inNode->left->left = nil ; 102 inNode->left->right = nil ; 103 104 inNode->left->range.address = inRange.address ; 105 inNode->left->range.length = inRange.length ; 106 } 107 } 108 } 109 110 const UInt32 111 CoalesceTree::GetCount() const 112 { 113 return GetCount(mTop) ; 114 } 115 116 const UInt32 117 CoalesceTree::GetCount(Node* inNode) const 118 { 119 if (inNode) 120 return 1 + GetCount(inNode->left) + GetCount(inNode->right) ; 121 else 122 return 0 ; 123 } 124 125 void 126 CoalesceTree::GetCoalesceList(IOVirtualRange* outRanges) const 127 { 128 UInt32 index = 0 ; 129 GetCoalesceList(outRanges, mTop, & index) ; 130 } 131 132 void 133 CoalesceTree::GetCoalesceList(IOVirtualRange* outRanges, Node* inNode, UInt32* pIndex) const 134 { 135 if (inNode) 136 { 137 // add ranges less than us first 138 GetCoalesceList(outRanges, inNode->left, pIndex) ; 139 140 // add us 141 outRanges[*pIndex].address = inNode->range.address ; 142 outRanges[*pIndex].length = inNode->range.length ; 143 ++(*pIndex) ; 144 145 // add ranges to the right of us 146 GetCoalesceList(outRanges, inNode->right, pIndex) ; 147 } 148 } 149 150} // namespace 151