xnu-6153.81.5.tar.gz

[apple/xnu.git] / iokit / Kernel / IORangeAllocator.cpp

diff --git a/iokit/Kernel/IORangeAllocator.cpp b/iokit/Kernel/IORangeAllocator.cpp
index 393a9c03b1642265954584f7a8067e70413d6aca..6e114869755ca824d2f94f5b1d0080aca8e690ae 100644 (file)
--- 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@
  * 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
  * 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.
  * 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.
  * 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,
  * 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.
  * 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@
  */
 /*
  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  */
 /*


@@ -49,328 +49,355 @@
 OSDefineMetaClassAndStructors( IORangeAllocator, OSObject )
 
 struct IORangeAllocatorElement {
 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 )
        if( options & kLocking) IOTakeLock( gIORangeAllocatorLock )

-#define UNLOCK()       \
+#define UNLOCK()        \

        if( options & kLocking) IOUnlock( gIORangeAllocatorLock )
 
 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 
        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
 }
 
 
 // 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
 }
 
 // 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;

 }
 }

-