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 * Remove item from list.
114 ******************************************************************************/
sl_slist_remove(sl_slist_node_t ** head,sl_slist_node_t * item)115 void sl_slist_remove(sl_slist_node_t **head,
116 sl_slist_node_t *item)
117 {
118 sl_slist_node_t **node_ptr;
119
120 EFM_ASSERT((item != NULL) && (head != NULL));
121
122 for (node_ptr = head; *node_ptr != NULL; node_ptr = &((*node_ptr)->node)) {
123 if (*node_ptr == item) {
124 *node_ptr = item->node;
125 return;
126 }
127 }
128
129 EFM_ASSERT(node_ptr != NULL);
130 }
131
132 /***************************************************************************//**
133 * Sorts list items.
134 ******************************************************************************/
sl_slist_sort(sl_slist_node_t ** head,bool (* cmp_fnct)(sl_slist_node_t * item_l,sl_slist_node_t * item_r))135 void sl_slist_sort(sl_slist_node_t **head,
136 bool (*cmp_fnct)(sl_slist_node_t *item_l,
137 sl_slist_node_t *item_r))
138 {
139 bool swapped;
140 sl_slist_node_t **pp_item_l;
141
142 EFM_ASSERT((head != NULL) && (cmp_fnct != NULL));
143
144 do {
145 swapped = false;
146
147 pp_item_l = head;
148 // Loop until end of list is found.
149 while ((*pp_item_l != NULL) && ((*pp_item_l)->node != NULL)) {
150 sl_slist_node_t *p_item_r = (*pp_item_l)->node;
151 bool ordered;
152
153 // Call provided compare fnct.
154 ordered = cmp_fnct(*pp_item_l, p_item_r);
155 if (ordered == false) {
156 // If order is not correct, swap items.
157 sl_slist_node_t *p_tmp = p_item_r->node;
158
159 // Swap the two items.
160 p_item_r->node = *pp_item_l;
161 (*pp_item_l)->node = p_tmp;
162 *pp_item_l = p_item_r;
163 pp_item_l = &(p_item_r->node);
164 // Indicate a swap has been done.
165 swapped = true;
166 } else {
167 pp_item_l = &((*pp_item_l)->node);
168 }
169 }
170 // Re-loop until no items have been swapped.
171 } while (swapped == true);
172 }
173
