Index: src/OFObject.m ================================================================== --- src/OFObject.m +++ src/OFObject.m @@ -219,11 +219,15 @@ { #if !defined(OF_APPLE_RUNTIME) || defined(__OBJC2__) objc_setUncaughtExceptionHandler(uncaughtExceptionHandler); #endif +#if defined(OF_APPLE_RUNTIME) objc_setForwardHandler((void*)&of_forward, (void*)&of_forward_stret); +#else + objc_setForwardHandler((IMP)&of_forward, (IMP)&of_forward_stret); +#endif #ifdef HAVE_OBJC_ENUMERATIONMUTATION objc_setEnumerationMutationHandler(enumerationMutationHandler); #endif Index: src/runtime/Makefile ================================================================== --- src/runtime/Makefile +++ src/runtime/Makefile @@ -6,10 +6,11 @@ STATIC_LIB_NOINST = ${RUNTIME_A} SRCS = arc.m \ category.m \ class.m \ + dtable.m \ exception.m \ hashtable.m \ init.m \ lookup.m \ property.m \ Index: src/runtime/class.m ================================================================== --- src/runtime/class.m +++ src/runtime/class.m @@ -23,21 +23,17 @@ #include #import "runtime.h" #import "runtime-private.h" -struct sparsearray { - void *next[256]; -}; - static struct objc_hashtable *classes = NULL; static unsigned classes_cnt = 0; static Class *load_queue = NULL; static size_t load_queue_cnt = 0; -static struct objc_sparsearray *empty_dtable = NULL; +static struct objc_dtable *empty_dtable = NULL; static unsigned lookups_till_fast_path = 128; -static struct sparsearray *sparsearray = NULL; +static struct objc_sparsearray *fast_path = NULL; static void register_class(struct objc_abi_class *cls) { if (classes == NULL) @@ -45,11 +41,11 @@ objc_hash_string, objc_equal_string, 2); objc_hashtable_set(classes, cls->name, cls); if (empty_dtable == NULL) - empty_dtable = objc_sparsearray_new(); + empty_dtable = objc_dtable_new(); cls->dtable = empty_dtable; cls->metaclass->dtable = empty_dtable; if (strcmp(cls->name, "Protocol") != 0) @@ -80,11 +76,11 @@ } Class objc_classname_to_class(const char *name, bool cache) { - Class c; + Class cls; if (classes == NULL) return Nil; /* @@ -106,61 +102,30 @@ * as a call into objc_classname_to_class(). The reason for this is * that if the runtime calls into objc_classname_to_class(), it already * has the lock and thus the performance gain would be small, but it * would waste memory. */ - if (cache && sparsearray != NULL) { - uintptr_t clsidx = (uintptr_t)name; - struct sparsearray *iter = sparsearray; - uint_fast8_t i; - - for (i = 0; i < sizeof(uintptr_t) - 1; i++) { - uintptr_t idx = (clsidx >> - ((sizeof(uintptr_t) - i - 1) * 8)) & 0xFF; - - if ((iter = iter->next[idx]) == NULL) - break; - } - - if (iter != NULL && (c = iter->next[clsidx & 0xFF]) != Nil) - return c; + if (cache && fast_path != NULL) { + cls = objc_sparsearray_get(fast_path, (uintptr_t)name); + + if (cls != Nil) + return cls; } objc_global_mutex_lock(); - c = (Class)((uintptr_t)objc_hashtable_get(classes, name) & ~1); - - if (cache && sparsearray == NULL && --lookups_till_fast_path == 0) - if ((sparsearray = calloc(1, - sizeof(struct sparsearray))) == NULL) - OBJC_ERROR("Failed to allocate memory for class lookup " - "fast path!"); - - if (cache && sparsearray != NULL) { - uintptr_t clsidx = (uintptr_t)name; - struct sparsearray *iter = sparsearray; - uint_fast8_t i; - - for (i = 0; i < sizeof(uintptr_t) - 1; i++) { - uintptr_t idx = (clsidx >> - ((sizeof(uintptr_t) - i - 1) * 8)) & 0xFF; - - if (iter->next[idx] == NULL) - if ((iter->next[idx] = calloc(1, - sizeof(struct sparsearray))) == NULL) - OBJC_ERROR("Failed to allocate memory " - "for class lookup fast path!"); - - iter = iter->next[idx]; - } - - iter->next[clsidx & 0xFF] = c; - } + cls = (Class)((uintptr_t)objc_hashtable_get(classes, name) & ~1); + + if (cache && fast_path == NULL && --lookups_till_fast_path == 0) + fast_path = objc_sparsearray_new(sizeof(uintptr_t)); + + if (cache && fast_path != NULL) + objc_sparsearray_set(fast_path, (uintptr_t)name, cls); objc_global_mutex_unlock(); - return c; + return cls; } static void call_method(Class cls, const char *method) { @@ -217,18 +182,18 @@ if (!(cls->info & OBJC_CLASS_INFO_DTABLE)) return; if (cls->dtable == empty_dtable) - cls->dtable = objc_sparsearray_new(); + cls->dtable = objc_dtable_new(); if (cls->superclass != Nil) - objc_sparsearray_copy(cls->dtable, cls->superclass->dtable); + objc_dtable_copy(cls->dtable, cls->superclass->dtable); for (ml = cls->methodlist; ml != NULL; ml = ml->next) for (i = 0; i < ml->count; i++) - objc_sparsearray_set(cls->dtable, + objc_dtable_set(cls->dtable, (uint32_t)ml->methods[i].sel.uid, ml->methods[i].imp); if ((cats = objc_categories_for_class(cls)) != NULL) { for (i = 0; cats[i] != NULL; i++) { @@ -237,11 +202,11 @@ ml = (cls->info & OBJC_CLASS_INFO_CLASS ? cats[i]->instance_methods : cats[i]->class_methods); for (; ml != NULL; ml = ml->next) for (j = 0; j < ml->count; j++) - objc_sparsearray_set(cls->dtable, + objc_dtable_set(cls->dtable, (uint32_t)ml->methods[j].sel.uid, ml->methods[j].imp); } } @@ -843,11 +808,11 @@ free(rcls->subclass_list); rcls->subclass_list = NULL; } if (rcls->dtable != NULL && rcls->dtable != empty_dtable) - objc_sparsearray_free(rcls->dtable); + objc_dtable_free(rcls->dtable); rcls->dtable = NULL; if (rcls->superclass != Nil) cls->superclass = rcls->superclass->name; @@ -871,24 +836,10 @@ unregister_class(cls); unregister_class(cls->isa); } -static void -free_sparsearray(struct sparsearray *sa, size_t depth) -{ - uint_fast16_t i; - - if (sa == NULL || depth == 0) - return; - - for (i = 0; i < 256; i++) - free_sparsearray(sa->next[i], depth - 1); - - free(sa); -} - void objc_unregister_all_classes(void) { uint_fast32_t i; @@ -918,15 +869,15 @@ } assert(classes_cnt == 0); if (empty_dtable != NULL) { - objc_sparsearray_free(empty_dtable); + objc_dtable_free(empty_dtable); empty_dtable = NULL; } - free_sparsearray(sparsearray, sizeof(uintptr_t)); - sparsearray = NULL; + objc_sparsearray_free(fast_path); + fast_path = NULL; objc_hashtable_free(classes); classes = NULL; } ADDED src/runtime/dtable.m Index: src/runtime/dtable.m ================================================================== --- src/runtime/dtable.m +++ src/runtime/dtable.m @@ -0,0 +1,217 @@ +/* + * Copyright (c) 2008, 2009, 2010, 2011, 2012, 2013, 2014 + * Jonathan Schleifer + * + * All rights reserved. + * + * This file is part of ObjFW. It may be distributed under the terms of the + * Q Public License 1.0, which can be found in the file LICENSE.QPL included in + * the packaging of this file. + * + * Alternatively, it may be distributed under the terms of the GNU General + * Public License, either version 2 or 3, which can be found in the file + * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this + * file. + */ + +#include "config.h" + +#include +#include + +#import "runtime.h" +#import "runtime-private.h" + +static struct objc_dtable_level2 *empty_level2 = NULL; +#ifdef OF_SELUID24 +static struct objc_dtable_level3 *empty_level3 = NULL; +#endif + +static void +init(void) +{ + uint_fast16_t i; + + empty_level2 = malloc(sizeof(struct objc_dtable_level2)); + if (empty_level2 == NULL) + OBJC_ERROR("Not enough memory to allocate dtable!"); + +#ifdef OF_SELUID24 + empty_level3 = malloc(sizeof(struct objc_dtable_level3)); + if (empty_level3 == NULL) + OBJC_ERROR("Not enough memory to allocate dtable!"); +#endif + +#ifdef OF_SELUID24 + for (i = 0; i < 256; i++) { + empty_level2->buckets[i] = empty_level3; + empty_level3->buckets[i] = (IMP)0; + } +#else + for (i = 0; i < 256; i++) + empty_level2->buckets[i] = (IMP)0; +#endif +} + +struct objc_dtable* +objc_dtable_new(void) +{ + struct objc_dtable *dtable; + uint_fast16_t i; + +#ifdef OF_SELUID24 + if (empty_level2 == NULL || empty_level3 == NULL) + init(); +#else + if (empty_level2 == NULL) + init(); +#endif + + if ((dtable = malloc(sizeof(struct objc_dtable))) == NULL) + OBJC_ERROR("Not enough memory to allocate dtable!"); + + for (i = 0; i < 256; i++) + dtable->buckets[i] = empty_level2; + + return dtable; +} + +void +objc_dtable_copy(struct objc_dtable *dst, struct objc_dtable *src) +{ + uint_fast16_t i, j; +#ifdef OF_SELUID24 + uint_fast16_t k; +#endif + uint32_t idx; + + for (i = 0; i < 256; i++) { + if (src->buckets[i] == empty_level2) + continue; + +#ifdef OF_SELUID24 + for (j = 0; j < 256; j++) { + if (src->buckets[i]->buckets[j] == empty_level3) + continue; + + for (k = 0; k < 256; k++) { + IMP obj; + + obj = src->buckets[i]->buckets[j]->buckets[k]; + + if (obj == (IMP)0) + continue; + + idx = (uint32_t) + (((uint32_t)i << 16) | (j << 8) | k); + objc_dtable_set(dst, idx, obj); + } + } +#else + for (j = 0; j < 256; j++) { + IMP obj; + + obj = src->buckets[i]->buckets[j]; + + if (obj == (IMP)0) + continue; + + idx = (uint32_t)((i << 8) | j); + objc_dtable_set(dst, idx, obj); + } +#endif + } +} + +void +objc_dtable_set(struct objc_dtable *dtable, uint32_t idx, IMP obj) +{ +#ifdef OF_SELUID24 + uint8_t i = idx >> 16; + uint8_t j = idx >> 8; + uint8_t k = idx; +#else + uint8_t i = idx >> 8; + uint8_t j = idx; +#endif + + if (dtable->buckets[i] == empty_level2) { + struct objc_dtable_level2 *level2; + uint_fast16_t l; + + level2 = malloc(sizeof(struct objc_dtable_level2)); + + if (level2 == NULL) + OBJC_ERROR("Not enough memory to insert into dtable!"); + + for (l = 0; l < 256; l++) +#ifdef OF_SELUID24 + level2->buckets[l] = empty_level3; +#else + level2->buckets[l] = (IMP)0; +#endif + + dtable->buckets[i] = level2; + } + +#ifdef OF_SELUID24 + if (dtable->buckets[i]->buckets[j] == empty_level3) { + struct objc_dtable_level3 *level3; + uint_fast16_t l; + + level3 = malloc(sizeof(struct objc_dtable_level3)); + + if (level3 == NULL) + OBJC_ERROR("Not enough memory to insert into dtable!"); + + for (l = 0; l < 256; l++) + level3->buckets[l] = (IMP)0; + + dtable->buckets[i]->buckets[j] = level3; + } + + dtable->buckets[i]->buckets[j]->buckets[k] = obj; +#else + dtable->buckets[i]->buckets[j] = obj; +#endif +} + +void +objc_dtable_free(struct objc_dtable *dtable) +{ + uint_fast16_t i; +#ifdef OF_SELUID24 + uint_fast16_t j; +#endif + + for (i = 0; i < 256; i++) { + if (dtable->buckets[i] == empty_level2) + continue; + +#ifdef OF_SELUID24 + for (j = 0; j < 256; j++) + if (dtable->buckets[i]->buckets[j] != empty_level3) + free(dtable->buckets[i]->buckets[j]); +#endif + + free(dtable->buckets[i]); + } + + free(dtable); +} + +void +objc_dtable_cleanup(void) +{ + if (empty_level2 != NULL) + free(empty_level2); +#ifdef OF_SELUID24 + if (empty_level3 != NULL) + free(empty_level3); +#endif + + empty_level2 = NULL; +#ifdef OF_SELUID24 + empty_level3 = NULL; +#endif +} Index: src/runtime/init.m ================================================================== --- src/runtime/init.m +++ src/runtime/init.m @@ -39,10 +39,10 @@ objc_unregister_all_categories(); objc_unregister_all_classes(); objc_unregister_all_selectors(); objc_forget_pending_static_instances(); - objc_sparsearray_cleanup(); + objc_dtable_cleanup(); objc_global_mutex_unlock(); objc_global_mutex_free(); } Index: src/runtime/lookup.m ================================================================== --- src/runtime/lookup.m +++ src/runtime/lookup.m @@ -21,15 +21,15 @@ #import "runtime.h" #import "runtime-private.h" #import "macros.h" -static void *forward_handler = NULL; -static void *forward_handler_stret = NULL; +static IMP forward_handler = (IMP)0; +static IMP forward_handler_stret = (IMP)0; static IMP -common_method_not_found(id obj, SEL sel, IMP (*lookup)(id, SEL), void *forward) +common_method_not_found(id obj, SEL sel, IMP (*lookup)(id, SEL), IMP forward) { /* * obj might be a dummy object (see class_getMethodImplementation), so * don't access obj directly unless it's a class! */ @@ -87,11 +87,11 @@ return lookup(obj, sel); } } - if (forward != NULL) + if (forward != (IMP)0) return forward; OBJC_ERROR("Selector %c[%s] is not implemented for class %s!", (is_class ? '+' : '-'), sel_getName(sel), object_getClassName(obj)); } @@ -109,11 +109,11 @@ return common_method_not_found(obj, sel, objc_msg_lookup_stret, forward_handler_stret); } void -objc_setForwardHandler(void *forward, void *forward_stret) +objc_setForwardHandler(IMP forward, IMP forward_stret) { forward_handler = forward; forward_handler_stret = forward_stret; } @@ -121,11 +121,11 @@ class_respondsToSelector(Class cls, SEL sel) { if (cls == Nil) return false; - return (objc_sparsearray_get(cls->dtable, (uint32_t)sel->uid) != NULL); + return (objc_dtable_get(cls->dtable, (uint32_t)sel->uid) != (IMP)0); } #ifndef OF_ASM_LOOKUP static id nil_method(id self, SEL _cmd) @@ -139,14 +139,13 @@ IMP imp; if (obj == nil) return (IMP)nil_method; - imp = objc_sparsearray_get(object_getClass(obj)->dtable, - (uint32_t)sel->uid); + imp = objc_dtable_get(object_getClass(obj)->dtable, (uint32_t)sel->uid); - if (imp == NULL) + if (imp == (IMP)0) return not_found(obj, sel); return imp; } @@ -169,13 +168,13 @@ IMP imp; if (super->self == nil) return (IMP)nil_method; - imp = objc_sparsearray_get(super->cls->dtable, (uint32_t)sel->uid); + imp = objc_dtable_get(super->cls->dtable, (uint32_t)sel->uid); - if (imp == NULL) + if (imp == (IMP)0) return not_found(super->self, sel); return imp; } Index: src/runtime/runtime-private.h ================================================================== --- src/runtime/runtime-private.h +++ src/runtime/runtime-private.h @@ -101,26 +101,27 @@ uint32_t count, size; struct objc_hashtable_bucket **data; }; struct objc_sparsearray { - struct objc_sparsearray_level2 *buckets[256]; -}; - -#ifdef OF_SELUID24 -struct objc_sparsearray_level2 { - struct objc_sparsearray_level3 *buckets[256]; -}; - -struct objc_sparsearray_level3 { - const void *buckets[256]; -}; -#else -struct objc_sparsearray_level2 { - const void *buckets[256]; -}; -#endif + struct objc_sparsearray_data { + void *next[256]; + } *data; + uint_fast8_t index_size; +}; + +struct objc_dtable { + struct objc_dtable_level2 { +#ifdef OF_SELUID24 + struct objc_dtable_level3 { + IMP buckets[256]; + } *buckets[256]; +#else + IMP buckets[256]; +#endif + } *buckets[256]; +}; extern void objc_register_all_categories(struct objc_abi_symtab*); extern struct objc_category** objc_categories_for_class(Class); extern void objc_unregister_all_categories(void); extern void objc_initialize_class(Class); @@ -140,17 +141,19 @@ extern void objc_hashtable_delete(struct objc_hashtable*, const void*); extern void objc_hashtable_free(struct objc_hashtable *h); extern void objc_register_selector(struct objc_abi_selector*); extern void objc_register_all_selectors(struct objc_abi_symtab*); extern void objc_unregister_all_selectors(void); -extern struct objc_sparsearray* objc_sparsearray_new(void); -extern void objc_sparsearray_copy(struct objc_sparsearray*, - struct objc_sparsearray*); -extern void objc_sparsearray_set(struct objc_sparsearray*, uint32_t, - const void*); +extern struct objc_sparsearray *objc_sparsearray_new(uint_fast8_t); +extern void *objc_sparsearray_get(struct objc_sparsearray*, uintptr_t); +extern void objc_sparsearray_set(struct objc_sparsearray*, uintptr_t, void*); extern void objc_sparsearray_free(struct objc_sparsearray*); -extern void objc_sparsearray_cleanup(void); +extern struct objc_dtable* objc_dtable_new(void); +extern void objc_dtable_copy(struct objc_dtable*, struct objc_dtable*); +extern void objc_dtable_set(struct objc_dtable*, uint32_t, IMP); +extern void objc_dtable_free(struct objc_dtable*); +extern void objc_dtable_cleanup(void); extern void objc_init_static_instances(struct objc_abi_symtab*); extern void objc_forget_pending_static_instances(void); extern void __objc_exec_class(struct objc_abi_module*); #ifdef OF_HAVE_THREADS extern void objc_global_mutex_lock(void); @@ -160,24 +163,24 @@ # define objc_global_mutex_lock() # define objc_global_mutex_unlock() # define objc_global_mutex_free() #endif -static inline void* -objc_sparsearray_get(const struct objc_sparsearray *s, uint32_t idx) +static inline IMP +objc_dtable_get(const struct objc_dtable *dtable, uint32_t idx) { #ifdef OF_SELUID24 uint8_t i = idx >> 16; uint8_t j = idx >> 8; uint8_t k = idx; - return (void*)s->buckets[i]->buckets[j]->buckets[k]; + return dtable->buckets[i]->buckets[j]->buckets[k]; #else uint8_t i = idx >> 8; uint8_t j = idx; - return (void*)s->buckets[i]->buckets[j]; + return dtable->buckets[i]->buckets[j]; #endif } #if defined(__ELF__) # if defined(__x86_64__) || defined(__amd64__) || defined(__i386__) || \ Index: src/runtime/runtime.h ================================================================== --- src/runtime/runtime.h +++ src/runtime/runtime.h @@ -59,11 +59,11 @@ unsigned long version; unsigned long info; long instance_size; struct objc_ivar_list *ivars; struct objc_method_list *methodlist; - struct objc_sparsearray *dtable; + struct objc_dtable *dtable; Class *subclass_list; void *sibling_class; struct objc_protocol_list *protocols; void *gc_object_type; unsigned long abi_version; @@ -215,11 +215,11 @@ extern bool protocol_isEqual(Protocol*, Protocol*); extern bool protocol_conformsToProtocol(Protocol*, Protocol*); extern void objc_exit(void); extern objc_uncaught_exception_handler objc_setUncaughtExceptionHandler( objc_uncaught_exception_handler); -extern void objc_setForwardHandler(void*, void*); +extern void objc_setForwardHandler(IMP, IMP); extern id objc_autorelease(id); extern void* objc_autoreleasePoolPush(void); extern void objc_autoreleasePoolPop(void*); extern id _objc_rootAutorelease(id); /* Used by the compiler, but can be called manually. */ Index: src/runtime/selector.m ================================================================== --- src/runtime/selector.m +++ src/runtime/selector.m @@ -25,12 +25,14 @@ #import "macros.h" #ifdef OF_SELUID24 # define SEL_MAX 0xFFFFFF +# define SEL_SIZE 3 #else # define SEL_MAX 0xFFFF +# define SEL_SIZE 2 #endif static struct objc_hashtable *selectors = NULL; static uint32_t selectors_cnt = 0; static struct objc_sparsearray *selector_names = NULL; @@ -53,18 +55,18 @@ ((struct objc_selector*)sel)->uid = rsel->uid; return; } if (selector_names == NULL) - selector_names = objc_sparsearray_new(); + selector_names = objc_sparsearray_new(SEL_SIZE); name = sel->name; rsel = (struct objc_selector*)sel; rsel->uid = selectors_cnt++; objc_hashtable_set(selectors, name, rsel); - objc_sparsearray_set(selector_names, (uint32_t)rsel->uid, name); + objc_sparsearray_set(selector_names, (uint32_t)rsel->uid, (void*)name); } SEL sel_registerName(const char *name) { Index: src/runtime/sparsearray.m ================================================================== --- src/runtime/sparsearray.m +++ src/runtime/sparsearray.m @@ -20,201 +20,81 @@ #include #import "runtime.h" #import "runtime-private.h" -static struct objc_sparsearray_level2 *empty_level2 = NULL; -#ifdef OF_SELUID24 -static struct objc_sparsearray_level3 *empty_level3 = NULL; -#endif - -static void -init(void) -{ - uint_fast16_t i; - - empty_level2 = malloc(sizeof(struct objc_sparsearray_level2)); - if (empty_level2 == NULL) - OBJC_ERROR("Not enough memory to allocate sparse array!"); - -#ifdef OF_SELUID24 - empty_level3 = malloc(sizeof(struct objc_sparsearray_level3)); - if (empty_level3 == NULL) - OBJC_ERROR("Not enough memory to allocate sparse array!"); -#endif - -#ifdef OF_SELUID24 - for (i = 0; i < 256; i++) { - empty_level2->buckets[i] = empty_level3; - empty_level3->buckets[i] = NULL; - } -#else - for (i = 0; i < 256; i++) - empty_level2->buckets[i] = NULL; -#endif -} - -struct objc_sparsearray* -objc_sparsearray_new(void) -{ - struct objc_sparsearray *s; - uint_fast16_t i; - -#ifdef OF_SELUID24 - if (empty_level2 == NULL || empty_level3 == NULL) - init(); -#else - if (empty_level2 == NULL) - init(); -#endif - - if ((s = malloc(sizeof(struct objc_sparsearray))) == NULL) - OBJC_ERROR("Not enough memory to allocate sparse array!"); - - for (i = 0; i < 256; i++) - s->buckets[i] = empty_level2; - - return s; -} - -void -objc_sparsearray_copy(struct objc_sparsearray *dst, - struct objc_sparsearray *src) -{ - uint_fast16_t i, j; -#ifdef OF_SELUID24 - uint_fast16_t k; -#endif - uint32_t idx; - - for (i = 0; i < 256; i++) { - if (src->buckets[i] == empty_level2) - continue; - -#ifdef OF_SELUID24 - for (j = 0; j < 256; j++) { - if (src->buckets[i]->buckets[j] == empty_level3) - continue; - - for (k = 0; k < 256; k++) { - const void *obj; - - obj = src->buckets[i]->buckets[j]->buckets[k]; - - if (obj == NULL) - continue; - - idx = (uint32_t) - (((uint32_t)i << 16) | (j << 8) | k); - objc_sparsearray_set(dst, idx, obj); - } - } -#else - for (j = 0; j < 256; j++) { - const void *obj; - - obj = src->buckets[i]->buckets[j]; - - if (obj == NULL) - continue; - - idx = (uint32_t)((i << 8) | j); - objc_sparsearray_set(dst, idx, obj); - } -#endif - } -} - -void -objc_sparsearray_set(struct objc_sparsearray *s, uint32_t idx, const void *obj) -{ -#ifdef OF_SELUID24 - uint8_t i = idx >> 16; - uint8_t j = idx >> 8; - uint8_t k = idx; -#else - uint8_t i = idx >> 8; - uint8_t j = idx; -#endif - - if (s->buckets[i] == empty_level2) { - struct objc_sparsearray_level2 *t; - uint_fast16_t l; - - t = malloc(sizeof(struct objc_sparsearray_level2)); - - if (t == NULL) - OBJC_ERROR("Not enough memory to insert into sparse " - "array!"); - - for (l = 0; l < 256; l++) -#ifdef OF_SELUID24 - t->buckets[l] = empty_level3; -#else - t->buckets[l] = NULL; -#endif - - s->buckets[i] = t; - } - -#ifdef OF_SELUID24 - if (s->buckets[i]->buckets[j] == empty_level3) { - struct objc_sparsearray_level3 *t; - uint_fast16_t l; - - t = malloc(sizeof(struct objc_sparsearray_level3)); - - if (t == NULL) - OBJC_ERROR("Not enough memory to insert into sparse " - "array!"); - - for (l = 0; l < 256; l++) - t->buckets[l] = NULL; - - s->buckets[i]->buckets[j] = t; - } - - s->buckets[i]->buckets[j]->buckets[k] = obj; -#else - s->buckets[i]->buckets[j] = obj; -#endif -} - -void -objc_sparsearray_free(struct objc_sparsearray *s) -{ - uint_fast16_t i; -#ifdef OF_SELUID24 - uint_fast16_t j; -#endif - - for (i = 0; i < 256; i++) { - if (s->buckets[i] == empty_level2) - continue; - -#ifdef OF_SELUID24 - for (j = 0; j < 256; j++) - if (s->buckets[i]->buckets[j] != empty_level3) - free(s->buckets[i]->buckets[j]); -#endif - - free(s->buckets[i]); - } - - free(s); -} - -void -objc_sparsearray_cleanup(void) -{ - if (empty_level2 != NULL) - free(empty_level2); -#ifdef OF_SELUID24 - if (empty_level3 != NULL) - free(empty_level3); -#endif - - empty_level2 = NULL; -#ifdef OF_SELUID24 - empty_level3 = NULL; -#endif +struct objc_sparsearray* +objc_sparsearray_new(uint_fast8_t index_size) +{ + struct objc_sparsearray *sparsearray; + + if ((sparsearray = calloc(1, sizeof(*sparsearray))) == NULL) + OBJC_ERROR("Failed to allocate memory for sparse array!"); + + if ((sparsearray->data = calloc(1, sizeof(*sparsearray->data))) == NULL) + OBJC_ERROR("Failed to allocate memory for sparse array!"); + + sparsearray->index_size = index_size; + + return sparsearray; +} + +void* +objc_sparsearray_get(struct objc_sparsearray *sparsearray, uintptr_t idx) +{ + struct objc_sparsearray_data *iter = sparsearray->data; + uint_fast8_t i; + + for (i = 0; i < sparsearray->index_size - 1; i++) { + uintptr_t j = + (idx >> ((sparsearray->index_size - i - 1) * 8)) & 0xFF; + + if ((iter = iter->next[j]) == NULL) + return NULL; + } + + return iter->next[idx & 0xFF]; +} + +void +objc_sparsearray_set(struct objc_sparsearray *sparsearray, uintptr_t idx, + void *value) +{ + struct objc_sparsearray_data *iter = sparsearray->data; + uint_fast8_t i; + + for (i = 0; i < sparsearray->index_size - 1; i++) { + uintptr_t j = + (idx >> ((sparsearray->index_size - i - 1) * 8)) & 0xFF; + + if (iter->next[j] == NULL) + if ((iter->next[j] = calloc(1, + sizeof(struct objc_sparsearray_data))) == NULL) + OBJC_ERROR("Failed to allocate memory for " + "sparse array!"); + + iter = iter->next[j]; + } + + iter->next[idx & 0xFF] = value; +} + +static void +free_sparsearray_data(struct objc_sparsearray_data *data, uint_fast8_t depth) +{ + uint_fast16_t i; + + if (data == NULL || depth == 0) + return; + + for (i = 0; i < 256; i++) + free_sparsearray_data(data->next[i], depth - 1); + + free(data); +} + +void +objc_sparsearray_free(struct objc_sparsearray *sparsearray) +{ + free_sparsearray_data(sparsearray->data, sparsearray->index_size); + free(sparsearray); }