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);

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 @@
	1	/// Functions for list manipulation.
	2	#pragma once
	3
	4	#include "scene_memory.h"
	5
	6	// NOTE: SceneMemory guarantees that index 0 can be regarded as an invalid
	7	// index.
	8
	9	#define MEM_GET(INDEX) \
	10	_Generic((INDEX), camera_idx \
	11	: mem_get_camera, material_idx \
	12	: mem_get_material, mesh_idx \
	13	: mem_get_mesh, mesh_link_idx \
	14	: mem_get_mesh_link, node_idx \
	15	: mem_get_node, object_idx \
	16	: mem_get_object, scene_idx \
	17	: mem_get_scene)(INDEX)
	18
	19	#define MEM_GET_INDEX(ITEM) \
	20	_Generic((ITEM), SceneCamera * \
	21	: mem_get_camera_index, Material * \
	22	: mem_get_material_index, Mesh * \
	23	: mem_get_mesh_index, MeshLink * \
	24	: mem_get_mesh_link_index, SceneNode * \
	25	: mem_get_node_index, SceneObject * \
	26	: mem_get_object_index, Scene * \
	27	: mem_get_scene_index)(ITEM)
	28
	29	/// Assert the list node invariant.
	30	///
	31	/// - A node does not point to itself.
	32	#define ASSERT_LIST_NODE_INVARIANT(ITEM) \
	33	{ \
	34	const gfx_idx item_idx = MEM_GET_INDEX(ITEM).val; \
	35	assert((ITEM)->prev.val != item_idx); \
	36	assert((ITEM)->next.val != item_idx); \
	37	}
	38
	39	/// Assert the tree node invariant.
	40	///
	41	/// - A node does not point to itself.
	42	/// - The node's left and right siblings cannot be equal, unless both are 0.
	43	/// - The node's left/right sibling cannot be its child, unless both are 0.
	44	/// - The node's parent cannot be the node's child or sibling, unless it's 0.
	45	/// - If the node has a parent and the node is the leftmost sibling, then the
	46	/// parent's child is the node.
	47	#define ASSERT_TREE_NODE_INVARIANT(ITEM) \
	48	{ \
	49	const gfx_idx item_idx = MEM_GET_INDEX(ITEM).val; \
	50	assert((ITEM)->prev.val != item_idx); \
	51	assert((ITEM)->next.val != item_idx); \
	52	if ((ITEM)->prev.val) { \
	53	assert((ITEM)->prev.val != (ITEM)->next.val); \
	54	} \
	55	if ((ITEM)->child.val) { \
	56	assert((ITEM)->child.val != (ITEM)->prev.val); \
	57	assert((ITEM)->child.val != (ITEM)->next.val); \
	58	} \
	59	assert((ITEM)->parent.val != item_idx); \
	60	if ((ITEM)->parent.val && !(ITEM)->prev.val) { \
	61	assert((ITEM)->parent.val != (ITEM)->prev.val); \
	62	assert((ITEM)->parent.val != (ITEM)->next.val); \
	63	const __typeof__(ITEM) item_parent = MEM_GET((ITEM)->parent); \
	64	assert(item_parent->child.val == item_idx); \
	65	} \
	66	}
	67
	68	/// Prepend an item to a list.
	69	/// Modify HEAD_INDEX to equal the index of the new head.
	70	#define LIST_PREPEND(HEAD_INDEX, ITEM) \
	71	(ITEM)->next = HEAD_INDEX; \
	72	if (HEAD_INDEX.val) { \
	73	__typeof__(ITEM) old_head = MEM_GET(HEAD_INDEX); \
	74	old_head->prev = MEM_GET_INDEX(ITEM); \
	75	} \
	76	HEAD_INDEX = MEM_GET_INDEX(ITEM); \
	77	ASSERT_LIST_NODE_INVARIANT(ITEM);
	78
	79	/// Disconnect an item from its siblings.
	80	#define LIST_REMOVE(ITEM) \
	81	if ((ITEM)->prev.val) { \
	82	__typeof__(ITEM) prev_sibling = MEM_GET((ITEM)->prev); \
	83	prev_sibling->next = (ITEM)->next; \
	84	} \
	85	if ((ITEM)->next.val) { \
	86	__typeof__(ITEM) next_sibling = MEM_GET((ITEM)->next); \
	87	next_sibling->prev = (ITEM)->prev; \
	88	} \
	89	(ITEM)->prev.val = 0; \
	90	(ITEM)->next.val = 0; \
	91	ASSERT_LIST_NODE_INVARIANT(ITEM);
	92
	93	/// Set the child's parent.
	94	///
	95	/// The hierarchy is a strict tree hierarchy and a parent node points to its
	96	/// first/leftmost child only. To add a new child, the new child becomes the
	97	/// leftmost node in the list of siblings, the one that the parent then points
	98	/// to.
	99	///
	100	/// The child is also completely disconnected from its previous hierarchy. This
	101	/// is because siblings in a hierarchy must all point to the same parent.
	102	#define SET_PARENT(CHILD, PARENT) \
	103	assert(CHILD); \
	104	assert(CHILD != PARENT); \
	105	ASSERT_TREE_NODE_INVARIANT(CHILD); \
	106	ASSERT_TREE_NODE_INVARIANT(PARENT); \
	107	TREE_REMOVE(CHILD); /* Disconnect CHILD from its previous hierarchy. */ \
	108	if (PARENT) { \
	109	LIST_PREPEND((PARENT)->child, CHILD); \
	110	(CHILD)->parent = MEM_GET_INDEX(PARENT); \
	111	} else { \
	112	(CHILD)->parent.val = 0; \
	113	} \
	114	ASSERT_TREE_NODE_INVARIANT(CHILD); \
	115	if (PARENT) { \
	116	ASSERT_TREE_NODE_INVARIANT(PARENT); \
	117	}
	118
	119	/// Remove an item from its hierarchy.
	120	///
	121	/// The item is disconnected from its parents and siblings. The hierarchy rooted
	122	/// under the item remains intact.
	123	#define TREE_REMOVE(ITEM) \
	124	assert(ITEM); \
	125	if ((ITEM)->parent.val) { \
	126	/* The parent points only to its first/leftmost child. If this item is */ \
	127	/* the leftmost sibling, then we need to rewire the parent to point to */ \
	128	/* the next sibling to keep the parent connected to its children. */ \
	129	__typeof__(ITEM) parent = MEM_GET((ITEM)->parent); \
	130	const __typeof__(ITEM) parent_child = MEM_GET(parent->child); \
	131	if (parent_child == ITEM) { \
	132	assert((ITEM)->prev.val == 0); \
	133	parent->child = (ITEM)->next; \
	134	} \
	135	} \
	136	(ITEM)->parent.val = 0; \
	137	LIST_REMOVE(ITEM); /* Disconnect ITEM from its siblings. */ \
	138	ASSERT_TREE_NODE_INVARIANT(ITEM);