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