00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
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
00173 s_node_ptr l_node = d_available;
00174 DEBUG (fprintf (stderr, "w "););
00175 while (! l_node) {
00176 DEBUG (fprintf (stderr, "x\n"););
00177
00178 d_ioBlock->wait ();
00179
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
00186 if (num_available () == 1) {
00187
00188 d_available = NULL;
00189 } else
00190 d_available = l_node->next ();
00191 l_node->remove ();
00192
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
00209 if (num_used () == 1) {
00210
00211 d_inUse = NULL;
00212 } else
00213 d_inUse = l_node->next ();
00214 l_node->remove ();
00215
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
00224 d_ioBlock->signal ();
00225 DEBUG (fprintf (stderr, "t "););
00226
00227
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
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
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
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