1 /**************************************************************************\
2 * Copyright (c) Kongsberg Oil & Gas Technologies AS
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met:
8 *
9 * Redistributions of source code must retain the above copyright notice,
10 * this list of conditions and the following disclaimer.
11 *
12 * Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * Neither the name of the copyright holder nor the names of its
17 * contributors may be used to endorse or promote products derived from
18 * this software without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 \**************************************************************************/
32
33 /*! \file Inventor/C/threads/common.h */
34
35 /*!
36 \struct cc_fifo common.h Inventor/C/threads/common.h
37 \ingroup threads
38 \brief The structure for a first-in, first-out queue.
39 */
40
41 /*!
42 \typedef struct cc_fifo cc_fifo
43 \ingroup threads
44 \brief The type definition for the first-in, first-out queue structure.
45 */
46
47 /*! \file fifo.h */
48 #include <Inventor/C/threads/fifo.h>
49
50 #include <cstdlib>
51 #include <cassert>
52
53 #include <Inventor/C/threads/mutex.h>
54 #include <Inventor/C/threads/condvar.h>
55 #include <Inventor/C/errors/debugerror.h>
56
57 #include "threads/fifop.h"
58 #include "threads/mutexp.h"
59 #include "threads/condvarp.h"
60
61 /*
62 The cc_fifo is a C datatype for managing a pointer first-in,
63 first-out queue.
64 */
65
66 /* ********************************************************************** */
67
68 static cc_fifo_item * cc_fifo_item_new(void);
69 static void cc_fifo_item_delete(cc_fifo_item * item);
70
71 static cc_fifo_item * i_get_free_item(cc_fifo * fifo);
72 static void i_append(cc_fifo * fifo, cc_fifo_item * item);
73 static cc_fifo_item * i_unlink_head(cc_fifo * fifo);
74
75 /* ********************************************************************** */
76
77 void
cc_fifo_struct_init(cc_fifo * fifo)78 cc_fifo_struct_init(cc_fifo * fifo)
79 {
80 assert(fifo != NULL);
81 cc_mutex_struct_init(&fifo->access);
82 fifo->head = NULL;
83 fifo->tail = NULL;
84 fifo->free = NULL;
85 fifo->elements = 0;
86 cc_condvar_struct_init(&fifo->sleep);
87 }
88
89 void
cc_fifo_struct_clean(cc_fifo * fifo)90 cc_fifo_struct_clean(cc_fifo * fifo)
91 {
92 cc_fifo_item * item, * next;
93 assert(fifo != NULL);
94 cc_mutex_struct_clean(&fifo->access);
95 /* free fifo list */
96 item = fifo->head;
97 while ( item != NULL ) {
98 next = item->next;
99 cc_fifo_item_delete(item);
100 item = next;
101 }
102 /* free free list */
103 item = fifo->free;
104 while ( item != NULL ) {
105 next = item->next;
106 cc_fifo_item_delete(item);
107 item = next;
108 }
109 cc_condvar_struct_clean(&fifo->sleep);
110 }
111
112 /* ********************************************************************** */
113
114 /*! Constructs a new first-in, first-out queue. */
115 cc_fifo *
cc_fifo_new(void)116 cc_fifo_new(void)
117 {
118 cc_fifo * fifo;
119 fifo = (cc_fifo*) malloc(sizeof(cc_fifo));
120 cc_fifo_struct_init(fifo);
121 return fifo;
122 }
123
124 /*! Destroys the \a fifo first-in, first-out queue. */
125 void
cc_fifo_delete(cc_fifo * fifo)126 cc_fifo_delete(cc_fifo * fifo)
127 {
128 cc_fifo_struct_clean(fifo);
129 free(fifo);
130 }
131
132 /* ********************************************************************** */
133
134 /*! Appends the \a ptr of type \a type to the end of the \a fifo
135 first-in, first-out queue. */
136 void
cc_fifo_assign(cc_fifo * fifo,void * ptr,uint32_t type)137 cc_fifo_assign(cc_fifo * fifo, void * ptr, uint32_t type)
138 {
139 cc_fifo_item * item;
140 assert(fifo != NULL);
141 cc_mutex_lock(&fifo->access);
142 item = i_get_free_item(fifo);
143 item->item = ptr;
144 item->type = type;
145 i_append(fifo, item);
146 cc_condvar_wake_one(&fifo->sleep);
147 cc_mutex_unlock(&fifo->access);
148 }
149
150 /*! Retrieves the first item from the \a fifo
151 first-in, first-out queue. */
152 void
cc_fifo_retrieve(cc_fifo * fifo,void ** ptr,uint32_t * type)153 cc_fifo_retrieve(cc_fifo * fifo, void ** ptr, uint32_t * type)
154 {
155 cc_fifo_item * item;
156 assert(fifo != NULL && ptr != NULL);
157 cc_mutex_lock(&fifo->access);
158 while ( TRUE ) {
159 if ( fifo->elements == 0 ) {
160 cc_condvar_wait(&fifo->sleep, &fifo->access);
161 } else {
162 item = i_unlink_head(fifo);
163 *ptr = item->item;
164 if ( type != NULL ) *type = item->type;
165 item->next = fifo->free;
166 fifo->free = item;
167 cc_mutex_unlock(&fifo->access);
168 cc_condvar_wake_one(&fifo->sleep);
169 return;
170 }
171 }
172 }
173
174 /*! Checks the \a fifo first-in, first-out queue to see if an item can be
175 retrieved. If so the properties of the first available item are returned. */
176 SbBool
cc_fifo_try_retrieve(cc_fifo * fifo,void ** ptr,uint32_t * type)177 cc_fifo_try_retrieve(cc_fifo * fifo, void ** ptr, uint32_t * type)
178 {
179 cc_fifo_item * item;
180 assert(fifo != NULL && ptr != NULL);
181 /* FIXME: consider cc_mutex_try_lock()? to escape even a failed lock */
182 if ( ! cc_mutex_try_lock(&fifo->access) ) {
183 return FALSE;
184 }
185 if ( fifo->elements == 0 ) {
186 cc_mutex_unlock(&fifo->access);
187 return FALSE;
188 }
189 item = i_unlink_head(fifo);
190 *ptr = item->item;
191 if ( type != NULL ) *type = item->type;
192 cc_fifo_item_delete(item);
193 cc_mutex_unlock(&fifo->access);
194 cc_condvar_wake_one(&fifo->sleep);
195 return TRUE;
196 }
197
198 /* ********************************************************************** */
199
200 /*! Returns the number of elements in the \a fifo first-in, first-out queue. */
201 unsigned int
cc_fifo_size(cc_fifo * fifo)202 cc_fifo_size(cc_fifo * fifo)
203 {
204 assert(fifo != NULL);
205 return fifo->elements;
206 }
207
208 /* ********************************************************************** */
209
210 cc_fifo_item *
cc_fifo_item_new(void)211 cc_fifo_item_new(void) /* static */
212 {
213 cc_fifo_item * item;
214 item = (cc_fifo_item*) malloc(sizeof(cc_fifo_item));
215 assert(item != NULL);
216 item->next = NULL;
217 item->item = NULL;
218 item->type = 0;
219 return item;
220 }
221
222 void
cc_fifo_item_delete(cc_fifo_item * item)223 cc_fifo_item_delete(cc_fifo_item * item) /* static */
224 {
225 assert(item != NULL);
226 free(item);
227 }
228
229 /* ********************************************************************** */
230
231 /*! Locks the \a fifo first-in, first-out queue. */
232 void
cc_fifo_lock(cc_fifo * fifo)233 cc_fifo_lock(cc_fifo * fifo)
234 {
235 assert(fifo != NULL);
236 cc_mutex_lock(&fifo->access);
237 }
238
239 SbBool
cc_fifo_try_lock(cc_fifo * fifo)240 cc_fifo_try_lock(cc_fifo * fifo)
241 {
242 assert(fifo != NULL);
243 return cc_mutex_try_lock(&fifo->access);
244 }
245
246 /*! Unlocks the \a fifo first-in, first-out queue. */
247 void
cc_fifo_unlock(cc_fifo * fifo)248 cc_fifo_unlock(cc_fifo * fifo)
249 {
250 assert(fifo != NULL);
251 cc_mutex_unlock(&fifo->access);
252 }
253
254 /* ********************************************************************** */
255
256 /*! Returns the properties of the first item in the \a fifo first-in, first-out queue. */
257 SbBool
cc_fifo_peek(cc_fifo * fifo,void ** item,uint32_t * type)258 cc_fifo_peek(cc_fifo * fifo, void ** item, uint32_t * type)
259 {
260 assert(fifo != NULL);
261 if ( fifo->head == NULL ) return FALSE;
262 *item = fifo->head->item;
263 if ( type != NULL ) *type = fifo->head->type;
264 return TRUE;
265 }
266
267 /*! Checks if the \a fifo first-in, first-out queue contains the \a itemptr item. */
268 SbBool
cc_fifo_contains(cc_fifo * fifo,void * itemptr)269 cc_fifo_contains(cc_fifo * fifo, void * itemptr)
270 {
271 cc_fifo_item * item;
272 assert(fifo != NULL);
273 item = fifo->head;
274 while ( item != NULL ) {
275 if ( item->item == itemptr ) return TRUE;
276 item = item->next;
277 }
278 return FALSE;
279 }
280
281 /*! Removes from the \a fifo first-in, first-out queue the \a itemptr item if present. */
282 SbBool
cc_fifo_reclaim(cc_fifo * fifo,void * itemptr)283 cc_fifo_reclaim(cc_fifo * fifo, void * itemptr)
284 {
285 cc_fifo_item * item, * prev;
286 assert(fifo != NULL);
287 item = fifo->head;
288 prev = NULL;
289 while ( item != NULL ) {
290 if ( item->item == itemptr ) {
291 if ( prev == NULL ) fifo->head = item->next;
292 else prev->next = item->next;
293 if ( fifo->tail == item ) fifo->tail = prev;
294 /* and reset/store the container */
295 item->item = NULL;
296 item->type = 0;
297 item->next = fifo->free;
298 fifo->free = item;
299 return TRUE;
300 }
301 prev = item;
302 item = item->next;
303 }
304 return FALSE;
305 }
306
307 /* ********************************************************************** */
308
309 /*
310 get item from free list or construct a new one
311 */
312
313 cc_fifo_item *
i_get_free_item(cc_fifo * fifo)314 i_get_free_item(cc_fifo * fifo) /* static */
315 {
316 cc_fifo_item * item;
317 if ( fifo->free != NULL ) {
318 item = fifo->free;
319 fifo->free = item->next;
320 item->next = NULL;
321 } else {
322 item = cc_fifo_item_new();
323 }
324 return item;
325 }
326
327 /*
328 append item to fifo. make sure both ::head and ::tail are correct
329 after.
330 */
331
332 void
i_append(cc_fifo * fifo,cc_fifo_item * item)333 i_append(cc_fifo * fifo, cc_fifo_item * item) /* static */
334 {
335 if ( fifo->tail == NULL ) {
336 fifo->head = item;
337 fifo->tail = item;
338 } else {
339 fifo->tail->next = item;
340 fifo->tail = item;
341 }
342 fifo->elements += 1;
343 }
344
345 /*
346 unlink first item from fifo. make sure both ::head and ::tail are
347 correct after.
348 */
349
350 cc_fifo_item *
i_unlink_head(cc_fifo * fifo)351 i_unlink_head(cc_fifo * fifo) /* static */
352 {
353 cc_fifo_item * item;
354 item = fifo->head;
355 fifo->head = item->next;
356 if ( fifo->head == NULL )
357 fifo->tail = NULL;
358 fifo->elements -= 1;
359 return item;
360 }
361