refactor

1 files changed, 259 insertions, 54 deletions

diff --git a/include/direct.h b/include/direct.h
index c26907e..4302db0 100644
--- a/include/direct.h
+++ b/include/direct.h
@@ -1,11 +1,21 @@
-#ifndef DT_H
-#define DT_H
+// direct.h — Computation graph with topological update
+//
+// Thread safety: Not thread-safe. External synchronization required.
+// Behavior: dt_update does DFS from origin, evaluates nodes in reverse
+//   order (topological). Uses a global generation counter to avoid
+//   re-visiting nodes. The counter is u64 and overflows after ~1.8e19
+//   calls, at which point reachable node generations are reset.
+// Memory: Edges are heap-allocated per dt_connect. Use dt_clear_edges to
+//   free all edges for a node.
 
-#include <stdbool.h>
-#include <stdlib.h>
-#include <stdio.h>
+#ifndef DIRECT_H
+#define DIRECT_H
 
-struct value_t;
+/* USER-DEFINED (define before including):
+ *   typedef <type> direct_value_t;
+ */
+
+#include "type.h"
 
 typedef struct edge {
   struct edge *next;
@@ -14,108 +24,303 @@ typedef struct edge {
 
 typedef struct node {
   struct edge *edge;
-  value_t x;
-  bool flag;
-  value_t (*function)(struct node *node);
+  direct_value_t x;
+  u64 visited_generation;
+  direct_value_t (*function)(struct node *node);
 } node_t;
 
-void dt_connect(node_t *, node_t *);
+int dt_connect(node_t *, node_t *);
+int dt_connect_ok(node_t *, node_t *);
 void dt_disconnect(node_t *, node_t *);
 void dt_update(node_t *);
+void dt_update_trace(node_t *);
+void dt_clear_edges(node_t *);
 
-value_t dt_one(node_t *node);
-value_t dt_add(node_t *node);
-value_t dt_subtract(node_t *node);
+direct_value_t dt_one(node_t *node);
+direct_value_t dt_add(node_t *node);
+direct_value_t dt_subtract(node_t *node);
 
 #endif
 
 #ifdef DT_IMPLEMENTATION
+#ifndef DT_IMPLEMENTED
+#define DT_IMPLEMENTED
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+
+// dt_connect() / dt_connect_ok()
+//
+// Add an edge from 'to' to 'from'. When dt_update is called on a node,
+// it will recursively evaluate its connected dependents.
+//
+// to   - Destination node (depends on 'from')
+// from - Source node
+//
+// return - 1 on success, 0 on failure
+
+int dt_connect(node_t *to, node_t *from) {
+  return dt_connect_ok(to, from);
+}
+
+int dt_connect_ok(node_t *to, node_t *from) {
+  if (!to || !from)
+    return 0;
 
-void dt_connect(node_t *to, node_t *from) {
   edge_t *edge = malloc(sizeof(edge_t));
+  if (!edge)
+    return 0;
   edge->node = from;
   edge->next = to->edge;
   to->edge = edge;
+  return 1;
 }
 
+// dt_disconnect()
+//
+// Remove the edge from 'to' to 'from'
+
 void dt_disconnect(node_t *to, node_t *from) {
+  if (!to || !from)
+    return;
+
   edge_t *edge = to->edge;
-  edge_t *last = NULL;
+  edge_t *prev = NULL;
 
   while (edge) {
     if (edge->node == from) {
-      edge_t *tmp = edge;
-      last->next = edge->next;
-      free(tmp);
+      if (prev) {
+        prev->next = edge->next;
+      } else {
+        to->edge = edge->next;
+      }
+      free(edge);
+      break;
     }
-
-    last = edge;
+    prev = edge;
     edge = edge->next;
   }
 }
 
-void dt_update(node_t *origin) {
-  // printf(">: %p - %lf\n", origin, origin->x);
+static u64 _dt_generation = 1;
 
-  edge_t *edge = origin->edge;
-  origin->flag = !origin->flag;
+static int dt_grow(node_t ***s, node_t ***e, u32 *cap) {
+  if (*cap > UINT32_MAX / 2) return 0;
+  u32 nc = (*cap) * 2;
+  size_t grow_sz = (size_t)nc * sizeof(node_t *);
+  if (nc > 0 && grow_sz / nc != sizeof(node_t *)) return 0;
+  node_t **ns = realloc(*s, grow_sz);
+  if (!ns) return 0;
+  node_t **ne = realloc(*e, grow_sz);
+  if (!ne) {
+    node_t **shrunk = realloc(*s, (size_t)(*cap) * sizeof(node_t *));
+    if (!shrunk)
+      shrunk = ns;
+    else
+      free(ns);
+    *s = shrunk;
+    return 0;
+  }
+  *s = ns;
+  *e = ne;
+  *cap = nc;
+  return 1;
+}
 
-  while (edge) {
-    if (origin->flag != edge->node->flag) {
-      dt_update(edge->node);
+static void dt_update_impl(node_t *origin) {
+  if (!origin || !origin->function)
+    return;
+  u32 cap = 64;
+  node_t **dfs = malloc(cap * sizeof(node_t *));
+  if (!dfs) return;
+  node_t **eval = malloc(cap * sizeof(node_t *));
+  if (!eval) { free(dfs); return; }
+  u32 sp = 0, ep = 0;
+  dfs[sp++] = origin;
+  while (sp > 0) {
+    node_t *c = dfs[--sp];
+    if (!c || !c->function) continue;
+    if (c->visited_generation == _dt_generation) continue;
+    c->visited_generation = _dt_generation;
+    if (!dt_grow(&dfs, &eval, &cap)) { free(dfs); free(eval); return; }
+    eval[ep++] = c;
+    edge_t *e = c->edge;
+    while (e) {
+      if (e->node && e->node->function && e->node->visited_generation != _dt_generation) {
+        if (!dt_grow(&dfs, &eval, &cap)) { free(dfs); free(eval); return; }
+        dfs[sp++] = e->node;
+      }
+      e = e->next;
     }
-
-    edge = edge->next;
   }
-
-  origin->x = origin->function(origin);
-  // printf("<: %p - %lf\n", origin, origin->x);
+  for (u32 i = ep; i > 0; i--)
+    eval[i - 1]->x = eval[i - 1]->function(eval[i - 1]);
+  free(dfs);
+  free(eval);
 }
 
-void dt_update_trace(node_t *origin) {
-  printf(">: %p - %lf\n", origin, origin->x);
+static void dt_reset_generations(node_t *origin, node_t **dfs, u32 *dfs_sp,
+                                   u32 cap, u32 *stack_cap) {
+    (void)cap;
+    if (*stack_cap == 0) return;
+    node_t *c = origin;
+    if (!c || !c->function) return;
+    dfs[(*dfs_sp)++] = c;
+    c->visited_generation = 0;
+    while (*dfs_sp > 0) {
+        node_t *n = dfs[--(*dfs_sp)];
+        edge_t *e = n->edge;
+        while (e) {
+            if (e->node && e->node->function && e->node->visited_generation != 0) {
+                if (*dfs_sp >= *stack_cap) {
+                    u32 nc = (*stack_cap) * 2;
+                    node_t **nd = realloc(dfs, (size_t)nc * sizeof(node_t *));
+                    if (nd) { dfs = nd; *stack_cap = nc; }
+                    else return;
+                }
+                dfs[(*dfs_sp)++] = e->node;
+                e->node->visited_generation = 0;
+            }
+            e = e->next;
+        }
+    }
+}
 
-  edge_t *edge = origin->edge;
-  origin->flag = !origin->flag;
+// dt_update()
+//
+// Evaluate the computation graph starting from origin. Performs DFS to
+// collect all reachable nodes, then evaluates them in reverse (topological)
+// order. Uses generation counters to skip already-evaluated nodes.
 
-  while (edge) {
-    if (origin->flag != edge->node->flag) {
-      dt_update_trace(edge->node);
+void dt_update(node_t *origin) {
+  if (!origin || !origin->function)
+    return;
+  if (_dt_generation >= UINT64_MAX) {
+    _dt_generation = 1;
+    u32 cap = 64;
+    u32 sp = 0;
+    node_t **dfs = malloc(cap * sizeof(node_t *));
+    if (dfs) {
+        dt_reset_generations(origin, dfs, &sp, cap, &cap);
+        free(dfs);
     }
-
-    edge = edge->next;
+  } else {
+    _dt_generation++;
   }
+  dt_update_impl(origin);
+}
 
-  origin->x = origin->function(origin);
-  printf("<: %p - %lf\n", origin, origin->x);
+static void dt_update_trace_impl(node_t *origin) {
+  if (!origin || !origin->function)
+    return;
+  u32 cap = 64;
+  node_t **dfs = malloc(cap * sizeof(node_t *));
+  if (!dfs) return;
+  node_t **eval = malloc(cap * sizeof(node_t *));
+  if (!eval) { free(dfs); return; }
+  u32 sp = 0, ep = 0;
+  dfs[sp++] = origin;
+  while (sp > 0) {
+    node_t *c = dfs[--sp];
+    if (!c || !c->function) continue;
+    if (c->visited_generation == _dt_generation) continue;
+    c->visited_generation = _dt_generation;
+    if (!dt_grow(&dfs, &eval, &cap)) { free(dfs); free(eval); return; }
+    eval[ep++] = c;
+    fprintf(stderr, ">: %p\n", (void *)c);
+    edge_t *e = c->edge;
+    while (e) {
+      if (e->node && e->node->function && e->node->visited_generation != _dt_generation) {
+        if (!dt_grow(&dfs, &eval, &cap)) { free(dfs); free(eval); return; }
+        dfs[sp++] = e->node;
+      }
+      e = e->next;
+    }
+  }
+  for (u32 i = ep; i > 0; i--) {
+    node_t *n = eval[i - 1];
+    n->x = n->function(n);
+    fprintf(stderr, "<: %p\n", (void *)n);
+  }
+  free(dfs);
+  free(eval);
 }
 
-value_t dt_one(node_t *node) {
-  return 1;
+// dt_update_trace()
+//
+// Same as dt_update, but prints each node's address to stderr as it is
+// visited (">:") and evaluated ("<:") for debugging purposes.
+
+void dt_update_trace(node_t *origin) {
+  if (!origin || !origin->function)
+    return;
+  if (_dt_generation >= UINT64_MAX) {
+    _dt_generation = 1;
+    u32 cap = 64;
+    u32 sp = 0;
+    node_t **dfs = malloc(cap * sizeof(node_t *));
+    if (dfs) {
+        dt_reset_generations(origin, dfs, &sp, cap, &cap);
+        free(dfs);
+    }
+  } else {
+    _dt_generation++;
+  }
+  dt_update_trace_impl(origin);
 }
 
-value_t dt_add(node_t *node) {
+// dt_one() - Constant node that always returns 1
+direct_value_t dt_one(node_t *node) { (void)node; return 1; }
+
+// dt_add() - Sums the values of all connected input nodes plus the node's own value
+direct_value_t dt_add(node_t *node) {
+  if (!node)
+    return 0;
   edge_t *edge = node->edge;
-  value_t x = node->x;
+  direct_value_t x = node->x;
 
-  while(edge) {
-    x += edge->node->x;
+  while (edge) {
+    if (edge->node)
+      x += edge->node->x;
     edge = edge->next;
   }
 
   return x;
 }
 
-value_t dt_subtract(node_t *node) {
+// dt_subtract() - Subtracts all connected input node values from the node's own value
+direct_value_t dt_subtract(node_t *node) {
+  if (!node)
+    return 0;
   edge_t *edge = node->edge;
-  value_t x = node->x;
+  direct_value_t x = node->x;
 
-  while(edge) {
-    x -= edge->node->x;
+  while (edge) {
+    if (edge->node)
+      x -= edge->node->x;
     edge = edge->next;
   }
 
   return x;
 }
 
-#endif
+// dt_clear_edges()
+//
+// Free all edges connected to a node
+
+void dt_clear_edges(node_t *node) {
+  if (!node)
+    return;
+  edge_t *edge = node->edge;
+  node->edge = NULL;
+
+  while (edge) {
+    edge_t *next = edge->next;
+    free(edge);
+    edge = next;
+  }
+}
+
+#endif /* DT_IMPLEMENTED */
+#endif /* DT_IMPLEMENTATION */