← Back to branch summary

~siretart/ubuntu/utopic/blender/libav10

« back to all changes in this revision

Viewing changes to extern/recastnavigation/Detour/Include/DetourNode.h

  • Committer: Package Import Robot
  • Author(s): Matteo F. Vescovi
  • Date: 2012-07-23 08:54:18 UTC
  • mfrom: (14.2.16 sid)
  • mto: (14.2.19 sid)
  • mto: This revision was merged to the branch mainline in revision 42.
  • Revision ID: package-import@ubuntu.com-20120723085418-9foz30v6afaf5ffs
Tags: 2.63a-2
http://bugs.debian.org/658075
* debian/: Cycles support added (Closes: #658075)
  For now, this top feature has been enabled only
  on [any-amd64 any-i386] architectures because
  of OpenImageIO failing on all others
* debian/: scripts installation path changed
  from /usr/lib to /usr/share:
  + debian/patches/: patchset re-worked for path changing
  + debian/control: "Breaks" field added on yafaray-exporter

Show diffs side-by-side

added added

removed removed

Lines of Context:
extern/recastnavigation/Detour/Include/DetourNode.h
 
1
//
 
2
// Copyright (c) 2009 Mikko Mononen memon@inside.org
 
3
//
 
4
// This software is provided 'as-is', without any express or implied
 
5
// warranty.  In no event will the authors be held liable for any damages
 
6
// arising from the use of this software.
 
7
// Permission is granted to anyone to use this software for any purpose,
 
8
// including commercial applications, and to alter it and redistribute it
 
9
// freely, subject to the following restrictions:
 
10
// 1. The origin of this software must not be misrepresented; you must not
 
11
//    claim that you wrote the original software. If you use this software
 
12
//    in a product, an acknowledgment in the product documentation would be
 
13
//    appreciated but is not required.
 
14
// 2. Altered source versions must be plainly marked as such, and must not be
 
15
//    misrepresented as being the original software.
 
16
// 3. This notice may not be removed or altered from any source distribution.
 
17
//
 
18
 
 
19
#ifndef DETOURNODE_H
 
20
#define DETOURNODE_H
 
21
 
 
22
enum dtNodeFlags
 
23
{
 
24
        DT_NODE_OPEN = 0x01,
 
25
        DT_NODE_CLOSED = 0x02,
 
26
};
 
27
 
 
28
struct dtNode
 
29
{
 
30
        float cost;
 
31
        float total;
 
32
        unsigned int id;
 
33
        unsigned int pidx : 30;
 
34
        unsigned int flags : 2;
 
35
};
 
36
 
 
37
class dtNodePool
 
38
{
 
39
public:
 
40
        dtNodePool(int maxNodes, int hashSize);
 
41
        ~dtNodePool();
 
42
        inline void operator=(const dtNodePool&) {}
 
43
        void clear();
 
44
        dtNode* getNode(unsigned int id);
 
45
        const dtNode* findNode(unsigned int id) const;
 
46
 
 
47
        inline unsigned int getNodeIdx(const dtNode* node) const
 
48
        {
 
49
                if (!node) return 0;
 
50
                return (unsigned int)(node - m_nodes)+1;
 
51
        }
 
52
 
 
53
        inline dtNode* getNodeAtIdx(unsigned int idx)
 
54
        {
 
55
                if (!idx) return 0;
 
56
                return &m_nodes[idx-1];
 
57
        }
 
58
        
 
59
        inline int getMemUsed() const
 
60
        {
 
61
                return sizeof(*this) +
 
62
                sizeof(dtNode)*m_maxNodes +
 
63
                sizeof(unsigned short)*m_maxNodes +
 
64
                sizeof(unsigned short)*m_hashSize;
 
65
        }
 
66
        
 
67
private:
 
68
        inline unsigned int hashint(unsigned int a) const
 
69
        {
 
70
                a += ~(a<<15);
 
71
                a ^=  (a>>10);
 
72
                a +=  (a<<3);
 
73
                a ^=  (a>>6);
 
74
                a += ~(a<<11);
 
75
                a ^=  (a>>16);
 
76
                return a;
 
77
        }
 
78
        
 
79
        dtNode* m_nodes;
 
80
        unsigned short* m_first;
 
81
        unsigned short* m_next;
 
82
        const int m_maxNodes;
 
83
        const int m_hashSize;
 
84
        int m_nodeCount;
 
85
};
 
86
 
 
87
class dtNodeQueue
 
88
{
 
89
public:
 
90
        dtNodeQueue(int n);
 
91
        ~dtNodeQueue();
 
92
        inline void operator=(dtNodeQueue&) {}
 
93
        
 
94
        inline void clear()
 
95
        {
 
96
                m_size = 0;
 
97
        }
 
98
        
 
99
        inline dtNode* top()
 
100
        {
 
101
                return m_heap[0];
 
102
        }
 
103
        
 
104
        inline dtNode* pop()
 
105
        {
 
106
                dtNode* result = m_heap[0];
 
107
                m_size--;
 
108
                trickleDown(0, m_heap[m_size]);
 
109
                return result;
 
110
        }
 
111
        
 
112
        inline void push(dtNode* node)
 
113
        {
 
114
                m_size++;
 
115
                bubbleUp(m_size-1, node);
 
116
        }
 
117
        
 
118
        inline void modify(dtNode* node)
 
119
        {
 
120
                for (int i = 0; i < m_size; ++i)
 
121
                {
 
122
                        if (m_heap[i] == node)
 
123
                        {
 
124
                                bubbleUp(i, node);
 
125
                                return;
 
126
                        }
 
127
                }
 
128
        }
 
129
        
 
130
        inline bool empty() const { return m_size == 0; }
 
131
        
 
132
        inline int getMemUsed() const
 
133
        {
 
134
                return sizeof(*this) +
 
135
                sizeof(dtNode*)*(m_capacity+1);
 
136
        }
 
137
        
 
138
        
 
139
private:
 
140
        void bubbleUp(int i, dtNode* node);
 
141
        void trickleDown(int i, dtNode* node);
 
142
        
 
143
        dtNode** m_heap;
 
144
        const int m_capacity;
 
145
        int m_size;
 
146
};              
 
147
 
 
148
 
 
149
#endif // DETOURNODE_H
 
 
b'\\ No newline at end of file'