1 /***************************************************************************//**
2 * @file
3 * @brief Single Link List
4 *******************************************************************************
5 * # License
6 * <b>Copyright 2019 Silicon Laboratories Inc. www.silabs.com</b>
7 *******************************************************************************
8 *
9 * SPDX-License-Identifier: Zlib
10 *
11 * The licensor of this software is Silicon Laboratories Inc.
12 *
13 * This software is provided 'as-is', without any express or implied
14 * warranty. In no event will the authors be held liable for any damages
15 * arising from the use of this software.
16 *
17 * Permission is granted to anyone to use this software for any purpose,
18 * including commercial applications, and to alter it and redistribute it
19 * freely, subject to the following restrictions:
20 *
21 * 1. The origin of this software must not be misrepresented; you must not
22 * claim that you wrote the original software. If you use this software
23 * in a product, an acknowledgment in the product documentation would be
24 * appreciated but is not required.
25 * 2. Altered source versions must be plainly marked as such, and must not be
26 * misrepresented as being the original software.
27 * 3. This notice may not be removed or altered from any source distribution.
28 *
29 ******************************************************************************/
30
31 #include "sl_assert.h"
32 #include "sl_slist.h"
33 #include <stdbool.h>
34 #include <stdlib.h>
35 #include <stdint.h>
36
37 /*******************************************************************************
38 ************************** GLOBAL FUNCTIONS *******************************
39 ******************************************************************************/
40
41 /***************************************************************************//**
42 * Initializes a singly-linked list.
43 ******************************************************************************/
sl_slist_init(sl_slist_node_t ** head)44 void sl_slist_init(sl_slist_node_t **head)
45 {
46 *head = 0;
47 }
48
49 /***************************************************************************//**
50 * Add given item at beginning of list.
51 ******************************************************************************/
sl_slist_push(sl_slist_node_t ** head,sl_slist_node_t * item)52 void sl_slist_push(sl_slist_node_t **head,
53 sl_slist_node_t *item)
54 {
55 EFM_ASSERT((item != NULL) && (head != NULL));
56
57 item->node = *head;
58 *head = item;
59 }
60
61 /***************************************************************************//**
62 * Add item at end of list.
63 ******************************************************************************/
sl_slist_push_back(sl_slist_node_t ** head,sl_slist_node_t * item)64 void sl_slist_push_back(sl_slist_node_t **head,
65 sl_slist_node_t *item)
66 {
67 sl_slist_node_t **node_ptr = head;
68
69 EFM_ASSERT((item != NULL) && (head != NULL));
70
71 while (*node_ptr != NULL) {
72 node_ptr = &((*node_ptr)->node);
73 }
74
75 item->node = NULL;
76 *node_ptr = item;
77 }
78
79 /***************************************************************************//**
80 * Removes and returns first element of list.
81 ******************************************************************************/
sl_slist_pop(sl_slist_node_t ** head)82 sl_slist_node_t *sl_slist_pop(sl_slist_node_t **head)
83 {
84 sl_slist_node_t *item;
85
86 EFM_ASSERT(head != NULL);
87
88 item = *head;
89 if (item == NULL) {
90 return (NULL);
91 }
92
93 *head = item->node;
94
95 item->node = NULL;
96
97 return (item);
98 }
99
100 /***************************************************************************//**
101 * Insert item after given item.
102 ******************************************************************************/
sl_slist_insert(sl_slist_node_t * item,sl_slist_node_t * pos)103 void sl_slist_insert(sl_slist_node_t *item,
104 sl_slist_node_t *pos)
105 {
106 EFM_ASSERT((item != NULL) && (pos != NULL));
107
108 item->node = pos->node;
109 pos->node = item;
110 }
111
112 /***************************************************************************//**
113 * Add item at end of list.
114 ******************************************************************************/
sl_slist_join(sl_slist_node_t ** head_list_1,sl_slist_node_t ** head_list_2)115 void sl_slist_join(sl_slist_node_t **head_list_1,
116 sl_slist_node_t **head_list_2)
117 {
118 sl_slist_node_t **node_ptr = head_list_1;
119
120 EFM_ASSERT((head_list_2 != NULL)
121 && (head_list_1 != NULL));
122
123 while (*node_ptr != NULL) {
124 node_ptr = &((*node_ptr)->node);
125 }
126
127 *node_ptr = *head_list_2;
128 *head_list_2 = NULL;
129 }
130
131 /***************************************************************************//**
132 * Remove item from list.
133 ******************************************************************************/
sl_slist_remove(sl_slist_node_t ** head,sl_slist_node_t * item)134 void sl_slist_remove(sl_slist_node_t **head,
135 sl_slist_node_t *item)
136 {
137 sl_slist_node_t **node_ptr;
138
139 EFM_ASSERT((item != NULL) && (head != NULL));
140
141 for (node_ptr = head; *node_ptr != NULL; node_ptr = &((*node_ptr)->node)) {
142 if (*node_ptr == item) {
143 *node_ptr = item->node;
144 item->node = NULL;
145 return;
146 }
147 }
148 }
149
150 /***************************************************************************//**
151 * Sorts list items.
152 ******************************************************************************/
sl_slist_sort(sl_slist_node_t ** head,bool (* cmp_fnct)(sl_slist_node_t * item_l,sl_slist_node_t * item_r))153 void sl_slist_sort(sl_slist_node_t **head,
154 bool (*cmp_fnct)(sl_slist_node_t *item_l,
155 sl_slist_node_t *item_r))
156 {
157 bool swapped;
158 sl_slist_node_t **pp_item_l;
159
160 EFM_ASSERT((head != NULL) && (cmp_fnct != NULL));
161
162 do {
163 swapped = false;
164
165 pp_item_l = head;
166 // Loop until end of list is found.
167 while ((*pp_item_l != NULL) && ((*pp_item_l)->node != NULL)) {
168 sl_slist_node_t *p_item_r = (*pp_item_l)->node;
169 bool ordered;
170
171 // Call provided compare fnct.
172 ordered = cmp_fnct(*pp_item_l, p_item_r);
173 if (ordered == false) {
174 // If order is not correct, swap items.
175 sl_slist_node_t *p_tmp = p_item_r->node;
176
177 // Swap the two items.
178 p_item_r->node = *pp_item_l;
179 (*pp_item_l)->node = p_tmp;
180 *pp_item_l = p_item_r;
181 pp_item_l = &(p_item_r->node);
182 // Indicate a swap has been done.
183 swapped = true;
184 } else {
185 pp_item_l = &((*pp_item_l)->node);
186 }
187 }
188 // Re-loop until no items have been swapped.
189 } while (swapped == true);
190 }
191
