1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
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);
|
