am_list.h (7398B)
1 #ifndef AM_LIST_H 2 #define AM_LIST_H 3 4 #define DLL_APPEND_NP(f, l, n, next, prev) \ 5 ((f) == NULL \ 6 ? ((f) = (l) = (n) \ 7 , (f)->prev = (n)->next = NULL) \ 8 : ((n)->prev = (l) \ 9 , (l)->next = (n) \ 10 , (l) = (n) \ 11 , (n)->next = NULL)) 12 13 #define DLL_REMOVE_NP(f, l, n, next, prev) \ 14 ((f) == (l) && (f) == (n) \ 15 ? ((f) = (l) = NULL) \ 16 : ((f) == (n) \ 17 ? ((f) = (f)->next \ 18 , (f)->prev = NULL) \ 19 : ((l) == (n) \ 20 ? ((l) = (l)->prev \ 21 , (l)->next = NULL) \ 22 : ((n)->prev->next = (n)->next \ 23 , (n)->next->prev = (n)->prev)))) 24 25 #define SLL_QUEUE_PUSH_N(f, l, n, next) \ 26 ((f) == NULL \ 27 ? ((f) = (l) = (n)) \ 28 : ((l)->next = (n) \ 29 , (l) = (n) \ 30 , (n)->next = NULL)) 31 32 #define SLL_QUEUE_PUSH_FRONT_N(f, l, n, next) \ 33 ((f) == NULL \ 34 ? ((f) = (l) = (n) \ 35 , (n)->next = NULL) \ 36 : ((n)->next = (f) \ 37 , (f) = (n))) 38 39 // TODO: It's maybe somewhat surprising to the user that these pop functions 40 // don't return the popped node. 41 #define SLL_QUEUE_POP_N(f, l, next) \ 42 ((f) == (l) \ 43 ? ((f) = (l) = NULL) \ 44 : ((f) = (f)->next)) 45 46 47 #define SLL_STACK_PUSH_N(f, n, next) ((n)->next = (f), (f) = (n)) 48 49 #define SLL_STACK_POP_N(f, next) \ 50 ((f) == NULL \ 51 ? 0 \ 52 : ((f) = (f)->next)) 53 54 #define DLL_APPEND(f, l, n) DLL_APPEND_NP((f), (l), (n), next, prev) 55 #define DLL_PREPEND(f, l, n) DLL_APPEND_NP((l), (f), (n), prev, next) 56 #define DLL_REMOVE(f, l, n) DLL_REMOVE_NP((f), (l), (n), next, prev) 57 58 #define SLL_QUEUE_PUSH(f, l, n) SLL_QUEUE_PUSH_N((f), (l), (n), next) 59 #define SLL_QUEUE_PUSH_FRONT(f, l, n) SLL_QUEUE_PUSH_FRONT_N((f), (l), (n), next) 60 #define SLL_QUEUE_POP(f, l) SLL_QUEUE_POP_N((f), (l), next) 61 62 #define SLL_STACK_PUSH(f, n) SLL_STACK_PUSH_N((f), (n), next) 63 #define SLL_STACK_POP(f) SLL_STACK_POP_N((f), next) 64 65 #ifdef AM_LIST_TESTS 66 typedef struct TestNode TestNode; 67 struct TestNode { 68 TestNode *next; 69 TestNode *prev; 70 s32 val; 71 }; 72 73 internal void am_list_test(void) { 74 TestNode nodes[10] = {0}; 75 for (size_t i = 0; i < ARRAY_COUNT(nodes); i++) { 76 nodes[i].val = i; 77 } 78 79 { 80 TestNode *first = NULL; 81 TestNode *last = NULL; 82 83 printf("dll append and remove from front\n"); 84 for (size_t i = 0; i < ARRAY_COUNT(nodes); i++) { 85 DLL_APPEND(first, last, &nodes[i]); 86 printf("["); 87 for (TestNode *n = first; n; n = n->next) { 88 printf(" %i ", n->val); 89 } 90 printf(" <|> "); 91 for (TestNode *n = last; n; n = n->prev) { 92 printf(" %i ", n->val); 93 } 94 printf("]\n"); 95 } 96 97 for (size_t i = 0; i < ARRAY_COUNT(nodes); i++) { 98 DLL_REMOVE(first, last, &nodes[i]); 99 printf("["); 100 for (TestNode *n = first; n; n = n->next) { 101 printf(" %i ", n->val); 102 } 103 printf(" <|> "); 104 for (TestNode *n = last; n; n = n->prev) { 105 printf(" %i ", n->val); 106 } 107 printf("]\n"); 108 } 109 110 printf("dll prepend and remove from back\n"); 111 for (size_t i = 0; i < ARRAY_COUNT(nodes); i++) { 112 DLL_PREPEND(first, last, &nodes[i]); 113 printf("["); 114 for (TestNode *n = first; n; n = n->next) { 115 printf(" %i ", n->val); 116 } 117 printf(" <|> "); 118 for (TestNode *n = last; n; n = n->prev) { 119 printf(" %i ", n->val); 120 } 121 printf("]\n"); 122 } 123 124 for (size_t i = 0; i < ARRAY_COUNT(nodes); i++) { 125 DLL_REMOVE(first, last, &nodes[i]); 126 printf("["); 127 for (TestNode *n = first; n; n = n->next) { 128 printf(" %i ", n->val); 129 } 130 printf(" <|> "); 131 for (TestNode *n = last; n; n = n->prev) { 132 printf(" %i ", n->val); 133 } 134 printf("]\n"); 135 } 136 137 printf("dll append and remove from middle\n"); 138 for (size_t i = 0; i < ARRAY_COUNT(nodes); i++) { 139 DLL_APPEND(first, last, &nodes[i]); 140 printf("["); 141 for (TestNode *n = first; n; n = n->next) { 142 printf(" %i ", n->val); 143 } 144 printf(" <|> "); 145 for (TestNode *n = last; n; n = n->prev) { 146 printf(" %i ", n->val); 147 } 148 printf("]\n"); 149 } 150 151 for (size_t i = 0; i < ARRAY_COUNT(nodes); i++) { 152 DLL_REMOVE(first, last, &nodes[(i + (ARRAY_COUNT(nodes) / 2)) % ARRAY_COUNT(nodes)]); 153 printf("["); 154 for (TestNode *n = first; n; n = n->next) { 155 printf(" %i ", n->val); 156 } 157 printf(" <|> "); 158 for (TestNode *n = last; n; n = n->prev) { 159 printf(" %i ", n->val); 160 } 161 printf("]\n"); 162 } 163 } 164 165 { 166 TestNode *first = NULL; 167 TestNode *last = NULL; 168 169 printf("sll queue push and pop\n"); 170 for (size_t i = 0; i < ARRAY_COUNT(nodes); i++) { 171 SLL_QUEUE_PUSH(first, last, &nodes[i]); 172 printf("["); 173 for (TestNode *n = first; n; n = n->next) { 174 printf(" %i ", n->val); 175 } 176 printf("]\n"); 177 } 178 179 while (first) { 180 SLL_QUEUE_POP(first, last); 181 printf("["); 182 for (TestNode *n = first; n; n = n->next) { 183 printf(" %i ", n->val); 184 } 185 printf("]\n"); 186 } 187 188 printf("sll queue push front and pop\n"); 189 for (size_t i = 0; i < ARRAY_COUNT(nodes); i++) { 190 SLL_QUEUE_PUSH_FRONT(first, last, &nodes[i]); 191 printf("["); 192 for (TestNode *n = first; n; n = n->next) { 193 printf(" %i ", n->val); 194 } 195 printf("]\n"); 196 } 197 198 while (first) { 199 SLL_QUEUE_POP(first, last); 200 printf("["); 201 for (TestNode *n = first; n; n = n->next) { 202 printf(" %i ", n->val); 203 } 204 printf("]\n"); 205 } 206 } 207 208 { 209 TestNode *first = NULL; 210 211 printf("sll stack push and pop\n"); 212 for (size_t i = 0; i < ARRAY_COUNT(nodes); i++) { 213 SLL_STACK_PUSH(first, &nodes[i]); 214 printf("["); 215 for (TestNode *n = first; n; n = n->next) { 216 printf(" %i ", n->val); 217 } 218 printf("]\n"); 219 } 220 221 while (first) { 222 SLL_STACK_POP(first); 223 printf("["); 224 for (TestNode *n = first; n; n = n->next) { 225 printf(" %i ", n->val); 226 } 227 printf("]\n"); 228 } 229 } 230 } 231 #endif // AM_LIST_TESTS 232 233 #endif // AM_LIST_H