1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/LibOVR/Src/Kernel/OVR_List.h	Wed Jan 14 06:51:16 2015 +0200
     1.3 @@ -0,0 +1,342 @@
     1.4 +/************************************************************************************
     1.5 +
     1.6 +PublicHeader:   OVR
     1.7 +Filename    :   OVR_List.h
     1.8 +Content     :   Template implementation for doubly-connected linked List
     1.9 +Created     :   September 19, 2012
    1.10 +Notes       : 
    1.11 +
    1.12 +Copyright   :   Copyright 2014 Oculus VR, LLC All Rights reserved.
    1.13 +
    1.14 +Licensed under the Oculus VR Rift SDK License Version 3.2 (the "License"); 
    1.15 +you may not use the Oculus VR Rift SDK except in compliance with the License, 
    1.16 +which is provided at the time of installation or download, or which 
    1.17 +otherwise accompanies this software in either electronic or hard copy form.
    1.18 +
    1.19 +You may obtain a copy of the License at
    1.20 +
    1.21 +http://www.oculusvr.com/licenses/LICENSE-3.2 
    1.22 +
    1.23 +Unless required by applicable law or agreed to in writing, the Oculus VR SDK 
    1.24 +distributed under the License is distributed on an "AS IS" BASIS,
    1.25 +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    1.26 +See the License for the specific language governing permissions and
    1.27 +limitations under the License.
    1.28 +
    1.29 +************************************************************************************/
    1.30 +
    1.31 +#ifndef OVR_List_h
    1.32 +#define OVR_List_h
    1.33 +
    1.34 +#include "OVR_Types.h"
    1.35 +
    1.36 +namespace OVR {
    1.37 +
    1.38 +//-----------------------------------------------------------------------------------
    1.39 +// ***** ListNode
    1.40 +//
    1.41 +// Base class for the elements of the intrusive linked list.
    1.42 +// To store elements in the List do:
    1.43 +//
    1.44 +// struct MyData : ListNode<MyData>
    1.45 +// {
    1.46 +//     . . .
    1.47 +// };
    1.48 +
    1.49 +template<class T>
    1.50 +struct ListNode
    1.51 +{
    1.52 +    union {
    1.53 +        T*    pPrev;
    1.54 +        void* pVoidPrev;
    1.55 +    };
    1.56 +    union {
    1.57 +        T*    pNext;
    1.58 +        void* pVoidNext;
    1.59 +    };
    1.60 +
    1.61 +    ListNode()
    1.62 +    {
    1.63 +        pPrev = NULL;
    1.64 +        pNext = NULL;
    1.65 +    }
    1.66 +
    1.67 +    void    RemoveNode()
    1.68 +    {
    1.69 +        pPrev->pNext = pNext;
    1.70 +        pNext->pPrev = pPrev;
    1.71 +    }
    1.72 +
    1.73 +    // Removes us from the list and inserts pnew there instead.
    1.74 +    void    ReplaceNodeWith(T* pnew)
    1.75 +    {
    1.76 +        pPrev->pNext = pnew;
    1.77 +        pNext->pPrev = pnew;
    1.78 +        pnew->pPrev = pPrev;
    1.79 +        pnew->pNext = pNext;
    1.80 +    }
    1.81 +       
    1.82 +    // Inserts the argument linked list node after us in the list.
    1.83 +    void    InsertNodeAfter(T* p)
    1.84 +    {
    1.85 +        p->pPrev          = pNext->pPrev; // this
    1.86 +        p->pNext          = pNext;
    1.87 +        pNext->pPrev      = p;
    1.88 +        pNext             = p;
    1.89 +    }
    1.90 +    // Inserts the argument linked list node before us in the list.
    1.91 +    void    InsertNodeBefore(T* p)
    1.92 +    {
    1.93 +        p->pNext          = pNext->pPrev; // this
    1.94 +        p->pPrev          = pPrev;
    1.95 +        pPrev->pNext      = p;
    1.96 +        pPrev             = p;
    1.97 +    }
    1.98 +
    1.99 +    void    Alloc_MoveTo(ListNode<T>* pdest)
   1.100 +    {
   1.101 +        pdest->pNext = pNext;
   1.102 +        pdest->pPrev = pPrev;
   1.103 +        pPrev->pNext = (T*)pdest;
   1.104 +        pNext->pPrev = (T*)pdest;
   1.105 +    }
   1.106 +};
   1.107 +
   1.108 +
   1.109 +//------------------------------------------------------------------------
   1.110 +// ***** List
   1.111 +//
   1.112 +// Doubly linked intrusive list. 
   1.113 +// The data type must be derived from ListNode.
   1.114 +// 
   1.115 +// Adding:   PushFront(), PushBack().
   1.116 +// Removing: Remove() - the element must be in the list!
   1.117 +// Moving:   BringToFront(), SendToBack() - the element must be in the list!
   1.118 +//
   1.119 +// Iterating:
   1.120 +//    MyData* data = MyList.GetFirst();
   1.121 +//    while (!MyList.IsNull(data))
   1.122 +//    {
   1.123 +//        . . .
   1.124 +//        data = MyList.GetNext(data);
   1.125 +//    }
   1.126 +//
   1.127 +// Removing:
   1.128 +//    MyData* data = MyList.GetFirst();
   1.129 +//    while (!MyList.IsNull(data))
   1.130 +//    {
   1.131 +//        MyData* next = MyList.GetNext(data);
   1.132 +//        if (ToBeRemoved(data))
   1.133 +//             MyList.Remove(data);
   1.134 +//        data = next;
   1.135 +//    }
   1.136 +//
   1.137 +
   1.138 +// List<> represents a doubly-linked list of T, where each T must derive
   1.139 +// from ListNode<B>. B specifies the base class that was directly
   1.140 +// derived from ListNode, and is only necessary if there is an intermediate
   1.141 +// inheritance chain.
   1.142 +
   1.143 +template<class T, class B = T> class List
   1.144 +{
   1.145 +public:
   1.146 +    typedef T ValueType;
   1.147 +
   1.148 +    List()
   1.149 +    {
   1.150 +        Root.pNext = Root.pPrev = (ValueType*)&Root;
   1.151 +    }
   1.152 +
   1.153 +    void Clear()
   1.154 +    {
   1.155 +        Root.pNext = Root.pPrev = (ValueType*)&Root;
   1.156 +    }
   1.157 +
   1.158 +    const ValueType* GetFirst() const { return (const ValueType*)Root.pNext; }
   1.159 +    const ValueType* GetLast () const { return (const ValueType*)Root.pPrev; }
   1.160 +          ValueType* GetFirst()       { return (ValueType*)Root.pNext; }
   1.161 +          ValueType* GetLast ()       { return (ValueType*)Root.pPrev; }
   1.162 +
   1.163 +    // Determine if list is empty (i.e.) points to itself.
   1.164 +    // Go through void* access to avoid issues with strict-aliasing optimizing out the
   1.165 +    // access after RemoveNode(), etc.
   1.166 +    bool IsEmpty()                   const { return Root.pVoidNext == (const T*)(const B*)&Root; }
   1.167 +    bool IsFirst(const ValueType* p) const { return p == Root.pNext; }
   1.168 +    bool IsLast (const ValueType* p) const { return p == Root.pPrev; }
   1.169 +    bool IsNull (const ValueType* p) const { return p == (const T*)(const B*)&Root; }
   1.170 +
   1.171 +    inline static const ValueType* GetPrev(const ValueType* p) { return (const ValueType*)p->pPrev; }
   1.172 +    inline static const ValueType* GetNext(const ValueType* p) { return (const ValueType*)p->pNext; }
   1.173 +    inline static       ValueType* GetPrev(      ValueType* p) { return (ValueType*)p->pPrev; }
   1.174 +    inline static       ValueType* GetNext(      ValueType* p) { return (ValueType*)p->pNext; }
   1.175 +
   1.176 +    void PushFront(ValueType* p)
   1.177 +    {
   1.178 +        p->pNext          =  Root.pNext;
   1.179 +        p->pPrev          = (ValueType*)&Root;
   1.180 +        Root.pNext->pPrev =  p;
   1.181 +        Root.pNext        =  p;
   1.182 +    }
   1.183 +
   1.184 +    void PushBack(ValueType* p)
   1.185 +    {
   1.186 +        p->pPrev          =  Root.pPrev;
   1.187 +        p->pNext          = (ValueType*)&Root;
   1.188 +        Root.pPrev->pNext =  p;
   1.189 +        Root.pPrev        =  p;
   1.190 +    }
   1.191 +
   1.192 +    static void Remove(ValueType* p)
   1.193 +    {
   1.194 +        p->pPrev->pNext = p->pNext;
   1.195 +        p->pNext->pPrev = p->pPrev;
   1.196 +    }
   1.197 +
   1.198 +    void BringToFront(ValueType* p)
   1.199 +    {
   1.200 +        Remove(p);
   1.201 +        PushFront(p);
   1.202 +    }
   1.203 +
   1.204 +    void SendToBack(ValueType* p)
   1.205 +    {
   1.206 +        Remove(p);
   1.207 +        PushBack(p);
   1.208 +    }
   1.209 +
   1.210 +    // Appends the contents of the argument list to the front of this list;
   1.211 +    // items are removed from the argument list.
   1.212 +    void PushListToFront(List<T>& src)
   1.213 +    {
   1.214 +        if (!src.IsEmpty())
   1.215 +        {
   1.216 +            ValueType* pfirst = src.GetFirst();
   1.217 +            ValueType* plast  = src.GetLast();
   1.218 +            src.Clear();
   1.219 +            plast->pNext   = Root.pNext;
   1.220 +            pfirst->pPrev  = (ValueType*)&Root;
   1.221 +            Root.pNext->pPrev = plast;
   1.222 +            Root.pNext        = pfirst;
   1.223 +        }
   1.224 +    }
   1.225 +
   1.226 +    void PushListToBack(List<T>& src)
   1.227 +    {
   1.228 +        if (!src.IsEmpty())
   1.229 +        {
   1.230 +            ValueType* pfirst = src.GetFirst();
   1.231 +            ValueType* plast  = src.GetLast();
   1.232 +            src.Clear();
   1.233 +            plast->pNext   = (ValueType*)&Root;
   1.234 +            pfirst->pPrev  = Root.pPrev;
   1.235 +            Root.pPrev->pNext = pfirst;
   1.236 +            Root.pPrev        = plast;
   1.237 +        }
   1.238 +    }
   1.239 +
   1.240 +    // Removes all source list items after (and including) the 'pfirst' node from the 
   1.241 +    // source list and adds them to out list.
   1.242 +    void    PushFollowingListItemsToFront(List<T>& src, ValueType *pfirst)
   1.243 +    {
   1.244 +        if (pfirst != &src.Root)
   1.245 +        {
   1.246 +            ValueType *plast = src.Root.pPrev;
   1.247 +
   1.248 +            // Remove list remainder from source.
   1.249 +            pfirst->pPrev->pNext = (ValueType*)&src.Root;
   1.250 +            src.Root.pPrev      = pfirst->pPrev;
   1.251 +            // Add the rest of the items to list.
   1.252 +            plast->pNext      = Root.pNext;
   1.253 +            pfirst->pPrev     = (ValueType*)&Root;
   1.254 +            Root.pNext->pPrev = plast;
   1.255 +            Root.pNext        = pfirst;
   1.256 +        }
   1.257 +    }
   1.258 +
   1.259 +    // Removes all source list items up to but NOT including the 'pend' node from the 
   1.260 +    // source list and adds them to out list.
   1.261 +    void    PushPrecedingListItemsToFront(List<T>& src, ValueType *ptail)
   1.262 +    {
   1.263 +        if (src.GetFirst() != ptail)
   1.264 +        {
   1.265 +            ValueType *pfirst = src.Root.pNext;
   1.266 +            ValueType *plast  = ptail->pPrev;
   1.267 +
   1.268 +            // Remove list remainder from source.
   1.269 +            ptail->pPrev      = (ValueType*)&src.Root;
   1.270 +            src.Root.pNext    = ptail;            
   1.271 +
   1.272 +            // Add the rest of the items to list.
   1.273 +            plast->pNext      = Root.pNext;
   1.274 +            pfirst->pPrev     = (ValueType*)&Root;
   1.275 +            Root.pNext->pPrev = plast;
   1.276 +            Root.pNext        = pfirst;
   1.277 +        }
   1.278 +    }
   1.279 +
   1.280 +
   1.281 +    // Removes a range of source list items starting at 'pfirst' and up to, but not including 'pend',
   1.282 +    // and adds them to out list. Note that source items MUST already be in the list.
   1.283 +    void    PushListItemsToFront(ValueType *pfirst, ValueType *pend)
   1.284 +    {
   1.285 +        if (pfirst != pend)
   1.286 +        {
   1.287 +            ValueType *plast = pend->pPrev;
   1.288 +
   1.289 +            // Remove list remainder from source.
   1.290 +            pfirst->pPrev->pNext = pend;
   1.291 +            pend->pPrev          = pfirst->pPrev;
   1.292 +            // Add the rest of the items to list.
   1.293 +            plast->pNext      = Root.pNext;
   1.294 +            pfirst->pPrev     = (ValueType*)&Root;
   1.295 +            Root.pNext->pPrev = plast;
   1.296 +            Root.pNext        = pfirst;
   1.297 +        }
   1.298 +    }
   1.299 +
   1.300 +
   1.301 +    void    Alloc_MoveTo(List<T>* pdest)
   1.302 +    {
   1.303 +        if (IsEmpty())
   1.304 +            pdest->Clear();
   1.305 +        else
   1.306 +        {
   1.307 +            pdest->Root.pNext = Root.pNext;
   1.308 +            pdest->Root.pPrev = Root.pPrev;
   1.309 +
   1.310 +            Root.pNext->pPrev = (ValueType*)&pdest->Root;
   1.311 +            Root.pPrev->pNext = (ValueType*)&pdest->Root;
   1.312 +        }        
   1.313 +    }
   1.314 +
   1.315 +
   1.316 +private:
   1.317 +    // Copying is prohibited
   1.318 +    List(const List<T>&);
   1.319 +    const List<T>& operator = (const List<T>&);
   1.320 +
   1.321 +    ListNode<B> Root;
   1.322 +};
   1.323 +
   1.324 +
   1.325 +//------------------------------------------------------------------------
   1.326 +// ***** FreeListElements
   1.327 +//
   1.328 +// Remove all elements in the list and free them in the allocator
   1.329 +
   1.330 +template<class List, class Allocator>
   1.331 +void FreeListElements(List& list, Allocator& allocator)
   1.332 +{
   1.333 +    typename List::ValueType* self = list.GetFirst();
   1.334 +    while(!list.IsNull(self))
   1.335 +    {
   1.336 +        typename List::ValueType* next = list.GetNext(self);
   1.337 +        allocator.Free(self);
   1.338 +        self = next;
   1.339 +    }
   1.340 +    list.Clear();
   1.341 +}
   1.342 +
   1.343 +} // OVR
   1.344 +
   1.345 +#endif