diff options
Diffstat (limited to 'contrib/libobjc/class.c')
-rw-r--r-- | contrib/libobjc/class.c | 703 |
1 files changed, 0 insertions, 703 deletions
diff --git a/contrib/libobjc/class.c b/contrib/libobjc/class.c deleted file mode 100644 index 4374852..0000000 --- a/contrib/libobjc/class.c +++ /dev/null @@ -1,703 +0,0 @@ -/* GNU Objective C Runtime class related functions - Copyright (C) 1993, 1995, 1996, 1997, 2001, 2002 - Free Software Foundation, Inc. - Contributed by Kresten Krab Thorup and Dennis Glatting. - - Lock-free class table code designed and written from scratch by - Nicola Pero, 2001. - -This file is part of GCC. - -GCC is free software; you can redistribute it and/or modify it under the -terms of the GNU General Public License as published by the Free Software -Foundation; either version 2, or (at your option) any later version. - -GCC is distributed in the hope that it will be useful, but WITHOUT ANY -WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS -FOR A PARTICULAR PURPOSE. See the GNU General Public License for more -details. - -You should have received a copy of the GNU General Public License along with -GCC; see the file COPYING. If not, write to the Free Software -Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ - -/* As a special exception, if you link this library with files compiled with - GCC to produce an executable, this does not cause the resulting executable - to be covered by the GNU General Public License. This exception does not - however invalidate any other reasons why the executable file might be - covered by the GNU General Public License. */ - -/* - The code in this file critically affects class method invocation - speed. This long preamble comment explains why, and the issues - involved. - - - One of the traditional weaknesses of the GNU Objective-C runtime is - that class method invocations are slow. The reason is that when you - write - - array = [NSArray new]; - - this gets basically compiled into the equivalent of - - array = [(objc_get_class ("NSArray")) new]; - - objc_get_class returns the class pointer corresponding to the string - `NSArray'; and because of the lookup, the operation is more - complicated and slow than a simple instance method invocation. - - Most high performance Objective-C code (using the GNU Objc runtime) - I had the opportunity to read (or write) work around this problem by - caching the class pointer: - - Class arrayClass = [NSArray class]; - - ... later on ... - - array = [arrayClass new]; - array = [arrayClass new]; - array = [arrayClass new]; - - In this case, you always perform a class lookup (the first one), but - then all the [arrayClass new] methods run exactly as fast as an - instance method invocation. It helps if you have many class method - invocations to the same class. - - The long-term solution to this problem would be to modify the - compiler to output tables of class pointers corresponding to all the - class method invocations, and to add code to the runtime to update - these tables - that should in the end allow class method invocations - to perform precisely as fast as instance method invocations, because - no class lookup would be involved. I think the Apple Objective-C - runtime uses this technique. Doing this involves synchronized - modifications in the runtime and in the compiler. - - As a first medicine to the problem, I [NP] have redesigned and - rewritten the way the runtime is performing class lookup. This - doesn't give as much speed as the other (definitive) approach, but - at least a class method invocation now takes approximately 4.5 times - an instance method invocation on my machine (it would take approx 12 - times before the rewriting), which is a lot better. - - One of the main reason the new class lookup is so faster is because - I implemented it in a way that can safely run multithreaded without - using locks - a so-called `lock-free' data structure. The atomic - operation is pointer assignment. The reason why in this problem - lock-free data structures work so well is that you never remove - classes from the table - and the difficult thing with lock-free data - structures is freeing data when is removed from the structures. */ - -#include "objc/runtime.h" /* the kitchen sink */ -#include "objc/sarray.h" - -#include "objc/objc.h" -#include "objc/objc-api.h" -#include "objc/thr.h" - -/* We use a table which maps a class name to the corresponding class - * pointer. The first part of this file defines this table, and - * functions to do basic operations on the table. The second part of - * the file implements some higher level Objective-C functionality for - * classes by using the functions provided in the first part to manage - * the table. */ - -/** - ** Class Table Internals - **/ - -/* A node holding a class */ -typedef struct class_node -{ - struct class_node *next; /* Pointer to next entry on the list. - NULL indicates end of list. */ - - const char *name; /* The class name string */ - int length; /* The class name string length */ - Class pointer; /* The Class pointer */ - -} *class_node_ptr; - -/* A table containing classes is a class_node_ptr (pointing to the - first entry in the table - if it is NULL, then the table is - empty). */ - -/* We have 1024 tables. Each table contains all class names which - have the same hash (which is a number between 0 and 1023). To look - up a class_name, we compute its hash, and get the corresponding - table. Once we have the table, we simply compare strings directly - till we find the one which we want (using the length first). The - number of tables is quite big on purpose (a normal big application - has less than 1000 classes), so that you shouldn't normally get any - collisions, and get away with a single comparison (which we can't - avoid since we need to know that you have got the right thing). */ -#define CLASS_TABLE_SIZE 1024 -#define CLASS_TABLE_MASK 1023 - -static class_node_ptr class_table_array[CLASS_TABLE_SIZE]; - -/* The table writing mutex - we lock on writing to avoid conflicts - between different writers, but we read without locks. That is - possible because we assume pointer assignment to be an atomic - operation. */ -static objc_mutex_t __class_table_lock = NULL; - -/* CLASS_TABLE_HASH is how we compute the hash of a class name. It is - a macro - *not* a function - arguments *are* modified directly. - - INDEX should be a variable holding an int; - HASH should be a variable holding an int; - CLASS_NAME should be a variable holding a (char *) to the class_name. - - After the macro is executed, INDEX contains the length of the - string, and HASH the computed hash of the string; CLASS_NAME is - untouched. */ - -#define CLASS_TABLE_HASH(INDEX, HASH, CLASS_NAME) \ - HASH = 0; \ - for (INDEX = 0; CLASS_NAME[INDEX] != '\0'; INDEX++) \ - { \ - HASH = (HASH << 4) ^ (HASH >> 28) ^ CLASS_NAME[INDEX]; \ - } \ - \ - HASH = (HASH ^ (HASH >> 10) ^ (HASH >> 20)) & CLASS_TABLE_MASK; - -/* Setup the table. */ -static void -class_table_setup (void) -{ - /* Start - nothing in the table. */ - memset (class_table_array, 0, sizeof (class_node_ptr) * CLASS_TABLE_SIZE); - - /* The table writing mutex. */ - __class_table_lock = objc_mutex_allocate (); -} - - -/* Insert a class in the table (used when a new class is registered). */ -static void -class_table_insert (const char *class_name, Class class_pointer) -{ - int hash, length; - class_node_ptr new_node; - - /* Find out the class name's hash and length. */ - CLASS_TABLE_HASH (length, hash, class_name); - - /* Prepare the new node holding the class. */ - new_node = objc_malloc (sizeof (struct class_node)); - new_node->name = class_name; - new_node->length = length; - new_node->pointer = class_pointer; - - /* Lock the table for modifications. */ - objc_mutex_lock (__class_table_lock); - - /* Insert the new node in the table at the beginning of the table at - class_table_array[hash]. */ - new_node->next = class_table_array[hash]; - class_table_array[hash] = new_node; - - objc_mutex_unlock (__class_table_lock); -} - -/* Replace a class in the table (used only by poseAs:). */ -static void -class_table_replace (Class old_class_pointer, Class new_class_pointer) -{ - int hash; - class_node_ptr node; - - objc_mutex_lock (__class_table_lock); - - hash = 0; - node = class_table_array[hash]; - - while (hash < CLASS_TABLE_SIZE) - { - if (node == NULL) - { - hash++; - if (hash < CLASS_TABLE_SIZE) - { - node = class_table_array[hash]; - } - } - else - { - Class class1 = node->pointer; - - if (class1 == old_class_pointer) - { - node->pointer = new_class_pointer; - } - node = node->next; - } - } - - objc_mutex_unlock (__class_table_lock); -} - - -/* Get a class from the table. This does not need mutex protection. - Currently, this function is called each time you call a static - method, this is why it must be very fast. */ -static inline Class -class_table_get_safe (const char *class_name) -{ - class_node_ptr node; - int length, hash; - - /* Compute length and hash. */ - CLASS_TABLE_HASH (length, hash, class_name); - - node = class_table_array[hash]; - - if (node != NULL) - { - do - { - if (node->length == length) - { - /* Compare the class names. */ - int i; - - for (i = 0; i < length; i++) - { - if ((node->name)[i] != class_name[i]) - { - break; - } - } - - if (i == length) - { - /* They are equal! */ - return node->pointer; - } - } - } - while ((node = node->next) != NULL); - } - - return Nil; -} - -/* Enumerate over the class table. */ -struct class_table_enumerator -{ - int hash; - class_node_ptr node; -}; - - -static Class -class_table_next (struct class_table_enumerator **e) -{ - struct class_table_enumerator *enumerator = *e; - class_node_ptr next; - - if (enumerator == NULL) - { - *e = objc_malloc (sizeof (struct class_table_enumerator)); - enumerator = *e; - enumerator->hash = 0; - enumerator->node = NULL; - - next = class_table_array[enumerator->hash]; - } - else - { - next = enumerator->node->next; - } - - if (next != NULL) - { - enumerator->node = next; - return enumerator->node->pointer; - } - else - { - enumerator->hash++; - - while (enumerator->hash < CLASS_TABLE_SIZE) - { - next = class_table_array[enumerator->hash]; - if (next != NULL) - { - enumerator->node = next; - return enumerator->node->pointer; - } - enumerator->hash++; - } - - /* Ok - table finished - done. */ - objc_free (enumerator); - return Nil; - } -} - -#if 0 /* DEBUGGING FUNCTIONS */ -/* Debugging function - print the class table. */ -void -class_table_print (void) -{ - int i; - - for (i = 0; i < CLASS_TABLE_SIZE; i++) - { - class_node_ptr node; - - printf ("%d:\n", i); - node = class_table_array[i]; - - while (node != NULL) - { - printf ("\t%s\n", node->name); - node = node->next; - } - } -} - -/* Debugging function - print an histogram of number of classes in - function of hash key values. Useful to evaluate the hash function - in real cases. */ -void -class_table_print_histogram (void) -{ - int i, j; - int counter = 0; - - for (i = 0; i < CLASS_TABLE_SIZE; i++) - { - class_node_ptr node; - - node = class_table_array[i]; - - while (node != NULL) - { - counter++; - node = node->next; - } - if (((i + 1) % 50) == 0) - { - printf ("%4d:", i + 1); - for (j = 0; j < counter; j++) - { - printf ("X"); - } - printf ("\n"); - counter = 0; - } - } - printf ("%4d:", i + 1); - for (j = 0; j < counter; j++) - { - printf ("X"); - } - printf ("\n"); -} -#endif /* DEBUGGING FUNCTIONS */ - -/** - ** Objective-C runtime functions - **/ - -/* From now on, the only access to the class table data structure - should be via the class_table_* functions. */ - -/* This is a hook which is called by objc_get_class and - objc_lookup_class if the runtime is not able to find the class. - This may e.g. try to load in the class using dynamic loading. */ -Class (*_objc_lookup_class) (const char *name) = 0; /* !T:SAFE */ - - -/* True when class links has been resolved. */ -BOOL __objc_class_links_resolved = NO; /* !T:UNUSED */ - - -void -__objc_init_class_tables (void) -{ - /* Allocate the class hash table. */ - - if (__class_table_lock) - return; - - objc_mutex_lock (__objc_runtime_mutex); - - class_table_setup (); - - objc_mutex_unlock (__objc_runtime_mutex); -} - -/* This function adds a class to the class hash table, and assigns the - class a number, unless it's already known. */ -void -__objc_add_class_to_hash (Class class) -{ - Class h_class; - - objc_mutex_lock (__objc_runtime_mutex); - - /* Make sure the table is there. */ - assert (__class_table_lock); - - /* Make sure it's not a meta class. */ - assert (CLS_ISCLASS (class)); - - /* Check to see if the class is already in the hash table. */ - h_class = class_table_get_safe (class->name); - if (! h_class) - { - /* The class isn't in the hash table. Add the class and assign a class - number. */ - static unsigned int class_number = 1; - - CLS_SETNUMBER (class, class_number); - CLS_SETNUMBER (class->class_pointer, class_number); - - ++class_number; - class_table_insert (class->name, class); - } - - objc_mutex_unlock (__objc_runtime_mutex); -} - -/* Get the class object for the class named NAME. If NAME does not - identify a known class, the hook _objc_lookup_class is called. If - this fails, nil is returned. */ -Class -objc_lookup_class (const char *name) -{ - Class class; - - class = class_table_get_safe (name); - - if (class) - return class; - - if (_objc_lookup_class) - return (*_objc_lookup_class) (name); - else - return 0; -} - -/* Get the class object for the class named NAME. If NAME does not - identify a known class, the hook _objc_lookup_class is called. If - this fails, an error message is issued and the system aborts. */ -Class -objc_get_class (const char *name) -{ - Class class; - - class = class_table_get_safe (name); - - if (class) - return class; - - if (_objc_lookup_class) - class = (*_objc_lookup_class) (name); - - if (class) - return class; - - objc_error (nil, OBJC_ERR_BAD_CLASS, - "objc runtime: cannot find class %s\n", name); - return 0; -} - -MetaClass -objc_get_meta_class (const char *name) -{ - return objc_get_class (name)->class_pointer; -} - -/* This function provides a way to enumerate all the classes in the - executable. Pass *ENUM_STATE == NULL to start the enumeration. The - function will return 0 when there are no more classes. - For example: - id class; - void *es = NULL; - while ((class = objc_next_class (&es))) - ... do something with class; -*/ -Class -objc_next_class (void **enum_state) -{ - Class class; - - objc_mutex_lock (__objc_runtime_mutex); - - /* Make sure the table is there. */ - assert (__class_table_lock); - - class = class_table_next ((struct class_table_enumerator **) enum_state); - - objc_mutex_unlock (__objc_runtime_mutex); - - return class; -} - -/* Resolve super/subclass links for all classes. The only thing we - can be sure of is that the class_pointer for class objects point to - the right meta class objects. */ -void -__objc_resolve_class_links (void) -{ - struct class_table_enumerator *es = NULL; - Class object_class = objc_get_class ("Object"); - Class class1; - - assert (object_class); - - objc_mutex_lock (__objc_runtime_mutex); - - /* Assign subclass links. */ - while ((class1 = class_table_next (&es))) - { - /* Make sure we have what we think we have. */ - assert (CLS_ISCLASS (class1)); - assert (CLS_ISMETA (class1->class_pointer)); - - /* The class_pointer of all meta classes point to Object's meta - class. */ - class1->class_pointer->class_pointer = object_class->class_pointer; - - if (! CLS_ISRESOLV (class1)) - { - CLS_SETRESOLV (class1); - CLS_SETRESOLV (class1->class_pointer); - - if (class1->super_class) - { - Class a_super_class - = objc_get_class ((char *) class1->super_class); - - assert (a_super_class); - - DEBUG_PRINTF ("making class connections for: %s\n", - class1->name); - - /* Assign subclass links for superclass. */ - class1->sibling_class = a_super_class->subclass_list; - a_super_class->subclass_list = class1; - - /* Assign subclass links for meta class of superclass. */ - if (a_super_class->class_pointer) - { - class1->class_pointer->sibling_class - = a_super_class->class_pointer->subclass_list; - a_super_class->class_pointer->subclass_list - = class1->class_pointer; - } - } - else /* A root class, make its meta object be a subclass of - Object. */ - { - class1->class_pointer->sibling_class - = object_class->subclass_list; - object_class->subclass_list = class1->class_pointer; - } - } - } - - /* Assign superclass links. */ - es = NULL; - while ((class1 = class_table_next (&es))) - { - Class sub_class; - for (sub_class = class1->subclass_list; sub_class; - sub_class = sub_class->sibling_class) - { - sub_class->super_class = class1; - if (CLS_ISCLASS (sub_class)) - sub_class->class_pointer->super_class = class1->class_pointer; - } - } - - objc_mutex_unlock (__objc_runtime_mutex); -} - - - -#define CLASSOF(c) ((c)->class_pointer) - -Class -class_pose_as (Class impostor, Class super_class) -{ - if (! CLS_ISRESOLV (impostor)) - __objc_resolve_class_links (); - - /* Preconditions */ - assert (impostor); - assert (super_class); - assert (impostor->super_class == super_class); - assert (CLS_ISCLASS (impostor)); - assert (CLS_ISCLASS (super_class)); - assert (impostor->instance_size == super_class->instance_size); - - { - Class *subclass = &(super_class->subclass_list); - - /* Move subclasses of super_class to impostor. */ - while (*subclass) - { - Class nextSub = (*subclass)->sibling_class; - - if (*subclass != impostor) - { - Class sub = *subclass; - - /* Classes */ - sub->sibling_class = impostor->subclass_list; - sub->super_class = impostor; - impostor->subclass_list = sub; - - /* It will happen that SUB is not a class object if it is - the top of the meta class hierarchy chain (root - meta-class objects inherit their class object). If - that is the case... don't mess with the meta-meta - class. */ - if (CLS_ISCLASS (sub)) - { - /* Meta classes */ - CLASSOF (sub)->sibling_class = - CLASSOF (impostor)->subclass_list; - CLASSOF (sub)->super_class = CLASSOF (impostor); - CLASSOF (impostor)->subclass_list = CLASSOF (sub); - } - } - - *subclass = nextSub; - } - - /* Set subclasses of superclass to be impostor only. */ - super_class->subclass_list = impostor; - CLASSOF (super_class)->subclass_list = CLASSOF (impostor); - - /* Set impostor to have no sibling classes. */ - impostor->sibling_class = 0; - CLASSOF (impostor)->sibling_class = 0; - } - - /* Check relationship of impostor and super_class is kept. */ - assert (impostor->super_class == super_class); - assert (CLASSOF (impostor)->super_class == CLASSOF (super_class)); - - /* This is how to update the lookup table. Regardless of what the - keys of the hashtable is, change all values that are superclass - into impostor. */ - - objc_mutex_lock (__objc_runtime_mutex); - - class_table_replace (super_class, impostor); - - objc_mutex_unlock (__objc_runtime_mutex); - - /* Next, we update the dispatch tables... */ - __objc_update_dispatch_table_for_class (CLASSOF (impostor)); - __objc_update_dispatch_table_for_class (impostor); - - return impostor; -} |