tsiry-sandratraina.com
A modern Music Player Daemon based on Rockbox open source high quality audio player
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
1/***************************************************************************
2 * __________ __ ___.
3 * Open \______ \ ____ ____ | | _\_ |__ _______ ___
4 * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ /
5 * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < <
6 * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \
7 * \/ \/ \/ \/ \/
8 * $Id$
9 *
10 * Copyright (C) 2014 by Michael Sevakis
11 *
12 * This program is free software; you can redistribute it and/or
13 * modify it under the terms of the GNU General Public License
14 * as published by the Free Software Foundation; either version 2
15 * of the License, or (at your option) any later version.
16 *
17 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
18 * KIND, either express or implied.
19 *
20 ****************************************************************************/
21#include <stddef.h>
22#include "linked_list.h"
23
24
25/** (L)inked (L)ist **/
26
27/**
28 * Helper to find the node previous to 'find'
29 *
30 * returns: NULL if 'find' is the first node
31 * last node if the 'find' isn't found in the list
32 */
33static struct ll_node * ll_search_prev(struct ll_head *list,
34 struct ll_node *find)
35{
36 struct ll_node *prev = NULL;
37 struct ll_node *node = list->head;
38
39 while (node != NULL && node != find)
40 {
41 prev = node;
42 node = node->next;
43 }
44
45 return prev;
46}
47
48/**
49 * Adds a node to s singly-linked list using "insert next"
50 */
51void ll_insert_next(struct ll_head *list, struct ll_node *node,
52 struct ll_node *newnode)
53{
54 struct ll_node **nodep = node != NULL ? &node->next : &list->head;
55 struct ll_node *next = *nodep;
56
57 newnode->next = next;
58 *nodep = newnode;
59
60 if (next == NULL)
61 list->tail = newnode;
62}
63
64/**
65 * Adds a node to a singly-linked list using "insert first"
66 */
67void ll_insert_first(struct ll_head *list, struct ll_node *node)
68{
69 struct ll_node *head = list->head;
70
71 node->next = head;
72 list->head = node;
73
74 if (head == NULL)
75 list->tail = node;
76}
77
78/**
79 * Adds a node to a singly-linked list using "insert last"
80 */
81void ll_insert_last(struct ll_head *list, struct ll_node *node)
82{
83 struct ll_node *tail = list->tail;
84
85 node->next = NULL;
86 list->tail = node;
87
88 if (tail == NULL)
89 list->head = node;
90 else
91 tail->next = node;
92}
93
94/**
95 * Removes the node after "node"; if there is none, nothing is changed
96 */
97void ll_remove_next(struct ll_head *list, struct ll_node *node)
98{
99 struct ll_node **nodep = node != NULL ? &node->next : &list->head;
100 struct ll_node *next = *nodep;
101
102 if (next != NULL)
103 {
104 next = next->next;
105 *nodep = next;
106
107 if (next == NULL)
108 list->tail = node;
109 }
110}
111
112/**
113 * Removes the first node in the list
114 */
115void ll_remove_first(struct ll_head *list)
116{
117 struct ll_node *node = list->head->next;
118
119 list->head = node;
120
121 if (node == NULL)
122 list->tail = NULL;
123}
124
125/**
126 * Removes the node from the list
127 */
128void ll_remove(struct ll_head *list, struct ll_node *node)
129{
130 ll_remove_next(list, ll_search_prev(list, node));
131}
132
133
134/** (L)inked (L)ist (D)ouble **/
135
136void lld_insert_next(struct lld_head *list, struct lld_node *node,
137 struct lld_node *newnode)
138{
139 struct lld_node **nodep = node != NULL ? &node->next : &list->head;
140 struct lld_node *next = *nodep;
141
142 newnode->next = next;
143 newnode->prev = node;
144 *nodep = newnode;
145
146 if (next == NULL)
147 list->tail = newnode;
148 else
149 next->prev = newnode;
150}
151
152void lld_insert_prev(struct lld_head *list, struct lld_node *node,
153 struct lld_node *newnode)
154{
155 struct lld_node **nodep = node != NULL ? &node->prev : &list->tail;
156 struct lld_node *prev = *nodep;
157
158 newnode->next = node;
159 newnode->prev = prev;
160 *nodep = newnode;
161
162 if (prev == NULL)
163 list->head = newnode;
164 else
165 prev->next = newnode;
166}
167
168/**
169 * Adds a node to a doubly-linked list using "insert first"
170 */
171void lld_insert_first(struct lld_head *list, struct lld_node *node)
172{
173 struct lld_node *head = list->head;
174
175 list->head = node;
176
177 if (head == NULL)
178 list->tail = node;
179 else
180 head->prev = node;
181
182 node->next = head;
183 node->prev = NULL;
184}
185
186/**
187 * Adds a node to a doubly-linked list using "insert last"
188 */
189void lld_insert_last(struct lld_head *list, struct lld_node *node)
190{
191 struct lld_node *tail = list->tail;
192
193 list->tail = node;
194
195 if (tail == NULL)
196 list->head = node;
197 else
198 tail->next = node;
199
200 node->next = NULL;
201 node->prev = tail;
202}
203
204/**
205 * Removes a node from a doubly-linked list
206 */
207void lld_remove(struct lld_head *list, struct lld_node *node)
208{
209 struct lld_node *next = node->next;
210 struct lld_node *prev = node->prev;
211
212 if (prev == NULL)
213 list->head = next;
214 else
215 prev->next = next;
216
217 if (next == NULL)
218 list->tail = prev;
219 else
220 next->prev = prev;
221}
222
223
224/** (L)inked (L)ist (D)ouble (C)ircular **/
225
226/**
227 * Helper that inserts a node into a doubly-link circular list; does not
228 * affect list->head, just returns its state
229 */
230static inline struct lldc_node * lldc_insert(struct lldc_head *list,
231 struct lldc_node *node)
232{
233 struct lldc_node *head = list->head;
234
235 if (head == NULL)
236 {
237 node->prev = node;
238 node->next = node;
239 }
240 else
241 {
242 node->prev = head->prev;
243 node->next = head;
244 head->prev->next = node;
245 head->prev = node;
246 }
247
248 return head;
249}
250
251/**
252 * Adds a node to a doubly-linked circular list using "insert first"
253 */
254void lldc_insert_first(struct lldc_head *list, struct lldc_node *node)
255{
256 lldc_insert(list, node);
257 list->head = node;
258}
259
260/**
261 * Adds a node to a doubly-linked circular list using "insert last"
262 */
263void lldc_insert_last(struct lldc_head *list, struct lldc_node *node)
264{
265 if (lldc_insert(list, node) == NULL)
266 list->head = node;
267}
268
269/**
270 * Removes a node from a doubly-linked circular list
271 */
272void lldc_remove(struct lldc_head *list, struct lldc_node *node)
273{
274 struct lldc_node *next = node->next;
275
276 if (node == list->head)
277 {
278 if (node == next)
279 {
280 list->head = NULL;
281 return;
282 }
283
284 list->head = next;
285 }
286
287 struct lldc_node *prev = node->prev;
288 next->prev = prev;
289 prev->next = next;
290}