1 /* Declarations of global objects.
2 Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it>
3 Copyright (C) 2010-2016 BUGSENG srl (http://bugseng.com)
4
5 This file is part of the Parma Polyhedra Library (PPL).
6
7 The PPL is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3 of the License, or (at your
10 option) any later version.
11
12 The PPL is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software Foundation,
19 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA.
20
21 For the most up-to-date information see the Parma Polyhedra Library
22 site: http://bugseng.com/products/ppl/ . */
23
24 #ifndef PPL_globals_defs_hh
25 #define PPL_globals_defs_hh 1
26
27 #include "globals_types.hh"
28 #include "C_Integer.hh"
29 #include "meta_programming.hh"
30 #include "Slow_Copy.hh"
31 #include "Temp_defs.hh"
32 #include <exception>
33 #include <gmpxx.h>
34
35 #ifndef PPL_PROFILE_ADD_WEIGHT
36 #define PPL_PROFILE_ADD_WEIGHT 0
37 #endif
38
39 #if defined(NDEBUG) && PPL_PROFILE_ADD_WEIGHT
40 #include "Weight_Profiler_defs.hh"
41 #endif
42
43 #if defined(NDEBUG)
44
45 #if PPL_PROFILE_ADD_WEIGHT
46
47 #define WEIGHT_BEGIN() Weight_Profiler::begin()
48
49 #define WEIGHT_ADD(delta) \
50 do { \
51 static Weight_Profiler wp__(__FILE__, __LINE__, delta); \
52 wp__.end(); \
53 } while (false)
54
55 #define WEIGHT_ADD_MUL(delta, factor) \
56 do { \
57 static Weight_Profiler wp__(__FILE__, __LINE__, delta); \
58 wp__.end(factor); \
59 } while (false)
60
61 #else // !PPL_PROFILE_ADD_WEIGHT
62
63 #define WEIGHT_BEGIN() \
64 do { \
65 } while (false)
66
67 #define WEIGHT_ADD(delta) \
68 do { \
69 Weightwatch_Traits::weight += (delta); \
70 } while (false)
71
72 #define WEIGHT_ADD_MUL(delta, factor) \
73 do { \
74 Weightwatch_Traits::weight += (delta)*(factor); \
75 } while (false)
76
77 #endif // !PPL_PROFILE_ADD_WEIGHT
78
79 #else // !defined(NDEBUG)
80
81 #define WEIGHT_BEGIN()
82
83 #define WEIGHT_ADD(delta) \
84 do { \
85 if (!In_Assert::asserting()) { \
86 Weightwatch_Traits::weight += delta; \
87 } \
88 } while (false)
89
90 #define WEIGHT_ADD_MUL(delta, factor) \
91 do { \
92 if (!In_Assert::asserting()) { \
93 Weightwatch_Traits::weight += delta * factor; \
94 } \
95 } while (false)
96
97 #endif // !defined(NDEBUG)
98
99
100 namespace Parma_Polyhedra_Library {
101
102 //! Returns a value that does not designate a valid dimension.
103 dimension_type
104 not_a_dimension();
105
106 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
107 //! Returns the hash code for space dimension \p dim.
108 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
109 int32_t
110 hash_code_from_dimension(dimension_type dim);
111
112 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
113 /*! \brief
114 Make sure swap() is specialized when needed.
115
116 This will cause a compile-time error whenever a specialization for \p T
117 is beneficial but missing.
118 */
119 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
120 template <typename T>
121 inline typename Enable_If<Slow_Copy<T>::value, void>::type
swap(T &,T &)122 swap(T&, T&) {
123 PPL_COMPILE_TIME_CHECK(!Slow_Copy<T>::value, "missing swap specialization");
124 }
125
126 /*! \brief
127 Declare a local variable named \p id, of type Coefficient, and containing
128 an unknown initial value.
129
130 Use of this macro to declare temporaries of type Coefficient results
131 in decreased memory allocation overhead and in better locality.
132 */
133 #define PPL_DIRTY_TEMP_COEFFICIENT(id) \
134 PPL_DIRTY_TEMP(Parma_Polyhedra_Library::Coefficient, id)
135
136 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
137 //! Speculative allocation function.
138 /*!
139 \return
140 The actual capacity to be allocated.
141
142 \param requested_size
143 The number of elements we need.
144
145 \param maximum_size
146 The maximum number of elements to be allocated. It is assumed
147 to be no less than \p requested_size.
148
149 Computes a capacity given a requested size.
150 Allows for speculative allocation aimed at reducing the number of
151 reallocations enough to guarantee amortized constant insertion time
152 for our vector-like data structures. In all cases, the speculative
153 allocation will not exceed \p maximum_size.
154 */
155 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
156 dimension_type
157 compute_capacity(dimension_type requested_size,
158 dimension_type maximum_size);
159
160
161 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
162 //! Traits class for the deterministic timeout mechanism.
163 /*! \ingroup PPL_CXX_interface
164 This abstract base class should be instantiated by those users
165 willing to provide a polynomial upper bound to the time spent
166 by any invocation of a library operator.
167 */
168 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
169 struct Weightwatch_Traits {
170 //! The type used to specify thresholds for computational weight.
171 typedef unsigned long long Threshold;
172
173 //! The type used to specify increments of computational weight.
174 typedef unsigned long long Delta;
175
176 //! Returns the current computational weight.
177 static const Threshold& get();
178
179 //! Compares the two weights \p a and \p b.
180 static bool less_than(const Threshold& a, const Threshold& b);
181
182 //! Computes a \c Delta value from \p unscaled and \p scale.
183 /*!
184 \return
185 \f$u \cdot 2^s\f$, where \f$u\f$ is the value of \p unscaled and
186 \f$s\f$ is the value of \p scale.
187
188 \param unscaled
189 The value of delta before scaling.
190
191 \param scale
192 The scaling to be applied to \p unscaled.
193 */
194 static Delta compute_delta(unsigned long unscaled, unsigned scale);
195
196 //! Sets \p threshold to be \p delta units bigger than the current weight.
197 static void from_delta(Threshold& threshold, const Delta& delta);
198
199 //! The current computational weight.
200 static Threshold weight;
201
202 /*! \brief
203 A pointer to the function that has to be called when checking
204 the reaching of thresholds.
205
206 The pointer can be null if no thresholds are set.
207 */
208 static void (*check_function)(void);
209 };
210
211
212 #ifndef NDEBUG
213
214 class In_Assert {
215 private:
216 //! Non zero during evaluation of PPL_ASSERT expression.
217 static unsigned int count;
218 public:
In_Assert()219 In_Assert() {
220 ++count;
221 }
~In_Assert()222 ~In_Assert() {
223 --count;
224 }
asserting()225 static bool asserting() {
226 return count != 0;
227 }
228 };
229
230 #endif
231
232
233 //! User objects the PPL can throw.
234 /*! \ingroup PPL_CXX_interface
235 This abstract base class should be instantiated by those users
236 willing to provide a polynomial upper bound to the time spent
237 by any invocation of a library operator.
238 */
239 class Throwable {
240 public:
241 //! Throws the user defined exception object.
242 virtual void throw_me() const = 0;
243
244 //! Virtual destructor.
245 virtual ~Throwable();
246 };
247
248 /*! \brief
249 A pointer to an exception object.
250
251 \ingroup PPL_CXX_interface
252 This pointer, which is initialized to zero, is repeatedly checked
253 along any super-linear (i.e., computationally expensive) computation
254 path in the library.
255 When it is found nonzero the exception it points to is thrown.
256 In other words, making this pointer point to an exception (and
257 leaving it in this state) ensures that the library will return
258 control to the client application, possibly by throwing the given
259 exception, within a time that is a linear function of the size
260 of the representation of the biggest object (powerset of polyhedra,
261 polyhedron, system of constraints or generators) on which the library
262 is operating upon.
263
264 \note
265 The only sensible way to assign to this pointer is from within a
266 signal handler or from a parallel thread. For this reason, the
267 library, apart from ensuring that the pointer is initially set to zero,
268 never assigns to it. In particular, it does not zero it again when
269 the exception is thrown: it is the client's responsibility to do so.
270 */
271 extern const Throwable* volatile abandon_expensive_computations;
272
273 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
274 /*! \brief
275 If the pointer abandon_expensive_computations is found
276 to be nonzero, the exception it points to is thrown.
277
278 \relates Throwable
279 */
280 #endif
281 void
282 maybe_abandon();
283
284 //! A tag class.
285 /*! \ingroup PPL_CXX_interface
286 Tag class to distinguish those constructors that recycle the data
287 structures of their arguments, instead of taking a copy.
288 */
289 struct Recycle_Input {
290 };
291
292 // Turn s into a string: PPL_STR(x + y) => "x + y".
293 #define PPL_STR(s) #s
294 // Turn the expansion of s into a string: PPL_XSTR(x) => "x expanded".
295 #define PPL_XSTR(s) PPL_STR(s)
296
297 #define PPL_OUTPUT_DECLARATIONS \
298 /*! \brief Writes to \c std::cerr an ASCII representation of \p *this. */ \
299 void ascii_dump() const; \
300 /*! \brief Writes to \p s an ASCII representation of \p *this. */ \
301 void ascii_dump(std::ostream& s) const; \
302 /*! \brief Prints \p *this to \c std::cerr using \c operator<<. */ \
303 void print() const;
304
305 #define PPL_OUTPUT_DEFINITIONS(class_name) \
306 void \
307 Parma_Polyhedra_Library::class_name::ascii_dump() const { \
308 ascii_dump(std::cerr); \
309 } \
310 \
311 void \
312 Parma_Polyhedra_Library::class_name::print() const { \
313 using IO_Operators::operator<<; \
314 std::cerr << *this; \
315 }
316
317 #define PPL_OUTPUT_DEFINITIONS_ASCII_ONLY(class_name) \
318 void \
319 Parma_Polyhedra_Library::class_name::ascii_dump() const { \
320 ascii_dump(std::cerr); \
321 } \
322 \
323 void \
324 Parma_Polyhedra_Library::class_name::print() const { \
325 std::cerr << "No user level output operator defined " \
326 << "for class " PPL_XSTR(class_name) << "." << std::endl; \
327 }
328
329 #define PPL_OUTPUT_TEMPLATE_DEFINITIONS(type_symbol, class_prefix) \
330 template <typename type_symbol> \
331 void \
332 class_prefix::ascii_dump() const { \
333 ascii_dump(std::cerr); \
334 } \
335 \
336 template <typename type_symbol> \
337 void \
338 class_prefix::print() const { \
339 using IO_Operators::operator<<; \
340 std::cerr << *this; \
341 }
342
343 #define PPL_OUTPUT_2_PARAM_TEMPLATE_DEFINITIONS(type_symbol1, \
344 type_symbol2, \
345 class_prefix) \
346 template <typename type_symbol1, typename type_symbol2> \
347 void \
348 PPL_U(class_prefix)<PPL_U(type_symbol1), PPL_U(type_symbol2)> \
349 ::ascii_dump() const { \
350 ascii_dump(std::cerr); \
351 } \
352 \
353 template <typename type_symbol1, typename type_symbol2> \
354 void \
355 PPL_U(class_prefix)<PPL_U(type_symbol1), PPL_U(type_symbol2)> \
356 ::print() const { \
357 using IO_Operators::operator<<; \
358 std::cerr << *this; \
359 }
360
361 #define PPL_OUTPUT_3_PARAM_TEMPLATE_DEFINITIONS(type_symbol1, \
362 type_symbol2, \
363 type_symbol3, \
364 class_prefix) \
365 template <typename type_symbol1, typename type_symbol2, \
366 typename type_symbol3> \
367 void \
368 PPL_U(class_prefix)<PPL_U(type_symbol1), type_symbol2, \
369 PPL_U(type_symbol3)>::ascii_dump() \
370 const { \
371 ascii_dump(std::cerr); \
372 } \
373 \
374 template <typename type_symbol1, typename type_symbol2, \
375 typename type_symbol3> \
376 void \
377 PPL_U(class_prefix)<PPL_U(type_symbol1), type_symbol2, \
378 PPL_U(type_symbol3)>::print() \
379 const { \
380 using IO_Operators::operator<<; \
381 std::cerr << *this; \
382 }
383
384 #define PPL_OUTPUT_TEMPLATE_DEFINITIONS_ASCII_ONLY(type_symbol, class_prefix) \
385 template <typename type_symbol> \
386 void \
387 class_prefix::ascii_dump() const { \
388 ascii_dump(std::cerr); \
389 } \
390 \
391 template <typename type_symbol> \
392 void \
393 class_prefix::print() const { \
394 std::cerr << "No user level output operator defined " \
395 << "for " PPL_XSTR(class_prefix) << "." << std::endl; \
396 }
397
398 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
399 //! Returns <CODE>true</CODE> if \p c is any kind of space character.
400 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
401 bool is_space(char c);
402
403 template <typename T, long long v, typename Enable = void>
404 struct Fit : public False {
405 };
406
407 template <typename T, long long v>
408 struct Fit<T, v, typename Enable_If<C_Integer<T>::value>::type> {
409 enum {
410 value = (v >= static_cast<long long>(C_Integer<T>::min)
411 && v <= static_cast<long long>(C_Integer<T>::max))
412 };
413 };
414
415 template <typename T, T v>
416 struct TConstant {
417 static const T value = v;
418 };
419
420
421 template <typename T, T v>
422 const T TConstant<T, v>::value;
423
424 template <typename T, long long v, bool prefer_signed = true,
425 typename Enable = void>
426 struct Constant_ : public TConstant<T, v> {
427 };
428
429 //! \cond
430 // Keep Doxygen off until it learns how to deal properly with `||'.
431
432 template <typename T, long long v, bool prefer_signed>
433 struct Constant_<T, v, prefer_signed,
434 typename Enable_If<(Fit<typename C_Integer<T>::smaller_signed_type, v>::value
435 && (prefer_signed
436 || !Fit<typename C_Integer<T>::smaller_unsigned_type, v>::value))>::type>
437 : public Constant_<typename C_Integer<T>::smaller_signed_type, v, prefer_signed> {
438 };
439
440 template <typename T, long long v, bool prefer_signed>
441 struct Constant_<T, v, prefer_signed,
442 typename Enable_If<(Fit<typename C_Integer<T>::smaller_unsigned_type, v>::value
443 && (!prefer_signed
444 || !Fit<typename C_Integer<T>::smaller_signed_type, v>::value))>::type>
445 : public Constant_<typename C_Integer<T>::smaller_unsigned_type, v, prefer_signed> {
446 };
447
448 //! \endcond
449
450 template <long long v, bool prefer_signed = true>
451 struct Constant : public Constant_<long long, v, prefer_signed> {
452 };
453
454 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
455 //! \name Memory Size Inspection Functions
456 //@{
457 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
458
459 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
460 /*! \brief
461 For native types, returns the total size in bytes of the memory
462 occupied by the type of the (unused) parameter, i.e., 0.
463 */
464 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
465 template <typename T>
466 typename Enable_If<Is_Native<T>::value, memory_size_type>::type
467 total_memory_in_bytes(const T&);
468
469 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
470 /*! \brief
471 For native types, returns the size in bytes of the memory managed
472 by the type of the (unused) parameter, i.e., 0.
473 */
474 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
475 template <typename T>
476 typename Enable_If<Is_Native<T>::value, memory_size_type>::type
477 external_memory_in_bytes(const T&);
478
479 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
480 //! Returns the total size in bytes of the memory occupied by \p x.
481 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
482 memory_size_type
483 total_memory_in_bytes(const mpz_class& x);
484
485 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
486 //! Returns the size in bytes of the memory managed by \p x.
487 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
488 memory_size_type
489 external_memory_in_bytes(const mpz_class& x);
490
491 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
492 //! Returns the total size in bytes of the memory occupied by \p x.
493 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
494 memory_size_type
495 total_memory_in_bytes(const mpq_class& x);
496
497 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
498 //! Returns the size in bytes of the memory managed by \p x.
499 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
500 memory_size_type
501 external_memory_in_bytes(const mpq_class& x);
502
503 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
504 //@} // Memory Size Inspection Functions
505 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
506
507
508 template <typename T, typename Enable = void>
509 struct Has_OK : public False { };
510
511 template <typename T>
512 struct Has_OK<T, typename Enable_If_Is<bool (T::*)() const, &T::OK>::type>
513 : public True {
514 };
515
516 template <typename T>
517 inline typename Enable_If<Has_OK<T>::value, bool>::type
f_OK(const T & to)518 f_OK(const T& to) {
519 return to.OK();
520 }
521
522 #define FOK(T) inline bool f_OK(const T&) { return true; }
523
524 FOK(char)
525 FOK(signed char)
526 FOK(unsigned char)
527 FOK(signed short)
528 FOK(unsigned short)
529 FOK(signed int)
530 FOK(unsigned int)
531 FOK(signed long)
532 FOK(unsigned long)
533 FOK(signed long long)
534 FOK(unsigned long long)
535 FOK(float)
536 FOK(double)
537 FOK(long double)
538 FOK(mpz_class)
539 FOK(mpq_class)
540
541 void ascii_dump(std::ostream& s, Representation r);
542 bool ascii_load(std::istream& s, Representation& r);
543
544 dimension_type
545 check_space_dimension_overflow(dimension_type dim,
546 dimension_type max,
547 const char* domain,
548 const char* method,
549 const char* reason);
550
551 template <typename RA_Container>
552 typename RA_Container::iterator
553 nth_iter(RA_Container& cont, dimension_type n);
554
555 template <typename RA_Container>
556 typename RA_Container::const_iterator
557 nth_iter(const RA_Container& cont, dimension_type n);
558
559 dimension_type
560 least_significant_one_mask(dimension_type i);
561
562 } // namespace Parma_Polyhedra_Library
563
564 // By default, use sparse matrices both for MIP_Problem and PIP_Problem.
565 #ifndef PPL_USE_SPARSE_MATRIX
566 #define PPL_USE_SPARSE_MATRIX 1
567 #endif
568
569 #include "globals_inlines.hh"
570
571 #endif // !defined(PPL_globals_defs_hh)
572