summary refs log tree commit diff stats
path: root/libs/cocos2d/Support/ccCArray.h
diff options
context:
space:
mode:
Diffstat (limited to 'libs/cocos2d/Support/ccCArray.h')
-rwxr-xr-xlibs/cocos2d/Support/ccCArray.h447
1 files changed, 447 insertions, 0 deletions
diff --git a/libs/cocos2d/Support/ccCArray.h b/libs/cocos2d/Support/ccCArray.h new file mode 100755 index 0000000..20d9633 --- /dev/null +++ b/libs/cocos2d/Support/ccCArray.h
@@ -0,0 +1,447 @@
1/* Copyright (c) 2007 Scott Lembcke
2 *
3 * Permission is hereby granted, free of charge, to any person obtaining a copy
4 * of this software and associated documentation files (the "Software"), to deal
5 * in the Software without restriction, including without limitation the rights
6 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
7 * copies of the Software, and to permit persons to whom the Software is
8 * furnished to do so, subject to the following conditions:
9 *
10 * The above copyright notice and this permission notice shall be included in
11 * all copies or substantial portions of the Software.
12 *
13 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
18 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
19 * SOFTWARE.
20 */
21
22/**
23 @file
24 Based on Chipmunk cpArray.
25 ccArray is a faster alternative to NSMutableArray, it does pretty much the
26 same thing (stores NSObjects and retains/releases them appropriately). It's
27 faster because:
28 - it uses a plain C interface so it doesn't incur Objective-c messaging overhead
29 - it assumes you know what you're doing, so it doesn't spend time on safety checks
30 (index out of bounds, required capacity etc.)
31 - comparisons are done using pointer equality instead of isEqual
32
33 There are 2 kind of functions:
34 - ccArray functions that manipulates objective-c objects (retain and release are performanced)
35 - ccCArray functions that manipulates values like if they were standard C structures (no retain/release is performed)
36 */
37
38#ifndef CC_ARRAY_H
39#define CC_ARRAY_H
40
41#import <Foundation/Foundation.h>
42
43#import <stdlib.h>
44#import <string.h>
45
46
47#pragma mark -
48#pragma mark ccArray for Objects
49
50// Easy integration
51#define CCARRAYDATA_FOREACH(__array__, __object__) \
52__object__=__array__->arr[0]; for(NSUInteger i=0, num=__array__->num; i<num; i++, __object__=__array__->arr[i]) \
53
54
55typedef struct ccArray {
56 NSUInteger num, max;
57 id *arr;
58} ccArray;
59
60/** Allocates and initializes a new array with specified capacity */
61static inline ccArray* ccArrayNew(NSUInteger capacity) {
62 if (capacity == 0)
63 capacity = 1;
64
65 ccArray *arr = (ccArray*)malloc( sizeof(ccArray) );
66 arr->num = 0;
67 arr->arr = (id*) malloc( capacity * sizeof(id) );
68 arr->max = capacity;
69
70 return arr;
71}
72
73static inline void ccArrayRemoveAllObjects(ccArray *arr);
74
75/** Frees array after removing all remaining objects. Silently ignores nil arr. */
76static inline void ccArrayFree(ccArray *arr)
77{
78 if( arr == nil ) return;
79
80 ccArrayRemoveAllObjects(arr);
81
82 free(arr->arr);
83 free(arr);
84}
85
86/** Doubles array capacity */
87static inline void ccArrayDoubleCapacity(ccArray *arr)
88{
89 arr->max *= 2;
90 id *newArr = (id *)realloc( arr->arr, arr->max * sizeof(id) );
91 // will fail when there's not enough memory
92 NSCAssert(newArr != NULL, @"ccArrayDoubleCapacity failed. Not enough memory");
93 arr->arr = newArr;
94}
95
96/** Increases array capacity such that max >= num + extra. */
97static inline void ccArrayEnsureExtraCapacity(ccArray *arr, NSUInteger extra)
98{
99 while (arr->max < arr->num + extra)
100 ccArrayDoubleCapacity(arr);
101}
102
103/** shrinks the array so the memory footprint corresponds with the number of items */
104static inline void ccArrayShrink(ccArray *arr)
105{
106 NSUInteger newSize;
107
108 //only resize when necessary
109 if (arr->max > arr->num && !(arr->num==0 && arr->max==1))
110 {
111 if (arr->num!=0)
112 {
113 newSize=arr->num;
114 arr->max=arr->num;
115 }
116 else
117 {//minimum capacity of 1, with 0 elements the array would be free'd by realloc
118 newSize=1;
119 arr->max=1;
120 }
121
122 arr->arr = (id*) realloc(arr->arr,newSize * sizeof(id) );
123 NSCAssert(arr->arr!=NULL,@"could not reallocate the memory");
124 }
125}
126
127/** Returns index of first occurence of object, NSNotFound if object not found. */
128static inline NSUInteger ccArrayGetIndexOfObject(ccArray *arr, id object)
129{
130 for( NSUInteger i = 0; i < arr->num; i++)
131 if( arr->arr[i] == object ) return i;
132
133 return NSNotFound;
134}
135
136/** Returns a Boolean value that indicates whether object is present in array. */
137static inline BOOL ccArrayContainsObject(ccArray *arr, id object)
138{
139 return ccArrayGetIndexOfObject(arr, object) != NSNotFound;
140}
141
142/** Appends an object. Bahaviour undefined if array doesn't have enough capacity. */
143static inline void ccArrayAppendObject(ccArray *arr, id object)
144{
145 arr->arr[arr->num] = [object retain];
146 arr->num++;
147}
148
149/** Appends an object. Capacity of arr is increased if needed. */
150static inline void ccArrayAppendObjectWithResize(ccArray *arr, id object)
151{
152 ccArrayEnsureExtraCapacity(arr, 1);
153 ccArrayAppendObject(arr, object);
154}
155
156/** Appends objects from plusArr to arr. Behaviour undefined if arr doesn't have
157 enough capacity. */
158static inline void ccArrayAppendArray(ccArray *arr, ccArray *plusArr)
159{
160 for( NSUInteger i = 0; i < plusArr->num; i++)
161 ccArrayAppendObject(arr, plusArr->arr[i]);
162}
163
164/** Appends objects from plusArr to arr. Capacity of arr is increased if needed. */
165static inline void ccArrayAppendArrayWithResize(ccArray *arr, ccArray *plusArr)
166{
167 ccArrayEnsureExtraCapacity(arr, plusArr->num);
168 ccArrayAppendArray(arr, plusArr);
169}
170
171/** Inserts an object at index */
172static inline void ccArrayInsertObjectAtIndex(ccArray *arr, id object, NSUInteger index)
173{
174 NSCAssert(index<=arr->num, @"Invalid index. Out of bounds");
175
176 ccArrayEnsureExtraCapacity(arr, 1);
177
178 NSUInteger remaining = arr->num - index;
179 if( remaining > 0)
180 memmove(&arr->arr[index+1], &arr->arr[index], sizeof(id) * remaining );
181
182 arr->arr[index] = [object retain];
183 arr->num++;
184}
185
186/** Swaps two objects */
187static inline void ccArraySwapObjectsAtIndexes(ccArray *arr, NSUInteger index1, NSUInteger index2)
188{
189 NSCAssert(index1 < arr->num, @"(1) Invalid index. Out of bounds");
190 NSCAssert(index2 < arr->num, @"(2) Invalid index. Out of bounds");
191
192 id object1 = arr->arr[index1];
193
194 arr->arr[index1] = arr->arr[index2];
195 arr->arr[index2] = object1;
196}
197
198/** Removes all objects from arr */
199static inline void ccArrayRemoveAllObjects(ccArray *arr)
200{
201 while( arr->num > 0 )
202 [arr->arr[--arr->num] release];
203}
204
205/** Removes object at specified index and pushes back all subsequent objects.
206 Behaviour undefined if index outside [0, num-1]. */
207static inline void ccArrayRemoveObjectAtIndex(ccArray *arr, NSUInteger index)
208{
209 [arr->arr[index] release];
210 arr->num--;
211
212 NSUInteger remaining = arr->num - index;
213 if(remaining>0)
214 memmove(&arr->arr[index], &arr->arr[index+1], remaining * sizeof(id));
215}
216
217/** Removes object at specified index and fills the gap with the last object,
218 thereby avoiding the need to push back subsequent objects.
219 Behaviour undefined if index outside [0, num-1]. */
220static inline void ccArrayFastRemoveObjectAtIndex(ccArray *arr, NSUInteger index)
221{
222 [arr->arr[index] release];
223 NSUInteger last = --arr->num;
224 arr->arr[index] = arr->arr[last];
225}
226
227static inline void ccArrayFastRemoveObject(ccArray *arr, id object)
228{
229 NSUInteger index = ccArrayGetIndexOfObject(arr, object);
230 if (index != NSNotFound)
231 ccArrayFastRemoveObjectAtIndex(arr, index);
232}
233
234/** Searches for the first occurance of object and removes it. If object is not
235 found the function has no effect. */
236static inline void ccArrayRemoveObject(ccArray *arr, id object)
237{
238 NSUInteger index = ccArrayGetIndexOfObject(arr, object);
239 if (index != NSNotFound)
240 ccArrayRemoveObjectAtIndex(arr, index);
241}
242
243/** Removes from arr all objects in minusArr. For each object in minusArr, the
244 first matching instance in arr will be removed. */
245static inline void ccArrayRemoveArray(ccArray *arr, ccArray *minusArr)
246{
247 for( NSUInteger i = 0; i < minusArr->num; i++)
248 ccArrayRemoveObject(arr, minusArr->arr[i]);
249}
250
251/** Removes from arr all objects in minusArr. For each object in minusArr, all
252 matching instances in arr will be removed. */
253static inline void ccArrayFullRemoveArray(ccArray *arr, ccArray *minusArr)
254{
255 NSUInteger back = 0;
256
257 for( NSUInteger i = 0; i < arr->num; i++) {
258 if( ccArrayContainsObject(minusArr, arr->arr[i]) ) {
259 [arr->arr[i] release];
260 back++;
261 } else
262 arr->arr[i - back] = arr->arr[i];
263 }
264
265 arr->num -= back;
266}
267
268/** Sends to each object in arr the message identified by given selector. */
269static inline void ccArrayMakeObjectsPerformSelector(ccArray *arr, SEL sel)
270{
271 for( NSUInteger i = 0; i < arr->num; i++)
272 [arr->arr[i] performSelector:sel];
273}
274
275static inline void ccArrayMakeObjectsPerformSelectorWithObject(ccArray *arr, SEL sel, id object)
276{
277 for( NSUInteger i = 0; i < arr->num; i++)
278 [arr->arr[i] performSelector:sel withObject:object];
279}
280
281
282#pragma mark -
283#pragma mark ccCArray for Values (c structures)
284
285typedef ccArray ccCArray;
286
287static inline void ccCArrayRemoveAllValues(ccCArray *arr);
288
289/** Allocates and initializes a new C array with specified capacity */
290static inline ccCArray* ccCArrayNew(NSUInteger capacity) {
291 if (capacity == 0)
292 capacity = 1;
293
294 ccCArray *arr = (ccCArray*)malloc( sizeof(ccCArray) );
295 arr->num = 0;
296 arr->arr = (id*) malloc( capacity * sizeof(id) );
297 arr->max = capacity;
298
299 return arr;
300}
301
302/** Frees C array after removing all remaining values. Silently ignores nil arr. */
303static inline void ccCArrayFree(ccCArray *arr)
304{
305 if( arr == nil ) return;
306
307 ccCArrayRemoveAllValues(arr);
308
309 free(arr->arr);
310 free(arr);
311}
312
313/** Doubles C array capacity */
314static inline void ccCArrayDoubleCapacity(ccCArray *arr)
315{
316 ccArrayDoubleCapacity(arr);
317}
318
319/** Increases array capacity such that max >= num + extra. */
320static inline void ccCArrayEnsureExtraCapacity(ccCArray *arr, NSUInteger extra)
321{
322 ccArrayEnsureExtraCapacity(arr,extra);
323}
324
325/** Returns index of first occurence of value, NSNotFound if value not found. */
326static inline NSUInteger ccCArrayGetIndexOfValue(ccCArray *arr, void* value)
327{
328 for( NSUInteger i = 0; i < arr->num; i++)
329 if( arr->arr[i] == value ) return i;
330 return NSNotFound;
331}
332
333/** Returns a Boolean value that indicates whether value is present in the C array. */
334static inline BOOL ccCArrayContainsValue(ccCArray *arr, void* value)
335{
336 return ccCArrayGetIndexOfValue(arr, value) != NSNotFound;
337}
338
339/** Inserts a value at a certain position. Behaviour undefined if aray doesn't have enough capacity */
340static inline void ccCArrayInsertValueAtIndex( ccCArray *arr, void *value, NSUInteger index)
341{
342 NSCAssert( index < arr->max, @"ccCArrayInsertValueAtIndex: invalid index");
343
344 NSUInteger remaining = arr->num - index;
345
346 // last Value doesn't need to be moved
347 if( remaining > 0) {
348 // tex coordinates
349 memmove( &arr->arr[index+1],&arr->arr[index], sizeof(void*) * remaining );
350 }
351
352 arr->num++;
353 arr->arr[index] = (id) value;
354}
355
356/** Appends an value. Bahaviour undefined if array doesn't have enough capacity. */
357static inline void ccCArrayAppendValue(ccCArray *arr, void* value)
358{
359 arr->arr[arr->num] = (id) value;
360 arr->num++;
361}
362
363/** Appends an value. Capacity of arr is increased if needed. */
364static inline void ccCArrayAppendValueWithResize(ccCArray *arr, void* value)
365{
366 ccCArrayEnsureExtraCapacity(arr, 1);
367 ccCArrayAppendValue(arr, value);
368}
369
370/** Appends values from plusArr to arr. Behaviour undefined if arr doesn't have
371 enough capacity. */
372static inline void ccCArrayAppendArray(ccCArray *arr, ccCArray *plusArr)
373{
374 for( NSUInteger i = 0; i < plusArr->num; i++)
375 ccCArrayAppendValue(arr, plusArr->arr[i]);
376}
377
378/** Appends values from plusArr to arr. Capacity of arr is increased if needed. */
379static inline void ccCArrayAppendArrayWithResize(ccCArray *arr, ccCArray *plusArr)
380{
381 ccCArrayEnsureExtraCapacity(arr, plusArr->num);
382 ccCArrayAppendArray(arr, plusArr);
383}
384
385/** Removes all values from arr */
386static inline void ccCArrayRemoveAllValues(ccCArray *arr)
387{
388 arr->num = 0;
389}
390
391/** Removes value at specified index and pushes back all subsequent values.
392 Behaviour undefined if index outside [0, num-1].
393 @since v0.99.4
394 */
395static inline void ccCArrayRemoveValueAtIndex(ccCArray *arr, NSUInteger index)
396{
397 for( NSUInteger last = --arr->num; index < last; index++)
398 arr->arr[index] = arr->arr[index + 1];
399}
400
401/** Removes value at specified index and fills the gap with the last value,
402 thereby avoiding the need to push back subsequent values.
403 Behaviour undefined if index outside [0, num-1].
404 @since v0.99.4
405 */
406static inline void ccCArrayFastRemoveValueAtIndex(ccCArray *arr, NSUInteger index)
407{
408 NSUInteger last = --arr->num;
409 arr->arr[index] = arr->arr[last];
410}
411
412/** Searches for the first occurance of value and removes it. If value is not found the function has no effect.
413 @since v0.99.4
414 */
415static inline void ccCArrayRemoveValue(ccCArray *arr, void* value)
416{
417 NSUInteger index = ccCArrayGetIndexOfValue(arr, value);
418 if (index != NSNotFound)
419 ccCArrayRemoveValueAtIndex(arr, index);
420}
421
422/** Removes from arr all values in minusArr. For each Value in minusArr, the first matching instance in arr will be removed.
423 @since v0.99.4
424 */
425static inline void ccCArrayRemoveArray(ccCArray *arr, ccCArray *minusArr)
426{
427 for( NSUInteger i = 0; i < minusArr->num; i++)
428 ccCArrayRemoveValue(arr, minusArr->arr[i]);
429}
430
431/** Removes from arr all values in minusArr. For each value in minusArr, all matching instances in arr will be removed.
432 @since v0.99.4
433 */
434static inline void ccCArrayFullRemoveArray(ccCArray *arr, ccCArray *minusArr)
435{
436 NSUInteger back = 0;
437
438 for( NSUInteger i = 0; i < arr->num; i++) {
439 if( ccCArrayContainsValue(minusArr, arr->arr[i]) ) {
440 back++;
441 } else
442 arr->arr[i - back] = arr->arr[i];
443 }
444
445 arr->num -= back;
446}
447#endif // CC_ARRAY_H