1 /* 2 * %CopyrightBegin% 3 * 4 * Copyright Ericsson AB and Kjell Winblad 2019. All Rights Reserved. 5 * 6 * Licensed under the Apache License, Version 2.0 (the "License"); 7 * you may not use this file except in compliance with the License. 8 * You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, software 13 * distributed under the License is distributed on an "AS IS" BASIS, 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 * See the License for the specific language governing permissions and 16 * limitations under the License. 17 * 18 * %CopyrightEnd% 19 */ 20 21 /* 22 * Author: Kjell Winblad 23 */ 24 25 #ifndef YIELDING_C_FUN_LISTS_H 26 #define YIELDING_C_FUN_LISTS_H 27 28 #include <stdlib.h> 29 #include <stdio.h> 30 31 32 #define INIT_LIST(L) \ 33 do{ \ 34 (L)->head = NULL; \ 35 (L)->last = NULL; \ 36 }while(0) 37 38 #define APPEND_LIST(L,E) \ 39 do{ \ 40 void* e = E; \ 41 if((L)->head == NULL){ \ 42 (L)->head = e; \ 43 } else { \ 44 (L)->last->next = e; \ 45 } \ 46 (L)->last = e; \ 47 }while(0) 48 49 #define PREPEND_LIST(T,L,E) \ 50 do{ \ 51 T* e = E; \ 52 if((L)->head == NULL){ \ 53 (L)->last = e; \ 54 } else { \ 55 e->next = (L)->head; \ 56 } \ 57 (L)->head = e; \ 58 }while(0) 59 60 #define CONCAT_LIST(T,L1,L2) \ 61 do{ \ 62 T* current = (L2)->head; \ 63 while(current != NULL){ \ 64 APPEND_LIST(L1, current); \ 65 current = current->next; \ 66 } \ 67 }while(0) 68 69 #define PRINT_LIST(T,L, NAME) \ 70 do{ \ 71 printf("NAME %s\n", NAME); \ 72 printf("HEAD %p\n", (L)->head); \ 73 printf("LAST %p\n", (L)->last); \ 74 printf("ELEMS:\n"); \ 75 T* current = (L)->head; \ 76 while(current != NULL){ \ 77 printf("E: %p\n", current); \ 78 current = current->next; \ 79 } \ 80 }while(0) 81 82 #define REMOVE_LIST(T,L,E) \ 83 do{ \ 84 T* prev = NULL; \ 85 T* rl_current = (L)->head; \ 86 T* e = E; \ 87 while(rl_current != e && rl_current != NULL){ \ 88 prev = rl_current ; \ 89 rl_current = rl_current ->next; \ 90 } \ 91 if(rl_current == NULL){ \ 92 exit(1); \ 93 } \ 94 if(prev == NULL){ \ 95 if((L)->head == (L)->last){ \ 96 (L)->last = NULL; \ 97 } \ 98 (L)->head = (L)->head->next; \ 99 }else{ \ 100 if(rl_current == (L)->last){ \ 101 (L)->last = prev; \ 102 } \ 103 prev->next = rl_current ->next; \ 104 } \ 105 }while(0) 106 107 #define INSERT_AFTER_LIST(T,L,E,TO_INSERT) \ 108 do{ \ 109 T* current_y = (L)->head; \ 110 T* elem_x = E; \ 111 T* to_insert2 = TO_INSERT; \ 112 if(elem_x == NULL){ \ 113 PREPEND_LIST(T,L,to_insert2); \ 114 break; \ 115 }else if(elem_x == (L)->last){ \ 116 APPEND_LIST(L,to_insert2); \ 117 break; \ 118 } \ 119 while(current_y != elem_x && current_y != NULL){ \ 120 current_y = current_y->next; \ 121 } \ 122 if(current_y == NULL){ \ 123 printf("CANNOT INSERT AFTER NONEXISTING\n"); \ 124 exit(1); \ 125 } \ 126 to_insert2->next = current_y->next; \ 127 current_y->next = to_insert2; \ 128 }while(0) 129 130 #define INSERT_BEFORE_LIST(T,L,E_BEFORE,TO_INSERT) \ 131 do{ \ 132 T* prev_x = NULL; \ 133 T* current_x = (L)->head; \ 134 T* to_insert_x = TO_INSERT; \ 135 T* e_before_x = E_BEFORE; \ 136 while(current_x != e_before_x && current_x != NULL){ \ 137 prev_x = current_x; \ 138 current_x = current_x->next; \ 139 } \ 140 if(current_x == NULL){ \ 141 printf("CANNOT INSERT AFTER NONEXISTING\n"); \ 142 exit(1); \ 143 } \ 144 INSERT_AFTER_LIST(T,L,prev_x,to_insert_x); \ 145 }while(0) 146 147 148 #define REPLACE_LIST(T,L,OLD,NEW) \ 149 do{ \ 150 T* old = OLD; \ 151 T* new = NEW; \ 152 T* prev_old_next = old->next; \ 153 INSERT_AFTER_LIST(T,L,old,new); \ 154 REMOVE_LIST(T,L,old); \ 155 old->next = prev_old_next; \ 156 }while(0) 157 158 159 /* list functions */ 160 161 #define GENERATE_LIST_FUNCTIONS(NODE_TYPE) \ 162 \ 163 NODE_TYPE##_list NODE_TYPE##_list_empty(){ \ 164 NODE_TYPE##_list list; \ 165 INIT_LIST(&list); \ 166 return list; \ 167 } \ 168 \ 169 NODE_TYPE* NODE_TYPE##_shallow_copy(NODE_TYPE* n){ \ 170 NODE_TYPE* new = ycf_malloc(sizeof(NODE_TYPE)); \ 171 *new = *n; \ 172 new->next = NULL; \ 173 return new; \ 174 } \ 175 \ 176 NODE_TYPE##_list NODE_TYPE##_list_shallow_copy(NODE_TYPE##_list n){ \ 177 NODE_TYPE##_list new; \ 178 NODE_TYPE* current = n.head; \ 179 INIT_LIST(&new); \ 180 while(current != NULL){ \ 181 APPEND_LIST(&new, NODE_TYPE##_shallow_copy(current)); \ 182 current = current->next; \ 183 } \ 184 return new; \ 185 } \ 186 \ 187 int NODE_TYPE##_list_get_item_position(NODE_TYPE##_list* list, NODE_TYPE* node){ \ 188 NODE_TYPE* current = list->head; \ 189 int pos = 0; \ 190 while(current != NULL){ \ 191 if(current == node){ \ 192 return pos; \ 193 } \ 194 pos = pos + 1; \ 195 current = current->next; \ 196 } \ 197 return -1; \ 198 } \ 199 \ 200 NODE_TYPE* NODE_TYPE##_list_get_item_at_position(NODE_TYPE##_list* list, int pos){ \ 201 NODE_TYPE* current = list->head; \ 202 int current_pos = 0; \ 203 while(current != NULL){ \ 204 if(current_pos == pos){ \ 205 return current; \ 206 } \ 207 current_pos = current_pos + 1; \ 208 current = current->next; \ 209 } \ 210 return NULL; \ 211 } \ 212 \ 213 void NODE_TYPE##_list_append(NODE_TYPE##_list* list, NODE_TYPE* node){ \ 214 APPEND_LIST(list, node); \ 215 } \ 216 \ 217 NODE_TYPE##_list NODE_TYPE##_list_copy_append(NODE_TYPE##_list list, NODE_TYPE* node){ \ 218 NODE_TYPE##_list list_copy = NODE_TYPE##_list_shallow_copy(list); \ 219 NODE_TYPE* node_copy = NODE_TYPE##_shallow_copy(node); \ 220 NODE_TYPE##_list_append(&list_copy, node_copy); \ 221 return list_copy; \ 222 } \ 223 \ 224 void NODE_TYPE##_list_prepend(NODE_TYPE##_list* list, NODE_TYPE* node){ \ 225 PREPEND_LIST(NODE_TYPE, list, node); \ 226 } \ 227 \ 228 NODE_TYPE##_list NODE_TYPE##_list_copy_prepend(NODE_TYPE##_list list, NODE_TYPE* node){ \ 229 NODE_TYPE##_list list_copy = NODE_TYPE##_list_shallow_copy(list); \ 230 NODE_TYPE* node_copy = NODE_TYPE##_shallow_copy(node); \ 231 NODE_TYPE##_list_prepend(&list_copy, node_copy); \ 232 return list_copy; \ 233 } \ 234 \ 235 void NODE_TYPE##_list_insert_before(NODE_TYPE##_list* list, NODE_TYPE* before_this, NODE_TYPE* to_insert_z){ \ 236 INSERT_BEFORE_LIST(NODE_TYPE, list, before_this, to_insert_z); \ 237 } \ 238 \ 239 NODE_TYPE##_list NODE_TYPE##_list_copy_insert_before(NODE_TYPE##_list list, NODE_TYPE* before_this, NODE_TYPE* to_insert){ \ 240 int pos = NODE_TYPE##_list_get_item_position(&list, before_this); \ 241 NODE_TYPE##_list list_copy = NODE_TYPE##_list_shallow_copy(list);; \ 242 NODE_TYPE* actual_this = NODE_TYPE##_list_get_item_at_position(&list_copy, pos); \ 243 NODE_TYPE* to_insert_copy = NODE_TYPE##_shallow_copy(to_insert); \ 244 NODE_TYPE##_list_insert_before(&list_copy, actual_this, to_insert_copy); \ 245 return list_copy; \ 246 } \ 247 \ 248 void NODE_TYPE##_list_insert_after(NODE_TYPE##_list* list, NODE_TYPE* after_this, NODE_TYPE* to_insert_z){ \ 249 INSERT_AFTER_LIST(NODE_TYPE, list, after_this, to_insert_z); \ 250 } \ 251 \ 252 NODE_TYPE##_list NODE_TYPE##_list_copy_insert_after(NODE_TYPE##_list list, NODE_TYPE* after_this, NODE_TYPE* to_insert){ \ 253 int pos = NODE_TYPE##_list_get_item_position(&list, after_this); \ 254 NODE_TYPE##_list list_copy = NODE_TYPE##_list_shallow_copy(list); \ 255 NODE_TYPE* actual_this = NODE_TYPE##_list_get_item_at_position(&list_copy, pos); \ 256 NODE_TYPE* to_insert_copy = NODE_TYPE##_shallow_copy(to_insert); \ 257 NODE_TYPE##_list_insert_after(&list_copy, actual_this, to_insert_copy); \ 258 return list_copy; \ 259 } \ 260 \ 261 void NODE_TYPE##_list_remove(NODE_TYPE##_list* list, NODE_TYPE* to_remove){ \ 262 REMOVE_LIST(NODE_TYPE, list, to_remove); \ 263 } \ 264 \ 265 NODE_TYPE##_list NODE_TYPE##_list_copy_remove(NODE_TYPE##_list list, NODE_TYPE* to_remove){ \ 266 int pos = NODE_TYPE##_list_get_item_position(&list, to_remove); \ 267 NODE_TYPE##_list list_copy = NODE_TYPE##_list_shallow_copy(list); \ 268 NODE_TYPE* actual_this = NODE_TYPE##_list_get_item_at_position(&list_copy, pos); \ 269 NODE_TYPE##_list_remove(&list_copy, actual_this); \ 270 return list_copy; \ 271 } \ 272 \ 273 void NODE_TYPE##_list_replace(NODE_TYPE##_list* list, NODE_TYPE* to_replace, NODE_TYPE* replace_with){ \ 274 REPLACE_LIST(NODE_TYPE, list, to_replace, replace_with); \ 275 } \ 276 \ 277 NODE_TYPE##_list NODE_TYPE##_list_copy_replace(NODE_TYPE##_list list, NODE_TYPE* to_replace, NODE_TYPE* replace_with){ \ 278 int pos = NODE_TYPE##_list_get_item_position(&list, to_replace); \ 279 NODE_TYPE##_list list_copy = NODE_TYPE##_list_shallow_copy(list); \ 280 NODE_TYPE* actual_this = NODE_TYPE##_list_get_item_at_position(&list_copy, pos); \ 281 NODE_TYPE* replace_with_copy = NODE_TYPE##_shallow_copy(replace_with); \ 282 NODE_TYPE##_list_replace(&list_copy, actual_this, replace_with_copy); \ 283 return list_copy; \ 284 } \ 285 \ 286 void NODE_TYPE##_list_concat(NODE_TYPE##_list* list1, NODE_TYPE##_list* list2){ \ 287 CONCAT_LIST(NODE_TYPE, list1, list2); \ 288 } \ 289 NODE_TYPE##_list NODE_TYPE##_list_copy_concat(NODE_TYPE##_list list1, NODE_TYPE##_list list2){ \ 290 NODE_TYPE##_list list1_copy = NODE_TYPE##_list_shallow_copy(list1); \ 291 NODE_TYPE##_list list2_copy = NODE_TYPE##_list_shallow_copy(list2); \ 292 CONCAT_LIST(NODE_TYPE, &list1_copy, &list2_copy); \ 293 return list1_copy; \ 294 } \ 295 \ 296 size_t NODE_TYPE##_list_length(NODE_TYPE##_list list){ \ 297 NODE_TYPE* current = list.head; \ 298 size_t count = 0; \ 299 while(current != NULL){ \ 300 count = count + 1; \ 301 current = current->next; \ 302 } \ 303 return count; \ 304 } 305 306 /* void print_string_list(string_list n){ */ 307 /* string_list_item* current = n.head; */ 308 /* printf("START\n"); */ 309 /* while(current != NULL){ */ 310 /* printf("%s\n", current->str); */ 311 /* current = current->next; */ 312 /* } */ 313 /* printf("END\n"); */ 314 /* } */ 315 316 #endif //YIELDING_C_FUN_LISTS_H 317