this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Guido Tack <tack@gecode.org>
5 *
6 * Copyright:
7 * Guido Tack, 2006
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34namespace Gecode { namespace Gist {
35
36 template<class T>
37 void
38 NodeAllocatorBase<T>::allocate(void) {
39 cur_b++;
40 cur_t = 0;
41 if (cur_b==n) {
42 int oldn = n;
43 n = static_cast<int>(n*1.5+1.0);
44 b = heap.realloc<Block*>(b,oldn,n);
45 }
46 b[cur_b] = static_cast<Block*>(heap.ralloc(sizeof(Block)));
47 }
48
49 template<class T>
50 NodeAllocatorBase<T>::NodeAllocatorBase(bool bab)
51 : _bab(bab) {
52 b = heap.alloc<Block*>(10);
53 n = 10;
54 cur_b = -1;
55 cur_t = NodeBlockSize-1;
56 }
57
58 template<class T>
59 NodeAllocatorBase<T>::~NodeAllocatorBase(void) {
60 for (int i=cur_b+1; i--;)
61 heap.rfree(b[i]);
62 heap.free<Block*>(b,n);
63 }
64
65 template<class T>
66 forceinline int
67 NodeAllocatorBase<T>::allocate(int p) {
68 cur_t++;
69 if (cur_t==NodeBlockSize)
70 allocate();
71 new (&b[cur_b]->b[cur_t]) T(p);
72 b[cur_b]->best[cur_t] = -1;
73 return cur_b*NodeBlockSize+cur_t;
74 }
75
76 template<class T>
77 forceinline int
78 NodeAllocatorBase<T>::allocate(Space* root) {
79 cur_t++;
80 if (cur_t==NodeBlockSize)
81 allocate();
82 new (&b[cur_b]->b[cur_t]) T(root);
83 b[cur_b]->best[cur_t] = -1;
84 return cur_b*NodeBlockSize+cur_t;
85 }
86
87 template<class T>
88 forceinline T*
89 NodeAllocatorBase<T>::operator [](int i) const {
90 assert(i/NodeBlockSize < n);
91 assert(i/NodeBlockSize < cur_b || i%NodeBlockSize <= cur_t);
92 return &(b[i/NodeBlockSize]->b[i%NodeBlockSize]);
93 }
94
95 template<class T>
96 forceinline T*
97 NodeAllocatorBase<T>::best(int i) const {
98 assert(i/NodeBlockSize < n);
99 assert(i/NodeBlockSize < cur_b || i%NodeBlockSize <= cur_t);
100 int bi = b[i/NodeBlockSize]->best[i%NodeBlockSize];
101 return bi == -1 ? nullptr : (*this)[bi];
102 }
103
104 template<class T>
105 forceinline void
106 NodeAllocatorBase<T>::setBest(int i, int best) {
107 assert(i/NodeBlockSize < n);
108 assert(i/NodeBlockSize < cur_b || i%NodeBlockSize <= cur_t);
109 b[i/NodeBlockSize]->best[i%NodeBlockSize] = best;
110 }
111
112 template<class T>
113 forceinline bool
114 NodeAllocatorBase<T>::bab(void) const {
115 return _bab;
116 }
117
118 template<class T>
119 forceinline bool
120 NodeAllocatorBase<T>::showLabels(void) const {
121 return !labels.isEmpty();
122 }
123
124 template<class T>
125 bool
126 NodeAllocatorBase<T>::hasLabel(T* n) const {
127 return labels.contains(n);
128 }
129
130 template<class T>
131 void
132 NodeAllocatorBase<T>::setLabel(T* n, const QString& l) {
133 labels[n] = l;
134 }
135
136 template<class T>
137 void
138 NodeAllocatorBase<T>::clearLabel(T* n) {
139 labels.remove(n);
140 }
141
142 template<class T>
143 QString
144 NodeAllocatorBase<T>::getLabel(T* n) const {
145 return labels.value(n);
146 }
147
148 forceinline unsigned int
149 Node::getTag(void) const {
150 return static_cast<unsigned int>
151 (reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & 3);
152 }
153
154 forceinline void
155 Node::setTag(unsigned int tag) {
156 assert(tag <= 3);
157 assert(getTag() == UNDET);
158 childrenOrFirstChild = reinterpret_cast<void*>
159 ( (reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & ~(3)) | tag);
160 }
161
162 forceinline void*
163 Node::getPtr(void) const {
164 return reinterpret_cast<void*>
165 (reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & ~(3));
166 }
167
168 forceinline int
169 Node::getFirstChild(void) const {
170 return static_cast<int>
171 ((reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & ~(3)) >> 2);
172 }
173
174 forceinline
175 Node::Node(int p, bool failed) : parent(p) {
176 childrenOrFirstChild = nullptr;
177 noOfChildren = 0;
178 setTag(failed ? LEAF : UNDET);
179 }
180
181 forceinline int
182 Node::getParent(void) const {
183 return parent;
184 }
185
186 forceinline VisualNode*
187 Node::getParent(const NodeAllocator& na) const {
188 return parent < 0 ? nullptr : na[parent];
189 }
190
191 forceinline bool
192 Node::isUndetermined(void) const { return getTag() == UNDET; }
193
194 forceinline int
195 Node::getChild(int n) const {
196 assert(getTag() != UNDET && getTag() != LEAF);
197 if (getTag() == TWO_CHILDREN) {
198 assert(n != 1 || noOfChildren <= 0);
199 return n == 0 ? getFirstChild() : -noOfChildren;
200 }
201 assert(n < noOfChildren);
202 return static_cast<int*>(getPtr())[n];
203 }
204
205 forceinline VisualNode*
206 Node::getChild(const NodeAllocator& na, int n) const {
207 return na[getChild(n)];
208 }
209
210 forceinline bool
211 Node::isRoot(void) const { return parent == -1; }
212
213 forceinline unsigned int
214 Node::getNumberOfChildren(void) const {
215 switch (getTag()) {
216 case UNDET:
217 case LEAF:
218 return 0;
219 case TWO_CHILDREN:
220 return (noOfChildren <= 0) ? 2 : 1;
221 default:
222 return static_cast<unsigned int>(noOfChildren);
223 }
224 }
225
226 forceinline int
227 Node::getIndex(const NodeAllocator& na) const {
228 if (parent==-1)
229 return 0;
230 Node* p = na[parent];
231 for (int i=p->getNumberOfChildren(); i--;)
232 if (p->getChild(na,i) == this)
233 return p->getChild(i);
234 GECODE_NEVER;
235 return -1;
236 }
237
238}}
239
240// STATISTICS: gist-any