FList.hpp 8.41 KB
Newer Older
1
// ===================================================================================
2 3 4 5 6 7 8 9
// Logiciel initial: ScalFmm Version 0.5
// Co-auteurs : Olivier Coulaud, Bérenger Bramas.
// Propriétaires : INRIA.
// Copyright © 2011-2012, diffusé sous les termes et conditions d’une licence propriétaire.
// Initial software: ScalFmm Version 0.5
// Co-authors: Olivier Coulaud, Bérenger Bramas.
// Owners: INRIA.
// Copyright © 2011-2012, spread under the terms and conditions of a proprietary license.
10
// ===================================================================================
11 12
#ifndef FLIST_HPP
#define FLIST_HPP
13

14 15 16

#include "../Utils/FGlobal.hpp"

17

18 19 20 21 22 23 24 25 26 27 28 29
/**
 * @author Berenger Bramas (berenger.bramas@inria.fr)
 * @class FList
 * Please read the license
 *
 * This class is a linked list container.
 * It is a very basic list to enable strong performance.
 *
 * Please refere to unit test flistUTest.cpp to know more.
 */
template< class Object >
class FList {
30 31 32 33 34
    /** A list node */
    struct Node {
        Object target;	//< Object of the node
        Node* next;	//< Next node
    };
35

36 37
    Node* root; //< Root node, NULL if size is 0
    int size;   //< Elements in the list
38

39
    /**
40 41 42
        * Copy a list into current object
        * The current list has to be empty when this function is called
        */
43 44 45 46 47 48 49 50 51 52 53
    void copy(const FList& other){
        // on iterator on the current list, another for the original list
        const Node* FRestrict  otherRoot = other.root;
        Node * FRestrict * myRoot = &this->root;
        // create, copy and progress
        while(otherRoot){
            (*myRoot) = new Node;
            (*myRoot)->target = otherRoot->target;

            myRoot = &(*myRoot)->next;
            otherRoot = otherRoot->next;
54
        }
55 56 57 58
        // End with null
        *myRoot = 0;
        this->size = other.size;
    }
59 60

public:
61
    typedef Object ValueType; /**< data type of data in FVector */
62

63 64 65
    /** Constructor (of an empty list) */
    FList() : root(0) , size(0) {
    }
66

67 68 69 70
    /** Desctructor */
    virtual ~FList(){
        clear();
    }
71

72
    /**
73 74 75
        * Copy operator
        * This will clear the current list before copying
        * @param other the source list
76
        * @return the current list as a reference
77
        */
78 79 80 81
    FList& operator=(const FList& other){
        if(this != &other){
            clear();
            copy(other);
82
        }
83 84
        return *this;
    }
85

86
    /**
87
        * Copy constructor
88
        * @param other the source/original list
89
        */
90 91 92
    FList(const FList& other): root(0) , size(0)  {
        copy(other);
    }
93

94
    /**
95 96 97
        * To clear the list
        * Size is 0 after calling this function
        */
98 99 100 101 102
    void clear(){
        while(this->root){
            Node*const FRestrict next = this->root->next;
            delete this->root;
            this->root = next;
103
        }
104 105
        this->size = 0;
    }
106

107
    /**
berenger-bramas's avatar
berenger-bramas committed
108
        * Push an element in the head of the list
109
        * @param inObject the object to insert
110
        */
111 112 113 114
    void push(const Object& inObject){
        Node* newNode   = new Node;
        newNode->target = inObject;
        newNode->next 	= this->root;
115

116 117 118
        this->root 	= newNode;
        ++this->size;
    }
119 120


121
    /**
berenger-bramas's avatar
berenger-bramas committed
122
        * To get head value (last pushed value)
123 124 125
        * the list is unchanged after this function
        * @param defaultValue as the returned value in case size == 0, equal Object() if no param as passed
        * @return first value if exists or defaultValue otherwise
126
        * FList does not check that size != 0
127
        */
128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154
    Object& head(/*Object& defaultValue = Object()*/){
        return this->root->target;
    }

    /**
    * To get head value as const
    * the list is unchanged after this function
    * @param defaultValue as the returned value in case size == 0, equal Object() if no param as passed
    * @return first value if exists or defaultValue otherwise
    * FList does not check that size != 0
    */
    const Object& head(/*const Object& defaultValue = Object()*/) const {
        return this->root->target;
    }

    /**
    * To remove the head value from the list
    * @warning you must check the list's size before calling this function!
    */
    void pop(){
        --this->size;
        Node*const FRestrict headNode  = this->root;
        this->root                     = this->root->next;
        delete headNode;
    }

    /**
155 156 157
        * To get the number of elements in the list
        * @return size
        */
158 159 160
    int getSize() const{
        return this->size;
    }
161

162
    /**
163 164 165 166 167 168 169
          * This iterator allow accessing list's elements
          * If you change the target list pointed by an iterator
          * you cannot used the iterator any more.
          * <code>
          * FList<int> values; <br>
          * // inserting ... <br>
          * FList<int>::BasicIterator iter(values); <br>
berenger-bramas's avatar
berenger-bramas committed
170 171
          * while( iter.hasNotFinished() ){ <br>
          *     iter.data() += 1; <br>
berenger-bramas's avatar
berenger-bramas committed
172
          *     iter.gotoNext(); <br>
173 174 175
          * } <br>
          * </code>
          */
176 177 178
    class BasicIterator {
    private:
        Node** iter; //< current node on the list
179

180 181 182 183 184 185 186
    public:
        /**
          * Constructor needs the target list
          * @param the list to iterate on
          */
        explicit BasicIterator(FList& list) : iter(&list.root) {
        }
187

188 189 190 191 192 193
        /** To gotoNext on the list */
        void gotoNext(){
            if( hasNotFinished() ){
                // TODO bug! printf("%s %p to %p\n",((*iter) != 0?"Not null":"Null"), *iter, &((*iter)->next));
                iter = &((*iter)->next);
                if( (*iter)->next ) Prefetch_Write( (*iter)->next->next);
194
            }
195
        }
196

197
        /**
198
            * Current pointed value
berenger-bramas's avatar
berenger-bramas committed
199
            * current iterator must be valide (hasNotFinished()) to use this function
200
            */
201 202 203
        Object& data(){
            return (*iter)->target;
        }
204

205
        /**
206
            * Current pointed value
berenger-bramas's avatar
berenger-bramas committed
207
            * current iterator must be valide (hasNotFinished()) to use this function
208
            */
209 210 211
        const Object& data() const{
            return (*iter)->target;
        }
212

213 214 215 216
        /** Set the data */
        void setData(const Object& inData){
            (*iter)->target = inData;
        }
217

218
        /**
219
            * To know if an iterator is at the end of the list
berenger-bramas's avatar
berenger-bramas committed
220
            * @return true if the current iterator can gotoNext and access to value, else false
221
            */
222 223 224
        bool hasNotFinished() const{
            return (*iter) != 0;
        }
225

226
        /** Remove an element
227
              */
228 229 230 231 232
        void remove() {
            if( hasNotFinished() ){
                Node* temp = (*iter)->next;
                delete (*iter);
                (*iter) = temp;
233
            }
234
        }
235

236
    };
237

238
    /**
239 240 241 242 243 244 245
          * This iterator allow accessing list's elements
          * If you change the target list pointed by an iterator
          * you cannot used the iterator any more.
          * <code>
          * FList<int> values; <br>
          * // inserting ... <br>
          * FList<int>::ConstBasicIterator iter(values); <br>
berenger-bramas's avatar
berenger-bramas committed
246 247
          * while( iter.hasNotFinished() ){ <br>
          *     iter.data() += 1; <br>
berenger-bramas's avatar
berenger-bramas committed
248
          *     iter.gotoNext(); <br>
249 250 251
          * } <br>
          * </code>
          */
252 253 254
    class ConstBasicIterator {
    private:
        const Node* iter; //< current node on the list
255

256 257
    public:
        /**
258 259 260
              * Constructor needs the target list
              * @param the list to iterate on
              */
261 262
        explicit ConstBasicIterator(const FList& list) : iter(list.root){
        }
263

264 265 266 267 268
        /** to gotoNext on the list */
        void gotoNext(){
            if(this->iter){
                this->iter = this->iter->next;
                if(this->iter) Prefetch_Read(this->iter->next);
269
            }
270
        }
271

272
        /**
273
            * Current pointed value
berenger-bramas's avatar
berenger-bramas committed
274
            * current iterator must be valide (hasNotFinished()) to use this function
275
            */
276 277 278
        Object data(){
            return this->iter->target;
        }
279

280
        /**
281
            * Current pointed value
berenger-bramas's avatar
berenger-bramas committed
282
            * current iterator must be valide (hasNotFinished()) to use this function
283
            */
284 285 286
        const Object& data() const{
            return this->iter->target;
        }
287

288
        /**
289
            * To know if an iterator is at the end of the list
berenger-bramas's avatar
berenger-bramas committed
290
            * @return true if the current iterator can gotoNext and access to value, else false
291
            */
292 293 294 295
        bool hasNotFinished() const{
            return iter;
        }
    };
296 297

};
298

299
#endif //FLIST_HPP
300