Universal Software Radio Peripheral
|
00001 /* -*- c++ -*- */ 00002 /* 00003 * Copyright 2006 Free Software Foundation, Inc. 00004 * 00005 * This file is part of GNU Radio. 00006 * 00007 * GNU Radio is free software; you can redistribute it and/or modify 00008 * it under the terms of the GNU General Public License as published by 00009 * the Free Software Foundation; either version 3, or (at your option) 00010 * any later version. 00011 * 00012 * GNU Radio is distributed in the hope that it will be useful, 00013 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 * GNU General Public License for more details. 00016 * 00017 * You should have received a copy of the GNU General Public License 00018 * along with GNU Radio; see the file COPYING. If not, write to 00019 * the Free Software Foundation, Inc., 51 Franklin Street, 00020 * Boston, MA 02110-1301, USA. 00021 */ 00022 00023 #ifndef _CIRCULAR_LINKED_LIST_H_ 00024 #define _CIRCULAR_LINKED_LIST_H_ 00025 00026 #include <mld_threads.h> 00027 #include <stdexcept> 00028 00029 #define __INLINE__ inline 00030 00031 #ifndef DO_DEBUG 00032 #define DO_DEBUG 0 00033 #endif 00034 00035 #if DO_DEBUG 00036 #define DEBUG(X) do{X} while(0); 00037 #else 00038 #define DEBUG(X) do{} while(0); 00039 #endif 00040 00041 template <class T> class s_both; 00042 00043 template <class T> class s_node 00044 { 00045 typedef s_node<T>* s_node_ptr; 00046 00047 private: 00048 T d_object; 00049 bool d_available; 00050 s_node_ptr d_prev, d_next; 00051 s_both<T>* d_both; 00052 00053 public: 00054 s_node (T l_object, 00055 s_node_ptr l_prev = NULL, 00056 s_node_ptr l_next = NULL) 00057 : d_object (l_object), d_available (TRUE), d_prev (l_prev), 00058 d_next (l_next), d_both (0) {}; 00059 00060 __INLINE__ s_node (s_node_ptr l_prev, s_node_ptr l_next = NULL) { 00061 s_node ((T) NULL, l_prev, l_next); }; 00062 __INLINE__ s_node () { s_node (NULL, NULL, NULL); }; 00063 __INLINE__ ~s_node () {}; 00064 00065 void remove () { 00066 d_prev->next (d_next); 00067 d_next->prev (d_prev); 00068 d_prev = d_next = this; 00069 }; 00070 00071 void insert_before (s_node_ptr l_next) { 00072 if (l_next) { 00073 s_node_ptr l_prev = l_next->prev (); 00074 d_next = l_next; 00075 d_prev = l_prev; 00076 l_prev->next (this); 00077 l_next->prev (this); 00078 } else 00079 d_next = d_prev = this; 00080 }; 00081 00082 void insert_after (s_node_ptr l_prev) { 00083 if (l_prev) { 00084 s_node_ptr l_next = l_prev->next (); 00085 d_prev = l_prev; 00086 d_next = l_next; 00087 l_next->prev (this); 00088 l_prev->next (this); 00089 } else 00090 d_prev = d_next = this; 00091 }; 00092 00093 __INLINE__ T object () { return (d_object); }; 00094 __INLINE__ void object (T l_object) { d_object = l_object; }; 00095 __INLINE__ bool available () { return (d_available); }; 00096 __INLINE__ void set_available () { d_available = TRUE; }; 00097 __INLINE__ void set_available (bool l_avail) { d_available = l_avail; }; 00098 __INLINE__ void set_not_available () { d_available = FALSE; }; 00099 __INLINE__ s_node_ptr next () { return (d_next); }; 00100 __INLINE__ s_node_ptr prev () { return (d_prev); }; 00101 __INLINE__ s_both<T>* both () { return (d_both); }; 00102 __INLINE__ void next (s_node_ptr l_next) { d_next = l_next; }; 00103 __INLINE__ void prev (s_node_ptr l_prev) { d_prev = l_prev; }; 00104 __INLINE__ void both (s_both<T>* l_both) { d_both = l_both; }; 00105 }; 00106 00107 template <class T> class circular_linked_list { 00108 typedef s_node<T>* s_node_ptr; 00109 00110 private: 00111 s_node_ptr d_current, d_iterate, d_available, d_inUse; 00112 UInt32 d_n_nodes, d_n_used; 00113 mld_mutex_ptr d_internal; 00114 mld_condition_ptr d_ioBlock; 00115 00116 public: 00117 circular_linked_list (UInt32 n_nodes) { 00118 if (n_nodes == 0) 00119 throw std::runtime_error ("circular_linked_list(): n_nodes == 0"); 00120 00121 d_iterate = NULL; 00122 d_n_nodes = n_nodes; 00123 d_n_used = 0; 00124 s_node_ptr l_prev, l_next; 00125 d_inUse = d_current = l_next = l_prev = NULL; 00126 00127 l_prev = new s_node<T> (); 00128 l_prev->set_available (); 00129 l_prev->next (l_prev); 00130 l_prev->prev (l_prev); 00131 if (n_nodes > 1) { 00132 l_next = new s_node<T> (l_prev, l_prev); 00133 l_next->set_available (); 00134 l_next->next (l_prev); 00135 l_next->prev (l_prev); 00136 l_prev->next (l_next); 00137 l_prev->prev (l_next); 00138 if (n_nodes > 2) { 00139 UInt32 n = n_nodes - 2; 00140 while (n-- > 0) { 00141 d_current = new s_node<T> (l_prev, l_next); 00142 d_current->set_available (); 00143 d_current->prev (l_prev); 00144 d_current->next (l_next); 00145 l_prev->next (d_current); 00146 l_next->prev (d_current); 00147 l_next = d_current; 00148 d_current = NULL; 00149 } 00150 } 00151 } 00152 d_available = d_current = l_prev; 00153 d_ioBlock = new mld_condition (); 00154 d_internal = d_ioBlock->mutex (); 00155 }; 00156 00157 ~circular_linked_list () { 00158 iterate_start (); 00159 s_node_ptr l_node = iterate_next (); 00160 while (l_node) { 00161 delete l_node; 00162 l_node = iterate_next (); 00163 } 00164 delete d_ioBlock; 00165 d_ioBlock = NULL; 00166 d_available = d_inUse = d_iterate = d_current = NULL; 00167 d_n_used = d_n_nodes = 0; 00168 }; 00169 00170 s_node_ptr find_next_available_node () { 00171 d_internal->lock (); 00172 // find an available node 00173 s_node_ptr l_node = d_available; 00174 DEBUG (fprintf (stderr, "w ");); 00175 while (! l_node) { 00176 DEBUG (fprintf (stderr, "x\n");); 00177 // the ioBlock condition will automatically unlock() d_internal 00178 d_ioBlock->wait (); 00179 // and lock() is here 00180 DEBUG (fprintf (stderr, "y\n");); 00181 l_node = d_available; 00182 } 00183 DEBUG (fprintf (stderr, "::f_n_a_n: #u = %ld, node = %p\n", 00184 num_used(), l_node);); 00185 // remove this one from the current available list 00186 if (num_available () == 1) { 00187 // last one, just set available to NULL 00188 d_available = NULL; 00189 } else 00190 d_available = l_node->next (); 00191 l_node->remove (); 00192 // add is to the inUse list 00193 if (! d_inUse) 00194 d_inUse = l_node; 00195 else 00196 l_node->insert_before (d_inUse); 00197 d_n_used++; 00198 l_node->set_not_available (); 00199 d_internal->unlock (); 00200 return (l_node); 00201 }; 00202 00203 void make_node_available (s_node_ptr l_node) { 00204 if (!l_node) return; 00205 d_internal->lock (); 00206 DEBUG (fprintf (stderr, "::m_n_a: #u = %ld, node = %p\n", 00207 num_used(), l_node);); 00208 // remove this node from the inUse list 00209 if (num_used () == 1) { 00210 // last one, just set inUse to NULL 00211 d_inUse = NULL; 00212 } else 00213 d_inUse = l_node->next (); 00214 l_node->remove (); 00215 // add this node to the available list 00216 if (! d_available) 00217 d_available = l_node; 00218 else 00219 l_node->insert_before (d_available); 00220 d_n_used--; 00221 00222 DEBUG (fprintf (stderr, "s%ld ", d_n_used);); 00223 // signal the condition when new data arrives 00224 d_ioBlock->signal (); 00225 DEBUG (fprintf (stderr, "t ");); 00226 00227 // unlock the mutex for thread safety 00228 d_internal->unlock (); 00229 }; 00230 00231 __INLINE__ void iterate_start () { d_iterate = d_current; }; 00232 00233 s_node_ptr iterate_next () { 00234 #if 0 00235 // lock the mutex for thread safety 00236 d_internal->lock (); 00237 #endif 00238 s_node_ptr l_this = NULL; 00239 if (d_iterate) { 00240 l_this = d_iterate; 00241 d_iterate = d_iterate->next (); 00242 if (d_iterate == d_current) 00243 d_iterate = NULL; 00244 } 00245 #if 0 00246 // unlock the mutex for thread safety 00247 d_internal->unlock (); 00248 #endif 00249 return (l_this); 00250 }; 00251 00252 __INLINE__ T object () { return (d_current->d_object); }; 00253 __INLINE__ void object (T l_object) { d_current->d_object = l_object; }; 00254 __INLINE__ UInt32 num_nodes () { return (d_n_nodes); }; 00255 __INLINE__ UInt32 num_used () { return (d_n_used); }; 00256 __INLINE__ void num_used (UInt32 l_n_used) { d_n_used = l_n_used; }; 00257 __INLINE__ UInt32 num_available () { return (d_n_nodes - d_n_used); }; 00258 __INLINE__ void num_used_inc (void) { 00259 if (d_n_used < d_n_nodes) ++d_n_used; 00260 }; 00261 __INLINE__ void num_used_dec (void) { 00262 if (d_n_used != 0) --d_n_used; 00263 // signal the condition that new data has arrived 00264 d_ioBlock->signal (); 00265 }; 00266 __INLINE__ bool in_use () { return (d_n_used != 0); }; 00267 }; 00268 00269 template <class T> class s_both 00270 { 00271 private: 00272 s_node<T>* d_node; 00273 void* d_this; 00274 public: 00275 __INLINE__ s_both (s_node<T>* l_node, void* l_this) 00276 : d_node (l_node), d_this (l_this) {}; 00277 __INLINE__ ~s_both () {}; 00278 __INLINE__ s_node<T>* node () { return (d_node); }; 00279 __INLINE__ void* This () { return (d_this); }; 00280 __INLINE__ void set (s_node<T>* l_node, void* l_this) { 00281 d_node = l_node; d_this = l_this;}; 00282 }; 00283 00284 #endif /* _CIRCULAR_LINKED_LIST_H_ */