Index: ChangeLog
===================================================================
--- ChangeLog   (revision 172255)
+++ ChangeLog   (working copy)
@@ -1,3 +1,15 @@
+2011-04-11  Nicola Pero  <nicola.pero@meta-innovation.com>
+
+       Rewritten the hashtable holding interfaces for speed.
+       * objc-act.h (INTERFACE_HASHTABLE_SIZE, interface_hashtable_entry,
+       interface_hash, interface_hashtable): New.
+       (interface_chain, OCTI_INF_CHAIN): Removed.
+       * objc-act.c (interface_tuple, interface_htab, hash_interface,
+       eq_interface): Removed.
+       (lookup_interface): Rewritten.
+       (add_class): Renamed to add_interface, reimplemented.
+       (interface_hashtable): New.
+
 2011-04-06  Joseph Myers  <joseph@codesourcery.com>
 
        * objc-act.c: Include c-target.h instead of target.h.
Index: objc-act.c
===================================================================
--- objc-act.c  (revision 172255)
+++ objc-act.c  (working copy)
@@ -187,7 +187,11 @@ static hash hash_lookup (hash *, tree);
 static tree lookup_method (tree, tree);
 static tree lookup_method_static (tree, tree, int);
 
-static tree add_class (tree, tree);
+/* Hashtable with all the interfaces.  You can look things up in it by
+   using lookup_interface().  */
+interface_hash *interface_hashtable = 0;
+static void add_interface (tree, tree);
+
 static void add_category (tree, tree);
 static inline tree lookup_category (tree, tree);
 
@@ -3764,27 +3768,6 @@ objc_generate_write_barrier (tree lhs, enum tree_c
   return result;
 }
 
-struct GTY(()) interface_tuple {
-  tree id;
-  tree class_name;
-};
-
-static GTY ((param_is (struct interface_tuple))) htab_t interface_htab;
-
-static hashval_t
-hash_interface (const void *p)
-{
-  const struct interface_tuple *d = (const struct interface_tuple *) p;
-  return IDENTIFIER_HASH_VALUE (d->id);
-}
-
-static int
-eq_interface (const void *p1, const void *p2)
-{
-  const struct interface_tuple *d = (const struct interface_tuple *) p1;
-  return d->id == p2;
-}
-
 tree
 lookup_interface (tree ident)
 {
@@ -3797,19 +3780,19 @@ lookup_interface (tree ident)
     return NULL_TREE;
 
   {
-    struct interface_tuple **slot;
-    tree i = NULL_TREE;
+    interface_hash target;
+    
+    target = interface_hashtable[IDENTIFIER_HASH_VALUE (ident) % INTERFACE_HASHTABLE_SIZE];
 
-    if (interface_htab)
+    while (target)
       {
-       slot = (struct interface_tuple **)
-         htab_find_slot_with_hash (interface_htab, ident,
-                                   IDENTIFIER_HASH_VALUE (ident),
-                                   NO_INSERT);
-       if (slot && *slot)
-         i = (*slot)->class_name;
+       if (ident == target->ident)
+         return target->class_name;
+
+       target = target->next;
       }
-    return i;
+    
+    return NULL_TREE;
   }
 }
 @@ -5507,6 +5490,8 @@ hash_init (void)
 
   ivar_offset_hash_list = ggc_alloc_cleared_vec_hash (SIZEHASHTABLE);
 
+  interface_hashtable = ggc_alloc_cleared_vec_interface_hash (INTERFACE_HASHTABLE_SIZE);
+
   /* Initialize the hash table used to hold the constant string objects.  */
   string_htab = htab_create_ggc (31, string_hash,
                                   string_eq, NULL);
@@ -5878,29 +5863,16 @@ objc_add_method (tree klass, tree method, int is_c
   return method;
 }
 
-static tree
-add_class (tree class_name, tree name)
+static void
+add_interface (tree class_name, tree name)
 {
-  struct interface_tuple **slot;
-
-  /* Put interfaces on list in reverse order.  */
-  TREE_CHAIN (class_name) = interface_chain;
-  interface_chain = class_name;
-
-  if (interface_htab == NULL)
-    interface_htab = htab_create_ggc (31, hash_interface, eq_interface, NULL);
-  slot = (struct interface_tuple **)
-    htab_find_slot_with_hash (interface_htab, name,
-                             IDENTIFIER_HASH_VALUE (name),
-                             INSERT);
-  if (!*slot)
-    {
-      *slot = ggc_alloc_cleared_interface_tuple ();
-      (*slot)->id = name;
-    }
-  (*slot)->class_name = class_name;
-
-  return interface_chain;
+  int slot = IDENTIFIER_HASH_VALUE (name) % INTERFACE_HASHTABLE_SIZE;
+  interface_hash entry = ggc_alloc_interface_hashtable_entry ();
+  entry->ident = name;
+  entry->class_name = class_name;
+  
+  entry->next = interface_hashtable[slot];
+  interface_hashtable[slot] = entry;
 }
 
 static void
@@ -6633,8 +6605,8 @@ start_class (enum tree_code code, tree class_name,
         {
          warning (0, "cannot find interface declaration for %qE",
                   class_name);
-         add_class (implementation_template = objc_implementation_context,
-                    class_name);
+         add_interface (implementation_template = objc_implementation_context,
+                        class_name);
         }
 
       /* If a super class has been specified in the implementation,
@@ -6667,7 +6639,7 @@ start_class (enum tree_code code, tree class_name,
         warning (0, "duplicate interface declaration for class %qE", class_name);
 #endif
       else
-       add_class (klass, class_name);
+       add_interface (klass, class_name);
        
       if (protocol_list)
        CLASS_PROTOCOL_LIST (klass)
Index: objc-act.h
===================================================================
--- objc-act.h  (revision 172255)
+++ objc-act.h  (working copy)
@@ -258,6 +258,21 @@ extern GTY ((length ("SIZEHASHTABLE"))) hash *cls_
 extern GTY ((length ("SIZEHASHTABLE"))) hash *cls_name_hash_list;
 extern GTY ((length ("SIZEHASHTABLE"))) hash *als_name_hash_list;
 
+
+/* Hash table to manage the list of interfaces.  */
+
+#define INTERFACE_HASHTABLE_SIZE 257
+
+typedef struct interface_hashtable_entry *interface_hash;
+
+struct GTY(()) interface_hashtable_entry {
+  tree ident;
+  tree class_name;
+  interface_hash next;
+};
+
+extern GTY ((length ("INTERFACE_HASHTABLE_SIZE"))) interface_hash *interface_hashtable;
+
 /* An array of all the local variables in the current function that
    need to be marked as volatile.  */
 extern GTY(()) VEC(tree,gc) *local_variables_to_volatilize;
@@ -303,7 +318,6 @@ enum objc_tree_index
     OCTI_NST_TYPE,
     OCTI_PROTO_TYPE,
 
-    OCTI_INTF_CHAIN,
     OCTI_PROTO_CHAIN,
     OCTI_IMPL_CHAIN,
     OCTI_CLS_REF_CHAIN,
@@ -454,7 +468,6 @@ extern GTY(()) tree objc_global_trees[OCTI_MAX];
        (TREE_CODE (TYPE) == POINTER_TYPE                               \
         && TREE_TYPE (TYPE) == objc_super_template)
 
-#define interface_chain                objc_global_trees[OCTI_INTF_CHAIN]
 #define protocol_chain         objc_global_trees[OCTI_PROTO_CHAIN]
 #define implemented_classes    objc_global_trees[OCTI_IMPL_CHAIN]

