[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH 3/5] Refactor: Use a doubly-linked list of rules instead of a sin
From: |
Mark Seaborn |
Subject: |
[PATCH 3/5] Refactor: Use a doubly-linked list of rules instead of a singly-linked list |
Date: |
Sun, 25 Feb 2007 18:25:40 +0000 (GMT) |
---
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;
--