From 9cd57b731ab1c666d4a1cb725538fdc137763d12 Mon Sep 17 00:00:00 2001 From: Starla Insigna Date: Sat, 30 Jul 2011 11:19:14 -0400 Subject: Initial commit (version 0.2.1) --- libs/cocos2d/Support/CCArray.h | 106 ++++ libs/cocos2d/Support/CCArray.m | 290 ++++++++++ libs/cocos2d/Support/CCFileUtils.h | 62 ++ libs/cocos2d/Support/CCFileUtils.m | 169 ++++++ libs/cocos2d/Support/CCProfiling.h | 53 ++ libs/cocos2d/Support/CCProfiling.m | 117 ++++ libs/cocos2d/Support/CGPointExtension.h | 334 +++++++++++ libs/cocos2d/Support/CGPointExtension.m | 196 +++++++ libs/cocos2d/Support/OpenGL_Internal.h | 80 +++ libs/cocos2d/Support/TGAlib.h | 55 ++ libs/cocos2d/Support/TGAlib.m | 274 +++++++++ libs/cocos2d/Support/TransformUtils.h | 37 ++ libs/cocos2d/Support/TransformUtils.m | 46 ++ libs/cocos2d/Support/ZipUtils.h | 91 +++ libs/cocos2d/Support/ZipUtils.m | 251 +++++++++ libs/cocos2d/Support/base64.c | 93 +++ libs/cocos2d/Support/base64.h | 33 ++ libs/cocos2d/Support/ccCArray.h | 447 +++++++++++++++ libs/cocos2d/Support/ccUtils.c | 20 + libs/cocos2d/Support/ccUtils.h | 29 + libs/cocos2d/Support/uthash.h | 972 ++++++++++++++++++++++++++++++++ libs/cocos2d/Support/utlist.h | 490 ++++++++++++++++ 22 files changed, 4245 insertions(+) create mode 100755 libs/cocos2d/Support/CCArray.h create mode 100755 libs/cocos2d/Support/CCArray.m create mode 100755 libs/cocos2d/Support/CCFileUtils.h create mode 100755 libs/cocos2d/Support/CCFileUtils.m create mode 100755 libs/cocos2d/Support/CCProfiling.h create mode 100755 libs/cocos2d/Support/CCProfiling.m create mode 100755 libs/cocos2d/Support/CGPointExtension.h create mode 100755 libs/cocos2d/Support/CGPointExtension.m create mode 100755 libs/cocos2d/Support/OpenGL_Internal.h create mode 100755 libs/cocos2d/Support/TGAlib.h create mode 100755 libs/cocos2d/Support/TGAlib.m create mode 100755 libs/cocos2d/Support/TransformUtils.h create mode 100755 libs/cocos2d/Support/TransformUtils.m create mode 100755 libs/cocos2d/Support/ZipUtils.h create mode 100755 libs/cocos2d/Support/ZipUtils.m create mode 100755 libs/cocos2d/Support/base64.c create mode 100755 libs/cocos2d/Support/base64.h create mode 100755 libs/cocos2d/Support/ccCArray.h create mode 100755 libs/cocos2d/Support/ccUtils.c create mode 100755 libs/cocos2d/Support/ccUtils.h create mode 100755 libs/cocos2d/Support/uthash.h create mode 100755 libs/cocos2d/Support/utlist.h (limited to 'libs/cocos2d/Support') diff --git a/libs/cocos2d/Support/CCArray.h b/libs/cocos2d/Support/CCArray.h new file mode 100755 index 0000000..0c7b2b8 --- /dev/null +++ b/libs/cocos2d/Support/CCArray.h @@ -0,0 +1,106 @@ +/* + * cocos2d for iPhone: http://www.cocos2d-iphone.org + * + * Copyright (c) 2010 ForzeField Studios S.L. http://forzefield.com + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ + + +#import "ccCArray.h" + + +/** A faster alternative of NSArray. + CCArray uses internally a c-array. + @since v0.99.4 + */ + + +/** @def CCARRAY_FOREACH + A convience macro to iterate over a CCArray using. It is faster than the "fast enumeration" interface. + @since v0.99.4 + */ + +#define CCARRAY_FOREACH(__array__, __object__) \ +if (__array__ && __array__->data->num > 0) \ +for(id *__arr__ = __array__->data->arr, *end = __array__->data->arr + __array__->data->num-1; \ + __arr__ <= end && ((__object__ = *__arr__) != nil || true); \ + __arr__++) + +@interface CCArray : NSObject +{ + @public ccArray *data; +} + ++ (id) array; ++ (id) arrayWithCapacity:(NSUInteger)capacity; ++ (id) arrayWithArray:(CCArray*)otherArray; ++ (id) arrayWithNSArray:(NSArray*)otherArray; + + +- (id) initWithCapacity:(NSUInteger)capacity; +- (id) initWithArray:(CCArray*)otherArray; +- (id) initWithNSArray:(NSArray*)otherArray; + + +// Querying an Array + +- (NSUInteger) count; +- (NSUInteger) capacity; +- (NSUInteger) indexOfObject:(id)object; +- (id) objectAtIndex:(NSUInteger)index; +- (BOOL) containsObject:(id)object; +- (id) randomObject; +- (id) lastObject; +- (NSArray*) getNSArray; + + +// Adding Objects + +- (void) addObject:(id)object; +- (void) addObjectsFromArray:(CCArray*)otherArray; +- (void) addObjectsFromNSArray:(NSArray*)otherArray; +- (void) insertObject:(id)object atIndex:(NSUInteger)index; + + +// Removing Objects + +- (void) removeLastObject; +- (void) removeObject:(id)object; +- (void) removeObjectAtIndex:(NSUInteger)index; +- (void) removeObjectsInArray:(CCArray*)otherArray; +- (void) removeAllObjects; +- (void) fastRemoveObject:(id)object; +- (void) fastRemoveObjectAtIndex:(NSUInteger)index; + + +// Rearranging Content + +- (void) exchangeObject:(id)object1 withObject:(id)object2; +- (void) exchangeObjectAtIndex:(NSUInteger)index1 withObjectAtIndex:(NSUInteger)index2; +- (void) reverseObjects; +- (void) reduceMemoryFootprint; + +// Sending Messages to Elements + +- (void) makeObjectsPerformSelector:(SEL)aSelector; +- (void) makeObjectsPerformSelector:(SEL)aSelector withObject:(id)object; + + +@end diff --git a/libs/cocos2d/Support/CCArray.m b/libs/cocos2d/Support/CCArray.m new file mode 100755 index 0000000..a48a5f3 --- /dev/null +++ b/libs/cocos2d/Support/CCArray.m @@ -0,0 +1,290 @@ +/* + * cocos2d for iPhone: http://www.cocos2d-iphone.org + * + * Copyright (c) 2010 ForzeField Studios S.L. http://forzefield.com + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + */ + +#import "CCArray.h" +#import "../ccMacros.h" + + +@implementation CCArray + ++ (id) array +{ + return [[[self alloc] init] autorelease]; +} + ++ (id) arrayWithCapacity:(NSUInteger)capacity +{ + return [[[self alloc] initWithCapacity:capacity] autorelease]; +} + ++ (id) arrayWithArray:(CCArray*)otherArray +{ + return [[(CCArray*)[self alloc] initWithArray:otherArray] autorelease]; +} + ++ (id) arrayWithNSArray:(NSArray*)otherArray +{ + return [[(CCArray*)[self alloc] initWithNSArray:otherArray] autorelease]; +} + +- (id) init +{ + self = [self initWithCapacity:2]; + return self; +} + +- (id) initWithCapacity:(NSUInteger)capacity +{ + self = [super init]; + if (self != nil) { + data = ccArrayNew(capacity); + } + return self; +} + +- (id) initWithArray:(CCArray*)otherArray +{ + self = [self initWithCapacity:otherArray->data->num]; + if (self != nil) { + [self addObjectsFromArray:otherArray]; + } + return self; +} + +- (id) initWithNSArray:(NSArray*)otherArray +{ + self = [self initWithCapacity:otherArray.count]; + if (self != nil) { + [self addObjectsFromNSArray:otherArray]; + } + return self; +} + +- (id) initWithCoder:(NSCoder*)coder +{ + self = [self initWithNSArray:[coder decodeObjectForKey:@"nsarray"]]; + return self; +} + + +#pragma mark Querying an Array + +- (NSUInteger) count +{ + return data->num; +} + +- (NSUInteger) capacity +{ + return data->max; +} + +- (NSUInteger) indexOfObject:(id)object +{ + return ccArrayGetIndexOfObject(data, object); +} + +- (id) objectAtIndex:(NSUInteger)index +{ + NSAssert2( index < data->num, @"index out of range in objectAtIndex(%d), index %i", data->num, index ); + + return data->arr[index]; +} + +- (BOOL) containsObject:(id)object +{ + return ccArrayContainsObject(data, object); +} + +- (id) lastObject +{ + if( data->num > 0 ) + return data->arr[data->num-1]; + return nil; +} + +- (id) randomObject +{ + if(data->num==0) return nil; + return data->arr[(int)(data->num*CCRANDOM_0_1())]; +} + +- (NSArray*) getNSArray +{ + return [NSArray arrayWithObjects:data->arr count:data->num]; +} + + +#pragma mark Adding Objects + +- (void) addObject:(id)object +{ + ccArrayAppendObjectWithResize(data, object); +} + +- (void) addObjectsFromArray:(CCArray*)otherArray +{ + ccArrayAppendArrayWithResize(data, otherArray->data); +} + +- (void) addObjectsFromNSArray:(NSArray*)otherArray +{ + ccArrayEnsureExtraCapacity(data, otherArray.count); + for(id object in otherArray) + ccArrayAppendObject(data, object); +} + +- (void) insertObject:(id)object atIndex:(NSUInteger)index +{ + ccArrayInsertObjectAtIndex(data, object, index); +} + + +#pragma mark Removing Objects + +- (void) removeObject:(id)object +{ + ccArrayRemoveObject(data, object); +} + +- (void) removeObjectAtIndex:(NSUInteger)index +{ + ccArrayRemoveObjectAtIndex(data, index); +} + +- (void) fastRemoveObject:(id)object +{ + ccArrayFastRemoveObject(data, object); +} + +- (void) fastRemoveObjectAtIndex:(NSUInteger)index +{ + ccArrayFastRemoveObjectAtIndex(data, index); +} + +- (void) removeObjectsInArray:(CCArray*)otherArray +{ + ccArrayRemoveArray(data, otherArray->data); +} + +- (void) removeLastObject +{ + NSAssert( data->num > 0, @"no objects added" ); + + ccArrayRemoveObjectAtIndex(data, data->num-1); +} + +- (void) removeAllObjects +{ + ccArrayRemoveAllObjects(data); +} + + +#pragma mark Rearranging Content + +- (void) exchangeObject:(id)object1 withObject:(id)object2 +{ + NSUInteger index1 = ccArrayGetIndexOfObject(data, object1); + if(index1 == NSNotFound) return; + NSUInteger index2 = ccArrayGetIndexOfObject(data, object2); + if(index2 == NSNotFound) return; + + ccArraySwapObjectsAtIndexes(data, index1, index2); +} + +- (void) exchangeObjectAtIndex:(NSUInteger)index1 withObjectAtIndex:(NSUInteger)index2 +{ + ccArraySwapObjectsAtIndexes(data, index1, index2); +} + +- (void) reverseObjects +{ + if (data->num > 1) + { + //floor it since in case of a oneven number the number of swaps stays the same + int count = (int) floorf(data->num/2.f); + NSUInteger maxIndex = data->num - 1; + + for (int i = 0; i < count ; i++) + { + ccArraySwapObjectsAtIndexes(data, i, maxIndex); + maxIndex--; + } + } +} + +- (void) reduceMemoryFootprint +{ + ccArrayShrink(data); +} + +#pragma mark Sending Messages to Elements + +- (void) makeObjectsPerformSelector:(SEL)aSelector +{ + ccArrayMakeObjectsPerformSelector(data, aSelector); +} + +- (void) makeObjectsPerformSelector:(SEL)aSelector withObject:(id)object +{ + ccArrayMakeObjectsPerformSelectorWithObject(data, aSelector, object); +} + + +#pragma mark CCArray - NSFastEnumeration protocol + +- (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id *)stackbuf count:(NSUInteger)len +{ + if(state->state == 1) return 0; + + state->mutationsPtr = (unsigned long *)self; + state->itemsPtr = &data->arr[0]; + state->state = 1; + return data->num; +} + + +#pragma mark CCArray - NSCopying protocol + +- (id)copyWithZone:(NSZone *)zone +{ + NSArray *nsArray = [self getNSArray]; + CCArray *newArray = [[[self class] allocWithZone:zone] initWithNSArray:nsArray]; + return newArray; +} + +- (void) encodeWithCoder:(NSCoder *)coder +{ + [coder encodeObject:[self getNSArray] forKey:@"nsarray"]; +} + +#pragma mark + +- (void) dealloc +{ + ccArrayFree(data); + [super dealloc]; +} + +@end diff --git a/libs/cocos2d/Support/CCFileUtils.h b/libs/cocos2d/Support/CCFileUtils.h new file mode 100755 index 0000000..0455202 --- /dev/null +++ b/libs/cocos2d/Support/CCFileUtils.h @@ -0,0 +1,62 @@ +/* + * cocos2d for iPhone: http://www.cocos2d-iphone.org + * + * Copyright (c) 2008-2010 Ricardo Quesada + * Copyright (c) 2011 Zynga Inc. + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + * + */ + + +#import + + +/** Helper class to handle file operations */ +@interface CCFileUtils : NSObject +{ +} + +/** Returns the fullpath of an filename. + + If this method is when Retina Display is enabled, then the + Retina Display suffix will be appended to the file (See ccConfig.h). + + If the Retina Display image doesn't exist, then it will return the "non-Retina Display" image + + */ ++(NSString*) fullPathFromRelativePath:(NSString*) relPath; +@end + +/** loads a file into memory. + the caller should release the allocated buffer. + + @returns the size of the allocated buffer + @since v0.99.5 + */ +NSInteger ccLoadFileIntoMemory(const char *filename, unsigned char **out); + + +/** removes the HD suffix from a path + + @returns NSString * without the HD suffix + @since v0.99.5 + */ +NSString *ccRemoveHDSuffixFromFile( NSString *path ); + diff --git a/libs/cocos2d/Support/CCFileUtils.m b/libs/cocos2d/Support/CCFileUtils.m new file mode 100755 index 0000000..6d33799 --- /dev/null +++ b/libs/cocos2d/Support/CCFileUtils.m @@ -0,0 +1,169 @@ +/* + * cocos2d for iPhone: http://www.cocos2d-iphone.org + * + * Copyright (c) 2008-2010 Ricardo Quesada + * Copyright (c) 2011 Zynga Inc. + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + * + */ + + +#import +#import "CCFileUtils.h" +#import "../CCConfiguration.h" +#import "../ccMacros.h" +#import "../ccConfig.h" + +static NSFileManager *__localFileManager=nil; + +// +NSInteger ccLoadFileIntoMemory(const char *filename, unsigned char **out) +{ + NSCAssert( out, @"ccLoadFileIntoMemory: invalid 'out' parameter"); + NSCAssert( &*out, @"ccLoadFileIntoMemory: invalid 'out' parameter"); + + size_t size = 0; + FILE *f = fopen(filename, "rb"); + if( !f ) { + *out = NULL; + return -1; + } + + fseek(f, 0, SEEK_END); + size = ftell(f); + fseek(f, 0, SEEK_SET); + + *out = malloc(size); + size_t read = fread(*out, 1, size, f); + if( read != size ) { + free(*out); + *out = NULL; + return -1; + } + + fclose(f); + + return size; +} + +NSString *ccRemoveHDSuffixFromFile( NSString *path ) +{ +#if CC_IS_RETINA_DISPLAY_SUPPORTED + + if( CC_CONTENT_SCALE_FACTOR() == 2 ) { + + NSString *name = [path lastPathComponent]; + + // check if path already has the suffix. + if( [name rangeOfString:CC_RETINA_DISPLAY_FILENAME_SUFFIX].location != NSNotFound ) { + + CCLOG(@"cocos2d: Filename(%@) contains %@ suffix. Removing it. See cocos2d issue #1040", path, CC_RETINA_DISPLAY_FILENAME_SUFFIX); + + NSString *newLastname = [name stringByReplacingOccurrencesOfString:CC_RETINA_DISPLAY_FILENAME_SUFFIX withString:@""]; + + NSString *pathWithoutLastname = [path stringByDeletingLastPathComponent]; + return [pathWithoutLastname stringByAppendingPathComponent:newLastname]; + } + } + +#endif // CC_IS_RETINA_DISPLAY_SUPPORTED + + return path; + +} + + +@implementation CCFileUtils + ++(void) initialize +{ + if( self == [CCFileUtils class] ) + __localFileManager = [[NSFileManager alloc] init]; +} + ++(NSString*) getDoubleResolutionImage:(NSString*)path +{ +#if CC_IS_RETINA_DISPLAY_SUPPORTED + + if( CC_CONTENT_SCALE_FACTOR() == 2 ) + { + + NSString *pathWithoutExtension = [path stringByDeletingPathExtension]; + NSString *name = [pathWithoutExtension lastPathComponent]; + + // check if path already has the suffix. + if( [name rangeOfString:CC_RETINA_DISPLAY_FILENAME_SUFFIX].location != NSNotFound ) { + + CCLOG(@"cocos2d: WARNING Filename(%@) already has the suffix %@. Using it.", name, CC_RETINA_DISPLAY_FILENAME_SUFFIX); + return path; + } + + + NSString *extension = [path pathExtension]; + + if( [extension isEqualToString:@"ccz"] || [extension isEqualToString:@"gz"] ) + { + // All ccz / gz files should be in the format filename.xxx.ccz + // so we need to pull off the .xxx part of the extension as well + extension = [NSString stringWithFormat:@"%@.%@", [pathWithoutExtension pathExtension], extension]; + pathWithoutExtension = [pathWithoutExtension stringByDeletingPathExtension]; + } + + + NSString *retinaName = [pathWithoutExtension stringByAppendingString:CC_RETINA_DISPLAY_FILENAME_SUFFIX]; + retinaName = [retinaName stringByAppendingPathExtension:extension]; + + if( [__localFileManager fileExistsAtPath:retinaName] ) + return retinaName; + + CCLOG(@"cocos2d: CCFileUtils: Warning HD file not found: %@", [retinaName lastPathComponent] ); + } + +#endif // CC_IS_RETINA_DISPLAY_SUPPORTED + + return path; +} + ++(NSString*) fullPathFromRelativePath:(NSString*) relPath +{ + NSAssert(relPath != nil, @"CCFileUtils: Invalid path"); + + NSString *fullpath = nil; + + // only if it is not an absolute path + if( ! [relPath isAbsolutePath] ) + { + NSString *file = [relPath lastPathComponent]; + NSString *imageDirectory = [relPath stringByDeletingLastPathComponent]; + + fullpath = [[NSBundle mainBundle] pathForResource:file + ofType:nil + inDirectory:imageDirectory]; + } + + if (fullpath == nil) + fullpath = relPath; + + fullpath = [self getDoubleResolutionImage:fullpath]; + + return fullpath; +} + +@end diff --git a/libs/cocos2d/Support/CCProfiling.h b/libs/cocos2d/Support/CCProfiling.h new file mode 100755 index 0000000..b241fb9 --- /dev/null +++ b/libs/cocos2d/Support/CCProfiling.h @@ -0,0 +1,53 @@ +/* + * cocos2d for iPhone: http://www.cocos2d-iphone.org + * + * Copyright (c) 2010 Stuart Carnie + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + * + */ + + +#import +#import + +@class CCProfilingTimer; + +@interface CCProfiler : NSObject { + NSMutableArray* activeTimers; +} + ++ (CCProfiler*)sharedProfiler; ++ (CCProfilingTimer*)timerWithName:(NSString*)timerName andInstance:(id)instance; ++ (void)releaseTimer:(CCProfilingTimer*)timer; +- (void)displayTimers; + +@end + + +@interface CCProfilingTimer : NSObject { + NSString* name; + struct timeval startTime; + double averageTime; +} + +@end + +extern void CCProfilingBeginTimingBlock(CCProfilingTimer* timer); +extern void CCProfilingEndTimingBlock(CCProfilingTimer* timer); diff --git a/libs/cocos2d/Support/CCProfiling.m b/libs/cocos2d/Support/CCProfiling.m new file mode 100755 index 0000000..13c8c81 --- /dev/null +++ b/libs/cocos2d/Support/CCProfiling.m @@ -0,0 +1,117 @@ +/* + * cocos2d for iPhone: http://www.cocos2d-iphone.org + * + * Copyright (c) 2010 Stuart Carnie + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + * + */ + +#import "../ccConfig.h" + +#if CC_ENABLE_PROFILERS + +#import "CCProfiling.h" + +@interface CCProfilingTimer() +- (id)initWithName:(NSString*)timerName andInstance:(id)instance; +@end + +@implementation CCProfiler + +static CCProfiler* g_sharedProfiler; + ++ (CCProfiler*)sharedProfiler { + if (!g_sharedProfiler) + g_sharedProfiler = [[CCProfiler alloc] init]; + + return g_sharedProfiler; +} + ++ (CCProfilingTimer*)timerWithName:(NSString*)timerName andInstance:(id)instance { + CCProfiler* p = [CCProfiler sharedProfiler]; + CCProfilingTimer* t = [[CCProfilingTimer alloc] initWithName:timerName andInstance:instance]; + [p->activeTimers addObject:t]; + [t release]; + return t; +} + ++ (void)releaseTimer:(CCProfilingTimer*)timer { + CCProfiler* p = [CCProfiler sharedProfiler]; + [p->activeTimers removeObject:timer]; +} + +- (id)init { + if (!(self = [super init])) return nil; + + activeTimers = [[NSMutableArray alloc] init]; + + return self; +} + +- (void)dealloc { + [activeTimers release]; + [super dealloc]; +} + +- (void)displayTimers { + for (id timer in activeTimers) { + printf("%s\n", [[timer description] cStringUsingEncoding:[NSString defaultCStringEncoding]]); + } +} + +@end + +@implementation CCProfilingTimer + +- (id)initWithName:(NSString*)timerName andInstance:(id)instance { + if (!(self = [super init])) return nil; + + name = [[NSString stringWithFormat:@"%@ (0x%.8x)", timerName, instance] retain]; + + return self; +} + +- (void)dealloc { + [name release]; + [super dealloc]; +} + +- (NSString*)description { + return [NSString stringWithFormat:@"%@ : avg time, %fms", name, averageTime]; +} + +void CCProfilingBeginTimingBlock(CCProfilingTimer* timer) { + gettimeofday(&timer->startTime, NULL); +} + +typedef unsigned int uint32; +void CCProfilingEndTimingBlock(CCProfilingTimer* timer) { + struct timeval currentTime; + gettimeofday(¤tTime, NULL); + timersub(¤tTime, &timer->startTime, ¤tTime); + double duration = currentTime.tv_sec * 1000.0 + currentTime.tv_usec / 1000.0; + + // return in milliseconds + timer->averageTime = (timer->averageTime + duration) / 2.0f; +} + +@end + +#endif diff --git a/libs/cocos2d/Support/CGPointExtension.h b/libs/cocos2d/Support/CGPointExtension.h new file mode 100755 index 0000000..96edeb7 --- /dev/null +++ b/libs/cocos2d/Support/CGPointExtension.h @@ -0,0 +1,334 @@ +/* cocos2d for iPhone + * http://www.cocos2d-iphone.org + * + * Copyright (c) 2007 Scott Lembcke + * + * Copyright (c) 2010 Lam Pham + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +/* + * Some of the functions were based on Chipmunk's cpVect.h. + */ + +/** + @file + CGPoint extensions based on Chipmunk's cpVect file. + These extensions work both with CGPoint and cpVect. + + The "ccp" prefix means: "CoCos2d Point" + + Examples: + - ccpAdd( ccp(1,1), ccp(2,2) ); // preferred cocos2d way + - ccpAdd( CGPointMake(1,1), CGPointMake(2,2) ); // also ok but more verbose + + - cpvadd( cpv(1,1), cpv(2,2) ); // way of the chipmunk + - ccpAdd( cpv(1,1), cpv(2,2) ); // mixing chipmunk and cocos2d (avoid) + - cpvadd( CGPointMake(1,1), CGPointMake(2,2) ); // mixing chipmunk and CG (avoid) + */ + +#import + +#ifdef __IPHONE_OS_VERSION_MAX_ALLOWED +#import +#elif defined(__MAC_OS_X_VERSION_MAX_ALLOWED) +#import +#endif + +#import +#import + +#ifdef __cplusplus +extern "C" { +#endif + +/** Helper macro that creates a CGPoint + @return CGPoint + @since v0.7.2 + */ +#define ccp(__X__,__Y__) CGPointMake(__X__,__Y__) + + +/** Returns opposite of point. + @return CGPoint + @since v0.7.2 + */ +static inline CGPoint +ccpNeg(const CGPoint v) +{ + return ccp(-v.x, -v.y); +} + +/** Calculates sum of two points. + @return CGPoint + @since v0.7.2 + */ +static inline CGPoint +ccpAdd(const CGPoint v1, const CGPoint v2) +{ + return ccp(v1.x + v2.x, v1.y + v2.y); +} + +/** Calculates difference of two points. + @return CGPoint + @since v0.7.2 + */ +static inline CGPoint +ccpSub(const CGPoint v1, const CGPoint v2) +{ + return ccp(v1.x - v2.x, v1.y - v2.y); +} + +/** Returns point multiplied by given factor. + @return CGPoint + @since v0.7.2 + */ +static inline CGPoint +ccpMult(const CGPoint v, const CGFloat s) +{ + return ccp(v.x*s, v.y*s); +} + +/** Calculates midpoint between two points. + @return CGPoint + @since v0.7.2 + */ +static inline CGPoint +ccpMidpoint(const CGPoint v1, const CGPoint v2) +{ + return ccpMult(ccpAdd(v1, v2), 0.5f); +} + +/** Calculates dot product of two points. + @return CGFloat + @since v0.7.2 + */ +static inline CGFloat +ccpDot(const CGPoint v1, const CGPoint v2) +{ + return v1.x*v2.x + v1.y*v2.y; +} + +/** Calculates cross product of two points. + @return CGFloat + @since v0.7.2 + */ +static inline CGFloat +ccpCross(const CGPoint v1, const CGPoint v2) +{ + return v1.x*v2.y - v1.y*v2.x; +} + +/** Calculates perpendicular of v, rotated 90 degrees counter-clockwise -- cross(v, perp(v)) >= 0 + @return CGPoint + @since v0.7.2 + */ +static inline CGPoint +ccpPerp(const CGPoint v) +{ + return ccp(-v.y, v.x); +} + +/** Calculates perpendicular of v, rotated 90 degrees clockwise -- cross(v, rperp(v)) <= 0 + @return CGPoint + @since v0.7.2 + */ +static inline CGPoint +ccpRPerp(const CGPoint v) +{ + return ccp(v.y, -v.x); +} + +/** Calculates the projection of v1 over v2. + @return CGPoint + @since v0.7.2 + */ +static inline CGPoint +ccpProject(const CGPoint v1, const CGPoint v2) +{ + return ccpMult(v2, ccpDot(v1, v2)/ccpDot(v2, v2)); +} + +/** Rotates two points. + @return CGPoint + @since v0.7.2 + */ +static inline CGPoint +ccpRotate(const CGPoint v1, const CGPoint v2) +{ + return ccp(v1.x*v2.x - v1.y*v2.y, v1.x*v2.y + v1.y*v2.x); +} + +/** Unrotates two points. + @return CGPoint + @since v0.7.2 + */ +static inline CGPoint +ccpUnrotate(const CGPoint v1, const CGPoint v2) +{ + return ccp(v1.x*v2.x + v1.y*v2.y, v1.y*v2.x - v1.x*v2.y); +} + +/** Calculates the square length of a CGPoint (not calling sqrt() ) + @return CGFloat + @since v0.7.2 + */ +static inline CGFloat +ccpLengthSQ(const CGPoint v) +{ + return ccpDot(v, v); +} + +/** Calculates distance between point an origin + @return CGFloat + @since v0.7.2 + */ +CGFloat ccpLength(const CGPoint v); + +/** Calculates the distance between two points + @return CGFloat + @since v0.7.2 + */ +CGFloat ccpDistance(const CGPoint v1, const CGPoint v2); + +/** Returns point multiplied to a length of 1. + @return CGPoint + @since v0.7.2 + */ +CGPoint ccpNormalize(const CGPoint v); + +/** Converts radians to a normalized vector. + @return CGPoint + @since v0.7.2 + */ +CGPoint ccpForAngle(const CGFloat a); + +/** Converts a vector to radians. + @return CGFloat + @since v0.7.2 + */ +CGFloat ccpToAngle(const CGPoint v); + + +/** Clamp a value between from and to. + @since v0.99.1 + */ +float clampf(float value, float min_inclusive, float max_inclusive); + +/** Clamp a point between from and to. + @since v0.99.1 + */ +CGPoint ccpClamp(CGPoint p, CGPoint from, CGPoint to); + +/** Quickly convert CGSize to a CGPoint + @since v0.99.1 + */ +CGPoint ccpFromSize(CGSize s); + +/** Run a math operation function on each point component + * absf, fllorf, ceilf, roundf + * any function that has the signature: float func(float); + * For example: let's try to take the floor of x,y + * ccpCompOp(p,floorf); + @since v0.99.1 + */ +CGPoint ccpCompOp(CGPoint p, float (*opFunc)(float)); + +/** Linear Interpolation between two points a and b + @returns + alpha == 0 ? a + alpha == 1 ? b + otherwise a value between a..b + @since v0.99.1 + */ +CGPoint ccpLerp(CGPoint a, CGPoint b, float alpha); + + +/** @returns if points have fuzzy equality which means equal with some degree of variance. + @since v0.99.1 + */ +BOOL ccpFuzzyEqual(CGPoint a, CGPoint b, float variance); + + +/** Multiplies a nd b components, a.x*b.x, a.y*b.y + @returns a component-wise multiplication + @since v0.99.1 + */ +CGPoint ccpCompMult(CGPoint a, CGPoint b); + +/** @returns the signed angle in radians between two vector directions + @since v0.99.1 + */ +float ccpAngleSigned(CGPoint a, CGPoint b); + +/** @returns the angle in radians between two vector directions + @since v0.99.1 +*/ +float ccpAngle(CGPoint a, CGPoint b); + +/** Rotates a point counter clockwise by the angle around a pivot + @param v is the point to rotate + @param pivot is the pivot, naturally + @param angle is the angle of rotation cw in radians + @returns the rotated point + @since v0.99.1 + */ +CGPoint ccpRotateByAngle(CGPoint v, CGPoint pivot, float angle); + +/** A general line-line intersection test + @param p1 + is the startpoint for the first line P1 = (p1 - p2) + @param p2 + is the endpoint for the first line P1 = (p1 - p2) + @param p3 + is the startpoint for the second line P2 = (p3 - p4) + @param p4 + is the endpoint for the second line P2 = (p3 - p4) + @param s + is the range for a hitpoint in P1 (pa = p1 + s*(p2 - p1)) + @param t + is the range for a hitpoint in P3 (pa = p2 + t*(p4 - p3)) + @return bool + indicating successful intersection of a line + note that to truly test intersection for segments we have to make + sure that s & t lie within [0..1] and for rays, make sure s & t > 0 + the hit point is p3 + t * (p4 - p3); + the hit point also is p1 + s * (p2 - p1); + @since v0.99.1 + */ +BOOL ccpLineIntersect(CGPoint p1, CGPoint p2, + CGPoint p3, CGPoint p4, + float *s, float *t); + +/* + ccpSegmentIntersect returns YES if Segment A-B intersects with segment C-D + @since v1.0.0 + */ +BOOL ccpSegmentIntersect(CGPoint A, CGPoint B, CGPoint C, CGPoint D); + +/* + ccpIntersectPoint returns the intersection point of line A-B, C-D + @since v1.0.0 + */ +CGPoint ccpIntersectPoint(CGPoint A, CGPoint B, CGPoint C, CGPoint D); + +#ifdef __cplusplus +} +#endif diff --git a/libs/cocos2d/Support/CGPointExtension.m b/libs/cocos2d/Support/CGPointExtension.m new file mode 100755 index 0000000..b06859d --- /dev/null +++ b/libs/cocos2d/Support/CGPointExtension.m @@ -0,0 +1,196 @@ +/* cocos2d for iPhone + * http://www.cocos2d-iphone.org + * + * Copyright (c) 2007 Scott Lembcke + * + * Copyright (c) 2010 Lam Pham + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +#include "stdio.h" +#include "math.h" + +#import "../ccMacros.h" // CC_SWAP +#include "CGPointExtension.h" + +#define kCGPointEpsilon FLT_EPSILON + +CGFloat +ccpLength(const CGPoint v) +{ + return sqrtf(ccpLengthSQ(v)); +} + +CGFloat +ccpDistance(const CGPoint v1, const CGPoint v2) +{ + return ccpLength(ccpSub(v1, v2)); +} + +CGPoint +ccpNormalize(const CGPoint v) +{ + return ccpMult(v, 1.0f/ccpLength(v)); +} + +CGPoint +ccpForAngle(const CGFloat a) +{ + return ccp(cosf(a), sinf(a)); +} + +CGFloat +ccpToAngle(const CGPoint v) +{ + return atan2f(v.y, v.x); +} + +CGPoint ccpLerp(CGPoint a, CGPoint b, float alpha) +{ + return ccpAdd(ccpMult(a, 1.f - alpha), ccpMult(b, alpha)); +} + +float clampf(float value, float min_inclusive, float max_inclusive) +{ + if (min_inclusive > max_inclusive) { + CC_SWAP(min_inclusive,max_inclusive); + } + return value < min_inclusive ? min_inclusive : value < max_inclusive? value : max_inclusive; +} + +CGPoint ccpClamp(CGPoint p, CGPoint min_inclusive, CGPoint max_inclusive) +{ + return ccp(clampf(p.x,min_inclusive.x,max_inclusive.x), clampf(p.y, min_inclusive.y, max_inclusive.y)); +} + +CGPoint ccpFromSize(CGSize s) +{ + return ccp(s.width, s.height); +} + +CGPoint ccpCompOp(CGPoint p, float (*opFunc)(float)) +{ + return ccp(opFunc(p.x), opFunc(p.y)); +} + +BOOL ccpFuzzyEqual(CGPoint a, CGPoint b, float var) +{ + if(a.x - var <= b.x && b.x <= a.x + var) + if(a.y - var <= b.y && b.y <= a.y + var) + return true; + return false; +} + +CGPoint ccpCompMult(CGPoint a, CGPoint b) +{ + return ccp(a.x * b.x, a.y * b.y); +} + +float ccpAngleSigned(CGPoint a, CGPoint b) +{ + CGPoint a2 = ccpNormalize(a); + CGPoint b2 = ccpNormalize(b); + float angle = atan2f(a2.x * b2.y - a2.y * b2.x, ccpDot(a2, b2)); + if( fabs(angle) < kCGPointEpsilon ) return 0.f; + return angle; +} + +CGPoint ccpRotateByAngle(CGPoint v, CGPoint pivot, float angle) +{ + CGPoint r = ccpSub(v, pivot); + float cosa = cosf(angle), sina = sinf(angle); + float t = r.x; + r.x = t*cosa - r.y*sina + pivot.x; + r.y = t*sina + r.y*cosa + pivot.y; + return r; +} + + +BOOL ccpSegmentIntersect(CGPoint A, CGPoint B, CGPoint C, CGPoint D) +{ + float S, T; + + if( ccpLineIntersect(A, B, C, D, &S, &T ) + && (S >= 0.0f && S <= 1.0f && T >= 0.0f && T <= 1.0f) ) + return YES; + + return NO; +} + +CGPoint ccpIntersectPoint(CGPoint A, CGPoint B, CGPoint C, CGPoint D) +{ + float S, T; + + if( ccpLineIntersect(A, B, C, D, &S, &T) ) { + // Point of intersection + CGPoint P; + P.x = A.x + S * (B.x - A.x); + P.y = A.y + S * (B.y - A.y); + return P; + } + + return CGPointZero; +} + +BOOL ccpLineIntersect(CGPoint A, CGPoint B, + CGPoint C, CGPoint D, + float *S, float *T) +{ + // FAIL: Line undefined + if ( (A.x==B.x && A.y==B.y) || (C.x==D.x && C.y==D.y) ) return NO; + + const float BAx = B.x - A.x; + const float BAy = B.y - A.y; + const float DCx = D.x - C.x; + const float DCy = D.y - C.y; + const float ACx = A.x - C.x; + const float ACy = A.y - C.y; + + const float denom = DCy*BAx - DCx*BAy; + + *S = DCx*ACy - DCy*ACx; + *T = BAx*ACy - BAy*ACx; + + if (denom == 0) { + if (*S == 0 || *T == 0) { + // Lines incident + return YES; + } + // Lines parallel and not incident + return NO; + } + + *S = *S / denom; + *T = *T / denom; + + // Point of intersection + // CGPoint P; + // P.x = A.x + *S * (B.x - A.x); + // P.y = A.y + *S * (B.y - A.y); + + return YES; +} + +float ccpAngle(CGPoint a, CGPoint b) +{ + float angle = acosf(ccpDot(ccpNormalize(a), ccpNormalize(b))); + if( fabs(angle) < kCGPointEpsilon ) return 0.f; + return angle; +} diff --git a/libs/cocos2d/Support/OpenGL_Internal.h b/libs/cocos2d/Support/OpenGL_Internal.h new file mode 100755 index 0000000..4789683 --- /dev/null +++ b/libs/cocos2d/Support/OpenGL_Internal.h @@ -0,0 +1,80 @@ +/* + +===== IMPORTANT ===== + +This is sample code demonstrating API, technology or techniques in development. +Although this sample code has been reviewed for technical accuracy, it is not +final. Apple is supplying this information to help you plan for the adoption of +the technologies and programming interfaces described herein. This information +is subject to change, and software implemented based on this sample code should +be tested with final operating system software and final documentation. Newer +versions of this sample code may be provided with future seeds of the API or +technology. For information about updates to this and other developer +documentation, view the New & Updated sidebars in subsequent documentation +seeds. + +===================== + +File: OpenGL_Internal.h +Abstract: This file is included for support purposes and isn't necessary for +understanding this sample. + +Version: 1.0 + +Disclaimer: IMPORTANT: This Apple software is supplied to you by Apple Inc. +("Apple") in consideration of your agreement to the following terms, and your +use, installation, modification or redistribution of this Apple software +constitutes acceptance of these terms. If you do not agree with these terms, +please do not use, install, modify or redistribute this Apple software. + +In consideration of your agreement to abide by the following terms, and subject +to these terms, Apple grants you a personal, non-exclusive license, under +Apple's copyrights in this original Apple software (the "Apple Software"), to +use, reproduce, modify and redistribute the Apple Software, with or without +modifications, in source and/or binary forms; provided that if you redistribute +the Apple Software in its entirety and without modifications, you must retain +this notice and the following text and disclaimers in all such redistributions +of the Apple Software. +Neither the name, trademarks, service marks or logos of Apple Inc. may be used +to endorse or promote products derived from the Apple Software without specific +prior written permission from Apple. Except as expressly stated in this notice, +no other rights or licenses, express or implied, are granted by Apple herein, +including but not limited to any patent rights that may be infringed by your +derivative works or by other works in which the Apple Software may be +incorporated. + +The Apple Software is provided by Apple on an "AS IS" basis. APPLE MAKES NO +WARRANTIES, EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION THE IMPLIED +WARRANTIES OF NON-INFRINGEMENT, MERCHANTABILITY AND FITNESS FOR A PARTICULAR +PURPOSE, REGARDING THE APPLE SOFTWARE OR ITS USE AND OPERATION ALONE OR IN +COMBINATION WITH YOUR PRODUCTS. + +IN NO EVENT SHALL APPLE BE LIABLE FOR ANY SPECIAL, INDIRECT, INCIDENTAL OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE +GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +ARISING IN ANY WAY OUT OF THE USE, REPRODUCTION, MODIFICATION AND/OR +DISTRIBUTION OF THE APPLE SOFTWARE, HOWEVER CAUSED AND WHETHER UNDER THEORY OF +CONTRACT, TORT (INCLUDING NEGLIGENCE), STRICT LIABILITY OR OTHERWISE, EVEN IF +APPLE HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +Copyright (C) 2008 Apple Inc. All Rights Reserved. + +*/ + +/* Generic error reporting */ +#define REPORT_ERROR(__FORMAT__, ...) printf("%s: %s\n", __FUNCTION__, [[NSString stringWithFormat:__FORMAT__, __VA_ARGS__] UTF8String]) + +/* EAGL and GL functions calling wrappers that log on error */ +#define CALL_EAGL_FUNCTION(__FUNC__, ...) ({ EAGLError __error = __FUNC__( __VA_ARGS__ ); if(__error != kEAGLErrorSuccess) printf("%s() called from %s returned error %i\n", #__FUNC__, __FUNCTION__, __error); (__error ? NO : YES); }) +//#define CHECK_GL_ERROR() ({ GLenum __error = glGetError(); if(__error) printf("OpenGL error 0x%04X in %s\n", __error, __FUNCTION__); (__error ? NO : YES); }) +#define CHECK_GL_ERROR() ({ GLenum __error = glGetError(); if(__error) printf("OpenGL error 0x%04X in %s\n", __error, __FUNCTION__); }) + +/* Optional delegate methods support */ +#ifndef __DELEGATE_IVAR__ +#define __DELEGATE_IVAR__ _delegate +#endif +#ifndef __DELEGATE_METHODS_IVAR__ +#define __DELEGATE_METHODS_IVAR__ _delegateMethods +#endif +#define TEST_DELEGATE_METHOD_BIT(__BIT__) (self->__DELEGATE_METHODS_IVAR__ & (1 << __BIT__)) +#define SET_DELEGATE_METHOD_BIT(__BIT__, __NAME__) { if([self->__DELEGATE_IVAR__ respondsToSelector:@selector(__NAME__)]) self->__DELEGATE_METHODS_IVAR__ |= (1 << __BIT__); else self->__DELEGATE_METHODS_IVAR__ &= ~(1 << __BIT__); } diff --git a/libs/cocos2d/Support/TGAlib.h b/libs/cocos2d/Support/TGAlib.h new file mode 100755 index 0000000..247084e --- /dev/null +++ b/libs/cocos2d/Support/TGAlib.h @@ -0,0 +1,55 @@ +// +// TGA lib for cocos2d-iphone +// +// sources from: http://www.lighthouse3d.com/opengl/terrain/index.php3?tgasource +// + +//#ifndef TGA_LIB +//#define TGA_LIB + +/** + @file + TGA image support + */ + +enum { + TGA_OK, + TGA_ERROR_FILE_OPEN, + TGA_ERROR_READING_FILE, + TGA_ERROR_INDEXED_COLOR, + TGA_ERROR_MEMORY, + TGA_ERROR_COMPRESSED_FILE, +}; + +/** TGA format */ +typedef struct sImageTGA { + int status; + unsigned char type, pixelDepth; + + /** map width */ + short int width; + + /** map height */ + short int height; + + /** raw data */ + unsigned char *imageData; + int flipped; +} tImageTGA; + +/// load the image header fields. We only keep those that matter! +void tgaLoadHeader(FILE *file, tImageTGA *info); + +/// loads the image pixels. You shouldn't call this function directly +void tgaLoadImageData(FILE *file, tImageTGA *info); + +/// this is the function to call when we want to load an image +tImageTGA * tgaLoad(const char *filename); + +// /converts RGB to greyscale +void tgaRGBtogreyscale(tImageTGA *info); + +/// releases the memory used for the image +void tgaDestroy(tImageTGA *info); + +//#endif // TGA_LIB diff --git a/libs/cocos2d/Support/TGAlib.m b/libs/cocos2d/Support/TGAlib.m new file mode 100755 index 0000000..11303b4 --- /dev/null +++ b/libs/cocos2d/Support/TGAlib.m @@ -0,0 +1,274 @@ +// +// TGA lib for cocos2d-iphone +// +// sources from: http://www.lighthouse3d.com/opengl/terrain/index.php3?tgasource +// +// TGA RLE compression support by Ernesto Corvi + +#include +#include +#include + +#import "TGAlib.h" + +void tgaLoadRLEImageData(FILE *file, tImageTGA *info); +void tgaFlipImage( tImageTGA *info ); + +// load the image header fields. We only keep those that matter! +void tgaLoadHeader(FILE *file, tImageTGA *info) { + unsigned char cGarbage; + short int iGarbage; + + fread(&cGarbage, sizeof(unsigned char), 1, file); + fread(&cGarbage, sizeof(unsigned char), 1, file); + + // type must be 2 or 3 + fread(&info->type, sizeof(unsigned char), 1, file); + + fread(&iGarbage, sizeof(short int), 1, file); + fread(&iGarbage, sizeof(short int), 1, file); + fread(&cGarbage, sizeof(unsigned char), 1, file); + fread(&iGarbage, sizeof(short int), 1, file); + fread(&iGarbage, sizeof(short int), 1, file); + + fread(&info->width, sizeof(short int), 1, file); + fread(&info->height, sizeof(short int), 1, file); + fread(&info->pixelDepth, sizeof(unsigned char), 1, file); + + fread(&cGarbage, sizeof(unsigned char), 1, file); + + info->flipped = 0; + if ( cGarbage & 0x20 ) info->flipped = 1; +} + +// loads the image pixels. You shouldn't call this function directly +void tgaLoadImageData(FILE *file, tImageTGA *info) { + + int mode,total,i; + unsigned char aux; + + // mode equal the number of components for each pixel + mode = info->pixelDepth / 8; + // total is the number of unsigned chars we'll have to read + total = info->height * info->width * mode; + + fread(info->imageData,sizeof(unsigned char),total,file); + + // mode=3 or 4 implies that the image is RGB(A). However TGA + // stores it as BGR(A) so we'll have to swap R and B. + if (mode >= 3) + for (i=0; i < total; i+= mode) { + aux = info->imageData[i]; + info->imageData[i] = info->imageData[i+2]; + info->imageData[i+2] = aux; + } +} + +// loads the RLE encoded image pixels. You shouldn't call this function directly +void tgaLoadRLEImageData(FILE *file, tImageTGA *info) +{ + unsigned int mode,total,i, index = 0; + unsigned char aux[4], runlength = 0; + unsigned int skip = 0, flag = 0; + + // mode equal the number of components for each pixel + mode = info->pixelDepth / 8; + // total is the number of unsigned chars we'll have to read + total = info->height * info->width; + + for( i = 0; i < total; i++ ) + { + // if we have a run length pending, run it + if ( runlength != 0 ) + { + // we do, update the run length count + runlength--; + skip = (flag != 0); + } + else + { + // otherwise, read in the run length token + if ( fread(&runlength,sizeof(unsigned char),1,file) != 1 ) + return; + + // see if it's a RLE encoded sequence + flag = runlength & 0x80; + if ( flag ) runlength -= 128; + skip = 0; + } + + // do we need to skip reading this pixel? + if ( !skip ) + { + // no, read in the pixel data + if ( fread(aux,sizeof(unsigned char),mode,file) != mode ) + return; + + // mode=3 or 4 implies that the image is RGB(A). However TGA + // stores it as BGR(A) so we'll have to swap R and B. + if ( mode >= 3 ) + { + unsigned char tmp; + + tmp = aux[0]; + aux[0] = aux[2]; + aux[2] = tmp; + } + } + + // add the pixel to our image + memcpy(&info->imageData[index], aux, mode); + index += mode; + } +} + +void tgaFlipImage( tImageTGA *info ) +{ + // mode equal the number of components for each pixel + int mode = info->pixelDepth / 8; + int rowbytes = info->width*mode; + unsigned char *row = (unsigned char *)malloc(rowbytes); + int y; + + if (row == NULL) return; + + for( y = 0; y < (info->height/2); y++ ) + { + memcpy(row, &info->imageData[y*rowbytes],rowbytes); + memcpy(&info->imageData[y*rowbytes], &info->imageData[(info->height-(y+1))*rowbytes], rowbytes); + memcpy(&info->imageData[(info->height-(y+1))*rowbytes], row, rowbytes); + } + + free(row); + info->flipped = 0; +} + +// this is the function to call when we want to load an image +tImageTGA * tgaLoad(const char *filename) { + + FILE *file; + tImageTGA *info; + int mode,total; + + // allocate memory for the info struct and check! + info = (tImageTGA *)malloc(sizeof(tImageTGA)); + if (info == NULL) + return(NULL); + + + // open the file for reading (binary mode) + file = fopen(filename, "rb"); + if (file == NULL) { + info->status = TGA_ERROR_FILE_OPEN; + return(info); + } + + // load the header + tgaLoadHeader(file,info); + + // check for errors when loading the header + if (ferror(file)) { + info->status = TGA_ERROR_READING_FILE; + fclose(file); + return(info); + } + + // check if the image is color indexed + if (info->type == 1) { + info->status = TGA_ERROR_INDEXED_COLOR; + fclose(file); + return(info); + } + // check for other types (compressed images) + if ((info->type != 2) && (info->type !=3) && (info->type !=10) ) { + info->status = TGA_ERROR_COMPRESSED_FILE; + fclose(file); + return(info); + } + + // mode equals the number of image components + mode = info->pixelDepth / 8; + // total is the number of unsigned chars to read + total = info->height * info->width * mode; + // allocate memory for image pixels + info->imageData = (unsigned char *)malloc(sizeof(unsigned char) * + total); + + // check to make sure we have the memory required + if (info->imageData == NULL) { + info->status = TGA_ERROR_MEMORY; + fclose(file); + return(info); + } + // finally load the image pixels + if ( info->type == 10 ) + tgaLoadRLEImageData(file, info); + else + tgaLoadImageData(file,info); + + // check for errors when reading the pixels + if (ferror(file)) { + info->status = TGA_ERROR_READING_FILE; + fclose(file); + return(info); + } + fclose(file); + info->status = TGA_OK; + + if ( info->flipped ) + { + tgaFlipImage( info ); + if ( info->flipped ) info->status = TGA_ERROR_MEMORY; + } + + return(info); +} + +// converts RGB to greyscale +void tgaRGBtogreyscale(tImageTGA *info) { + + int mode,i,j; + + unsigned char *newImageData; + + // if the image is already greyscale do nothing + if (info->pixelDepth == 8) + return; + + // compute the number of actual components + mode = info->pixelDepth / 8; + + // allocate an array for the new image data + newImageData = (unsigned char *)malloc(sizeof(unsigned char) * + info->height * info->width); + if (newImageData == NULL) { + return; + } + + // convert pixels: greyscale = o.30 * R + 0.59 * G + 0.11 * B + for (i = 0,j = 0; j < info->width * info->height; i +=mode, j++) + newImageData[j] = + (unsigned char)(0.30 * info->imageData[i] + + 0.59 * info->imageData[i+1] + + 0.11 * info->imageData[i+2]); + + + //free old image data + free(info->imageData); + + // reassign pixelDepth and type according to the new image type + info->pixelDepth = 8; + info->type = 3; + // reassing imageData to the new array. + info->imageData = newImageData; +} + +// releases the memory used for the image +void tgaDestroy(tImageTGA *info) { + + if (info != NULL) { + if (info->imageData != NULL) + free(info->imageData); + free(info); + } +} diff --git a/libs/cocos2d/Support/TransformUtils.h b/libs/cocos2d/Support/TransformUtils.h new file mode 100755 index 0000000..49fde35 --- /dev/null +++ b/libs/cocos2d/Support/TransformUtils.h @@ -0,0 +1,37 @@ +/* + * cocos2d for iPhone: http://www.cocos2d-iphone.org + * + * Copyright (c) 2009 Valentin Milea + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + * + */ + +#import + +#ifdef __IPHONE_OS_VERSION_MAX_ALLOWED +#import +#import +#elif defined(__MAC_OS_X_VERSION_MAX_ALLOWED) +#import +#import +#endif + +void CGAffineToGL(const CGAffineTransform *t, GLfloat *m); +void GLToCGAffine(const GLfloat *m, CGAffineTransform *t); diff --git a/libs/cocos2d/Support/TransformUtils.m b/libs/cocos2d/Support/TransformUtils.m new file mode 100755 index 0000000..9caecf0 --- /dev/null +++ b/libs/cocos2d/Support/TransformUtils.m @@ -0,0 +1,46 @@ +/* + * cocos2d for iPhone: http://www.cocos2d-iphone.org + * + * Copyright (c) 2009 Valentin Milea + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. + * + */ + + +#import "TransformUtils.h" + +void CGAffineToGL(const CGAffineTransform *t, GLfloat *m) +{ + // | m[0] m[4] m[8] m[12] | | m11 m21 m31 m41 | | a c 0 tx | + // | m[1] m[5] m[9] m[13] | | m12 m22 m32 m42 | | b d 0 ty | + // | m[2] m[6] m[10] m[14] | <=> | m13 m23 m33 m43 | <=> | 0 0 1 0 | + // | m[3] m[7] m[11] m[15] | | m14 m24 m34 m44 | | 0 0 0 1 | + + m[2] = m[3] = m[6] = m[7] = m[8] = m[9] = m[11] = m[14] = 0.0f; + m[10] = m[15] = 1.0f; + m[0] = t->a; m[4] = t->c; m[12] = t->tx; + m[1] = t->b; m[5] = t->d; m[13] = t->ty; +} + +void GLToCGAffine(const GLfloat *m, CGAffineTransform *t) +{ + t->a = m[0]; t->c = m[4]; t->tx = m[12]; + t->b = m[1]; t->d = m[5]; t->ty = m[13]; +} diff --git a/libs/cocos2d/Support/ZipUtils.h b/libs/cocos2d/Support/ZipUtils.h new file mode 100755 index 0000000..363f911 --- /dev/null +++ b/libs/cocos2d/Support/ZipUtils.h @@ -0,0 +1,91 @@ +/* cocos2d for iPhone + * + * http://www.cocos2d-iphone.org + * + * + * inflateMemory_ based on zlib example code + * http://www.zlib.net + * + * Some ideas were taken from: + * http://themanaworld.org/ + * from the mapreader.cpp file + * + */ + +#ifndef __CC_ZIP_UTILS_H +#define __CC_ZIP_UTILS_H + +#import + +#ifdef __cplusplus +extern "C" { +#endif + + /* XXX: pragma pack ??? */ + /** @struct CCZHeader + */ + struct CCZHeader { + uint8_t sig[4]; // signature. Should be 'CCZ!' 4 bytes + uint16_t compression_type; // should 0 + uint16_t version; // should be 2 (although version type==1 is also supported) + uint32_t reserved; // Reserverd for users. + uint32_t len; // size of the uncompressed file + }; + + enum { + CCZ_COMPRESSION_ZLIB, // zlib format. + CCZ_COMPRESSION_BZIP2, // bzip2 format (not supported yet) + CCZ_COMPRESSION_GZIP, // gzip format (not supported yet) + CCZ_COMPRESSION_NONE, // plain (not supported yet) + }; + +/** @file + * Zip helper functions + */ + +/** + * Inflates either zlib or gzip deflated memory. The inflated memory is + * expected to be freed by the caller. + * + * It will allocate 256k for the destination buffer. If it is not enought it will multiply the previous buffer size per 2, until there is enough memory. + * @returns the length of the deflated buffer + * + @since v0.8.1 + */ +int ccInflateMemory(unsigned char *in, unsigned int inLength, unsigned char **out); + +/** + * Inflates either zlib or gzip deflated memory. The inflated memory is + * expected to be freed by the caller. + * + * outLenghtHint is assumed to be the needed room to allocate the inflated buffer. + * + * @returns the length of the deflated buffer + * + @since v1.0.0 + */ +int ccInflateMemoryWithHint(unsigned char *in, unsigned int inLength, unsigned char **out, unsigned int outLenghtHint ); + + +/** inflates a GZip file into memory + * + * @returns the length of the deflated buffer + * + * @since v0.99.5 + */ +int ccInflateGZipFile(const char *filename, unsigned char **out); + +/** inflates a CCZ file into memory + * + * @returns the length of the deflated buffer + * + * @since v0.99.5 + */ +int ccInflateCCZFile(const char *filename, unsigned char **out); + + +#ifdef __cplusplus +} +#endif + +#endif // __CC_ZIP_UTILS_H diff --git a/libs/cocos2d/Support/ZipUtils.m b/libs/cocos2d/Support/ZipUtils.m new file mode 100755 index 0000000..ccd8bbc --- /dev/null +++ b/libs/cocos2d/Support/ZipUtils.m @@ -0,0 +1,251 @@ +/* cocos2d for iPhone + * + * http://www.cocos2d-iphone.org + * + * + * Inflates either zlib or gzip deflated memory. The inflated memory is + * expected to be freed by the caller. + * + * inflateMemory_ based on zlib example code + * http://www.zlib.net + * + * Some ideas were taken from: + * http://themanaworld.org/ + * from the mapreader.cpp file + */ + +#import + +#import +#import +#import +#import + +#import "ZipUtils.h" +#import "CCFileUtils.h" +#import "../ccMacros.h" + +// memory in iPhone is precious +// Should buffer factor be 1.5 instead of 2 ? +#define BUFFER_INC_FACTOR (2) + +static int inflateMemoryWithHint(unsigned char *in, unsigned int inLength, unsigned char **out, unsigned int *outLength, unsigned int outLenghtHint ) +{ + /* ret value */ + int err = Z_OK; + + int bufferSize = outLenghtHint; + *out = (unsigned char*) malloc(bufferSize); + + z_stream d_stream; /* decompression stream */ + d_stream.zalloc = (alloc_func)0; + d_stream.zfree = (free_func)0; + d_stream.opaque = (voidpf)0; + + d_stream.next_in = in; + d_stream.avail_in = inLength; + d_stream.next_out = *out; + d_stream.avail_out = bufferSize; + + /* window size to hold 256k */ + if( (err = inflateInit2(&d_stream, 15 + 32)) != Z_OK ) + return err; + + for (;;) { + err = inflate(&d_stream, Z_NO_FLUSH); + + if (err == Z_STREAM_END) + break; + + switch (err) { + case Z_NEED_DICT: + err = Z_DATA_ERROR; + case Z_DATA_ERROR: + case Z_MEM_ERROR: + inflateEnd(&d_stream); + return err; + } + + // not enough memory ? + if (err != Z_STREAM_END) { + + unsigned char *tmp = realloc(*out, bufferSize * BUFFER_INC_FACTOR); + + /* not enough memory, ouch */ + if (! tmp ) { + CCLOG(@"cocos2d: ZipUtils: realloc failed"); + inflateEnd(&d_stream); + return Z_MEM_ERROR; + } + /* only assign to *out if tmp is valid. it's not guaranteed that realloc will reuse the memory */ + *out = tmp; + + d_stream.next_out = *out + bufferSize; + d_stream.avail_out = bufferSize; + bufferSize *= BUFFER_INC_FACTOR; + } + } + + + *outLength = bufferSize - d_stream.avail_out; + err = inflateEnd(&d_stream); + return err; +} + +int ccInflateMemoryWithHint(unsigned char *in, unsigned int inLength, unsigned char **out, unsigned int outLengthHint ) +{ + unsigned int outLength = 0; + int err = inflateMemoryWithHint(in, inLength, out, &outLength, outLengthHint ); + + if (err != Z_OK || *out == NULL) { + if (err == Z_MEM_ERROR) + CCLOG(@"cocos2d: ZipUtils: Out of memory while decompressing map data!"); + + else if (err == Z_VERSION_ERROR) + CCLOG(@"cocos2d: ZipUtils: Incompatible zlib version!"); + + else if (err == Z_DATA_ERROR) + CCLOG(@"cocos2d: ZipUtils: Incorrect zlib compressed data!"); + + else + CCLOG(@"cocos2d: ZipUtils: Unknown error while decompressing map data!"); + + free(*out); + *out = NULL; + outLength = 0; + } + + return outLength; +} + +int ccInflateMemory(unsigned char *in, unsigned int inLength, unsigned char **out) +{ + // 256k for hint + return ccInflateMemoryWithHint(in, inLength, out, 256 * 1024 ); +} + +int ccInflateGZipFile(const char *path, unsigned char **out) +{ + int len; + unsigned int offset = 0; + + NSCAssert( out, @"ccInflateGZipFile: invalid 'out' parameter"); + NSCAssert( &*out, @"ccInflateGZipFile: invalid 'out' parameter"); + + gzFile inFile = gzopen(path, "rb"); + if( inFile == NULL ) { + CCLOG(@"cocos2d: ZipUtils: error open gzip file: %s", path); + return -1; + } + + /* 512k initial decompress buffer */ + int bufferSize = 512 * 1024; + unsigned int totalBufferSize = bufferSize; + + *out = malloc( bufferSize ); + if( ! out ) { + CCLOG(@"cocos2d: ZipUtils: out of memory"); + return -1; + } + + for (;;) { + len = gzread(inFile, *out + offset, bufferSize); + if (len < 0) { + CCLOG(@"cocos2d: ZipUtils: error in gzread"); + free( *out ); + *out = NULL; + return -1; + } + if (len == 0) + break; + + offset += len; + + // finish reading the file + if( len < bufferSize ) + break; + + bufferSize *= BUFFER_INC_FACTOR; + totalBufferSize += bufferSize; + unsigned char *tmp = realloc(*out, totalBufferSize ); + + if( ! tmp ) { + CCLOG(@"cocos2d: ZipUtils: out of memory"); + free( *out ); + *out = NULL; + return -1; + } + + *out = tmp; + } + + if (gzclose(inFile) != Z_OK) + CCLOG(@"cocos2d: ZipUtils: gzclose failed"); + + return offset; +} + +int ccInflateCCZFile(const char *path, unsigned char **out) +{ + NSCAssert( out, @"ccInflateCCZFile: invalid 'out' parameter"); + NSCAssert( &*out, @"ccInflateCCZFile: invalid 'out' parameter"); + + // load file into memory + unsigned char *compressed = NULL; + NSInteger fileLen = ccLoadFileIntoMemory( path, &compressed ); + if( fileLen < 0 ) { + CCLOG(@"cocos2d: Error loading CCZ compressed file"); + } + + struct CCZHeader *header = (struct CCZHeader*) compressed; + + // verify header + if( header->sig[0] != 'C' || header->sig[1] != 'C' || header->sig[2] != 'Z' || header->sig[3] != '!' ) { + CCLOG(@"cocos2d: Invalid CCZ file"); + free(compressed); + return -1; + } + + // verify header version + uint16_t version = CFSwapInt16BigToHost( header->version ); + if( version > 2 ) { + CCLOG(@"cocos2d: Unsupported CCZ header format"); + free(compressed); + return -1; + } + + // verify compression format + if( CFSwapInt16BigToHost(header->compression_type) != CCZ_COMPRESSION_ZLIB ) { + CCLOG(@"cocos2d: CCZ Unsupported compression method"); + free(compressed); + return -1; + } + + uint32_t len = CFSwapInt32BigToHost( header->len ); + + *out = malloc( len ); + if(! *out ) + { + CCLOG(@"cocos2d: CCZ: Failed to allocate memory for texture"); + free(compressed); + return -1; + } + + + uLongf destlen = len; + uLongf source = (uLongf) compressed + sizeof(*header); + int ret = uncompress(*out, &destlen, (Bytef*)source, fileLen - sizeof(*header) ); + + free( compressed ); + + if( ret != Z_OK ) + { + CCLOG(@"cocos2d: CCZ: Failed to uncompress data"); + free( *out ); + *out = NULL; + return -1; + } + + + return len; +} diff --git a/libs/cocos2d/Support/base64.c b/libs/cocos2d/Support/base64.c new file mode 100755 index 0000000..9aa52a6 --- /dev/null +++ b/libs/cocos2d/Support/base64.c @@ -0,0 +1,93 @@ +/* + public domain BASE64 code + + modified for cocos2d-iphone: http://www.cocos2d-iphone.org + */ + +#include +#include + +#include "base64.h" + +unsigned char alphabet[64] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"; + +int _base64Decode( unsigned char *input, unsigned int input_len, unsigned char *output, unsigned int *output_len ); + +int _base64Decode( unsigned char *input, unsigned int input_len, unsigned char *output, unsigned int *output_len ) +{ + static char inalphabet[256], decoder[256]; + int i, bits, c, char_count, errors = 0; + unsigned int input_idx = 0; + unsigned int output_idx = 0; + + for (i = (sizeof alphabet) - 1; i >= 0 ; i--) { + inalphabet[alphabet[i]] = 1; + decoder[alphabet[i]] = i; + } + + char_count = 0; + bits = 0; + for( input_idx=0; input_idx < input_len ; input_idx++ ) { + c = input[ input_idx ]; + if (c == '=') + break; + if (c > 255 || ! inalphabet[c]) + continue; + bits += decoder[c]; + char_count++; + if (char_count == 4) { + output[ output_idx++ ] = (bits >> 16); + output[ output_idx++ ] = ((bits >> 8) & 0xff); + output[ output_idx++ ] = ( bits & 0xff); + bits = 0; + char_count = 0; + } else { + bits <<= 6; + } + } + + if( c == '=' ) { + switch (char_count) { + case 1: + fprintf(stderr, "base64Decode: encoding incomplete: at least 2 bits missing"); + errors++; + break; + case 2: + output[ output_idx++ ] = ( bits >> 10 ); + break; + case 3: + output[ output_idx++ ] = ( bits >> 16 ); + output[ output_idx++ ] = (( bits >> 8 ) & 0xff); + break; + } + } else if ( input_idx < input_len ) { + if (char_count) { + fprintf(stderr, "base64 encoding incomplete: at least %d bits truncated", + ((4 - char_count) * 6)); + errors++; + } + } + + *output_len = output_idx; + return errors; +} + +int base64Decode(unsigned char *in, unsigned int inLength, unsigned char **out) +{ + unsigned int outLength = 0; + + //should be enough to store 6-bit buffers in 8-bit buffers + *out = malloc( inLength * 3.0f / 4.0f + 1 ); + if( *out ) { + int ret = _base64Decode(in, inLength, *out, &outLength); + + if (ret > 0 ) + { + printf("Base64Utils: error decoding"); + free(*out); + *out = NULL; + outLength = 0; + } + } + return outLength; +} diff --git a/libs/cocos2d/Support/base64.h b/libs/cocos2d/Support/base64.h new file mode 100755 index 0000000..d30878e --- /dev/null +++ b/libs/cocos2d/Support/base64.h @@ -0,0 +1,33 @@ +/* + public domain BASE64 code + + modified for cocos2d-iphone: http://www.cocos2d-iphone.org + */ + +#ifndef __CC_BASE64_DECODE_H +#define __CC_BASE64_DECODE_H + +#ifdef __cplusplus +extern "C" { +#endif + + +/** @file + base64 helper functions + */ + +/** + * Decodes a 64base encoded memory. The decoded memory is + * expected to be freed by the caller. + * + * @returns the length of the out buffer + * + @since v0.8.1 + */ +int base64Decode(unsigned char *in, unsigned int inLength, unsigned char **out); + +#ifdef __cplusplus +} +#endif + +#endif // __CC_BASE64_DECODE_H 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 @@ +/* Copyright (c) 2007 Scott Lembcke + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +/** + @file + Based on Chipmunk cpArray. + ccArray is a faster alternative to NSMutableArray, it does pretty much the + same thing (stores NSObjects and retains/releases them appropriately). It's + faster because: + - it uses a plain C interface so it doesn't incur Objective-c messaging overhead + - it assumes you know what you're doing, so it doesn't spend time on safety checks + (index out of bounds, required capacity etc.) + - comparisons are done using pointer equality instead of isEqual + + There are 2 kind of functions: + - ccArray functions that manipulates objective-c objects (retain and release are performanced) + - ccCArray functions that manipulates values like if they were standard C structures (no retain/release is performed) + */ + +#ifndef CC_ARRAY_H +#define CC_ARRAY_H + +#import + +#import +#import + + +#pragma mark - +#pragma mark ccArray for Objects + +// Easy integration +#define CCARRAYDATA_FOREACH(__array__, __object__) \ +__object__=__array__->arr[0]; for(NSUInteger i=0, num=__array__->num; iarr[i]) \ + + +typedef struct ccArray { + NSUInteger num, max; + id *arr; +} ccArray; + +/** Allocates and initializes a new array with specified capacity */ +static inline ccArray* ccArrayNew(NSUInteger capacity) { + if (capacity == 0) + capacity = 1; + + ccArray *arr = (ccArray*)malloc( sizeof(ccArray) ); + arr->num = 0; + arr->arr = (id*) malloc( capacity * sizeof(id) ); + arr->max = capacity; + + return arr; +} + +static inline void ccArrayRemoveAllObjects(ccArray *arr); + +/** Frees array after removing all remaining objects. Silently ignores nil arr. */ +static inline void ccArrayFree(ccArray *arr) +{ + if( arr == nil ) return; + + ccArrayRemoveAllObjects(arr); + + free(arr->arr); + free(arr); +} + +/** Doubles array capacity */ +static inline void ccArrayDoubleCapacity(ccArray *arr) +{ + arr->max *= 2; + id *newArr = (id *)realloc( arr->arr, arr->max * sizeof(id) ); + // will fail when there's not enough memory + NSCAssert(newArr != NULL, @"ccArrayDoubleCapacity failed. Not enough memory"); + arr->arr = newArr; +} + +/** Increases array capacity such that max >= num + extra. */ +static inline void ccArrayEnsureExtraCapacity(ccArray *arr, NSUInteger extra) +{ + while (arr->max < arr->num + extra) + ccArrayDoubleCapacity(arr); +} + +/** shrinks the array so the memory footprint corresponds with the number of items */ +static inline void ccArrayShrink(ccArray *arr) +{ + NSUInteger newSize; + + //only resize when necessary + if (arr->max > arr->num && !(arr->num==0 && arr->max==1)) + { + if (arr->num!=0) + { + newSize=arr->num; + arr->max=arr->num; + } + else + {//minimum capacity of 1, with 0 elements the array would be free'd by realloc + newSize=1; + arr->max=1; + } + + arr->arr = (id*) realloc(arr->arr,newSize * sizeof(id) ); + NSCAssert(arr->arr!=NULL,@"could not reallocate the memory"); + } +} + +/** Returns index of first occurence of object, NSNotFound if object not found. */ +static inline NSUInteger ccArrayGetIndexOfObject(ccArray *arr, id object) +{ + for( NSUInteger i = 0; i < arr->num; i++) + if( arr->arr[i] == object ) return i; + + return NSNotFound; +} + +/** Returns a Boolean value that indicates whether object is present in array. */ +static inline BOOL ccArrayContainsObject(ccArray *arr, id object) +{ + return ccArrayGetIndexOfObject(arr, object) != NSNotFound; +} + +/** Appends an object. Bahaviour undefined if array doesn't have enough capacity. */ +static inline void ccArrayAppendObject(ccArray *arr, id object) +{ + arr->arr[arr->num] = [object retain]; + arr->num++; +} + +/** Appends an object. Capacity of arr is increased if needed. */ +static inline void ccArrayAppendObjectWithResize(ccArray *arr, id object) +{ + ccArrayEnsureExtraCapacity(arr, 1); + ccArrayAppendObject(arr, object); +} + +/** Appends objects from plusArr to arr. Behaviour undefined if arr doesn't have + enough capacity. */ +static inline void ccArrayAppendArray(ccArray *arr, ccArray *plusArr) +{ + for( NSUInteger i = 0; i < plusArr->num; i++) + ccArrayAppendObject(arr, plusArr->arr[i]); +} + +/** Appends objects from plusArr to arr. Capacity of arr is increased if needed. */ +static inline void ccArrayAppendArrayWithResize(ccArray *arr, ccArray *plusArr) +{ + ccArrayEnsureExtraCapacity(arr, plusArr->num); + ccArrayAppendArray(arr, plusArr); +} + +/** Inserts an object at index */ +static inline void ccArrayInsertObjectAtIndex(ccArray *arr, id object, NSUInteger index) +{ + NSCAssert(index<=arr->num, @"Invalid index. Out of bounds"); + + ccArrayEnsureExtraCapacity(arr, 1); + + NSUInteger remaining = arr->num - index; + if( remaining > 0) + memmove(&arr->arr[index+1], &arr->arr[index], sizeof(id) * remaining ); + + arr->arr[index] = [object retain]; + arr->num++; +} + +/** Swaps two objects */ +static inline void ccArraySwapObjectsAtIndexes(ccArray *arr, NSUInteger index1, NSUInteger index2) +{ + NSCAssert(index1 < arr->num, @"(1) Invalid index. Out of bounds"); + NSCAssert(index2 < arr->num, @"(2) Invalid index. Out of bounds"); + + id object1 = arr->arr[index1]; + + arr->arr[index1] = arr->arr[index2]; + arr->arr[index2] = object1; +} + +/** Removes all objects from arr */ +static inline void ccArrayRemoveAllObjects(ccArray *arr) +{ + while( arr->num > 0 ) + [arr->arr[--arr->num] release]; +} + +/** Removes object at specified index and pushes back all subsequent objects. + Behaviour undefined if index outside [0, num-1]. */ +static inline void ccArrayRemoveObjectAtIndex(ccArray *arr, NSUInteger index) +{ + [arr->arr[index] release]; + arr->num--; + + NSUInteger remaining = arr->num - index; + if(remaining>0) + memmove(&arr->arr[index], &arr->arr[index+1], remaining * sizeof(id)); +} + +/** Removes object at specified index and fills the gap with the last object, + thereby avoiding the need to push back subsequent objects. + Behaviour undefined if index outside [0, num-1]. */ +static inline void ccArrayFastRemoveObjectAtIndex(ccArray *arr, NSUInteger index) +{ + [arr->arr[index] release]; + NSUInteger last = --arr->num; + arr->arr[index] = arr->arr[last]; +} + +static inline void ccArrayFastRemoveObject(ccArray *arr, id object) +{ + NSUInteger index = ccArrayGetIndexOfObject(arr, object); + if (index != NSNotFound) + ccArrayFastRemoveObjectAtIndex(arr, index); +} + +/** Searches for the first occurance of object and removes it. If object is not + found the function has no effect. */ +static inline void ccArrayRemoveObject(ccArray *arr, id object) +{ + NSUInteger index = ccArrayGetIndexOfObject(arr, object); + if (index != NSNotFound) + ccArrayRemoveObjectAtIndex(arr, index); +} + +/** Removes from arr all objects in minusArr. For each object in minusArr, the + first matching instance in arr will be removed. */ +static inline void ccArrayRemoveArray(ccArray *arr, ccArray *minusArr) +{ + for( NSUInteger i = 0; i < minusArr->num; i++) + ccArrayRemoveObject(arr, minusArr->arr[i]); +} + +/** Removes from arr all objects in minusArr. For each object in minusArr, all + matching instances in arr will be removed. */ +static inline void ccArrayFullRemoveArray(ccArray *arr, ccArray *minusArr) +{ + NSUInteger back = 0; + + for( NSUInteger i = 0; i < arr->num; i++) { + if( ccArrayContainsObject(minusArr, arr->arr[i]) ) { + [arr->arr[i] release]; + back++; + } else + arr->arr[i - back] = arr->arr[i]; + } + + arr->num -= back; +} + +/** Sends to each object in arr the message identified by given selector. */ +static inline void ccArrayMakeObjectsPerformSelector(ccArray *arr, SEL sel) +{ + for( NSUInteger i = 0; i < arr->num; i++) + [arr->arr[i] performSelector:sel]; +} + +static inline void ccArrayMakeObjectsPerformSelectorWithObject(ccArray *arr, SEL sel, id object) +{ + for( NSUInteger i = 0; i < arr->num; i++) + [arr->arr[i] performSelector:sel withObject:object]; +} + + +#pragma mark - +#pragma mark ccCArray for Values (c structures) + +typedef ccArray ccCArray; + +static inline void ccCArrayRemoveAllValues(ccCArray *arr); + +/** Allocates and initializes a new C array with specified capacity */ +static inline ccCArray* ccCArrayNew(NSUInteger capacity) { + if (capacity == 0) + capacity = 1; + + ccCArray *arr = (ccCArray*)malloc( sizeof(ccCArray) ); + arr->num = 0; + arr->arr = (id*) malloc( capacity * sizeof(id) ); + arr->max = capacity; + + return arr; +} + +/** Frees C array after removing all remaining values. Silently ignores nil arr. */ +static inline void ccCArrayFree(ccCArray *arr) +{ + if( arr == nil ) return; + + ccCArrayRemoveAllValues(arr); + + free(arr->arr); + free(arr); +} + +/** Doubles C array capacity */ +static inline void ccCArrayDoubleCapacity(ccCArray *arr) +{ + ccArrayDoubleCapacity(arr); +} + +/** Increases array capacity such that max >= num + extra. */ +static inline void ccCArrayEnsureExtraCapacity(ccCArray *arr, NSUInteger extra) +{ + ccArrayEnsureExtraCapacity(arr,extra); +} + +/** Returns index of first occurence of value, NSNotFound if value not found. */ +static inline NSUInteger ccCArrayGetIndexOfValue(ccCArray *arr, void* value) +{ + for( NSUInteger i = 0; i < arr->num; i++) + if( arr->arr[i] == value ) return i; + return NSNotFound; +} + +/** Returns a Boolean value that indicates whether value is present in the C array. */ +static inline BOOL ccCArrayContainsValue(ccCArray *arr, void* value) +{ + return ccCArrayGetIndexOfValue(arr, value) != NSNotFound; +} + +/** Inserts a value at a certain position. Behaviour undefined if aray doesn't have enough capacity */ +static inline void ccCArrayInsertValueAtIndex( ccCArray *arr, void *value, NSUInteger index) +{ + NSCAssert( index < arr->max, @"ccCArrayInsertValueAtIndex: invalid index"); + + NSUInteger remaining = arr->num - index; + + // last Value doesn't need to be moved + if( remaining > 0) { + // tex coordinates + memmove( &arr->arr[index+1],&arr->arr[index], sizeof(void*) * remaining ); + } + + arr->num++; + arr->arr[index] = (id) value; +} + +/** Appends an value. Bahaviour undefined if array doesn't have enough capacity. */ +static inline void ccCArrayAppendValue(ccCArray *arr, void* value) +{ + arr->arr[arr->num] = (id) value; + arr->num++; +} + +/** Appends an value. Capacity of arr is increased if needed. */ +static inline void ccCArrayAppendValueWithResize(ccCArray *arr, void* value) +{ + ccCArrayEnsureExtraCapacity(arr, 1); + ccCArrayAppendValue(arr, value); +} + +/** Appends values from plusArr to arr. Behaviour undefined if arr doesn't have + enough capacity. */ +static inline void ccCArrayAppendArray(ccCArray *arr, ccCArray *plusArr) +{ + for( NSUInteger i = 0; i < plusArr->num; i++) + ccCArrayAppendValue(arr, plusArr->arr[i]); +} + +/** Appends values from plusArr to arr. Capacity of arr is increased if needed. */ +static inline void ccCArrayAppendArrayWithResize(ccCArray *arr, ccCArray *plusArr) +{ + ccCArrayEnsureExtraCapacity(arr, plusArr->num); + ccCArrayAppendArray(arr, plusArr); +} + +/** Removes all values from arr */ +static inline void ccCArrayRemoveAllValues(ccCArray *arr) +{ + arr->num = 0; +} + +/** Removes value at specified index and pushes back all subsequent values. + Behaviour undefined if index outside [0, num-1]. + @since v0.99.4 + */ +static inline void ccCArrayRemoveValueAtIndex(ccCArray *arr, NSUInteger index) +{ + for( NSUInteger last = --arr->num; index < last; index++) + arr->arr[index] = arr->arr[index + 1]; +} + +/** Removes value at specified index and fills the gap with the last value, + thereby avoiding the need to push back subsequent values. + Behaviour undefined if index outside [0, num-1]. + @since v0.99.4 + */ +static inline void ccCArrayFastRemoveValueAtIndex(ccCArray *arr, NSUInteger index) +{ + NSUInteger last = --arr->num; + arr->arr[index] = arr->arr[last]; +} + +/** Searches for the first occurance of value and removes it. If value is not found the function has no effect. + @since v0.99.4 + */ +static inline void ccCArrayRemoveValue(ccCArray *arr, void* value) +{ + NSUInteger index = ccCArrayGetIndexOfValue(arr, value); + if (index != NSNotFound) + ccCArrayRemoveValueAtIndex(arr, index); +} + +/** Removes from arr all values in minusArr. For each Value in minusArr, the first matching instance in arr will be removed. + @since v0.99.4 + */ +static inline void ccCArrayRemoveArray(ccCArray *arr, ccCArray *minusArr) +{ + for( NSUInteger i = 0; i < minusArr->num; i++) + ccCArrayRemoveValue(arr, minusArr->arr[i]); +} + +/** Removes from arr all values in minusArr. For each value in minusArr, all matching instances in arr will be removed. + @since v0.99.4 + */ +static inline void ccCArrayFullRemoveArray(ccCArray *arr, ccCArray *minusArr) +{ + NSUInteger back = 0; + + for( NSUInteger i = 0; i < arr->num; i++) { + if( ccCArrayContainsValue(minusArr, arr->arr[i]) ) { + back++; + } else + arr->arr[i - back] = arr->arr[i]; + } + + arr->num -= back; +} +#endif // CC_ARRAY_H diff --git a/libs/cocos2d/Support/ccUtils.c b/libs/cocos2d/Support/ccUtils.c new file mode 100755 index 0000000..39786ec --- /dev/null +++ b/libs/cocos2d/Support/ccUtils.c @@ -0,0 +1,20 @@ +/* + * cocos2d for iPhone: http://www.cocos2d-iphone.org + * + */ + +/* + ccNextPOT function is licensed under the same license that is used in CCTexture2D.m. + */ +#include "ccUtils.h" + +unsigned long ccNextPOT(unsigned long x) +{ + x = x - 1; + x = x | (x >> 1); + x = x | (x >> 2); + x = x | (x >> 4); + x = x | (x >> 8); + x = x | (x >>16); + return x + 1; +} \ No newline at end of file diff --git a/libs/cocos2d/Support/ccUtils.h b/libs/cocos2d/Support/ccUtils.h new file mode 100755 index 0000000..783fc54 --- /dev/null +++ b/libs/cocos2d/Support/ccUtils.h @@ -0,0 +1,29 @@ +/* + * cocos2d for iPhone: http://www.cocos2d-iphone.org + * + */ + +#ifndef __CC_UTILS_H +#define __CC_UTILS_H + +/** @file ccUtils.h + Misc free functions + */ + +/* + ccNextPOT function is licensed under the same license that is used in CCTexture2D.m. + */ + +/** returns the Next Power of Two value. + + Examples: + - If "value" is 15, it will return 16. + - If "value" is 16, it will return 16. + - If "value" is 17, it will return 32. + + @since v0.99.5 + */ + +unsigned long ccNextPOT( unsigned long value ); + +#endif // ! __CC_UTILS_H diff --git a/libs/cocos2d/Support/uthash.h b/libs/cocos2d/Support/uthash.h new file mode 100755 index 0000000..a4bdc18 --- /dev/null +++ b/libs/cocos2d/Support/uthash.h @@ -0,0 +1,972 @@ +/* +Copyright (c) 2003-2010, Troy D. Hanson http://uthash.sourceforge.net +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS +IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A +PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER +OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef UTHASH_H +#define UTHASH_H + +#include /* memcmp,strlen */ +#include /* ptrdiff_t */ + +/* These macros use decltype or the earlier __typeof GNU extension. + As decltype is only available in newer compilers (VS2010 or gcc 4.3+ + when compiling c++ source) this code uses whatever method is needed + or, for VS2008 where neither is available, uses casting workarounds. */ +#ifdef _MSC_VER /* MS compiler */ +#if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */ +#define DECLTYPE(x) (decltype(x)) +#else /* VS2008 or older (or VS2010 in C mode) */ +#define NO_DECLTYPE +#define DECLTYPE(x) +#endif +#else /* GNU, Sun and other compilers */ +#define DECLTYPE(x) (__typeof(x)) +#endif + +#ifdef NO_DECLTYPE +#define DECLTYPE_ASSIGN(dst,src) \ +do { \ + char **_da_dst = (char**)(&(dst)); \ + *_da_dst = (char*)(src); \ +} while(0) +#else +#define DECLTYPE_ASSIGN(dst,src) \ +do { \ + (dst) = DECLTYPE(dst)(src); \ +} while(0) +#endif + +/* a number of the hash function use uint32_t which isn't defined on win32 */ +#ifdef _MSC_VER +typedef unsigned int uint32_t; +#else +#include /* uint32_t */ +#endif + +#define UTHASH_VERSION 1.9.3 + +#define uthash_fatal(msg) exit(-1) /* fatal error (out of memory,etc) */ +#define uthash_malloc(sz) malloc(sz) /* malloc fcn */ +#define uthash_free(ptr,sz) free(ptr) /* free fcn */ + +#define uthash_noexpand_fyi(tbl) /* can be defined to log noexpand */ +#define uthash_expand_fyi(tbl) /* can be defined to log expands */ + +/* initial number of buckets */ +#define HASH_INITIAL_NUM_BUCKETS 32 /* initial number of buckets */ +#define HASH_INITIAL_NUM_BUCKETS_LOG2 5 /* lg2 of initial number of buckets */ +#define HASH_BKT_CAPACITY_THRESH 10 /* expand when bucket count reaches */ + +/* calculate the element whose hash handle address is hhe */ +#define ELMT_FROM_HH(tbl,hhp) ((void*)(((char*)(hhp)) - ((tbl)->hho))) + +#define HASH_FIND(hh,head,keyptr,keylen,out) \ +do { \ + unsigned _hf_bkt,_hf_hashv; \ + out=NULL; \ + if (head) { \ + HASH_FCN(keyptr,keylen, (head)->hh.tbl->num_buckets, _hf_hashv, _hf_bkt); \ + if (HASH_BLOOM_TEST((head)->hh.tbl, _hf_hashv)) { \ + HASH_FIND_IN_BKT((head)->hh.tbl, hh, (head)->hh.tbl->buckets[ _hf_bkt ], \ + keyptr,keylen,out); \ + } \ + } \ +} while (0) + +#ifdef HASH_BLOOM +#define HASH_BLOOM_BITLEN (1ULL << HASH_BLOOM) +#define HASH_BLOOM_BYTELEN (HASH_BLOOM_BITLEN/8) + ((HASH_BLOOM_BITLEN%8) ? 1:0) +#define HASH_BLOOM_MAKE(tbl) \ +do { \ + (tbl)->bloom_nbits = HASH_BLOOM; \ + (tbl)->bloom_bv = (uint8_t*)uthash_malloc(HASH_BLOOM_BYTELEN); \ + if (!((tbl)->bloom_bv)) { uthash_fatal( "out of memory"); } \ + memset((tbl)->bloom_bv, 0, HASH_BLOOM_BYTELEN); \ + (tbl)->bloom_sig = HASH_BLOOM_SIGNATURE; \ +} while (0); + +#define HASH_BLOOM_FREE(tbl) \ +do { \ + uthash_free((tbl)->bloom_bv, HASH_BLOOM_BYTELEN); \ +} while (0); + +#define HASH_BLOOM_BITSET(bv,idx) (bv[(idx)/8] |= (1U << ((idx)%8))) +#define HASH_BLOOM_BITTEST(bv,idx) (bv[(idx)/8] & (1U << ((idx)%8))) + +#define HASH_BLOOM_ADD(tbl,hashv) \ + HASH_BLOOM_BITSET((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1))) + +#define HASH_BLOOM_TEST(tbl,hashv) \ + HASH_BLOOM_BITTEST((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1))) + +#else +#define HASH_BLOOM_MAKE(tbl) +#define HASH_BLOOM_FREE(tbl) +#define HASH_BLOOM_ADD(tbl,hashv) +#define HASH_BLOOM_TEST(tbl,hashv) (1) +#endif + +#define HASH_MAKE_TABLE(hh,head) \ +do { \ + (head)->hh.tbl = (UT_hash_table*)uthash_malloc( \ + sizeof(UT_hash_table)); \ + if (!((head)->hh.tbl)) { uthash_fatal( "out of memory"); } \ + memset((head)->hh.tbl, 0, sizeof(UT_hash_table)); \ + (head)->hh.tbl->tail = &((head)->hh); \ + (head)->hh.tbl->num_buckets = HASH_INITIAL_NUM_BUCKETS; \ + (head)->hh.tbl->log2_num_buckets = HASH_INITIAL_NUM_BUCKETS_LOG2; \ + (head)->hh.tbl->hho = (char*)(&(head)->hh) - (char*)(head); \ + (head)->hh.tbl->buckets = (UT_hash_bucket*)uthash_malloc( \ + HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \ + if (! (head)->hh.tbl->buckets) { uthash_fatal( "out of memory"); } \ + memset((head)->hh.tbl->buckets, 0, \ + HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \ + HASH_BLOOM_MAKE((head)->hh.tbl); \ + (head)->hh.tbl->signature = HASH_SIGNATURE; \ +} while(0) + +#define HASH_ADD(hh,head,fieldname,keylen_in,add) \ + HASH_ADD_KEYPTR(hh,head,&add->fieldname,keylen_in,add) + +#define HASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add) \ +do { \ + unsigned _ha_bkt; \ + (add)->hh.next = NULL; \ + (add)->hh.key = (char*)keyptr; \ + (add)->hh.keylen = keylen_in; \ + if (!(head)) { \ + head = (add); \ + (head)->hh.prev = NULL; \ + HASH_MAKE_TABLE(hh,head); \ + } else { \ + (head)->hh.tbl->tail->next = (add); \ + (add)->hh.prev = ELMT_FROM_HH((head)->hh.tbl, (head)->hh.tbl->tail); \ + (head)->hh.tbl->tail = &((add)->hh); \ + } \ + (head)->hh.tbl->num_items++; \ + (add)->hh.tbl = (head)->hh.tbl; \ + HASH_FCN(keyptr,keylen_in, (head)->hh.tbl->num_buckets, \ + (add)->hh.hashv, _ha_bkt); \ + HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt],&(add)->hh); \ + HASH_BLOOM_ADD((head)->hh.tbl,(add)->hh.hashv); \ + HASH_EMIT_KEY(hh,head,keyptr,keylen_in); \ + HASH_FSCK(hh,head); \ +} while(0) + +#define HASH_TO_BKT( hashv, num_bkts, bkt ) \ +do { \ + bkt = ((hashv) & ((num_bkts) - 1)); \ +} while(0) + +/* delete "delptr" from the hash table. + * "the usual" patch-up process for the app-order doubly-linked-list. + * The use of _hd_hh_del below deserves special explanation. + * These used to be expressed using (delptr) but that led to a bug + * if someone used the same symbol for the head and deletee, like + * HASH_DELETE(hh,users,users); + * We want that to work, but by changing the head (users) below + * we were forfeiting our ability to further refer to the deletee (users) + * in the patch-up process. Solution: use scratch space to + * copy the deletee pointer, then the latter references are via that + * scratch pointer rather than through the repointed (users) symbol. + */ +#define HASH_DELETE(hh,head,delptr) \ +do { \ + unsigned _hd_bkt; \ + struct UT_hash_handle *_hd_hh_del; \ + if ( ((delptr)->hh.prev == NULL) && ((delptr)->hh.next == NULL) ) { \ + uthash_free((head)->hh.tbl->buckets, \ + (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \ + HASH_BLOOM_FREE((head)->hh.tbl); \ + uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ + head = NULL; \ + } else { \ + _hd_hh_del = &((delptr)->hh); \ + if ((delptr) == ELMT_FROM_HH((head)->hh.tbl,(head)->hh.tbl->tail)) { \ + (head)->hh.tbl->tail = \ + (UT_hash_handle*)((char*)((delptr)->hh.prev) + \ + (head)->hh.tbl->hho); \ + } \ + if ((delptr)->hh.prev) { \ + ((UT_hash_handle*)((char*)((delptr)->hh.prev) + \ + (head)->hh.tbl->hho))->next = (delptr)->hh.next; \ + } else { \ + DECLTYPE_ASSIGN(head,(delptr)->hh.next); \ + } \ + if (_hd_hh_del->next) { \ + ((UT_hash_handle*)((char*)_hd_hh_del->next + \ + (head)->hh.tbl->hho))->prev = \ + _hd_hh_del->prev; \ + } \ + HASH_TO_BKT( _hd_hh_del->hashv, (head)->hh.tbl->num_buckets, _hd_bkt); \ + HASH_DEL_IN_BKT(hh,(head)->hh.tbl->buckets[_hd_bkt], _hd_hh_del); \ + (head)->hh.tbl->num_items--; \ + } \ + HASH_FSCK(hh,head); \ +} while (0) + + +/* convenience forms of HASH_FIND/HASH_ADD/HASH_DEL */ +#define HASH_FIND_STR(head,findstr,out) \ + HASH_FIND(hh,head,findstr,strlen(findstr),out) +#define HASH_ADD_STR(head,strfield,add) \ + HASH_ADD(hh,head,strfield,strlen(add->strfield),add) +#define HASH_FIND_INT(head,findint,out) \ + HASH_FIND(hh,head,findint,sizeof(int),out) +#define HASH_ADD_INT(head,intfield,add) \ + HASH_ADD(hh,head,intfield,sizeof(int),add) +#define HASH_FIND_PTR(head,findptr,out) \ + HASH_FIND(hh,head,findptr,sizeof(void *),out) +#define HASH_ADD_PTR(head,ptrfield,add) \ + HASH_ADD(hh,head,ptrfield,sizeof(void *),add) +#define HASH_DEL(head,delptr) \ + HASH_DELETE(hh,head,delptr) + +/* HASH_FSCK checks hash integrity on every add/delete when HASH_DEBUG is defined. + * This is for uthash developer only; it compiles away if HASH_DEBUG isn't defined. + */ +#ifdef HASH_DEBUG +#define HASH_OOPS(...) do { fprintf(stderr,__VA_ARGS__); exit(-1); } while (0) +#define HASH_FSCK(hh,head) \ +do { \ + unsigned _bkt_i; \ + unsigned _count, _bkt_count; \ + char *_prev; \ + struct UT_hash_handle *_thh; \ + if (head) { \ + _count = 0; \ + for( _bkt_i = 0; _bkt_i < (head)->hh.tbl->num_buckets; _bkt_i++) { \ + _bkt_count = 0; \ + _thh = (head)->hh.tbl->buckets[_bkt_i].hh_head; \ + _prev = NULL; \ + while (_thh) { \ + if (_prev != (char*)(_thh->hh_prev)) { \ + HASH_OOPS("invalid hh_prev %p, actual %p\n", \ + _thh->hh_prev, _prev ); \ + } \ + _bkt_count++; \ + _prev = (char*)(_thh); \ + _thh = _thh->hh_next; \ + } \ + _count += _bkt_count; \ + if ((head)->hh.tbl->buckets[_bkt_i].count != _bkt_count) { \ + HASH_OOPS("invalid bucket count %d, actual %d\n", \ + (head)->hh.tbl->buckets[_bkt_i].count, _bkt_count); \ + } \ + } \ + if (_count != (head)->hh.tbl->num_items) { \ + HASH_OOPS("invalid hh item count %d, actual %d\n", \ + (head)->hh.tbl->num_items, _count ); \ + } \ + /* traverse hh in app order; check next/prev integrity, count */ \ + _count = 0; \ + _prev = NULL; \ + _thh = &(head)->hh; \ + while (_thh) { \ + _count++; \ + if (_prev !=(char*)(_thh->prev)) { \ + HASH_OOPS("invalid prev %p, actual %p\n", \ + _thh->prev, _prev ); \ + } \ + _prev = (char*)ELMT_FROM_HH((head)->hh.tbl, _thh); \ + _thh = ( _thh->next ? (UT_hash_handle*)((char*)(_thh->next) + \ + (head)->hh.tbl->hho) : NULL ); \ + } \ + if (_count != (head)->hh.tbl->num_items) { \ + HASH_OOPS("invalid app item count %d, actual %d\n", \ + (head)->hh.tbl->num_items, _count ); \ + } \ + } \ +} while (0) +#else +#define HASH_FSCK(hh,head) +#endif + +/* When compiled with -DHASH_EMIT_KEYS, length-prefixed keys are emitted to + * the descriptor to which this macro is defined for tuning the hash function. + * The app can #include to get the prototype for write(2). */ +#ifdef HASH_EMIT_KEYS +#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) \ +do { \ + unsigned _klen = fieldlen; \ + write(HASH_EMIT_KEYS, &_klen, sizeof(_klen)); \ + write(HASH_EMIT_KEYS, keyptr, fieldlen); \ +} while (0) +#else +#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) +#endif + +/* default to Jenkin's hash unless overridden e.g. DHASH_FUNCTION=HASH_SAX */ +#ifdef HASH_FUNCTION +#define HASH_FCN HASH_FUNCTION +#else +#define HASH_FCN HASH_JEN +#endif + +/* The Bernstein hash function, used in Perl prior to v5.6 */ +#define HASH_BER(key,keylen,num_bkts,hashv,bkt) \ +do { \ + unsigned _hb_keylen=keylen; \ + char *_hb_key=(char*)(key); \ + (hashv) = 0; \ + while (_hb_keylen--) { (hashv) = ((hashv) * 33) + *_hb_key++; } \ + bkt = (hashv) & (num_bkts-1); \ +} while (0) + + +/* SAX/FNV/OAT/JEN hash functions are macro variants of those listed at + * http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx */ +#define HASH_SAX(key,keylen,num_bkts,hashv,bkt) \ +do { \ + unsigned _sx_i; \ + char *_hs_key=(char*)(key); \ + hashv = 0; \ + for(_sx_i=0; _sx_i < keylen; _sx_i++) \ + hashv ^= (hashv << 5) + (hashv >> 2) + _hs_key[_sx_i]; \ + bkt = hashv & (num_bkts-1); \ +} while (0) + +#define HASH_FNV(key,keylen,num_bkts,hashv,bkt) \ +do { \ + unsigned _fn_i; \ + char *_hf_key=(char*)(key); \ + hashv = 2166136261UL; \ + for(_fn_i=0; _fn_i < keylen; _fn_i++) \ + hashv = (hashv * 16777619) ^ _hf_key[_fn_i]; \ + bkt = hashv & (num_bkts-1); \ +} while(0); + +#define HASH_OAT(key,keylen,num_bkts,hashv,bkt) \ +do { \ + unsigned _ho_i; \ + char *_ho_key=(char*)(key); \ + hashv = 0; \ + for(_ho_i=0; _ho_i < keylen; _ho_i++) { \ + hashv += _ho_key[_ho_i]; \ + hashv += (hashv << 10); \ + hashv ^= (hashv >> 6); \ + } \ + hashv += (hashv << 3); \ + hashv ^= (hashv >> 11); \ + hashv += (hashv << 15); \ + bkt = hashv & (num_bkts-1); \ +} while(0) + +#define HASH_JEN_MIX(a,b,c) \ +do { \ + a -= b; a -= c; a ^= ( c >> 13 ); \ + b -= c; b -= a; b ^= ( a << 8 ); \ + c -= a; c -= b; c ^= ( b >> 13 ); \ + a -= b; a -= c; a ^= ( c >> 12 ); \ + b -= c; b -= a; b ^= ( a << 16 ); \ + c -= a; c -= b; c ^= ( b >> 5 ); \ + a -= b; a -= c; a ^= ( c >> 3 ); \ + b -= c; b -= a; b ^= ( a << 10 ); \ + c -= a; c -= b; c ^= ( b >> 15 ); \ +} while (0) + +#define HASH_JEN(key,keylen,num_bkts,hashv,bkt) \ +do { \ + unsigned _hj_i,_hj_j,_hj_k; \ + char *_hj_key=(char*)(key); \ + hashv = 0xfeedbeef; \ + _hj_i = _hj_j = 0x9e3779b9; \ + _hj_k = keylen; \ + while (_hj_k >= 12) { \ + _hj_i += (_hj_key[0] + ( (unsigned)_hj_key[1] << 8 ) \ + + ( (unsigned)_hj_key[2] << 16 ) \ + + ( (unsigned)_hj_key[3] << 24 ) ); \ + _hj_j += (_hj_key[4] + ( (unsigned)_hj_key[5] << 8 ) \ + + ( (unsigned)_hj_key[6] << 16 ) \ + + ( (unsigned)_hj_key[7] << 24 ) ); \ + hashv += (_hj_key[8] + ( (unsigned)_hj_key[9] << 8 ) \ + + ( (unsigned)_hj_key[10] << 16 ) \ + + ( (unsigned)_hj_key[11] << 24 ) ); \ + \ + HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ + \ + _hj_key += 12; \ + _hj_k -= 12; \ + } \ + hashv += keylen; \ + switch ( _hj_k ) { \ + case 11: hashv += ( (unsigned)_hj_key[10] << 24 ); \ + case 10: hashv += ( (unsigned)_hj_key[9] << 16 ); \ + case 9: hashv += ( (unsigned)_hj_key[8] << 8 ); \ + case 8: _hj_j += ( (unsigned)_hj_key[7] << 24 ); \ + case 7: _hj_j += ( (unsigned)_hj_key[6] << 16 ); \ + case 6: _hj_j += ( (unsigned)_hj_key[5] << 8 ); \ + case 5: _hj_j += _hj_key[4]; \ + case 4: _hj_i += ( (unsigned)_hj_key[3] << 24 ); \ + case 3: _hj_i += ( (unsigned)_hj_key[2] << 16 ); \ + case 2: _hj_i += ( (unsigned)_hj_key[1] << 8 ); \ + case 1: _hj_i += _hj_key[0]; \ + } \ + HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ + bkt = hashv & (num_bkts-1); \ +} while(0) + +/* The Paul Hsieh hash function */ +#undef get16bits +#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \ + || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__) +#define get16bits(d) (*((const uint16_t *) (d))) +#endif + +#if !defined (get16bits) +#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \ + +(uint32_t)(((const uint8_t *)(d))[0]) ) +#endif +#define HASH_SFH(key,keylen,num_bkts,hashv,bkt) \ +do { \ + char *_sfh_key=(char*)(key); \ + uint32_t _sfh_tmp, _sfh_len = keylen; \ + \ + int _sfh_rem = _sfh_len & 3; \ + _sfh_len >>= 2; \ + hashv = 0xcafebabe; \ + \ + /* Main loop */ \ + for (;_sfh_len > 0; _sfh_len--) { \ + hashv += get16bits (_sfh_key); \ + _sfh_tmp = (get16bits (_sfh_key+2) << 11) ^ hashv; \ + hashv = (hashv << 16) ^ _sfh_tmp; \ + _sfh_key += 2*sizeof (uint16_t); \ + hashv += hashv >> 11; \ + } \ + \ + /* Handle end cases */ \ + switch (_sfh_rem) { \ + case 3: hashv += get16bits (_sfh_key); \ + hashv ^= hashv << 16; \ + hashv ^= _sfh_key[sizeof (uint16_t)] << 18; \ + hashv += hashv >> 11; \ + break; \ + case 2: hashv += get16bits (_sfh_key); \ + hashv ^= hashv << 11; \ + hashv += hashv >> 17; \ + break; \ + case 1: hashv += *_sfh_key; \ + hashv ^= hashv << 10; \ + hashv += hashv >> 1; \ + } \ + \ + /* Force "avalanching" of final 127 bits */ \ + hashv ^= hashv << 3; \ + hashv += hashv >> 5; \ + hashv ^= hashv << 4; \ + hashv += hashv >> 17; \ + hashv ^= hashv << 25; \ + hashv += hashv >> 6; \ + bkt = hashv & (num_bkts-1); \ +} while(0); + +#ifdef HASH_USING_NO_STRICT_ALIASING +/* The MurmurHash exploits some CPU's (e.g. x86) tolerance for unaligned reads. + * For other types of CPU's (e.g. Sparc) an unaligned read causes a bus error. + * So MurmurHash comes in two versions, the faster unaligned one and the slower + * aligned one. We only use the faster one on CPU's where we know it's safe. + * + * Note the preprocessor built-in defines can be emitted using: + * + * gcc -m64 -dM -E - < /dev/null (on gcc) + * cc -## a.c (where a.c is a simple test file) (Sun Studio) + */ +#if (defined(__i386__) || defined(__x86_64__)) +#define HASH_MUR HASH_MUR_UNALIGNED +#else +#define HASH_MUR HASH_MUR_ALIGNED +#endif + +/* Appleby's MurmurHash fast version for unaligned-tolerant archs like i386 */ +#define HASH_MUR_UNALIGNED(key,keylen,num_bkts,hashv,bkt) \ +do { \ + const unsigned int _mur_m = 0x5bd1e995; \ + const int _mur_r = 24; \ + hashv = 0xcafebabe ^ keylen; \ + char *_mur_key = (char *)(key); \ + uint32_t _mur_tmp, _mur_len = keylen; \ + \ + for (;_mur_len >= 4; _mur_len-=4) { \ + _mur_tmp = *(uint32_t *)_mur_key; \ + _mur_tmp *= _mur_m; \ + _mur_tmp ^= _mur_tmp >> _mur_r; \ + _mur_tmp *= _mur_m; \ + hashv *= _mur_m; \ + hashv ^= _mur_tmp; \ + _mur_key += 4; \ + } \ + \ + switch(_mur_len) \ + { \ + case 3: hashv ^= _mur_key[2] << 16; \ + case 2: hashv ^= _mur_key[1] << 8; \ + case 1: hashv ^= _mur_key[0]; \ + hashv *= _mur_m; \ + }; \ + \ + hashv ^= hashv >> 13; \ + hashv *= _mur_m; \ + hashv ^= hashv >> 15; \ + \ + bkt = hashv & (num_bkts-1); \ +} while(0) + +/* Appleby's MurmurHash version for alignment-sensitive archs like Sparc */ +#define HASH_MUR_ALIGNED(key,keylen,num_bkts,hashv,bkt) \ +do { \ + const unsigned int _mur_m = 0x5bd1e995; \ + const int _mur_r = 24; \ + hashv = 0xcafebabe ^ (keylen); \ + char *_mur_key = (char *)(key); \ + uint32_t _mur_len = keylen; \ + int _mur_align = (int)_mur_key & 3; \ + \ + if (_mur_align && (_mur_len >= 4)) { \ + unsigned _mur_t = 0, _mur_d = 0; \ + switch(_mur_align) { \ + case 1: _mur_t |= _mur_key[2] << 16; \ + case 2: _mur_t |= _mur_key[1] << 8; \ + case 3: _mur_t |= _mur_key[0]; \ + } \ + _mur_t <<= (8 * _mur_align); \ + _mur_key += 4-_mur_align; \ + _mur_len -= 4-_mur_align; \ + int _mur_sl = 8 * (4-_mur_align); \ + int _mur_sr = 8 * _mur_align; \ + \ + for (;_mur_len >= 4; _mur_len-=4) { \ + _mur_d = *(unsigned *)_mur_key; \ + _mur_t = (_mur_t >> _mur_sr) | (_mur_d << _mur_sl); \ + unsigned _mur_k = _mur_t; \ + _mur_k *= _mur_m; \ + _mur_k ^= _mur_k >> _mur_r; \ + _mur_k *= _mur_m; \ + hashv *= _mur_m; \ + hashv ^= _mur_k; \ + _mur_t = _mur_d; \ + _mur_key += 4; \ + } \ + _mur_d = 0; \ + if(_mur_len >= _mur_align) { \ + switch(_mur_align) { \ + case 3: _mur_d |= _mur_key[2] << 16; \ + case 2: _mur_d |= _mur_key[1] << 8; \ + case 1: _mur_d |= _mur_key[0]; \ + } \ + unsigned _mur_k = (_mur_t >> _mur_sr) | (_mur_d << _mur_sl); \ + _mur_k *= _mur_m; \ + _mur_k ^= _mur_k >> _mur_r; \ + _mur_k *= _mur_m; \ + hashv *= _mur_m; \ + hashv ^= _mur_k; \ + _mur_k += _mur_align; \ + _mur_len -= _mur_align; \ + \ + switch(_mur_len) \ + { \ + case 3: hashv ^= _mur_key[2] << 16; \ + case 2: hashv ^= _mur_key[1] << 8; \ + case 1: hashv ^= _mur_key[0]; \ + hashv *= _mur_m; \ + } \ + } else { \ + switch(_mur_len) \ + { \ + case 3: _mur_d ^= _mur_key[2] << 16; \ + case 2: _mur_d ^= _mur_key[1] << 8; \ + case 1: _mur_d ^= _mur_key[0]; \ + case 0: hashv ^= (_mur_t >> _mur_sr) | (_mur_d << _mur_sl); \ + hashv *= _mur_m; \ + } \ + } \ + \ + hashv ^= hashv >> 13; \ + hashv *= _mur_m; \ + hashv ^= hashv >> 15; \ + } else { \ + for (;_mur_len >= 4; _mur_len-=4) { \ + unsigned _mur_k = *(unsigned*)_mur_key; \ + _mur_k *= _mur_m; \ + _mur_k ^= _mur_k >> _mur_r; \ + _mur_k *= _mur_m; \ + hashv *= _mur_m; \ + hashv ^= _mur_k; \ + _mur_key += 4; \ + } \ + switch(_mur_len) \ + { \ + case 3: hashv ^= _mur_key[2] << 16; \ + case 2: hashv ^= _mur_key[1] << 8; \ + case 1: hashv ^= _mur_key[0]; \ + hashv *= _mur_m; \ + } \ + \ + hashv ^= hashv >> 13; \ + hashv *= _mur_m; \ + hashv ^= hashv >> 15; \ + } \ + bkt = hashv & (num_bkts-1); \ +} while(0) +#endif /* HASH_USING_NO_STRICT_ALIASING */ + +/* key comparison function; return 0 if keys equal */ +#define HASH_KEYCMP(a,b,len) memcmp(a,b,len) + +/* iterate over items in a known bucket to find desired item */ +#define HASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,out) \ +do { \ + if (head.hh_head) DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,head.hh_head)); \ + else out=NULL; \ + while (out) { \ + if (out->hh.keylen == keylen_in) { \ + if ((HASH_KEYCMP(out->hh.key,keyptr,keylen_in)) == 0) break; \ + } \ + if (out->hh.hh_next) DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,out->hh.hh_next)); \ + else out = NULL; \ + } \ +} while(0) + +/* add an item to a bucket */ +#define HASH_ADD_TO_BKT(head,addhh) \ +do { \ + head.count++; \ + (addhh)->hh_next = head.hh_head; \ + (addhh)->hh_prev = NULL; \ + if (head.hh_head) { (head).hh_head->hh_prev = (addhh); } \ + (head).hh_head=addhh; \ + if (head.count >= ((head.expand_mult+1) * HASH_BKT_CAPACITY_THRESH) \ + && (addhh)->tbl->noexpand != 1) { \ + HASH_EXPAND_BUCKETS((addhh)->tbl); \ + } \ +} while(0) + +/* remove an item from a given bucket */ +#define HASH_DEL_IN_BKT(hh,head,hh_del) \ + (head).count--; \ + if ((head).hh_head == hh_del) { \ + (head).hh_head = hh_del->hh_next; \ + } \ + if (hh_del->hh_prev) { \ + hh_del->hh_prev->hh_next = hh_del->hh_next; \ + } \ + if (hh_del->hh_next) { \ + hh_del->hh_next->hh_prev = hh_del->hh_prev; \ + } + +/* Bucket expansion has the effect of doubling the number of buckets + * and redistributing the items into the new buckets. Ideally the + * items will distribute more or less evenly into the new buckets + * (the extent to which this is true is a measure of the quality of + * the hash function as it applies to the key domain). + * + * With the items distributed into more buckets, the chain length + * (item count) in each bucket is reduced. Thus by expanding buckets + * the hash keeps a bound on the chain length. This bounded chain + * length is the essence of how a hash provides constant time lookup. + * + * The calculation of tbl->ideal_chain_maxlen below deserves some + * explanation. First, keep in mind that we're calculating the ideal + * maximum chain length based on the *new* (doubled) bucket count. + * In fractions this is just n/b (n=number of items,b=new num buckets). + * Since the ideal chain length is an integer, we want to calculate + * ceil(n/b). We don't depend on floating point arithmetic in this + * hash, so to calculate ceil(n/b) with integers we could write + * + * ceil(n/b) = (n/b) + ((n%b)?1:0) + * + * and in fact a previous version of this hash did just that. + * But now we have improved things a bit by recognizing that b is + * always a power of two. We keep its base 2 log handy (call it lb), + * so now we can write this with a bit shift and logical AND: + * + * ceil(n/b) = (n>>lb) + ( (n & (b-1)) ? 1:0) + * + */ +#define HASH_EXPAND_BUCKETS(tbl) \ +do { \ + unsigned _he_bkt; \ + unsigned _he_bkt_i; \ + struct UT_hash_handle *_he_thh, *_he_hh_nxt; \ + UT_hash_bucket *_he_new_buckets, *_he_newbkt; \ + _he_new_buckets = (UT_hash_bucket*)uthash_malloc( \ + 2 * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ + if (!_he_new_buckets) { uthash_fatal( "out of memory"); } \ + memset(_he_new_buckets, 0, \ + 2 * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ + tbl->ideal_chain_maxlen = \ + (tbl->num_items >> (tbl->log2_num_buckets+1)) + \ + ((tbl->num_items & ((tbl->num_buckets*2)-1)) ? 1 : 0); \ + tbl->nonideal_items = 0; \ + for(_he_bkt_i = 0; _he_bkt_i < tbl->num_buckets; _he_bkt_i++) \ + { \ + _he_thh = tbl->buckets[ _he_bkt_i ].hh_head; \ + while (_he_thh) { \ + _he_hh_nxt = _he_thh->hh_next; \ + HASH_TO_BKT( _he_thh->hashv, tbl->num_buckets*2, _he_bkt); \ + _he_newbkt = &(_he_new_buckets[ _he_bkt ]); \ + if (++(_he_newbkt->count) > tbl->ideal_chain_maxlen) { \ + tbl->nonideal_items++; \ + _he_newbkt->expand_mult = _he_newbkt->count / \ + tbl->ideal_chain_maxlen; \ + } \ + _he_thh->hh_prev = NULL; \ + _he_thh->hh_next = _he_newbkt->hh_head; \ + if (_he_newbkt->hh_head) _he_newbkt->hh_head->hh_prev = \ + _he_thh; \ + _he_newbkt->hh_head = _he_thh; \ + _he_thh = _he_hh_nxt; \ + } \ + } \ + uthash_free( tbl->buckets, tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \ + tbl->num_buckets *= 2; \ + tbl->log2_num_buckets++; \ + tbl->buckets = _he_new_buckets; \ + tbl->ineff_expands = (tbl->nonideal_items > (tbl->num_items >> 1)) ? \ + (tbl->ineff_expands+1) : 0; \ + if (tbl->ineff_expands > 1) { \ + tbl->noexpand=1; \ + uthash_noexpand_fyi(tbl); \ + } \ + uthash_expand_fyi(tbl); \ +} while(0) + + +/* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */ +/* Note that HASH_SORT assumes the hash handle name to be hh. + * HASH_SRT was added to allow the hash handle name to be passed in. */ +#define HASH_SORT(head,cmpfcn) HASH_SRT(hh,head,cmpfcn) +#define HASH_SRT(hh,head,cmpfcn) \ +do { \ + unsigned _hs_i; \ + unsigned _hs_looping,_hs_nmerges,_hs_insize,_hs_psize,_hs_qsize; \ + struct UT_hash_handle *_hs_p, *_hs_q, *_hs_e, *_hs_list, *_hs_tail; \ + if (head) { \ + _hs_insize = 1; \ + _hs_looping = 1; \ + _hs_list = &((head)->hh); \ + while (_hs_looping) { \ + _hs_p = _hs_list; \ + _hs_list = NULL; \ + _hs_tail = NULL; \ + _hs_nmerges = 0; \ + while (_hs_p) { \ + _hs_nmerges++; \ + _hs_q = _hs_p; \ + _hs_psize = 0; \ + for ( _hs_i = 0; _hs_i < _hs_insize; _hs_i++ ) { \ + _hs_psize++; \ + _hs_q = (UT_hash_handle*)((_hs_q->next) ? \ + ((void*)((char*)(_hs_q->next) + \ + (head)->hh.tbl->hho)) : NULL); \ + if (! (_hs_q) ) break; \ + } \ + _hs_qsize = _hs_insize; \ + while ((_hs_psize > 0) || ((_hs_qsize > 0) && _hs_q )) { \ + if (_hs_psize == 0) { \ + _hs_e = _hs_q; \ + _hs_q = (UT_hash_handle*)((_hs_q->next) ? \ + ((void*)((char*)(_hs_q->next) + \ + (head)->hh.tbl->hho)) : NULL); \ + _hs_qsize--; \ + } else if ( (_hs_qsize == 0) || !(_hs_q) ) { \ + _hs_e = _hs_p; \ + _hs_p = (UT_hash_handle*)((_hs_p->next) ? \ + ((void*)((char*)(_hs_p->next) + \ + (head)->hh.tbl->hho)) : NULL); \ + _hs_psize--; \ + } else if (( \ + cmpfcn(DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_p)), \ + DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_q))) \ + ) <= 0) { \ + _hs_e = _hs_p; \ + _hs_p = (UT_hash_handle*)((_hs_p->next) ? \ + ((void*)((char*)(_hs_p->next) + \ + (head)->hh.tbl->hho)) : NULL); \ + _hs_psize--; \ + } else { \ + _hs_e = _hs_q; \ + _hs_q = (UT_hash_handle*)((_hs_q->next) ? \ + ((void*)((char*)(_hs_q->next) + \ + (head)->hh.tbl->hho)) : NULL); \ + _hs_qsize--; \ + } \ + if ( _hs_tail ) { \ + _hs_tail->next = ((_hs_e) ? \ + ELMT_FROM_HH((head)->hh.tbl,_hs_e) : NULL); \ + } else { \ + _hs_list = _hs_e; \ + } \ + _hs_e->prev = ((_hs_tail) ? \ + ELMT_FROM_HH((head)->hh.tbl,_hs_tail) : NULL); \ + _hs_tail = _hs_e; \ + } \ + _hs_p = _hs_q; \ + } \ + _hs_tail->next = NULL; \ + if ( _hs_nmerges <= 1 ) { \ + _hs_looping=0; \ + (head)->hh.tbl->tail = _hs_tail; \ + DECLTYPE_ASSIGN(head,ELMT_FROM_HH((head)->hh.tbl, _hs_list)); \ + } \ + _hs_insize *= 2; \ + } \ + HASH_FSCK(hh,head); \ + } \ +} while (0) + +/* This function selects items from one hash into another hash. + * The end result is that the selected items have dual presence + * in both hashes. There is no copy of the items made; rather + * they are added into the new hash through a secondary hash + * hash handle that must be present in the structure. */ +#define HASH_SELECT(hh_dst, dst, hh_src, src, cond) \ +do { \ + unsigned _src_bkt, _dst_bkt; \ + void *_last_elt=NULL, *_elt; \ + UT_hash_handle *_src_hh, *_dst_hh, *_last_elt_hh=NULL; \ + ptrdiff_t _dst_hho = ((char*)(&(dst)->hh_dst) - (char*)(dst)); \ + if (src) { \ + for(_src_bkt=0; _src_bkt < (src)->hh_src.tbl->num_buckets; _src_bkt++) { \ + for(_src_hh = (src)->hh_src.tbl->buckets[_src_bkt].hh_head; \ + _src_hh; \ + _src_hh = _src_hh->hh_next) { \ + _elt = ELMT_FROM_HH((src)->hh_src.tbl, _src_hh); \ + if (cond(_elt)) { \ + _dst_hh = (UT_hash_handle*)(((char*)_elt) + _dst_hho); \ + _dst_hh->key = _src_hh->key; \ + _dst_hh->keylen = _src_hh->keylen; \ + _dst_hh->hashv = _src_hh->hashv; \ + _dst_hh->prev = _last_elt; \ + _dst_hh->next = NULL; \ + if (_last_elt_hh) { _last_elt_hh->next = _elt; } \ + if (!dst) { \ + DECLTYPE_ASSIGN(dst,_elt); \ + HASH_MAKE_TABLE(hh_dst,dst); \ + } else { \ + _dst_hh->tbl = (dst)->hh_dst.tbl; \ + } \ + HASH_TO_BKT(_dst_hh->hashv, _dst_hh->tbl->num_buckets, _dst_bkt); \ + HASH_ADD_TO_BKT(_dst_hh->tbl->buckets[_dst_bkt],_dst_hh); \ + (dst)->hh_dst.tbl->num_items++; \ + _last_elt = _elt; \ + _last_elt_hh = _dst_hh; \ + } \ + } \ + } \ + } \ + HASH_FSCK(hh_dst,dst); \ +} while (0) + +#define HASH_CLEAR(hh,head) \ +do { \ + if (head) { \ + uthash_free((head)->hh.tbl->buckets, \ + (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket)); \ + uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ + (head)=NULL; \ + } \ +} while(0) + +#ifdef NO_DECLTYPE +#define HASH_ITER(hh,head,el,tmp) \ +for((el)=(head), (*(char**)(&(tmp)))=(char*)((head)?(head)->hh.next:NULL); \ + el; (el)=(tmp),(*(char**)(&(tmp)))=(char*)((tmp)?(tmp)->hh.next:NULL)) +#else +#define HASH_ITER(hh,head,el,tmp) \ +for((el)=(head),(tmp)=DECLTYPE(el)((head)?(head)->hh.next:NULL); \ + el; (el)=(tmp),(tmp)=DECLTYPE(el)((tmp)?(tmp)->hh.next:NULL)) +#endif + +/* obtain a count of items in the hash */ +#define HASH_COUNT(head) HASH_CNT(hh,head) +#define HASH_CNT(hh,head) ((head)?((head)->hh.tbl->num_items):0) + +typedef struct UT_hash_bucket { + struct UT_hash_handle *hh_head; + unsigned count; + + /* expand_mult is normally set to 0. In this situation, the max chain length + * threshold is enforced at its default value, HASH_BKT_CAPACITY_THRESH. (If + * the bucket's chain exceeds this length, bucket expansion is triggered). + * However, setting expand_mult to a non-zero value delays bucket expansion + * (that would be triggered by additions to this particular bucket) + * until its chain length reaches a *multiple* of HASH_BKT_CAPACITY_THRESH. + * (The multiplier is simply expand_mult+1). The whole idea of this + * multiplier is to reduce bucket expansions, since they are expensive, in + * situations where we know that a particular bucket tends to be overused. + * It is better to let its chain length grow to a longer yet-still-bounded + * value, than to do an O(n) bucket expansion too often. + */ + unsigned expand_mult; + +} UT_hash_bucket; + +/* random signature used only to find hash tables in external analysis */ +#define HASH_SIGNATURE 0xa0111fe1 +#define HASH_BLOOM_SIGNATURE 0xb12220f2 + +typedef struct UT_hash_table { + UT_hash_bucket *buckets; + unsigned num_buckets, log2_num_buckets; + unsigned num_items; + struct UT_hash_handle *tail; /* tail hh in app order, for fast append */ + ptrdiff_t hho; /* hash handle offset (byte pos of hash handle in element */ + + /* in an ideal situation (all buckets used equally), no bucket would have + * more than ceil(#items/#buckets) items. that's the ideal chain length. */ + unsigned ideal_chain_maxlen; + + /* nonideal_items is the number of items in the hash whose chain position + * exceeds the ideal chain maxlen. these items pay the penalty for an uneven + * hash distribution; reaching them in a chain traversal takes >ideal steps */ + unsigned nonideal_items; + + /* ineffective expands occur when a bucket doubling was performed, but + * afterward, more than half the items in the hash had nonideal chain + * positions. If this happens on two consecutive expansions we inhibit any + * further expansion, as it's not helping; this happens when the hash + * function isn't a good fit for the key domain. When expansion is inhibited + * the hash will still work, albeit no longer in constant time. */ + unsigned ineff_expands, noexpand; + + uint32_t signature; /* used only to find hash tables in external analysis */ +#ifdef HASH_BLOOM + uint32_t bloom_sig; /* used only to test bloom exists in external analysis */ + uint8_t *bloom_bv; + char bloom_nbits; +#endif + +} UT_hash_table; + +typedef struct UT_hash_handle { + struct UT_hash_table *tbl; + void *prev; /* prev element in app order */ + void *next; /* next element in app order */ + struct UT_hash_handle *hh_prev; /* previous hh in bucket order */ + struct UT_hash_handle *hh_next; /* next hh in bucket order */ + void *key; /* ptr to enclosing struct's key */ + unsigned keylen; /* enclosing struct's key len */ + unsigned hashv; /* result of hash-fcn(key) */ +} UT_hash_handle; + +#endif /* UTHASH_H */ diff --git a/libs/cocos2d/Support/utlist.h b/libs/cocos2d/Support/utlist.h new file mode 100755 index 0000000..34c725b --- /dev/null +++ b/libs/cocos2d/Support/utlist.h @@ -0,0 +1,490 @@ +/* +Copyright (c) 2007-2010, Troy D. Hanson http://uthash.sourceforge.net +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS +IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A +PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER +OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef UTLIST_H +#define UTLIST_H + +#define UTLIST_VERSION 1.9.1 + +/* + * This file contains macros to manipulate singly and doubly-linked lists. + * + * 1. LL_ macros: singly-linked lists. + * 2. DL_ macros: doubly-linked lists. + * 3. CDL_ macros: circular doubly-linked lists. + * + * To use singly-linked lists, your structure must have a "next" pointer. + * To use doubly-linked lists, your structure must "prev" and "next" pointers. + * Either way, the pointer to the head of the list must be initialized to NULL. + * + * ----------------.EXAMPLE ------------------------- + * struct item { + * int id; + * struct item *prev, *next; + * } + * + * struct item *list = NULL: + * + * int main() { + * struct item *item; + * ... allocate and populate item ... + * DL_APPEND(list, item); + * } + * -------------------------------------------------- + * + * For doubly-linked lists, the append and delete macros are O(1) + * For singly-linked lists, append and delete are O(n) but prepend is O(1) + * The sort macro is O(n log(n)) for all types of single/double/circular lists. + */ + +/* These macros use decltype or the earlier __typeof GNU extension. + As decltype is only available in newer compilers (VS2010 or gcc 4.3+ + when compiling c++ code), this code uses whatever method is needed + or, for VS2008 where neither is available, uses casting workarounds. */ +#ifdef _MSC_VER /* MS compiler */ +#if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */ +#define LDECLTYPE(x) decltype(x) +#else /* VS2008 or older (or VS2010 in C mode) */ +#define NO_DECLTYPE +#define LDECLTYPE(x) char* +#endif +#else /* GNU, Sun and other compilers */ +#define LDECLTYPE(x) __typeof(x) +#endif + +/* for VS2008 we use some workarounds to get around the lack of decltype, + * namely, we always reassign our tmp variable to the list head if we need + * to dereference its prev/next pointers, and save/restore the real head.*/ +#ifdef NO_DECLTYPE +#define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); } +#define _NEXT(elt,list) ((char*)((list)->next)) +#define _NEXTASGN(elt,list,to) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); } +#define _PREV(elt,list) ((char*)((list)->prev)) +#define _PREVASGN(elt,list,to) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); } +#define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; } +#define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); } +#else +#define _SV(elt,list) +#define _NEXT(elt,list) ((elt)->next) +#define _NEXTASGN(elt,list,to) ((elt)->next)=(to) +#define _PREV(elt,list) ((elt)->prev) +#define _PREVASGN(elt,list,to) ((elt)->prev)=(to) +#define _RS(list) +#define _CASTASGN(a,b) (a)=(b) +#endif + +/****************************************************************************** + * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort * + * Unwieldy variable names used here to avoid shadowing passed-in variables. * + *****************************************************************************/ +#define LL_SORT(list, cmp) \ +do { \ + LDECLTYPE(list) _ls_p; \ + LDECLTYPE(list) _ls_q; \ + LDECLTYPE(list) _ls_e; \ + LDECLTYPE(list) _ls_tail; \ + LDECLTYPE(list) _ls_oldhead; \ + LDECLTYPE(list) _tmp; \ + int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ + if (list) { \ + _ls_insize = 1; \ + _ls_looping = 1; \ + while (_ls_looping) { \ + _CASTASGN(_ls_p,list); \ + _CASTASGN(_ls_oldhead,list); \ + list = NULL; \ + _ls_tail = NULL; \ + _ls_nmerges = 0; \ + while (_ls_p) { \ + _ls_nmerges++; \ + _ls_q = _ls_p; \ + _ls_psize = 0; \ + for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ + _ls_psize++; \ + _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); \ + if (!_ls_q) break; \ + } \ + _ls_qsize = _ls_insize; \ + while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ + if (_ls_psize == 0) { \ + _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ + } else if (_ls_qsize == 0 || !_ls_q) { \ + _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \ + } else if (cmp(_ls_p,_ls_q) <= 0) { \ + _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \ + } else { \ + _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ + } \ + if (_ls_tail) { \ + _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \ + } else { \ + _CASTASGN(list,_ls_e); \ + } \ + _ls_tail = _ls_e; \ + } \ + _ls_p = _ls_q; \ + } \ + _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list); \ + if (_ls_nmerges <= 1) { \ + _ls_looping=0; \ + } \ + _ls_insize *= 2; \ + } \ + } else _tmp=NULL; /* quiet gcc unused variable warning */ \ +} while (0) + +#define DL_SORT(list, cmp) \ +do { \ + LDECLTYPE(list) _ls_p; \ + LDECLTYPE(list) _ls_q; \ + LDECLTYPE(list) _ls_e; \ + LDECLTYPE(list) _ls_tail; \ + LDECLTYPE(list) _ls_oldhead; \ + LDECLTYPE(list) _tmp; \ + int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ + if (list) { \ + _ls_insize = 1; \ + _ls_looping = 1; \ + while (_ls_looping) { \ + _CASTASGN(_ls_p,list); \ + _CASTASGN(_ls_oldhead,list); \ + list = NULL; \ + _ls_tail = NULL; \ + _ls_nmerges = 0; \ + while (_ls_p) { \ + _ls_nmerges++; \ + _ls_q = _ls_p; \ + _ls_psize = 0; \ + for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ + _ls_psize++; \ + _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); \ + if (!_ls_q) break; \ + } \ + _ls_qsize = _ls_insize; \ + while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ + if (_ls_psize == 0) { \ + _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ + } else if (_ls_qsize == 0 || !_ls_q) { \ + _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \ + } else if (cmp(_ls_p,_ls_q) <= 0) { \ + _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \ + } else { \ + _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ + } \ + if (_ls_tail) { \ + _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \ + } else { \ + _CASTASGN(list,_ls_e); \ + } \ + _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list); \ + _ls_tail = _ls_e; \ + } \ + _ls_p = _ls_q; \ + } \ + _CASTASGN(list->prev, _ls_tail); \ + _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list); \ + if (_ls_nmerges <= 1) { \ + _ls_looping=0; \ + } \ + _ls_insize *= 2; \ + } \ + } else _tmp=NULL; /* quiet gcc unused variable warning */ \ +} while (0) + +#define CDL_SORT(list, cmp) \ +do { \ + LDECLTYPE(list) _ls_p; \ + LDECLTYPE(list) _ls_q; \ + LDECLTYPE(list) _ls_e; \ + LDECLTYPE(list) _ls_tail; \ + LDECLTYPE(list) _ls_oldhead; \ + LDECLTYPE(list) _tmp; \ + LDECLTYPE(list) _tmp2; \ + int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ + if (list) { \ + _ls_insize = 1; \ + _ls_looping = 1; \ + while (_ls_looping) { \ + _CASTASGN(_ls_p,list); \ + _CASTASGN(_ls_oldhead,list); \ + list = NULL; \ + _ls_tail = NULL; \ + _ls_nmerges = 0; \ + while (_ls_p) { \ + _ls_nmerges++; \ + _ls_q = _ls_p; \ + _ls_psize = 0; \ + for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ + _ls_psize++; \ + _SV(_ls_q,list); \ + if (_NEXT(_ls_q,list) == _ls_oldhead) { \ + _ls_q = NULL; \ + } else { \ + _ls_q = _NEXT(_ls_q,list); \ + } \ + _RS(list); \ + if (!_ls_q) break; \ + } \ + _ls_qsize = _ls_insize; \ + while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ + if (_ls_psize == 0) { \ + _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ + if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ + } else if (_ls_qsize == 0 || !_ls_q) { \ + _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \ + if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ + } else if (cmp(_ls_p,_ls_q) <= 0) { \ + _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \ + if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ + } else { \ + _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ + if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ + } \ + if (_ls_tail) { \ + _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \ + } else { \ + _CASTASGN(list,_ls_e); \ + } \ + _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list); \ + _ls_tail = _ls_e; \ + } \ + _ls_p = _ls_q; \ + } \ + _CASTASGN(list->prev,_ls_tail); \ + _CASTASGN(_tmp2,list); \ + _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp2); _RS(list); \ + if (_ls_nmerges <= 1) { \ + _ls_looping=0; \ + } \ + _ls_insize *= 2; \ + } \ + } else _tmp=NULL; /* quiet gcc unused variable warning */ \ +} while (0) + +/****************************************************************************** + * singly linked list macros (non-circular) * + *****************************************************************************/ +#define LL_PREPEND(head,add) \ +do { \ + (add)->next = head; \ + head = add; \ +} while (0) + +#define LL_APPEND(head,add) \ +do { \ + LDECLTYPE(head) _tmp; \ + (add)->next=NULL; \ + if (head) { \ + _tmp = head; \ + while (_tmp->next) { _tmp = _tmp->next; } \ + _tmp->next=(add); \ + } else { \ + (head)=(add); \ + } \ +} while (0) + +#define LL_DELETE(head,del) \ +do { \ + LDECLTYPE(head) _tmp; \ + if ((head) == (del)) { \ + (head)=(head)->next; \ + } else { \ + _tmp = head; \ + while (_tmp->next && (_tmp->next != (del))) { \ + _tmp = _tmp->next; \ + } \ + if (_tmp->next) { \ + _tmp->next = ((del)->next); \ + } \ + } \ +} while (0) + +/* Here are VS2008 replacements for LL_APPEND and LL_DELETE */ +#define LL_APPEND_VS2008(head,add) \ +do { \ + if (head) { \ + (add)->next = head; /* use add->next as a temp variable */ \ + while ((add)->next->next) { (add)->next = (add)->next->next; } \ + (add)->next->next=(add); \ + } else { \ + (head)=(add); \ + } \ + (add)->next=NULL; \ +} while (0) + +#define LL_DELETE_VS2008(head,del) \ +do { \ + if ((head) == (del)) { \ + (head)=(head)->next; \ + } else { \ + char *_tmp = (char*)(head); \ + while (head->next && (head->next != (del))) { \ + head = head->next; \ + } \ + if (head->next) { \ + head->next = ((del)->next); \ + } \ + { \ + char **_head_alias = (char**)&(head); \ + *_head_alias = _tmp; \ + } \ + } \ +} while (0) +#ifdef NO_DECLTYPE +#undef LL_APPEND +#define LL_APPEND LL_APPEND_VS2008 +#undef LL_DELETE +#define LL_DELETE LL_DELETE_VS2008 +#endif +/* end VS2008 replacements */ + +#define LL_FOREACH(head,el) \ + for(el=head;el;el=el->next) + +#define LL_FOREACH_SAFE(head,el,tmp) \ + for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp) + +#define LL_SEARCH_SCALAR(head,out,field,val) \ +do { \ + LL_FOREACH(head,out) { \ + if ((out)->field == (val)) break; \ + } \ +} while(0) + +#define LL_SEARCH(head,out,elt,cmp) \ +do { \ + LL_FOREACH(head,out) { \ + if ((cmp(out,elt))==0) break; \ + } \ +} while(0) + +/****************************************************************************** + * doubly linked list macros (non-circular) * + *****************************************************************************/ +#define DL_PREPEND(head,add) \ +do { \ + (add)->next = head; \ + if (head) { \ + (add)->prev = (head)->prev; \ + (head)->prev = (add); \ + } else { \ + (add)->prev = (add); \ + } \ + (head) = (add); \ +} while (0) + +#define DL_APPEND(head,add) \ +do { \ + if (head) { \ + (add)->prev = (head)->prev; \ + (head)->prev->next = (add); \ + (head)->prev = (add); \ + (add)->next = NULL; \ + } else { \ + (head)=(add); \ + (head)->prev = (head); \ + (head)->next = NULL; \ + } \ +} while (0); + +#define DL_DELETE(head,del) \ +do { \ + if ((del)->prev == (del)) { \ + (head)=NULL; \ + } else if ((del)==(head)) { \ + (del)->next->prev = (del)->prev; \ + (head) = (del)->next; \ + } else { \ + (del)->prev->next = (del)->next; \ + if ((del)->next) { \ + (del)->next->prev = (del)->prev; \ + } else { \ + (head)->prev = (del)->prev; \ + } \ + } \ +} while (0); + + +#define DL_FOREACH(head,el) \ + for(el=head;el;el=el->next) + +/* this version is safe for deleting the elements during iteration */ +#define DL_FOREACH_SAFE(head,el,tmp) \ + for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp) + +/* these are identical to their singly-linked list counterparts */ +#define DL_SEARCH_SCALAR LL_SEARCH_SCALAR +#define DL_SEARCH LL_SEARCH + +/****************************************************************************** + * circular doubly linked list macros * + *****************************************************************************/ +#define CDL_PREPEND(head,add) \ +do { \ + if (head) { \ + (add)->prev = (head)->prev; \ + (add)->next = (head); \ + (head)->prev = (add); \ + (add)->prev->next = (add); \ + } else { \ + (add)->prev = (add); \ + (add)->next = (add); \ + } \ +(head)=(add); \ +} while (0) + +#define CDL_DELETE(head,del) \ +do { \ + if ( ((head)==(del)) && ((head)->next == (head))) { \ + (head) = 0L; \ + } else { \ + (del)->next->prev = (del)->prev; \ + (del)->prev->next = (del)->next; \ + if ((del) == (head)) (head)=(del)->next; \ + } \ +} while (0); + +#define CDL_FOREACH(head,el) \ + for(el=head;el;el=(el->next==head ? 0L : el->next)) + +#define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \ + for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \ + (el) && ((tmp2)=(el)->next, 1); \ + ((el) = (((el)==(tmp1)) ? 0L : (tmp2)))) + +#define CDL_SEARCH_SCALAR(head,out,field,val) \ +do { \ + CDL_FOREACH(head,out) { \ + if ((out)->field == (val)) break; \ + } \ +} while(0) + +#define CDL_SEARCH(head,out,elt,cmp) \ +do { \ + CDL_FOREACH(head,out) { \ + if ((cmp(out,elt))==0) break; \ + } \ +} while(0) + +#endif /* UTLIST_H */ + -- cgit 1.4.1