Generated on Sun Aug 26 2012 08:42:37 for Gecode by doxygen 1.8.1.1
node.hpp
Go to the documentation of this file.
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  * Last modified:
10  * $Date: 2011-05-02 23:44:28 +1000 (Mon, 02 May 2011) $ by $Author: tack $
11  * $Revision: 11981 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 namespace Gecode { namespace Gist {
39 
40  template<class T>
41  void
42  NodeAllocatorBase<T>::allocate(void) {
43  cur_b++;
44  cur_t = 0;
45  if (cur_b==n) {
46  int oldn = n;
47  n *= 1.5;
48  b = heap.realloc<Block*>(b,oldn,n);
49  }
50  b[cur_b] = static_cast<Block*>(heap.ralloc(sizeof(Block)));
51  }
52 
53  template<class T>
55  b = heap.alloc<Block*>(10);
56  n = 10;
57  cur_b = -1;
58  cur_t = NodeBlockSize-1;
59  }
60 
61  template<class T>
63  for (int i=cur_b+1; i--;)
64  heap.rfree(b[i]);
65  heap.free<Block*>(b,n);
66  }
67 
68  template<class T>
69  forceinline int
71  cur_t++;
72  if (cur_t==NodeBlockSize)
73  allocate();
74  new (&b[cur_b]->b[cur_t]) T(p);
75  b[cur_b]->best[cur_t] = -1;
76  return cur_b*NodeBlockSize+cur_t;
77  }
78 
79  template<class T>
80  forceinline int
82  cur_t++;
83  if (cur_t==NodeBlockSize)
84  allocate();
85  new (&b[cur_b]->b[cur_t]) T(root);
86  b[cur_b]->best[cur_t] = -1;
87  return cur_b*NodeBlockSize+cur_t;
88  }
89 
90  template<class T>
91  forceinline T*
93  assert(i/NodeBlockSize < n);
94  assert(i/NodeBlockSize < cur_b || i%NodeBlockSize <= cur_t);
95  return &(b[i/NodeBlockSize]->b[i%NodeBlockSize]);
96  }
97 
98  template<class T>
99  forceinline T*
101  assert(i/NodeBlockSize < n);
102  assert(i/NodeBlockSize < cur_b || i%NodeBlockSize <= cur_t);
103  int bi = b[i/NodeBlockSize]->best[i%NodeBlockSize];
104  return bi == -1 ? NULL : (*this)[bi];
105  }
106 
107  template<class T>
108  forceinline void
110  assert(i/NodeBlockSize < n);
111  assert(i/NodeBlockSize < cur_b || i%NodeBlockSize <= cur_t);
112  b[i/NodeBlockSize]->best[i%NodeBlockSize] = best;
113  }
114 
115  template<class T>
116  forceinline bool
118  return _bab;
119  }
120 
121  forceinline unsigned int
122  Node::getTag(void) const {
123  return static_cast<unsigned int>
124  (reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & 3);
125  }
126 
127  forceinline void
128  Node::setTag(unsigned int tag) {
129  assert(tag <= 3);
130  assert(getTag() == UNDET);
131  childrenOrFirstChild = reinterpret_cast<void*>
132  ( (reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & ~(3)) | tag);
133  }
134 
135  forceinline void*
136  Node::getPtr(void) const {
137  return reinterpret_cast<void*>
138  (reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & ~(3));
139  }
140 
141  forceinline int
142  Node::getFirstChild(void) const {
143  return static_cast<int>
144  ((reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & ~(3)) >> 2);
145  }
146 
148  Node::Node(int p, bool failed) : parent(p) {
149  childrenOrFirstChild = NULL;
150  noOfChildren = 0;
151  setTag(failed ? LEAF : UNDET);
152  }
153 
154  forceinline int
155  Node::getParent(void) const {
156  return parent;
157  }
158 
160  Node::getParent(const NodeAllocator& na) const {
161  return parent < 0 ? NULL : na[parent];
162  }
163 
164  forceinline bool
165  Node::isUndetermined(void) const { return getTag() == UNDET; }
166 
167  forceinline int
168  Node::getChild(int n) const {
169  assert(getTag() != UNDET && getTag() != LEAF);
170  if (getTag() == TWO_CHILDREN) {
171  assert(n != 1 || noOfChildren <= 0);
172  return n == 0 ? getFirstChild() : -noOfChildren;
173  }
174  assert(n < noOfChildren);
175  return static_cast<int*>(getPtr())[n];
176  }
177 
179  Node::getChild(const NodeAllocator& na, int n) const {
180  return na[getChild(n)];
181  }
182 
183  forceinline bool
184  Node::isRoot(void) const { return parent == -1; }
185 
186  forceinline unsigned int
188  switch (getTag()) {
189  case UNDET: return 0;
190  case LEAF: return 0;
191  case TWO_CHILDREN: return 1+(noOfChildren <= 0);
192  default: return noOfChildren;
193  }
194  }
195 
196  inline int
197  Node::getIndex(const NodeAllocator& na) const {
198  if (parent==-1)
199  return 0;
200  Node* p = na[parent];
201  for (int i=p->getNumberOfChildren(); i--;)
202  if (p->getChild(na,i) == this)
203  return p->getChild(i);
204  GECODE_NEVER;
205  return -1;
206  }
207 
208 }}
209 
210 // STATISTICS: gist-any