C_MultiList.cpp Source File

00001 /*
00002  *  This program is free software; you can redistribute it and/or modify
00003  *  it under the terms of the GNU General Public License as published by
00004  *  the Free Software Foundation; either version 2 of the License, or
00005  *  (at your option) any later version.
00006  *
00007  *  This program is distributed in the hope that it will be useful,
00008  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00009  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00010  *  GNU General Public License for more details.
00011  *
00012  *  You should have received a copy of the GNU General Public License
00013  *  along with this program; if not, write to the Free Software
00014  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00015  *
00016  * (c)Copyright 2006 Hewlett-Packard Development Company, LP.
00017  *
00018  */
00019 
00020 /**********************************************************************
00021  * File      : C_MultiList.cpp
00022  * Purpose   :
00023  * Version   :
00024  * Author(s) : Xavier Bourvellec
00025  *
00026  * Creation  : 1998
00027  * Modif.    :
00028  *             - 1999 : JDH
00029  *             - 2000 : XBC : modified the one-big-scenario-list system for  
00030  *                            a less CPU consumming system : scenarios  
00031  *                            are now 'sorted' according their current 
00032  *                            state ( receiving , sending, waiting ) 
00033  *                            among lists representing these states. 
00034  *                            This allow doing loops only on scenarios states
00035  *                            which really need it ( namely :  SENDING,WAITING )
00036  *********************************************************************/
00037 
00038 #include "C_MultiList.hpp"
00039 #include "Utils.hpp"
00040 
00041 #include "iostream_t.hpp"
00042 #ifdef GEN_DEBUG_MULTILIST
00043 #define MLIST_GEN_DEBUG(m) iostream_error << m << iostream_flush << iostream_endl
00044 #define MLIST_GEN_FATAL(m) iostream_error << m << iostream_flush << iostream_endl
00045 #else
00046 #define MLIST_GEN_DEBUG(m) 
00047 #define MLIST_GEN_FATAL(m)
00048 #endif
00049 
00050 
00051 #include <cassert>
00052 
00053 /* PRIVATE *******************************************************************/
00054 
00055 template <class Type> int C_MultiList<Type>::removeElement ( long elementIdx )
00056 {
00057   int L_return = TST_OK ;
00058   long L_oldState ;
00059   long L_prev;
00060   long L_next;
00061 
00062 #ifdef GEN_DEBUG_MULTILIST
00063  if ( ! initDone )
00064  {
00065    MLIST_GEN_FATAL("initList has NOT been called before using list");
00066    assert (0);
00067  }
00068   MLIST_GEN_DEBUG("BEGIN removeElement, element=" << elementIdx << ", state=" << elementList[elementIdx].currentList);
00069 #endif /* GEN_DEBUG_MULTILIST */
00070 
00071   /* Get element chaining characteristics                                     */
00072   L_prev = elementList[elementIdx].prevElement ;
00073   L_next = elementList[elementIdx].nextElement ;
00074 
00075   /* Extract element list (which also specify the concerned list)             */
00076   L_oldState = elementList[elementIdx].currentList ;
00077 
00078   /* IF first pointer pointed on removed element                              */
00079   /* THEN IF last pointer pointed on removed element                          */
00080   /*      THEN sub-list becomes empty                                         */
00081   /*      ELSE next element becomes the new first pointed                     */
00082   /* ELSE IF last pointer pointed on removed element                          */
00083   /*      THEN previous element becomes the last pointed                      */
00084 
00085   if ( stateList[L_oldState].firstElement == elementIdx )
00086     {
00087       if ( stateList[L_oldState].lastElement == elementIdx )
00088       {
00089         /* It is the first and the last, so the alone element        */
00090         /* of the sub-list so makes the sub-list empty               */
00091         stateList[L_oldState].firstElement = NULL_INDEX_ELEMENT ;
00092         stateList[L_oldState].lastElement  = NULL_INDEX_ELEMENT ;
00093       }
00094       else
00095       {
00096         /* It is the first of a no empty list                        */
00097         /* The new first is the next one                             */
00098         stateList[L_oldState].firstElement = L_next ;
00099 
00100         /* unlink current element's 'next' from current element */
00101         elementList[L_next].prevElement = NULL_INDEX_ELEMENT ;
00102       }
00103     }
00104   else
00105     {
00106       if ( stateList[L_oldState].lastElement == elementIdx )
00107       {
00108         /* It is the last of a no empty list                         */
00109         /* The new last is the previous                              */
00110         stateList[L_oldState].lastElement = L_prev ;
00111 
00112         /* unlink current element's 'previous' from current element */
00113         elementList[L_prev].nextElement = NULL_INDEX_ELEMENT ;
00114       }
00115       else
00116       {
00117         /* It is an indifferent element of the sub-list              */
00118         elementList[L_next].prevElement = L_prev ;
00119         elementList[L_prev].nextElement = L_next ;
00120       }
00121     }
00122 
00123 #ifdef GEN_DEBUG_MULTILIST
00124     MLIST_GEN_DEBUG ("END removeElement, FirstIdle=" << stateList[L_oldState].firstElement
00125                 << ", LastIdle="  << stateList[L_oldState].lastElement);
00126 
00127 #endif /* GEN_DEBUG_MULTILIST */
00128 
00129   return ( L_return );
00130 }
00131 
00132 template <class Type> int C_MultiList<Type>::initSingleElement( long P_initState , long elementIdx )
00133 {
00134   int             L_return = TST_OK ;
00135 
00136   elementList[elementIdx].currentList      = P_initState ;
00137   /* Chain all elements */
00138   if ( elementIdx != 0 )
00139     {
00140       elementList[elementIdx].prevElement    = elementIdx-1 ;
00141     }
00142   else
00143     {
00144       elementList[elementIdx].prevElement    = NULL_INDEX_ELEMENT ;
00145     }
00146 
00147   if ( elementIdx != nbElements-1 )
00148     {
00149       elementList[elementIdx].nextElement    = elementIdx+1 ;
00150     }
00151   else
00152     {
00153       elementList[elementIdx].nextElement    = NULL_INDEX_ELEMENT ;
00154     }
00155 
00156   elementList[elementIdx].payLoad = NULL;
00157 
00158   return (L_return) ;
00159 }
00160 
00161 /* PUBLIC **************************************************************/
00162 
00163 template <class Type> C_MultiList<Type>::C_MultiList ( long numberOfLists, long numberOfElements )
00164 {
00165 
00166   firstListIndex = 0;
00167   lastListIndex = numberOfLists - 1;
00168   nbLists = numberOfLists;
00169   nbElements = numberOfElements;
00170 
00171   ALLOC_TABLE (elementList, struct_element*, 
00172                sizeof(struct_element), numberOfElements) ;
00173   ALLOC_TABLE (stateList, struct_listHeader*,
00174                sizeof(struct_listHeader), numberOfLists) ;
00175 
00176   initDone = 0;
00177 
00178   if (!elementList || !stateList )
00179   {
00180     iostream_error 
00181       << "C_MultiList class constructor : cannot allocate required memory (" 
00182       << numberOfLists  << " lists and " 
00183       << numberOfElements<< " elements )" << iostream_endl << iostream_flush ;
00184       assert (0);
00185   }
00186 };
00187 
00188 template <class Type> C_MultiList<Type>::~C_MultiList ( void )
00189 {
00190 #ifdef GEN_DEBUG_MULTILIST
00191   MLIST_GEN_DEBUG("C_MultiList destructor " << nbLists << " lists and " << nbElements << " elements ");
00192 #endif /* GEN_DEBUG_MULTILIST */
00193 
00194   FREE_TABLE (elementList);
00195   FREE_TABLE (stateList);
00196 };
00197 
00198 template <class Type> int C_MultiList<Type>::initList (long P_initState)
00199 {
00200   int L_return = TST_OK ;
00201   long  elementIdx = 0 ;
00202   long           listIndex = 0;
00203 
00204   /* test argument validity */
00205   if (P_initState >= firstListIndex && P_initState <= lastListIndex )
00206     {
00207       /* Initialize sub-list pointers                                          */
00208 
00209       for ( listIndex = 0 ; listIndex < nbLists ; listIndex ++ )
00210       {
00211         stateList[ listIndex ].firstElement  = NULL_INDEX_ELEMENT ;
00212         stateList[ listIndex ].lastElement   = NULL_INDEX_ELEMENT ;
00213         stateList[ listIndex ].nbElements    = 0;
00214       }
00215 
00216       stateList[P_initState].firstElement   = 0 ;
00217       stateList[P_initState].lastElement    = nbElements - 1;
00218       stateList[P_initState].nbElements     = nbElements;
00219 
00220       /* WHILE no error AND no all elements initialize DO                         */
00221       elementIdx = 0 ;
00222       while ( ( L_return == TST_OK ) && ( elementIdx < nbElements ) )
00223       {
00224         /* Initialize the <L_loop>th element                                     */
00225         L_return = initSingleElement( P_initState , elementIdx ) ;
00226         elementIdx ++ ;
00227       }
00228       /* END WHILE no error AND no all elements initialize DO                     */
00229       initDone = 1;
00230     }
00231   else
00232     {
00233       iostream_error << "GEN_ERROR : initList : P_initState=" 
00234                      <<  P_initState << iostream_endl ;
00235       L_return = TST_ERROR;
00236     }
00237 
00238   return (L_return) ;
00239 
00240 };
00241 
00242 template <class Type> int C_MultiList<Type>::moveToList (long listIdx, long elementIdx)
00243 {
00244   int L_return = TST_OK ;
00245   long prevElemList;
00246 
00247 #ifdef GEN_DEBUG_MULTILIST
00248     if ( ! initDone )
00249     {
00250       MLIST_GEN_FATAL("initList has NOT been called before using list");
00251       assert (0);
00252     }
00253     MLIST_GEN_DEBUG ("BEGIN C_MultiList::moveToList ( element " << elementIdx << " list " << listIdx << " )");
00254 #endif /* GEN_DEBUG_MULTILIST */
00255 
00256 #ifdef MLIST_ARGUMENTS_TESTING
00257 /* test argument validity */
00258   if (listIdx >= firstListIndex && listIdx <= lastListIndex && elementIdx != TST_ERROR   )
00259     {
00260 #endif /* MLIST_ARGUMENTS_TESTING */
00261 
00262       /* Get element list */
00263       prevElemList = elementList[elementIdx].currentList;
00264 
00265       /* Remove element from its current place                                    */
00266       L_return = removeElement ( elementIdx )  ;
00267 
00268       /* IF sub-list empty                                                     */
00269       if ( stateList[listIdx].lastElement == NULL_INDEX_ELEMENT )
00270       {
00271         /* THEN initialize sub-list                                                  */
00272         elementList[elementIdx].prevElement = NULL_INDEX_ELEMENT ;
00273         elementList[elementIdx].nextElement = NULL_INDEX_ELEMENT ;
00274         stateList[listIdx].firstElement     = elementIdx ;
00275         stateList[listIdx].lastElement      = elementIdx ;
00276       }
00277       else
00278       {
00279         /* ELSE Insert element at tail of 'listIdx' sub-list                     */
00280         /* - Next     field of old last  points on new element                   */
00281         /* - Previous field of new element  points on old last                   */
00282         /* - Next     field of new element  points on NULL                       */
00283         /* - Last  pointer               points on new element                   */
00284         elementList[stateList[listIdx].lastElement].nextElement = elementIdx ;
00285         elementList[elementIdx].prevElement = stateList[listIdx].lastElement ;
00286         elementList[elementIdx].nextElement = NULL_INDEX_ELEMENT ;
00287         stateList[listIdx].lastElement      = elementIdx ;
00288       }
00289       /* END IF sub-list empty                                                 */
00290 
00291       // decrement previous list counter
00292       stateList[prevElemList].nbElements --;
00293 
00294       // increment actual list counter
00295       stateList[listIdx].nbElements ++;
00296 
00297       // set element list to new one
00298       elementList[elementIdx].currentList = listIdx ;
00299 
00300 #ifdef MLIST_ARGUMENTS_TESTING
00301     }
00302   else
00303     {
00304       MLIST_GEN_DEBUG ("C_MultiList::moveToList : out of bounds arguments : list " << listIdx << " element " << elementIdx);
00305       assert (0); /* GEN_DEBUG */
00306       L_return = TST_ERROR;
00307     }
00308 #endif /* MLIST_ARGUMENTS_TESTING */
00309 
00310 
00311 #ifdef MLIST_INTERNAL_COHERENCE
00312   /* ++ GEN_DEBUG */
00313   long prevE = -1;
00314   long nextE = -1;
00315 
00316   prevE = elementList[elementIdx].nextElement;
00317   nextE = elementList[elementIdx].prevElement;
00318 
00319   if ( nextE != -1 )
00320     {
00321       if ( elementList[elementIdx].currentList != elementList[nextE].currentList )
00322       {
00323         MLIST_GEN_FATAL ("C_MultiList::moveToList: next element list is not the same as current elem list!!! ");
00324         assert (0);
00325       }
00326     }
00327 
00328   if ( prevE != -1 )
00329     {
00330       if ( elementList[elementIdx].currentList != elementList[prevE].currentList )
00331       {
00332         MLIST_GEN_FATAL ("C_MultiList::moveToList: prev element list is not the same as current elem list!!! ");
00333         assert (0);
00334       }
00335     }
00336 
00337   /* -- GEN_DEBUG */
00338 #endif /* MLIST_INTERNAL_COHERENCE */
00339   return ( L_return );
00340 };
00341 
00342 template <class Type> long C_MultiList<Type>::getFirst (long listIdx)
00343 {
00344 #ifdef GEN_DEBUG_MULTILIST
00345   MLIST_GEN_DEBUG("BEGIN getFirst " << listIdx);
00346 #endif /* GEN_DEBUG_MULTILIST */
00347 
00348 #ifdef MLIST_ARGUMENTS_TESTING
00349   if (listIdx >= firstListIndex && listIdx <= lastListIndex)
00350     {
00351 #  ifdef GEN_DEBUG_MULTILIST
00352     MLIST_GEN_DEBUG("END getFirst : returning " << stateList[listIdx].firstElement );
00353 #  endif /* GEN_DEBUG_MULTILIST */
00354 #endif /* MLIST_ARGUMENTS_TESTING */
00355       return ( stateList[listIdx].firstElement );
00356 #ifdef MLIST_ARGUMENTS_TESTING
00357     }
00358   else
00359     {
00360       MLIST_GEN_DEBUG ("END getFirst : out of bounds list index (" << listIdx << " while max index is " << lastListIndex << ")");
00361       assert (0); /* GEN_DEBUG */
00362       return (TST_ERROR);
00363     }
00364 #endif /* MLIST_ARGUMENTS_TESTING */
00365 };
00366 
00367 template <class Type> long C_MultiList<Type>::getNext (long elementIndex)
00368 {
00369 #ifdef GEN_DEBUG_MULTILIST
00370   MLIST_GEN_DEBUG("BEGIN getNext of element " << elementIndex);
00371 #endif /* GEN_DEBUG_MULTILIST */
00372 
00373 #ifdef MLIST_ARGUMENTS_TESTING
00374   if (elementIndex >= 0 && elementIndex < nbElements)
00375     {
00376 #     ifdef GEN_DEBUG_MULTILIST
00377      MLIST_GEN_DEBUG("END getNext : returning " << elementList[elementIndex].nextElement);
00378 #     endif /* GEN_DEBUG_MULTILIST */
00379 #endif /* MLIST_ARGUMENTS_TESTING */
00380       return ( elementList[elementIndex].nextElement );
00381 
00382 #ifdef MLIST_ARGUMENTS_TESTING
00383     }
00384   else
00385     {
00386       MLIST_GEN_DEBUG ("C_MultiList::getNext : out of bounds index ( " << elementIndex << " )");
00387       assert (0); /* GEN_DEBUG */
00388       return (TST_ERROR);
00389     }
00390 #endif /* MLIST_ARGUMENTS_TESTING */
00391 };
00392 
00393 template <class Type> int C_MultiList<Type>::isInState (long listIdx, long elementIndex)
00394 {
00395 #ifdef MLIST_ARGUMENTS_TESTING
00396   if (listIdx >= firstListIndex && listIdx <= lastListIndex && elementIndex >= 0 && elementIndex < nbElements )
00397     {
00398 #endif /* MLIST_ARGUMENTS_TESTING */
00399       return ( elementList[elementIndex].currentList == listIdx )
00400       ? 1 : 0 ;
00401 #ifdef MLIST_ARGUMENTS_TESTING
00402     }
00403   else
00404     {
00405       MLIST_GEN_DEBUG ("GEN_ERROR : isInState : out of bound indexes. Returning TST_ERROR, BEWARE.");
00406       return (TST_ERROR);
00407     }
00408 #endif /* MLIST_ARGUMENTS_TESTING */
00409 };
00410 
00411 template <class Type> long C_MultiList<Type>::getCurrentList (long elementIndex)
00412 {
00413 #ifdef MLIST_ARGUMENTS_TESTING
00414   if (elementIndex >= 0 && elementIndex < nbElements )
00415     {
00416 #endif /* MLIST_ARGUMENTS_TESTING */
00417 
00418       return ( elementList[elementIndex].currentList);
00419 
00420 #ifdef MLIST_ARGUMENTS_TESTING
00421     }
00422   else
00423     {
00424       MLIST_GEN_DEBUG("GEN_ERROR : isInState : out of bound indexes. Returning TST_ERROR, BEWARE.");
00425       return (TST_ERROR);
00426     }
00427 #endif /* MLIST_ARGUMENTS_TESTING */
00428 }
00429 
00430 template <class Type> Type * C_MultiList<Type>::getElementPayload ( long elementIndex)
00431 {
00432 
00433 #ifdef GEN_DEBUG_MULTILIST
00434     if ( ! initDone )
00435     {
00436       MLIST_GEN_FATAL("GEN_ERROR : getElementPayload : initList has NOT been called before using list");
00437       assert (0);
00438     }
00439 
00440 #endif /* GEN_DEBUG_MULTILIST */
00441 
00442 #ifdef MLIST_ARGUMENTS_TESTING
00443   if (elementIndex >= 0 && elementIndex < nbElements)
00444     {
00445 #endif /* MLIST_ARGUMENTS_TESTING */
00446       return ( elementList[elementIndex].payLoad );
00447 #ifdef MLIST_ARGUMENTS_TESTING
00448     }
00449   else
00450     {
00451       MLIST_GEN_DEBUG ("GEN_ERROR : getElementPayload : out of bounds element index ( " << elementIndex << " )");
00452       return (NULL);
00453     }
00454 #endif /* MLIST_ARGUMENTS_TESTING */
00455 }
00456 
00457 template <class Type> int C_MultiList<Type>::setElementPayload ( long elementIndex, Type * payLoad )
00458 {
00459 
00460 #ifdef GEN_DEBUG_MULTILIST
00461     if ( ! initDone )
00462     {
00463       MLIST_GEN_FATAL("GEN_ERROR : setElementPayload : initList has NOT been called before using list");
00464       assert (0);
00465     }
00466 #endif /* GEN_DEBUG_MULTILIST */
00467 
00468 #ifdef MLIST_ARGUMENTS_TESTING
00469   if (elementIndex >= 0 && elementIndex < nbElements )
00470     {
00471 #endif /* MLIST_ARGUMENTS_TESTING */
00472       elementList[elementIndex].payLoad = payLoad;
00473       return ( TST_OK );
00474 #ifdef MLIST_ARGUMENTS_TESTING
00475     }
00476   else
00477     {
00478       MLIST_GEN_DEBUG("GEN_ERROR : setElementPayload : out of bounds element index ( " << elementIndex << " )");
00479       return ( TST_ERROR );
00480     }
00481 #endif /* MLIST_ARGUMENTS_TESTING */
00482 }
00483 
00484 
00485 template <class Type> long C_MultiList<Type>::getNbElements ( long listIdx )
00486 {
00487 #ifdef GEN_DEBUG_MULTILIST
00488   MLIST_GEN_DEBUG("BEGIN getNbElements " << listIdx);
00489 #endif /* GEN_DEBUG_MULTILIST */
00490 
00491 #ifdef MLIST_ARGUMENTS_TESTING
00492   if (listIdx >= firstListIndex && listIdx <= lastListIndex)
00493     {
00494 #  ifdef GEN_DEBUG_MULTILIST
00495     MLIST_GEN_DEBUG("END getNbElements : returning " << stateList[listIdx].nbElements);
00496 #  endif /* GEN_DEBUG_MULTILIST */
00497 #endif /* MLIST_ARGUMENTS_TESTING */
00498       return ( stateList[listIdx].nbElements );
00499 #ifdef MLIST_ARGUMENTS_TESTING
00500     }
00501   else
00502     {
00503       MLIST_GEN_DEBUG("END getNbElements : out of bounds list index (" << listIdx << " while max index is " << lastListIndex << ")");
00504       assert (0); /* GEN_DEBUG */
00505       return (TST_ERROR);
00506     }
00507 #endif /* MLIST_ARGUMENTS_TESTING */
00508 }
00509 
00510 template <class Type> void C_MultiList<Type>::dump (void)
00511 {
00512   int L_int, L_cpt, L_cpt2, L_loop;
00513 
00514 #ifdef GEN_DEBUG_MULTILIST
00515     if ( ! initDone )
00516     {
00517       MLIST_GEN_FATAL("initList has NOT been called before using list");
00518       assert (0);
00519     }
00520 #endif /* GEN_DEBUG_MULTILIST */
00521 
00522   MLIST_GEN_DEBUG ("-- DUMP -----------------------");
00523   for (L_loop = 0; L_loop < nbLists; L_loop++)
00524     {
00525       L_int = stateList[L_loop].firstElement;
00526       L_cpt = 0;
00527 
00528       if (L_int != NULL_INDEX_ELEMENT)
00529       {
00530         L_cpt = 1;
00531       }
00532 
00533       while (L_int != stateList[L_loop].lastElement)
00534       {
00535         L_cpt++;
00536         L_int = elementList[L_int].nextElement;
00537         if (L_cpt > nbElements)
00538           L_int = stateList[L_loop].lastElement;
00539 
00540         if ( L_loop != elementList[L_int].currentList )
00541         {
00542             MLIST_GEN_FATAL ("(1) Element " << L_int << " found in list " << L_loop << " while having " << elementList[L_int].currentList << " as current list ???" );
00543             assert (0 );
00544         }
00545       }
00546 
00547       L_int = stateList[L_loop].lastElement;
00548       L_cpt2 = 0;
00549 
00550       if (L_int != NULL_INDEX_ELEMENT)
00551       {
00552         L_cpt2 = 1;
00553       }
00554 
00555       while (L_int != stateList[L_loop].firstElement)
00556       {
00557         L_cpt2++;
00558         L_int = elementList[L_int].prevElement;
00559         if (L_cpt2 > nbElements)
00560           {
00561           L_int = stateList[L_loop].firstElement;
00562           }
00563 
00564         if ( L_loop != elementList[L_int].currentList )
00565         {
00566             MLIST_GEN_FATAL ("(2) Element " << L_int << " found in list " << L_loop << " while having " << elementList[L_int].currentList << " as current list ???" );
00567             assert (0 );
00568         }
00569       }
00570       MLIST_GEN_DEBUG ("Nb elements in list [" << setw(6) << L_loop << "] compteur 1 :" << setw(6) << L_cpt << " compteur 2: " << setw(6) << L_cpt2 << " getNbElements " << getNbElements (L_loop) << " first element: " << setw(6) << stateList[L_loop].firstElement );
00571     }
00572     MLIST_GEN_DEBUG ("-- END OF DUMP -----------------" );
00573 };