acid-drop- Hacking the planet from a LilyGo T-Deck using custom firmware |
git clone git://git.acid.vegas/acid-drop.git |
Log | Files | Refs | Archive | README | LICENSE |
lv_ll.c (11419B)
1 /** 2 * @file lv_ll.c 3 * Handle linked lists. 4 * The nodes are dynamically allocated by the 'lv_mem' module, 5 */ 6 7 /********************* 8 * INCLUDES 9 *********************/ 10 #include "lv_ll.h" 11 #include "lv_mem.h" 12 13 /********************* 14 * DEFINES 15 *********************/ 16 #define LL_NODE_META_SIZE (sizeof(lv_ll_node_t *) + sizeof(lv_ll_node_t *)) 17 #define LL_PREV_P_OFFSET(ll_p) (ll_p->n_size) 18 #define LL_NEXT_P_OFFSET(ll_p) (ll_p->n_size + sizeof(lv_ll_node_t *)) 19 20 /********************** 21 * TYPEDEFS 22 **********************/ 23 24 /********************** 25 * STATIC PROTOTYPES 26 **********************/ 27 static void node_set_prev(lv_ll_t * ll_p, lv_ll_node_t * act, lv_ll_node_t * prev); 28 static void node_set_next(lv_ll_t * ll_p, lv_ll_node_t * act, lv_ll_node_t * next); 29 30 /********************** 31 * STATIC VARIABLES 32 **********************/ 33 34 /********************** 35 * MACROS 36 **********************/ 37 38 /********************** 39 * GLOBAL FUNCTIONS 40 **********************/ 41 42 /** 43 * Initialize linked list 44 * @param ll_p pointer to lv_ll_t variable 45 * @param node_size the size of 1 node in bytes 46 */ 47 void _lv_ll_init(lv_ll_t * ll_p, uint32_t node_size) 48 { 49 ll_p->head = NULL; 50 ll_p->tail = NULL; 51 #ifdef LV_ARCH_64 52 /*Round the size up to 8*/ 53 node_size = (node_size + 7) & (~0x7); 54 #else 55 /*Round the size up to 4*/ 56 node_size = (node_size + 3) & (~0x3); 57 #endif 58 59 ll_p->n_size = node_size; 60 } 61 62 /** 63 * Add a new head to a linked list 64 * @param ll_p pointer to linked list 65 * @return pointer to the new head 66 */ 67 void * _lv_ll_ins_head(lv_ll_t * ll_p) 68 { 69 lv_ll_node_t * n_new; 70 71 n_new = lv_mem_alloc(ll_p->n_size + LL_NODE_META_SIZE); 72 73 if(n_new != NULL) { 74 node_set_prev(ll_p, n_new, NULL); /*No prev. before the new head*/ 75 node_set_next(ll_p, n_new, ll_p->head); /*After new comes the old head*/ 76 77 if(ll_p->head != NULL) { /*If there is old head then before it goes the new*/ 78 node_set_prev(ll_p, ll_p->head, n_new); 79 } 80 81 ll_p->head = n_new; /*Set the new head in the dsc.*/ 82 if(ll_p->tail == NULL) { /*If there is no tail (1. node) set the tail too*/ 83 ll_p->tail = n_new; 84 } 85 } 86 87 return n_new; 88 } 89 90 /** 91 * Insert a new node in front of the n_act node 92 * @param ll_p pointer to linked list 93 * @param n_act pointer a node 94 * @return pointer to the new node 95 */ 96 void * _lv_ll_ins_prev(lv_ll_t * ll_p, void * n_act) 97 { 98 lv_ll_node_t * n_new; 99 100 if(NULL == ll_p || NULL == n_act) return NULL; 101 102 if(_lv_ll_get_head(ll_p) == n_act) { 103 n_new = _lv_ll_ins_head(ll_p); 104 if(n_new == NULL) return NULL; 105 } 106 else { 107 n_new = lv_mem_alloc(ll_p->n_size + LL_NODE_META_SIZE); 108 if(n_new == NULL) return NULL; 109 110 lv_ll_node_t * n_prev; 111 n_prev = _lv_ll_get_prev(ll_p, n_act); 112 node_set_next(ll_p, n_prev, n_new); 113 node_set_prev(ll_p, n_new, n_prev); 114 node_set_prev(ll_p, n_act, n_new); 115 node_set_next(ll_p, n_new, n_act); 116 } 117 118 return n_new; 119 } 120 121 /** 122 * Add a new tail to a linked list 123 * @param ll_p pointer to linked list 124 * @return pointer to the new tail 125 */ 126 void * _lv_ll_ins_tail(lv_ll_t * ll_p) 127 { 128 lv_ll_node_t * n_new; 129 130 n_new = lv_mem_alloc(ll_p->n_size + LL_NODE_META_SIZE); 131 132 if(n_new != NULL) { 133 node_set_next(ll_p, n_new, NULL); /*No next after the new tail*/ 134 node_set_prev(ll_p, n_new, ll_p->tail); /*The prev. before new is the old tail*/ 135 if(ll_p->tail != NULL) { /*If there is old tail then the new comes after it*/ 136 node_set_next(ll_p, ll_p->tail, n_new); 137 } 138 139 ll_p->tail = n_new; /*Set the new tail in the dsc.*/ 140 if(ll_p->head == NULL) { /*If there is no head (1. node) set the head too*/ 141 ll_p->head = n_new; 142 } 143 } 144 145 return n_new; 146 } 147 148 /** 149 * Remove the node 'node_p' from 'll_p' linked list. 150 * It does not free the memory of node. 151 * @param ll_p pointer to the linked list of 'node_p' 152 * @param node_p pointer to node in 'll_p' linked list 153 */ 154 void _lv_ll_remove(lv_ll_t * ll_p, void * node_p) 155 { 156 if(ll_p == NULL) return; 157 158 if(_lv_ll_get_head(ll_p) == node_p) { 159 /*The new head will be the node after 'n_act'*/ 160 ll_p->head = _lv_ll_get_next(ll_p, node_p); 161 if(ll_p->head == NULL) { 162 ll_p->tail = NULL; 163 } 164 else { 165 node_set_prev(ll_p, ll_p->head, NULL); 166 } 167 } 168 else if(_lv_ll_get_tail(ll_p) == node_p) { 169 /*The new tail will be the node before 'n_act'*/ 170 ll_p->tail = _lv_ll_get_prev(ll_p, node_p); 171 if(ll_p->tail == NULL) { 172 ll_p->head = NULL; 173 } 174 else { 175 node_set_next(ll_p, ll_p->tail, NULL); 176 } 177 } 178 else { 179 lv_ll_node_t * n_prev = _lv_ll_get_prev(ll_p, node_p); 180 lv_ll_node_t * n_next = _lv_ll_get_next(ll_p, node_p); 181 182 node_set_next(ll_p, n_prev, n_next); 183 node_set_prev(ll_p, n_next, n_prev); 184 } 185 } 186 187 /** 188 * Remove and free all elements from a linked list. The list remain valid but become empty. 189 * @param ll_p pointer to linked list 190 */ 191 void _lv_ll_clear(lv_ll_t * ll_p) 192 { 193 void * i; 194 void * i_next; 195 196 i = _lv_ll_get_head(ll_p); 197 i_next = NULL; 198 199 while(i != NULL) { 200 i_next = _lv_ll_get_next(ll_p, i); 201 202 _lv_ll_remove(ll_p, i); 203 lv_mem_free(i); 204 205 i = i_next; 206 } 207 } 208 209 /** 210 * Move a node to a new linked list 211 * @param ll_ori_p pointer to the original (old) linked list 212 * @param ll_new_p pointer to the new linked list 213 * @param node pointer to a node 214 * @param head true: be the head in the new list 215 * false be the tail in the new list 216 */ 217 void _lv_ll_chg_list(lv_ll_t * ll_ori_p, lv_ll_t * ll_new_p, void * node, bool head) 218 { 219 _lv_ll_remove(ll_ori_p, node); 220 221 if(head) { 222 /*Set node as head*/ 223 node_set_prev(ll_new_p, node, NULL); 224 node_set_next(ll_new_p, node, ll_new_p->head); 225 226 if(ll_new_p->head != NULL) { /*If there is old head then before it goes the new*/ 227 node_set_prev(ll_new_p, ll_new_p->head, node); 228 } 229 230 ll_new_p->head = node; /*Set the new head in the dsc.*/ 231 if(ll_new_p->tail == NULL) { /*If there is no tail (first node) set the tail too*/ 232 ll_new_p->tail = node; 233 } 234 } 235 else { 236 /*Set node as tail*/ 237 node_set_prev(ll_new_p, node, ll_new_p->tail); 238 node_set_next(ll_new_p, node, NULL); 239 240 if(ll_new_p->tail != NULL) { /*If there is old tail then after it goes the new*/ 241 node_set_next(ll_new_p, ll_new_p->tail, node); 242 } 243 244 ll_new_p->tail = node; /*Set the new tail in the dsc.*/ 245 if(ll_new_p->head == NULL) { /*If there is no head (first node) set the head too*/ 246 ll_new_p->head = node; 247 } 248 } 249 } 250 251 /** 252 * Return with head node of the linked list 253 * @param ll_p pointer to linked list 254 * @return pointer to the head of 'll_p' 255 */ 256 void * _lv_ll_get_head(const lv_ll_t * ll_p) 257 { 258 if(ll_p == NULL) return NULL; 259 return ll_p->head; 260 } 261 262 /** 263 * Return with tail node of the linked list 264 * @param ll_p pointer to linked list 265 * @return pointer to the tail of 'll_p' 266 */ 267 void * _lv_ll_get_tail(const lv_ll_t * ll_p) 268 { 269 if(ll_p == NULL) return NULL; 270 return ll_p->tail; 271 } 272 273 /** 274 * Return with the pointer of the next node after 'n_act' 275 * @param ll_p pointer to linked list 276 * @param n_act pointer a node 277 * @return pointer to the next node 278 */ 279 void * _lv_ll_get_next(const lv_ll_t * ll_p, const void * n_act) 280 { 281 /*Pointer to the next node is stored in the end of this node. 282 *Go there and return the address found there*/ 283 const lv_ll_node_t * n_act_d = n_act; 284 n_act_d += LL_NEXT_P_OFFSET(ll_p); 285 return *((lv_ll_node_t **)n_act_d); 286 } 287 288 /** 289 * Return with the pointer of the previous node before 'n_act' 290 * @param ll_p pointer to linked list 291 * @param n_act pointer a node 292 * @return pointer to the previous node 293 */ 294 void * _lv_ll_get_prev(const lv_ll_t * ll_p, const void * n_act) 295 { 296 /*Pointer to the prev. node is stored in the end of this node. 297 *Go there and return the address found there*/ 298 const lv_ll_node_t * n_act_d = n_act; 299 n_act_d += LL_PREV_P_OFFSET(ll_p); 300 return *((lv_ll_node_t **)n_act_d); 301 } 302 303 /** 304 * Return the length of the linked list. 305 * @param ll_p pointer to linked list 306 * @return length of the linked list 307 */ 308 uint32_t _lv_ll_get_len(const lv_ll_t * ll_p) 309 { 310 uint32_t len = 0; 311 void * node; 312 313 for(node = _lv_ll_get_head(ll_p); node != NULL; node = _lv_ll_get_next(ll_p, node)) { 314 len++; 315 } 316 317 return len; 318 } 319 320 /** 321 * Move a node before an other node in the same linked list 322 * @param ll_p pointer to a linked list 323 * @param n_act pointer to node to move 324 * @param n_after pointer to a node which should be after `n_act` 325 */ 326 void _lv_ll_move_before(lv_ll_t * ll_p, void * n_act, void * n_after) 327 { 328 if(n_act == n_after) return; /*Can't move before itself*/ 329 330 void * n_before; 331 if(n_after != NULL) 332 n_before = _lv_ll_get_prev(ll_p, n_after); 333 else 334 n_before = _lv_ll_get_tail(ll_p); /*if `n_after` is NULL `n_act` should be the new tail*/ 335 336 if(n_act == n_before) return; /*Already before `n_after`*/ 337 338 /*It's much easier to remove from the list and add again*/ 339 _lv_ll_remove(ll_p, n_act); 340 341 /*Add again by setting the prev. and next nodes*/ 342 node_set_next(ll_p, n_before, n_act); 343 node_set_prev(ll_p, n_act, n_before); 344 node_set_prev(ll_p, n_after, n_act); 345 node_set_next(ll_p, n_act, n_after); 346 347 /*If `n_act` was moved before NULL then it become the new tail*/ 348 if(n_after == NULL) ll_p->tail = n_act; 349 350 /*If `n_act` was moved before `NULL` then it's the new head*/ 351 if(n_before == NULL) ll_p->head = n_act; 352 } 353 354 /** 355 * Check if a linked list is empty 356 * @param ll_p pointer to a linked list 357 * @return true: the linked list is empty; false: not empty 358 */ 359 bool _lv_ll_is_empty(lv_ll_t * ll_p) 360 { 361 if(ll_p == NULL) return true; 362 363 if(ll_p->head == NULL && ll_p->tail == NULL) return true; 364 365 return false; 366 } 367 368 /********************** 369 * STATIC FUNCTIONS 370 **********************/ 371 372 /** 373 * Set the previous node pointer of a node 374 * @param ll_p pointer to linked list 375 * @param act pointer to a node which prev. node pointer should be set 376 * @param prev pointer to a node which should be the previous node before 'act' 377 */ 378 static void node_set_prev(lv_ll_t * ll_p, lv_ll_node_t * act, lv_ll_node_t * prev) 379 { 380 if(act == NULL) return; /*Can't set the prev node of `NULL`*/ 381 382 uint8_t * act8 = (uint8_t *)act; 383 384 act8 += LL_PREV_P_OFFSET(ll_p); 385 386 lv_ll_node_t ** act_node_p = (lv_ll_node_t **) act8; 387 lv_ll_node_t ** prev_node_p = (lv_ll_node_t **) &prev; 388 389 *act_node_p = *prev_node_p; 390 } 391 392 /** 393 * Set the 'next node pointer' of a node 394 * @param ll_p pointer to linked list 395 * @param act pointer to a node which next node pointer should be set 396 * @param next pointer to a node which should be the next node before 'act' 397 */ 398 static void node_set_next(lv_ll_t * ll_p, lv_ll_node_t * act, lv_ll_node_t * next) 399 { 400 if(act == NULL) return; /*Can't set the next node of `NULL`*/ 401 uint8_t * act8 = (uint8_t *)act; 402 403 act8 += LL_NEXT_P_OFFSET(ll_p); 404 lv_ll_node_t ** act_node_p = (lv_ll_node_t **) act8; 405 lv_ll_node_t ** next_node_p = (lv_ll_node_t **) &next; 406 407 *act_node_p = *next_node_p; 408 }