1/*
2Copyright (c) 2012, Broadcom Europe Ltd
3All rights reserved.
4
5Redistribution and use in source and binary forms, with or without
6modification, are permitted provided that the following conditions are met:
7 * Redistributions of source code must retain the above copyright
8 notice, this list of conditions and the following disclaimer.
9 * Redistributions in binary form must reproduce the above copyright
10 notice, this list of conditions and the following disclaimer in the
11 documentation and/or other materials provided with the distribution.
12 * Neither the name of the copyright holder nor the
13 names of its contributors may be used to endorse or promote products
14 derived from this software without specific prior written permission.
15
16THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
17ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY
20DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26*/
27
28#include "interface/vcos/vcos.h"
29#include "interface/mmal/util/mmal_list.h"
30
31
32/* Private list context */
33typedef struct MMAL_LIST_PRIVATE_T
34{
35 MMAL_LIST_T list; /* must be first */
36 VCOS_MUTEX_T lock;
37} MMAL_LIST_PRIVATE_T;
38
39
40/* Lock the list. */
41static inline void mmal_list_lock(MMAL_LIST_T *list)
42{
43 vcos_mutex_lock(&((MMAL_LIST_PRIVATE_T*)list)->lock);
44}
45
46/* Unlock the list. */
47static inline void mmal_list_unlock(MMAL_LIST_T *list)
48{
49 vcos_mutex_unlock(&((MMAL_LIST_PRIVATE_T*)list)->lock);
50}
51
52/* Create a new linked list. */
53MMAL_LIST_T* mmal_list_create(void)
54{
55 MMAL_LIST_PRIVATE_T *private;
56
57 private = vcos_malloc(sizeof(MMAL_LIST_PRIVATE_T), "mmal-list");
58 if (private == NULL)
59 goto error;
60
61 if (vcos_mutex_create(&private->lock, "mmal-list lock") != VCOS_SUCCESS)
62 goto error;
63
64 /* lock to keep coverity happy */
65 vcos_mutex_lock(&private->lock);
66 private->list.first = NULL;
67 private->list.last = NULL;
68 private->list.length = 0;
69 vcos_mutex_unlock(&private->lock);
70
71 return &private->list;
72
73error:
74 vcos_free(private);
75 return NULL;
76}
77
78/* Destroy a linked list. */
79void mmal_list_destroy(MMAL_LIST_T *list)
80{
81 MMAL_LIST_PRIVATE_T *private = (MMAL_LIST_PRIVATE_T*)list;
82
83 vcos_mutex_delete(&private->lock);
84 vcos_free(private);
85}
86
87/* Remove the last element in the list. */
88MMAL_LIST_ELEMENT_T* mmal_list_pop_back(MMAL_LIST_T *list)
89{
90 MMAL_LIST_ELEMENT_T *element;
91
92 mmal_list_lock(list);
93
94 element = list->last;
95 if (element != NULL)
96 {
97 list->length--;
98
99 list->last = element->prev;
100 if (list->last)
101 list->last->next = NULL;
102 else
103 list->first = NULL; /* list is now empty */
104
105 element->prev = NULL;
106 element->next = NULL;
107 }
108
109 mmal_list_unlock(list);
110
111 return element;
112}
113
114/* Remove the first element in the list. */
115MMAL_LIST_ELEMENT_T* mmal_list_pop_front(MMAL_LIST_T *list)
116{
117 MMAL_LIST_ELEMENT_T *element;
118
119 mmal_list_lock(list);
120
121 element = list->first;
122 if (element != NULL)
123 {
124 list->length--;
125
126 list->first = element->next;
127 if (list->first)
128 list->first->prev = NULL;
129 else
130 list->last = NULL; /* list is now empty */
131
132 element->prev = NULL;
133 element->next = NULL;
134 }
135
136 mmal_list_unlock(list);
137
138 return element;
139}
140
141/* Add an element to the front of the list. */
142void mmal_list_push_front(MMAL_LIST_T *list, MMAL_LIST_ELEMENT_T *element)
143{
144 mmal_list_lock(list);
145
146 list->length++;
147
148 element->prev = NULL;
149 element->next = list->first;
150
151 if (list->first)
152 list->first->prev = element;
153 else
154 list->last = element; /* list was empty */
155
156 list->first = element;
157
158 mmal_list_unlock(list);
159}
160
161/* Add an element to the back of the list. */
162void mmal_list_push_back(MMAL_LIST_T *list, MMAL_LIST_ELEMENT_T *element)
163{
164 mmal_list_lock(list);
165
166 list->length++;
167
168 element->next = NULL;
169 element->prev = list->last;
170
171 if (list->last)
172 list->last->next = element;
173 else
174 list->first = element; /* list was empty */
175
176 list->last = element;
177
178 mmal_list_unlock(list);
179}
180
181/* Insert an element into the list. */
182void mmal_list_insert(MMAL_LIST_T *list, MMAL_LIST_ELEMENT_T *element, MMAL_LIST_COMPARE_T compare)
183{
184 MMAL_LIST_ELEMENT_T *cur;
185
186 mmal_list_lock(list);
187
188 if (list->first == NULL)
189 {
190 /* List empty */
191 mmal_list_unlock(list);
192 mmal_list_push_front(list, element);
193 return;
194 }
195
196 cur = list->first;
197 while (cur)
198 {
199 if (compare(element, cur))
200 {
201 /* Slot found! */
202 list->length++;
203 if (cur == list->first)
204 list->first = element;
205 else
206 cur->prev->next = element;
207 element->prev = cur->prev;
208 element->next = cur;
209 cur->prev = element;
210 mmal_list_unlock(list);
211 return;
212 }
213
214 cur = cur->next;
215 }
216
217 /* If we get here, none of the existing elements are greater
218 * than the new on, so just add it to the back of the list */
219 mmal_list_unlock(list);
220 mmal_list_push_back(list, element);
221}
222