Generated on Mon Aug 27 2012 17:15:46 for Gecode by doxygen 1.8.1.2
global-prop-info.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2009
8  *
9  * Last modified:
10  * $Date: 2009-10-27 07:16:25 +1100 (Tue, 27 Oct 2009) $ by $Author: schulte $
11  * $Revision: 9991 $
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 {
39 
40  class GlobalPropInfo;
41 
43  class PropInfo {
44  private:
46  double _afc;
47  public:
49  PropInfo(void);
51  void init(void);
53  double afc(void) const;
55  void fail(GlobalPropInfo& gpi);
56  };
57 
60  friend class PropInfo;
61  private:
63  class Block {
64  public:
66  Block* next;
68  PropInfo pi[1];
70  static Block* allocate(unsigned int n, Block* p=NULL);
71  };
73  static const unsigned int size_min = 32;
75  static const unsigned int size_max = 32 * 1024;
77  class Object {
78  public:
80  Support::Mutex* mutex;
82  Object* parent;
84  unsigned int use_cnt;
86  unsigned int size;
88  unsigned int free;
90  Block* cur;
92  Object(Support::Mutex* m, Object* p=NULL);
94  static void* operator new(size_t s);
96  static void operator delete(void* p);
97  };
99  void* mo;
101  Object* object(void) const;
103  bool local(void) const;
105  void local(Object* o);
107  void global(void* mo);
108  public:
110  GlobalPropInfo(void);
112  GlobalPropInfo(const GlobalPropInfo& gpi);
114  ~GlobalPropInfo(void);
116  PropInfo& allocate(void);
117  };
118 
119 
120  /*
121  * Propagator information
122  *
123  */
126  : _afc(0.0) {}
127  forceinline void
129  _afc=0.0;
130  }
131  forceinline double
132  PropInfo::afc(void) const {
133  return _afc;
134  }
135 
136 
137  /*
138  * Global propagator information
139  *
140  */
141 
142  forceinline void*
143  GlobalPropInfo::Object::operator new(size_t s) {
144  return Gecode::heap.ralloc(s);
145  }
146 
147  forceinline void
148  GlobalPropInfo::Object::operator delete(void* p) {
149  Gecode::heap.rfree(p);
150  }
151 
152  forceinline GlobalPropInfo::Block*
153  GlobalPropInfo::Block::allocate(unsigned int n, GlobalPropInfo::Block* p) {
154  Block* b = static_cast<Block*>(heap.ralloc(sizeof(Block)+
155  (n-1)*sizeof(PropInfo)));
156  b->next = p;
157  return b;
158  }
159 
161  GlobalPropInfo::Object::Object(Support::Mutex* m, Object* p)
162  : mutex(m), parent(p), use_cnt(1), size(size_min), free(size_min),
163  cur(Block::allocate(size)) {}
164 
165  forceinline GlobalPropInfo::Object*
166  GlobalPropInfo::object(void) const {
167  return static_cast<Object*>(Support::funmark(mo));
168  }
169  forceinline bool
170  GlobalPropInfo::local(void) const {
171  return !Support::marked(mo);
172  }
173  forceinline void
174  GlobalPropInfo::local(Object* o) {
175  assert(!Support::marked(o));
176  mo = o;
177  }
178  forceinline void
179  GlobalPropInfo::global(void* o) {
180  mo = Support::fmark(o);
181  }
182 
185  // No synchronization needed as single thread is creating this object
186  local(new Object(new Support::Mutex));
187  }
188 
191  global(gpi.mo);
192  Object* o = object();
193  o->mutex->acquire();
194  o->use_cnt++;
195  o->mutex->release();
196  }
197 
200  Support::Mutex* m = object()->mutex;
201  m->acquire();
202  Object* c = object();
203  while ((c != NULL) && (--c->use_cnt == 0)) {
204  // Delete all blocks for c
205  Block* b = c->cur;
206  while (b != NULL) {
207  Block* d = b; b=b->next;
208  heap.rfree(d);
209  }
210  // Delete object
211  Object* d = c; c = c->parent;
212  delete d;
213  }
214  m->release();
215  // All objects are deleted, so also delete mutex
216  if (c == NULL)
217  delete m;
218  }
219 
220  forceinline void
222  Support::Mutex& m = *gpi.object()->mutex;
223  m.acquire();
224  _afc++;
225  m.release();
226  }
227 
230  /*
231  * If there is no local object, create one.
232  *
233  * There is no synchronization needed as only ONE space has access
234  * to the marked pointer AND the local object.
235  */
236  if (!local())
237  local(new Object(object()->mutex,object()));
238 
239  assert(local());
240 
241  Object* o = object();
242 
243  if (o->free == 0) {
244  if (2*o->size <= size_max)
245  o->size *= 2;
246  o->free = o->size;
247  o->cur = Block::allocate(o->size,o->cur);
248  }
249 
250  PropInfo* pi = &o->cur->pi[--o->free];
251  pi->init();
252 
253  return *pi;
254  }
255 
256 }
257 
258 // STATISTICS: kernel-prop