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