X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/a39ff7e25e19b3a8c3020042a3872ca9ec9659f1..c6bf4f310a33a9262d455ea4d3f0630b1255e3fe:/iokit/Kernel/IORangeAllocator.cpp

diff --git a/iokit/Kernel/IORangeAllocator.cpp b/iokit/Kernel/IORangeAllocator.cpp
index 393a9c03b..6e1148697 100644
--- a/iokit/Kernel/IORangeAllocator.cpp
+++ b/iokit/Kernel/IORangeAllocator.cpp
@@ -2,7 +2,7 @@
  * Copyright (c) 1998-2000 Apple Computer, Inc. All rights reserved.
  *
  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
- * 
+ *
  * This file contains Original Code and/or Modifications of Original Code
  * as defined in and that are subject to the Apple Public Source License
  * Version 2.0 (the 'License'). You may not use this file except in
@@ -11,10 +11,10 @@
  * unlawful or unlicensed copies of an Apple operating system, or to
  * circumvent, violate, or enable the circumvention or violation of, any
  * terms of an Apple operating system software license agreement.
- * 
+ *
  * Please obtain a copy of the License at
  * http://www.opensource.apple.com/apsl/ and read it before using this file.
- * 
+ *
  * The Original Code and all software distributed under the License are
  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
@@ -22,7 +22,7 @@
  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  * Please see the License for the specific language governing rights and
  * limitations under the License.
- * 
+ *
  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  */
 /*
@@ -49,328 +49,355 @@
 OSDefineMetaClassAndStructors( IORangeAllocator, OSObject )
 
 struct IORangeAllocatorElement {
-    // closed range
-    IORangeScalar	start;
-    IORangeScalar	end;
+	// closed range
+	IORangeScalar       start;
+	IORangeScalar       end;
 };
 
-IOLock *	gIORangeAllocatorLock;
+IOLock *        gIORangeAllocatorLock;
 
-#define LOCK()		\
+#define LOCK()          \
 	if( options & kLocking)	IOTakeLock( gIORangeAllocatorLock )
-#define UNLOCK()	\
+#define UNLOCK()        \
 	if( options & kLocking)	IOUnlock( gIORangeAllocatorLock )
 
 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 
-bool IORangeAllocator::init( IORangeScalar endOfRange,
-				IORangeScalar _defaultAlignment,
-				UInt32 _capacity,
-				IOOptionBits _options )
+bool
+IORangeAllocator::init( IORangeScalar endOfRange,
+    IORangeScalar _defaultAlignment,
+    UInt32 _capacity,
+    IOOptionBits _options )
 {
-    if( !super::init())
-	return( false );
-
-    if( !_capacity)
-	_capacity = 1;
-    if( !_defaultAlignment)
-	_defaultAlignment = 1;
-    capacity		= 0;
-    capacityIncrement	= _capacity;
-    numElements 	= 0;
-    elements 		= 0;
-    defaultAlignmentMask = _defaultAlignment - 1;
-    options		= _options;
-
-    if( (!gIORangeAllocatorLock) && (options & kLocking))
-	gIORangeAllocatorLock = IOLockAlloc();
-
-    if( endOfRange)
-	deallocate( 0, endOfRange + 1 );
-
-    return( true );
+	if (!super::init()) {
+		return false;
+	}
+
+	if (!_capacity) {
+		_capacity = 1;
+	}
+	if (!_defaultAlignment) {
+		_defaultAlignment = 1;
+	}
+	capacity            = 0;
+	capacityIncrement   = _capacity;
+	numElements         = 0;
+	elements            = NULL;
+	defaultAlignmentMask = _defaultAlignment - 1;
+	options             = _options;
+
+	if ((!gIORangeAllocatorLock) && (options & kLocking)) {
+		gIORangeAllocatorLock = IOLockAlloc();
+	}
+
+	if (endOfRange) {
+		deallocate( 0, endOfRange + 1 );
+	}
+
+	return true;
 }
 
-IORangeAllocator * IORangeAllocator::withRange(
-					IORangeScalar endOfRange,
-				        IORangeScalar defaultAlignment,
-				        UInt32 capacity,
-					IOOptionBits options )
+IORangeAllocator *
+IORangeAllocator::withRange(
+	IORangeScalar endOfRange,
+	IORangeScalar defaultAlignment,
+	UInt32 capacity,
+	IOOptionBits options )
 {
-    IORangeAllocator * thingy;
+	IORangeAllocator * thingy;
 
-    thingy = new IORangeAllocator;
-    if( thingy && ! thingy->init( endOfRange, defaultAlignment,
-				capacity, options )) {
-	thingy->release();
-	thingy = 0;
-    }
+	thingy = new IORangeAllocator;
+	if (thingy && !thingy->init( endOfRange, defaultAlignment,
+	    capacity, options )) {
+		thingy->release();
+		thingy = NULL;
+	}
 
-    return( thingy );
+	return thingy;
 }
 
-void IORangeAllocator::free()
+void
+IORangeAllocator::free()
 {
-    if( elements)
-	IODelete( elements, IORangeAllocatorElement, capacity );
+	if (elements) {
+		IODelete( elements, IORangeAllocatorElement, capacity );
+	}
 
-    super::free();
+	super::free();
 }
 
-UInt32 IORangeAllocator::getFragmentCount( void )
+UInt32
+IORangeAllocator::getFragmentCount( void )
 {
-    return( numElements );
+	return numElements;
 }
 
-UInt32 IORangeAllocator::getFragmentCapacity( void )
+UInt32
+IORangeAllocator::getFragmentCapacity( void )
 {
-    return( capacity );
+	return capacity;
 }
 
-void IORangeAllocator::setFragmentCapacityIncrement( UInt32 count )
+void
+IORangeAllocator::setFragmentCapacityIncrement( UInt32 count )
 {
-    capacityIncrement = count;
+	capacityIncrement = count;
 }
 
 
 // allocate element at index
-bool IORangeAllocator::allocElement( UInt32 index )
+bool
+IORangeAllocator::allocElement( UInt32 index )
 {
-    UInt32			newCapacity;
-    IORangeAllocatorElement *	newElements;
-
-    if( ((numElements == capacity) && capacityIncrement)
-     || (!elements)) {
-
-	if (os_add_overflow(capacity, capacityIncrement, &newCapacity))
-	    return( false );
-	newElements = IONew( IORangeAllocatorElement, newCapacity );
-	if( !newElements)
-	    return( false );
-
-	if( elements) {
-	    bcopy( elements,
-		   newElements,
-		   index * sizeof( IORangeAllocatorElement));
-	    bcopy( elements + index,
-		   newElements + index + 1,
-		   (numElements - index) * sizeof( IORangeAllocatorElement));
-
-	    IODelete( elements, IORangeAllocatorElement, capacity );
+	UInt32                      newCapacity;
+	IORangeAllocatorElement *   newElements;
+
+	if (((numElements == capacity) && capacityIncrement)
+	    || (!elements)) {
+		if (os_add_overflow(capacity, capacityIncrement, &newCapacity)) {
+			return false;
+		}
+		newElements = IONew( IORangeAllocatorElement, newCapacity );
+		if (!newElements) {
+			return false;
+		}
+
+		if (elements) {
+			bcopy( elements,
+			    newElements,
+			    index * sizeof(IORangeAllocatorElement));
+			bcopy( elements + index,
+			    newElements + index + 1,
+			    (numElements - index) * sizeof(IORangeAllocatorElement));
+
+			IODelete( elements, IORangeAllocatorElement, capacity );
+		}
+
+		elements = newElements;
+		capacity = newCapacity;
+	} else {
+		bcopy( elements + index,
+		    elements + index + 1,
+		    (numElements - index) * sizeof(IORangeAllocatorElement));
 	}
+	numElements++;
 
-	elements = newElements;
-	capacity = newCapacity;
-
-    } else {
-
-	bcopy( elements + index,
-	       elements + index + 1,
-	       (numElements - index) * sizeof( IORangeAllocatorElement));
-    }
-    numElements++;
-
-    return( true );
+	return true;
 }
 
 // destroy element at index
-void IORangeAllocator::deallocElement( UInt32 index )
+void
+IORangeAllocator::deallocElement( UInt32 index )
 {
-    numElements--;
-    bcopy( elements + index + 1,
-	   elements + index,
-	   (numElements - index) * sizeof( IORangeAllocatorElement));
+	numElements--;
+	bcopy( elements + index + 1,
+	    elements + index,
+	    (numElements - index) * sizeof(IORangeAllocatorElement));
 }
 
-bool IORangeAllocator::allocate( IORangeScalar size,
-				 IORangeScalar * result,
-				 IORangeScalar alignment )
+bool
+IORangeAllocator::allocate( IORangeScalar size,
+    IORangeScalar * result,
+    IORangeScalar alignment )
 {
-    IORangeScalar	data, dataEnd;
-    IORangeScalar	thisStart, thisEnd;
-    UInt32		index;
-    bool		ok = false;
-
-    if( !size || !result)
-	return( false );
-
-    if( 0 == alignment)
-	alignment = defaultAlignmentMask;
-    else
-        alignment--;
-
-    size = (size + defaultAlignmentMask) & ~defaultAlignmentMask;
-
-    LOCK();
-
-    for( index = 0; index < numElements; index++ ) {
-
-	thisStart = elements[index].start;
-	thisEnd = elements[index].end;
-        data = (thisStart + alignment) & ~alignment;
-	dataEnd = (data + size - 1);
-
-	ok = (dataEnd <= thisEnd);
-	if( ok) {
-	    if( data != thisStart) {
-		if( dataEnd != thisEnd) {
-		    if( allocElement( index + 1 )) {
-			elements[index++].end = data - 1;
-			elements[index].start = dataEnd + 1;
-			elements[index].end = thisEnd;
-		    } else
-			ok = false;
-		} else
-		    elements[index].end = data - 1;
-	    } else {
-		if( dataEnd != thisEnd)
-		    elements[index].start = dataEnd + 1;
-		else
-		    deallocElement( index );
-	    }
-	    if( ok)
-		*result = data;
-      	    break;
-	} 
-    }
-
-    UNLOCK();
-
-    return( ok );
-}
+	IORangeScalar       data, dataEnd;
+	IORangeScalar       thisStart, thisEnd;
+	UInt32              index;
+	bool                ok = false;
 
-bool IORangeAllocator::allocateRange( IORangeScalar data,
-					 IORangeScalar size )
-{
-    IORangeScalar	thisStart, thisEnd;
-    IORangeScalar	dataEnd;
-    UInt32		index;
-    bool		found = false;
-
-    if( !size)
-	return( 0 );
-
-    size = (size + defaultAlignmentMask) & ~defaultAlignmentMask;
-    dataEnd = data + size - 1;
-
-    LOCK();
-
-    for( index = 0;
-	 (!found) && (index < numElements);
-	 index++ ) {
-
-	thisStart = elements[index].start;
-	thisEnd = elements[index].end;
-
-	if( thisStart > data)
-	    break;
-	found = (dataEnd <= thisEnd);
-
-        if( found) {
-	    if( data != thisStart) {
-	        if( dataEnd != thisEnd) {
-		    found = allocElement( index + 1 );
-		    if( found) {
-		        elements[index++].end = data - 1;
-		        elements[index].start = dataEnd + 1;
-		        elements[index].end = thisEnd;
-		    }
-	        } else
-	       	    elements[index].end = data - 1;
-	    } else if( dataEnd != thisEnd)
-      	        elements[index].start = dataEnd + 1;
-	    else
-	        deallocElement( index );
-        }
-    }
-
-    UNLOCK();
-
-    return( found );
+	if (!size || !result) {
+		return false;
+	}
+
+	if (0 == alignment) {
+		alignment = defaultAlignmentMask;
+	} else {
+		alignment--;
+	}
+
+	size = (size + defaultAlignmentMask) & ~defaultAlignmentMask;
+
+	LOCK();
+
+	for (index = 0; index < numElements; index++) {
+		thisStart = elements[index].start;
+		thisEnd = elements[index].end;
+		data = (thisStart + alignment) & ~alignment;
+		dataEnd = (data + size - 1);
+
+		ok = (dataEnd <= thisEnd);
+		if (ok) {
+			if (data != thisStart) {
+				if (dataEnd != thisEnd) {
+					if (allocElement( index + 1 )) {
+						elements[index++].end = data - 1;
+						elements[index].start = dataEnd + 1;
+						elements[index].end = thisEnd;
+					} else {
+						ok = false;
+					}
+				} else {
+					elements[index].end = data - 1;
+				}
+			} else {
+				if (dataEnd != thisEnd) {
+					elements[index].start = dataEnd + 1;
+				} else {
+					deallocElement( index );
+				}
+			}
+			if (ok) {
+				*result = data;
+			}
+			break;
+		}
+	}
+
+	UNLOCK();
+
+	return ok;
 }
 
-void IORangeAllocator::deallocate( IORangeScalar data,
-				   IORangeScalar size )
+bool
+IORangeAllocator::allocateRange( IORangeScalar data,
+    IORangeScalar size )
 {
-    IORangeScalar	dataEnd;
-    UInt32		index;
-    bool		headContig = false;
-    bool		tailContig = false;
-
-    size = (size + defaultAlignmentMask) & ~defaultAlignmentMask;
-    dataEnd = data + size - 1;
+	IORangeScalar       thisStart, thisEnd;
+	IORangeScalar       dataEnd;
+	UInt32              index;
+	bool                found = false;
 
-    LOCK();
+	if (!size) {
+		return 0;
+	}
 
-    for( index = 0; index < numElements; index++ ) {
-	if( elements[index].start < data) {
-	    headContig = (data <= (elements[index].end + 1));
-	    continue;
+	size = (size + defaultAlignmentMask) & ~defaultAlignmentMask;
+	dataEnd = data + size - 1;
+
+	LOCK();
+
+	for (index = 0;
+	    (!found) && (index < numElements);
+	    index++) {
+		thisStart = elements[index].start;
+		thisEnd = elements[index].end;
+
+		if (thisStart > data) {
+			break;
+		}
+		found = (dataEnd <= thisEnd);
+
+		if (found) {
+			if (data != thisStart) {
+				if (dataEnd != thisEnd) {
+					found = allocElement( index + 1 );
+					if (found) {
+						elements[index++].end = data - 1;
+						elements[index].start = dataEnd + 1;
+						elements[index].end = thisEnd;
+					}
+				} else {
+					elements[index].end = data - 1;
+				}
+			} else if (dataEnd != thisEnd) {
+				elements[index].start = dataEnd + 1;
+			} else {
+				deallocElement( index );
+			}
+		}
 	}
-	tailContig = ((data + size) >= elements[index].start);
-	break;
-    }
-
-    if( headContig) {
-        if( tailContig) {
-            elements[index-1].end = elements[index].end;
-	    deallocElement( index );
-	} else /*safe*/ if( dataEnd > elements[index-1].end)
-	    elements[index-1].end = dataEnd;
-
-    } else if( tailContig) {
-	if( data < elements[index].start) /*safe*/
-	    elements[index].start = data;
-
-    } else if( allocElement( index)) {
-	elements[index].start = data;
-	elements[index].end = dataEnd;
-    }
-
-    UNLOCK();
+
+	UNLOCK();
+
+	return found;
 }
 
-bool IORangeAllocator::serialize(OSSerialize *s) const
+void
+IORangeAllocator::deallocate( IORangeScalar data,
+    IORangeScalar size )
 {
-    OSArray *	array = OSArray::withCapacity( numElements * 2 );
-    OSNumber *	num;
-    UInt32	index;
-    bool	ret;
+	IORangeScalar       dataEnd;
+	UInt32              index;
+	bool                headContig = false;
+	bool                tailContig = false;
+
+	size = (size + defaultAlignmentMask) & ~defaultAlignmentMask;
+	dataEnd = data + size - 1;
+
+	LOCK();
+
+	for (index = 0; index < numElements; index++) {
+		if (elements[index].start < data) {
+			headContig = (data <= (elements[index].end + 1));
+			continue;
+		}
+		tailContig = ((data + size) >= elements[index].start);
+		break;
+	}
 
-    if( !array)
-	return( false );
+	if (headContig) {
+		if (tailContig) {
+			elements[index - 1].end = elements[index].end;
+			deallocElement( index );
+		} else /*safe*/ if (dataEnd > elements[index - 1].end) {
+			elements[index - 1].end = dataEnd;
+		}
+	} else if (tailContig) {
+		if (data < elements[index].start) { /*safe*/
+			elements[index].start = data;
+		}
+	} else if (allocElement( index)) {
+		elements[index].start = data;
+		elements[index].end = dataEnd;
+	}
 
-    LOCK();
+	UNLOCK();
+}
 
-    for( index = 0; index < numElements; index++) {
-	if( (num = OSNumber::withNumber( elements[index].start,
-					8 * sizeof(IORangeScalar) ))) {
-	    array->setObject(num);
-	    num->release();
+bool
+IORangeAllocator::serialize(OSSerialize *s) const
+{
+	OSArray *   array = OSArray::withCapacity( numElements * 2 );
+	OSNumber *  num;
+	UInt32      index;
+	bool        ret;
+
+	if (!array) {
+		return false;
 	}
-	if( (num = OSNumber::withNumber( elements[index].end,
-					8 * sizeof(IORangeScalar) ))) {
-	    array->setObject(num);
-	    num->release();
+
+	LOCK();
+
+	for (index = 0; index < numElements; index++) {
+		if ((num = OSNumber::withNumber( elements[index].start,
+		    8 * sizeof(IORangeScalar)))) {
+			array->setObject(num);
+			num->release();
+		}
+		if ((num = OSNumber::withNumber( elements[index].end,
+		    8 * sizeof(IORangeScalar)))) {
+			array->setObject(num);
+			num->release();
+		}
 	}
-    }
 
-    UNLOCK();
+	UNLOCK();
 
-    ret = array->serialize(s);
-    array->release();
+	ret = array->serialize(s);
+	array->release();
 
-    return( ret );
+	return ret;
 }
 
-IORangeScalar IORangeAllocator::getFreeCount( void )
+IORangeScalar
+IORangeAllocator::getFreeCount( void )
 {
-    UInt32		index;
-    IORangeScalar	sum = 0;
+	UInt32              index;
+	IORangeScalar       sum = 0;
 
-    for( index = 0; index < numElements; index++)
-	sum += elements[index].end - elements[index].start + 1;
+	for (index = 0; index < numElements; index++) {
+		sum += elements[index].end - elements[index].start + 1;
+	}
 
-    return( sum );
+	return sum;
 }
-