main page
modules
namespaces
classes
files
Gecode home
Generated on Fri Aug 31 2012 16:21:44 for Gecode by
doxygen
1.8.1.2
gecode
search
parallel
restart.cpp
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-08-11 23:05:41 +1000 (Tue, 11 Aug 2009) $ by $Author: schulte $
11
* $Revision: 9585 $
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 <
gecode/support.hh
>
39
40
#ifdef GECODE_HAS_THREADS
41
42
#include <
gecode/search/parallel/restart.hh
>
43
44
namespace
Gecode {
namespace
Search {
namespace
Parallel {
45
46
Space*
47
Restart::next
(
void
) {
48
// Invariant: the worker holds the wait mutex
49
m_search
.
acquire
();
50
// Check whether root space is already failed
51
if
(
root
== NULL) {
52
m_search
.
release
();
53
return
NULL;
54
}
55
while
(!
solutions
.
empty
()) {
56
// No search needs to be done, try to take leftover solution
57
Space
* s =
solutions
.
pop
();
58
if
(
best
== NULL) {
59
best
= s->
clone
();
60
reset_needed
=
true
;
61
m_search
.
release
();
62
return
s;
63
}
else
{
64
s->
constrain
(*
best
);
65
if
(s->
status
() ==
SS_FAILED
) {
66
delete
s;
67
}
else
{
68
delete
best
;
69
best
= s->
clone
();
70
reset_needed
=
true
;
71
m_search
.
release
();
72
return
s;
73
}
74
}
75
}
76
// We ignore stopped (it will be reported again if needed)
77
has_stopped
=
false
;
78
// No more solutions?
79
if
(
n_busy
== 0) {
80
m_search
.
release
();
81
return
NULL;
82
}
83
if
(
reset_needed
) {
84
reset_needed
=
false
;
85
root
->
constrain
(*
best
);
86
// Leave lock
87
m_search
.
release
();
88
// Grab wait lock for reset
89
m_wait_reset
.
acquire
();
90
// Release workers for reset
91
release
(
C_RESET
);
92
// Wait for reset cycle started
93
e_reset_ack_start
.
wait
();
94
// Perform reset
95
root
=
reset
(
root
);
96
// Block workers again to ensure invariant
97
block
();
98
// Release reset lock
99
m_wait_reset
.
release
();
100
// Wait for reset cycle stopped
101
e_reset_ack_stop
.
wait
();
102
if
(
root
== NULL)
103
return
NULL;
104
}
else
{
105
m_search
.
release
();
106
}
107
108
// Okay, now search has to continue, make the guys work
109
release
(
C_WORK
);
110
111
/*
112
* Wait until a search related event has happened. It might be that
113
* the event has already been signalled in the last run, but the
114
* solution has been removed. So we have to try until there has
115
* something new happened.
116
*/
117
while
(
true
) {
118
e_search
.
wait
();
119
m_search
.
acquire
();
120
while
(!
solutions
.
empty
()) {
121
// Check solution
122
Space
* s =
solutions
.
pop
();
123
if
(
best
== NULL) {
124
best
= s->
clone
();
125
reset_needed
=
true
;
126
m_search
.
release
();
127
// Make workers wait again
128
block
();
129
return
s;
130
}
else
{
131
s->
constrain
(*
best
);
132
if
(s->
status
() ==
SS_FAILED
) {
133
delete
s;
134
}
else
{
135
delete
best
;
136
best
= s->
clone
();
137
reset_needed
=
true
;
138
m_search
.
release
();
139
// Make workers wait again
140
block
();
141
return
s;
142
}
143
}
144
}
145
// No more solutions or stopped?
146
if
((
n_busy
== 0) ||
has_stopped
) {
147
m_search
.
release
();
148
// Make workers wait again
149
block
();
150
return
NULL;
151
}
152
m_search
.
release
();
153
}
154
GECODE_NEVER
;
155
return
NULL;
156
}
157
158
Restart::~Restart
(
void
) {
159
delete
best
;
160
delete
root
;
161
}
162
163
}}}
164
165
#endif
166
167
// STATISTICS: search-parallel