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