[PATCH 4/5] Record rule targets in a hash table

[Mark Seaborn]

This is not used to replace any lookups yet.

---
 main.c |    1 +
 rule.c |   75 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 rule.h |    1 +
 3 files changed, 77 insertions(+), 0 deletions(-)

diff --git a/main.c b/main.c
index ba7f87d..351e92c 100644
--- a/main.c
+++ b/main.c
@@ -541,6 +541,7 @@ initialize_global_hash_tables (void)
   init_hash_files ();
   hash_init_directories ();
   hash_init_function_table ();
+  rule_init ();
 }
 
 static struct file *
diff --git a/rule.c b/rule.c
index 311400e..af1cefa 100644
--- a/rule.c
+++ b/rule.c
@@ -16,6 +16,8 @@ You should have received a copy of the GNU General Public 
License along with
 GNU Make; see the file COPYING.  If not, write to the Free Software
 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.  */
 
+#include <assert.h>
+
 #include "make.h"
 #include "dep.h"
 #include "filedef.h"
@@ -27,11 +29,22 @@ Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 
02110-1301 USA.  */
 static void add_rule (struct rule *rule);
 static void remove_rule (struct rule *rule);
 static void free_rule (struct rule *rule);
+
+/* List of rules with the same target. */
+struct rule_target_list
+{
+  const char *target;
+  int target_num;
+  struct rule *rule;
+  struct rule_target_list *next;
+};
 
 /* Chain of all pattern rules.  */
 
 struct rule pattern_rules = { 1, &pattern_rules, &pattern_rules };
 
+struct hash_table rules_by_target;
+
 /* Number of rules in the chain.  */
 
 unsigned int num_pattern_rules;
@@ -57,6 +70,30 @@ struct file *suffix_file;
 
 unsigned int maxsuffix;
 
+static unsigned long
+rule_hash_1 (const void *key)
+{
+  return_ISTRING_HASH_1 (((struct rule_target_list *) key)->target);
+}
+
+static unsigned long
+rule_hash_2 (const void *key)
+{
+  return_ISTRING_HASH_2 (((struct rule_target_list *) key)->target);
+}
+
+static int
+rule_hash_cmp (const void *x, const void *y)
+{
+  return_ISTRING_COMPARE (((struct rule_target_list *) x)->target,
+                         ((struct rule_target_list *) y)->target);
+}
+
+void rule_init ()
+{
+  hash_init (&rules_by_target, 199, rule_hash_1, rule_hash_2, rule_hash_cmp);
+}
+
 /* Compute the maximum dependency length and maximum number of
    dependencies of all implicit rules.  Also sets the subdir
    flag for a rule when appropriate.  */
@@ -343,6 +380,20 @@ new_pattern_rule (struct rule *rule, int override)
 static void
 add_rule (struct rule *rule)
 {
+  /* Add to hash table. */
+  int i;
+  for (i = 0; rule->targets[i] != NULL; i++)
+    {
+      struct rule_target_list *node =
+       (void *) xmalloc (sizeof (struct rule_target_list));
+      node->target = rule->targets[i];
+      node->target_num = i;
+      node->rule = rule;
+      node->next = hash_find_item (&rules_by_target, node);
+      hash_insert (&rules_by_target, node);
+    }
+
+  /* Add to list. */
   rule->list_head = 0;
   rule->next = &pattern_rules;
   rule->prev = pattern_rules.prev;
@@ -353,6 +404,30 @@ add_rule (struct rule *rule)
 static void
 remove_rule (struct rule *rule)
 {
+  /* Remove from hash table. */
+  int i;
+  for (i = 0; rule->targets[i] != NULL; i++)
+    {
+      struct rule_target_list key, **list;
+      key.target = rule->targets[i];
+      list = (struct rule_target_list **) hash_find_slot (&rules_by_target,
+                                                         &key);
+      while(1)
+       {
+         assert (*list != NULL);
+         if ((*list)->rule == rule &&
+             (*list)->target_num == i)
+           {
+             struct rule_target_list *node = *list;
+             *list = node->next;
+             free (node);
+             break;
+           }
+         list = &(*list)->next;
+       }
+    }
+
+  /* Remove from list. */
   rule->prev->next = rule->next;
   rule->next->prev = rule->prev;
 }
diff --git a/rule.h b/rule.h
index 8f8c301..4c8a8b6 100644
--- a/rule.h
+++ b/rule.h
@@ -50,6 +50,7 @@ extern struct file *suffix_file;
 extern unsigned int maxsuffix;
 
 
+void rule_init (void);
 void install_pattern_rule (struct pspec *p, int terminal);
 int new_pattern_rule (struct rule *rule, int override);
 void count_implicit_rule_limits (void);
--