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