Universal Software Radio Peripheral
circular_linked_list.h
Go to the documentation of this file.
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_ */