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 <gruel/thread.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 size_t d_n_nodes, d_n_used;
00113 gruel::mutex* d_internal;
00114 gruel::condition_variable* d_ioBlock;
00115
00116 public:
00117 circular_linked_list (size_t 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 size_t 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 gruel::condition_variable ();
00154 d_internal = new gruel::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 delete d_internal;
00167 d_internal = NULL;
00168 d_available = d_inUse = d_iterate = d_current = NULL;
00169 d_n_used = d_n_nodes = 0;
00170 };
00171
00172 s_node_ptr find_next_available_node () {
00173 gruel::scoped_lock l (*d_internal);
00174
00175 s_node_ptr l_node = d_available;
00176 DEBUG (std::cerr << "w ");
00177 while (! l_node) {
00178 DEBUG (std::cerr << "x" << std::endl);
00179
00180 d_ioBlock->wait (l);
00181
00182 DEBUG (std::cerr << "y" << std::endl);
00183 l_node = d_available;
00184 }
00185 DEBUG (std::cerr << "::f_n_a_n: #u = " << num_used()
00186 << ", node = " << l_node << std::endl);
00187
00188 if (num_available () == 1) {
00189
00190 d_available = NULL;
00191 } else
00192 d_available = l_node->next ();
00193 l_node->remove ();
00194
00195 if (! d_inUse)
00196 d_inUse = l_node;
00197 else
00198 l_node->insert_before (d_inUse);
00199 d_n_used++;
00200 l_node->set_not_available ();
00201 return (l_node);
00202 };
00203
00204 void make_node_available (s_node_ptr l_node) {
00205 if (!l_node) return;
00206 gruel::scoped_lock l (*d_internal);
00207 DEBUG (std::cerr << "::m_n_a: #u = " << num_used()
00208 << ", node = " << l_node << std::endl);
00209
00210 if (num_used () == 1) {
00211
00212 d_inUse = NULL;
00213 } else
00214 d_inUse = l_node->next ();
00215 l_node->remove ();
00216
00217 if (! d_available)
00218 d_available = l_node;
00219 else
00220 l_node->insert_before (d_available);
00221 d_n_used--;
00222
00223 DEBUG (std::cerr << "s" << d_n_used);
00224
00225 d_ioBlock->notify_one ();
00226 DEBUG (std::cerr << "t ");
00227 };
00228
00229 __INLINE__ void iterate_start () { d_iterate = d_current; };
00230
00231 s_node_ptr iterate_next () {
00232 #if 0
00233
00234 gruel::scoped_lock l (*d_internal);
00235 #endif
00236 s_node_ptr l_this = NULL;
00237 if (d_iterate) {
00238 l_this = d_iterate;
00239 d_iterate = d_iterate->next ();
00240 if (d_iterate == d_current)
00241 d_iterate = NULL;
00242 }
00243 return (l_this);
00244 };
00245
00246 __INLINE__ T object () { return (d_current->d_object); };
00247 __INLINE__ void object (T l_object) { d_current->d_object = l_object; };
00248 __INLINE__ size_t num_nodes () { return (d_n_nodes); };
00249 __INLINE__ size_t num_used () { return (d_n_used); };
00250 __INLINE__ void num_used (size_t l_n_used) { d_n_used = l_n_used; };
00251 __INLINE__ size_t num_available () { return (d_n_nodes - d_n_used); };
00252 __INLINE__ void num_used_inc (void) {
00253 if (d_n_used < d_n_nodes) ++d_n_used;
00254 };
00255 __INLINE__ void num_used_dec (void) {
00256 if (d_n_used != 0) --d_n_used;
00257
00258 d_ioBlock->notify_one ();
00259 };
00260 __INLINE__ bool in_use () { return (d_n_used != 0); };
00261 };
00262
00263 template <class T> class s_both
00264 {
00265 private:
00266 s_node<T>* d_node;
00267 void* d_this;
00268 public:
00269 __INLINE__ s_both (s_node<T>* l_node, void* l_this)
00270 : d_node (l_node), d_this (l_this) {};
00271 __INLINE__ ~s_both () {};
00272 __INLINE__ s_node<T>* node () { return (d_node); };
00273 __INLINE__ void* This () { return (d_this); };
00274 __INLINE__ void set (s_node<T>* l_node, void* l_this) {
00275 d_node = l_node; d_this = l_this;};
00276 };
00277
00278 #endif