3 * Copyright 2006 Free Software Foundation, Inc.
5 * This file is part of GNU Radio.
7 * GNU Radio is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 3, or (at your option)
12 * GNU Radio is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with GNU Radio; see the file COPYING. If not, write to
19 * the Free Software Foundation, Inc., 51 Franklin Street,
20 * Boston, MA 02110-1301, USA.
23 #ifndef _CIRCULAR_LINKED_LIST_H_
24 #define _CIRCULAR_LINKED_LIST_H_
26 #include <mld_threads.h>
29 #define __INLINE__ inline
36 #define DEBUG(X) do{X} while(0);
38 #define DEBUG(X) do{} while(0);
41 template <class T> class s_both;
43 template <class T> class s_node
45 typedef s_node<T>* s_node_ptr;
50 s_node_ptr d_prev, d_next;
55 s_node_ptr l_prev = NULL,
56 s_node_ptr l_next = NULL)
57 : d_object (l_object), d_available (TRUE), d_prev (l_prev),
58 d_next (l_next), d_both (0) {};
60 __INLINE__ s_node (s_node_ptr l_prev, s_node_ptr l_next = NULL) {
61 s_node ((T) NULL, l_prev, l_next); };
62 __INLINE__ s_node () { s_node (NULL, NULL, NULL); };
63 __INLINE__ ~s_node () {};
66 d_prev->next (d_next);
67 d_next->prev (d_prev);
68 d_prev = d_next = this;
71 void insert_before (s_node_ptr l_next) {
73 s_node_ptr l_prev = l_next->prev ();
79 d_next = d_prev = this;
82 void insert_after (s_node_ptr l_prev) {
84 s_node_ptr l_next = l_prev->next ();
90 d_prev = d_next = this;
93 __INLINE__ T object () { return (d_object); };
94 __INLINE__ void object (T l_object) { d_object = l_object; };
95 __INLINE__ bool available () { return (d_available); };
96 __INLINE__ void set_available () { d_available = TRUE; };
97 __INLINE__ void set_available (bool l_avail) { d_available = l_avail; };
98 __INLINE__ void set_not_available () { d_available = FALSE; };
99 __INLINE__ s_node_ptr next () { return (d_next); };
100 __INLINE__ s_node_ptr prev () { return (d_prev); };
101 __INLINE__ s_both<T>* both () { return (d_both); };
102 __INLINE__ void next (s_node_ptr l_next) { d_next = l_next; };
103 __INLINE__ void prev (s_node_ptr l_prev) { d_prev = l_prev; };
104 __INLINE__ void both (s_both<T>* l_both) { d_both = l_both; };
107 template <class T> class circular_linked_list {
108 typedef s_node<T>* s_node_ptr;
111 s_node_ptr d_current, d_iterate, d_available, d_inUse;
112 UInt32 d_n_nodes, d_n_used;
113 mld_mutex_ptr d_internal;
114 mld_condition_ptr d_ioBlock;
117 circular_linked_list (UInt32 n_nodes) {
119 throw std::runtime_error ("circular_linked_list(): n_nodes == 0");
124 s_node_ptr l_prev, l_next;
125 d_inUse = d_current = l_next = l_prev = NULL;
127 l_prev = new s_node<T> ();
128 l_prev->set_available ();
129 l_prev->next (l_prev);
130 l_prev->prev (l_prev);
132 l_next = new s_node<T> (l_prev, l_prev);
133 l_next->set_available ();
134 l_next->next (l_prev);
135 l_next->prev (l_prev);
136 l_prev->next (l_next);
137 l_prev->prev (l_next);
139 UInt32 n = n_nodes - 2;
141 d_current = new s_node<T> (l_prev, l_next);
142 d_current->set_available ();
143 d_current->prev (l_prev);
144 d_current->next (l_next);
145 l_prev->next (d_current);
146 l_next->prev (d_current);
152 d_available = d_current = l_prev;
153 d_ioBlock = new mld_condition ();
154 d_internal = d_ioBlock->mutex ();
157 ~circular_linked_list () {
159 s_node_ptr l_node = iterate_next ();
162 l_node = iterate_next ();
166 d_available = d_inUse = d_iterate = d_current = NULL;
167 d_n_used = d_n_nodes = 0;
170 s_node_ptr find_next_available_node () {
172 // find an available node
173 s_node_ptr l_node = d_available;
174 DEBUG (fprintf (stderr, "w "););
176 DEBUG (fprintf (stderr, "x\n"););
177 // the ioBlock condition will automatically unlock() d_internal
179 // and lock() is here
180 DEBUG (fprintf (stderr, "y\n"););
181 l_node = d_available;
183 DEBUG (fprintf (stderr, "::f_n_a_n: #u = %ld, node = %p\n",
184 num_used(), l_node););
185 // remove this one from the current available list
186 if (num_available () == 1) {
187 // last one, just set available to NULL
190 d_available = l_node->next ();
192 // add is to the inUse list
196 l_node->insert_before (d_inUse);
198 l_node->set_not_available ();
199 d_internal->unlock ();
203 void make_node_available (s_node_ptr l_node) {
206 DEBUG (fprintf (stderr, "::m_n_a: #u = %ld, node = %p\n",
207 num_used(), l_node););
208 // remove this node from the inUse list
209 if (num_used () == 1) {
210 // last one, just set inUse to NULL
213 d_inUse = l_node->next ();
215 // add this node to the available list
217 d_available = l_node;
219 l_node->insert_before (d_available);
222 DEBUG (fprintf (stderr, "s%ld ", d_n_used););
223 // signal the condition when new data arrives
224 d_ioBlock->signal ();
225 DEBUG (fprintf (stderr, "t "););
227 // unlock the mutex for thread safety
228 d_internal->unlock ();
231 __INLINE__ void iterate_start () { d_iterate = d_current; };
233 s_node_ptr iterate_next () {
235 // lock the mutex for thread safety
238 s_node_ptr l_this = NULL;
241 d_iterate = d_iterate->next ();
242 if (d_iterate == d_current)
246 // unlock the mutex for thread safety
247 d_internal->unlock ();
252 __INLINE__ T object () { return (d_current->d_object); };
253 __INLINE__ void object (T l_object) { d_current->d_object = l_object; };
254 __INLINE__ UInt32 num_nodes () { return (d_n_nodes); };
255 __INLINE__ UInt32 num_used () { return (d_n_used); };
256 __INLINE__ void num_used (UInt32 l_n_used) { d_n_used = l_n_used; };
257 __INLINE__ UInt32 num_available () { return (d_n_nodes - d_n_used); };
258 __INLINE__ void num_used_inc (void) {
259 if (d_n_used < d_n_nodes) ++d_n_used;
261 __INLINE__ void num_used_dec (void) {
262 if (d_n_used != 0) --d_n_used;
263 // signal the condition that new data has arrived
264 d_ioBlock->signal ();
266 __INLINE__ bool in_use () { return (d_n_used != 0); };
269 template <class T> class s_both
275 __INLINE__ s_both (s_node<T>* l_node, void* l_this)
276 : d_node (l_node), d_this (l_this) {};
277 __INLINE__ ~s_both () {};
278 __INLINE__ s_node<T>* node () { return (d_node); };
279 __INLINE__ void* This () { return (d_this); };
280 __INLINE__ void set (s_node<T>* l_node, void* l_this) {
281 d_node = l_node; d_this = l_this;};
284 #endif /* _CIRCULAR_LINKED_LIST_H_ */