git.gag.com Git - debian/gnuradio/blob - usrp/host/lib/legacy/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 3, 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 #define DO_DEBUG 0
  31
  32 #if DO_DEBUG
  33 #define DEBUG(X) do{X} while(0);
  34 #else
  35 #define DEBUG(X) do{} while(0);
  36 #endif
  37
  38 template <class T> class s_both;
  39
  40 template <class T> class s_node
  41 {
  42   typedef s_node<T>* s_node_ptr;
  43
  44 private:
  45   T d_object;
  46   bool d_available;
  47   s_node_ptr d_prev, d_next;
  48   s_both<T>* d_both;
  49
  50 public:
  51   s_node (T l_object,
  52           s_node_ptr l_prev = NULL,
  53           s_node_ptr l_next = NULL)
  54     : d_object (l_object), d_available (TRUE), d_prev (l_prev),
  55     d_next (l_next), d_both (0) {};
  56
  57   __INLINE__ s_node (s_node_ptr l_prev, s_node_ptr l_next = NULL) {
  58     s_node ((T) NULL, l_prev, l_next); };
  59   __INLINE__ s_node () { s_node (NULL, NULL, NULL); };
  60   __INLINE__ ~s_node () {};
  61
  62   void remove () {
  63     d_prev->next (d_next);
  64     d_next->prev (d_prev);
  65     d_prev = d_next = this;
  66   };
  67
  68   void insert_before (s_node_ptr l_next) {
  69     if (l_next) {
  70       s_node_ptr l_prev = l_next->prev ();
  71       d_next = l_next;
  72       d_prev = l_prev;
  73       l_prev->next (this);
  74       l_next->prev (this);
  75     } else
  76       d_next = d_prev = this;
  77   };
  78
  79   void insert_after (s_node_ptr l_prev) {
  80     if (l_prev) {
  81       s_node_ptr l_next = l_prev->next ();
  82       d_prev = l_prev;
  83       d_next = l_next;
  84       l_next->prev (this);
  85       l_prev->next (this);
  86     } else
  87       d_prev = d_next = this;
  88   };
  89
  90   __INLINE__ T object () { return (d_object); };
  91   __INLINE__ void object (T l_object) { d_object = l_object; };
  92   __INLINE__ bool available () { return (d_available); };
  93   __INLINE__ void set_available () { d_available = TRUE; };
  94   __INLINE__ void set_available (bool l_avail) { d_available = l_avail; };
  95   __INLINE__ void set_not_available () { d_available = FALSE; };
  96   __INLINE__ s_node_ptr next () { return (d_next); };
  97   __INLINE__ s_node_ptr prev () { return (d_prev); };
  98   __INLINE__ s_both<T>* both () { return (d_both); };
  99   __INLINE__ void next (s_node_ptr l_next) { d_next = l_next; };
 100   __INLINE__ void prev (s_node_ptr l_prev) { d_prev = l_prev; };
 101   __INLINE__ void both (s_both<T>* l_both) { d_both = l_both; };
 102 };
 103
 104 template <class T> class circular_linked_list {
 105   typedef s_node<T>* s_node_ptr;
 106
 107 private:
 108   s_node_ptr d_current, d_iterate, d_available, d_inUse;
 109   UInt32 d_n_nodes, d_n_used;
 110   mld_mutex_ptr d_internal;
 111   mld_condition_ptr d_ioBlock;
 112
 113 public:
 114   circular_linked_list (UInt32 n_nodes) {
 115     if (n_nodes == 0)
 116       throw std::runtime_error ("circular_linked_list(): n_nodes == 0");
 117
 118     d_iterate = NULL;
 119     d_n_nodes = n_nodes;
 120     d_n_used = 0;
 121     s_node_ptr l_prev, l_next;
 122     d_inUse = d_current = l_next = l_prev = NULL;
 123
 124     l_prev = new s_node<T> ();
 125     l_prev->set_available ();
 126     l_prev->next (l_prev);
 127     l_prev->prev (l_prev);
 128     if (n_nodes > 1) {
 129       l_next = new s_node<T> (l_prev, l_prev);
 130       l_next->set_available ();
 131       l_next->next (l_prev);
 132       l_next->prev (l_prev);
 133       l_prev->next (l_next);
 134       l_prev->prev (l_next);
 135       if (n_nodes > 2) {
 136         UInt32 n = n_nodes - 2;
 137         while (n-- > 0) {
 138           d_current = new s_node<T> (l_prev, l_next);
 139           d_current->set_available ();
 140           d_current->prev (l_prev);
 141           d_current->next (l_next);
 142           l_prev->next (d_current);
 143           l_next->prev (d_current);
 144           l_next = d_current;
 145           d_current = NULL;
 146         }
 147       }
 148     }
 149     d_available = d_current = l_prev;
 150     d_ioBlock = new mld_condition ();
 151     d_internal = d_ioBlock->mutex ();
 152   };
 153
 154   ~circular_linked_list () {
 155     iterate_start ();
 156     s_node_ptr l_node = iterate_next ();
 157     while (l_node) {
 158       delete l_node;
 159       l_node = iterate_next ();
 160     }
 161     delete d_ioBlock;
 162     d_ioBlock = NULL;
 163     d_available = d_inUse = d_iterate = d_current = NULL;
 164     d_n_used = d_n_nodes = 0;
 165   };
 166
 167   s_node_ptr find_next_available_node () {
 168     d_internal->lock ();
 169 // find an available node
 170     s_node_ptr l_node = d_available;
 171     DEBUG (fprintf (stderr, "w "));
 172     while (! l_node) {
 173       DEBUG (fprintf (stderr, "x\n"));
 174       // the ioBlock condition will automatically unlock() d_internal
 175       d_ioBlock->wait ();
 176       // and lock() is here
 177       DEBUG (fprintf (stderr, "y\n"));
 178       l_node = d_available;
 179     }
 180     DEBUG (fprintf (stderr, "::f_n_a_n: #u = %ld, node = %p\n",
 181                     num_used(), l_node));
 182 // remove this one from the current available list
 183     if (num_available () == 1) {
 184 // last one, just set available to NULL
 185       d_available = NULL;
 186     } else
 187       d_available = l_node->next ();
 188     l_node->remove ();
 189 // add is to the inUse list
 190     if (! d_inUse)
 191       d_inUse = l_node;
 192     else
 193       l_node->insert_before (d_inUse);
 194     d_n_used++;
 195     l_node->set_not_available ();
 196     d_internal->unlock ();
 197     return (l_node);
 198   };
 199
 200   void make_node_available (s_node_ptr l_node) {
 201     if (!l_node) return;
 202     d_internal->lock ();
 203     DEBUG (fprintf (stderr, "::m_n_a: #u = %ld, node = %p\n",
 204                     num_used(), l_node));
 205 // remove this node from the inUse list
 206     if (num_used () == 1) {
 207 // last one, just set inUse to NULL
 208       d_inUse = NULL;
 209     } else
 210       d_inUse = l_node->next ();
 211     l_node->remove ();
 212 // add this node to the available list
 213     if (! d_available)
 214       d_available = l_node;
 215     else
 216       l_node->insert_before (d_available);
 217     d_n_used--;
 218
 219     DEBUG (fprintf (stderr, "s%ld ", d_n_used));
 220 // signal the condition when new data arrives
 221     d_ioBlock->signal ();
 222     DEBUG (fprintf (stderr, "t "));
 223
 224 // unlock the mutex for thread safety
 225     d_internal->unlock ();
 226   };
 227
 228   __INLINE__ void iterate_start () { d_iterate = d_current; };
 229
 230   s_node_ptr iterate_next () {
 231 #if 0
 232 // lock the mutex for thread safety
 233     d_internal->lock ();
 234 #endif
 235     s_node_ptr l_this = NULL;
 236     if (d_iterate) {
 237       l_this = d_iterate;
 238       d_iterate = d_iterate->next ();
 239       if (d_iterate == d_current)
 240         d_iterate = NULL;
 241     }
 242 #if 0
 243 // unlock the mutex for thread safety
 244     d_internal->unlock ();
 245 #endif
 246     return (l_this);
 247   };
 248
 249   __INLINE__ T object () { return (d_current->d_object); };
 250   __INLINE__ void object (T l_object) { d_current->d_object = l_object; };
 251   __INLINE__ UInt32 num_nodes () { return (d_n_nodes); };
 252   __INLINE__ UInt32 num_used () { return (d_n_used); };
 253   __INLINE__ void num_used (UInt32 l_n_used) { d_n_used = l_n_used; };
 254   __INLINE__ UInt32 num_available () { return (d_n_nodes - d_n_used); };
 255   __INLINE__ void num_used_inc (void) {
 256     if (d_n_used < d_n_nodes) ++d_n_used;
 257   };
 258   __INLINE__ void num_used_dec (void) {
 259     if (d_n_used != 0) --d_n_used;
 260 // signal the condition that new data has arrived
 261     d_ioBlock->signal ();
 262   };
 263   __INLINE__ bool in_use () { return (d_n_used != 0); };
 264 };
 265
 266 template <class T> class s_both
 267 {
 268 private:
 269   s_node<T>* d_node;
 270   void* d_this;
 271 public:
 272   __INLINE__ s_both (s_node<T>* l_node, void* l_this)
 273     : d_node (l_node), d_this (l_this) {};
 274   __INLINE__ ~s_both () {};
 275   __INLINE__ s_node<T>* node () { return (d_node); };
 276   __INLINE__ void* This () { return (d_this); };
 277   __INLINE__ void set (s_node<T>* l_node, void* l_this) {
 278     d_node = l_node; d_this = l_this;};
 279 };
 280
 281 #endif /* _CIRCULAR_LINKED_LIST_H_ */