Generated on Sat May 25 2013 18:00:40 for Gecode by doxygen 1.8.3.1
global-afc.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: 2013-02-25 17:38:28 +0100 (Mon, 25 Feb 2013) $ by $Author: schulte $
11  * $Revision: 13398 $
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 #include <cmath>
39 
40 namespace Gecode {
41 
43  class GlobalAFC {
44  public:
46  class Counter {
47  public:
49  double c;
51  unsigned long int t;
53  void init(void);
54  };
55  private:
57  class Block {
58  public:
60  Block* next;
62  Counter c[1];
64  static Block* allocate(unsigned int n, Block* p=NULL);
65  };
67  class DecayManager {
68  protected:
70  double d;
72  static const unsigned int n_dpow = 8U;
74  double dpow[n_dpow];
76  unsigned long int t;
78  void decay(Counter& c);
79  public:
81  DecayManager(void);
83  void decay(double d);
85  double decay(void) const;
87  void inc(Counter& c);
89  double val(Counter& c);
91  static void* operator new(size_t s);
93  static void operator delete(void* p);
94  };
96  static const unsigned int size_min = 32;
98  static const unsigned int size_max = 32 * 1024;
100  class Object {
101  public:
103  Support::Mutex* mutex;
105  DecayManager* decay;
107  Object* parent;
109  unsigned int use_cnt;
111  unsigned int size;
113  unsigned int free;
115  Block* cur;
117  Object(Support::Mutex* m, Object* p=NULL);
119  static void* operator new(size_t s);
121  static void operator delete(void* p);
122  };
124  void* mo;
126  Object* object(void) const;
128  bool local(void) const;
130  void local(Object* o);
132  void global(void* mo);
133  public:
135  GlobalAFC(void);
137  GlobalAFC(const GlobalAFC& ga);
139  ~GlobalAFC(void);
141  void decay(double d);
143  double decay(void) const;
145  void fail(Counter& c);
147  double afc(Counter& c);
149  Counter& allocate(void);
150  };
151 
152 
153 
154  forceinline void
156  c=1.0; t=0UL;
157  }
158 
159  forceinline void
160  GlobalAFC::DecayManager::decay(double d0) {
161  d = d0;
162  if (d != 1.0) {
163  double p = d;
164  unsigned int i=0;
165  do {
166  dpow[i++]=p; p*=d;
167  } while (i<n_dpow);
168  }
169  }
171  GlobalAFC::DecayManager::DecayManager(void)
172  : d(1.0), t(0UL) {}
173 
174  forceinline double
175  GlobalAFC::DecayManager::decay(void) const {
176  return d;
177  }
178  forceinline void
179  GlobalAFC::DecayManager::decay(Counter& c) {
180  assert((t >= c.t) && (d != 1.0));
181  unsigned int n = t - c.t;
182  if (n > 0) {
183  if (n <= n_dpow) {
184  c.c *= dpow[n-1];
185  } else {
186  c.c *= pow(d,static_cast<double>(n));
187  }
188  c.t = t;
189  }
190  }
191  forceinline void
192  GlobalAFC::DecayManager::inc(Counter& c) {
193  if (d == 1.0) {
194  c.c += 1.0;
195  } else {
196  decay(c);
197  c.c += 1.0; c.t = ++t;
198  }
199  }
200  forceinline double
201  GlobalAFC::DecayManager::val(Counter& c) {
202  if (d != 1.0)
203  decay(c);
204  return c.c;
205  }
206  forceinline void*
207  GlobalAFC::DecayManager::operator new(size_t s) {
208  return Gecode::heap.ralloc(s);
209  }
210  forceinline void
211  GlobalAFC::DecayManager::operator delete(void* p) {
213  }
214 
215 
216  /*
217  * Global AFC information
218  *
219  */
220 
221  forceinline void*
222  GlobalAFC::Object::operator new(size_t s) {
223  return Gecode::heap.ralloc(s);
224  }
225 
226  forceinline void
227  GlobalAFC::Object::operator delete(void* p) {
229  }
230 
231  forceinline GlobalAFC::Block*
232  GlobalAFC::Block::allocate(unsigned int n, GlobalAFC::Block* p) {
233  Block* b = static_cast<Block*>(heap.ralloc(sizeof(Block)+
234  (n-1)*sizeof(Counter)));
235  b->next = p;
236  return b;
237  }
238 
240  GlobalAFC::Object::Object(Support::Mutex* m, Object* p)
241  : mutex(m), parent(p), use_cnt(1), size(size_min), free(size_min),
242  cur(Block::allocate(size)) {
243  if (parent == NULL) {
244  decay = new DecayManager;
245  } else {
246  decay = parent->decay;
247  }
248  }
249 
250  forceinline GlobalAFC::Object*
251  GlobalAFC::object(void) const {
252  return static_cast<Object*>(Support::funmark(mo));
253  }
254  forceinline bool
255  GlobalAFC::local(void) const {
256  return !Support::marked(mo);
257  }
258  forceinline void
259  GlobalAFC::local(Object* o) {
260  assert(!Support::marked(o));
261  mo = o;
262  }
263  forceinline void
264  GlobalAFC::global(void* o) {
265  mo = Support::fmark(o);
266  }
267 
270  // No synchronization needed as single thread is creating this object
271  local(new Object(new Support::Mutex));
272  }
273 
276  global(gpi.mo);
277  Object* o = object();
278  o->mutex->acquire();
279  o->use_cnt++;
280  o->mutex->release();
281  }
282 
285  Support::Mutex* m = object()->mutex;
286  m->acquire();
287  Object* c = object();
288  DecayManager* decay = c->decay;
289  while ((c != NULL) && (--c->use_cnt == 0)) {
290  // Delete all blocks for c
291  Block* b = c->cur;
292  while (b != NULL) {
293  Block* d = b; b=b->next;
294  heap.rfree(d);
295  }
296  // Delete object
297  Object* d = c; c = c->parent;
298  delete d;
299  }
300  m->release();
301  // All objects are deleted, so also delete mutex and decya info
302  if (c == NULL) {
303  delete decay;
304  delete m;
305  }
306  }
307 
308  forceinline void
310  Support::Mutex& m = *object()->mutex;
311  m.acquire();
312  object()->decay->inc(c);
313  m.release();
314  }
315 
316  forceinline double
318  Support::Mutex& m = *object()->mutex;
319  double d;
320  m.acquire();
321  d = object()->decay->val(c);
322  m.release();
323  return d;
324  }
325 
326  forceinline double
327  GlobalAFC::decay(void) const {
328  Support::Mutex& m = *object()->mutex;
329  double d;
330  m.acquire();
331  d = object()->decay->decay();
332  m.release();
333  return d;
334  }
335 
336  forceinline void
337  GlobalAFC::decay(double d) {
338  Support::Mutex& m = *object()->mutex;
339  m.acquire();
340  object()->decay->decay(d);
341  m.release();
342  }
343 
346  /*
347  * If there is no local object, create one.
348  *
349  * There is no synchronization needed as only ONE space has access
350  * to the marked pointer AND the local object.
351  */
352  if (!local())
353  local(new Object(object()->mutex,object()));
354 
355  assert(local());
356 
357  Object* o = object();
358 
359  if (o->free == 0) {
360  if (2*o->size <= size_max)
361  o->size *= 2;
362  o->free = o->size;
363  o->cur = Block::allocate(o->size,o->cur);
364  }
365 
366  Counter* c = &o->cur->c[--o->free];
367  c->init();
368 
369  return *c;
370  }
371 
372 }
373 
374 // STATISTICS: kernel-prop