Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

Changeset 5229 in orxonox.OLD for trunk/src/lib


Ignore:
Timestamp:
Sep 23, 2005, 11:47:18 PM (19 years ago)
Author:
patrick
Message:

orxonox/trunk: remastered the tList class, some speed improvements and some security features. more documentation

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/lib/util/list.h

    r5211 r5229  
    2626
    2727   you will use this as a generic list for all type of objects
    28 */
     28 */
    2929template<class T> class tList
    3030{
    3131  friend class tIterator<T>;
    3232
    33  public:
    34   tList ();
    35   ~tList ();
    36 
    37   void add(T* entity);
    38   void addAtBeginning(T* entity); //!< @todo This should be made with an ENUM
    39   void remove(const T* entity);
    40   void removeLast();
    41   void flush();
    42   T* firstElement() const;
    43   T* lastElement() const;
    44   bool isEmpty() const;
    45   unsigned int getSize() const;
    46   bool inList(T* entity);
    47   tIterator<T>* getIterator() const;
    48   T* nextElement(T* toEntity);
    49   T* toArray();
    50 
    51  private:
    52   unsigned int       size;             //!< the size (lenght) of the list
    53   listElement<T>*    first;            //!< pointer to the first element
    54   listElement<T>*    last;             //!< pointer to the last element
    55   listElement<T>*    currentEl;        //!< pointer to the current element
     33  public:
     34    tList ();
     35    ~tList ();
     36
     37    void add(T* entity);
     38    void addAtBeginning(T* entity); //!< @todo This should be made with an ENUM
     39    void remove(const T* entity);
     40    void removeLast();
     41    void flush();
     42    T* firstElement() const;
     43    T* lastElement() const;
     44    bool isEmpty() const;
     45    unsigned int getSize() const;
     46    bool inList(T* entity) const;
     47    tIterator<T>* getIterator() const;
     48    T* nextElement(T* toEntity);
     49    T* toArray();
     50
     51  private:
     52    unsigned int       size;             //!< the size (lenght) of the list
     53    listElement<T>*    first;            //!< pointer to the first element
     54    listElement<T>*    last;             //!< pointer to the last element
     55    listElement<T>*    currentEl;        //!< pointer to the current element
    5656};
    5757
     
    5959/**
    6060 *  the constructor
    61 */
    62 template<class T>
    63 inline tList<T>::tList ()
    64 {
     61 */
     62template<class T>
     63    inline tList<T>::tList ()
     64{
     65  this->currentEl = NULL;
    6566  this->first = NULL;
    6667  this->last = NULL;
     
    7273 *  the deconstructor
    7374
    74    this will delete only the list. ATTENTION: the list is deleted, but the objects in the list will
    75    not be deleted
    76 */
    77 template<class T>
    78 inline tList<T>::~tList ()
     75   this will delete only the list. ATTENTION: the list is deleted, but the objects in the list will remain
     76 */
     77template<class T>
     78    inline tList<T>::~tList ()
    7979{
    8080  this->currentEl = this->first;
     81  listElement<T>* le;
    8182  while(this->currentEl != NULL)
    82     {
    83       listElement<T>* le = this->currentEl->next;
    84       //delete this->currentEl->curr;  //! THIS IS EXTREMELY UNSAFE (the list only stores pointers not instances) //
    85       delete this->currentEl;
    86       this->currentEl = le;
    87     }
     83  {
     84    le = this->currentEl->next;
     85    delete this->currentEl;
     86    this->currentEl = le;
     87  }
    8888  this->first = NULL;
    8989  this->last = NULL;
     90  this->currentEl = NULL;
    9091  this->size = 0;
    9192}
     
    9596 *  add an entity to the list
    9697 * @param entity: the entity to add
    97 */
    98 template<class T>
    99 inline void tList<T>::add(T* entity)
     98 */
     99template<class T>
     100    inline void tList<T>::add(T* entity)
    100101{
    101102  if( unlikely(entity == NULL)) return;
     
    127128  this->first = el;
    128129
    129   if( unlikely(el->next == NULL)) this->first = el; /* if first element */
     130  if( unlikely(el->next == NULL)) this->last = el; /* if first element */
    130131  else el->next->prev = el;
    131132  this->size++;
     
    136137 *  remove an entity from the list
    137138 * @param entity: the entity to be removed
    138 */
    139 template<class T>
    140 inline void tList<T>::remove(const T* entity)
     139 */
     140template<class T>
     141    inline void tList<T>::remove(const T* entity)
    141142{
    142143  this->currentEl = this->first;
    143144  while( this->currentEl != NULL)
     145  {
     146    if( unlikely(this->currentEl->curr == entity))
    144147    {
    145       if( unlikely(this->currentEl->curr == entity))
    146         {
    147           if( unlikely(this->currentEl->prev  == NULL)) this->first = this->currentEl->next;
    148           else this->currentEl->prev->next = this->currentEl->next;
    149 
    150           if( unlikely(this->currentEl->next == NULL)) this->last = this->currentEl->prev;
    151           else this->currentEl->next->prev = this->currentEl->prev;
    152 
    153           delete this->currentEl;
    154           this->size--;
    155           return;
    156         }
    157       this->currentEl = this->currentEl->next;
     148      // erstes element?
     149      if( unlikely(this->currentEl->prev == NULL)) this->first = this->currentEl->next;
     150      else this->currentEl->prev->next = this->currentEl->next;
     151
     152      // letztes element?
     153      if( unlikely(this->currentEl->next == NULL)) this->last = this->currentEl->prev;
     154      else this->currentEl->next->prev = this->currentEl->prev;
     155
     156      delete this->currentEl;
     157      this->size--;
     158      return;
    158159    }
    159 }
     160    this->currentEl = this->currentEl->next;
     161  }
     162}
     163
    160164
    161165/**
     
    165169     inline void tList<T>::removeLast()
    166170{
    167   if (this->last == NULL)
     171  if( unlikely(this->last == NULL))
    168172    return;
    169   else if (this->last == this->first)
     173
     174  // only one element in the list (and its not NULL :D )
     175  if( unlikely(this->last == this->first))
    170176  {
    171177    delete this->first;
     
    183189}
    184190
    185 /**
    186  *  this will deletes the objects from the list
    187 */
    188 template<class T>
    189 inline void tList<T>::flush()
     191
     192/**
     193 *  this will delete all objects from the list, this can be very dangerous if there are ghost objects in the list.
     194 */
     195template<class T>
     196    inline void tList<T>::flush()
    190197{
    191198  this->currentEl = this->first;
    192   while(this->currentEl != NULL)
    193     {
    194       listElement<T>* le = this->currentEl->next;
    195       delete this->currentEl->curr;
    196       delete this->currentEl;
    197       this->currentEl = le;
    198     }
     199
     200  listElement<T>* le;
     201  while( this->currentEl != NULL)
     202  {
     203    le = this->currentEl->next;
     204    delete this->currentEl->curr;
     205    delete this->currentEl;
     206    this->currentEl = le;
     207  }
    199208  this->first = NULL;
    200209  this->last = NULL;
     
    206215 *  returns the first element of the list
    207216 * @returns first element
    208 */
    209 template<class T>
    210 inline T* tList<T>::firstElement() const
     217 */
     218template<class T>
     219    inline T* tList<T>::firstElement() const
    211220{
    212221  return this->first->curr;
     
    217226 *  function returns the last element of the list
    218227 * @returns the last element
    219 */
    220 template<class T>
    221 inline T* tList<T>::lastElement() const
     228 */
     229template<class T>
     230    inline T* tList<T>::lastElement() const
    222231{
    223232  return this->last->curr;
     
    228237 *  returns true if the list is empty
    229238 * @returns true if the list is empty
    230 */
    231 template<class T>
    232 inline bool tList<T>::isEmpty() const
    233 {
    234   return (this->size==0)?true:false;
    235 }
    236 
    237 /**
    238  *  checks if an entity is in the List
     239 */
     240template<class T>
     241    inline bool tList<T>::isEmpty() const
     242{
     243  return (this->size == 0)?true:false;
     244}
     245
     246
     247/**
     248 *  checks if an entity is in the List.
    239249 * @param entity The entity to check for in the entire List.
    240250 * @returns true if it is, false otherwise
    241 */
    242 template<class T>
    243 inline bool tList<T>::inList(T* entity)
     251 */
     252template<class T>
     253    inline bool tList<T>::inList(T* entity) const
    244254{
    245255  // pre checks
    246   if(this->size == 0) return false;
    247   if( entity == NULL) return false;
     256  if( unlikely(entity == NULL)) return false;
    248257
    249258  // search in the List
    250   this->currentEl = this->first;
    251   while(this->currentEl->curr != entity && this->currentEl != NULL)
    252     this->currentEl = this->currentEl->next;
    253 
    254   // post checks
    255   if(this->currentEl == NULL)
    256     return false;
    257   else
    258     return true;
    259 }
     259  listElement<T>* el = this->first;
     260  while( this->currentEl != NULL)
     261  {
     262    if( this->currentEl->curr == entity)
     263      return true;
     264
     265    el = this->currentEl->next;
     266  }
     267}
     268
    260269
    261270/**
    262271 *  this returns the number of elements in the list
    263272 * @returns number of elements
    264 */
    265 template<class T>
    266 inline unsigned int tList<T>::getSize() const
     273 */
     274template<class T>
     275    inline unsigned int tList<T>::getSize() const
    267276{
    268277  return this->size;
     
    275284
    276285   You will use this, if you want to iterate through the list
    277 */
    278 template<class T>
    279 inline tIterator<T>* tList<T>::getIterator() const
     286 */
     287template<class T>
     288    inline tIterator<T>* tList<T>::getIterator() const
    280289{
    281290  return new tIterator<T>(this);
     
    288297 * @param toEntity: the entity after which is an entity, that has to be returned, sorry, terrible phrase
    289298 * @returns the element after toEntity
    290 */
    291 template<class T>
    292 inline T* tList<T>::nextElement(T* toEntity)
     299 */
     300template<class T>
     301    inline T* tList<T>::nextElement(T* toEntity)
    293302{
    294303  //if( this->last == this->first == NULL) return NULL;
     
    298307  this->currentEl = this->first;
    299308  while(this->currentEl->curr != toEntity && this->currentEl->next != NULL)
    300     {
    301       this->currentEl = this->currentEl->next;
    302     }
     309  {
     310    this->currentEl = this->currentEl->next;
     311  }
    303312  if(this->currentEl == NULL) return NULL;
    304313  return this->currentEl->next->curr;
     
    311320
    312321   ATTENTION: function is not implemented and wont do anything
    313 */
    314 template<class T>
    315 T* tList<T>::toArray()
     322 */
     323template<class T>
     324    T* tList<T>::toArray()
    316325{
    317326  return NULL;
     
    322331
    323332/**
    324  *  an iterator class
     333    *  an iterator class
    325334
    326335   this enables the user to iterate through a list very easely
     
    336345    T* nextElement();
    337346    T* prevElement();
    338     T* seekElement(T* element);
     347    T* seekElement(const T* element);
    339348    T* iteratorElement(const tIterator<T>* iterator);
    340349
     
    376385template<class T>
    377386    inline tIterator<T>::~tIterator ()
    378 {
    379 }
    380 
     387{}
     388
     389/**
     390 * this returns the first element of the iterator list
     391 * @returns first element
     392 */
    381393template<class T>
    382394    inline T* tIterator<T>::firstElement ()
    383395{
    384396  this->tmpEl = this->list->first;
    385   if (this->tmpEl != NULL)
     397  if( likely(this->tmpEl != NULL))
    386398  {
    387399    this->currentEl = this->tmpEl->next;
     
    392404}
    393405
     406/**
     407 * this returns the last element of the iterator list
     408 * @returns last element
     409 */
    394410template<class T>
    395411    inline T* tIterator<T>::lastElement ()
    396412{
    397413  this->tmpEl = this->list->last;
    398   if (this->tmpEl != NULL)
     414  if( likely(this->tmpEl != NULL))
    399415  {
    400416    this->currentEl = tmpEl->prev;
     
    413429    inline T* tIterator<T>::nextElement ()
    414430{
    415   if( this->currentEl == NULL)
     431  if( unlikely(this->currentEl == NULL))
    416432    return NULL;
    417433
     
    422438}
    423439
     440
    424441/**
    425442 *  use it to iterate backwards through the list
     
    429446    inline T* tIterator<T>::prevElement ()
    430447{
    431   if( this->currentEl == NULL)
     448  if( unlikely(this->currentEl == NULL))
    432449    return NULL;
    433450
     
    445462 */
    446463template<class T>
    447     inline T* tIterator<T>::seekElement (T* element)
    448 {
    449   if (element == NULL)
     464    inline T* tIterator<T>::seekElement (const T* element)
     465{
     466  if( unlikely(element == NULL))
    450467  {
    451468    this->currentEl = NULL;
     
    476493    T* tIterator<T>::iteratorElement(const tIterator<T>* iterator)
    477494{
    478   if (iterator != NULL && iterator->list == this->list)
     495  if( unlikely(iterator != NULL && iterator->list == this->list))
    479496  {
    480497    this->currentEl = iterator->currentEl;
Note: See TracChangeset for help on using the changeset viewer.