OR-Tools  8.2
model_cache.cc
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14#include <string>
15#include <vector>
16
23
24ABSL_DECLARE_FLAG(int, cache_initial_size);
25ABSL_FLAG(bool, cp_disable_cache, false, "Disable caching of model objects");
26
27namespace operations_research {
28// ----- ModelCache -----
29
30ModelCache::ModelCache(Solver* const solver) : solver_(solver) {}
31
33
34Solver* ModelCache::solver() const { return solver_; }
35
36namespace {
37// ----- Helpers -----
38
39template <class T>
40bool IsEqual(const T& a1, const T& a2) {
41 return a1 == a2;
42}
43
44template <class T>
45bool IsEqual(const std::vector<T*>& a1, const std::vector<T*>& a2) {
46 if (a1.size() != a2.size()) {
47 return false;
48 }
49 for (int i = 0; i < a1.size(); ++i) {
50 if (a1[i] != a2[i]) {
51 return false;
52 }
53 }
54 return true;
55}
56
57template <class A1, class A2>
58uint64 Hash2(const A1& a1, const A2& a2) {
59 uint64 a = Hash1(a1);
60 uint64 b = uint64_t{0xe08c1d668b756f82}; // more of the golden ratio
61 uint64 c = Hash1(a2);
62 mix(a, b, c);
63 return c;
64}
65
66template <class A1, class A2, class A3>
67uint64 Hash3(const A1& a1, const A2& a2, const A3& a3) {
68 uint64 a = Hash1(a1);
69 uint64 b = Hash1(a2);
70 uint64 c = Hash1(a3);
71 mix(a, b, c);
72 return c;
73}
74
75template <class A1, class A2, class A3, class A4>
76uint64 Hash4(const A1& a1, const A2& a2, const A3& a3, const A4& a4) {
77 uint64 a = Hash1(a1);
78 uint64 b = Hash1(a2);
79 uint64 c = Hash2(a3, a4);
80 mix(a, b, c);
81 return c;
82}
83
84template <class C>
85void Double(C*** array_ptr, int* size_ptr) {
86 DCHECK(array_ptr != nullptr);
87 DCHECK(size_ptr != nullptr);
88 C** const old_cell_array = *array_ptr;
89 const int old_size = *size_ptr;
90 (*size_ptr) *= 2;
91 (*array_ptr) = new C*[(*size_ptr)];
92 memset(*array_ptr, 0, (*size_ptr) * sizeof(**array_ptr));
93 for (int i = 0; i < old_size; ++i) {
94 C* tmp = old_cell_array[i];
95 while (tmp != nullptr) {
96 C* const to_reinsert = tmp;
97 tmp = tmp->next();
98 const uint64 position = to_reinsert->Hash() % (*size_ptr);
99 to_reinsert->set_next((*array_ptr)[position]);
100 (*array_ptr)[position] = to_reinsert;
101 }
102 }
103 delete[](old_cell_array);
104}
105
106// ----- Cache objects built with 1 object -----
107
108template <class C, class A1>
109class Cache1 {
110 public:
111 Cache1()
112 : array_(new Cell*[absl::GetFlag(FLAGS_cache_initial_size)]),
113 size_(absl::GetFlag(FLAGS_cache_initial_size)),
114 num_items_(0) {
115 memset(array_, 0, sizeof(*array_) * size_);
116 }
117
118 ~Cache1() {
119 for (int i = 0; i < size_; ++i) {
120 Cell* tmp = array_[i];
121 while (tmp != nullptr) {
122 Cell* const to_delete = tmp;
123 tmp = tmp->next();
124 delete to_delete;
125 }
126 }
127 delete[] array_;
128 }
129
130 void Clear() {
131 for (int i = 0; i < size_; ++i) {
132 Cell* tmp = array_[i];
133 while (tmp != nullptr) {
134 Cell* const to_delete = tmp;
135 tmp = tmp->next();
136 delete to_delete;
137 }
138 array_[i] = nullptr;
139 }
140 }
141
142 C* Find(const A1& a1) const {
143 uint64 code = Hash1(a1) % size_;
144 Cell* tmp = array_[code];
145 while (tmp) {
146 C* const result = tmp->ReturnsIfEqual(a1);
147 if (result != nullptr) {
148 return result;
149 }
150 tmp = tmp->next();
151 }
152 return nullptr;
153 }
154
155 void UnsafeInsert(const A1& a1, C* const c) {
156 const int position = Hash1(a1) % size_;
157 Cell* const cell = new Cell(a1, c, array_[position]);
158 array_[position] = cell;
159 if (++num_items_ > 2 * size_) {
160 Double(&array_, &size_);
161 }
162 }
163
164 private:
165 class Cell {
166 public:
167 Cell(const A1& a1, C* const container, Cell* const next)
168 : a1_(a1), container_(container), next_(next) {}
169
170 C* ReturnsIfEqual(const A1& a1) const {
171 if (IsEqual(a1_, a1)) {
172 return container_;
173 }
174 return nullptr;
175 }
176
177 uint64 Hash() const { return Hash1(a1_); }
178
179 void set_next(Cell* const next) { next_ = next; }
180
181 Cell* next() const { return next_; }
182
183 private:
184 const A1 a1_;
185 C* const container_;
186 Cell* next_;
187 };
188
189 Cell** array_;
190 int size_;
191 int num_items_;
192};
193
194// ----- Cache objects built with 2 objects -----
195
196template <class C, class A1, class A2>
197class Cache2 {
198 public:
199 Cache2()
200 : array_(new Cell*[absl::GetFlag(FLAGS_cache_initial_size)]),
201 size_(absl::GetFlag(FLAGS_cache_initial_size)),
202 num_items_(0) {
203 memset(array_, 0, sizeof(*array_) * size_);
204 }
205
206 ~Cache2() {
207 for (int i = 0; i < size_; ++i) {
208 Cell* tmp = array_[i];
209 while (tmp != nullptr) {
210 Cell* const to_delete = tmp;
211 tmp = tmp->next();
212 delete to_delete;
213 }
214 }
215 delete[] array_;
216 }
217
218 void Clear() {
219 for (int i = 0; i < size_; ++i) {
220 Cell* tmp = array_[i];
221 while (tmp != nullptr) {
222 Cell* const to_delete = tmp;
223 tmp = tmp->next();
224 delete to_delete;
225 }
226 array_[i] = nullptr;
227 }
228 }
229
230 C* Find(const A1& a1, const A2& a2) const {
231 uint64 code = Hash2(a1, a2) % size_;
232 Cell* tmp = array_[code];
233 while (tmp) {
234 C* const result = tmp->ReturnsIfEqual(a1, a2);
235 if (result != nullptr) {
236 return result;
237 }
238 tmp = tmp->next();
239 }
240 return nullptr;
241 }
242
243 void UnsafeInsert(const A1& a1, const A2& a2, C* const c) {
244 const int position = Hash2(a1, a2) % size_;
245 Cell* const cell = new Cell(a1, a2, c, array_[position]);
246 array_[position] = cell;
247 if (++num_items_ > 2 * size_) {
248 Double(&array_, &size_);
249 }
250 }
251
252 private:
253 class Cell {
254 public:
255 Cell(const A1& a1, const A2& a2, C* const container, Cell* const next)
256 : a1_(a1), a2_(a2), container_(container), next_(next) {}
257
258 C* ReturnsIfEqual(const A1& a1, const A2& a2) const {
259 if (IsEqual(a1_, a1) && IsEqual(a2_, a2)) {
260 return container_;
261 }
262 return nullptr;
263 }
264
265 uint64 Hash() const { return Hash2(a1_, a2_); }
266
267 void set_next(Cell* const next) { next_ = next; }
268
269 Cell* next() const { return next_; }
270
271 private:
272 const A1 a1_;
273 const A2 a2_;
274 C* const container_;
275 Cell* next_;
276 };
277
278 Cell** array_;
279 int size_;
280 int num_items_;
281};
282
283// ----- Cache objects built with 2 objects -----
284
285template <class C, class A1, class A2, class A3>
286class Cache3 {
287 public:
288 Cache3()
289 : array_(new Cell*[absl::GetFlag(FLAGS_cache_initial_size)]),
290 size_(absl::GetFlag(FLAGS_cache_initial_size)),
291 num_items_(0) {
292 memset(array_, 0, sizeof(*array_) * size_);
293 }
294
295 ~Cache3() {
296 for (int i = 0; i < size_; ++i) {
297 Cell* tmp = array_[i];
298 while (tmp != nullptr) {
299 Cell* const to_delete = tmp;
300 tmp = tmp->next();
301 delete to_delete;
302 }
303 }
304 delete[] array_;
305 }
306
307 void Clear() {
308 for (int i = 0; i < size_; ++i) {
309 Cell* tmp = array_[i];
310 while (tmp != nullptr) {
311 Cell* const to_delete = tmp;
312 tmp = tmp->next();
313 delete to_delete;
314 }
315 array_[i] = nullptr;
316 }
317 }
318
319 C* Find(const A1& a1, const A2& a2, const A3& a3) const {
320 uint64 code = Hash3(a1, a2, a3) % size_;
321 Cell* tmp = array_[code];
322 while (tmp) {
323 C* const result = tmp->ReturnsIfEqual(a1, a2, a3);
324 if (result != nullptr) {
325 return result;
326 }
327 tmp = tmp->next();
328 }
329 return nullptr;
330 }
331
332 void UnsafeInsert(const A1& a1, const A2& a2, const A3& a3, C* const c) {
333 const int position = Hash3(a1, a2, a3) % size_;
334 Cell* const cell = new Cell(a1, a2, a3, c, array_[position]);
335 array_[position] = cell;
336 if (++num_items_ > 2 * size_) {
337 Double(&array_, &size_);
338 }
339 }
340
341 private:
342 class Cell {
343 public:
344 Cell(const A1& a1, const A2& a2, const A3& a3, C* const container,
345 Cell* const next)
346 : a1_(a1), a2_(a2), a3_(a3), container_(container), next_(next) {}
347
348 C* ReturnsIfEqual(const A1& a1, const A2& a2, const A3& a3) const {
349 if (IsEqual(a1_, a1) && IsEqual(a2_, a2) && IsEqual(a3_, a3)) {
350 return container_;
351 }
352 return nullptr;
353 }
354
355 uint64 Hash() const { return Hash3(a1_, a2_, a3_); }
356
357 void set_next(Cell* const next) { next_ = next; }
358
359 Cell* next() const { return next_; }
360
361 private:
362 const A1 a1_;
363 const A2 a2_;
364 const A3 a3_;
365 C* const container_;
366 Cell* next_;
367 };
368
369 Cell** array_;
370 int size_;
371 int num_items_;
372};
373
374// ----- Model Cache -----
375
376class NonReversibleCache : public ModelCache {
377 public:
378 typedef Cache1<IntExpr, IntExpr*> ExprIntExprCache;
379 typedef Cache1<IntExpr, std::vector<IntVar*> > VarArrayIntExprCache;
380
381 typedef Cache2<Constraint, IntVar*, int64> VarConstantConstraintCache;
382 typedef Cache2<Constraint, IntExpr*, IntExpr*> ExprExprConstraintCache;
383 typedef Cache2<IntExpr, IntVar*, int64> VarConstantIntExprCache;
384 typedef Cache2<IntExpr, IntExpr*, int64> ExprConstantIntExprCache;
385 typedef Cache2<IntExpr, IntExpr*, IntExpr*> ExprExprIntExprCache;
386 typedef Cache2<IntExpr, IntVar*, const std::vector<int64>&>
387 VarConstantArrayIntExprCache;
388 typedef Cache2<IntExpr, std::vector<IntVar*>, const std::vector<int64>&>
389 VarArrayConstantArrayIntExprCache;
390 typedef Cache2<IntExpr, std::vector<IntVar*>, int64>
391 VarArrayConstantIntExprCache;
392
393 typedef Cache3<IntExpr, IntVar*, int64, int64>
394 VarConstantConstantIntExprCache;
395 typedef Cache3<Constraint, IntVar*, int64, int64>
396 VarConstantConstantConstraintCache;
397 typedef Cache3<IntExpr, IntExpr*, IntExpr*, int64>
398 ExprExprConstantIntExprCache;
399
400 explicit NonReversibleCache(Solver* const solver)
401 : ModelCache(solver), void_constraints_(VOID_CONSTRAINT_MAX, nullptr) {
402 for (int i = 0; i < VAR_CONSTANT_CONSTRAINT_MAX; ++i) {
403 var_constant_constraints_.push_back(new VarConstantConstraintCache);
404 }
405 for (int i = 0; i < EXPR_EXPR_CONSTRAINT_MAX; ++i) {
406 expr_expr_constraints_.push_back(new ExprExprConstraintCache);
407 }
408 for (int i = 0; i < VAR_CONSTANT_CONSTANT_CONSTRAINT_MAX; ++i) {
409 var_constant_constant_constraints_.push_back(
410 new VarConstantConstantConstraintCache);
411 }
412 for (int i = 0; i < EXPR_EXPRESSION_MAX; ++i) {
413 expr_expressions_.push_back(new ExprIntExprCache);
414 }
415 for (int i = 0; i < EXPR_CONSTANT_EXPRESSION_MAX; ++i) {
416 expr_constant_expressions_.push_back(new ExprConstantIntExprCache);
417 }
418 for (int i = 0; i < EXPR_EXPR_EXPRESSION_MAX; ++i) {
419 expr_expr_expressions_.push_back(new ExprExprIntExprCache);
420 }
421 for (int i = 0; i < VAR_CONSTANT_CONSTANT_EXPRESSION_MAX; ++i) {
422 var_constant_constant_expressions_.push_back(
423 new VarConstantConstantIntExprCache);
424 }
425 for (int i = 0; i < VAR_CONSTANT_ARRAY_EXPRESSION_MAX; ++i) {
426 var_constant_array_expressions_.push_back(
427 new VarConstantArrayIntExprCache);
428 }
429 for (int i = 0; i < VAR_ARRAY_EXPRESSION_MAX; ++i) {
430 var_array_expressions_.push_back(new VarArrayIntExprCache);
431 }
432 for (int i = 0; i < VAR_ARRAY_CONSTANT_ARRAY_EXPRESSION_MAX; ++i) {
433 var_array_constant_array_expressions_.push_back(
434 new VarArrayConstantArrayIntExprCache);
435 }
436 for (int i = 0; i < VAR_ARRAY_CONSTANT_EXPRESSION_MAX; ++i) {
437 var_array_constant_expressions_.push_back(
438 new VarArrayConstantIntExprCache);
439 }
440 for (int i = 0; i < EXPR_EXPR_CONSTANT_EXPRESSION_MAX; ++i) {
441 expr_expr_constant_expressions_.push_back(
442 new ExprExprConstantIntExprCache);
443 }
444 }
445
446 ~NonReversibleCache() override {
447 gtl::STLDeleteElements(&var_constant_constraints_);
448 gtl::STLDeleteElements(&expr_expr_constraints_);
449 gtl::STLDeleteElements(&var_constant_constant_constraints_);
450 gtl::STLDeleteElements(&expr_expressions_);
451 gtl::STLDeleteElements(&expr_constant_expressions_);
452 gtl::STLDeleteElements(&expr_expr_expressions_);
453 gtl::STLDeleteElements(&var_constant_constant_expressions_);
454 gtl::STLDeleteElements(&var_constant_array_expressions_);
455 gtl::STLDeleteElements(&var_array_expressions_);
456 gtl::STLDeleteElements(&var_array_constant_array_expressions_);
457 gtl::STLDeleteElements(&var_array_constant_expressions_);
458 gtl::STLDeleteElements(&expr_expr_constant_expressions_);
459 }
460
461 void Clear() override {
462 for (int i = 0; i < VAR_CONSTANT_CONSTRAINT_MAX; ++i) {
463 var_constant_constraints_[i]->Clear();
464 }
465 for (int i = 0; i < EXPR_EXPR_CONSTRAINT_MAX; ++i) {
466 expr_expr_constraints_[i]->Clear();
467 }
468 for (int i = 0; i < VAR_CONSTANT_CONSTANT_CONSTRAINT_MAX; ++i) {
469 var_constant_constant_constraints_[i]->Clear();
470 }
471 for (int i = 0; i < EXPR_EXPRESSION_MAX; ++i) {
472 expr_expressions_[i]->Clear();
473 }
474 for (int i = 0; i < EXPR_CONSTANT_EXPRESSION_MAX; ++i) {
475 expr_constant_expressions_[i]->Clear();
476 }
477 for (int i = 0; i < EXPR_EXPR_EXPRESSION_MAX; ++i) {
478 expr_expr_expressions_[i]->Clear();
479 }
480 for (int i = 0; i < VAR_CONSTANT_CONSTANT_EXPRESSION_MAX; ++i) {
481 var_constant_constant_expressions_[i]->Clear();
482 }
483 for (int i = 0; i < VAR_CONSTANT_ARRAY_EXPRESSION_MAX; ++i) {
484 var_constant_array_expressions_[i]->Clear();
485 }
486 for (int i = 0; i < VAR_ARRAY_EXPRESSION_MAX; ++i) {
487 var_array_expressions_[i]->Clear();
488 }
489 for (int i = 0; i < VAR_ARRAY_CONSTANT_ARRAY_EXPRESSION_MAX; ++i) {
490 var_array_constant_array_expressions_[i]->Clear();
491 }
492 for (int i = 0; i < VAR_ARRAY_CONSTANT_EXPRESSION_MAX; ++i) {
493 var_array_constant_expressions_[i]->Clear();
494 }
495 for (int i = 0; i < EXPR_EXPR_CONSTANT_EXPRESSION_MAX; ++i) {
496 expr_expr_constant_expressions_[i]->Clear();
497 }
498 }
499
500 // Void Constraint.-
501
502 Constraint* FindVoidConstraint(VoidConstraintType type) const override {
503 DCHECK_GE(type, 0);
504 DCHECK_LT(type, VOID_CONSTRAINT_MAX);
505 return void_constraints_[type];
506 }
507
508 void InsertVoidConstraint(Constraint* const ct,
509 VoidConstraintType type) override {
510 DCHECK_GE(type, 0);
511 DCHECK_LT(type, VOID_CONSTRAINT_MAX);
512 DCHECK(ct != nullptr);
513 if (solver()->state() == Solver::OUTSIDE_SEARCH &&
514 !absl::GetFlag(FLAGS_cp_disable_cache)) {
515 void_constraints_[type] = ct;
516 }
517 }
518
519 // VarConstantConstraint.
520
521 Constraint* FindVarConstantConstraint(
522 IntVar* const var, int64 value,
523 VarConstantConstraintType type) const override {
524 DCHECK(var != nullptr);
525 DCHECK_GE(type, 0);
526 DCHECK_LT(type, VAR_CONSTANT_CONSTRAINT_MAX);
527 return var_constant_constraints_[type]->Find(var, value);
528 }
529
530 void InsertVarConstantConstraint(Constraint* const ct, IntVar* const var,
531 int64 value,
532 VarConstantConstraintType type) override {
533 DCHECK(ct != nullptr);
534 DCHECK(var != nullptr);
535 DCHECK_GE(type, 0);
536 DCHECK_LT(type, VAR_CONSTANT_CONSTRAINT_MAX);
537 if (solver()->state() == Solver::OUTSIDE_SEARCH &&
538 !absl::GetFlag(FLAGS_cp_disable_cache) &&
539 var_constant_constraints_[type]->Find(var, value) == nullptr) {
540 var_constant_constraints_[type]->UnsafeInsert(var, value, ct);
541 }
542 }
543
544 // Var Constant Constant Constraint.
545
546 Constraint* FindVarConstantConstantConstraint(
547 IntVar* const var, int64 value1, int64 value2,
548 VarConstantConstantConstraintType type) const override {
549 DCHECK(var != nullptr);
550 DCHECK_GE(type, 0);
551 DCHECK_LT(type, VAR_CONSTANT_CONSTANT_CONSTRAINT_MAX);
552 return var_constant_constant_constraints_[type]->Find(var, value1, value2);
553 }
554
555 void InsertVarConstantConstantConstraint(
556 Constraint* const ct, IntVar* const var, int64 value1, int64 value2,
557 VarConstantConstantConstraintType type) override {
558 DCHECK(ct != nullptr);
559 DCHECK(var != nullptr);
560 DCHECK_GE(type, 0);
561 DCHECK_LT(type, VAR_CONSTANT_CONSTANT_CONSTRAINT_MAX);
562 if (solver()->state() == Solver::OUTSIDE_SEARCH &&
563 !absl::GetFlag(FLAGS_cp_disable_cache) &&
564 var_constant_constant_constraints_[type]->Find(var, value1, value2) ==
565 nullptr) {
566 var_constant_constant_constraints_[type]->UnsafeInsert(var, value1,
567 value2, ct);
568 }
569 }
570
571 // Var Var Constraint.
572
573 Constraint* FindExprExprConstraint(
574 IntExpr* const var1, IntExpr* const var2,
575 ExprExprConstraintType type) const override {
576 DCHECK(var1 != nullptr);
577 DCHECK(var2 != nullptr);
578 DCHECK_GE(type, 0);
579 DCHECK_LT(type, EXPR_EXPR_CONSTRAINT_MAX);
580 return expr_expr_constraints_[type]->Find(var1, var2);
581 }
582
583 void InsertExprExprConstraint(Constraint* const ct, IntExpr* const var1,
584 IntExpr* const var2,
585 ExprExprConstraintType type) override {
586 DCHECK(ct != nullptr);
587 DCHECK(var1 != nullptr);
588 DCHECK(var2 != nullptr);
589 DCHECK_GE(type, 0);
590 DCHECK_LT(type, EXPR_EXPR_CONSTRAINT_MAX);
591 if (solver()->state() == Solver::OUTSIDE_SEARCH &&
592 !absl::GetFlag(FLAGS_cp_disable_cache) &&
593 expr_expr_constraints_[type]->Find(var1, var2) == nullptr) {
594 expr_expr_constraints_[type]->UnsafeInsert(var1, var2, ct);
595 }
596 }
597
598 // Expr Expression.
599
600 IntExpr* FindExprExpression(IntExpr* const expr,
601 ExprExpressionType type) const override {
602 DCHECK(expr != nullptr);
603 DCHECK_GE(type, 0);
604 DCHECK_LT(type, EXPR_EXPRESSION_MAX);
605 return expr_expressions_[type]->Find(expr);
606 }
607
608 void InsertExprExpression(IntExpr* const expression, IntExpr* const expr,
609 ExprExpressionType type) override {
610 DCHECK(expression != nullptr);
611 DCHECK(expr != nullptr);
612 DCHECK_GE(type, 0);
613 DCHECK_LT(type, EXPR_EXPRESSION_MAX);
614 if (solver()->state() == Solver::OUTSIDE_SEARCH &&
615 !absl::GetFlag(FLAGS_cp_disable_cache) &&
616 expr_expressions_[type]->Find(expr) == nullptr) {
617 expr_expressions_[type]->UnsafeInsert(expr, expression);
618 }
619 }
620
621 // Expr Constant Expressions.
622
623 IntExpr* FindExprConstantExpression(
624 IntExpr* const expr, int64 value,
625 ExprConstantExpressionType type) const override {
626 DCHECK(expr != nullptr);
627 DCHECK_GE(type, 0);
628 DCHECK_LT(type, EXPR_CONSTANT_EXPRESSION_MAX);
629 return expr_constant_expressions_[type]->Find(expr, value);
630 }
631
632 void InsertExprConstantExpression(IntExpr* const expression,
633 IntExpr* const expr, int64 value,
634 ExprConstantExpressionType type) override {
635 DCHECK(expression != nullptr);
636 DCHECK(expr != nullptr);
637 DCHECK_GE(type, 0);
638 DCHECK_LT(type, EXPR_CONSTANT_EXPRESSION_MAX);
639 if (solver()->state() == Solver::OUTSIDE_SEARCH &&
640 !absl::GetFlag(FLAGS_cp_disable_cache) &&
641 expr_constant_expressions_[type]->Find(expr, value) == nullptr) {
642 expr_constant_expressions_[type]->UnsafeInsert(expr, value, expression);
643 }
644 }
645
646 // Expr Expr Expression.
647
648 IntExpr* FindExprExprExpression(IntExpr* const var1, IntExpr* const var2,
649 ExprExprExpressionType type) const override {
650 DCHECK(var1 != nullptr);
651 DCHECK(var2 != nullptr);
652 DCHECK_GE(type, 0);
653 DCHECK_LT(type, EXPR_EXPR_EXPRESSION_MAX);
654 return expr_expr_expressions_[type]->Find(var1, var2);
655 }
656
657 void InsertExprExprExpression(IntExpr* const expression, IntExpr* const var1,
658 IntExpr* const var2,
659 ExprExprExpressionType type) override {
660 DCHECK(expression != nullptr);
661 DCHECK(var1 != nullptr);
662 DCHECK(var2 != nullptr);
663 DCHECK_GE(type, 0);
664 DCHECK_LT(type, EXPR_EXPR_EXPRESSION_MAX);
665 if (solver()->state() == Solver::OUTSIDE_SEARCH &&
666 !absl::GetFlag(FLAGS_cp_disable_cache) &&
667 expr_expr_expressions_[type]->Find(var1, var2) == nullptr) {
668 expr_expr_expressions_[type]->UnsafeInsert(var1, var2, expression);
669 }
670 }
671
672 // Expr Expr Constant Expression.
673
674 IntExpr* FindExprExprConstantExpression(
675 IntExpr* const var1, IntExpr* const var2, int64 constant,
676 ExprExprConstantExpressionType type) const override {
677 DCHECK(var1 != nullptr);
678 DCHECK(var2 != nullptr);
679 DCHECK_GE(type, 0);
680 DCHECK_LT(type, EXPR_EXPR_CONSTANT_EXPRESSION_MAX);
681 return expr_expr_constant_expressions_[type]->Find(var1, var2, constant);
682 }
683
684 void InsertExprExprConstantExpression(
685 IntExpr* const expression, IntExpr* const var1, IntExpr* const var2,
686 int64 constant, ExprExprConstantExpressionType type) override {
687 DCHECK(expression != nullptr);
688 DCHECK(var1 != nullptr);
689 DCHECK(var2 != nullptr);
690 DCHECK_GE(type, 0);
691 DCHECK_LT(type, EXPR_EXPR_CONSTANT_EXPRESSION_MAX);
692 if (solver()->state() == Solver::OUTSIDE_SEARCH &&
693 !absl::GetFlag(FLAGS_cp_disable_cache) &&
694 expr_expr_constant_expressions_[type]->Find(var1, var2, constant) ==
695 nullptr) {
696 expr_expr_constant_expressions_[type]->UnsafeInsert(var1, var2, constant,
697 expression);
698 }
699 }
700
701 // Var Constant Constant Expression.
702
703 IntExpr* FindVarConstantConstantExpression(
704 IntVar* const var, int64 value1, int64 value2,
705 VarConstantConstantExpressionType type) const override {
706 DCHECK(var != nullptr);
707 DCHECK_GE(type, 0);
708 DCHECK_LT(type, VAR_CONSTANT_CONSTANT_EXPRESSION_MAX);
709 return var_constant_constant_expressions_[type]->Find(var, value1, value2);
710 }
711
712 void InsertVarConstantConstantExpression(
713 IntExpr* const expression, IntVar* const var, int64 value1, int64 value2,
714 VarConstantConstantExpressionType type) override {
715 DCHECK(expression != nullptr);
716 DCHECK(var != nullptr);
717 DCHECK_GE(type, 0);
718 DCHECK_LT(type, VAR_CONSTANT_CONSTANT_EXPRESSION_MAX);
719 if (solver()->state() == Solver::OUTSIDE_SEARCH &&
720 !absl::GetFlag(FLAGS_cp_disable_cache) &&
721 var_constant_constant_expressions_[type]->Find(var, value1, value2) ==
722 nullptr) {
723 var_constant_constant_expressions_[type]->UnsafeInsert(
724 var, value1, value2, expression);
725 }
726 }
727
728 // Var Constant Array Expression.
729
730 IntExpr* FindVarConstantArrayExpression(
731 IntVar* const var, const std::vector<int64>& values,
732 VarConstantArrayExpressionType type) const override {
733 DCHECK(var != nullptr);
734 DCHECK_GE(type, 0);
735 DCHECK_LT(type, VAR_CONSTANT_ARRAY_EXPRESSION_MAX);
736 return var_constant_array_expressions_[type]->Find(var, values);
737 }
738
739 void InsertVarConstantArrayExpression(
740 IntExpr* const expression, IntVar* const var,
741 const std::vector<int64>& values,
742 VarConstantArrayExpressionType type) override {
743 DCHECK(expression != nullptr);
744 DCHECK(var != nullptr);
745 DCHECK_GE(type, 0);
746 DCHECK_LT(type, VAR_CONSTANT_ARRAY_EXPRESSION_MAX);
747 if (solver()->state() == Solver::OUTSIDE_SEARCH &&
748 !absl::GetFlag(FLAGS_cp_disable_cache) &&
749 var_constant_array_expressions_[type]->Find(var, values) == nullptr) {
750 var_constant_array_expressions_[type]->UnsafeInsert(var, values,
751 expression);
752 }
753 }
754
755 // Var Array Expression.
756
757 IntExpr* FindVarArrayExpression(const std::vector<IntVar*>& vars,
758 VarArrayExpressionType type) const override {
759 DCHECK_GE(type, 0);
760 DCHECK_LT(type, VAR_ARRAY_EXPRESSION_MAX);
761 return var_array_expressions_[type]->Find(vars);
762 }
763
764 void InsertVarArrayExpression(IntExpr* const expression,
765 const std::vector<IntVar*>& vars,
766 VarArrayExpressionType type) override {
767 DCHECK(expression != nullptr);
768 DCHECK_GE(type, 0);
769 DCHECK_LT(type, VAR_ARRAY_EXPRESSION_MAX);
770 if (solver()->state() == Solver::OUTSIDE_SEARCH &&
771 !absl::GetFlag(FLAGS_cp_disable_cache) &&
772 var_array_expressions_[type]->Find(vars) == nullptr) {
773 var_array_expressions_[type]->UnsafeInsert(vars, expression);
774 }
775 }
776
777 // Var Array Constant Array Expressions.
778
779 IntExpr* FindVarArrayConstantArrayExpression(
780 const std::vector<IntVar*>& vars, const std::vector<int64>& values,
781 VarArrayConstantArrayExpressionType type) const override {
782 DCHECK_GE(type, 0);
783 DCHECK_LT(type, VAR_ARRAY_CONSTANT_ARRAY_EXPRESSION_MAX);
784 return var_array_constant_array_expressions_[type]->Find(vars, values);
785 }
786
787 void InsertVarArrayConstantArrayExpression(
788 IntExpr* const expression, const std::vector<IntVar*>& vars,
789 const std::vector<int64>& values,
790 VarArrayConstantArrayExpressionType type) override {
791 DCHECK(expression != nullptr);
792 DCHECK_GE(type, 0);
793 DCHECK_LT(type, VAR_ARRAY_CONSTANT_ARRAY_EXPRESSION_MAX);
794 if (solver()->state() != Solver::IN_SEARCH &&
795 var_array_constant_array_expressions_[type]->Find(vars, values) ==
796 nullptr) {
797 var_array_constant_array_expressions_[type]->UnsafeInsert(vars, values,
798 expression);
799 }
800 }
801
802 // Var Array Constant Expressions.
803
804 IntExpr* FindVarArrayConstantExpression(
805 const std::vector<IntVar*>& vars, int64 value,
806 VarArrayConstantExpressionType type) const override {
807 DCHECK_GE(type, 0);
808 DCHECK_LT(type, VAR_ARRAY_CONSTANT_EXPRESSION_MAX);
809 return var_array_constant_expressions_[type]->Find(vars, value);
810 }
811
812 void InsertVarArrayConstantExpression(
813 IntExpr* const expression, const std::vector<IntVar*>& vars, int64 value,
814 VarArrayConstantExpressionType type) override {
815 DCHECK(expression != nullptr);
816 DCHECK_GE(type, 0);
817 DCHECK_LT(type, VAR_ARRAY_CONSTANT_EXPRESSION_MAX);
818 if (solver()->state() != Solver::IN_SEARCH &&
819 var_array_constant_expressions_[type]->Find(vars, value) == nullptr) {
820 var_array_constant_expressions_[type]->UnsafeInsert(vars, value,
821 expression);
822 }
823 }
824
825 private:
826 std::vector<Constraint*> void_constraints_;
827 std::vector<VarConstantConstraintCache*> var_constant_constraints_;
828 std::vector<ExprExprConstraintCache*> expr_expr_constraints_;
829 std::vector<VarConstantConstantConstraintCache*>
830 var_constant_constant_constraints_;
831 std::vector<ExprIntExprCache*> expr_expressions_;
832 std::vector<ExprConstantIntExprCache*> expr_constant_expressions_;
833 std::vector<ExprExprIntExprCache*> expr_expr_expressions_;
834 std::vector<VarConstantConstantIntExprCache*>
835 var_constant_constant_expressions_;
836 std::vector<VarConstantArrayIntExprCache*> var_constant_array_expressions_;
837 std::vector<VarArrayIntExprCache*> var_array_expressions_;
838 std::vector<VarArrayConstantArrayIntExprCache*>
839 var_array_constant_array_expressions_;
840 std::vector<VarArrayConstantIntExprCache*> var_array_constant_expressions_;
841 std::vector<ExprExprConstantIntExprCache*> expr_expr_constant_expressions_;
842};
843} // namespace
844
846 return new NonReversibleCache(solver);
847}
848
849ModelCache* Solver::Cache() const { return model_cache_.get(); }
850} // namespace operations_research
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define DCHECK(condition)
Definition: base/logging.h:884
Implements a complete cache for model elements: expressions and constraints.
ModelCache(Solver *const solver)
Definition: model_cache.cc:30
@ OUTSIDE_SEARCH
Before search, after search.
@ IN_SEARCH
Executing the search code.
ModelCache * Cache() const
Returns the cache of the model.
Definition: model_cache.cc:849
Block * next
const Constraint * ct
int64 value
IntVar * var
Definition: expr_array.cc:1858
int64_t int64
uint64_t uint64
ABSL_DECLARE_FLAG(int, cache_initial_size)
ABSL_FLAG(bool, cp_disable_cache, false, "Disable caching of model objects")
Definition: cleanup.h:22
void STLDeleteElements(T *container)
Definition: stl_util.h:372
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
ModelCache * BuildModelCache(Solver *const solver)
Definition: model_cache.cc:845
uint64 Hash1(uint64 value)
Hash functions.
static void mix(uint32 &a, uint32 &b, uint32 &c)
Definition: hash.h:28
uint64 Hash(uint64 num, uint64 c)
Definition: hash.h:150