commit b95e303

use hash table for graph target lookup

 1@@ -196,12 +196,8 @@ addrule(struct GraphState *gs, const char *name, const struct RuleNode *rule)
 2 			return;
 3 	}
 4 
 5-	t = findtarget(gs->graph, name);
 6-	if (!t) {
 7-		gs->graph->v = xrealloc(gs->graph->v, (gs->graph->n + 1) * sizeof(gs->graph->v[0]));
 8-		t = &gs->graph->v[gs->graph->n++];
 9-		memset(t, 0, sizeof(*t));
10-		t->name = intern(name);
11+	t = gettarget(gs->graph, name, 0);
12+	if (!t->defined) {
13 		t->dcolon = rule->dcolon;
14 	} else if (t->defined && t->dcolon != rule->dcolon) {
15 		fprintf(stderr, "target file `%s' has both : and :: entries, i can't handle that!\n", name);
16@@ -243,13 +239,7 @@ addrule(struct GraphState *gs, const char *name, const struct RuleNode *rule)
17 
18 		if (strchr(prereqs.v[i], '%'))
19 			continue;
20-		t = findtarget(gs->graph, prereqs.v[i]);
21-		if (!t) {
22-			gs->graph->v = xrealloc(gs->graph->v, (gs->graph->n + 1) * sizeof(gs->graph->v[0]));
23-			t = &gs->graph->v[gs->graph->n++];
24-			memset(t, 0, sizeof(*t));
25-			t->name = intern(prereqs.v[i]);
26-		}
27+		t = gettarget(gs->graph, prereqs.v[i], 0);
28 		if (hasword(gs->phony, t->name))
29 			t->phony = 1;
30 		memset(&penv, 0, sizeof(penv));
31@@ -384,10 +374,7 @@ buildgraph(const struct RuleSet *ruleset, const struct StrList *goals, struct Gr
32 				free(gs.tas);
33 				return -1;
34 			}
35-			graph->v = xrealloc(graph->v, (graph->n + 1) * sizeof(graph->v[0]));
36-			t = &graph->v[graph->n++];
37-			memset(t, 0, sizeof(*t));
38-			t->name = intern(goals->v[i]);
39+			t = gettarget(graph, goals->v[i], 0);
40 			if (hasword(gs.phony, t->name))
41 				t->phony = 1;
42 		}
43@@ -453,10 +440,7 @@ buildgraph(const struct RuleSet *ruleset, const struct StrList *goals, struct Gr
44 				if (!findtarget(graph, prereq)) {
45 					struct Target *nt;
46 
47-					graph->v = xrealloc(graph->v, (graph->n + 1) * sizeof(graph->v[0]));
48-					nt = &graph->v[graph->n++];
49-					memset(nt, 0, sizeof(*nt));
50-					nt->name = intern(prereq);
51+					nt = gettarget(graph, prereq, 0);
52 					if (hasword(gs.phony, nt->name))
53 						nt->phony = 1;
54 					changed = 1;
55@@ -600,9 +584,13 @@ freegraph(struct Graph *graph)
56 	for (i = 0; i < graph->nsubs; i++)
57 		freesubgraph(&graph->subs[i]);
58 	free(graph->v);
59+	free(graph->targetindex);
60 	free(graph->subs);
61 	graph->v = 0;
62 	graph->n = 0;
63+	graph->targetindex = 0;
64+	graph->ntargetindex = 0;
65+	graph->cap_targetindex = 0;
66 	graph->subs = 0;
67 	graph->nsubs = 0;
68 }

 1@@ -346,10 +346,7 @@ mergetarget(struct Graph *graph, const struct Target *src)
 2 
 3 	dst = findtarget(graph, src->name);
 4 	if (!dst) {
 5-		graph->v = xrealloc(graph->v, (graph->n + 1) * sizeof(graph->v[0]));
 6-		dst = &graph->v[graph->n++];
 7-		memset(dst, 0, sizeof(*dst));
 8-		dst->name = src->name;
 9+		dst = gettarget(graph, src->name, 0);
10 		if (src->owner)
11 			dst->owner = xstrdup(src->owner);
12 	} else if (!dst->owner && src->owner) {

1@@ -74,6 +74,7 @@ void envsetvar(struct Env *env, const char *name, char *val, int simple, enum Or
2                int exported);
3 struct Target *findtarget(struct Graph *graph, const char *name);
4 const struct Target *findctarget(const struct Graph *graph, const char *name);
5+struct Target *gettarget(struct Graph *graph, const char *name, int *added);
6 const char *firstprereq(const struct Target *t);
7 char *joinallprereqs(const struct Target *t, const char *sep);
8 size_t totalprereqs(const struct Target *t);

 1@@ -229,10 +229,14 @@ struct Target {
 2 };
 3 
 4 struct SubGraph;
 5+struct GraphIndexEnt;
 6 
 7 struct Graph {
 8 	struct Target *v;
 9 	size_t n;
10+	struct GraphIndexEnt *targetindex;
11+	size_t ntargetindex;
12+	size_t cap_targetindex;
13 	struct SubGraph *subs;
14 	size_t nsubs;
15 };

 1@@ -181,6 +181,11 @@ static struct InternEntry *intern_table;
 2 static size_t intern_n;
 3 static size_t intern_cap;
 4 
 5+struct GraphIndexEnt {
 6+	const char *name;
 7+	size_t idx;
 8+};
 9+
10 static size_t
11 strhash(const char *s)
12 {
13@@ -652,11 +657,79 @@ findtarget0(const struct Graph *graph, const char *name)
14 	size_t i;
15 
16 	iname = intern(name);
17-	for (i = 0; i < graph->n; i++) {
18-		if (graph->v[i].name == iname)
19-			return &graph->v[i];
20+	if (!graph->cap_targetindex)
21+		return 0;
22+	i = strhash(iname) & (graph->cap_targetindex - 1);
23+	for (;;) {
24+		if (!graph->targetindex[i].name)
25+			return 0;
26+		if (graph->targetindex[i].name == iname)
27+			return &graph->v[graph->targetindex[i].idx];
28+		i = (i + 1) & (graph->cap_targetindex - 1);
29 	}
30-	return 0;
31+}
32+
33+static void
34+graphindexgrow(struct Graph *graph)
35+{
36+	size_t i, newcap;
37+	struct GraphIndexEnt *newtab;
38+
39+	newcap = graph->cap_targetindex ? graph->cap_targetindex * 2 : 16;
40+	newtab = xmalloc(newcap * sizeof(newtab[0]));
41+	memset(newtab, 0, newcap * sizeof(newtab[0]));
42+	for (i = 0; i < graph->cap_targetindex; i++) {
43+		size_t j;
44+
45+		if (!graph->targetindex[i].name)
46+			continue;
47+		j = strhash(graph->targetindex[i].name) & (newcap - 1);
48+		while (newtab[j].name)
49+			j = (j + 1) & (newcap - 1);
50+		newtab[j] = graph->targetindex[i];
51+	}
52+	free(graph->targetindex);
53+	graph->targetindex = newtab;
54+	graph->cap_targetindex = newcap;
55+}
56+
57+static void
58+graphindexput(struct Graph *graph, const char *name, size_t idx)
59+{
60+	size_t i;
61+
62+	if (!graph->cap_targetindex || graph->ntargetindex * 3 >= graph->cap_targetindex * 2)
63+		graphindexgrow(graph);
64+	i = strhash(name) & (graph->cap_targetindex - 1);
65+	while (graph->targetindex[i].name)
66+		i = (i + 1) & (graph->cap_targetindex - 1);
67+	graph->targetindex[i].name = name;
68+	graph->targetindex[i].idx = idx;
69+	graph->ntargetindex++;
70+}
71+
72+struct Target *
73+gettarget(struct Graph *graph, const char *name, int *added)
74+{
75+	struct Target *t;
76+	const char *iname;
77+
78+	t = findtarget(graph, name);
79+	if (t) {
80+		if (added)
81+			*added = 0;
82+		return t;
83+	}
84+	iname = intern(name);
85+	graph->v = xrealloc(graph->v, (graph->n + 1) * sizeof(graph->v[0]));
86+	t = &graph->v[graph->n];
87+	memset(t, 0, sizeof(*t));
88+	t->name = iname;
89+	graphindexput(graph, iname, graph->n);
90+	graph->n++;
91+	if (added)
92+		*added = 1;
93+	return t;
94 }
95 
96 struct Target *