Restructure projectHEADmain

1 files changed, 138 insertions, 0 deletions

diff --git a/src/scene/scene_graph.h b/src/scene/scene_graph.h
new file mode 100644
index 0000000..a26f828
--- /dev/null
+++ b/src/scene/scene_graph.h
@@ -0,0 +1,138 @@
+/// Functions for list manipulation.
+#pragma once
+
+#include "scene_memory.h"
+
+// NOTE: SceneMemory guarantees that index 0 can be regarded as an invalid
+// index.
+
+#define MEM_GET(INDEX)                    \
+  _Generic((INDEX), camera_idx            \
+           : mem_get_camera, material_idx \
+           : mem_get_material, mesh_idx   \
+           : mem_get_mesh, mesh_link_idx  \
+           : mem_get_mesh_link, node_idx  \
+           : mem_get_node, object_idx     \
+           : mem_get_object, scene_idx    \
+           : mem_get_scene)(INDEX)
+
+#define MEM_GET_INDEX(ITEM)                       \
+  _Generic((ITEM), SceneCamera *                  \
+           : mem_get_camera_index, Material *     \
+           : mem_get_material_index, Mesh *       \
+           : mem_get_mesh_index, MeshLink *       \
+           : mem_get_mesh_link_index, SceneNode * \
+           : mem_get_node_index, SceneObject *    \
+           : mem_get_object_index, Scene *        \
+           : mem_get_scene_index)(ITEM)
+
+/// Assert the list node invariant.
+///
+/// - A node does not point to itself.
+#define ASSERT_LIST_NODE_INVARIANT(ITEM)              \
+  {                                                   \
+    const gfx_idx item_idx = MEM_GET_INDEX(ITEM).val; \
+    assert((ITEM)->prev.val != item_idx);             \
+    assert((ITEM)->next.val != item_idx);             \
+  }
+
+/// Assert the tree node invariant.
+///
+/// - A node does not point to itself.
+/// - The node's left and right siblings cannot be equal, unless both are 0.
+/// - The node's left/right sibling cannot be its child, unless both are 0.
+/// - The node's parent cannot be the node's child or sibling, unless it's 0.
+/// - If the node has a parent and the node is the leftmost sibling, then the
+///   parent's child is the node.
+#define ASSERT_TREE_NODE_INVARIANT(ITEM)                            \
+  {                                                                 \
+    const gfx_idx item_idx = MEM_GET_INDEX(ITEM).val;               \
+    assert((ITEM)->prev.val != item_idx);                           \
+    assert((ITEM)->next.val != item_idx);                           \
+    if ((ITEM)->prev.val) {                                         \
+      assert((ITEM)->prev.val != (ITEM)->next.val);                 \
+    }                                                               \
+    if ((ITEM)->child.val) {                                        \
+      assert((ITEM)->child.val != (ITEM)->prev.val);                \
+      assert((ITEM)->child.val != (ITEM)->next.val);                \
+    }                                                               \
+    assert((ITEM)->parent.val != item_idx);                         \
+    if ((ITEM)->parent.val && !(ITEM)->prev.val) {                  \
+      assert((ITEM)->parent.val != (ITEM)->prev.val);               \
+      assert((ITEM)->parent.val != (ITEM)->next.val);               \
+      const __typeof__(ITEM) item_parent = MEM_GET((ITEM)->parent); \
+      assert(item_parent->child.val == item_idx);                   \
+    }                                                               \
+  }
+
+/// Prepend an item to a list.
+/// Modify HEAD_INDEX to equal the index of the new head.
+#define LIST_PREPEND(HEAD_INDEX, ITEM)               \
+  (ITEM)->next = HEAD_INDEX;                         \
+  if (HEAD_INDEX.val) {                              \
+    __typeof__(ITEM) old_head = MEM_GET(HEAD_INDEX); \
+    old_head->prev            = MEM_GET_INDEX(ITEM); \
+  }                                                  \
+  HEAD_INDEX = MEM_GET_INDEX(ITEM);                  \
+  ASSERT_LIST_NODE_INVARIANT(ITEM);
+
+/// Disconnect an item from its siblings.
+#define LIST_REMOVE(ITEM)                                  \
+  if ((ITEM)->prev.val) {                                  \
+    __typeof__(ITEM) prev_sibling = MEM_GET((ITEM)->prev); \
+    prev_sibling->next            = (ITEM)->next;          \
+  }                                                        \
+  if ((ITEM)->next.val) {                                  \
+    __typeof__(ITEM) next_sibling = MEM_GET((ITEM)->next); \
+    next_sibling->prev            = (ITEM)->prev;          \
+  }                                                        \
+  (ITEM)->prev.val = 0;                                    \
+  (ITEM)->next.val = 0;                                    \
+  ASSERT_LIST_NODE_INVARIANT(ITEM);
+
+/// Set the child's parent.
+///
+/// The hierarchy is a strict tree hierarchy and a parent node points to its
+/// first/leftmost child only. To add a new child, the new child becomes the
+/// leftmost node in the list of siblings, the one that the parent then points
+/// to.
+///
+/// The child is also completely disconnected from its previous hierarchy. This
+/// is because siblings in a hierarchy must all point to the same parent.
+#define SET_PARENT(CHILD, PARENT)                                         \
+  assert(CHILD);                                                          \
+  assert(CHILD != PARENT);                                                \
+  ASSERT_TREE_NODE_INVARIANT(CHILD);                                      \
+  ASSERT_TREE_NODE_INVARIANT(PARENT);                                     \
+  TREE_REMOVE(CHILD); /* Disconnect CHILD from its previous hierarchy. */ \
+  if (PARENT) {                                                           \
+    LIST_PREPEND((PARENT)->child, CHILD);                                 \
+    (CHILD)->parent = MEM_GET_INDEX(PARENT);                              \
+  } else {                                                                \
+    (CHILD)->parent.val = 0;                                              \
+  }                                                                       \
+  ASSERT_TREE_NODE_INVARIANT(CHILD);                                      \
+  if (PARENT) {                                                           \
+    ASSERT_TREE_NODE_INVARIANT(PARENT);                                   \
+  }
+
+/// Remove an item from its hierarchy.
+///
+/// The item is disconnected from its parents and siblings. The hierarchy rooted
+/// under the item remains intact.
+#define TREE_REMOVE(ITEM)                                                     \
+  assert(ITEM);                                                               \
+  if ((ITEM)->parent.val) {                                                   \
+    /* The parent points only to its first/leftmost child. If this item is */ \
+    /* the leftmost sibling, then we need to rewire the parent to point to */ \
+    /* the next sibling to keep the parent connected to its children. */      \
+    __typeof__(ITEM)       parent       = MEM_GET((ITEM)->parent);            \
+    const __typeof__(ITEM) parent_child = MEM_GET(parent->child);             \
+    if (parent_child == ITEM) {                                               \
+      assert((ITEM)->prev.val == 0);                                          \
+      parent->child = (ITEM)->next;                                           \
+    }                                                                         \
+  }                                                                           \
+  (ITEM)->parent.val = 0;                                                     \
+  LIST_REMOVE(ITEM); /* Disconnect ITEM from its siblings. */                 \
+  ASSERT_TREE_NODE_INVARIANT(ITEM);