[PATCH 3/5] Refactor: Use a doubly-linked list of rules instead of a singly-linked list

[Mark Seaborn]

---
 implicit.c |    2 +-
 rule.c     |   86 +++++++++++++++++++++++++-----------------------------------
 rule.h     |    7 +++--
 3 files changed, 41 insertions(+), 54 deletions(-)

diff --git a/implicit.c b/implicit.c
index d239952..82f2c79 100644
--- a/implicit.c
+++ b/implicit.c
@@ -301,7 +301,7 @@ pattern_search (struct file *file, int archive,
      and may be considered.  Put them in TRYRULES.  */
 
   nrules = 0;
-  for (rule = pattern_rules; rule != 0; rule = rule->next)
+  for (rule = pattern_rules.next; !rule->list_head; rule = rule->next)
     {
       unsigned int ti;
 
diff --git a/rule.c b/rule.c
index a12f9d1..311400e 100644
--- a/rule.c
+++ b/rule.c
@@ -24,15 +24,13 @@ Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 
02110-1301 USA.  */
 #include "variable.h"
 #include "rule.h"
 
-static void freerule (struct rule *rule, struct rule *lastrule);
+static void add_rule (struct rule *rule);
+static void remove_rule (struct rule *rule);
+static void free_rule (struct rule *rule);
 
 /* Chain of all pattern rules.  */
 
-struct rule *pattern_rules;
-
-/* Pointer to last rule in the chain, so we can add onto the end.  */
-
-struct rule *last_pattern_rule;
+struct rule pattern_rules = { 1, &pattern_rules, &pattern_rules };
 
 /* Number of rules in the chain.  */
 
@@ -75,7 +73,7 @@ count_implicit_rule_limits (void)
 
   name = 0;
   namelen = 0;
-  for (rule = pattern_rules; rule != NULL; rule = rule->next)
+  for (rule = pattern_rules.next; !rule->list_head; rule = rule->next)
     {
       unsigned int ndeps = 0;
       register struct dep *dep;
@@ -305,16 +303,13 @@ rule_dependency_lists_equal (struct rule *rule1, struct 
rule *rule2)
 int
 new_pattern_rule (struct rule *rule, int override)
 {
-  register struct rule *r, *lastrule;
+  register struct rule *r;
 
   rule->in_use = 0;
   rule->terminal = 0;
 
-  rule->next = 0;
-
   /* Search for an identical rule.  */
-  lastrule = 0;
-  for (r = pattern_rules; r != 0; lastrule = r, r = r->next)
+  for (r = pattern_rules.next; !r->list_head; r = r->next)
     {
       if (rule_targets_superset (rule, r) &&
          rule_dependency_lists_equal (rule, r))
@@ -322,42 +317,46 @@ new_pattern_rule (struct rule *rule, int override)
          /* All the dependencies matched.  */
          if (override)
            {
-             /* Remove the old rule.  */
-             freerule (r, lastrule);
-             /* Install the new one.  */
-             if (pattern_rules == 0)
-               pattern_rules = rule;
-             else
-               last_pattern_rule->next = rule;
-             last_pattern_rule = rule;
-
+             remove_rule (r);
+             free_rule (r);
+             
+             add_rule (rule);
+             
              /* We got one.  Stop looking.  */
-             goto matched;
+             return 1;
            }
          else
            {
              /* The old rule stays intact.  Destroy the new one.  */
-             freerule (rule, (struct rule *) 0);
+             free_rule (rule);
              return 0;
            }
        }
     }
 
- matched:;
-
-  if (r == 0)
-    {
-      /* There was no rule to replace.  */
-      if (pattern_rules == 0)
-       pattern_rules = rule;
-      else
-       last_pattern_rule->next = rule;
-      last_pattern_rule = rule;
-    }
+  /* There was no rule to replace.  */
+  add_rule (rule);
 
   return 1;
 }
 
+static void
+add_rule (struct rule *rule)
+{
+  rule->list_head = 0;
+  rule->next = &pattern_rules;
+  rule->prev = pattern_rules.prev;
+  pattern_rules.prev->next = rule;
+  pattern_rules.prev = rule;
+}
+
+static void
+remove_rule (struct rule *rule)
+{
+  rule->prev->next = rule->next;
+  rule->next->prev = rule->prev;
+}
+
 
 /* Install an implicit pattern rule based on the three text strings
    in the structure P points to.  These strings come from one of
@@ -410,14 +409,11 @@ install_pattern_rule (struct pspec *p, int terminal)
 }
 
 
-/* Free all the storage used in RULE and take it out of the
-   pattern_rules chain.  LASTRULE is the rule whose next pointer
-   points to RULE.  */
+/* Free all the storage used in RULE.  */
 
 static void
-freerule (struct rule *rule, struct rule *lastrule)
+free_rule (struct rule *rule)
 {
-  struct rule *next = rule->next;
   register unsigned int i;
   register struct dep *dep;
 
@@ -453,16 +449,6 @@ freerule (struct rule *rule, struct rule *lastrule)
        pointer from the `struct file' for the suffix rule.  */
 
   free (rule);
-
-  if (pattern_rules == rule)
-    if (lastrule != 0)
-      abort ();
-    else
-      pattern_rules = next;
-  else if (lastrule != 0)
-    lastrule->next = next;
-  if (last_pattern_rule == rule)
-    last_pattern_rule = lastrule;
 }
 
 /* Create a new pattern rule with the targets in the nil-terminated
@@ -552,7 +538,7 @@ print_rule_data_base (void)
   puts (_("\n# Implicit Rules"));
 
   rules = terminal = 0;
-  for (r = pattern_rules; r != 0; r = r->next)
+  for (r = pattern_rules.next; !r->list_head; r = r->next)
     {
       ++rules;
 
diff --git a/rule.h b/rule.h
index 91378f6..8f8c301 100644
--- a/rule.h
+++ b/rule.h
@@ -20,7 +20,9 @@ Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 
02110-1301 USA.  */
 
 struct rule
   {
-    struct rule *next;
+    int list_head;
+    struct rule *prev, *next;
+    
     char **targets;            /* Targets of the rule.  */
     unsigned int *lens;                /* Lengths of each target.  */
     char **suffixes;           /* Suffixes (after `%') of each target.  */
@@ -37,8 +39,7 @@ struct pspec
   };
 
 
-extern struct rule *pattern_rules;
-extern struct rule *last_pattern_rule;
+extern struct rule pattern_rules;
 extern unsigned int num_pattern_rules;
 
 extern unsigned int max_pattern_deps;
--