commit 6d171e7
shrub
·
2026-07-06 14:39:26 +0000 UTC
parent b95e303
use hash table index for env
5 files changed,
+135,
-58
+0,
-46
1@@ -14,52 +14,6 @@
2 * execute conditionals and flatten the chosen branch
3 */
4
5-struct Var *
6-findvar(struct Env *env, const char *name)
7-{
8- const char *iname;
9- size_t i;
10-
11- iname = intern(name);
12- for (i = 0; i < env->n; i++) {
13- if (env->v[i].name == iname)
14- return &env->v[i];
15- }
16- return 0;
17-}
18-
19-void
20-freeenv(struct Env *env)
21-{
22- size_t i;
23-
24- for (i = 0; i < env->n; i++)
25- free(env->v[i].val);
26- free(env->v);
27- env->v = 0;
28- env->n = 0;
29- env->cap = 0;
30-}
31-
32-void
33-copyenv(struct Env *dst, const struct Env *src)
34-{
35- size_t i;
36-
37- memset(dst, 0, sizeof(*dst));
38- if (src->n)
39- dst->v = xrealloc(0, src->n * sizeof(dst->v[0]));
40- for (i = 0; i < src->n; i++) {
41- dst->v[i].name = src->v[i].name;
42- dst->v[i].val = xstrdup(src->v[i].val);
43- dst->v[i].simple = src->v[i].simple;
44- dst->v[i].origin = src->v[i].origin;
45- dst->v[i].exported = src->v[i].exported;
46- }
47- dst->n = src->n;
48- dst->cap = src->n;
49-}
50-
51 static char *
52 runshellassign(const char *cmd)
53 {
+1,
-11
1@@ -1401,17 +1401,7 @@ fnforeach(struct EvalCtx *ctx, const char *args)
2 saved->origin = saved_origin;
3 saved->exported = saved_exported;
4 } else {
5- size_t k;
6-
7- for (k = 0; k < ctx->env->n; k++) {
8- if (ctx->env->v[k].name == iname) {
9- free(ctx->env->v[k].val);
10- memmove(&ctx->env->v[k], &ctx->env->v[k + 1],
11- (ctx->env->n - k - 1) * sizeof(ctx->env->v[0]));
12- ctx->env->n--;
13- break;
14- }
15- }
16+ envdelvar(ctx->env, iname);
17 }
18
19 free(list);
+1,
-0
1@@ -72,6 +72,7 @@ void copysubmake(struct SubMake *dst, const struct SubMake *src);
2 int parsesubmake(struct SubMake *dst, const char *cmd);
3 void envsetvar(struct Env *env, const char *name, char *val, int simple, enum Origin origin,
4 int exported);
5+void envdelvar(struct Env *env, const char *name);
6 struct Target *findtarget(struct Graph *graph, const char *name);
7 const struct Target *findctarget(const struct Graph *graph, const char *name);
8 struct Target *gettarget(struct Graph *graph, const char *name, int *added);
+5,
-0
1@@ -208,10 +208,15 @@ struct Var {
2 int exported;
3 };
4
5+struct EnvIndexEnt;
6+
7 struct Env {
8 struct Var *v;
9 size_t n;
10 size_t cap;
11+ struct EnvIndexEnt *varindex;
12+ size_t nvarindex;
13+ size_t cap_varindex;
14 };
15
16 struct Target {
+128,
-1
1@@ -186,6 +186,11 @@ struct GraphIndexEnt {
2 size_t idx;
3 };
4
5+struct EnvIndexEnt {
6+ const char *name;
7+ size_t idx;
8+};
9+
10 static size_t
11 strhash(const char *s)
12 {
13@@ -708,6 +713,105 @@ graphindexput(struct Graph *graph, const char *name, size_t idx)
14 graph->ntargetindex++;
15 }
16
17+static void
18+envindexgrow(struct Env *env)
19+{
20+ size_t i, newcap;
21+ struct EnvIndexEnt *newtab;
22+
23+ newcap = env->cap_varindex ? env->cap_varindex * 2 : 16;
24+ newtab = xmalloc(newcap * sizeof(newtab[0]));
25+ memset(newtab, 0, newcap * sizeof(newtab[0]));
26+ for (i = 0; i < env->cap_varindex; i++) {
27+ size_t j;
28+
29+ if (!env->varindex[i].name)
30+ continue;
31+ j = strhash(env->varindex[i].name) & (newcap - 1);
32+ while (newtab[j].name)
33+ j = (j + 1) & (newcap - 1);
34+ newtab[j] = env->varindex[i];
35+ }
36+ free(env->varindex);
37+ env->varindex = newtab;
38+ env->cap_varindex = newcap;
39+}
40+
41+static void
42+envindexput(struct Env *env, const char *name, size_t idx)
43+{
44+ size_t i;
45+
46+ if (!env->cap_varindex || env->nvarindex * 3 >= env->cap_varindex * 2)
47+ envindexgrow(env);
48+ i = strhash(name) & (env->cap_varindex - 1);
49+ while (env->varindex[i].name)
50+ i = (i + 1) & (env->cap_varindex - 1);
51+ env->varindex[i].name = name;
52+ env->varindex[i].idx = idx;
53+ env->nvarindex++;
54+}
55+
56+static void
57+envindexrebuild(struct Env *env)
58+{
59+ size_t i;
60+
61+ free(env->varindex);
62+ env->varindex = 0;
63+ env->nvarindex = 0;
64+ env->cap_varindex = 0;
65+ for (i = 0; i < env->n; i++)
66+ envindexput(env, env->v[i].name, i);
67+}
68+
69+struct Var *
70+findvar(struct Env *env, const char *name)
71+{
72+ const char *iname;
73+ size_t i;
74+
75+ iname = intern(name);
76+ if (!env->cap_varindex)
77+ return 0;
78+ i = strhash(iname) & (env->cap_varindex - 1);
79+ for (;;) {
80+ if (!env->varindex[i].name)
81+ return 0;
82+ if (env->varindex[i].name == iname)
83+ return &env->v[env->varindex[i].idx];
84+ i = (i + 1) & (env->cap_varindex - 1);
85+ }
86+}
87+
88+void
89+freeenv(struct Env *env)
90+{
91+ size_t i;
92+
93+ for (i = 0; i < env->n; i++)
94+ free(env->v[i].val);
95+ free(env->v);
96+ free(env->varindex);
97+ env->v = 0;
98+ env->n = 0;
99+ env->cap = 0;
100+ env->varindex = 0;
101+ env->nvarindex = 0;
102+ env->cap_varindex = 0;
103+}
104+
105+void
106+copyenv(struct Env *dst, const struct Env *src)
107+{
108+ size_t i;
109+
110+ memset(dst, 0, sizeof(*dst));
111+ for (i = 0; i < src->n; i++)
112+ envsetvar(dst, src->v[i].name, xstrdup(src->v[i].val), src->v[i].simple,
113+ src->v[i].origin, src->v[i].exported);
114+}
115+
116 struct Target *
117 gettarget(struct Graph *graph, const char *name, int *added)
118 {
119@@ -810,6 +914,7 @@ void
120 envsetvar(struct Env *env, const char *name, char *val, int simple, enum Origin origin, int exported)
121 {
122 struct Var *v;
123+ const char *iname;
124
125 v = findvar(env, name);
126 if (v) {
127@@ -829,14 +934,36 @@ envsetvar(struct Env *env, const char *name, char *val, int simple, enum Origin
128 env->cap = env->cap ? env->cap * 2 : 4;
129 env->v = xrealloc(env->v, env->cap * sizeof(env->v[0]));
130 }
131- env->v[env->n].name = intern(name);
132+ iname = intern(name);
133+ env->v[env->n].name = iname;
134 env->v[env->n].val = val;
135 env->v[env->n].simple = simple;
136 env->v[env->n].origin = origin;
137 env->v[env->n].exported = exported;
138+ envindexput(env, iname, env->n);
139 env->n++;
140 }
141
142+/* foreach puts a loop variable into Env and then removes it
143+ * we need deletion so we keep the hash table index in sync with the v array */
144+void
145+envdelvar(struct Env *env, const char *name)
146+{
147+ const char *iname;
148+ size_t i;
149+
150+ iname = intern(name);
151+ for (i = 0; i < env->n; i++) {
152+ if (env->v[i].name != iname)
153+ continue;
154+ free(env->v[i].val);
155+ memmove(&env->v[i], &env->v[i + 1], (env->n - i - 1) * sizeof(env->v[0]));
156+ env->n--;
157+ envindexrebuild(env);
158+ return;
159+ }
160+}
161+
162 void
163 warnlikemake(const char *path, int line, const char *msg)
164 {