libobjc/class.c

   1 /* GNU Objective C Runtime class related functions
   2    Copyright (C) 1993, 1995, 1996, 1997, 2001, 2002, 2009
   3      Free Software Foundation, Inc.
   4    Contributed by Kresten Krab Thorup and Dennis Glatting.
   5
   6    Lock-free class table code designed and written from scratch by
   7    Nicola Pero, 2001.
   8
   9 This file is part of GCC.
  10
  11 GCC is free software; you can redistribute it and/or modify it under the
  12 terms of the GNU General Public License as published by the Free Software
  13 Foundation; either version 3, or (at your option) any later version.
  14
  15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  16 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  17 FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
  18 details.
  19
  20 Under Section 7 of GPL version 3, you are granted additional
  21 permissions described in the GCC Runtime Library Exception, version
  22 3.1, as published by the Free Software Foundation.
  23
  24 You should have received a copy of the GNU General Public License and
  25 a copy of the GCC Runtime Library Exception along with this program;
  26 see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  27 <http://www.gnu.org/licenses/>.  */
  28
  29 /*
  30   The code in this file critically affects class method invocation
  31   speed.  This long preamble comment explains why, and the issues
  32   involved.
  33
  34
  35   One of the traditional weaknesses of the GNU Objective-C runtime is
  36   that class method invocations are slow.  The reason is that when you
  37   write
  38
  39   array = [NSArray new];
  40
  41   this gets basically compiled into the equivalent of
  42
  43   array = [(objc_get_class ("NSArray")) new];
  44
  45   objc_get_class returns the class pointer corresponding to the string
  46   `NSArray'; and because of the lookup, the operation is more
  47   complicated and slow than a simple instance method invocation.
  48
  49   Most high performance Objective-C code (using the GNU Objc runtime)
  50   I had the opportunity to read (or write) work around this problem by
  51   caching the class pointer:
  52
  53   Class arrayClass = [NSArray class];
  54
  55   ... later on ...
  56
  57   array = [arrayClass new];
  58   array = [arrayClass new];
  59   array = [arrayClass new];
  60
  61   In this case, you always perform a class lookup (the first one), but
  62   then all the [arrayClass new] methods run exactly as fast as an
  63   instance method invocation.  It helps if you have many class method
  64   invocations to the same class.
  65
  66   The long-term solution to this problem would be to modify the
  67   compiler to output tables of class pointers corresponding to all the
  68   class method invocations, and to add code to the runtime to update
  69   these tables - that should in the end allow class method invocations
  70   to perform precisely as fast as instance method invocations, because
  71   no class lookup would be involved.  I think the Apple Objective-C
  72   runtime uses this technique.  Doing this involves synchronized
  73   modifications in the runtime and in the compiler.
  74
  75   As a first medicine to the problem, I [NP] have redesigned and
  76   rewritten the way the runtime is performing class lookup.  This
  77   doesn't give as much speed as the other (definitive) approach, but
  78   at least a class method invocation now takes approximately 4.5 times
  79   an instance method invocation on my machine (it would take approx 12
  80   times before the rewriting), which is a lot better.
  81
  82   One of the main reason the new class lookup is so faster is because
  83   I implemented it in a way that can safely run multithreaded without
  84   using locks - a so-called `lock-free' data structure.  The atomic
  85   operation is pointer assignment.  The reason why in this problem
  86   lock-free data structures work so well is that you never remove
  87   classes from the table - and the difficult thing with lock-free data
  88   structures is freeing data when is removed from the structures.  */
  89
  90 #include "objc-private/common.h"
  91 #include "objc-private/error.h"
  92 #include "objc/runtime.h"
  93 #include "objc/thr.h"
  94 #include "objc-private/module-abi-8.h"  /* For CLS_ISCLASS and similar.  */
  95 #include "objc-private/runtime.h"       /* the kitchen sink */
  96 #include "objc-private/sarray.h"        /* For sarray_put_at_safe.  */
  97 #include <string.h>                     /* For memset */
  98
  99 /* We use a table which maps a class name to the corresponding class
 100  * pointer.  The first part of this file defines this table, and
 101  * functions to do basic operations on the table.  The second part of
 102  * the file implements some higher level Objective-C functionality for
 103  * classes by using the functions provided in the first part to manage
 104  * the table. */
 105
 106 /**
 107  ** Class Table Internals
 108  **/
 109
 110 /* A node holding a class */
 111 typedef struct class_node
 112 {
 113   struct class_node *next;      /* Pointer to next entry on the list.
 114                                    NULL indicates end of list. */
 115
 116   const char *name;             /* The class name string */
 117   int length;                   /* The class name string length */
 118   Class pointer;                /* The Class pointer */
 119
 120 } *class_node_ptr;
 121
 122 /* A table containing classes is a class_node_ptr (pointing to the
 123    first entry in the table - if it is NULL, then the table is
 124    empty). */
 125
 126 /* We have 1024 tables.  Each table contains all class names which
 127    have the same hash (which is a number between 0 and 1023).  To look
 128    up a class_name, we compute its hash, and get the corresponding
 129    table.  Once we have the table, we simply compare strings directly
 130    till we find the one which we want (using the length first).  The
 131    number of tables is quite big on purpose (a normal big application
 132    has less than 1000 classes), so that you shouldn't normally get any
 133    collisions, and get away with a single comparison (which we can't
 134    avoid since we need to know that you have got the right thing).  */
 135 #define CLASS_TABLE_SIZE 1024
 136 #define CLASS_TABLE_MASK 1023
 137
 138 static class_node_ptr class_table_array[CLASS_TABLE_SIZE];
 139
 140 /* The table writing mutex - we lock on writing to avoid conflicts
 141    between different writers, but we read without locks.  That is
 142    possible because we assume pointer assignment to be an atomic
 143    operation.  TODO: This is only true under certain circumstances,
 144    which should be clarified.  */
 145 static objc_mutex_t __class_table_lock = NULL;
 146
 147 /* CLASS_TABLE_HASH is how we compute the hash of a class name.  It is
 148    a macro - *not* a function - arguments *are* modified directly.
 149
 150    INDEX should be a variable holding an int;
 151    HASH should be a variable holding an int;
 152    CLASS_NAME should be a variable holding a (char *) to the class_name.
 153
 154    After the macro is executed, INDEX contains the length of the
 155    string, and HASH the computed hash of the string; CLASS_NAME is
 156    untouched.  */
 157
 158 #define CLASS_TABLE_HASH(INDEX, HASH, CLASS_NAME)          \
 159   HASH = 0;                                                  \
 160   for (INDEX = 0; CLASS_NAME[INDEX] != '\0'; INDEX++)        \
 161     {                                                        \
 162       HASH = (HASH << 4) ^ (HASH >> 28) ^ CLASS_NAME[INDEX]; \
 163     }                                                        \
 164                                                              \
 165   HASH = (HASH ^ (HASH >> 10) ^ (HASH >> 20)) & CLASS_TABLE_MASK;
 166
 167 /* Setup the table.  */
 168 static void
 169 class_table_setup (void)
 170 {
 171   /* Start - nothing in the table.  */
 172   memset (class_table_array, 0, sizeof (class_node_ptr) * CLASS_TABLE_SIZE);
 173
 174   /* The table writing mutex.  */
 175   __class_table_lock = objc_mutex_allocate ();
 176 }
 177
 178
 179 /* Insert a class in the table (used when a new class is registered).  */
 180 static void
 181 class_table_insert (const char *class_name, Class class_pointer)
 182 {
 183   int hash, length;
 184   class_node_ptr new_node;
 185
 186   /* Find out the class name's hash and length.  */
 187   CLASS_TABLE_HASH (length, hash, class_name);
 188
 189   /* Prepare the new node holding the class.  */
 190   new_node = objc_malloc (sizeof (struct class_node));
 191   new_node->name = class_name;
 192   new_node->length = length;
 193   new_node->pointer = class_pointer;
 194
 195   /* Lock the table for modifications.  */
 196   objc_mutex_lock (__class_table_lock);
 197
 198   /* Insert the new node in the table at the beginning of the table at
 199      class_table_array[hash].  */
 200   new_node->next = class_table_array[hash];
 201   class_table_array[hash] = new_node;
 202
 203   objc_mutex_unlock (__class_table_lock);
 204 }
 205
 206 /* Replace a class in the table (used only by poseAs:).  */
 207 static void
 208 class_table_replace (Class old_class_pointer, Class new_class_pointer)
 209 {
 210   int hash;
 211   class_node_ptr node;
 212
 213   objc_mutex_lock (__class_table_lock);
 214
 215   hash = 0;
 216   node = class_table_array[hash];
 217
 218   while (hash < CLASS_TABLE_SIZE)
 219     {
 220       if (node == NULL)
 221         {
 222           hash++;
 223           if (hash < CLASS_TABLE_SIZE)
 224             {
 225               node = class_table_array[hash];
 226             }
 227         }
 228       else
 229         {
 230           Class class1 = node->pointer;
 231
 232           if (class1 == old_class_pointer)
 233             {
 234               node->pointer = new_class_pointer;
 235             }
 236           node = node->next;
 237         }
 238     }
 239
 240   objc_mutex_unlock (__class_table_lock);
 241 }
 242
 243
 244 /* Get a class from the table.  This does not need mutex protection.
 245    Currently, this function is called each time you call a static
 246    method, this is why it must be very fast.  */
 247 static inline Class
 248 class_table_get_safe (const char *class_name)
 249 {
 250   class_node_ptr node;
 251   int length, hash;
 252
 253   /* Compute length and hash.  */
 254   CLASS_TABLE_HASH (length, hash, class_name);
 255
 256   node = class_table_array[hash];
 257
 258   if (node != NULL)
 259     {
 260       do
 261         {
 262           if (node->length == length)
 263             {
 264               /* Compare the class names.  */
 265               int i;
 266
 267               for (i = 0; i < length; i++)
 268                 {
 269                   if ((node->name)[i] != class_name[i])
 270                     {
 271                       break;
 272                     }
 273                 }
 274
 275               if (i == length)
 276                 {
 277                   /* They are equal!  */
 278                   return node->pointer;
 279                 }
 280             }
 281         }
 282       while ((node = node->next) != NULL);
 283     }
 284
 285   return Nil;
 286 }
 287
 288 /* Enumerate over the class table.  */
 289 struct class_table_enumerator
 290 {
 291   int hash;
 292   class_node_ptr node;
 293 };
 294
 295
 296 static Class
 297 class_table_next (struct class_table_enumerator **e)
 298 {
 299   struct class_table_enumerator *enumerator = *e;
 300   class_node_ptr next;
 301
 302   if (enumerator == NULL)
 303     {
 304        *e = objc_malloc (sizeof (struct class_table_enumerator));
 305       enumerator = *e;
 306       enumerator->hash = 0;
 307       enumerator->node = NULL;
 308
 309       next = class_table_array[enumerator->hash];
 310     }
 311   else
 312     {
 313       next = enumerator->node->next;
 314     }
 315
 316   if (next != NULL)
 317     {
 318       enumerator->node = next;
 319       return enumerator->node->pointer;
 320     }
 321   else
 322     {
 323       enumerator->hash++;
 324
 325       while (enumerator->hash < CLASS_TABLE_SIZE)
 326         {
 327           next = class_table_array[enumerator->hash];
 328           if (next != NULL)
 329             {
 330               enumerator->node = next;
 331               return enumerator->node->pointer;
 332             }
 333           enumerator->hash++;
 334         }
 335
 336       /* Ok - table finished - done.  */
 337       objc_free (enumerator);
 338       return Nil;
 339     }
 340 }
 341
 342 #if 0 /* DEBUGGING FUNCTIONS */
 343 /* Debugging function - print the class table.  */
 344 void
 345 class_table_print (void)
 346 {
 347   int i;
 348
 349   for (i = 0; i < CLASS_TABLE_SIZE; i++)
 350     {
 351       class_node_ptr node;
 352
 353       printf ("%d:\n", i);
 354       node = class_table_array[i];
 355
 356       while (node != NULL)
 357         {
 358           printf ("\t%s\n", node->name);
 359           node = node->next;
 360         }
 361     }
 362 }
 363
 364 /* Debugging function - print an histogram of number of classes in
 365    function of hash key values.  Useful to evaluate the hash function
 366    in real cases.  */
 367 void
 368 class_table_print_histogram (void)
 369 {
 370   int i, j;
 371   int counter = 0;
 372
 373   for (i = 0; i < CLASS_TABLE_SIZE; i++)
 374     {
 375       class_node_ptr node;
 376
 377       node = class_table_array[i];
 378
 379       while (node != NULL)
 380         {
 381           counter++;
 382           node = node->next;
 383         }
 384       if (((i + 1) % 50) == 0)
 385         {
 386           printf ("%4d:", i + 1);
 387           for (j = 0; j < counter; j++)
 388             {
 389               printf ("X");
 390             }
 391           printf ("\n");
 392           counter = 0;
 393         }
 394     }
 395   printf ("%4d:", i + 1);
 396   for (j = 0; j < counter; j++)
 397     {
 398       printf ("X");
 399     }
 400   printf ("\n");
 401 }
 402 #endif /* DEBUGGING FUNCTIONS */
 403
 404 /**
 405  ** Objective-C runtime functions
 406  **/
 407
 408 /* From now on, the only access to the class table data structure
 409    should be via the class_table_* functions.  */
 410
 411 /* This is a hook which is called by objc_get_class and
 412    objc_lookup_class if the runtime is not able to find the class.
 413    This may e.g. try to load in the class using dynamic loading.
 414
 415    This hook was a public, global variable in the Traditional GNU
 416    Objective-C Runtime API (objc/objc-api.h).  The modern GNU
 417    Objective-C Runtime API (objc/runtime.h) provides the
 418    objc_setGetUnknownClassHandler() function instead.
 419 */
 420 Class (*_objc_lookup_class) (const char *name) = 0;      /* !T:SAFE */
 421
 422 /* The handler currently in use.  PS: if both
 423    __obj_get_unknown_class_handler and _objc_lookup_class are defined,
 424    __objc_get_unknown_class_handler is called first.  */
 425 static objc_get_unknown_class_handler
 426 __objc_get_unknown_class_handler = NULL;
 427
 428 objc_get_unknown_class_handler
 429 objc_setGetUnknownClassHandler (objc_get_unknown_class_handler
 430                                 new_handler)
 431 {
 432   objc_get_unknown_class_handler old_handler
 433     = __objc_get_unknown_class_handler;
 434   __objc_get_unknown_class_handler = new_handler;
 435   return old_handler;
 436 }
 437
 438
 439 /* True when class links has been resolved.  */
 440 BOOL __objc_class_links_resolved = NO;                  /* !T:UNUSED */
 441
 442
 443 void
 444 __objc_init_class_tables (void)
 445 {
 446   /* Allocate the class hash table.  */
 447
 448   if (__class_table_lock)
 449     return;
 450
 451   objc_mutex_lock (__objc_runtime_mutex);
 452
 453   class_table_setup ();
 454
 455   objc_mutex_unlock (__objc_runtime_mutex);
 456 }
 457
 458 /* This function adds a class to the class hash table, and assigns the
 459    class a number, unless it's already known.  */
 460 void
 461 __objc_add_class_to_hash (Class class)
 462 {
 463   Class h_class;
 464
 465   objc_mutex_lock (__objc_runtime_mutex);
 466
 467   /* Make sure the table is there.  */
 468   assert (__class_table_lock);
 469
 470   /* Make sure it's not a meta class.  */
 471   assert (CLS_ISCLASS (class));
 472
 473   /* Check to see if the class is already in the hash table.  */
 474   h_class = class_table_get_safe (class->name);
 475   if (! h_class)
 476     {
 477       /* The class isn't in the hash table.  Add the class and assign a class
 478          number.  */
 479       static unsigned int class_number = 1;
 480
 481       CLS_SETNUMBER (class, class_number);
 482       CLS_SETNUMBER (class->class_pointer, class_number);
 483
 484       ++class_number;
 485       class_table_insert (class->name, class);
 486     }
 487
 488   objc_mutex_unlock (__objc_runtime_mutex);
 489 }
 490
 491 Class
 492 objc_getClass (const char *name)
 493 {
 494   Class class;
 495
 496   if (name == NULL)
 497     return Nil;
 498
 499   class = class_table_get_safe (name);
 500
 501   if (class)
 502     return class;
 503
 504   if (__objc_get_unknown_class_handler)
 505     return (*__objc_get_unknown_class_handler) (name);
 506
 507   if (_objc_lookup_class)
 508     return (*_objc_lookup_class) (name);
 509
 510   return Nil;
 511 }
 512
 513 Class
 514 objc_lookupClass (const char *name)
 515 {
 516   if (name == NULL)
 517     return Nil;
 518   else
 519     return class_table_get_safe (name);
 520 }
 521
 522 Class
 523 objc_getMetaClass (const char *name)
 524 {
 525   Class class = objc_getClass (name);
 526
 527   if (class)
 528     return class->class_pointer;
 529   else
 530     return Nil;
 531 }
 532
 533 Class
 534 objc_getRequiredClass (const char *name)
 535 {
 536   Class class = objc_getClass (name);
 537
 538   if (class)
 539     return class;
 540   else
 541     _objc_abort ("objc_getRequiredClass ('%s') failed: class not found\n", name);
 542 }
 543
 544 int
 545 objc_getClassList (Class *returnValue, int maxNumberOfClassesToReturn)
 546 {
 547   /* Iterate over all entries in the table.  */
 548   int hash, count = 0;
 549
 550   for (hash = 0; hash < CLASS_TABLE_SIZE; hash++)
 551     {
 552       class_node_ptr node = class_table_array[hash];
 553
 554       while (node != NULL)
 555         {
 556           if (returnValue)
 557             {
 558               if (count < maxNumberOfClassesToReturn)
 559                 returnValue[count] = node->pointer;
 560               else
 561                 {
 562                   return count;
 563                 }
 564             }
 565           count++;
 566           node = node->next;
 567         }
 568     }
 569
 570   return count;
 571 }
 572
 573 Class
 574 objc_allocateClassPair (Class super_class, const char *class_name, size_t extraBytes)
 575 {
 576   Class new_class;
 577   Class new_meta_class;
 578
 579   if (class_name == NULL)
 580     return Nil;
 581
 582   if (objc_getClass (class_name))
 583     return Nil;
 584
 585   if (super_class)
 586     {
 587       /* If you want to build a hierarchy of classes, you need to
 588          build and register them one at a time.  The risk is that you
 589          are able to cause confusion by registering a subclass before
 590          the superclass or similar.  */
 591       if (CLS_IS_IN_CONSTRUCTION (super_class))
 592         return Nil;
 593     }
 594
 595   /* Technically, we should create the metaclass first, then use
 596      class_createInstance() to create the class.  That complication
 597      would be relevant if we had class variables, but we don't, so we
 598      just ignore it and create everything directly and assume all
 599      classes have the same size.  */
 600   new_class = objc_calloc (1, sizeof (struct objc_class) + extraBytes);
 601   new_meta_class = objc_calloc (1, sizeof (struct objc_class) + extraBytes);
 602
 603   /* We create an unresolved class, similar to one generated by the
 604      compiler.  It will be resolved later when we register it.
 605
 606      Note how the metaclass details are not that important; when the
 607      class is resolved, the ones that matter will be fixed up.  */
 608   new_class->class_pointer = new_meta_class;
 609   new_meta_class->class_pointer = 0;
 610
 611   if (super_class)
 612     {
 613       /* Force the name of the superclass in place of the link to the
 614          actual superclass, which will be put there when the class is
 615          resolved.  */
 616       const char *super_class_name = class_getName (super_class);
 617       new_class->super_class = (void *)super_class_name;
 618       new_meta_class->super_class = (void *)super_class_name;
 619     }
 620   else
 621     {
 622       new_class->super_class = (void *)0;
 623       new_meta_class->super_class = (void *)0;
 624     }
 625
 626   new_class->name = objc_malloc (strlen (class_name) + 1);
 627   strcpy ((char*)new_class->name, class_name);
 628   new_meta_class->name = new_class->name;
 629
 630   new_class->version = 0;
 631   new_meta_class->version = 0;
 632
 633   new_class->info = _CLS_CLASS | _CLS_IN_CONSTRUCTION;
 634   new_meta_class->info = _CLS_META | _CLS_IN_CONSTRUCTION;
 635
 636   if (super_class)
 637     new_class->instance_size = super_class->instance_size;
 638   else
 639     new_class->instance_size = 0;
 640   new_meta_class->instance_size = sizeof (struct objc_class);
 641
 642   return new_class;
 643 }
 644
 645 void
 646 objc_registerClassPair (Class class_)
 647 {
 648   if (class_ == Nil)
 649     return;
 650
 651   if ((! CLS_ISCLASS (class_)) || (! CLS_IS_IN_CONSTRUCTION (class_)))
 652     return;
 653
 654   if ((! CLS_ISMETA (class_->class_pointer)) || (! CLS_IS_IN_CONSTRUCTION (class_->class_pointer)))
 655     return;
 656
 657   objc_mutex_lock (__objc_runtime_mutex);
 658
 659   if (objc_getClass (class_->name))
 660     {
 661       objc_mutex_unlock (__objc_runtime_mutex);
 662       return;
 663     }
 664
 665   CLS_SET_NOT_IN_CONSTRUCTION (class_);
 666   CLS_SET_NOT_IN_CONSTRUCTION (class_->class_pointer);
 667
 668   __objc_init_class (class_);
 669
 670   /* Resolve class links immediately.  No point in waiting.  */
 671   __objc_resolve_class_links ();
 672
 673   objc_mutex_unlock (__objc_runtime_mutex);
 674 }
 675
 676 void
 677 objc_disposeClassPair (Class class_)
 678 {
 679   if (class_ == Nil)
 680     return;
 681
 682   if ((! CLS_ISCLASS (class_)) || (! CLS_IS_IN_CONSTRUCTION (class_)))
 683     return;
 684
 685   if ((! CLS_ISMETA (class_->class_pointer)) || (! CLS_IS_IN_CONSTRUCTION (class_->class_pointer)))
 686     return;
 687
 688   /* Undo any class_addIvar().  */
 689   if (class_->ivars)
 690     {
 691       int i;
 692       for (i = 0; i < class_->ivars->ivar_count; i++)
 693         {
 694           struct objc_ivar *ivar = &(class_->ivars->ivar_list[i]);
 695
 696           objc_free ((char *)ivar->ivar_name);
 697           objc_free ((char *)ivar->ivar_type);
 698         }
 699
 700       objc_free (class_->ivars);
 701     }
 702
 703   /* Undo any class_addMethod().  */
 704   if (class_->methods)
 705     {
 706       struct objc_method_list *list = class_->methods;
 707       while (list)
 708         {
 709           int i;
 710           struct objc_method_list *next = list->method_next;
 711
 712           for (i = 0; i < list->method_count; i++)
 713             {
 714               struct objc_method *method = &(list->method_list[i]);
 715
 716               objc_free ((char *)method->method_name);
 717               objc_free ((char *)method->method_types);
 718             }
 719
 720           objc_free (list);
 721           list = next;
 722         }
 723     }
 724
 725   /* Undo any class_addProtocol().  */
 726   if (class_->protocols)
 727     {
 728       struct objc_protocol_list *list = class_->protocols;
 729       while (list)
 730         {
 731           struct objc_protocol_list *next = list->next;
 732
 733           objc_free (list);
 734           list = next;
 735         }
 736     }
 737
 738   /* Undo any class_addMethod() on the meta-class.  */
 739   if (class_->class_pointer->methods)
 740     {
 741       struct objc_method_list *list = class_->class_pointer->methods;
 742       while (list)
 743         {
 744           int i;
 745           struct objc_method_list *next = list->method_next;
 746
 747           for (i = 0; i < list->method_count; i++)
 748             {
 749               struct objc_method *method = &(list->method_list[i]);
 750
 751               objc_free ((char *)method->method_name);
 752               objc_free ((char *)method->method_types);
 753             }
 754
 755           objc_free (list);
 756           list = next;
 757         }
 758     }
 759
 760   /* Undo objc_allocateClassPair().  */
 761   objc_free ((char *)(class_->name));
 762   objc_free (class_->class_pointer);
 763   objc_free (class_);
 764 }
 765
 766 /* Traditional GNU Objective-C Runtime API.  */
 767 /* Get the class object for the class named NAME.  If NAME does not
 768    identify a known class, the hook _objc_lookup_class is called.  If
 769    this fails, nil is returned.  */
 770 Class
 771 objc_lookup_class (const char *name)
 772 {
 773   return objc_getClass (name);
 774 }
 775
 776 /* Traditional GNU Objective-C Runtime API.  Important: this method is
 777    called automatically by the compiler while messaging (if using the
 778    traditional ABI), so it is worth keeping it fast; don't make it
 779    just a wrapper around objc_getClass().  */
 780 /* Note that this is roughly equivalent to objc_getRequiredClass().  */
 781 /* Get the class object for the class named NAME.  If NAME does not
 782    identify a known class, the hook _objc_lookup_class is called.  If
 783    this fails, an error message is issued and the system aborts.  */
 784 Class
 785 objc_get_class (const char *name)
 786 {
 787   Class class;
 788
 789   class = class_table_get_safe (name);
 790
 791   if (class)
 792     return class;
 793
 794   if (__objc_get_unknown_class_handler)
 795     class = (*__objc_get_unknown_class_handler) (name);
 796
 797   if ((!class)  &&  _objc_lookup_class)
 798     class = (*_objc_lookup_class) (name);
 799
 800   if (class)
 801     return class;
 802
 803   _objc_abort ("objc runtime: cannot find class %s\n", name);
 804
 805   return 0;
 806 }
 807
 808 MetaClass
 809 objc_get_meta_class (const char *name)
 810 {
 811   return objc_get_class (name)->class_pointer;
 812 }
 813
 814 /* This function provides a way to enumerate all the classes in the
 815    executable.  Pass *ENUM_STATE == NULL to start the enumeration.  The
 816    function will return 0 when there are no more classes.
 817    For example:
 818        id class;
 819        void *es = NULL;
 820        while ((class = objc_next_class (&es)))
 821          ... do something with class;
 822 */
 823 Class
 824 objc_next_class (void **enum_state)
 825 {
 826   Class class;
 827
 828   objc_mutex_lock (__objc_runtime_mutex);
 829
 830   /* Make sure the table is there.  */
 831   assert (__class_table_lock);
 832
 833   class = class_table_next ((struct class_table_enumerator **) enum_state);
 834
 835   objc_mutex_unlock (__objc_runtime_mutex);
 836
 837   return class;
 838 }
 839
 840 /* This is used when the implementation of a method changes.  It goes
 841    through all classes, looking for the ones that have these methods
 842    (either method_a or method_b; method_b can be NULL), and reloads
 843    the implementation for these.  You should call this with the
 844    runtime mutex already locked.  */
 845 void
 846 __objc_update_classes_with_methods (struct objc_method *method_a, struct objc_method *method_b)
 847 {
 848   int hash;
 849
 850   /* Iterate over all classes.  */
 851   for (hash = 0; hash < CLASS_TABLE_SIZE; hash++)
 852     {
 853       class_node_ptr node = class_table_array[hash];
 854
 855       while (node != NULL)
 856         {
 857           /* Iterate over all methods in the class.  */
 858           Class class = node->pointer;
 859           struct objc_method_list * method_list = class->methods;
 860
 861           while (method_list)
 862             {
 863               int i;
 864
 865               for (i = 0; i < method_list->method_count; ++i)
 866                 {
 867                   struct objc_method *method = &method_list->method_list[i];
 868
 869                   /* If the method is one of the ones we are looking
 870                      for, update the implementation.  */
 871                   if (method == method_a)
 872                     {
 873                       sarray_at_put_safe (class->dtable,
 874                                           (sidx) method_a->method_name->sel_id,
 875                                           method_a->method_imp);
 876                     }
 877
 878                   if (method == method_b)
 879                     {
 880                       if (method_b != NULL)
 881                         {
 882                           sarray_at_put_safe (class->dtable,
 883                                               (sidx) method_b->method_name->sel_id,
 884                                               method_b->method_imp);
 885                         }
 886                     }
 887                 }
 888
 889               method_list = method_list->method_next;
 890             }
 891           node = node->next;
 892         }
 893     }
 894 }
 895
 896 /* Resolve super/subclass links for all classes.  The only thing we
 897    can be sure of is that the class_pointer for class objects point to
 898    the right meta class objects.  */
 899 void
 900 __objc_resolve_class_links (void)
 901 {
 902   struct class_table_enumerator *es = NULL;
 903   Class object_class = objc_get_class ("Object");
 904   Class class1;
 905
 906   assert (object_class);
 907
 908   objc_mutex_lock (__objc_runtime_mutex);
 909
 910   /* Assign subclass links.  */
 911   while ((class1 = class_table_next (&es)))
 912     {
 913       /* Make sure we have what we think we have.  */
 914       assert (CLS_ISCLASS (class1));
 915       assert (CLS_ISMETA (class1->class_pointer));
 916
 917       /* The class_pointer of all meta classes point to Object's meta
 918          class.  */
 919       class1->class_pointer->class_pointer = object_class->class_pointer;
 920
 921       if (! CLS_ISRESOLV (class1))
 922         {
 923           CLS_SETRESOLV (class1);
 924           CLS_SETRESOLV (class1->class_pointer);
 925
 926           if (class1->super_class)
 927             {
 928               Class a_super_class
 929                 = objc_get_class ((char *) class1->super_class);
 930
 931               assert (a_super_class);
 932
 933               DEBUG_PRINTF ("making class connections for: %s\n",
 934                             class1->name);
 935
 936               /* Assign subclass links for superclass.  */
 937               class1->sibling_class = a_super_class->subclass_list;
 938               a_super_class->subclass_list = class1;
 939
 940               /* Assign subclass links for meta class of superclass.  */
 941               if (a_super_class->class_pointer)
 942                 {
 943                   class1->class_pointer->sibling_class
 944                     = a_super_class->class_pointer->subclass_list;
 945                   a_super_class->class_pointer->subclass_list
 946                     = class1->class_pointer;
 947                 }
 948             }
 949           else /* A root class, make its meta object be a subclass of
 950                   Object.  */
 951             {
 952               class1->class_pointer->sibling_class
 953                 = object_class->subclass_list;
 954               object_class->subclass_list = class1->class_pointer;
 955             }
 956         }
 957     }
 958
 959   /* Assign superclass links.  */
 960    es = NULL;
 961    while ((class1 = class_table_next (&es)))
 962     {
 963       Class sub_class;
 964       for (sub_class = class1->subclass_list; sub_class;
 965            sub_class = sub_class->sibling_class)
 966         {
 967           sub_class->super_class = class1;
 968           if (CLS_ISCLASS (sub_class))
 969             sub_class->class_pointer->super_class = class1->class_pointer;
 970         }
 971     }
 972
 973   objc_mutex_unlock (__objc_runtime_mutex);
 974 }
 975
 976 const char *
 977 class_getName (Class class_)
 978 {
 979   if (class_ == Nil)
 980     return "nil";
 981
 982   return class_->name;
 983 }
 984
 985 BOOL
 986 class_isMetaClass (Class class_)
 987 {
 988   /* CLS_ISMETA includes the check for Nil class_.  */
 989   return CLS_ISMETA (class_);
 990 }
 991
 992 /* Even inside libobjc it may be worth using class_getSuperclass
 993    instead of accessing class_->super_class directly because it
 994    resolves the class links if needed.  If you access
 995    class_->super_class directly, make sure to deal with the situation
 996    where the class is not resolved yet!  */
 997 Class
 998 class_getSuperclass (Class class_)
 999 {
1000   if (class_ == Nil)
1001     return Nil;
1002
1003   /* Classes that are in construction are not resolved and can not be
1004      resolved!  */
1005   if (CLS_IS_IN_CONSTRUCTION (class_))
1006     return Nil;
1007
1008   /* If the class is not resolved yet, super_class would point to a
1009      string (the name of the super class) as opposed to the actual
1010      super class.  In that case, we need to resolve the class links
1011      before we can return super_class.  */
1012   if (! CLS_ISRESOLV (class_))
1013     __objc_resolve_class_links ();
1014
1015   return class_->super_class;
1016 }
1017
1018 int
1019 class_getVersion (Class class_)
1020 {
1021   if (class_ == Nil)
1022     return 0;
1023
1024   return (int)(class_->version);
1025 }
1026
1027 void
1028 class_setVersion (Class class_, int version)
1029 {
1030   if (class_ == Nil)
1031     return;
1032
1033   class_->version = version;
1034 }
1035
1036 size_t
1037 class_getInstanceSize (Class class_)
1038 {
1039   if (class_ == Nil)
1040     return 0;
1041
1042   return class_->instance_size;
1043 }
1044
1045 #define CLASSOF(c) ((c)->class_pointer)
1046
1047 Class
1048 class_pose_as (Class impostor, Class super_class)
1049 {
1050   if (! CLS_ISRESOLV (impostor))
1051     __objc_resolve_class_links ();
1052
1053   /* Preconditions */
1054   assert (impostor);
1055   assert (super_class);
1056   assert (impostor->super_class == super_class);
1057   assert (CLS_ISCLASS (impostor));
1058   assert (CLS_ISCLASS (super_class));
1059   assert (impostor->instance_size == super_class->instance_size);
1060
1061   {
1062     Class *subclass = &(super_class->subclass_list);
1063
1064     /* Move subclasses of super_class to impostor.  */
1065     while (*subclass)
1066       {
1067         Class nextSub = (*subclass)->sibling_class;
1068
1069         if (*subclass != impostor)
1070           {
1071             Class sub = *subclass;
1072
1073             /* Classes */
1074             sub->sibling_class = impostor->subclass_list;
1075             sub->super_class = impostor;
1076             impostor->subclass_list = sub;
1077
1078             /* It will happen that SUB is not a class object if it is
1079                the top of the meta class hierarchy chain (root
1080                meta-class objects inherit their class object).  If
1081                that is the case... don't mess with the meta-meta
1082                class.  */
1083             if (CLS_ISCLASS (sub))
1084               {
1085                 /* Meta classes */
1086                 CLASSOF (sub)->sibling_class =
1087                   CLASSOF (impostor)->subclass_list;
1088                 CLASSOF (sub)->super_class = CLASSOF (impostor);
1089                 CLASSOF (impostor)->subclass_list = CLASSOF (sub);
1090               }
1091           }
1092
1093         *subclass = nextSub;
1094       }
1095
1096     /* Set subclasses of superclass to be impostor only.  */
1097     super_class->subclass_list = impostor;
1098     CLASSOF (super_class)->subclass_list = CLASSOF (impostor);
1099
1100     /* Set impostor to have no sibling classes.  */
1101     impostor->sibling_class = 0;
1102     CLASSOF (impostor)->sibling_class = 0;
1103   }
1104
1105   /* Check relationship of impostor and super_class is kept.  */
1106   assert (impostor->super_class == super_class);
1107   assert (CLASSOF (impostor)->super_class == CLASSOF (super_class));
1108
1109   /* This is how to update the lookup table.  Regardless of what the
1110      keys of the hashtable is, change all values that are superclass
1111      into impostor.  */
1112
1113   objc_mutex_lock (__objc_runtime_mutex);
1114
1115   class_table_replace (super_class, impostor);
1116
1117   objc_mutex_unlock (__objc_runtime_mutex);
1118
1119   /* Next, we update the dispatch tables...  */
1120   __objc_update_dispatch_table_for_class (CLASSOF (impostor));
1121   __objc_update_dispatch_table_for_class (impostor);
1122
1123   return impostor;
1124 }