1 #pragma once 2 3 #include <assert.h> 4 5 #define _TREE_NODE(type, qual) \ 6 struct { \ 7 qual type *tn_parent; /* parent */ \ 8 qual type *tn_first; /* first child */ \ 9 qual type *tn_last; /* last child */ \ 10 qual type *tn_younger; /* younger sibling */ \ 11 qual type *tn_older; /* older sibling */ \ 12 } 13 #define TREE_NODE(type) _TREE_NODE(struct type,) 14 15 #define _TREE_SCRATCH(type, qual, size) \ 16 union { \ 17 struct { \ 18 qual type *stack[(size)]; \ 19 qual type **sp; \ 20 }; \ 21 struct { \ 22 qual type *queue[(size)]; \ 23 qual type **head; \ 24 qual type **tail; \ 25 }; \ 26 } 27 #define TREE_SCRATCH(type, size) _TREE_SCRATCH(struct type, , size) 28 29 #define TREE_INIT_NODE(elm, field) do { \ 30 (elm)->field.tn_parent = NULL; \ 31 (elm)->field.tn_first = NULL; \ 32 (elm)->field.tn_last = NULL; \ 33 (elm)->field.tn_younger = NULL; \ 34 (elm)->field.tn_older = NULL; \ 35 } while (0) 36 37 #define TREE_INSERT_CHILD(treeelm, elm, field) do { \ 38 (elm)->field.tn_parent = (treeelm); \ 39 if ((treeelm)->field.tn_last != NULL) { \ 40 (treeelm)->field.tn_last->field.tn_younger = (elm); \ 41 (elm)->field.tn_older = (treeelm)->field.tn_last; \ 42 } \ 43 (treeelm)->field.tn_last = (elm); \ 44 if ((treeelm)->field.tn_first == NULL) \ 45 (treeelm)->field.tn_first = (elm); \ 46 } while (0) 47 48 #define TREE_INSERT_YOUNGER(treeelm, elm, field) do { \ 49 (elm)->field.tn_parent = (treeelm)->field.tn_parent; \ 50 if ((treeelm)->field.tn_younger != NULL) { \ 51 (elm)->field.tn_younger = (treeelm)->field.tn_younger; \ 52 (elm)->field.tn_younger->field.tn_older = (elm); \ 53 } \ 54 else if ((treeelm)->field.tn_parent != NULL) \ 55 (treeelm)->field.tn_parent->field.tn_last = (elm); \ 56 (treeelm)->field.tn_younger = (elm); \ 57 (elm)->field.tn_older = (treeelm); \ 58 } while (0) 59 60 #define TREE_INSERT_OLDER(treeelm, elm, field) do { \ 61 (elm)->field.tn_parent = (treeelm)->field.tn_parent; \ 62 if ((treeelm)->field.tn_older != NULL) { \ 63 (elm)->field.tn_older = (treeelm)->field.tn_older; \ 64 (elm)->field.tn_older->field.tn_younger = (elm); \ 65 } \ 66 else if ((treeelm)->field.tn_parent != NULL) \ 67 (treeelm)->field.tn_parent->field.tn_first = (elm); \ 68 (treeelm)->field.tn_older = (elm); \ 69 (elm)->field.tn_younger = (treeelm); \ 70 } while (0) 71 72 #define TREE_DETACH(elm, field) do { \ 73 if ((elm)->field.tn_parent) { \ 74 if ((elm)->field.tn_parent->field.tn_first == (elm)) \ 75 (elm)->field.tn_parent->field.tn_first = (elm)->field.tn_younger; \ 76 if ((elm)->field.tn_parent->field.tn_last == (elm)) \ 77 (elm)->field.tn_parent->field.tn_last = (elm)->field.tn_older; \ 78 } \ 79 if ((elm)->field.tn_younger) \ 80 (elm)->field.tn_younger->field.tn_older = (elm)->field.tn_older; \ 81 if ((elm)->field.tn_older) \ 82 (elm)->field.tn_older->field.tn_younger = (elm)->field.tn_younger; \ 83 (elm)->field.tn_older = (elm)->field.tn_younger = NULL; \ 84 (elm)->field.tn_parent = NULL; \ 85 } while (0) 86 87 #define __TREE_DFS_PUSH(scratch, var) \ 88 (assert(&(scratch)->stack[sizeof((scratch)->stack)] > (scratch)->sp), \ 89 *(++((scratch)->sp)) = (var)) 90 #define __TREE_DFS_POP(scratch) \ 91 (*(((scratch)->sp)--)) 92 93 #define TREE_DFS_FOREACH(var, root, scratch, field) \ 94 for ((scratch)->stack[0] = NULL, (scratch)->sp = (scratch)->stack, \ 95 (var) = (root); (var); \ 96 (var) = (var)->field.tn_first \ 97 ? ((((var)->field.tn_younger && (var) != (root)) \ 98 ? __TREE_DFS_PUSH(scratch, (var)->field.tn_younger) : 0), \ 99 (var)->field.tn_first) \ 100 : ((var)->field.tn_younger && (var) != (root)) \ 101 ? (var)->field.tn_younger : __TREE_DFS_POP(scratch)) 102 103 #define TREE_DFS_FOREACH_SELECTIVE(var, root, scratch, field, sel) \ 104 for ((scratch)->stack[0] = NULL, (scratch)->sp = (scratch)->stack, \ 105 (var) = (root); (sel = true, var); \ 106 (var) = ((sel) && (var)->field.tn_first) \ 107 ? ((((var)->field.tn_younger && (var) != (root)) \ 108 ? __TREE_DFS_PUSH(scratch, (var)->field.tn_younger) : 0), \ 109 (var)->field.tn_first) \ 110 : ((var)->field.tn_younger && (var) != (root)) \ 111 ? (var)->field.tn_younger : __TREE_DFS_POP(scratch)) 112 113 #define __TREE_BFS_ENQUEUE(scratch, var) \ 114 (*(((scratch)->tail)++) = (var)) 115 #define __TREE_BFS_DEQUEUE(scratch) \ 116 (*(((scratch)->head)++)) 117 118 #define TREE_BFS_FOREACH(var, root, scratch, field) \ 119 for ((scratch)->head = (scratch)->tail = (scratch)->queue, \ 120 (var) = (root); (var); \ 121 (var) = (var)->field.tn_first \ 122 ? (var)->field.tn_younger \ 123 ? /* enqueue, the younger */ \ 124 (__TREE_BFS_ENQUEUE(scratch, (var)->field.tn_first), \ 125 (var)->field.tn_younger) \ 126 : (scratch)->head != (scratch)->tail \ 127 ? /* enqueue, dequeue */ \ 128 (__TREE_BFS_ENQUEUE(scratch, (var)->field.tn_first), \ 129 __TREE_BFS_DEQUEUE(scratch)) \ 130 : /* the first */ \ 131 (var)->field.tn_first \ 132 : (var)->field.tn_younger \ 133 ? /* the younger */ \ 134 (var)->field.tn_younger \ 135 : (scratch)->head != (scratch)->tail \ 136 ? /* dequeue */ \ 137 __TREE_BFS_DEQUEUE(scratch) \ 138 : NULL) 139 140 #define TREE_BFS_FOREACH_SELECTIVE(var, root, scratch, field, sel) \ 141 for ((scratch)->head = (scratch)->tail = (scratch)->queue, \ 142 (var) = (root); (sel = true, var); \ 143 (var) = ((sel) && (var)->field.tn_first) \ 144 ? (var)->field.tn_younger \ 145 ? /* enqueue, the younger */ \ 146 (__TREE_BFS_ENQUEUE(scratch, (var)->field.tn_first), \ 147 (var)->field.tn_younger) \ 148 : (scratch)->head != (scratch)->tail \ 149 ? /* enqueue, dequeue */ \ 150 (__TREE_BFS_ENQUEUE(scratch, (var)->field.tn_first), \ 151 __TREE_BFS_DEQUEUE(scratch)) \ 152 : /* the first */ \ 153 (var)->field.tn_first \ 154 : (var)->field.tn_younger \ 155 ? /* the younger */ \ 156 (var)->field.tn_younger \ 157 : (scratch)->head != (scratch)->tail \ 158 ? /* dequeue */ \ 159 __TREE_BFS_DEQUEUE(scratch) \ 160 : NULL) 161 162 #define TREE_FIRSTBORN(ent, field) ((ent)->field.tn_first) 163 #define TREE_LASTBORN(ent, field) ((ent)->field.tn_last) 164 #define TREE_YOUNGER(ent, field) ((ent)->field.tn_younger) 165 #define TREE_OLDER(ent, field) ((ent)->field.tn_older) 166 #define TREE_PARENT(ent, field) ((ent)->field.tn_parent) 167 168