file_systems/btrfs/ExtentAllocator.cpp

110 	CachedExtent* node = FindClosest(lowerBound, false);
113 	uint64 flags = node->flags & (~BTRFS_EXTENT_FLAG_ALLOCATED);
114 	if (lowerBound < node->offset) {
115 		hole = CachedExtent::Create(lowerBound, node->offset - lowerBound,
123 	while ((next = Next(node)) != NULL && next->End() < upperBound) {
124 		if (node->End() == next->offset) {
125 			node = next;
129 		hole = CachedExtent::Create(node->End(), next->offset - node->End(),
134 		node = next;
137 	// final node should be a right most node
138 	if (upperBound > node->End()) {
139 		hole = CachedExtent::Create(node->End(), upperBound - node->End(),
149 CachedExtentTree::_RemoveExtent(CachedExtent* node)
151 	node->refCount--;
152 	if (node->refCount <= 0) {
153 		Remove(node);
154 		node->Delete();
160 CachedExtentTree::_AddAllocatedExtent(CachedExtent* node)
162 	if (node == NULL || node->IsAllocated() == false)
165 	CachedExtent* found = Find(node->offset);
167 		Insert(node);
171 	if ((found->IsData() && !node->IsData())
172 		|| (!found->IsData() && node->IsData())) {
175 		node->Delete();
181 		if (node->End() > found->End()) {
183 			node->Delete();
188 		//    |-- node ---|
189 		uint64 diff = node->offset - found->offset;
190 		found->offset += diff + node->length;
191 		found->length -= diff + node->length;
195 				node->offset - diff, diff, found->flags);
204 		Insert(node);
208 	if (found->length == node->length) {
214 	node->Delete();
221 CachedExtentTree::_AddFreeExtent(CachedExtent* node)
223 	if (node == NULL || node->IsAllocated() == true)
226 	CachedExtent* found = Find(node->offset);
228 		Insert(node);
229 		_CombineFreeExtent(node);
233 	if ((found->IsData() && !node->IsData())
234 		|| (!found->IsData() && node->IsData())) {
237 		node->Delete();
241 	if (found->End() < node->End()) {
243 		//      |--- node ------|
245 			node->End() - found->End(), node->flags);
247 		node->length -= node->End() - found->End();
253 		//    |-- node ---|
254 		uint64 diff = node->offset - found->offset;
255 		found->offset += diff + node->length;
256 		found->length -= diff + node->length;
259 			CachedExtent* left = CachedExtent::Create(node->offset - diff,
267 		Insert(node);
268 		_CombineFreeExtent(node);
285 CachedExtentTree::_CombineFreeExtent(CachedExtent* node)
287 	// node should be inserted first to call this function,
289 	if (node->IsAllocated() == true)
292 	CachedExtent* other = Next(node);
294 		if (node->End() == other->offset && node->flags == other->flags) {
295 			node->length += other->length;
300 	other = Previous(node);
302 		if (other->End() == node->offset && node->flags == other->flags) {
303 			other->length += node->length;
304 			_RemoveExtent(node);
311 CachedExtentTree::_DumpInOrder(CachedExtent* node) const
313 	if (node == NULL)
315 	_DumpInOrder(_GetValue(node->left));
316 	node->Info();
317 	_DumpInOrder(_GetValue(node->right));
339 CachedExtentTree::_Delete(CachedExtent* node)
341 	if (node == NULL)
343 	_Delete(_GetValue(node->left));
344 	_Delete(_GetValue(node->right));
345 	node->Delete();