diff options
Diffstat (limited to 'obsolete')
| -rw-r--r-- | obsolete/dom.c | 155 | ||||
| -rw-r--r-- | obsolete/table_test.c | 92 |
2 files changed, 247 insertions, 0 deletions
diff --git a/obsolete/dom.c b/obsolete/dom.c new file mode 100644 index 0000000..c6eaa97 --- /dev/null +++ b/obsolete/dom.c @@ -0,0 +1,155 @@ +#include <stdio.h> +#include <string.h> +#include <stdlib.h> +#define MAXN 1000 +#define MAX_HASH 1021 +typedef struct Edge Edge; +typedef struct Set Set; +typedef Set *Set_t; +typedef struct SetNode { + int val; + struct SetNode *next; +} SetNode; +struct Set { + SetNode *head[MAX_HASH]; +}; + +Set_t set_create() { + Set_t set = (Set_t)malloc(sizeof(Set)); + memset(set->head, 0, sizeof set->head); + return set; +} + +int set_belongs(Set_t set, int val) { + SetNode *p; + for (p = set->head[val % MAX_HASH]; p; p = p->next) + if (p->val == val) return 1; + return 0; +} + +void set_push(Set_t set, int val) { + SetNode *p = (SetNode*)malloc(sizeof(SetNode)); + int hv = val % MAX_HASH; + p->next = set->head[hv]; + p->val = val; + set->head[hv] = p; +} + +struct Edge { + int to; + Edge *next; +} *head[MAXN], *rhead[MAXN]; + +typedef struct DFNode DFNode; +struct DFNode { + int id; + DFNode *next; +}; + +void add_edge(int a, int b, Edge **head) { + Edge *p = (Edge*)malloc(sizeof(Edge)); + p->to = b; + p->next = head[a]; + head[a] = p; +} +int dom[MAXN], ord[MAXN], vis[MAXN], par[MAXN]; +int n, n0, m; +DFNode *df[MAXN]; +Set_t dfset[MAXN]; + +void dfs(int u, int v) { + static int ocnt = 0; + Edge *e; + if (vis[u] != -1) return; + par[u] = v; + vis[u] = 0; + for (e = head[u]; e; e = e->next) + dfs(e->to, u); + vis[u] = ocnt; + ord[ocnt++] = u; +} + +int intersect(int b1, int b2) { + while (b1 != b2) + if (b1 < b2) b1 = dom[b1]; + else b2 = dom[b2]; + return b1; +} + +int main() { + int i; + int ch = 1; + scanf("%d %d %d", &n, &m, &n0); + for (i = 0; i < m; i++) + { + int a, b; + scanf("%d %d", &a, &b); + add_edge(a, b, head); + add_edge(b, a, rhead); + } + for (i = 0; i < n; i++) + vis[i] = dom[i] = -1; + dfs(n0, -1); + for (i = 0; i < n; i++) + printf("%d ", ord[i]); puts(""); + dom[vis[n0]] = vis[n0]; + while (ch) + { + int i; + ch = 0; + for (i = n - 2; i >= 0; i--) + { + int id = ord[i]; + Edge *e = rhead[id]; + int new_idom = vis[par[id]]; + for (; e; e = e->next) + { + int p = e->to; + if (vis[p] == new_idom) continue; + if (dom[vis[p]] != -1) + new_idom = intersect(vis[p], new_idom); + } + if (dom[i] != new_idom) + { + ch = 1; + dom[i] = new_idom; + } + } + for (i = 0; i < n; i++) + printf("%d ", ord[dom[vis[i]]]); puts(""); + } + for (i = 0; i < n; i++) + { + dfset[i] = set_create(); + df[i] = NULL; + } + for (i = 0; i < n; i++) + if (rhead[i] && rhead[i]->next) + { + Edge *p = rhead[i]; + for (; p; p = p->next) + { + int runner = p->to; + while (vis[runner] != dom[vis[i]]) + { + if (!set_belongs(dfset[runner], i)) + { + DFNode *np = (DFNode*)malloc(sizeof(DFNode)); + np->id = i; + np->next = df[runner]; + set_push(dfset[runner], i); + df[runner] = np; + } + runner = ord[dom[vis[runner]]]; + } + } + } + for (i = 0; i < n; i++) + { + DFNode *p = df[i]; + printf("%d: ", i); + for (; p; p = p->next) + printf("%d ", p->id); puts(""); + } + return 0; +} diff --git a/obsolete/table_test.c b/obsolete/table_test.c new file mode 100644 index 0000000..46b9b8a --- /dev/null +++ b/obsolete/table_test.c @@ -0,0 +1,92 @@ +#include <stdlib.h> +#include <stdio.h> +#include "semantics.h" +#define PV(str) \ + do \ + { \ + if (cscope_push_var(scope, newvar(str))) \ + fprintf(stderr, "Successfully pushed var: %s\n", str); \ + else \ + fprintf(stderr, "Naming conflicts deteced: %s\n", str); \ + } while(0) + +#define PT(str) \ + do \ + { \ + if (cscope_push_type(scope, newtype(str))) \ + fprintf(stderr, "Successfully pushed type: %s\n", str); \ + else \ + fprintf(stderr, "Naming conflicts deteced: %s\n", str); \ + } while(0) + +CVar_t newvar(const char *name) { + return cvar_create(name, NULL, NULL); +} + +CType_t newtype(const char *name) { + return ctype_create(name, 0, NULL); +} + +void manual() { + CScope_t scope = cscope_create(); + PV("a"); + PV("b"); + PV("asdf"); + PV("fdsa"); + PV("hello"); + cscope_debug_print(scope); + cscope_enter(scope); + PV("a"); + PV("hello"); + PT("CType"); + cscope_debug_print(scope); + cscope_enter(scope); + PV("a"); + PV("yay"); + PV("world"); + PT("CType"); + PV("a"); + cscope_debug_print(scope); + cscope_exit(scope); + cscope_debug_print(scope); + cscope_exit(scope); + cscope_debug_print(scope); +} + +char *str_gen(int len) { + int i; + char *str = malloc(len); + for (i = 0; i < len; i++) + str[i] = rand() % 2 + 'a'; + return str; +} + +void autoforce() { + static const int max_lvl = 100, + max_push = 10; + int i, j; + CScope_t scope = cscope_create(); + for (i = 0; i < max_lvl; i++) + { + cscope_enter(scope); + int push = rand() % max_push; + for (j = 0; j < push; j++) + { + int len = rand() % 3 + 1; + int opt = rand() & 1; + if (opt) PV(str_gen(len)); + else PT(str_gen(len)); + } + } + for (i = 0; i < max_lvl; i++) + { + cscope_debug_print(scope); + cscope_exit(scope); + } +} + +int main() { +/* manual(); */ + autoforce(); + return 0; +} |