2 * Copyright (c) 1998-2000 Apple Computer, Inc. All rights reserved.
4 * @APPLE_LICENSE_HEADER_START@
6 * Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved.
8 * This file contains Original Code and/or Modifications of Original Code
9 * as defined in and that are subject to the Apple Public Source License
10 * Version 2.0 (the 'License'). You may not use this file except in
11 * compliance with the License. Please obtain a copy of the License at
12 * http://www.opensource.apple.com/apsl/ and read it before using this
15 * The Original Code and all software distributed under the License are
16 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
17 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
18 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
20 * Please see the License for the specific language governing rights and
21 * limitations under the License.
23 * @APPLE_LICENSE_HEADER_END@
26 * Copyright (c) 1999 Apple Computer, Inc.
31 * sdouglas 05 Nov 99 - created.
34 #include <libkern/c++/OSArray.h>
35 #include <libkern/c++/OSNumber.h>
36 #include <IOKit/IORangeAllocator.h>
37 #include <IOKit/IOLib.h>
38 #include <IOKit/IOLocks.h>
39 #include <IOKit/assert.h>
41 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
44 #define super OSObject
46 OSDefineMetaClassAndStructors( IORangeAllocator
, OSObject
)
48 struct IORangeAllocatorElement
{
54 IOLock
* gIORangeAllocatorLock
;
57 if( options & kLocking) IOTakeLock( gIORangeAllocatorLock )
59 if( options & kLocking) IOUnlock( gIORangeAllocatorLock )
61 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
63 bool IORangeAllocator::init( IORangeScalar endOfRange
,
64 IORangeScalar _defaultAlignment
,
66 IOOptionBits _options
)
73 if( !_defaultAlignment
)
74 _defaultAlignment
= 1;
76 capacityIncrement
= _capacity
;
79 defaultAlignmentMask
= _defaultAlignment
- 1;
82 if( (!gIORangeAllocatorLock
) && (options
& kLocking
))
83 gIORangeAllocatorLock
= IOLockAlloc();
86 deallocate( 0, endOfRange
+ 1 );
91 IORangeAllocator
* IORangeAllocator:: withRange(
92 IORangeScalar endOfRange
,
93 IORangeScalar defaultAlignment
,
95 IOOptionBits options
)
97 IORangeAllocator
* thingy
;
99 thingy
= new IORangeAllocator
;
100 if( thingy
&& ! thingy
->init( endOfRange
, defaultAlignment
,
101 capacity
, options
)) {
109 void IORangeAllocator::free()
112 IODelete( elements
, IORangeAllocatorElement
, capacity
);
117 UInt32
IORangeAllocator::getFragmentCount( void )
119 return( numElements
);
122 UInt32
IORangeAllocator::getFragmentCapacity( void )
127 void IORangeAllocator::setFragmentCapacityIncrement( UInt32 count
)
129 capacityIncrement
= count
;
133 // allocate element at index
134 bool IORangeAllocator::allocElement( UInt32 index
)
137 IORangeAllocatorElement
* newElements
;
139 if( ((numElements
== capacity
) && capacityIncrement
)
142 newCapacity
= capacity
+ capacityIncrement
;
143 newElements
= IONew( IORangeAllocatorElement
, newCapacity
);
150 index
* sizeof( IORangeAllocatorElement
));
151 bcopy( elements
+ index
,
152 newElements
+ index
+ 1,
153 (numElements
- index
) * sizeof( IORangeAllocatorElement
));
155 IODelete( elements
, IORangeAllocatorElement
, capacity
);
158 elements
= newElements
;
159 capacity
= newCapacity
;
163 bcopy( elements
+ index
,
164 elements
+ index
+ 1,
165 (numElements
- index
) * sizeof( IORangeAllocatorElement
));
172 // destroy element at index
173 void IORangeAllocator::deallocElement( UInt32 index
)
176 bcopy( elements
+ index
+ 1,
178 (numElements
- index
) * sizeof( IORangeAllocatorElement
));
181 bool IORangeAllocator::allocate( IORangeScalar size
,
182 IORangeScalar
* result
,
183 IORangeScalar alignment
)
185 IORangeScalar data
, dataEnd
;
186 IORangeScalar thisStart
, thisEnd
;
190 if( !size
|| !result
)
194 alignment
= defaultAlignmentMask
;
198 size
= (size
+ defaultAlignmentMask
) & ~defaultAlignmentMask
;
202 for( index
= 0; index
< numElements
; index
++ ) {
204 thisStart
= elements
[index
].start
;
205 thisEnd
= elements
[index
].end
;
206 data
= (thisStart
+ alignment
) & ~alignment
;
207 dataEnd
= (data
+ size
- 1);
209 ok
= (dataEnd
<= thisEnd
);
211 if( data
!= thisStart
) {
212 if( dataEnd
!= thisEnd
) {
213 if( allocElement( index
+ 1 )) {
214 elements
[index
++].end
= data
- 1;
215 elements
[index
].start
= dataEnd
+ 1;
216 elements
[index
].end
= thisEnd
;
220 elements
[index
].end
= data
- 1;
222 if( dataEnd
!= thisEnd
)
223 elements
[index
].start
= dataEnd
+ 1;
225 deallocElement( index
);
238 bool IORangeAllocator::allocateRange( IORangeScalar data
,
241 IORangeScalar thisStart
, thisEnd
;
242 IORangeScalar dataEnd
;
249 size
= (size
+ defaultAlignmentMask
) & ~defaultAlignmentMask
;
250 dataEnd
= data
+ size
- 1;
255 (!found
) && (index
< numElements
);
258 thisStart
= elements
[index
].start
;
259 thisEnd
= elements
[index
].end
;
261 if( thisStart
> data
)
263 found
= (dataEnd
<= thisEnd
);
266 if( data
!= thisStart
) {
267 if( dataEnd
!= thisEnd
) {
268 found
= allocElement( index
+ 1 );
270 elements
[index
++].end
= data
- 1;
271 elements
[index
].start
= dataEnd
+ 1;
272 elements
[index
].end
= thisEnd
;
275 elements
[index
].end
= data
- 1;
276 } else if( dataEnd
!= thisEnd
)
277 elements
[index
].start
= dataEnd
+ 1;
279 deallocElement( index
);
288 void IORangeAllocator::deallocate( IORangeScalar data
,
291 IORangeScalar dataEnd
;
293 bool headContig
= false;
294 bool tailContig
= false;
296 size
= (size
+ defaultAlignmentMask
) & ~defaultAlignmentMask
;
297 dataEnd
= data
+ size
- 1;
301 for( index
= 0; index
< numElements
; index
++ ) {
302 if( elements
[index
].start
< data
) {
303 headContig
= (data
<= (elements
[index
].end
+ 1));
306 tailContig
= ((data
+ size
) >= elements
[index
].start
);
312 elements
[index
-1].end
= elements
[index
].end
;
313 deallocElement( index
);
314 } else /*safe*/ if( dataEnd
> elements
[index
-1].end
)
315 elements
[index
-1].end
= dataEnd
;
317 } else if( tailContig
) {
318 if( data
< elements
[index
].start
) /*safe*/
319 elements
[index
].start
= data
;
321 } else if( allocElement( index
)) {
322 elements
[index
].start
= data
;
323 elements
[index
].end
= dataEnd
;
329 bool IORangeAllocator::serialize(OSSerialize
*s
) const
331 OSArray
* array
= OSArray::withCapacity( numElements
* 2 );
341 for( index
= 0; index
< numElements
; index
++) {
342 if( (num
= OSNumber::withNumber( elements
[index
].start
,
343 8 * sizeof(IORangeScalar
) ))) {
344 array
->setObject(num
);
347 if( (num
= OSNumber::withNumber( elements
[index
].end
,
348 8 * sizeof(IORangeScalar
) ))) {
349 array
->setObject(num
);
356 ret
= array
->serialize(s
);
362 IORangeScalar
IORangeAllocator::getFreeCount( void )
365 IORangeScalar sum
= 0;
367 for( index
= 0; index
< numElements
; index
++)
368 sum
+= elements
[index
].end
- elements
[index
].start
+ 1;