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 <stdint.h>
11
#include <string.h>
12

13
#include "lv_ll.h"
14
#include "lv_mem.h"
15

16
/*********************
17
 *      DEFINES
18
 *********************/
19
#define LL_NODE_META_SIZE (sizeof(lv_ll_node_t*) + sizeof(lv_ll_node_t*))
20
#define LL_PREV_P_OFFSET(ll_p) (ll_p->n_size)
21
#define LL_NEXT_P_OFFSET(ll_p) (ll_p->n_size + sizeof(lv_ll_node_t*))
22

23
/**********************
24
 *      TYPEDEFS
25
 **********************/
26

27
/**********************
28
 *  STATIC PROTOTYPES
29
 **********************/
30
static void node_set_prev(lv_ll_t * ll_p, lv_ll_node_t * act, lv_ll_node_t * prev);
31
static void node_set_next(lv_ll_t * ll_p, lv_ll_node_t * act, lv_ll_node_t * next);
32

33
/**********************
34
 *  STATIC VARIABLES
35
 **********************/
36

37
/**********************
38
 *      MACROS
39
 **********************/
40

41
/**********************
42
 *   GLOBAL FUNCTIONS
43
 **********************/
44

45
/**
46
 * Initialize linked list
47
 * @param ll_dsc pointer to ll_dsc variable
48
 * @param node_size the size of 1 node in bytes
49
 */
50
void lv_ll_init(lv_ll_t * ll_p, uint32_t node_size)
51
{
52
    ll_p->head = NULL;
53
    ll_p->tail = NULL;
54
#ifdef LV_MEM_ENV64
55
    /*Round the size up to 8*/
56
    if(node_size & 0x7) {
57
        node_size = node_size & (~0x7);
58
        node_size += 8;
59
    }
60
#else
61
    /*Round the size up to 4*/
62
    if(node_size & 0x3) {
63
        node_size = node_size & (~0x3);
64
        node_size += 4;
65
    }
66
#endif
67

68
    ll_p->n_size = node_size;
69
}
70

71
/**
72
 * Add a new head to a linked list
73
 * @param ll_p pointer to linked list
74
 * @return pointer to the new head
75
 */
76
void * lv_ll_ins_head(lv_ll_t * ll_p)
77
{
78
    lv_ll_node_t * n_new;
79

80
    n_new = lv_mem_alloc(ll_p->n_size + LL_NODE_META_SIZE);
81

82
    if(n_new != NULL) {
83
        node_set_prev(ll_p, n_new, NULL);           /*No prev. before the new head*/
84
        node_set_next(ll_p, n_new, ll_p->head);     /*After new comes the old head*/
85

86
        if(ll_p->head != NULL) { /*If there is old head then before it goes the new*/
87
            node_set_prev(ll_p, ll_p->head, n_new);
88
        }
89

90
        ll_p->head = n_new;         /*Set the new head in the dsc.*/
91
        if(ll_p->tail == NULL) {/*If there is no tail (1. node) set the tail too*/
92
            ll_p->tail = n_new;
93
        }
94
    }
95

96
    return n_new;
97
}
98

99
/**
100
 * Insert a new node in front of the n_act node
101
 * @param ll_p pointer to linked list
102
 * @param n_act pointer a node
103
 * @return pointer to the new head
104
 */
105
void * lv_ll_ins_prev(lv_ll_t * ll_p, void * n_act)
106
{
107
    lv_ll_node_t * n_new;
108
    lv_ll_node_t * n_prev;
109

110
    if(NULL == ll_p || NULL == n_act) return NULL;
111

112
    if(lv_ll_get_head(ll_p) == n_act) {
113
        n_new = lv_ll_ins_head(ll_p);
114
        if(n_new == NULL) return NULL;
115
    } else {
116
        n_new = lv_mem_alloc(ll_p->n_size + LL_NODE_META_SIZE);
117
        if(n_new == NULL) return NULL;
118

119
        n_prev = lv_ll_get_prev(ll_p, n_act);
120
        node_set_next(ll_p, n_prev, n_new);
121
        node_set_prev(ll_p, n_new, n_prev);
122
        node_set_prev(ll_p, n_act, n_new);
123
        node_set_next(ll_p, n_new, n_act);
124
    }
125

126
    return n_new;
127
}
128

129
/**
130
 * Add a new tail to a linked list
131
 * @param ll_p pointer to linked list
132
 * @return pointer to the new tail
133
 */
134
void * lv_ll_ins_tail(lv_ll_t * ll_p)
135
{
136
    lv_ll_node_t * n_new;
137

138
    n_new = lv_mem_alloc(ll_p->n_size + LL_NODE_META_SIZE);
139
    if(n_new == NULL) return NULL;
140

141
    if(n_new != NULL) {
142
        node_set_next(ll_p, n_new, NULL); /*No next after the new tail*/
143
        node_set_prev(ll_p, n_new, ll_p->tail); /*The prev. before new is tho old tail*/
144
        if(ll_p->tail != NULL) {    /*If there is old tail then the new comes after it*/
145
            node_set_next(ll_p, ll_p->tail, n_new);
146
        }
147

148
        ll_p->tail = n_new;      /*Set the new tail in the dsc.*/
149
        if(ll_p->head == NULL) { /*If there is no head (1. node) set the head too*/
150
            ll_p->head = n_new;
151
        }
152
    }
153

154
    return n_new;
155
}
156

157

158
/**
159
 * Remove the node 'node_p' from 'll_p' linked list.
160
 * It does not free the the memory of node.
161
 * @param ll_p pointer to the linked list of 'node_p'
162
 * @param node_p pointer to node in 'll_p' linked list
163
 */
164
void lv_ll_rem(lv_ll_t  * ll_p, void * node_p)
165
{
166
    if(lv_ll_get_head(ll_p) == node_p) {
167
        /*The new head will be the node after 'n_act'*/
168
        ll_p->head = lv_ll_get_next(ll_p, node_p);
169
        if(ll_p->head == NULL) {
170
            ll_p->tail = NULL;
171
        } else {
172
            node_set_prev(ll_p, ll_p->head, NULL);
173
        }
174
    } else if(lv_ll_get_tail(ll_p) == node_p) {
175
        /*The new tail will be the  node before 'n_act'*/
176
        ll_p->tail = lv_ll_get_prev(ll_p, node_p);
177
        if(ll_p->tail == NULL) {
178
            ll_p->head = NULL;
179
        } else {
180
            node_set_next(ll_p, ll_p->tail, NULL);
181
        }
182
    } else {
183
        lv_ll_node_t * n_prev = lv_ll_get_prev(ll_p, node_p);
184
        lv_ll_node_t * n_next = lv_ll_get_next(ll_p, node_p);
185

186
        node_set_next(ll_p, n_prev, n_next);
187
        node_set_prev(ll_p, n_next, n_prev);
188
    }
189
}
190

191
/**
192
 * Remove and free all elements from a linked list. The list remain valid but become empty.
193
 * @param ll_p pointer to linked list
194
 */
195
void lv_ll_clear(lv_ll_t * ll_p)
196
{
197
    void * i;
198
    void * i_next;
199

200
    i = lv_ll_get_head(ll_p);
201
    i_next = NULL;
202

203
    while(i != NULL) {
204
        i_next = lv_ll_get_next(ll_p, i);
205

206
        lv_ll_rem(ll_p, i);
207
        lv_mem_free(i);
208

209
        i = i_next;
210
    }
211
}
212

213
/**
214
 * Move a node to a new linked list
215
 * @param ll_ori_p pointer to the original (old) linked list
216
 * @param ll_new_p pointer to the new linked list
217
 * @param node pointer to a node
218
 * @return head changed
219
 */
220
bool lv_ll_chg_list(lv_ll_t * ll_ori_p, lv_ll_t * ll_new_p, void * node)
221
{
222
    bool changed = ll_new_p->head != node;
223

224
    lv_ll_rem(ll_ori_p, node);
225

226
    /*Set node as head*/
227
    node_set_prev(ll_new_p, node, NULL);
228
    node_set_next(ll_new_p, node, ll_new_p->head);
229

230
    if(ll_new_p->head != NULL) { /*If there is old head then before it goes the new*/
231
        node_set_prev(ll_new_p, ll_new_p->head, node);
232
    }
233

234
    ll_new_p->head = node;        /*Set the new head in the dsc.*/
235
    if(ll_new_p->tail == NULL) {     /*If there is no tail (first node) set the tail too*/
236
        ll_new_p->tail = node;
237
    }
238

239
    return changed;
240
}
241

242
/**
243
 * Return with head node of the linked list
244
 * @param ll_p pointer to linked list
245
 * @return pointer to the head of 'll_p'
246
 */
247
void * lv_ll_get_head(const lv_ll_t * ll_p)
248
{
249
    void * head = NULL;
250

251
    if(ll_p != NULL)    {
252
        head = ll_p->head;
253
    }
254

255
    return head;
256
}
257

258
/**
259
 * Return with tail node of the linked list
260
 * @param ll_p pointer to linked list
261
 * @return pointer to the head of 'll_p'
262
 */
263
void * lv_ll_get_tail(const lv_ll_t * ll_p)
264
{
265
    void * tail = NULL;
266

267
    if(ll_p != NULL)    {
268
        tail = ll_p->tail;
269
    }
270

271
    return tail;
272
}
273

274
/**
275
 * Return with the pointer of the next node after 'n_act'
276
 * @param ll_p pointer to linked list
277
 * @param n_act pointer a node
278
 * @return pointer to the next node
279
 */
280
void * lv_ll_get_next(const lv_ll_t * ll_p, const  void * n_act)
281
{
282
    void * next = NULL;
283

284
    if(ll_p != NULL)    {
285
        const lv_ll_node_t * n_act_d = n_act;
286
        memcpy(&next, n_act_d + LL_NEXT_P_OFFSET(ll_p), sizeof(void *));
287
    }
288

289
    return next;
290
}
291

292
/**
293
 * Return with the pointer of the previous node after 'n_act'
294
 * @param ll_p pointer to linked list
295
 * @param n_act pointer a node
296
 * @return pointer to the previous node
297
 */
298
void * lv_ll_get_prev(const lv_ll_t * ll_p, const  void * n_act)
299
{
300
    void * prev = NULL;
301

302
    if(ll_p != NULL) {
303
        const lv_ll_node_t * n_act_d = n_act;
304
        memcpy(&prev, n_act_d + LL_PREV_P_OFFSET(ll_p), sizeof(void *));
305
    }
306

307
    return prev;
308
}
309

310
void lv_ll_swap(lv_ll_t * ll_p, void * n1_p, void * n2_p)
311
{
312
    (void)(ll_p);
313
    (void)(n1_p);
314
    (void)(n2_p);
315
    /*TODO*/
316
}
317

318
/**
319
 * Move a nodw before an other node in the same linked list
320
 * @param ll_p pointer to a linked list
321
 * @param n_act pointer to node to move
322
 * @param n_after pointer to a node which should be after `n_act`
323
 */
324
void lv_ll_move_before(lv_ll_t * ll_p, void * n_act, void * n_after)
325
{
326
    if(n_act == n_after) return;    /*Can't move before itself*/
327

328

329
    void * n_before;
330
    if(n_after != NULL) n_before = lv_ll_get_prev(ll_p, n_after);
331
    else n_before = lv_ll_get_tail(ll_p);        /*if `n_after` is NULL `n_act` should be the new tail*/
332

333
    if(n_act == n_before) return;   /*Already before `n_after`*/
334

335
    /*It's much easier to remove from the list and add again*/
336
    lv_ll_rem(ll_p, n_act);
337

338
    /*Add again by setting the prev. and next nodes*/
339
    node_set_next(ll_p, n_before, n_act);
340
    node_set_prev(ll_p, n_act, n_before);
341
    node_set_prev(ll_p, n_after, n_act);
342
    node_set_next(ll_p, n_act, n_after);
343

344
    /*If `n_act` was moved before NULL then it become the new tail*/
345
    if(n_after == NULL) ll_p->tail = n_act;
346
}
347

348
/**********************
349
 *   STATIC FUNCTIONS
350
 **********************/
351

352
/**
353
 * Set the 'pervious node pointer' of a node
354
 * @param ll_p pointer to linked list
355
 * @param act pointer to a node which prev. node pointer should be set
356
 * @param prev pointer to a node which should be the previous node before 'act'
357
 */
358
static void node_set_prev(lv_ll_t * ll_p, lv_ll_node_t * act, lv_ll_node_t * prev)
359
{
360
    if(act == NULL) return;     /*Can't set the prev node of `NULL`*/
361

362
    uint32_t node_p_size = sizeof(lv_ll_node_t *);
363
    if(prev) memcpy(act + LL_PREV_P_OFFSET(ll_p), &prev, node_p_size);
364
    else memset(act + LL_PREV_P_OFFSET(ll_p), 0, node_p_size);
365
}
366

367
/**
368
 * Set the 'next node pointer' of a node
369
 * @param ll_p pointer to linked list
370
 * @param act pointer to a node which next node pointer should be set
371
 * @param next pointer to a node which should be the next node before 'act'
372
 */
373
static void node_set_next(lv_ll_t * ll_p, lv_ll_node_t * act, lv_ll_node_t * next)
374
{
375
    if(act == NULL) return;     /*Can't set the next node of `NULL`*/
376

377
    uint32_t node_p_size = sizeof(lv_ll_node_t *);
378
    if(next) memcpy(act + LL_NEXT_P_OFFSET(ll_p), &next, node_p_size);
379
    else memset(act + LL_NEXT_P_OFFSET(ll_p), 0, node_p_size);
380
}
381

382

383