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 2, 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 template <class T> class s_both;
00032 
00033 template <class T> class s_node
00034 {
00035   typedef s_node<T>* s_node_ptr;
00036 
00037 private:
00038   T d_object;
00039   bool d_available;
00040   s_node_ptr d_prev, d_next;
00041   s_both<T>* d_both;
00042 
00043 public:
00044   s_node (T l_object,
00045           s_node_ptr l_prev = NULL,
00046           s_node_ptr l_next = NULL)
00047     : d_object (l_object), d_available (TRUE), d_prev (l_prev),
00048     d_next (l_next), d_both (0) {};
00049 
00050   __INLINE__ s_node (s_node_ptr l_prev, s_node_ptr l_next = NULL) {
00051     s_node ((T) NULL, l_prev, l_next); };
00052   __INLINE__ s_node () { s_node (NULL, NULL, NULL); };
00053   __INLINE__ ~s_node () {};
00054 
00055   void remove () {
00056     d_prev->next (d_next);
00057     d_next->prev (d_prev);
00058     d_prev = d_next = this;
00059   };
00060 
00061   void insert_before (s_node_ptr l_next) {
00062     if (l_next) {
00063       s_node_ptr l_prev = l_next->prev ();
00064       d_next = l_next;
00065       d_prev = l_prev;
00066       l_prev->next (this);
00067       l_next->prev (this);
00068     } else
00069       d_next = d_prev = this;
00070   };
00071 
00072   void insert_after (s_node_ptr l_prev) {
00073     if (l_prev) {
00074       s_node_ptr l_next = l_prev->next ();
00075       d_prev = l_prev;
00076       d_next = l_next;
00077       l_next->prev (this);
00078       l_prev->next (this);
00079     } else
00080       d_prev = d_next = this;
00081   };
00082 
00083   __INLINE__ T object () { return (d_object); };
00084   __INLINE__ void object (T l_object) { d_object = l_object; };
00085   __INLINE__ bool available () { return (d_available); };
00086   __INLINE__ void set_available () { d_available = TRUE; };
00087   __INLINE__ void set_available (bool l_avail) { d_available = l_avail; };
00088   __INLINE__ void set_not_available () { d_available = FALSE; };
00089   __INLINE__ s_node_ptr next () { return (d_next); };
00090   __INLINE__ s_node_ptr prev () { return (d_prev); };
00091   __INLINE__ s_both<T>* both () { return (d_both); };
00092   __INLINE__ void next (s_node_ptr l_next) { d_next = l_next; };
00093   __INLINE__ void prev (s_node_ptr l_prev) { d_prev = l_prev; };
00094   __INLINE__ void both (s_both<T>* l_both) { d_both = l_both; };
00095 };
00096 
00097 template <class T> class circular_linked_list {
00098   typedef s_node<T>* s_node_ptr;
00099 
00100 private:
00101   s_node_ptr d_current, d_iterate, d_available, d_inUse;
00102   UInt32 d_n_nodes, d_n_used;
00103   mld_mutex_ptr d_internal;
00104   mld_condition_ptr d_ioBlock;
00105 
00106 public:
00107   circular_linked_list (UInt32 n_nodes) {
00108     if (n_nodes == 0)
00109       throw std::runtime_error ("circular_linked_list(): n_nodes == 0");
00110 
00111     d_iterate = NULL;
00112     d_n_nodes = n_nodes;
00113     d_n_used = 0;
00114     s_node_ptr l_prev, l_next;
00115     d_inUse = d_current = l_next = l_prev = NULL;
00116 
00117     l_prev = new s_node<T> ();
00118     l_prev->set_available ();
00119     l_prev->next (l_prev);
00120     l_prev->prev (l_prev);
00121     if (n_nodes > 1) {
00122       l_next = new s_node<T> (l_prev, l_prev);
00123       l_next->set_available ();
00124       l_next->next (l_prev);
00125       l_next->prev (l_prev);
00126       l_prev->next (l_next);
00127       l_prev->prev (l_next);
00128       if (n_nodes > 2) {
00129         UInt32 n = n_nodes - 2;
00130         while (n-- > 0) {
00131           d_current = new s_node<T> (l_prev, l_next);
00132           d_current->set_available ();
00133           d_current->prev (l_prev);
00134           d_current->next (l_next);
00135           l_prev->next (d_current);
00136           l_next->prev (d_current);
00137           l_next = d_current;
00138           d_current = NULL;
00139         }
00140       }
00141     }
00142     d_available = d_current = l_prev;
00143     d_internal = new mld_mutex ();
00144     d_ioBlock = new mld_condition ();
00145   };
00146 
00147   ~circular_linked_list () {
00148     iterate_start ();
00149     s_node_ptr l_node = iterate_next ();
00150     while (l_node) {
00151       delete l_node;
00152       l_node = iterate_next ();
00153     }
00154     delete d_internal;
00155     d_internal = NULL;
00156     delete d_ioBlock;
00157     d_ioBlock = NULL;
00158     d_available = d_inUse = d_iterate = d_current = NULL;
00159     d_n_used = d_n_nodes = 0;
00160   };
00161 
00162   s_node_ptr find_next_available_node () {
00163     d_internal->lock ();
00164 // find an available node
00165     s_node_ptr l_node = d_available; 
00166     while (! l_node) {
00167       d_internal->unlock ();
00168       d_ioBlock->wait ();
00169       d_internal->lock ();
00170       l_node = d_available;
00171     }
00172 //  fprintf (stderr, "::f_n_a_n: #u = %ld, node = %p\n", num_used(), l_node);
00173 // remove this one from the current available list
00174     if (num_available () == 1) {
00175 // last one, just set available to NULL
00176       d_available = NULL;
00177     } else
00178       d_available = l_node->next ();
00179     l_node->remove ();
00180 // add is to the inUse list
00181     if (! d_inUse)
00182       d_inUse = l_node;
00183     else
00184       l_node->insert_before (d_inUse);
00185     d_n_used++;
00186     l_node->set_not_available ();
00187     d_internal->unlock ();
00188     return (l_node);
00189   };
00190 
00191   void make_node_available (s_node_ptr l_node) {
00192     if (!l_node) return;
00193     d_internal->lock ();
00194 //  fprintf (stderr, "::m_n_a: #u = %ld, node = %p\n", num_used(), l_node);
00195 // remove this node from the inUse list
00196     if (num_used () == 1) {
00197 // last one, just set inUse to NULL
00198       d_inUse = NULL;
00199     } else
00200       d_inUse = l_node->next ();
00201     l_node->remove ();
00202 // add this node to the available list
00203     if (! d_available)
00204       d_available = l_node;
00205     else
00206       l_node->insert_before (d_available);
00207     d_n_used--;
00208 // signal the condition when new data arrives
00209     d_ioBlock->signal ();
00210 // unlock the mutex for thread safety
00211     d_internal->unlock ();
00212   };
00213 
00214   __INLINE__ void iterate_start () { d_iterate = d_current; };
00215 
00216   s_node_ptr iterate_next () {
00217 #if 0
00218 // lock the mutex for thread safety
00219     d_internal->lock ();
00220 #endif
00221     s_node_ptr l_this = NULL;
00222     if (d_iterate) {
00223       l_this = d_iterate;
00224       d_iterate = d_iterate->next ();
00225       if (d_iterate == d_current)
00226         d_iterate = NULL;
00227     }
00228 #if 0
00229 // unlock the mutex for thread safety
00230     d_internal->unlock ();
00231 #endif
00232     return (l_this);
00233   };
00234 
00235   __INLINE__ T object () { return (d_current->d_object); };
00236   __INLINE__ void object (T l_object) { d_current->d_object = l_object; };
00237   __INLINE__ UInt32 num_nodes () { return (d_n_nodes); };
00238   __INLINE__ UInt32 num_used () { return (d_n_used); };
00239   __INLINE__ void num_used (UInt32 l_n_used) { d_n_used = l_n_used; };
00240   __INLINE__ UInt32 num_available () { return (d_n_nodes - d_n_used); };
00241   __INLINE__ void num_used_inc (void) {
00242     if (d_n_used < d_n_nodes) ++d_n_used;
00243   };
00244   __INLINE__ void num_used_dec (void) {
00245     if (d_n_used != 0) --d_n_used;
00246 // signal the condition that new data has arrived
00247     d_ioBlock->signal ();
00248   };
00249   __INLINE__ bool in_use () { return (d_n_used != 0); };
00250 };
00251 
00252 template <class T> class s_both
00253 {
00254 private:
00255   s_node<T>* d_node;
00256   void* d_this;
00257 public:
00258   __INLINE__ s_both (s_node<T>* l_node, void* l_this)
00259     : d_node (l_node), d_this (l_this) {};
00260   __INLINE__ ~s_both () {};
00261   __INLINE__ s_node<T>* node () { return (d_node); };
00262   __INLINE__ void* This () { return (d_this); };
00263   __INLINE__ void set (s_node<T>* l_node, void* l_this) {
00264     d_node = l_node; d_this = l_this;};
00265 };
00266 
00267 #endif /* _CIRCULAR_LINKED_LIST_H_ */

Generated on Tue May 1 10:45:46 2007 for GNU Radio 3.0.3 by  doxygen 1.5.1