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 }