leveled.cpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028 #define FREPPLE_CORE
00029 #include "frepple/model.h"
00030 #include <climits>
00031
00032
00033
00034
00035
00036
00037
00038 namespace frepple
00039 {
00040
00041
00042 DECLARE_EXPORT bool HasLevel::recomputeLevels = false;
00043 DECLARE_EXPORT bool HasLevel::computationBusy = false;
00044 DECLARE_EXPORT short unsigned HasLevel::numberOfClusters = 0;
00045 DECLARE_EXPORT short unsigned HasLevel::numberOfHangingClusters = 0;
00046
00047
00048 DECLARE_EXPORT void HasLevel::computeLevels()
00049 {
00050 computationBusy = true;
00051
00052 static Mutex levelcomputationbusy;
00053 ScopeMutexLock l(levelcomputationbusy);
00054
00055
00056
00057 while (recomputeLevels)
00058 {
00059
00060
00061
00062 recomputeLevels = false;
00063
00064
00065 for (Buffer::iterator gbuf = Buffer::begin();
00066 gbuf != Buffer::end(); ++gbuf)
00067 {
00068 gbuf->cluster = 0;
00069 gbuf->lvl = -1;
00070 }
00071 for (Resource::iterator gres = Resource::begin();
00072 gres != Resource::end(); ++gres)
00073 {
00074 gres->cluster = 0;
00075 gres->lvl = -1;
00076 }
00077 for (Operation::iterator gop = Operation::begin();
00078 gop != Operation::end(); ++gop)
00079 {
00080 gop->cluster = 0;
00081 gop->lvl = -1;
00082 }
00083
00084
00085 stack< pair<Operation*,int> > stack;
00086 Operation* cur_oper;
00087 int cur_level;
00088 Buffer *cur_buf;
00089 const Flow* cur_Flow;
00090 bool search_level;
00091 int cur_cluster;
00092 numberOfClusters = 0;
00093 numberOfHangingClusters = 0;
00094 map<Operation*,short> visited;
00095 for (Operation::iterator g = Operation::begin();
00096 g != Operation::end(); ++g)
00097 {
00098
00099 #ifdef CLUSTERDEBUG
00100 logger << "Investigating operation '" << &*g
00101 << "' - current cluster " << g->cluster << endl;
00102 #endif
00103
00104
00105 if (g->cluster)
00106 cur_cluster = g->cluster;
00107 else
00108 {
00109 cur_cluster = ++numberOfClusters;
00110 if (numberOfClusters >= USHRT_MAX)
00111 throw LogicException("Too many clusters");
00112
00113
00114 if (g->getFlows().empty() && g->getLoads().empty()
00115 && g->getSuperOperations().empty()
00116 && g->getSubOperations().empty()
00117 )
00118 {
00119 ++numberOfHangingClusters;
00120 g->lvl = 0;
00121 continue;
00122 }
00123 }
00124
00125
00126
00127
00128
00129
00130 search_level = false;
00131 if (g->getSuperOperations().empty())
00132 {
00133 search_level = true;
00134
00135 for (Operation::flowlist::const_iterator fl = g->getFlows().begin();
00136 fl != g->getFlows().end() && search_level; ++fl)
00137 if (fl->isProducer()) search_level = false;
00138 if (search_level)
00139 {
00140
00141 for (Operation::Operationlist::const_reverse_iterator
00142 i = g->getSubOperations().rbegin();
00143 i != g->getSubOperations().rend() && search_level;
00144 ++i)
00145 for (Operation::flowlist::const_iterator
00146 fl = (*i)->getFlows().begin();
00147 fl != (*i)->getFlows().end() && search_level;
00148 ++fl)
00149 if (fl->isProducer()) search_level = false;
00150 }
00151 }
00152
00153
00154 if (!search_level && g->cluster) continue;
00155
00156
00157
00158
00159
00160 stack.push(make_pair(&*g, search_level ? 0 : -1));
00161 visited.clear();
00162 g->cluster = cur_cluster;
00163 if (search_level) g->lvl = 0;
00164 while (!stack.empty())
00165 {
00166
00167 cur_oper = stack.top().first;
00168 cur_level = stack.top().second;
00169 stack.pop();
00170
00171 #ifdef CLUSTERDEBUG
00172 logger << " Recursing in Operation '" << *(cur_oper)
00173 << "' - current level " << cur_level << endl;
00174 #endif
00175
00176 map<Operation*,short>::iterator detectloop = visited.find(cur_oper);
00177 if (detectloop == visited.end())
00178
00179 visited.insert(make_pair(cur_oper,0));
00180 else if (++(detectloop->second) > 1)
00181
00182 continue;
00183
00184
00185 for (Operation::Operationlist::const_reverse_iterator
00186 i = cur_oper->getSubOperations().rbegin();
00187 i != cur_oper->getSubOperations().rend();
00188 ++i)
00189 {
00190 if ((*i)->lvl < cur_level)
00191 {
00192
00193 stack.push(make_pair(*i,cur_level));
00194 (*i)->lvl = cur_level;
00195 (*i)->cluster = cur_cluster;
00196 }
00197 else if (!(*i)->cluster)
00198 {
00199
00200 stack.push(make_pair(*i,-1));
00201 (*i)->cluster = cur_cluster;
00202 }
00203
00204 }
00205
00206
00207 for (Operation::Operationlist::const_reverse_iterator
00208 j = cur_oper->getSuperOperations().rbegin();
00209 j != cur_oper->getSuperOperations().rend();
00210 ++j)
00211 {
00212 if ((*j)->lvl < cur_level)
00213 {
00214
00215 stack.push(make_pair(*j,cur_level));
00216 (*j)->lvl = cur_level;
00217 (*j)->cluster = cur_cluster;
00218 }
00219 else if (!(*j)->cluster)
00220 {
00221
00222 stack.push(make_pair(*j,-1));
00223 (*j)->cluster = cur_cluster;
00224 }
00225
00226 }
00227
00228
00229 for (Operation::loadlist::const_iterator gres =
00230 cur_oper->getLoads().begin();
00231 gres != cur_oper->getLoads().end(); ++gres)
00232 {
00233 Resource *resptr = gres->getResource();
00234
00235 if (resptr->lvl < cur_level) resptr->lvl = cur_level;
00236
00237 if (!resptr->cluster)
00238 {
00239 resptr->cluster = cur_cluster;
00240
00241 for (Resource::loadlist::const_iterator resops =
00242 resptr->getLoads().begin();
00243 resops != resptr->getLoads().end(); ++resops)
00244 if (!resops->getOperation()->cluster)
00245 {
00246 stack.push(make_pair(resops->getOperation(),-1));
00247 resops->getOperation()->cluster = cur_cluster;
00248 }
00249 }
00250 }
00251
00252
00253 for (Operation::flowlist::const_iterator
00254 gflow = cur_oper->getFlows().begin();
00255 gflow != cur_oper->getFlows().end();
00256 ++gflow)
00257 {
00258 cur_Flow = &*gflow;
00259 cur_buf = cur_Flow->getBuffer();
00260
00261
00262 search_level = cur_level!=-1 && cur_buf->lvl<cur_level+1;
00263
00264
00265 if (search_level || !cur_buf->cluster)
00266 {
00267
00268 cur_buf->cluster = cur_cluster;
00269
00270
00271 for (Buffer::flowlist::const_iterator
00272 buffl = cur_buf->getFlows().begin();
00273 buffl != cur_buf->getFlows().end();
00274 ++buffl)
00275 {
00276
00277 if (cur_Flow->isConsumer() && search_level)
00278 {
00279 if (buffl->getOperation()->lvl < cur_level+1
00280 && &*buffl != cur_Flow && buffl->isProducer())
00281 {
00282 stack.push(make_pair(buffl->getOperation(),cur_level+1));
00283 buffl->getOperation()->lvl = cur_level+1;
00284 buffl->getOperation()->cluster = cur_cluster;
00285 }
00286 else if (!buffl->getOperation()->cluster)
00287 {
00288 stack.push(make_pair(buffl->getOperation(),-1));
00289 buffl->getOperation()->cluster = cur_cluster;
00290 }
00291 cur_buf->lvl = cur_level+1;
00292 }
00293
00294 else if (!buffl->getOperation()->cluster)
00295 {
00296 stack.push(make_pair(buffl->getOperation(),-1));
00297 buffl->getOperation()->cluster = cur_cluster;
00298 }
00299 }
00300 }
00301 }
00302
00303 }
00304
00305 }
00306
00307
00308
00309
00310
00311 for (Buffer::iterator gbuf2 = Buffer::begin();
00312 gbuf2 != Buffer::end(); ++gbuf2)
00313 if (gbuf2->getFlows().empty())
00314 {
00315 gbuf2->cluster = ++numberOfClusters;
00316 if (numberOfClusters >= USHRT_MAX)
00317 throw LogicException("Too many clusters");
00318 ++numberOfHangingClusters;
00319 }
00320 for (Resource::iterator gres2 = Resource::begin();
00321 gres2 != Resource::end(); ++gres2)
00322 if (gres2->getLoads().empty())
00323 {
00324 gres2->cluster = ++numberOfClusters;
00325 if (numberOfClusters >= USHRT_MAX)
00326 throw LogicException("Too many clusters");
00327 ++numberOfHangingClusters;
00328 }
00329
00330 }
00331
00332
00333
00334 computationBusy = false;
00335 }
00336
00337 }