git.gag.com Git - debian/gnuradio/blob - usrp/host/lib/circular_linked_list.h

   1 /* -*- c++ -*- */
   2 /*
   3  * Copyright 2006 Free Software Foundation, Inc.
   4  *
   5  * This file is part of GNU Radio.
   6  *
   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)
  10  * any later version.
  11  *
  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.
  16  *
  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.
  21  */
  22
  23 #ifndef _CIRCULAR_LINKED_LIST_H_
  24 #define _CIRCULAR_LINKED_LIST_H_
  25
  26 #include <mld_threads.h>
  27 #include <stdexcept>
  28
  29 #define __INLINE__ inline
  30
  31 template <class T> class s_both;
  32
  33 template <class T> class s_node
  34 {
  35   typedef s_node<T>* s_node_ptr;
  36
  37 private:
  38   T d_object;
  39   bool d_available;
  40   s_node_ptr d_prev, d_next;
  41   s_both<T>* d_both;
  42
  43 public:
  44   s_node (T l_object,
  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) {};
  49
  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 () {};
  54
  55   void remove () {
  56     d_prev->next (d_next);
  57     d_next->prev (d_prev);
  58     d_prev = d_next = this;
  59   };
  60
  61   void insert_before (s_node_ptr l_next) {
  62     if (l_next) {
  63       s_node_ptr l_prev = l_next->prev ();
  64       d_next = l_next;
  65       d_prev = l_prev;
  66       l_prev->next (this);
  67       l_next->prev (this);
  68     } else
  69       d_next = d_prev = this;
  70   };
  71
  72   void insert_after (s_node_ptr l_prev) {
  73     if (l_prev) {
  74       s_node_ptr l_next = l_prev->next ();
  75       d_prev = l_prev;
  76       d_next = l_next;
  77       l_next->prev (this);
  78       l_prev->next (this);
  79     } else
  80       d_prev = d_next = this;
  81   };
  82
  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; };
  95 };
  96
  97 template <class T> class circular_linked_list {
  98   typedef s_node<T>* s_node_ptr;
  99
 100 private:
 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;
 105
 106 public:
 107   circular_linked_list (UInt32 n_nodes) {
 108     if (n_nodes == 0)
 109       throw std::runtime_error ("circular_linked_list(): n_nodes == 0");
 110
 111     d_iterate = NULL;
 112     d_n_nodes = n_nodes;
 113     d_n_used = 0;
 114     s_node_ptr l_prev, l_next;
 115     d_inUse = d_current = l_next = l_prev = NULL;
 116
 117     l_prev = new s_node<T> ();
 118     l_prev->set_available ();
 119     l_prev->next (l_prev);
 120     l_prev->prev (l_prev);
 121     if (n_nodes > 1) {
 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);
 128       if (n_nodes > 2) {
 129         UInt32 n = n_nodes - 2;
 130         while (n-- > 0) {
 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);
 137           l_next = d_current;
 138           d_current = NULL;
 139         }
 140       }
 141     }
 142     d_available = d_current = l_prev;
 143     d_internal = new mld_mutex ();
 144     d_ioBlock = new mld_condition ();
 145   };
 146
 147   ~circular_linked_list () {
 148     iterate_start ();
 149     s_node_ptr l_node = iterate_next ();
 150     while (l_node) {
 151       delete l_node;
 152       l_node = iterate_next ();
 153     }
 154     delete d_internal;
 155     d_internal = NULL;
 156     delete d_ioBlock;
 157     d_ioBlock = NULL;
 158     d_available = d_inUse = d_iterate = d_current = NULL;
 159     d_n_used = d_n_nodes = 0;
 160   };
 161
 162   s_node_ptr find_next_available_node () {
 163     d_internal->lock ();
 164 // find an available node
 165     s_node_ptr l_node = d_available;
 166     while (! l_node) {
 167       d_internal->unlock ();
 168       d_ioBlock->wait ();
 169       d_internal->lock ();
 170       l_node = d_available;
 171     }
 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
 176       d_available = NULL;
 177     } else
 178       d_available = l_node->next ();
 179     l_node->remove ();
 180 // add is to the inUse list
 181     if (! d_inUse)
 182       d_inUse = l_node;
 183     else
 184       l_node->insert_before (d_inUse);
 185     d_n_used++;
 186     l_node->set_not_available ();
 187     d_internal->unlock ();
 188     return (l_node);
 189   };
 190
 191   void make_node_available (s_node_ptr l_node) {
 192     if (!l_node) return;
 193     d_internal->lock ();
 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
 198       d_inUse = NULL;
 199     } else
 200       d_inUse = l_node->next ();
 201     l_node->remove ();
 202 // add this node to the available list
 203     if (! d_available)
 204       d_available = l_node;
 205     else
 206       l_node->insert_before (d_available);
 207     d_n_used--;
 208 // signal the condition when new data arrives
 209     d_ioBlock->signal ();
 210 // unlock the mutex for thread safety
 211     d_internal->unlock ();
 212   };
 213
 214   __INLINE__ void iterate_start () { d_iterate = d_current; };
 215
 216   s_node_ptr iterate_next () {
 217 #if 0
 218 // lock the mutex for thread safety
 219     d_internal->lock ();
 220 #endif
 221     s_node_ptr l_this = NULL;
 222     if (d_iterate) {
 223       l_this = d_iterate;
 224       d_iterate = d_iterate->next ();
 225       if (d_iterate == d_current)
 226         d_iterate = NULL;
 227     }
 228 #if 0
 229 // unlock the mutex for thread safety
 230     d_internal->unlock ();
 231 #endif
 232     return (l_this);
 233   };
 234
 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;
 243   };
 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 ();
 248   };
 249   __INLINE__ bool in_use () { return (d_n_used != 0); };
 250 };
 251
 252 template <class T> class s_both
 253 {
 254 private:
 255   s_node<T>* d_node;
 256   void* d_this;
 257 public:
 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;};
 265 };
 266
 267 #endif /* _CIRCULAR_LINKED_LIST_H_ */