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 2, 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
31 template <class T> class s_both;
33 template <class T> class s_node
35 typedef s_node<T>* s_node_ptr;
40 s_node_ptr d_prev, d_next;
45 s_node_ptr l_prev = NULL,
46 s_node_ptr l_next = NULL)
47 : d_object (l_object), d_available (TRUE), d_prev (l_prev),
48 d_next (l_next), d_both (0) {};
50 __INLINE__ s_node (s_node_ptr l_prev, s_node_ptr l_next = NULL) {
51 s_node ((T) NULL, l_prev, l_next); };
52 __INLINE__ s_node () { s_node (NULL, NULL, NULL); };
53 __INLINE__ ~s_node () {};
56 d_prev->next (d_next);
57 d_next->prev (d_prev);
58 d_prev = d_next = this;
61 void insert_before (s_node_ptr l_next) {
63 s_node_ptr l_prev = l_next->prev ();
69 d_next = d_prev = this;
72 void insert_after (s_node_ptr l_prev) {
74 s_node_ptr l_next = l_prev->next ();
80 d_prev = d_next = this;
83 __INLINE__ T object () { return (d_object); };
84 __INLINE__ void object (T l_object) { d_object = l_object; };
85 __INLINE__ bool available () { return (d_available); };
86 __INLINE__ void set_available () { d_available = TRUE; };
87 __INLINE__ void set_available (bool l_avail) { d_available = l_avail; };
88 __INLINE__ void set_not_available () { d_available = FALSE; };
89 __INLINE__ s_node_ptr next () { return (d_next); };
90 __INLINE__ s_node_ptr prev () { return (d_prev); };
91 __INLINE__ s_both<T>* both () { return (d_both); };
92 __INLINE__ void next (s_node_ptr l_next) { d_next = l_next; };
93 __INLINE__ void prev (s_node_ptr l_prev) { d_prev = l_prev; };
94 __INLINE__ void both (s_both<T>* l_both) { d_both = l_both; };
97 template <class T> class circular_linked_list {
98 typedef s_node<T>* s_node_ptr;
101 s_node_ptr d_current, d_iterate, d_available, d_inUse;
102 UInt32 d_n_nodes, d_n_used;
103 mld_mutex_ptr d_internal;
104 mld_condition_ptr d_ioBlock;
107 circular_linked_list (UInt32 n_nodes) {
109 throw std::runtime_error ("circular_linked_list(): n_nodes == 0");
114 s_node_ptr l_prev, l_next;
115 d_inUse = d_current = l_next = l_prev = NULL;
117 l_prev = new s_node<T> ();
118 l_prev->set_available ();
119 l_prev->next (l_prev);
120 l_prev->prev (l_prev);
122 l_next = new s_node<T> (l_prev, l_prev);
123 l_next->set_available ();
124 l_next->next (l_prev);
125 l_next->prev (l_prev);
126 l_prev->next (l_next);
127 l_prev->prev (l_next);
129 UInt32 n = n_nodes - 2;
131 d_current = new s_node<T> (l_prev, l_next);
132 d_current->set_available ();
133 d_current->prev (l_prev);
134 d_current->next (l_next);
135 l_prev->next (d_current);
136 l_next->prev (d_current);
142 d_available = d_current = l_prev;
143 d_internal = new mld_mutex ();
144 d_ioBlock = new mld_condition ();
147 ~circular_linked_list () {
149 s_node_ptr l_node = iterate_next ();
152 l_node = iterate_next ();
158 d_available = d_inUse = d_iterate = d_current = NULL;
159 d_n_used = d_n_nodes = 0;
162 s_node_ptr find_next_available_node () {
164 // find an available node
165 s_node_ptr l_node = d_available;
167 d_internal->unlock ();
170 l_node = d_available;
172 // fprintf (stderr, "::f_n_a_n: #u = %ld, node = %p\n", num_used(), l_node);
173 // remove this one from the current available list
174 if (num_available () == 1) {
175 // last one, just set available to NULL
178 d_available = l_node->next ();
180 // add is to the inUse list
184 l_node->insert_before (d_inUse);
186 l_node->set_not_available ();
187 d_internal->unlock ();
191 void make_node_available (s_node_ptr l_node) {
194 // fprintf (stderr, "::m_n_a: #u = %ld, node = %p\n", num_used(), l_node);
195 // remove this node from the inUse list
196 if (num_used () == 1) {
197 // last one, just set inUse to NULL
200 d_inUse = l_node->next ();
202 // add this node to the available list
204 d_available = l_node;
206 l_node->insert_before (d_available);
208 // signal the condition when new data arrives
209 d_ioBlock->signal ();
210 // unlock the mutex for thread safety
211 d_internal->unlock ();
214 __INLINE__ void iterate_start () { d_iterate = d_current; };
216 s_node_ptr iterate_next () {
218 // lock the mutex for thread safety
221 s_node_ptr l_this = NULL;
224 d_iterate = d_iterate->next ();
225 if (d_iterate == d_current)
229 // unlock the mutex for thread safety
230 d_internal->unlock ();
235 __INLINE__ T object () { return (d_current->d_object); };
236 __INLINE__ void object (T l_object) { d_current->d_object = l_object; };
237 __INLINE__ UInt32 num_nodes () { return (d_n_nodes); };
238 __INLINE__ UInt32 num_used () { return (d_n_used); };
239 __INLINE__ void num_used (UInt32 l_n_used) { d_n_used = l_n_used; };
240 __INLINE__ UInt32 num_available () { return (d_n_nodes - d_n_used); };
241 __INLINE__ void num_used_inc (void) {
242 if (d_n_used < d_n_nodes) ++d_n_used;
244 __INLINE__ void num_used_dec (void) {
245 if (d_n_used != 0) --d_n_used;
246 // signal the condition that new data has arrived
247 d_ioBlock->signal ();
249 __INLINE__ bool in_use () { return (d_n_used != 0); };
252 template <class T> class s_both
258 __INLINE__ s_both (s_node<T>* l_node, void* l_this)
259 : d_node (l_node), d_this (l_this) {};
260 __INLINE__ ~s_both () {};
261 __INLINE__ s_node<T>* node () { return (d_node); };
262 __INLINE__ void* This () { return (d_this); };
263 __INLINE__ void set (s_node<T>* l_node, void* l_this) {
264 d_node = l_node; d_this = l_this;};
267 #endif /* _CIRCULAR_LINKED_LIST_H_ */