Scippy

SCIP

Solving Constraint Integer Programs

misc.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2019 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file misc.c
17  * @brief miscellaneous methods
18  * @author Tobias Achterberg
19  * @author Gerald Gamrath
20  * @author Stefan Heinz
21  * @author Michael Winkler
22  * @author Kati Wolter
23  * @author Gregor Hendel
24  */
25 
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
27 
28 #include <assert.h>
29 #include <string.h>
30 #include <stdarg.h>
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <errno.h>
34 
35 #include "scip/def.h"
36 #include "scip/pub_message.h"
37 #include "scip/misc.h"
38 #include "scip/intervalarith.h"
39 #include "scip/pub_misc.h"
40 
41 #ifndef NDEBUG
42 #include "scip/struct_misc.h"
43 #endif
44 
45 /*
46  * methods for statistical tests
47  */
48 
49 #define SQRTOFTWO 1.4142136 /**< the square root of 2 with sufficient precision */
50 
51 /**< contains all critical values for a one-sided two sample t-test up to 15 degrees of freedom
52  * a critical value represents a threshold for rejecting the null-hypothesis in hypothesis testing at
53  * a certain confidence level;
54  *
55  * access through method SCIPstudentTGetCriticalValue()
56  *
57  * source: German Wikipedia
58  *
59  * for confidence levels
60  * c =
61  * 0.75 0.875 0.90 0.95 0.975 (one-sided)
62  * 0.50 0.750 0.80 0.90 0.950 (two-sided)
63  *
64  */
65 static const SCIP_Real studentt_quartiles[] = { /* df:*/
66  1.000, 2.414, 3.078, 6.314, 12.706, /* 1 */
67  0.816, 1.604, 1.886, 2.920, 4.303, /* 2 */
68  0.765, 1.423, 1.638, 2.353, 3.182, /* 3 */
69  0.741, 1.344, 1.533, 2.132, 2.776, /* 4 */
70  0.727, 1.301, 1.476, 2.015, 2.571, /* 5 */
71  0.718, 1.273, 1.440, 1.943, 2.447, /* 6 */
72  0.711, 1.254, 1.415, 1.895, 2.365, /* 7 */
73  0.706, 1.240, 1.397, 1.860, 2.306, /* 8 */
74  0.703, 1.230, 1.383, 1.833, 2.262, /* 9 */
75  0.700, 1.221, 1.372, 1.812, 2.228, /* 10 */
76  0.697, 1.214, 1.363, 1.796, 2.201, /* 11 */
77  0.695, 1.209, 1.356, 1.782, 2.179, /* 12 */
78  0.694, 1.204, 1.350, 1.771, 2.160, /* 13 */
79  0.692, 1.200, 1.345, 1.761, 2.145, /* 14 */
80  0.691, 1.197, 1.341, 1.753, 2.131 /* 15 */
81 };
82 
83 /**< critical values for higher degrees of freedom of Student-T distribution for the same error probabilities; infact,
84  * these are critical values of the standard normal distribution with mean 0 and variance 1
85  */
87  0.674, 1.150, 1.282, 1.645, 1.960
88 };
89 
90 /** the maximum degrees of freedom represented before switching to normal approximation */
91 static const int studentt_maxdf = sizeof(studentt_quartiles)/(5 * sizeof(SCIP_Real));
92 
93 /** get critical value of a Student-T distribution for a given number of degrees of freedom at a confidence level */
95  SCIP_CONFIDENCELEVEL clevel, /**< (one-sided) confidence level */
96  int df /**< degrees of freedom */
97  )
98 {
99  if( df > studentt_maxdf )
100  return studentt_quartilesabove[(int)clevel];
101  else
102  return studentt_quartiles[(int)clevel + 5 * (df - 1)];
103 }
104 
105 /** compute a t-value for the hypothesis that x and y are from the same population; Assuming that
106  * x and y represent normally distributed random samples with equal variance, the returned value
107  * comes from a Student-T distribution with countx + county - 2 degrees of freedom; this
108  * value can be compared with a critical value (see also SCIPstudentTGetCriticalValue()) at
109  * a predefined confidence level for checking if x and y significantly differ in location
110  */
112  SCIP_Real meanx, /**< the mean of the first distribution */
113  SCIP_Real meany, /**< the mean of the second distribution */
114  SCIP_Real variancex, /**< the variance of the x-distribution */
115  SCIP_Real variancey, /**< the variance of the y-distribution */
116  SCIP_Real countx, /**< number of samples of x */
117  SCIP_Real county /**< number of samples of y */
118  )
119 {
120  SCIP_Real pooledvariance;
121  SCIP_Real tresult;
122 
123  /* too few samples */
124  if( countx < 1.9 || county < 1.9 )
125  return SCIP_INVALID;
126 
127  /* pooled variance is the weighted average of the two variances */
128  pooledvariance = (countx - 1) * variancex + (county - 1) * variancey;
129  pooledvariance /= (countx + county - 2);
130 
131  /* a variance close to zero means the distributions are basically constant */
132  pooledvariance = MAX(pooledvariance, 1e-9);
133 
134  /* tresult can be understood as realization of a Student-T distributed variable with
135  * countx + county - 2 degrees of freedom
136  */
137  tresult = (meanx - meany) / pooledvariance;
138  tresult *= SQRT(countx * county / (countx + county));
139 
140  return tresult;
141 }
142 
143 /** returns the value of the Gauss error function evaluated at a given point */
145  SCIP_Real x /**< value to evaluate */
146  )
147 {
148 #if defined(_WIN32) || defined(_WIN64)
149  SCIP_Real a1, a2, a3, a4, a5, p, t, y;
150  int sign;
151 
152  a1 = 0.254829592;
153  a2 = -0.284496736;
154  a3 = 1.421413741;
155  a4 = -1.453152027;
156  a5 = 1.061405429;
157  p = 0.3275911;
158 
159  sign = (x >= 0) ? 1 : -1;
160  x = REALABS(x);
161 
162  t = 1.0/(1.0 + p*x);
163  y = 1.0 - (((((a5*t + a4)*t) + a3)*t + a2)*t + a1)*t*exp(-x*x);
164  return sign * y;
165 #else
166  return erf(x);
167 #endif
168 }
169 
170 /** get critical value of a standard normal distribution at a given confidence level */
172  SCIP_CONFIDENCELEVEL clevel /**< (one-sided) confidence level */
173  )
174 {
175  return studentt_quartilesabove[(int)clevel];
176 }
177 
178 /** calculates the cumulative distribution P(-infinity <= x <= value) that a normally distributed
179  * random variable x takes a value between -infinity and parameter \p value.
180  *
181  * The distribution is given by the respective mean and deviation. This implementation
182  * uses the error function SCIPerf().
183  */
185  SCIP_Real mean, /**< the mean value of the distribution */
186  SCIP_Real variance, /**< the square of the deviation of the distribution */
187  SCIP_Real value /**< the upper limit of the calculated distribution integral */
188  )
189 {
190  SCIP_Real normvalue;
191  SCIP_Real std;
192 
193  /* we need to calculate the standard deviation from the variance */
194  assert(variance >= -1e-9);
195  if( variance < 1e-9 )
196  std = 0.0;
197  else
198  std = sqrt(variance);
199 
200  /* special treatment for zero variance */
201  if( std < 1e-9 )
202  {
203  if( value < mean + 1e-9 )
204  return 1.0;
205  else
206  return 0.0;
207  }
208  assert( std != 0.0 ); /* for lint */
209 
210  /* scale and translate to standard normal distribution. Factor sqrt(2) is needed for SCIPerf() function */
211  normvalue = (value - mean)/(std * SQRTOFTWO);
212 
213  SCIPdebugMessage(" Normalized value %g = ( %g - %g ) / (%g * 1.4142136)\n", normvalue, value, mean, std);
214 
215  /* calculate the cumulative distribution function for normvalue. For negative normvalues, we negate the normvalue and
216  * use the oddness of the SCIPerf()-function; special treatment for values close to zero.
217  */
218  if( normvalue < 1e-9 && normvalue > -1e-9 )
219  return .5;
220  else if( normvalue > 0 )
221  {
222  SCIP_Real erfresult;
223 
224  erfresult = SCIPerf(normvalue);
225  return erfresult / 2.0 + 0.5;
226  }
227  else
228  {
229  SCIP_Real erfresult;
230 
231  erfresult = SCIPerf(-normvalue);
232 
233  return 0.5 - erfresult / 2.0;
234  }
235 }
236 
237 /*
238  * SCIP regression methods
239  */
240 
241 /** returns the number of observations of this regression */
243  SCIP_REGRESSION* regression /**< regression data structure */
244  )
245 {
246  assert(regression != NULL);
247 
248  return regression->nobservations;
249 }
250 
251 /** return the current slope of the regression */
253  SCIP_REGRESSION* regression /**< regression data structure */
254  )
255 {
256  assert(regression != NULL);
257 
258  return regression->slope;
259 }
260 
261 /** get the current y-intercept of the regression */
263  SCIP_REGRESSION* regression /**< regression data structure */
264  )
265 {
266  assert(regression != NULL);
267 
268  return regression->intercept;
269 }
270 
271 /** recomputes regression coefficients from available observation data */
272 static
274  SCIP_REGRESSION* regression /**< regression data structure */
275  )
276 {
277  /* regression coefficients require two or more observations and variance in x */
278  if( regression->nobservations <= 1 || EPSZ(regression->variancesumx, 1e-9) )
279  {
280  regression->slope = SCIP_INVALID;
281  regression->intercept = SCIP_INVALID;
282  regression->corrcoef = SCIP_INVALID;
283  }
284  else if( EPSZ(regression->variancesumy, 1e-9) )
285  {
286  /* if there is no variance in the y's (but in the x's), the regression line is horizontal with y-intercept through the mean y */
287  regression->slope = 0.0;
288  regression->corrcoef = 0.0;
289  regression->intercept = regression->meany;
290  }
291  else
292  {
293  /* we ruled this case out already, but to please some compilers... */
294  assert(regression->variancesumx > 0.0);
295  assert(regression->variancesumy > 0.0);
296 
297  /* compute slope */
298  regression->slope = (regression->sumxy - regression->nobservations * regression->meanx * regression->meany) / regression->variancesumx;
299 
300  /* compute y-intercept */
301  regression->intercept = regression->meany - regression->slope * regression->meanx;
302 
303  /* compute empirical correlation coefficient */
304  regression->corrcoef = (regression->sumxy - regression->nobservations * regression->meanx * regression->meany) /
305  sqrt(regression->variancesumx * regression->variancesumy);
306  }
307 }
308 
309 /* incremental update of statistics describing mean and variance */
310 static
312  SCIP_Real value, /**< current value to be added to incremental statistics */
313  SCIP_Real* meanptr, /**< pointer to value of current mean */
314  SCIP_Real* sumvarptr, /**< pointer to the value of the current variance sum term */
315  int nobservations, /**< total number of observations */
316  SCIP_Bool add /**< TRUE if the value should be added, FALSE for removing it */
317  )
318 {
319  SCIP_Real oldmean;
320  SCIP_Real addfactor;
321  assert(meanptr != NULL);
322  assert(sumvarptr != NULL);
323  assert(nobservations > 0 || add);
324 
325  addfactor = add ? 1.0 : -1.0;
326 
327  oldmean = *meanptr;
328  *meanptr = oldmean + addfactor * (value - oldmean)/(SCIP_Real)nobservations;
329  *sumvarptr += addfactor * (value - oldmean) * (value - (*meanptr));
330 
331  /* it may happen that *sumvarptr is slightly negative, especially after a series of add/removal operations */
332  assert(*sumvarptr >= -1e-4);
333  *sumvarptr = MAX(0.0, *sumvarptr);
334 }
335 
336 /** removes an observation (x,y) from the regression */
338  SCIP_REGRESSION* regression, /**< regression data structure */
339  SCIP_Real x, /**< X of observation */
340  SCIP_Real y /**< Y of the observation */
341  )
342 {
343  assert(regression != NULL);
344  assert(regression->nobservations > 0);
345 
346  /* simply call the reset function in the case of a single remaining observation to avoid numerical troubles */
347  if( regression->nobservations == 1 )
348  {
349  SCIPregressionReset(regression);
350  }
351  else
352  {
353  SCIP_Bool add = FALSE;
354  --regression->nobservations;
355 
356  /* decrement individual means and variances */
357  incrementalStatsUpdate(x, &regression->meanx, &regression->variancesumx, regression->nobservations, add);
358  incrementalStatsUpdate(y, &regression->meany, &regression->variancesumy, regression->nobservations, add);
359 
360  /* decrement product sum */
361  regression->sumxy -= (x * y);
362  }
363 
364  /* recompute regression parameters */
365  regressionRecompute(regression);
366 }
367 
368 /** update regression by a new observation (x,y) */
370  SCIP_REGRESSION* regression, /**< regression data structure */
371  SCIP_Real x, /**< X of observation */
372  SCIP_Real y /**< Y of the observation */
373  )
374 {
375  SCIP_Bool add = TRUE;
376  assert(regression != NULL);
377 
378  ++(regression->nobservations);
379  incrementalStatsUpdate(x, &regression->meanx, &regression->variancesumx, regression->nobservations, add);
380  incrementalStatsUpdate(y, &regression->meany, &regression->variancesumy, regression->nobservations, add);
381 
382  regression->sumxy += x * y;
383 
384  regressionRecompute(regression);
385 }
386 
387 /** reset regression data structure */
389  SCIP_REGRESSION* regression /**< regression data structure */
390  )
391 {
392  regression->intercept = SCIP_INVALID;
393  regression->slope = SCIP_INVALID;
394  regression->corrcoef = SCIP_INVALID;
395  regression->meanx = 0;
396  regression->variancesumx = 0;
397  regression->sumxy = 0;
398  regression->meany = 0;
399  regression->variancesumy = 0;
400  regression->nobservations = 0;
401 }
402 
403 /** creates and resets a regression */
405  SCIP_REGRESSION** regression /**< regression data structure */
406  )
407 {
408  assert(regression != NULL);
409 
410  /* allocate necessary memory */
411  SCIP_ALLOC (BMSallocMemory(regression) );
412 
413  /* reset the regression */
414  SCIPregressionReset(*regression);
415 
416  return SCIP_OKAY;
417 }
418 
419 /** creates and resets a regression */
421  SCIP_REGRESSION** regression /**< regression data structure */
422  )
423 {
424  BMSfreeMemory(regression);
425 }
426 
427 /** calculate memory size for dynamically allocated arrays (copied from scip/set.c) */
428 static
430  int initsize, /**< initial size of array */
431  SCIP_Real growfac, /**< growing factor of array */
432  int num /**< minimum number of entries to store */
433  )
434 {
435  int size;
436 
437  assert(initsize >= 0);
438  assert(growfac >= 1.0);
439  assert(num >= 0);
440 
441  if( growfac == 1.0 )
442  size = MAX(initsize, num);
443  else
444  {
445  int oldsize;
446 
447  /* calculate the size with this loop, such that the resulting numbers are always the same (-> block memory) */
448  initsize = MAX(initsize, 4);
449  size = initsize;
450  oldsize = size - 1;
451 
452  /* second condition checks against overflow */
453  while( size < num && size > oldsize )
454  {
455  oldsize = size;
456  size = (int)(growfac * size + initsize);
457  }
458 
459  /* if an overflow happened, set the correct value */
460  if( size <= oldsize )
461  size = num;
462  }
463 
464  assert(size >= initsize);
465  assert(size >= num);
466 
467  return size;
468 }
469 
470 /*
471  * GML graphical printing methods
472  * For a detailed format decription see http://docs.yworks.com/yfiles/doc/developers-guide/gml.html
473  */
474 
475 #define GMLNODEWIDTH 120.0
476 #define GMLNODEHEIGTH 30.0
477 #define GMLFONTSIZE 13
478 #define GMLNODETYPE "rectangle"
479 #define GMLNODEFILLCOLOR "#ff0000"
480 #define GMLEDGECOLOR "black"
481 #define GMLNODEBORDERCOLOR "#000000"
482 
483 
484 /** writes a node section to the given graph file */
486  FILE* file, /**< file to write to */
487  unsigned int id, /**< id of the node */
488  const char* label, /**< label of the node */
489  const char* nodetype, /**< type of the node, or NULL */
490  const char* fillcolor, /**< color of the node's interior, or NULL */
491  const char* bordercolor /**< color of the node's border, or NULL */
492  )
493 {
494  assert(file != NULL);
495  assert(label != NULL);
496 
497  fprintf(file, " node\n");
498  fprintf(file, " [\n");
499  fprintf(file, " id %u\n", id);
500  fprintf(file, " label \"%s\"\n", label);
501  fprintf(file, " graphics\n");
502  fprintf(file, " [\n");
503  fprintf(file, " w %g\n", GMLNODEWIDTH);
504  fprintf(file, " h %g\n", GMLNODEHEIGTH);
505 
506  if( nodetype != NULL )
507  fprintf(file, " type \"%s\"\n", nodetype);
508  else
509  fprintf(file, " type \"%s\"\n", GMLNODETYPE);
510 
511  if( fillcolor != NULL )
512  fprintf(file, " fill \"%s\"\n", fillcolor);
513  else
514  fprintf(file, " fill \"%s\"\n", GMLNODEFILLCOLOR);
515 
516  if( bordercolor != NULL )
517  fprintf(file, " outline \"%s\"\n", bordercolor);
518  else
519  fprintf(file, " outline \"%s\"\n", GMLNODEBORDERCOLOR);
520 
521  fprintf(file, " ]\n");
522  fprintf(file, " LabelGraphics\n");
523  fprintf(file, " [\n");
524  fprintf(file, " text \"%s\"\n", label);
525  fprintf(file, " fontSize %d\n", GMLFONTSIZE);
526  fprintf(file, " fontName \"Dialog\"\n");
527  fprintf(file, " anchor \"c\"\n");
528  fprintf(file, " ]\n");
529  fprintf(file, " ]\n");
530 }
531 
532 /** writes a node section including weight to the given graph file */
534  FILE* file, /**< file to write to */
535  unsigned int id, /**< id of the node */
536  const char* label, /**< label of the node */
537  const char* nodetype, /**< type of the node, or NULL */
538  const char* fillcolor, /**< color of the node's interior, or NULL */
539  const char* bordercolor, /**< color of the node's border, or NULL */
540  SCIP_Real weight /**< weight of node */
541  )
542 {
543  assert(file != NULL);
544  assert(label != NULL);
545 
546  fprintf(file, " node\n");
547  fprintf(file, " [\n");
548  fprintf(file, " id %u\n", id);
549  fprintf(file, " label \"%s\"\n", label);
550  fprintf(file, " weight %g\n", weight);
551  fprintf(file, " graphics\n");
552  fprintf(file, " [\n");
553  fprintf(file, " w %g\n", GMLNODEWIDTH);
554  fprintf(file, " h %g\n", GMLNODEHEIGTH);
555 
556  if( nodetype != NULL )
557  fprintf(file, " type \"%s\"\n", nodetype);
558  else
559  fprintf(file, " type \"%s\"\n", GMLNODETYPE);
560 
561  if( fillcolor != NULL )
562  fprintf(file, " fill \"%s\"\n", fillcolor);
563  else
564  fprintf(file, " fill \"%s\"\n", GMLNODEFILLCOLOR);
565 
566  if( bordercolor != NULL )
567  fprintf(file, " outline \"%s\"\n", bordercolor);
568  else
569  fprintf(file, " outline \"%s\"\n", GMLNODEBORDERCOLOR);
570 
571  fprintf(file, " ]\n");
572  fprintf(file, " LabelGraphics\n");
573  fprintf(file, " [\n");
574  fprintf(file, " text \"%s\"\n", label);
575  fprintf(file, " fontSize %d\n", GMLFONTSIZE);
576  fprintf(file, " fontName \"Dialog\"\n");
577  fprintf(file, " anchor \"c\"\n");
578  fprintf(file, " ]\n");
579  fprintf(file, " ]\n");
580 }
581 
582 /** writes an edge section to the given graph file */
584  FILE* file, /**< file to write to */
585  unsigned int source, /**< source node id of the node */
586  unsigned int target, /**< target node id of the edge */
587  const char* label, /**< label of the edge, or NULL */
588  const char* color /**< color of the edge, or NULL */
589  )
590 {
591  assert(file != NULL);
592 
593  fprintf(file, " edge\n");
594  fprintf(file, " [\n");
595  fprintf(file, " source %u\n", source);
596  fprintf(file, " target %u\n", target);
597 
598  if( label != NULL)
599  fprintf(file, " label \"%s\"\n", label);
600 
601  fprintf(file, " graphics\n");
602  fprintf(file, " [\n");
603 
604  if( color != NULL )
605  fprintf(file, " fill \"%s\"\n", color);
606  else
607  fprintf(file, " fill \"%s\"\n", GMLEDGECOLOR);
608 
609  /* fprintf(file, " arrow \"both\"\n"); */
610  fprintf(file, " ]\n");
611 
612  if( label != NULL)
613  {
614  fprintf(file, " LabelGraphics\n");
615  fprintf(file, " [\n");
616  fprintf(file, " text \"%s\"\n", label);
617  fprintf(file, " fontSize %d\n", GMLFONTSIZE);
618  fprintf(file, " fontName \"Dialog\"\n");
619  fprintf(file, " anchor \"c\"\n");
620  fprintf(file, " ]\n");
621  }
622 
623  fprintf(file, " ]\n");
624 }
625 
626 /** writes an arc section to the given graph file */
628  FILE* file, /**< file to write to */
629  unsigned int source, /**< source node id of the node */
630  unsigned int target, /**< target node id of the edge */
631  const char* label, /**< label of the edge, or NULL */
632  const char* color /**< color of the edge, or NULL */
633  )
634 {
635  assert(file != NULL);
636 
637  fprintf(file, " edge\n");
638  fprintf(file, " [\n");
639  fprintf(file, " source %u\n", source);
640  fprintf(file, " target %u\n", target);
641 
642  if( label != NULL)
643  fprintf(file, " label \"%s\"\n", label);
644 
645  fprintf(file, " graphics\n");
646  fprintf(file, " [\n");
647 
648  if( color != NULL )
649  fprintf(file, " fill \"%s\"\n", color);
650  else
651  fprintf(file, " fill \"%s\"\n", GMLEDGECOLOR);
652 
653  fprintf(file, " targetArrow \"standard\"\n");
654  fprintf(file, " ]\n");
655 
656  if( label != NULL)
657  {
658  fprintf(file, " LabelGraphics\n");
659  fprintf(file, " [\n");
660  fprintf(file, " text \"%s\"\n", label);
661  fprintf(file, " fontSize %d\n", GMLFONTSIZE);
662  fprintf(file, " fontName \"Dialog\"\n");
663  fprintf(file, " anchor \"c\"\n");
664  fprintf(file, " ]\n");
665  }
666 
667  fprintf(file, " ]\n");
668 }
669 
670 /** writes the starting line to a GML graph file, does not open a file */
672  FILE* file, /**< file to write to */
673  SCIP_Bool directed /**< is the graph directed */
674  )
675 {
676  assert(file != NULL);
677 
678  fprintf(file, "graph\n");
679  fprintf(file, "[\n");
680  fprintf(file, " hierarchic 1\n");
681 
682  if( directed )
683  fprintf(file, " directed 1\n");
684 }
685 
686 /** writes the ending lines to a GML graph file, does not close a file */
688  FILE* file /**< file to close */
689  )
690 {
691  assert(file != NULL);
692 
693  fprintf(file, "]\n");
694 }
695 
696 
697 /*
698  * Sparse solution
699  */
700 
701 /** creates a sparse solution */
703  SCIP_SPARSESOL** sparsesol, /**< pointer to store the created sparse solution */
704  SCIP_VAR** vars, /**< variables in the sparse solution, must not contain continuous
705  * variables
706  */
707  int nvars, /**< number of variables to store, size of the lower and upper bound
708  * arrays
709  */
710  SCIP_Bool cleared /**< should the lower and upper bound arrays be cleared (entries set to
711  * 0)
712  */
713  )
714 {
715  assert(sparsesol != NULL);
716  assert(vars != NULL);
717  assert(nvars >= 0);
718 
719  SCIP_ALLOC( BMSallocMemory(sparsesol) );
720 
721 #ifndef NDEBUG
722  {
723  int v;
724 
725  for( v = nvars - 1; v >= 0; --v )
726  {
727  assert(vars[v] != NULL);
728  /* assert(SCIPvarGetType(vars[v]) != SCIP_VARTYPE_CONTINUOUS); */
729  }
730  }
731 #endif
732 
733  /* copy variables */
734  SCIP_ALLOC( BMSduplicateMemoryArray(&((*sparsesol)->vars), vars, nvars) );
735 
736  /* create bound arrays */
737  if( cleared )
738  {
739  SCIP_ALLOC( BMSallocClearMemoryArray(&((*sparsesol)->lbvalues), nvars) );
740  SCIP_ALLOC( BMSallocClearMemoryArray(&((*sparsesol)->ubvalues), nvars) );
741  }
742  else
743  {
744  SCIP_ALLOC( BMSallocMemoryArray(&((*sparsesol)->lbvalues), nvars) );
745  SCIP_ALLOC( BMSallocMemoryArray(&((*sparsesol)->ubvalues), nvars) );
746  }
747 
748  (*sparsesol)->nvars = nvars;
749 
750  return SCIP_OKAY;
751 }
752 
753 /** frees sparse solution */
755  SCIP_SPARSESOL** sparsesol /**< pointer to a sparse solution */
756  )
757 {
758  assert(sparsesol != NULL);
759  assert(*sparsesol != NULL);
760 
761  BMSfreeMemoryArray(&((*sparsesol)->vars));
762  BMSfreeMemoryArray(&((*sparsesol)->ubvalues));
763  BMSfreeMemoryArray(&((*sparsesol)->lbvalues));
764  BMSfreeMemory(sparsesol);
765 }
766 
767 /** returns the variables stored in the given sparse solution */
769  SCIP_SPARSESOL* sparsesol /**< a sparse solution */
770  )
771 {
772  assert(sparsesol != NULL);
773 
774  return sparsesol->vars;
775 }
776 
777 /** returns the number of variables stored in the given sparse solution */
779  SCIP_SPARSESOL* sparsesol /**< a sparse solution */
780  )
781 {
782  assert(sparsesol != NULL);
783 
784  return sparsesol->nvars;
785 }
786 
787 /** returns the lower bound array for all variables for a given sparse solution */
789  SCIP_SPARSESOL* sparsesol /**< a sparse solution */
790  )
791 {
792  assert(sparsesol != NULL);
793 
794  return sparsesol->lbvalues;
795 }
796 
797 /** returns the upper bound array for all variables for a given sparse solution */
799  SCIP_SPARSESOL* sparsesol /**< a sparse solution */
800  )
801 {
802  assert(sparsesol != NULL);
803 
804  return sparsesol->ubvalues;
805 }
806 
807 /** constructs the first solution of sparse solution (all variables are set to their lower bound value */
809  SCIP_SPARSESOL* sparsesol, /**< sparse solutions */
810  SCIP_Longint* sol, /**< array to store the first solution */
811  int nvars /**< number of variables */
812  )
813 {
814  SCIP_Longint* lbvalues;
815  int v;
816 
817  assert(sparsesol != NULL);
818  assert(sol != NULL);
819  assert(nvars == SCIPsparseSolGetNVars(sparsesol));
820 
821  lbvalues = SCIPsparseSolGetLbs(sparsesol);
822  assert(lbvalues != NULL);
823 
824  /* copy the lower bounds */
825  for( v = 0; v < nvars; ++v )
826  sol[v] = lbvalues[v];
827 }
828 
829 
830 /** constructs the next solution of the sparse solution and return whether there was one more or not */
832  SCIP_SPARSESOL* sparsesol, /**< sparse solutions */
833  SCIP_Longint* sol, /**< current solution array which get changed to the next solution */
834  int nvars /**< number of variables */
835  )
836 {
837  SCIP_Longint* lbvalues;
838  SCIP_Longint* ubvalues;
839  SCIP_Longint lbvalue;
840  SCIP_Longint ubvalue;
841  SCIP_Bool singular;
842  SCIP_Bool carryflag;
843  int v;
844 
845  assert(sparsesol != NULL);
846  assert(sol != NULL);
847 
848  if( nvars == 0 )
849  return FALSE;
850 
851  assert(nvars > 0);
852  assert(nvars == SCIPsparseSolGetNVars(sparsesol));
853 
854  lbvalues = SCIPsparseSolGetLbs(sparsesol);
855  ubvalues = SCIPsparseSolGetUbs(sparsesol);
856  assert(lbvalues != NULL);
857  assert(ubvalues != NULL);
858 
859  singular = TRUE;
860  carryflag = FALSE;
861 
862  for( v = 0; v < nvars; ++v )
863  {
864  lbvalue = lbvalues[v];
865  ubvalue = ubvalues[v];
866 
867  if( lbvalue < ubvalue )
868  {
869  singular = FALSE;
870 
871  if( carryflag == FALSE )
872  {
873  if( sol[v] < ubvalue )
874  {
875  sol[v]++;
876  break;
877  }
878  else
879  {
880  /* in the last solution the variables v was set to its upper bound value */
881  assert(sol[v] == ubvalue);
882  sol[v] = lbvalue;
883  carryflag = TRUE;
884  }
885  }
886  else
887  {
888  if( sol[v] < ubvalue )
889  {
890  sol[v]++;
891  carryflag = FALSE;
892  break;
893  }
894  else
895  {
896  assert(sol[v] == ubvalue);
897  sol[v] = lbvalue;
898  }
899  }
900  }
901  }
902 
903  return (!carryflag && !singular);
904 }
905 
906 
907 /*
908  * Queue
909  */
910 
911 /** resizes element memory to hold at least the given number of elements */
912 static
914  SCIP_QUEUE* queue, /**< pointer to a queue */
915  int minsize /**< minimal number of storable elements */
916  )
917 {
918  assert(queue != NULL);
919  assert(minsize > 0);
920 
921  if( minsize <= queue->size )
922  return SCIP_OKAY;
923 
924  queue->size = MAX(minsize, (int)(queue->size * queue->sizefac));
925  SCIP_ALLOC( BMSreallocMemoryArray(&queue->slots, queue->size) );
926 
927  return SCIP_OKAY;
928 }
929 
930 
931 /** creates a (circular) queue, best used if the size will be fixed or will not be increased that much */
933  SCIP_QUEUE** queue, /**< pointer to the new queue */
934  int initsize, /**< initial number of available element slots */
935  SCIP_Real sizefac /**< memory growing factor applied, if more element slots are needed */
936  )
937 {
938  assert(queue != NULL);
939 
940  initsize = MAX(1, initsize);
941  sizefac = MAX(1.0, sizefac);
942 
943  SCIP_ALLOC( BMSallocMemory(queue) );
944  (*queue)->firstfree = 0;
945  (*queue)->firstused = -1;
946  (*queue)->size = 0;
947  (*queue)->sizefac = sizefac;
948  (*queue)->slots = NULL;
949 
950  SCIP_CALL( queueResize(*queue, initsize) );
951 
952  return SCIP_OKAY;
953 }
954 
955 /** frees queue, but not the data elements themselves */
957  SCIP_QUEUE** queue /**< pointer to a queue */
958  )
959 {
960  assert(queue != NULL);
961 
962  BMSfreeMemoryArray(&(*queue)->slots);
963  BMSfreeMemory(queue);
964 }
965 
966 /** clears the queue, but doesn't free the data elements themselves */
968  SCIP_QUEUE* queue /**< queue */
969  )
970 {
971  assert(queue != NULL);
972 
973  queue->firstfree = 0;
974  queue->firstused = -1;
975 }
976 
977 /** reallocates slots if queue is necessary */
978 static
980  SCIP_QUEUE* queue /**< queue */
981  )
982 {
983  if( queue->firstfree == queue->firstused )
984  {
985  int sizediff;
986  int oldsize = queue->size;
987 
988  SCIP_CALL( queueResize(queue, queue->size+1) );
989  assert(oldsize < queue->size);
990 
991  sizediff = queue->size - oldsize;
992 
993  /* move the used memory at the slots to the end */
994  BMSmoveMemoryArray(&(queue->slots[queue->firstused + sizediff]), &(queue->slots[queue->firstused]), oldsize - queue->firstused); /*lint !e866*/
995  queue->firstused += sizediff;
996  }
997  assert(queue->firstfree != queue->firstused);
998 
999  return SCIP_OKAY;
1000 }
1001 
1002 /** checks and adjusts marker of first free and first used slot */
1003 static
1005  SCIP_QUEUE* queue /**< queue */
1006  )
1007 {
1008  /* if we saved the value at the last position we need to reset the firstfree position */
1009  if( queue->firstfree == queue->size )
1010  queue->firstfree = 0;
1011 
1012  /* if a first element was added, we need to update the firstused counter */
1013  if( queue->firstused == -1 )
1014  queue->firstused = 0;
1015 }
1016 
1017 /** inserts pointer element at the end of the queue */
1019  SCIP_QUEUE* queue, /**< queue */
1020  void* elem /**< element to be inserted */
1021  )
1022 {
1023  assert(queue != NULL);
1024  assert(queue->slots != NULL);
1025  assert(queue->firstused >= -1 && queue->firstused < queue->size);
1026  assert(queue->firstfree >= 0 && queue->firstused < queue->size);
1027  assert(queue->firstused > -1 || queue->firstfree == 0);
1028  assert(elem != NULL);
1029 
1030  /* check allocated memory */
1031  SCIP_CALL( queueCheckSize(queue) );
1032 
1033  /* insert element at the first free slot */
1034  queue->slots[queue->firstfree].ptr = elem;
1035  ++(queue->firstfree);
1036 
1037  /* check and adjust marker */
1038  queueCheckMarker(queue);
1039 
1040  return SCIP_OKAY;
1041 }
1042 
1043 /** inserts unsigned integer element at the end of the queue */
1045  SCIP_QUEUE* queue, /**< queue */
1046  unsigned int elem /**< element to be inserted */
1047  )
1048 {
1049  assert(queue != NULL);
1050  assert(queue->slots != NULL);
1051  assert(queue->firstused >= -1 && queue->firstused < queue->size);
1052  assert(queue->firstfree >= 0 && queue->firstused < queue->size);
1053  assert(queue->firstused > -1 || queue->firstfree == 0);
1054 
1055  /* check allocated memory */
1056  SCIP_CALL( queueCheckSize(queue) );
1057 
1058  /* insert element at the first free slot */
1059  queue->slots[queue->firstfree].uinteger = elem;
1060  ++(queue->firstfree);
1061 
1062  /* check and adjust marker */
1063  queueCheckMarker(queue);
1064 
1065  return SCIP_OKAY;
1066 }
1067 
1068 /** removes and returns the first pointer element of the queue, or NULL if no element exists */
1070  SCIP_QUEUE* queue /**< queue */
1071  )
1072 {
1073  int pos;
1074 
1075  assert(queue != NULL);
1076  assert(queue->firstused >= -1 && queue->firstused < queue->size);
1077  assert(queue->firstfree >= 0 && queue->firstused < queue->size);
1078  assert(queue->firstused > -1 || queue->firstfree == 0);
1079 
1080  if( queue->firstused == -1 )
1081  return NULL;
1082 
1083  assert(queue->slots != NULL);
1084 
1085  pos = queue->firstused;
1086  ++(queue->firstused);
1087 
1088  /* if we removed the value at the last position we need to reset the firstused position */
1089  if( queue->firstused == queue->size )
1090  queue->firstused = 0;
1091 
1092  /* if we reached the first free position we can reset both, firstused and firstused, positions */
1093  if( queue->firstused == queue->firstfree )
1094  {
1095  queue->firstused = -1;
1096  queue->firstfree = 0; /* this is not necessary but looks better if we have an empty list to reset this value */
1097  }
1098 
1099  return (queue->slots[pos].ptr);
1100 }
1101 
1102 /** removes and returns the first unsigned integer element of the queue, or UINT_MAX if no element exists */
1103 unsigned int SCIPqueueRemoveUInt(
1104  SCIP_QUEUE* queue /**< queue */
1105  )
1106 {
1107  int pos;
1108 
1109  assert(queue != NULL);
1110  assert(queue->firstused >= -1 && queue->firstused < queue->size);
1111  assert(queue->firstfree >= 0 && queue->firstused < queue->size);
1112  assert(queue->firstused > -1 || queue->firstfree == 0);
1113 
1114  if( queue->firstused == -1 )
1115  return UINT_MAX;
1116 
1117  assert(queue->slots != NULL);
1118 
1119  pos = queue->firstused;
1120  ++(queue->firstused);
1121 
1122  /* if we removed the value at the last position we need to reset the firstused position */
1123  if( queue->firstused == queue->size )
1124  queue->firstused = 0;
1125 
1126  /* if we reached the first free position we can reset both, firstused and firstused, positions */
1127  if( queue->firstused == queue->firstfree )
1128  {
1129  queue->firstused = -1;
1130  queue->firstfree = 0; /* this is not necessary but looks better if we have an empty list to reset this value */
1131  }
1132 
1133  return (queue->slots[pos].uinteger);
1134 }
1135 
1136 /** returns the first element of the queue without removing it, or NULL if no element exists */
1138  SCIP_QUEUE* queue /**< queue */
1139  )
1140 {
1141  assert(queue != NULL);
1142  assert(queue->firstused >= -1 && queue->firstused < queue->size);
1143  assert(queue->firstfree >= 0 && queue->firstused < queue->size);
1144  assert(queue->firstused > -1 || queue->firstfree == 0);
1145 
1146  if( queue->firstused == -1 )
1147  return NULL;
1148 
1149  assert(queue->slots != NULL);
1150 
1151  return queue->slots[queue->firstused].ptr;
1152 }
1153 
1154 /** returns the first unsigned integer element of the queue without removing it, or UINT_MAX if no element exists */
1155 unsigned int SCIPqueueFirstUInt(
1156  SCIP_QUEUE* queue /**< queue */
1157  )
1158 {
1159  assert(queue != NULL);
1160  assert(queue->firstused >= -1 && queue->firstused < queue->size);
1161  assert(queue->firstfree >= 0 && queue->firstused < queue->size);
1162  assert(queue->firstused > -1 || queue->firstfree == 0);
1163 
1164  if( queue->firstused == -1 )
1165  return UINT_MAX;
1166 
1167  assert(queue->slots != NULL);
1168 
1169  return queue->slots[queue->firstused].uinteger;
1170 }
1171 
1172 /** returns whether the queue is empty */
1174  SCIP_QUEUE* queue /**< queue */
1175  )
1176 {
1177  assert(queue != NULL);
1178  assert(queue->firstused >= -1 && queue->firstused < queue->size);
1179  assert(queue->firstfree >= 0 && queue->firstused < queue->size);
1180  assert(queue->firstused > -1 || queue->firstfree == 0);
1181 
1182  return (queue->firstused == -1);
1183 }
1184 
1185 /** returns the number of elements in the queue */
1187  SCIP_QUEUE* queue /**< queue */
1188  )
1189 {
1190  assert(queue != NULL);
1191  assert(queue->firstused >= -1 && queue->firstused < queue->size);
1192  assert(queue->firstfree >= 0 && queue->firstused < queue->size);
1193  assert(queue->firstused > -1 || queue->firstfree == 0);
1194 
1195  if( queue->firstused == -1 )
1196  return 0;
1197  else if( queue->firstused < queue->firstfree )
1198  return queue->firstfree - queue->firstused;
1199  else if( queue->firstused == queue->firstfree )
1200  return queue->size;
1201  else
1202  return queue->firstfree + (queue->size - queue->firstused);
1203 }
1204 
1205 
1206 /*
1207  * Priority Queue
1208  */
1209 
1210 #define PQ_PARENT(q) (((q)+1)/2-1)
1211 #define PQ_LEFTCHILD(p) (2*(p)+1)
1212 #define PQ_RIGHTCHILD(p) (2*(p)+2)
1213 
1214 
1215 /** resizes element memory to hold at least the given number of elements */
1216 static
1218  SCIP_PQUEUE* pqueue, /**< pointer to a priority queue */
1219  int minsize /**< minimal number of storable elements */
1220  )
1221 {
1222  assert(pqueue != NULL);
1223 
1224  if( minsize <= pqueue->size )
1225  return SCIP_OKAY;
1226 
1227  pqueue->size = MAX(minsize, (int)(pqueue->size * pqueue->sizefac));
1228  SCIP_ALLOC( BMSreallocMemoryArray(&pqueue->slots, pqueue->size) );
1229 
1230  return SCIP_OKAY;
1231 }
1232 
1233 /** creates priority queue */
1235  SCIP_PQUEUE** pqueue, /**< pointer to a priority queue */
1236  int initsize, /**< initial number of available element slots */
1237  SCIP_Real sizefac, /**< memory growing factor applied, if more element slots are needed */
1238  SCIP_DECL_SORTPTRCOMP((*ptrcomp)) /**< data element comparator */
1239  )
1240 {
1241  assert(pqueue != NULL);
1242  assert(ptrcomp != NULL);
1243 
1244  initsize = MAX(1, initsize);
1245  sizefac = MAX(1.0, sizefac);
1246 
1247  SCIP_ALLOC( BMSallocMemory(pqueue) );
1248  (*pqueue)->len = 0;
1249  (*pqueue)->size = 0;
1250  (*pqueue)->sizefac = sizefac;
1251  (*pqueue)->slots = NULL;
1252  (*pqueue)->ptrcomp = ptrcomp;
1253  SCIP_CALL( pqueueResize(*pqueue, initsize) );
1254 
1255  return SCIP_OKAY;
1256 }
1257 
1258 /** frees priority queue, but not the data elements themselves */
1260  SCIP_PQUEUE** pqueue /**< pointer to a priority queue */
1261  )
1262 {
1263  assert(pqueue != NULL);
1264 
1265  BMSfreeMemoryArray(&(*pqueue)->slots);
1266  BMSfreeMemory(pqueue);
1267 }
1268 
1269 /** clears the priority queue, but doesn't free the data elements themselves */
1271  SCIP_PQUEUE* pqueue /**< priority queue */
1272  )
1273 {
1274  assert(pqueue != NULL);
1275 
1276  pqueue->len = 0;
1277 }
1278 
1279 /** inserts element into priority queue */
1281  SCIP_PQUEUE* pqueue, /**< priority queue */
1282  void* elem /**< element to be inserted */
1283  )
1284 {
1285  int pos;
1286 
1287  assert(pqueue != NULL);
1288  assert(pqueue->len >= 0);
1289  assert(elem != NULL);
1290 
1291  SCIP_CALL( pqueueResize(pqueue, pqueue->len+1) );
1292 
1293  /* insert element as leaf in the tree, move it towards the root as long it is better than its parent */
1294  pos = pqueue->len;
1295  pqueue->len++;
1296  while( pos > 0 && (*pqueue->ptrcomp)(elem, pqueue->slots[PQ_PARENT(pos)]) < 0 )
1297  {
1298  pqueue->slots[pos] = pqueue->slots[PQ_PARENT(pos)];
1299  pos = PQ_PARENT(pos);
1300  }
1301  pqueue->slots[pos] = elem;
1302 
1303  return SCIP_OKAY;
1304 }
1305 
1306 /** removes and returns best element from the priority queue */
1308  SCIP_PQUEUE* pqueue /**< priority queue */
1309  )
1310 {
1311  void* root;
1312  void* last;
1313  int pos;
1314  int childpos;
1315  int brotherpos;
1316 
1317  assert(pqueue != NULL);
1318  assert(pqueue->len >= 0);
1319 
1320  if( pqueue->len == 0 )
1321  return NULL;
1322 
1323  /* remove root element of the tree, move the better child to its parents position until the last element
1324  * of the queue could be placed in the empty slot
1325  */
1326  root = pqueue->slots[0];
1327  last = pqueue->slots[pqueue->len-1];
1328  pqueue->len--;
1329  pos = 0;
1330  while( pos <= PQ_PARENT(pqueue->len-1) )
1331  {
1332  childpos = PQ_LEFTCHILD(pos);
1333  brotherpos = PQ_RIGHTCHILD(pos);
1334  if( brotherpos <= pqueue->len && (*pqueue->ptrcomp)(pqueue->slots[brotherpos], pqueue->slots[childpos]) < 0 )
1335  childpos = brotherpos;
1336  if( (*pqueue->ptrcomp)(last, pqueue->slots[childpos]) <= 0 )
1337  break;
1338  pqueue->slots[pos] = pqueue->slots[childpos];
1339  pos = childpos;
1340  }
1341  assert(pos <= pqueue->len);
1342  pqueue->slots[pos] = last;
1343 
1344  return root;
1345 }
1346 
1347 /** returns the best element of the queue without removing it */
1349  SCIP_PQUEUE* pqueue /**< priority queue */
1350  )
1351 {
1352  assert(pqueue != NULL);
1353  assert(pqueue->len >= 0);
1354 
1355  if( pqueue->len == 0 )
1356  return NULL;
1357 
1358  return pqueue->slots[0];
1359 }
1360 
1361 /** returns the number of elements in the queue */
1363  SCIP_PQUEUE* pqueue /**< priority queue */
1364  )
1365 {
1366  assert(pqueue != NULL);
1367  assert(pqueue->len >= 0);
1368 
1369  return pqueue->len;
1370 }
1371 
1372 /** returns the elements of the queue; changing the returned array may destroy the queue's ordering! */
1374  SCIP_PQUEUE* pqueue /**< priority queue */
1375  )
1376 {
1377  assert(pqueue != NULL);
1378  assert(pqueue->len >= 0);
1379 
1380  return pqueue->slots;
1381 }
1382 
1383 
1384 
1385 
1386 /*
1387  * Hash Table
1388  */
1389 
1390 /** table of some prime numbers */
1391 static int primetable[] = {
1392  2,
1393  7,
1394  19,
1395  31,
1396  59,
1397  227,
1398  617,
1399  1523,
1400  3547,
1401  8011,
1402  17707,
1403  38723,
1404  83833,
1405  180317,
1406  385897,
1407  821411,
1408  1742369,
1409  3680893,
1410  5693959,
1411  7753849,
1412  9849703,
1413  11973277,
1414  14121853,
1415  17643961,
1416  24273817,
1417  32452843,
1418  49979687,
1419  67867967,
1420  86028121,
1421  104395301,
1422  122949823,
1423  141650939,
1424  160481183,
1425  179424673,
1426  198491317,
1427  217645177,
1428  256203161,
1429  314606869,
1430  373587883,
1431  433024223,
1432  492876847,
1433  553105243,
1434  613651349,
1435  694847533,
1436  756065159,
1437  817504243,
1438  879190747,
1439  941083981,
1440  982451653,
1441  INT_MAX
1442 };
1443 static const int primetablesize = sizeof(primetable)/sizeof(int);
1444 
1445 /** simple and fast 2-universal hash function using multiply and shift */
1446 static
1447 uint32_t hashvalue(
1448  uint64_t input /**< key value */
1449  )
1450 {
1451  return ( (uint32_t) ((UINT64_C(0x9e3779b97f4a7c15) * input)>>32) ) | 1u;
1452 }
1453 
1454 /** returns a reasonable hash table size (a prime number) that is at least as large as the specified value */
1456  int minsize /**< minimal size of the hash table */
1457  )
1458 {
1459  int pos;
1460 
1461  (void) SCIPsortedvecFindInt(primetable, minsize, primetablesize, &pos);
1462  assert(pos < primetablesize);
1463 
1464  return primetable[pos];
1465 }
1466 
1467 /** appends element to the multihash list */
1468 static
1470  SCIP_MULTIHASHLIST** multihashlist, /**< pointer to hash list */
1471  BMS_BLKMEM* blkmem, /**< block memory */
1472  void* element /**< element to append to the list */
1473  )
1474 {
1475  SCIP_MULTIHASHLIST* newlist;
1476 
1477  assert(multihashlist != NULL);
1478  assert(blkmem != NULL);
1479  assert(element != NULL);
1480 
1481  SCIP_ALLOC( BMSallocBlockMemory(blkmem, &newlist) );
1482  newlist->element = element;
1483  newlist->next = *multihashlist;
1484  *multihashlist = newlist;
1485 
1486  return SCIP_OKAY;
1487 }
1488 
1489 /** frees a multihash list entry and all its successors */
1490 static
1492  SCIP_MULTIHASHLIST** multihashlist, /**< pointer to multihash list to free */
1493  BMS_BLKMEM* blkmem /**< block memory */
1494  )
1495 {
1496  SCIP_MULTIHASHLIST* list;
1497  SCIP_MULTIHASHLIST* nextlist;
1498 
1499  assert(multihashlist != NULL);
1500  assert(blkmem != NULL);
1501 
1502  list = *multihashlist;
1503  while( list != NULL )
1504  {
1505  nextlist = list->next;
1506  BMSfreeBlockMemory(blkmem, &list);
1507  list = nextlist;
1508  }
1509 
1510  *multihashlist = NULL;
1511 }
1512 
1513 /** finds multihash list entry pointing to element with given key in the multihash list, returns NULL if not found */
1514 static
1516  SCIP_MULTIHASHLIST* multihashlist, /**< multihash list */
1517  SCIP_DECL_HASHGETKEY((*hashgetkey)), /**< gets the key of the given element */
1518  SCIP_DECL_HASHKEYEQ ((*hashkeyeq)), /**< returns TRUE iff both keys are equal */
1519  SCIP_DECL_HASHKEYVAL((*hashkeyval)), /**< returns the hash value of the key */
1520  void* userptr, /**< user pointer */
1521  uint64_t keyval, /**< hash value of key */
1522  void* key /**< key to retrieve */
1523  )
1524 {
1525  uint64_t currentkeyval;
1526  void* currentkey;
1527 
1528  assert(hashkeyeq != NULL);
1529  assert(key != NULL);
1530 
1531  while( multihashlist != NULL )
1532  {
1533  currentkey = hashgetkey(userptr, multihashlist->element);
1534  currentkeyval = hashkeyval(userptr, currentkey);
1535  if( currentkeyval == keyval && hashkeyeq(userptr, currentkey, key) )
1536  return multihashlist;
1537 
1538  multihashlist = multihashlist->next;
1539  }
1540 
1541  return NULL;
1542 }
1543 
1544 /** retrieves element with given key from the multihash list, or NULL */
1545 static
1547  SCIP_MULTIHASHLIST* multihashlist, /**< hash list */
1548  SCIP_DECL_HASHGETKEY((*hashgetkey)), /**< gets the key of the given element */
1549  SCIP_DECL_HASHKEYEQ ((*hashkeyeq)), /**< returns TRUE iff both keys are equal */
1550  SCIP_DECL_HASHKEYVAL((*hashkeyval)), /**< returns the hash value of the key */
1551  void* userptr, /**< user pointer */
1552  uint64_t keyval, /**< hash value of key */
1553  void* key /**< key to retrieve */
1554  )
1555 {
1557 
1558  /* find hash list entry */
1559  h = multihashlistFind(multihashlist, hashgetkey, hashkeyeq, hashkeyval, userptr, keyval, key);
1560 
1561  /* return element */
1562  if( h != NULL )
1563  {
1564 #ifndef NDEBUG
1565  SCIP_MULTIHASHLIST* h2;
1566 
1567  h2 = multihashlistFind(h->next, hashgetkey, hashkeyeq, hashkeyval, userptr, keyval, key);
1568 
1569  if( h2 != NULL )
1570  {
1571  void* key1;
1572  void* key2;
1573 
1574  key1 = hashgetkey(userptr, h->element);
1575  key2 = hashgetkey(userptr, h2->element);
1576  assert(hashkeyval(userptr, key1) == hashkeyval(userptr, key2));
1577 
1578  if( hashkeyeq(userptr, key1, key2) )
1579  {
1580  SCIPerrorMessage("WARNING: hashkey with same value exists multiple times (e.g. duplicate constraint/variable names), so the return value is maybe not correct\n");
1581  }
1582  }
1583 #endif
1584 
1585  return h->element;
1586  }
1587  else
1588  return NULL;
1589 }
1590 
1591 
1592 /** retrieves element with given key from the multihash list, or NULL
1593  * returns pointer to multihash table list entry
1594  */
1595 static
1597  SCIP_MULTIHASHLIST** multihashlist, /**< on input: hash list to search; on exit: hash list entry corresponding
1598  * to element after retrieved one, or NULL */
1599  SCIP_DECL_HASHGETKEY((*hashgetkey)), /**< gets the key of the given element */
1600  SCIP_DECL_HASHKEYEQ ((*hashkeyeq)), /**< returns TRUE iff both keys are equal */
1601  SCIP_DECL_HASHKEYVAL((*hashkeyval)), /**< returns the hash value of the key */
1602  void* userptr, /**< user pointer */
1603  uint64_t keyval, /**< hash value of key */
1604  void* key /**< key to retrieve */
1605  )
1606 {
1608 
1609  assert(multihashlist != NULL);
1610 
1611  /* find hash list entry */
1612  h = multihashlistFind(*multihashlist, hashgetkey, hashkeyeq, hashkeyval, userptr, keyval, key);
1613 
1614  /* return element */
1615  if( h != NULL )
1616  {
1617  *multihashlist = h->next;
1618 
1619  return h->element;
1620  }
1621 
1622  *multihashlist = NULL;
1623 
1624  return NULL;
1625 }
1626 
1627 /** removes element from the multihash list */
1628 static
1630  SCIP_MULTIHASHLIST** multihashlist, /**< pointer to hash list */
1631  BMS_BLKMEM* blkmem, /**< block memory */
1632  void* element /**< element to remove from the list */
1633  )
1634 {
1635  SCIP_MULTIHASHLIST* nextlist;
1636 
1637  assert(multihashlist != NULL);
1638  assert(blkmem != NULL);
1639  assert(element != NULL);
1640 
1641  while( *multihashlist != NULL && (*multihashlist)->element != element )
1642  multihashlist = &(*multihashlist)->next;
1643 
1644  if( *multihashlist != NULL )
1645  {
1646  nextlist = (*multihashlist)->next;
1647  BMSfreeBlockMemory(blkmem, multihashlist);
1648  *multihashlist = nextlist;
1649 
1650  return TRUE;
1651  }
1652 
1653  return FALSE;
1654 }
1655 
1656 #define SCIP_MULTIHASH_MAXSIZE 33554431 /* 2^25 - 1*/
1657 #define SCIP_MULTIHASH_RESIZE_PERCENTAGE 65
1658 #define SCIP_MULTIHASH_GROW_FACTOR 1.31
1659 
1660 /** resizing(increasing) the given multihash */
1661 static
1663  SCIP_MULTIHASH* multihash /**< hash table */
1664  )
1665 {
1666  SCIP_MULTIHASHLIST** newlists;
1667  SCIP_MULTIHASHLIST* multihashlist;
1668  SCIP_Longint nelements;
1669  int nnewlists;
1670  int l;
1671 
1672  assert(multihash != NULL);
1673  assert(multihash->lists != NULL);
1674  assert(multihash->nlists > 0);
1675  assert(multihash->hashgetkey != NULL);
1676  assert(multihash->hashkeyeq != NULL);
1677  assert(multihash->hashkeyval != NULL);
1678 
1679  /* get new memeory for hash table lists */
1680  nnewlists = (int) MIN((unsigned int)(multihash->nlists * SCIP_MULTIHASH_GROW_FACTOR), SCIP_MULTIHASH_MAXSIZE);
1681  nnewlists = MAX(nnewlists, multihash->nlists);
1682 
1683  SCIPdebugMessage("load = %g, nelements = %" SCIP_LONGINT_FORMAT ", nlists = %d, nnewlist = %d\n", SCIPmultihashGetLoad(multihash), multihash->nelements, multihash->nlists, nnewlists);
1684 
1685  if( nnewlists > multihash->nlists )
1686  {
1687  SCIP_Bool onlyone;
1688  void* key;
1689  uint64_t keyval;
1690  unsigned int hashval;
1691 
1692  SCIP_ALLOC( BMSallocClearBlockMemoryArray(multihash->blkmem, &newlists, nnewlists) );
1693 
1694  /* move all lists */
1695  for( l = multihash->nlists - 1; l >= 0; --l )
1696  {
1697  multihashlist = multihash->lists[l];
1698  onlyone = TRUE;
1699 
1700  /* move all elements frmm the old lists into the new lists */
1701  while( multihashlist != NULL )
1702  {
1703  /* get the hash key and its hash value */
1704  key = multihash->hashgetkey(multihash->userptr, multihashlist->element);
1705  keyval = multihash->hashkeyval(multihash->userptr, key);
1706  hashval = keyval % nnewlists; /*lint !e573*/
1707 
1708  /* if the old hash table list consists of only one entry, we still can use this old memory block instead
1709  * of creating a new one
1710  */
1711  if( multihashlist->next == NULL && onlyone )
1712  {
1713  /* the new list is also empty, we can directly copy the entry */
1714  if( newlists[hashval] == NULL )
1715  newlists[hashval] = multihashlist;
1716  /* the new list is not empty, so we need to find the first empty spot */
1717  else
1718  {
1719  SCIP_MULTIHASHLIST* lastnext = newlists[hashval];
1720  SCIP_MULTIHASHLIST* next = lastnext->next;
1721 
1722  while( next != NULL )
1723  {
1724  lastnext = next;
1725  next = next->next;
1726  }
1727 
1728  lastnext->next = multihashlist;
1729  }
1730 
1731  multihash->lists[l] = NULL;
1732  }
1733  else
1734  {
1735  /* append old element to the list at the hash position */
1736  SCIP_CALL( multihashlistAppend(&(newlists[hashval]), multihash->blkmem, multihashlist->element) );
1737  }
1738 
1739  onlyone = FALSE;
1740  multihashlist = multihashlist->next;
1741  }
1742  }
1743 
1744  /* remember number of elements */
1745  nelements = multihash->nelements;
1746  /* clear old lists */
1747  SCIPmultihashRemoveAll(multihash);
1748  /* free old lists */
1749  BMSfreeBlockMemoryArray(multihash->blkmem, &(multihash->lists), multihash->nlists);
1750 
1751  /* set new data */
1752  multihash->lists = newlists;
1753  multihash->nlists = nnewlists;
1754  multihash->nelements = nelements;
1755 
1756 #ifdef SCIP_MORE_DEBUG
1757  {
1758  SCIP_Longint sumslotsize = 0;
1759 
1760  for( l = 0; l < multihash->nlists; ++l )
1761  {
1762  multihashlist = multihash->lists[l];
1763  while( multihashlist != NULL )
1764  {
1765  sumslotsize++;
1766  multihashlist = multihashlist->next;
1767  }
1768  }
1769  assert(sumslotsize == multihash->nelements);
1770  }
1771 #endif
1772  }
1773 
1774  return SCIP_OKAY;
1775 }
1776 
1777 /** creates a multihash table */
1779  SCIP_MULTIHASH** multihash, /**< pointer to store the created multihash table */
1780  BMS_BLKMEM* blkmem, /**< block memory used to store multihash table entries */
1781  int tablesize, /**< size of the hash table */
1782  SCIP_DECL_HASHGETKEY((*hashgetkey)), /**< gets the key of the given element */
1783  SCIP_DECL_HASHKEYEQ ((*hashkeyeq)), /**< returns TRUE iff both keys are equal */
1784  SCIP_DECL_HASHKEYVAL((*hashkeyval)), /**< returns the hash value of the key */
1785  void* userptr /**< user pointer */
1786  )
1787 {
1788  /* only assert non negative to catch overflow errors
1789  * but not zeros due to integer divison
1790  */
1791  assert(tablesize >= 0);
1792  assert(multihash != NULL);
1793  assert(hashgetkey != NULL);
1794  assert(hashkeyeq != NULL);
1795  assert(hashkeyval != NULL);
1796 
1797  SCIP_ALLOC( BMSallocBlockMemory(blkmem, multihash) );
1798  SCIP_ALLOC( BMSallocClearBlockMemoryArray(blkmem, &(*multihash)->lists, tablesize) );
1799  (*multihash)->blkmem = blkmem;
1800  (*multihash)->nlists = tablesize;
1801  (*multihash)->hashgetkey = hashgetkey;
1802  (*multihash)->hashkeyeq = hashkeyeq;
1803  (*multihash)->hashkeyval = hashkeyval;
1804  (*multihash)->userptr = userptr;
1805  (*multihash)->nelements = 0;
1806 
1807  return SCIP_OKAY;
1808 }
1809 
1810 /** frees the multihash table */
1812  SCIP_MULTIHASH** multihash /**< pointer to the multihash table */
1813  )
1814 {
1815  int i;
1816  SCIP_MULTIHASH* table;
1817  BMS_BLKMEM* blkmem;
1818  SCIP_MULTIHASHLIST** lists;
1819 
1820  assert(multihash != NULL);
1821  assert(*multihash != NULL);
1822 
1823  table = (*multihash);
1824  blkmem = table->blkmem;
1825  lists = table->lists;
1826 
1827  /* free hash lists */
1828  for( i = table->nlists - 1; i >= 0; --i )
1829  multihashlistFree(&lists[i], blkmem);
1830 
1831  /* free main hash table data structure */
1832  BMSfreeBlockMemoryArray(blkmem, &table->lists, table->nlists);
1833  BMSfreeBlockMemory(blkmem, multihash);
1834 }
1835 
1836 
1837 /** inserts element in multihash table (multiple inserts of same element possible)
1838  *
1839  * @note A pointer to a multihashlist returned by SCIPmultihashRetrieveNext() might get invalid when adding an element
1840  * to the hash table, due to dynamic resizing.
1841  */
1843  SCIP_MULTIHASH* multihash, /**< multihash table */
1844  void* element /**< element to insert into the table */
1845  )
1846 {
1847  void* key;
1848  uint64_t keyval;
1849  unsigned int hashval;
1850 
1851  assert(multihash != NULL);
1852  assert(multihash->lists != NULL);
1853  assert(multihash->nlists > 0);
1854  assert(multihash->hashgetkey != NULL);
1855  assert(multihash->hashkeyeq != NULL);
1856  assert(multihash->hashkeyval != NULL);
1857  assert(element != NULL);
1858 
1859  /* dynamically resizing the hashtables */
1861  {
1862  SCIP_CALL( multihashResize(multihash) );
1863  }
1864 
1865  /* get the hash key and its hash value */
1866  key = multihash->hashgetkey(multihash->userptr, element);
1867  keyval = multihash->hashkeyval(multihash->userptr, key);
1868  hashval = keyval % multihash->nlists; /*lint !e573*/
1869 
1870  /* append element to the list at the hash position */
1871  SCIP_CALL( multihashlistAppend(&multihash->lists[hashval], multihash->blkmem, element) );
1872 
1873  ++(multihash->nelements);
1874 
1875  return SCIP_OKAY;
1876 }
1877 
1878 /** inserts element in multihash table (multiple insertion of same element is checked and results in an error)
1879  *
1880  * @note A pointer to a multihashlist returned by SCIPmultihashRetrieveNext() might get invalid when adding a new
1881  * element to the multihash table, due to dynamic resizing.
1882  */
1884  SCIP_MULTIHASH* multihash, /**< multihash table */
1885  void* element /**< element to insert into the table */
1886  )
1887 {
1888  assert(multihash != NULL);
1889  assert(multihash->hashgetkey != NULL);
1890 
1891  /* check, if key is already existing */
1892  if( SCIPmultihashRetrieve(multihash, multihash->hashgetkey(multihash->userptr, element)) != NULL )
1893  return SCIP_KEYALREADYEXISTING;
1894 
1895  /* insert element in hash table */
1896  SCIP_CALL( SCIPmultihashInsert(multihash, element) );
1897 
1898  return SCIP_OKAY;
1899 }
1900 
1901 /** retrieve element with key from multihash table, returns NULL if not existing */
1903  SCIP_MULTIHASH* multihash, /**< multihash table */
1904  void* key /**< key to retrieve */
1905  )
1906 {
1907  uint64_t keyval;
1908  unsigned int hashval;
1909 
1910  assert(multihash != NULL);
1911  assert(multihash->lists != NULL);
1912  assert(multihash->nlists > 0);
1913  assert(multihash->hashgetkey != NULL);
1914  assert(multihash->hashkeyeq != NULL);
1915  assert(multihash->hashkeyval != NULL);
1916  assert(key != NULL);
1917 
1918  /* get the hash value of the key */
1919  keyval = multihash->hashkeyval(multihash->userptr, key);
1920  hashval = keyval % multihash->nlists; /*lint !e573*/
1921 
1922  return multihashlistRetrieve(multihash->lists[hashval], multihash->hashgetkey, multihash->hashkeyeq,
1923  multihash->hashkeyval, multihash->userptr, keyval, key);
1924 }
1925 
1926 /** retrieve element with key from multihash table, returns NULL if not existing
1927  * can be used to retrieve all entries with the same key (one-by-one)
1928  *
1929  * @note The returned multimultihashlist pointer might get invalid when adding a new element to the multihash table.
1930  */
1932  SCIP_MULTIHASH* multihash, /**< multihash table */
1933  SCIP_MULTIHASHLIST** multihashlist, /**< input: entry in hash table list from which to start searching, or NULL
1934  * output: entry in hash table list corresponding to element after
1935  * retrieved one, or NULL */
1936  void* key /**< key to retrieve */
1937  )
1938 {
1939  uint64_t keyval;
1940 
1941  assert(multihash != NULL);
1942  assert(multihash->lists != NULL);
1943  assert(multihash->nlists > 0);
1944  assert(multihash->hashgetkey != NULL);
1945  assert(multihash->hashkeyeq != NULL);
1946  assert(multihash->hashkeyval != NULL);
1947  assert(multihashlist != NULL);
1948  assert(key != NULL);
1949 
1950  keyval = multihash->hashkeyval(multihash->userptr, key);
1951 
1952  if( *multihashlist == NULL )
1953  {
1954  unsigned int hashval;
1955 
1956  /* get the hash value of the key */
1957  hashval = keyval % multihash->nlists; /*lint !e573*/
1958 
1959  *multihashlist = multihash->lists[hashval];
1960  }
1961 
1962  return multihashlistRetrieveNext(multihashlist, multihash->hashgetkey, multihash->hashkeyeq,
1963  multihash->hashkeyval, multihash->userptr, keyval, key);
1964 }
1965 
1966 /** returns whether the given element exists in the multihash table */
1968  SCIP_MULTIHASH* multihash, /**< multihash table */
1969  void* element /**< element to search in the table */
1970  )
1971 {
1972  void* key;
1973  uint64_t keyval;
1974  unsigned int hashval;
1975 
1976  assert(multihash != NULL);
1977  assert(multihash->lists != NULL);
1978  assert(multihash->nlists > 0);
1979  assert(multihash->hashgetkey != NULL);
1980  assert(multihash->hashkeyeq != NULL);
1981  assert(multihash->hashkeyval != NULL);
1982  assert(element != NULL);
1983 
1984  /* get the hash key and its hash value */
1985  key = multihash->hashgetkey(multihash->userptr, element);
1986  keyval = multihash->hashkeyval(multihash->userptr, key);
1987  hashval = keyval % multihash->nlists; /*lint !e573*/
1988 
1989  return (multihashlistFind(multihash->lists[hashval], multihash->hashgetkey, multihash->hashkeyeq,
1990  multihash->hashkeyval, multihash->userptr, keyval, key) != NULL);
1991 }
1992 
1993 /** removes element from the multihash table, if it exists */
1995  SCIP_MULTIHASH* multihash, /**< multihash table */
1996  void* element /**< element to remove from the table */
1997  )
1998 {
1999  void* key;
2000  uint64_t keyval;
2001  unsigned int hashval;
2002 
2003  assert(multihash != NULL);
2004  assert(multihash->lists != NULL);
2005  assert(multihash->nlists > 0);
2006  assert(multihash->hashgetkey != NULL);
2007  assert(multihash->hashkeyeq != NULL);
2008  assert(multihash->hashkeyval != NULL);
2009  assert(element != NULL);
2010 
2011  /* get the hash key and its hash value */
2012  key = multihash->hashgetkey(multihash->userptr, element);
2013  keyval = multihash->hashkeyval(multihash->userptr, key);
2014  hashval = keyval % multihash->nlists; /*lint !e573*/
2015 
2016  /* remove element from the list at the hash position */
2017  if( multihashlistRemove(&multihash->lists[hashval], multihash->blkmem, element) )
2018  --(multihash->nelements);
2019 
2020  return SCIP_OKAY;
2021 }
2022 
2023 /** removes all elements of the multihash table
2024  *
2025  * @note From a performance point of view you should not fill and clear a hash table too often since the clearing can
2026  * be expensive. Clearing is done by looping over all buckets and removing the hash table lists one-by-one.
2027  */
2029  SCIP_MULTIHASH* multihash /**< multihash table */
2030  )
2031 {
2032  BMS_BLKMEM* blkmem;
2033  SCIP_MULTIHASHLIST** lists;
2034  int i;
2035 
2036  assert(multihash != NULL);
2037 
2038  blkmem = multihash->blkmem;
2039  lists = multihash->lists;
2040 
2041  /* free hash lists */
2042  for( i = multihash->nlists - 1; i >= 0; --i )
2043  multihashlistFree(&lists[i], blkmem);
2044 
2045  multihash->nelements = 0;
2046 }
2047 
2048 /** returns number of multihash table elements */
2050  SCIP_MULTIHASH* multihash /**< multihash table */
2051  )
2052 {
2053  assert(multihash != NULL);
2054 
2055  return multihash->nelements;
2056 }
2057 
2058 /** returns the load of the given multihash table in percentage */
2060  SCIP_MULTIHASH* multihash /**< multihash table */
2061  )
2062 {
2063  assert(multihash != NULL);
2064 
2065  return ((SCIP_Real)(multihash->nelements) / (multihash->nlists) * 100.0);
2066 }
2067 
2068 /** prints statistics about multihash table usage */
2070  SCIP_MULTIHASH* multihash, /**< multihash table */
2071  SCIP_MESSAGEHDLR* messagehdlr /**< message handler */
2072  )
2073 {
2074  SCIP_MULTIHASHLIST* multihashlist;
2075  int usedslots;
2076  int maxslotsize;
2077  int sumslotsize;
2078  int slotsize;
2079  int i;
2080 
2081  assert(multihash != NULL);
2082 
2083  usedslots = 0;
2084  maxslotsize = 0;
2085  sumslotsize = 0;
2086  for( i = 0; i < multihash->nlists; ++i )
2087  {
2088  multihashlist = multihash->lists[i];
2089  if( multihashlist != NULL )
2090  {
2091  usedslots++;
2092  slotsize = 0;
2093  while( multihashlist != NULL )
2094  {
2095  slotsize++;
2096  multihashlist = multihashlist->next;
2097  }
2098  maxslotsize = MAX(maxslotsize, slotsize);
2099  sumslotsize += slotsize;
2100  }
2101  }
2102  assert(sumslotsize == multihash->nelements);
2103 
2104  SCIPmessagePrintInfo(messagehdlr, "%" SCIP_LONGINT_FORMAT " multihash entries, used %d/%d slots (%.1f%%)",
2105  multihash->nelements, usedslots, multihash->nlists, 100.0*(SCIP_Real)usedslots/(SCIP_Real)(multihash->nlists));
2106  if( usedslots > 0 )
2107  SCIPmessagePrintInfo(messagehdlr, ", avg. %.1f entries/used slot, max. %d entries in slot",
2108  (SCIP_Real)(multihash->nelements)/(SCIP_Real)usedslots, maxslotsize);
2109  SCIPmessagePrintInfo(messagehdlr, "\n");
2110 }
2111 
2112 /** creates a hash table */
2114  SCIP_HASHTABLE** hashtable, /**< pointer to store the created hash table */
2115  BMS_BLKMEM* blkmem, /**< block memory used to store hash table entries */
2116  int tablesize, /**< size of the hash table */
2117  SCIP_DECL_HASHGETKEY((*hashgetkey)), /**< gets the key of the given element */
2118  SCIP_DECL_HASHKEYEQ ((*hashkeyeq)), /**< returns TRUE iff both keys are equal */
2119  SCIP_DECL_HASHKEYVAL((*hashkeyval)), /**< returns the hash value of the key */
2120  void* userptr /**< user pointer */
2121  )
2122 {
2123  unsigned int nslots;
2124 
2125  /* only assert non negative to catch overflow errors
2126  * but not zeros due to integer divison
2127  */
2128  assert(tablesize >= 0);
2129  assert(hashtable != NULL);
2130  assert(hashgetkey != NULL);
2131  assert(hashkeyeq != NULL);
2132  assert(hashkeyval != NULL);
2133  assert(blkmem != NULL);
2134 
2135  SCIP_ALLOC( BMSallocBlockMemory(blkmem, hashtable) );
2136 
2137  /* dont create too small hashtables, i.e. at least size 32, and increase
2138  * the given size by divinding it by 0.9, since then no rebuilding will
2139  * be necessary if the given number of elements are inserted. Finally round
2140  * to the next power of two.
2141  */
2142  (*hashtable)->shift = 32;
2143  (*hashtable)->shift -= (int)ceil(LOG2(MAX(32.0, tablesize / 0.9)));
2144 
2145  /* compute size from shift */
2146  nslots = 1u << (32 - (*hashtable)->shift);
2147 
2148  /* compute mask to do a fast modulo by nslots using bitwise and */
2149  (*hashtable)->mask = nslots - 1;
2150  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*hashtable)->slots, nslots) );
2151  SCIP_ALLOC( BMSallocClearBlockMemoryArray(blkmem, &(*hashtable)->hashes, nslots) );
2152  (*hashtable)->blkmem = blkmem;
2153  (*hashtable)->hashgetkey = hashgetkey;
2154  (*hashtable)->hashkeyeq = hashkeyeq;
2155  (*hashtable)->hashkeyval = hashkeyval;
2156  (*hashtable)->userptr = userptr;
2157  (*hashtable)->nelements = 0;
2158 
2159  return SCIP_OKAY;
2160 }
2161 
2162 /** frees the hash table */
2164  SCIP_HASHTABLE** hashtable /**< pointer to the hash table */
2165  )
2166 {
2167  uint32_t nslots;
2168  SCIP_HASHTABLE* table;
2169 
2170  assert(hashtable != NULL);
2171  assert(*hashtable != NULL);
2172  table = *hashtable;
2173  nslots = (*hashtable)->mask + 1;
2174 #ifdef SCIP_DEBUG
2175  {
2176  uint32_t maxprobelen = 0;
2177  uint64_t probelensum = 0;
2178  uint32_t i;
2179 
2180  assert(table != NULL);
2181 
2182  for( i = 0; i < nslots; ++i )
2183  {
2184  if( table->hashes[i] != 0 )
2185  {
2186  uint32_t probelen = ((i + table->mask + 1 - (table->hashes[i]>>(table->shift))) & table->mask) + 1;
2187  probelensum += probelen;
2188  maxprobelen = MAX(probelen, maxprobelen);
2189  }
2190  }
2191 
2192  SCIPdebugMessage("%u hash table entries, used %u/%u slots (%.1f%%)",
2193  (unsigned int)table->nelements, (unsigned int)table->nelements, (unsigned int)nslots,
2194  100.0*(SCIP_Real)table->nelements/(SCIP_Real)(nslots));
2195  if( table->nelements > 0 )
2196  SCIPdebugMessage(", avg. probe length is %.1f, max. probe length is %u",
2197  (SCIP_Real)(probelensum)/(SCIP_Real)table->nelements, (unsigned int)maxprobelen);
2198  SCIPdebugMessage("\n");
2199  }
2200 #endif
2201 
2202  /* free main hash table data structure */
2203  BMSfreeBlockMemoryArray((*hashtable)->blkmem, &table->hashes, nslots);
2204  BMSfreeBlockMemoryArray((*hashtable)->blkmem, &table->slots, nslots);
2205  BMSfreeBlockMemory((*hashtable)->blkmem, hashtable);
2206 }
2207 
2208 /** removes all elements of the hash table
2209  *
2210  * @note From a performance point of view you should not fill and clear a hash table too often since the clearing can
2211  * be expensive. Clearing is done by looping over all buckets and removing the hash table lists one-by-one.
2212  *
2213  * @deprecated Please use SCIPhashtableRemoveAll()
2214  */
2216  SCIP_HASHTABLE* hashtable /**< hash table */
2217  )
2218 {
2219  SCIPhashtableRemoveAll(hashtable);
2220 }
2221 
2222 /* computes the distance from it's desired position for the element stored at pos */
2223 #define ELEM_DISTANCE(pos) (((pos) + hashtable->mask + 1 - (hashtable->hashes[(pos)]>>(hashtable->shift))) & hashtable->mask)
2224 
2225 /** inserts element in hash table (multiple inserts of same element overrides previous one) */
2226 static
2228  SCIP_HASHTABLE* hashtable, /**< hash table */
2229  void* element, /**< element to insert into the table */
2230  void* key, /**< key of element */
2231  uint32_t hashval, /**< hash value of element */
2232  SCIP_Bool override /**< should element be overridden or an error be returned if already existing */
2233  )
2234 {
2235  uint32_t elemdistance;
2236  uint32_t pos;
2237 #ifndef NDEBUG
2238  SCIP_Bool swapped = FALSE;
2239 #endif
2240 
2241  assert(hashtable != NULL);
2242  assert(hashtable->slots != NULL);
2243  assert(hashtable->hashes != NULL);
2244  assert(hashtable->mask > 0);
2245  assert(hashtable->hashgetkey != NULL);
2246  assert(hashtable->hashkeyeq != NULL);
2247  assert(hashtable->hashkeyval != NULL);
2248  assert(element != NULL);
2249 
2250  pos = hashval>>(hashtable->shift);
2251  elemdistance = 0;
2252  while( TRUE ) /*lint !e716*/
2253  {
2254  uint32_t distance;
2255 
2256  /* if position is empty or key equal insert element */
2257  if( hashtable->hashes[pos] == 0 )
2258  {
2259  hashtable->slots[pos] = element;
2260  hashtable->hashes[pos] = hashval;
2261  ++hashtable->nelements;
2262  return SCIP_OKAY;
2263  }
2264 
2265  if( hashtable->hashes[pos] == hashval && hashtable->hashkeyeq(hashtable->userptr,
2266  hashtable->hashgetkey(hashtable->userptr, hashtable->slots[pos]), key) )
2267  {
2268  if( override )
2269  {
2270 #ifndef NDEBUG
2271  assert(! swapped);
2272 #endif
2273  hashtable->slots[pos] = element;
2274  hashtable->hashes[pos] = hashval;
2275  return SCIP_OKAY;
2276  }
2277  else
2278  {
2279  return SCIP_KEYALREADYEXISTING;
2280  }
2281  }
2282 
2283  /* otherwise check if the current element at this position is closer to its hashvalue */
2284  distance = ELEM_DISTANCE(pos);
2285  if( distance < elemdistance )
2286  {
2287  uint32_t tmp;
2288 
2289  /* if this is the case we insert the new element here and find a new position for the old one */
2290  elemdistance = distance;
2291  SCIPswapPointers(&hashtable->slots[pos], &element);
2292  tmp = hashval;
2293  hashval = hashtable->hashes[pos];
2294  hashtable->hashes[pos] = tmp;
2295  key = hashtable->hashgetkey(hashtable->userptr, element);
2296 
2297  /* after doing a swap the case that other elements are replaced must not happen anymore */
2298 #ifndef NDEBUG
2299  swapped = TRUE;
2300 #endif
2301  }
2302 
2303  /* continue until we have found an empty position */
2304  pos = (pos + 1) & hashtable->mask;
2305  ++elemdistance;
2306  }
2307 }
2308 
2309 /** check if the load factor of the hashtable is too high and rebuild if necessary */
2310 static
2312  SCIP_HASHTABLE* hashtable /**< hash table */
2313  )
2314 {
2315  assert(hashtable != NULL);
2316  assert(hashtable->shift < 32);
2317 
2318  /* use integer arithmetic to approximately check if load factor is above 90% */
2319  if( ((((uint64_t)hashtable->nelements)<<10)>>(32-hashtable->shift) > 921) )
2320  {
2321  void** slots;
2322  uint32_t* hashes;
2323  uint32_t nslots;
2324  uint32_t newnslots;
2325  uint32_t i;
2326 
2327  /* calculate new size (always power of two) */
2328  nslots = hashtable->mask + 1;
2329  newnslots = 2*nslots;
2330  hashtable->mask = newnslots-1;
2331  --hashtable->shift;
2332 
2333  /* reallocate array */
2334  SCIP_ALLOC( BMSallocBlockMemoryArray(hashtable->blkmem, &slots, newnslots) );
2335  SCIP_ALLOC( BMSallocClearBlockMemoryArray(hashtable->blkmem, &hashes, newnslots) );
2336 
2337  SCIPswapPointers((void**) &slots, (void**) &hashtable->slots);
2338  SCIPswapPointers((void**) &hashes, (void**) &hashtable->hashes);
2339  hashtable->nelements = 0;
2340 
2341  /* reinsert all elements */
2342  for( i = 0; i < nslots; ++i )
2343  {
2344  /* using SCIP_CALL_ABORT since there are no allocations or duplicates
2345  * and thus no bad return codes when inserting the elements
2346  */
2347  if( hashes[i] != 0 )
2348  {
2349  SCIP_CALL_ABORT( hashtableInsert(hashtable, slots[i], hashtable->hashgetkey(hashtable->userptr, slots[i]), hashes[i], FALSE) );
2350  }
2351  }
2352  BMSfreeBlockMemoryArray(hashtable->blkmem, &hashes, nslots);
2353  BMSfreeBlockMemoryArray(hashtable->blkmem, &slots, nslots);
2354  }
2355 
2356  return SCIP_OKAY;
2357 }
2358 
2359 
2360 /** inserts element in hash table
2361  *
2362  * @note multiple inserts of same element overrides previous one
2363  */
2365  SCIP_HASHTABLE* hashtable, /**< hash table */
2366  void* element /**< element to insert into the table */
2367  )
2368 {
2369  void* key;
2370  uint64_t keyval;
2371  uint32_t hashval;
2372 
2373  assert(hashtable != NULL);
2374  assert(hashtable->slots != NULL);
2375  assert(hashtable->hashes != NULL);
2376  assert(hashtable->mask > 0);
2377  assert(hashtable->hashgetkey != NULL);
2378  assert(hashtable->hashkeyeq != NULL);
2379  assert(hashtable->hashkeyval != NULL);
2380  assert(element != NULL);
2381 
2382  SCIP_CALL( hashtableCheckLoad(hashtable) );
2383 
2384  /* get the hash key and its hash value */
2385  key = hashtable->hashgetkey(hashtable->userptr, element);
2386  keyval = hashtable->hashkeyval(hashtable->userptr, key);
2387  hashval = hashvalue(keyval);
2388 
2389  return hashtableInsert(hashtable, element, key, hashval, TRUE);
2390 }
2391 
2392 /** inserts element in hash table
2393  *
2394  * @note multiple insertion of same element is checked and results in an error
2395  */
2397  SCIP_HASHTABLE* hashtable, /**< hash table */
2398  void* element /**< element to insert into the table */
2399  )
2400 {
2401  void* key;
2402  uint64_t keyval;
2403  uint32_t hashval;
2404 
2405  assert(hashtable != NULL);
2406  assert(hashtable->slots != NULL);
2407  assert(hashtable->hashes != NULL);
2408  assert(hashtable->mask > 0);
2409  assert(hashtable->hashgetkey != NULL);
2410  assert(hashtable->hashkeyeq != NULL);
2411  assert(hashtable->hashkeyval != NULL);
2412  assert(element != NULL);
2413 
2414  SCIP_CALL( hashtableCheckLoad(hashtable) );
2415 
2416  /* get the hash key and its hash value */
2417  key = hashtable->hashgetkey(hashtable->userptr, element);
2418  keyval = hashtable->hashkeyval(hashtable->userptr, key);
2419  hashval = hashvalue(keyval);
2420 
2421  return hashtableInsert(hashtable, element, key, hashval, FALSE);
2422 }
2423 
2424 /** retrieve element with key from hash table, returns NULL if not existing */
2426  SCIP_HASHTABLE* hashtable, /**< hash table */
2427  void* key /**< key to retrieve */
2428  )
2429 {
2430  uint64_t keyval;
2431  uint32_t hashval;
2432  uint32_t pos;
2433  uint32_t elemdistance;
2434 
2435  assert(hashtable != NULL);
2436  assert(hashtable->slots != NULL);
2437  assert(hashtable->hashes != NULL);
2438  assert(hashtable->mask > 0);
2439  assert(hashtable->hashgetkey != NULL);
2440  assert(hashtable->hashkeyeq != NULL);
2441  assert(hashtable->hashkeyval != NULL);
2442  assert(key != NULL);
2443 
2444  /* get the hash value of the key */
2445  keyval = hashtable->hashkeyval(hashtable->userptr, key);
2446  hashval = hashvalue(keyval);
2447 
2448  pos = hashval>>(hashtable->shift);
2449  elemdistance = 0;
2450 
2451  while( TRUE ) /*lint !e716*/
2452  {
2453  uint32_t distance;
2454 
2455  /* slots is empty so element cannot be contained */
2456  if( hashtable->hashes[pos] == 0 )
2457  return NULL;
2458 
2459  distance = ELEM_DISTANCE(pos);
2460 
2461  /* element cannot be contained since otherwise we would have swapped it with this one during insert */
2462  if( elemdistance > distance )
2463  return NULL;
2464 
2465  /* found element */
2466  if( hashtable->hashes[pos] == hashval && hashtable->hashkeyeq(hashtable->userptr,
2467  hashtable->hashgetkey(hashtable->userptr, hashtable->slots[pos]), key) )
2468  return hashtable->slots[pos];
2469 
2470  pos = (pos + 1) & hashtable->mask;
2471  ++elemdistance;
2472  }
2473 }
2474 
2475 /** returns whether the given element exists in the table */
2477  SCIP_HASHTABLE* hashtable, /**< hash table */
2478  void* element /**< element to search in the table */
2479  )
2480 {
2481  assert(hashtable != NULL);
2482  assert(hashtable->slots != NULL);
2483  assert(hashtable->hashes != NULL);
2484  assert(hashtable->mask > 0);
2485  assert(hashtable->hashgetkey != NULL);
2486  assert(hashtable->hashkeyeq != NULL);
2487  assert(hashtable->hashkeyval != NULL);
2488  assert(element != NULL);
2489 
2490  return (SCIPhashtableRetrieve(hashtable, hashtable->hashgetkey(hashtable->userptr, element)) != NULL);
2491 }
2492 
2493 /** removes element from the hash table, if it exists */
2495  SCIP_HASHTABLE* hashtable, /**< hash table */
2496  void* element /**< element to remove from the table */
2497  )
2498 {
2499  void* key;
2500  uint64_t keyval;
2501  uint32_t hashval;
2502  uint32_t elemdistance;
2503  uint32_t distance;
2504  uint32_t pos;
2505 
2506  assert(hashtable != NULL);
2507  assert(hashtable->slots != NULL);
2508  assert(hashtable->hashes != NULL);
2509  assert(hashtable->mask > 0);
2510  assert(hashtable->hashgetkey != NULL);
2511  assert(hashtable->hashkeyeq != NULL);
2512  assert(hashtable->hashkeyval != NULL);
2513  assert(element != NULL);
2514 
2515  /* get the hash key and its hash value */
2516  key = hashtable->hashgetkey(hashtable->userptr, element);
2517  keyval = hashtable->hashkeyval(hashtable->userptr, key);
2518  hashval = hashvalue(keyval);
2519 
2520  elemdistance = 0;
2521  pos = hashval>>(hashtable->shift);
2522  while( TRUE ) /*lint !e716*/
2523  {
2524  /* slots empty so element not contained */
2525  if( hashtable->hashes[pos] == 0 )
2526  return SCIP_OKAY;
2527 
2528  distance = ELEM_DISTANCE(pos);
2529 
2530  /* element can not be contained since otherwise we would have swapped it with this one */
2531  if( elemdistance > distance )
2532  return SCIP_OKAY;
2533 
2534  if( hashtable->hashes[pos] == hashval && hashtable->hashkeyeq(hashtable->userptr,
2535  hashtable->hashgetkey(hashtable->userptr, hashtable->slots[pos]), key) )
2536  {
2537  /* element exists at pos so break out of loop */
2538  break;
2539  }
2540 
2541  pos = (pos + 1) & hashtable->mask;
2542  ++elemdistance;
2543  }
2544 
2545  /* remove element */
2546  hashtable->hashes[pos] = 0;
2547  --hashtable->nelements;
2548  while( TRUE ) /*lint !e716*/
2549  {
2550  uint32_t nextpos = (pos + 1) & hashtable->mask;
2551 
2552  /* nothing to do since there is no chain that needs to be moved */
2553  if( hashtable->hashes[nextpos] == 0 )
2554  break;
2555 
2556  /* check if the element is the start of a new chain and return if that is the case */
2557  if( (hashtable->hashes[nextpos]>>(hashtable->shift)) == nextpos )
2558  break;
2559 
2560  /* element should be moved to the left and next element needs to be checked */
2561  hashtable->slots[pos] = hashtable->slots[nextpos];
2562  hashtable->hashes[pos] = hashtable->hashes[nextpos];
2563  hashtable->hashes[nextpos] = 0;
2564 
2565  pos = nextpos;
2566  }
2567 
2568  return SCIP_OKAY;
2569 }
2570 
2571 /** removes all elements of the hash table */
2573  SCIP_HASHTABLE* hashtable /**< hash table */
2574  )
2575 {
2576  assert(hashtable != NULL);
2577 
2578  BMSclearMemoryArray(hashtable->hashes, hashtable->mask + 1);
2579 
2580  hashtable->nelements = 0;
2581 }
2582 
2583 /** returns number of hash table elements */
2585  SCIP_HASHTABLE* hashtable /**< hash table */
2586  )
2587 {
2588  assert(hashtable != NULL);
2589 
2590  return hashtable->nelements;
2591 }
2592 
2593 /** gives the number of entries in the internal arrays of a hash table */
2595  SCIP_HASHTABLE* hashtable /**< hash table */
2596  )
2597 {
2598  return (int) hashtable->mask + 1;
2599 }
2600 
2601 /** gives the element at the given index or NULL if entry at that index has no element */
2603  SCIP_HASHTABLE* hashtable, /**< hash table */
2604  int entryidx /**< index of hash table entry */
2605  )
2606 {
2607  return hashtable->hashes[entryidx] == 0 ? NULL : hashtable->slots[entryidx];
2608 }
2609 
2610 /** returns the load of the given hash table in percentage */
2612  SCIP_HASHTABLE* hashtable /**< hash table */
2613  )
2614 {
2615  assert(hashtable != NULL);
2616 
2617  return ((SCIP_Real)(hashtable->nelements) / (hashtable->mask + 1) * 100.0);
2618 }
2619 
2620 /** prints statistics about hash table usage */
2622  SCIP_HASHTABLE* hashtable, /**< hash table */
2623  SCIP_MESSAGEHDLR* messagehdlr /**< message handler */
2624  )
2625 {
2626  uint32_t maxprobelen = 0;
2627  uint64_t probelensum = 0;
2628  uint32_t nslots;
2629  uint32_t i;
2630 
2631  assert(hashtable != NULL);
2632 
2633  nslots = hashtable->mask + 1;
2634 
2635  /* compute the maximum and average probe length */
2636  for( i = 0; i < nslots; ++i )
2637  {
2638  if( hashtable->hashes[i] != 0 )
2639  {
2640  uint32_t probelen = ELEM_DISTANCE(i) + 1;
2641  probelensum += probelen;
2642  maxprobelen = MAX(probelen, maxprobelen);
2643  }
2644  }
2645 
2646  /* print general hash table statistics */
2647  SCIPmessagePrintInfo(messagehdlr, "%u hash entries, used %u/%u slots (%.1f%%)",
2648  (unsigned int)hashtable->nelements, (unsigned int)hashtable->nelements,
2649  (unsigned int)nslots, 100.0*(SCIP_Real)hashtable->nelements/(SCIP_Real)(nslots));
2650 
2651  /* if not empty print average and maximum probe length */
2652  if( hashtable->nelements > 0 )
2653  SCIPmessagePrintInfo(messagehdlr, ", avg. probe length is %.1f, max. probe length is %u",
2654  (SCIP_Real)(probelensum)/(SCIP_Real)hashtable->nelements, (unsigned int)maxprobelen);
2655  SCIPmessagePrintInfo(messagehdlr, "\n");
2656 }
2657 
2658 /** returns TRUE iff both keys (i.e. strings) are equal */
2659 SCIP_DECL_HASHKEYEQ(SCIPhashKeyEqString)
2660 { /*lint --e{715}*/
2661  const char* string1 = (const char*)key1;
2662  const char* string2 = (const char*)key2;
2663 
2664  return (strcmp(string1, string2) == 0);
2665 }
2666 
2667 /** returns the hash value of the key (i.e. string) */
2668 SCIP_DECL_HASHKEYVAL(SCIPhashKeyValString)
2669 { /*lint --e{715}*/
2670  const char* str;
2671  uint64_t hash;
2672 
2673  str = (const char*)key;
2674  hash = 37;
2675  while( *str != '\0' )
2676  {
2677  hash *= 11;
2678  hash += (unsigned int)(*str); /*lint !e571*/
2679  str++;
2680  }
2681 
2682  return hash;
2683 }
2684 
2685 
2686 /** gets the element as the key */
2687 SCIP_DECL_HASHGETKEY(SCIPhashGetKeyStandard)
2688 { /*lint --e{715}*/
2689  /* the key is the element itself */
2690  return elem;
2691 }
2692 
2693 /** returns TRUE iff both keys(pointer) are equal */
2694 SCIP_DECL_HASHKEYEQ(SCIPhashKeyEqPtr)
2695 { /*lint --e{715}*/
2696  return (key1 == key2);
2697 }
2698 
2699 /** returns the hash value of the key */
2700 SCIP_DECL_HASHKEYVAL(SCIPhashKeyValPtr)
2701 { /*lint --e{715}*/
2702  /* the key is used as the keyvalue too */
2703  return (uint64_t) (uintptr_t) key;
2704 }
2705 
2706 
2707 
2708 /*
2709  * Hash Map
2710  */
2711 
2712 /* redefine ELEM_DISTANCE macro for hashmap */
2713 #undef ELEM_DISTANCE
2714 /* computes the distance from it's desired position for the element stored at pos */
2715 #define ELEM_DISTANCE(pos) (((pos) + hashmap->mask + 1 - (hashmap->hashes[(pos)]>>(hashmap->shift))) & hashmap->mask)
2716 
2717 /** inserts element in hash table */
2718 static
2720  SCIP_HASHMAP* hashmap, /**< hash map */
2721  void* origin, /**< element to insert into the table */
2722  SCIP_HASHMAPIMAGE image, /**< key of element */
2723  uint32_t hashval, /**< hash value of element */
2724  SCIP_Bool override /**< should element be overridden or error be returned if already existing */
2725  )
2726 {
2727  uint32_t elemdistance;
2728  uint32_t pos;
2729 
2730  assert(hashmap != NULL);
2731  assert(hashmap->slots != NULL);
2732  assert(hashmap->hashes != NULL);
2733  assert(hashmap->mask > 0);
2734  assert(hashval != 0);
2735 
2736  pos = hashval>>(hashmap->shift);
2737  elemdistance = 0;
2738  while( TRUE ) /*lint !e716*/
2739  {
2740  uint32_t distance;
2741 
2742  /* if position is empty or key equal insert element */
2743  if( hashmap->hashes[pos] == 0 )
2744  {
2745  hashmap->slots[pos].origin = origin;
2746  hashmap->slots[pos].image = image;
2747  hashmap->hashes[pos] = hashval;
2748  ++hashmap->nelements;
2749  return SCIP_OKAY;
2750  }
2751 
2752  if( hashval == hashmap->hashes[pos] && origin == hashmap->slots[pos].origin )
2753  {
2754  if( override )
2755  {
2756  hashmap->slots[pos].origin = origin;
2757  hashmap->slots[pos].image = image;
2758  hashmap->hashes[pos] = hashval;
2759  return SCIP_OKAY;
2760  }
2761  else
2762  {
2763  return SCIP_KEYALREADYEXISTING;
2764  }
2765  }
2766 
2767  /* otherwise check if the current element at this position is closer to its hashvalue */
2768  distance = ELEM_DISTANCE(pos);
2769  if( distance < elemdistance )
2770  {
2771  SCIP_HASHMAPIMAGE tmp;
2772  uint32_t tmphash;
2773 
2774  /* if this is the case we insert the new element here and find a new position for the old one */
2775  elemdistance = distance;
2776  tmphash = hashval;
2777  hashval = hashmap->hashes[pos];
2778  hashmap->hashes[pos] = tmphash;
2779  SCIPswapPointers(&hashmap->slots[pos].origin, &origin);
2780  tmp = image;
2781  image = hashmap->slots[pos].image;
2782  hashmap->slots[pos].image = tmp;
2783  }
2784 
2785  /* continue until we have found an empty position */
2786  pos = (pos + 1) & hashmap->mask;
2787  ++elemdistance;
2788  }
2789 }
2790 
2791 /** lookup origin in the hashmap. If element is found returns true and the position of the element,
2792  * otherwise returns FALSE.
2793  */
2794 static
2796  SCIP_HASHMAP* hashmap, /**< hash table */
2797  void* origin, /**< origin to lookup */
2798  uint32_t* pos /**< pointer to store position of element, if exists */
2799  )
2800 {
2801  uint32_t hashval;
2802  uint32_t elemdistance;
2803 
2804  assert(hashmap != NULL);
2805  assert(hashmap->slots != NULL);
2806  assert(hashmap->hashes != NULL);
2807  assert(hashmap->mask > 0);
2808 
2809  /* get the hash value */
2810  hashval = hashvalue((size_t)origin);
2811  assert(hashval != 0);
2812 
2813  *pos = hashval>>(hashmap->shift);
2814  elemdistance = 0;
2815 
2816  while( TRUE ) /*lint !e716*/
2817  {
2818  uint32_t distance;
2819 
2820  /* slots is empty so element cannot be contained */
2821  if( hashmap->hashes[*pos] == 0 )
2822  return FALSE;
2823 
2824  distance = ELEM_DISTANCE(*pos);
2825  /* element can not be contained since otherwise we would have swapped it with this one during insert */
2826  if( elemdistance > distance )
2827  return FALSE;
2828 
2829  /* found element */
2830  if( hashmap->hashes[*pos] == hashval && hashmap->slots[*pos].origin == origin )
2831  return TRUE;
2832 
2833  *pos = (*pos + 1) & hashmap->mask;
2834  ++elemdistance;
2835  }
2836 }
2837 
2838 /** check if the load factor of the hashmap is too high and rebuild if necessary */
2839 static
2841  SCIP_HASHMAP* hashmap /**< hash table */
2842  )
2843 {
2844  assert(hashmap != NULL);
2845  assert(hashmap->shift < 32);
2846 
2847  /* use integer arithmetic to approximately check if load factor is above 90% */
2848  if( ((((uint64_t)hashmap->nelements)<<10)>>(32-hashmap->shift) > 921) )
2849  {
2850  SCIP_HASHMAPENTRY* slots;
2851  uint32_t* hashes;
2852  uint32_t nslots;
2853  uint32_t newnslots;
2854  uint32_t i;
2855 
2856  /* calculate new size (always power of two) */
2857  nslots = hashmap->mask + 1;
2858  --hashmap->shift;
2859  newnslots = 2*nslots;
2860  hashmap->mask = newnslots-1;
2861 
2862  /* reallocate array */
2863  SCIP_ALLOC( BMSallocBlockMemoryArray(hashmap->blkmem, &slots, newnslots) );
2864  SCIP_ALLOC( BMSallocClearBlockMemoryArray(hashmap->blkmem, &hashes, newnslots) );
2865 
2866  SCIPswapPointers((void**) &slots, (void**) &hashmap->slots);
2867  SCIPswapPointers((void**) &hashes, (void**) &hashmap->hashes);
2868  hashmap->nelements = 0;
2869 
2870  /* reinsert all elements */
2871  for( i = 0; i < nslots; ++i )
2872  {
2873  /* using SCIP_CALL_ABORT since there are no allocations or duplicates
2874  * and thus no bad return codes when inserting the elements
2875  */
2876  if( hashes[i] != 0 )
2877  {
2878  SCIP_CALL_ABORT( hashmapInsert(hashmap, slots[i].origin, slots[i].image, hashes[i], FALSE) );
2879  }
2880  }
2881 
2882  /* free old arrays */
2883  BMSfreeBlockMemoryArray(hashmap->blkmem, &hashes, nslots);
2884  BMSfreeBlockMemoryArray(hashmap->blkmem, &slots, nslots);
2885  }
2886 
2887  return SCIP_OKAY;
2888 }
2889 
2890 /** creates a hash map mapping pointers to pointers */
2892  SCIP_HASHMAP** hashmap, /**< pointer to store the created hash map */
2893  BMS_BLKMEM* blkmem, /**< block memory used to store hash map entries */
2894  int mapsize /**< size of the hash map */
2895  )
2896 {
2897  uint32_t nslots;
2898 
2899  assert(hashmap != NULL);
2900  assert(mapsize >= 0);
2901  assert(blkmem != NULL);
2902 
2903  SCIP_ALLOC( BMSallocBlockMemory(blkmem, hashmap) );
2904 
2905  /* dont create too small hashtables, i.e. at least size 32, and increase
2906  * the given size by divinding it by 0.9, since then no rebuilding will
2907  * be necessary if the given number of elements are inserted. Finally round
2908  * to the next power of two.
2909  */
2910  (*hashmap)->shift = 32;
2911  (*hashmap)->shift -= (int)ceil(log(MAX(32, mapsize / 0.9)) / log(2.0));
2912  nslots = 1u << (32 - (*hashmap)->shift);
2913  (*hashmap)->mask = nslots - 1;
2914  (*hashmap)->blkmem = blkmem;
2915  (*hashmap)->nelements = 0;
2916  (*hashmap)->hashmaptype = SCIP_HASHMAPTYPE_UNKNOWN;
2917 
2918  SCIP_ALLOC( BMSallocBlockMemoryArray((*hashmap)->blkmem, &(*hashmap)->slots, nslots) );
2919  SCIP_ALLOC( BMSallocClearBlockMemoryArray((*hashmap)->blkmem, &(*hashmap)->hashes, nslots) );
2920 
2921  return SCIP_OKAY;
2922 }
2923 
2924 /** frees the hash map */
2926  SCIP_HASHMAP** hashmap /**< pointer to the hash map */
2927  )
2928 {
2929  uint32_t nslots;
2930 
2931  assert(hashmap != NULL);
2932  assert(*hashmap != NULL);
2933 
2934  nslots = (*hashmap)->mask + 1;
2935 #ifdef SCIP_DEBUG
2936  {
2937  uint32_t maxprobelen = 0;
2938  uint64_t probelensum = 0;
2939  uint32_t i;
2940 
2941  assert(hashmap != NULL);
2942 
2943  for( i = 0; i < nslots; ++i )
2944  {
2945  if( (*hashmap)->hashes[i] != 0 )
2946  {
2947  uint32_t probelen = ((i + (*hashmap)->mask + 1 - ((*hashmap)->hashes[i]>>((*hashmap)->shift))) & (*hashmap)->mask) + 1;
2948  probelensum += probelen;
2949  maxprobelen = MAX(probelen, maxprobelen);
2950  }
2951  }
2952 
2953  SCIPdebugMessage("%u hash map entries, used %u/%u slots (%.1f%%)",
2954  (unsigned int)(*hashmap)->nelements, (unsigned int)(*hashmap)->nelements, (unsigned int)nslots,
2955  100.0*(SCIP_Real)(*hashmap)->nelements/(SCIP_Real)(nslots));
2956  if( (*hashmap)->nelements > 0 )
2957  SCIPdebugMessage(", avg. probe length is %.1f, max. probe length is %u",
2958  (SCIP_Real)(probelensum)/(SCIP_Real)(*hashmap)->nelements, (unsigned int)maxprobelen);
2959  SCIPdebugMessage("\n");
2960  }
2961 #endif
2962 
2963  /* free main hash map data structure */
2964  BMSfreeBlockMemoryArray((*hashmap)->blkmem, &(*hashmap)->hashes, nslots);
2965  BMSfreeBlockMemoryArray((*hashmap)->blkmem, &(*hashmap)->slots, nslots);
2966  BMSfreeBlockMemory((*hashmap)->blkmem, hashmap);
2967 }
2968 
2969 /** inserts new origin->image pair in hash map
2970  *
2971  * @note multiple insertion of same element is checked and results in an error
2972  */
2974  SCIP_HASHMAP* hashmap, /**< hash map */
2975  void* origin, /**< origin to set image for */
2976  void* image /**< new image for origin */
2977  )
2978 {
2979  uint32_t hashval;
2980  SCIP_HASHMAPIMAGE img;
2981 
2982  assert(hashmap != NULL);
2983  assert(hashmap->slots != NULL);
2984  assert(hashmap->hashes != NULL);
2985  assert(hashmap->mask > 0);
2986  assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_POINTER);
2987 
2988 #ifndef NDEBUG
2989  if( hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN )
2991 #endif
2992 
2993  SCIP_CALL( hashmapCheckLoad(hashmap) );
2994 
2995  /* get the hash value */
2996  hashval = hashvalue((size_t)origin);
2997 
2998  /* append origin->image pair to hash map */
2999  img.ptr = image;
3000  SCIP_CALL( hashmapInsert(hashmap, origin, img, hashval, FALSE) );
3001 
3002  return SCIP_OKAY;
3003 }
3004 
3005 /** inserts new origin->image pair in hash map
3006  *
3007  * @note multiple insertion of same element is checked and results in an error
3008  */
3010  SCIP_HASHMAP* hashmap, /**< hash map */
3011  void* origin, /**< origin to set image for */
3012  int image /**< new image for origin */
3013  )
3014 {
3015  uint32_t hashval;
3016  SCIP_HASHMAPIMAGE img;
3017 
3018  assert(hashmap != NULL);
3019  assert(hashmap->slots != NULL);
3020  assert(hashmap->hashes != NULL);
3021  assert(hashmap->mask > 0);
3022  assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_INT);
3023 
3024 #ifndef NDEBUG
3025  if( hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN )
3026  hashmap->hashmaptype = SCIP_HASHMAPTYPE_INT;
3027 #endif
3028 
3029  SCIP_CALL( hashmapCheckLoad(hashmap) );
3030 
3031  /* get the hash value */
3032  hashval = hashvalue((size_t)origin);
3033 
3034  /* append origin->image pair to hash map */
3035  img.integer = image;
3036  SCIP_CALL( hashmapInsert(hashmap, origin, img, hashval, FALSE) );
3037 
3038  return SCIP_OKAY;
3039 }
3040 
3041 /** inserts new origin->image pair in hash map
3042  *
3043  * @note multiple insertion of same element is checked and results in an error
3044  */
3046  SCIP_HASHMAP* hashmap, /**< hash map */
3047  void* origin, /**< origin to set image for */
3048  SCIP_Real image /**< new image for origin */
3049  )
3050 {
3051  uint32_t hashval;
3052  SCIP_HASHMAPIMAGE img;
3053 
3054  assert(hashmap != NULL);
3055  assert(hashmap->slots != NULL);
3056  assert(hashmap->hashes != NULL);
3057  assert(hashmap->mask > 0);
3058  assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_REAL);
3059 
3060 #ifndef NDEBUG
3061  if( hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN )
3063 #endif
3064 
3065  SCIP_CALL( hashmapCheckLoad(hashmap) );
3066 
3067  /* get the hash value */
3068  hashval = hashvalue((size_t)origin);
3069 
3070  /* append origin->image pair to hash map */
3071  img.real = image;
3072  SCIP_CALL( hashmapInsert(hashmap, origin, img, hashval, FALSE) );
3073 
3074  return SCIP_OKAY;
3075 }
3076 
3077 /** retrieves image of given origin from the hash map, or NULL if no image exists */
3079  SCIP_HASHMAP* hashmap, /**< hash map */
3080  void* origin /**< origin to retrieve image for */
3081  )
3082 {
3083  uint32_t pos;
3084 
3085  assert(hashmap != NULL);
3086  assert(hashmap->slots != NULL);
3087  assert(hashmap->hashes != NULL);
3088  assert(hashmap->mask > 0);
3089  assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_POINTER);
3090 
3091  if( hashmapLookup(hashmap, origin, &pos) )
3092  return hashmap->slots[pos].image.ptr;
3093 
3094  return NULL;
3095 }
3096 
3097 /** retrieves image of given origin from the hash map, or INT_MAX if no image exists */
3099  SCIP_HASHMAP* hashmap, /**< hash map */
3100  void* origin /**< origin to retrieve image for */
3101  )
3102 {
3103  uint32_t pos;
3104 
3105  assert(hashmap != NULL);
3106  assert(hashmap->slots != NULL);
3107  assert(hashmap->hashes != NULL);
3108  assert(hashmap->mask > 0);
3109  assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_INT);
3110 
3111  if( hashmapLookup(hashmap, origin, &pos) )
3112  return hashmap->slots[pos].image.integer;
3113 
3114  return INT_MAX;
3115 }
3116 
3117 /** retrieves image of given origin from the hash map, or SCIP_INVALID if no image exists */
3119  SCIP_HASHMAP* hashmap, /**< hash map */
3120  void* origin /**< origin to retrieve image for */
3121  )
3122 {
3123  uint32_t pos;
3124 
3125  assert(hashmap != NULL);
3126  assert(hashmap->slots != NULL);
3127  assert(hashmap->hashes != NULL);
3128  assert(hashmap->mask > 0);
3129  assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_REAL);
3130 
3131  if( hashmapLookup(hashmap, origin, &pos) )
3132  return hashmap->slots[pos].image.real;
3133 
3134  return SCIP_INVALID;
3135 }
3136 
3137 /** sets image for given origin in the hash map, either by modifying existing origin->image pair
3138  * or by appending a new origin->image pair
3139  */
3141  SCIP_HASHMAP* hashmap, /**< hash map */
3142  void* origin, /**< origin to set image for */
3143  void* image /**< new image for origin */
3144  )
3145 {
3146  uint32_t hashval;
3147  SCIP_HASHMAPIMAGE img;
3148 
3149  assert(hashmap != NULL);
3150  assert(hashmap->slots != NULL);
3151  assert(hashmap->mask > 0);
3152  assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_POINTER);
3153 
3154 #ifndef NDEBUG
3155  if( hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN )
3157 #endif
3158 
3159  SCIP_CALL( hashmapCheckLoad(hashmap) );
3160 
3161  /* get the hash value */
3162  hashval = hashvalue((size_t)origin);
3163 
3164  /* append origin->image pair to hash map */
3165  img.ptr = image;
3166  SCIP_CALL( hashmapInsert(hashmap, origin, img, hashval, TRUE) );
3167 
3168  return SCIP_OKAY;
3169 }
3170 
3171 /** sets image for given origin in the hash map, either by modifying existing origin->image pair
3172  * or by appending a new origin->image pair
3173  */
3175  SCIP_HASHMAP* hashmap, /**< hash map */
3176  void* origin, /**< origin to set image for */
3177  int image /**< new image for origin */
3178  )
3179 {
3180  uint32_t hashval;
3181  SCIP_HASHMAPIMAGE img;
3182 
3183  assert(hashmap != NULL);
3184  assert(hashmap->slots != NULL);
3185  assert(hashmap->mask > 0);
3186  assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_INT);
3187 
3188 #ifndef NDEBUG
3189  if( hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN )
3190  hashmap->hashmaptype = SCIP_HASHMAPTYPE_INT;
3191 #endif
3192 
3193  SCIP_CALL( hashmapCheckLoad(hashmap) );
3194 
3195  /* get the hash value */
3196  hashval = hashvalue((size_t)origin);
3197 
3198  /* append origin->image pair to hash map */
3199  img.integer = image;
3200  SCIP_CALL( hashmapInsert(hashmap, origin, img, hashval, TRUE) );
3201 
3202  return SCIP_OKAY;
3203 }
3204 
3205 /** sets image for given origin in the hash map, either by modifying existing origin->image pair
3206  * or by appending a new origin->image pair
3207  */
3209  SCIP_HASHMAP* hashmap, /**< hash map */
3210  void* origin, /**< origin to set image for */
3211  SCIP_Real image /**< new image for origin */
3212  )
3213 {
3214  uint32_t hashval;
3215  SCIP_HASHMAPIMAGE img;
3216 
3217  assert(hashmap != NULL);
3218  assert(hashmap->slots != NULL);
3219  assert(hashmap->mask > 0);
3220  assert(hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN || hashmap->hashmaptype == SCIP_HASHMAPTYPE_REAL);
3221 
3222 #ifndef NDEBUG
3223  if( hashmap->hashmaptype == SCIP_HASHMAPTYPE_UNKNOWN )
3225 #endif
3226 
3227  SCIP_CALL( hashmapCheckLoad(hashmap) );
3228 
3229  /* get the hash value */
3230  hashval = hashvalue((size_t)origin);
3231 
3232  /* append origin->image pair to hash map */
3233  img.real = image;
3234  SCIP_CALL( hashmapInsert(hashmap, origin, img, hashval, TRUE) );
3235 
3236  return SCIP_OKAY;
3237 }
3238 
3239 /** checks whether an image to the given origin exists in the hash map */
3241  SCIP_HASHMAP* hashmap, /**< hash map */
3242  void* origin /**< origin to search for */
3243  )
3244 {
3245  uint32_t pos;
3246 
3247  assert(hashmap != NULL);
3248  assert(hashmap->slots != NULL);
3249  assert(hashmap->hashes != NULL);
3250  assert(hashmap->mask > 0);
3251 
3252  return hashmapLookup(hashmap, origin, &pos);
3253 }
3254 
3255 /** removes origin->image pair from the hash map, if it exists */
3257  SCIP_HASHMAP* hashmap, /**< hash map */
3258  void* origin /**< origin to remove from the list */
3259  )
3260 {
3261  uint32_t pos;
3262 
3263  assert(hashmap != NULL);
3264  assert(hashmap->slots != NULL);
3265  assert(hashmap->mask > 0);
3266 
3267  assert(origin != NULL);
3268 
3269  if( hashmapLookup(hashmap, origin, &pos) )
3270  {
3271  /* remove element */
3272  hashmap->hashes[pos] = 0;
3273  --hashmap->nelements;
3274 
3275  /* move other elements if necessary */
3276  while( TRUE ) /*lint !e716*/
3277  {
3278  uint32_t nextpos = (pos + 1) & hashmap->mask;
3279 
3280  /* nothing to do since there is no chain that needs to be moved */
3281  if( hashmap->hashes[nextpos] == 0 )
3282  return SCIP_OKAY;
3283 
3284  /* check if the element is the start of a new chain and return if that is the case */
3285  if( (hashmap->hashes[nextpos]>>(hashmap->shift)) == nextpos )
3286  return SCIP_OKAY;
3287 
3288  /* element should be moved to the left and next element needs to be checked */
3289  hashmap->slots[pos].origin = hashmap->slots[nextpos].origin;
3290  hashmap->slots[pos].image = hashmap->slots[nextpos].image;
3291  hashmap->hashes[pos] = hashmap->hashes[nextpos];
3292  hashmap->hashes[nextpos] = 0;
3293 
3294  pos = nextpos;
3295  }
3296  }
3297 
3298  return SCIP_OKAY;
3299 }
3300 
3301 /** prints statistics about hash map usage */
3303  SCIP_HASHMAP* hashmap, /**< hash map */
3304  SCIP_MESSAGEHDLR* messagehdlr /**< message handler */
3305  )
3306 {
3307  uint32_t maxprobelen = 0;
3308  uint64_t probelensum = 0;
3309  uint32_t nslots;
3310  uint32_t i;
3311 
3312  assert(hashmap != NULL);
3313 
3314  nslots = hashmap->mask + 1;
3315 
3316  /* compute the maximum and average probe length */
3317  for( i = 0; i < nslots; ++i )
3318  {
3319  if( hashmap->hashes[i] != 0 )
3320  {
3321  uint32_t probelen = ELEM_DISTANCE(i) + 1;
3322  probelensum += probelen;
3323  maxprobelen = MAX(probelen, maxprobelen);
3324  }
3325  }
3326 
3327  /* print general hash map statistics */
3328  SCIPmessagePrintInfo(messagehdlr, "%u hash entries, used %u/%u slots (%.1f%%)",
3329  (unsigned int)hashmap->nelements, (unsigned int)hashmap->nelements,
3330  (unsigned int)nslots, 100.0*(SCIP_Real)hashmap->nelements/(SCIP_Real)(nslots));
3331 
3332  /* if not empty print average and maximum probe length */
3333  if( hashmap->nelements > 0 )
3334  SCIPmessagePrintInfo(messagehdlr, ", avg. probe length is %.1f, max. probe length is %u",
3335  (SCIP_Real)(probelensum)/(SCIP_Real)hashmap->nelements, (unsigned int)maxprobelen);
3336  SCIPmessagePrintInfo(messagehdlr, "\n");
3337 }
3338 
3339 /** indicates whether a hash map has no entries */
3341  SCIP_HASHMAP* hashmap /**< hash map */
3342  )
3343 {
3344  assert(hashmap != NULL);
3345 
3346  return hashmap->nelements == 0;
3347 }
3348 
3349 /** gives the number of elements in a hash map */
3351  SCIP_HASHMAP* hashmap /**< hash map */
3352  )
3353 {
3354  return (int) hashmap->nelements;
3355 }
3356 
3357 /** gives the number of entries in the internal arrays of a hash map */
3359  SCIP_HASHMAP* hashmap /**< hash map */
3360  )
3361 {
3362  return (int) hashmap->mask + 1;
3363 }
3364 
3365 /** gives the hashmap entry at the given index or NULL if entry is empty */
3367  SCIP_HASHMAP* hashmap, /**< hash map */
3368  int entryidx /**< index of hash map entry */
3369  )
3370 {
3371  assert(hashmap != NULL);
3372 
3373  return hashmap->hashes[entryidx] == 0 ? NULL : &hashmap->slots[entryidx];
3374 }
3375 
3376 /** gives the origin of the hashmap entry */
3378  SCIP_HASHMAPENTRY* entry /**< hash map entry */
3379  )
3380 {
3381  assert(entry != NULL);
3382 
3383  return entry->origin;
3384 }
3385 
3386 /** gives the image of the hashmap entry */
3388  SCIP_HASHMAPENTRY* entry /**< hash map entry */
3389  )
3390 {
3391  assert(entry != NULL);
3392 
3393  return entry->image.ptr;
3394 }
3395 
3396 /** gives the image of the hashmap entry */
3398  SCIP_HASHMAPENTRY* entry /**< hash map entry */
3399  )
3400 {
3401  assert(entry != NULL);
3402 
3403  return entry->image.integer;
3404 }
3405 
3406 /** gives the image of the hashmap entry */
3408  SCIP_HASHMAPENTRY* entry /**< hash map entry */
3409  )
3410 {
3411  assert(entry != NULL);
3412 
3413  return entry->image.real;
3414 }
3415 
3416 /** sets pointer image of a hashmap entry */
3418  SCIP_HASHMAPENTRY* entry, /**< hash map entry */
3419  void* image /**< new image */
3420  )
3421 {
3422  assert(entry != NULL);
3423 
3424  entry->image.ptr = image;
3425 }
3426 
3427 /** sets integer image of a hashmap entry */
3429  SCIP_HASHMAPENTRY* entry, /**< hash map entry */
3430  int image /**< new image */
3431  )
3432 {
3433  assert(entry != NULL);
3434 
3435  entry->image.integer = image;
3436 }
3437 
3438 /** sets real image of a hashmap entry */
3440  SCIP_HASHMAPENTRY* entry, /**< hash map entry */
3441  SCIP_Real image /**< new image */
3442  )
3443 {
3444  assert(entry != NULL);
3445 
3446  entry->image.real = image;
3447 }
3448 
3449 /** removes all entries in a hash map. */
3451  SCIP_HASHMAP* hashmap /**< hash map */
3452  )
3453 {
3454  assert(hashmap != NULL);
3455 
3456  BMSclearMemoryArray(hashmap->hashes, hashmap->mask + 1);
3457 
3458  hashmap->nelements = 0;
3459 
3460  return SCIP_OKAY;
3461 }
3462 
3463 
3464 /*
3465  * Hash Set
3466  */
3467 
3468 /* redefine ELEM_DISTANCE macro for hashset */
3469 #undef ELEM_DISTANCE
3470 /* computes the distance from it's desired position for the element stored at pos */
3471 #define ELEM_DISTANCE(pos) (((pos) + nslots - hashSetDesiredPos(hashset, hashset->slots[(pos)])) & mask)
3472 
3473 /* calculate desired position of element in hash set */
3474 static
3476  SCIP_HASHSET* hashset, /**< the hash set */
3477  void* element /**< element to calculate position for */
3478  )
3479 {
3480  return (uint32_t)((UINT64_C(0x9e3779b97f4a7c15) * (uintptr_t)element)>>(hashset->shift));
3481 }
3482 
3483 static
3485  SCIP_HASHSET* hashset, /**< hash set */
3486  void* element /**< element to insert */
3487  )
3488 {
3489  uint32_t elemdistance;
3490  uint32_t pos;
3491  uint32_t nslots;
3492  uint32_t mask;
3493 
3494  assert(hashset != NULL);
3495  assert(hashset->slots != NULL);
3496  assert(element != NULL);
3497 
3498  pos = hashSetDesiredPos(hashset, element);
3499  nslots = (uint32_t)SCIPhashsetGetNSlots(hashset);
3500  mask = nslots - 1;
3501 
3502  elemdistance = 0;
3503  while( TRUE ) /*lint !e716*/
3504  {
3505  uint32_t distance;
3506 
3507  /* if position is empty or key equal insert element */
3508  if( hashset->slots[pos] == NULL )
3509  {
3510  hashset->slots[pos] = element;
3511  ++hashset->nelements;
3512  return;
3513  }
3514 
3515  if( hashset->slots[pos] == element )
3516  return;
3517 
3518  /* otherwise check if the current element at this position is closer to its hashvalue */
3519  distance = ELEM_DISTANCE(pos);
3520  if( distance < elemdistance )
3521  {
3522  /* if this is the case we insert the new element here and find a new position for the old one */
3523  elemdistance = distance;
3524  SCIPswapPointers(&hashset->slots[pos], &element);
3525  }
3526 
3527  /* continue until we have found an empty position */
3528  pos = (pos + 1) & mask;
3529  ++elemdistance;
3530  }
3531 }
3532 
3533 /** check if the load factor of the hash set is too high and rebuild if necessary */
3534 static
3536  SCIP_HASHSET* hashset, /**< hash set */
3537  BMS_BLKMEM* blkmem /**< block memory used to store hash set entries */
3538  )
3539 {
3540  assert(hashset != NULL);
3541  assert(hashset->shift < 64);
3542 
3543  /* use integer arithmetic to approximately check if load factor is above 90% */
3544  if( ((((uint64_t)hashset->nelements)<<10)>>(64-hashset->shift) > 921) )
3545  {
3546  void** slots;
3547  uint32_t nslots;
3548  uint32_t newnslots;
3549  uint32_t i;
3550 
3551  /* calculate new size (always power of two) */
3552  nslots = (uint32_t)SCIPhashsetGetNSlots(hashset);
3553  newnslots = 2*nslots;
3554  --hashset->shift;
3555 
3556  /* reallocate array */
3557  SCIP_ALLOC( BMSallocClearBlockMemoryArray(blkmem, &slots, newnslots) );
3558 
3559  SCIPswapPointers((void**) &slots, (void**) &hashset->slots);
3560  hashset->nelements = 0;
3561 
3562  /* reinsert all elements */
3563  for( i = 0; i < nslots; ++i )
3564  {
3565  if( slots[i] != NULL )
3566  hashsetInsert(hashset, slots[i]);
3567  }
3568 
3569  BMSfreeBlockMemoryArray(blkmem, &slots, nslots);
3570  }
3571 
3572  return SCIP_OKAY;
3573 }
3574 
3575 /** creates a hash set of pointers */
3577  SCIP_HASHSET** hashset, /**< pointer to store the created hash set */
3578  BMS_BLKMEM* blkmem, /**< block memory used to store hash set entries */
3579  int size /**< initial size of the hash set; it is guaranteed that the set is not
3580  * resized if at most that many elements are inserted */
3581  )
3582 {
3583  uint32_t nslots;
3584 
3585  assert(hashset != NULL);
3586  assert(size >= 0);
3587  assert(blkmem != NULL);
3588 
3589  SCIP_ALLOC( BMSallocBlockMemory(blkmem, hashset) );
3590 
3591  /* dont create too small hashtables, i.e. at least size 32, and increase
3592  * the given size by divinding it by 0.9, since then no rebuilding will
3593  * be necessary if the given number of elements are inserted. Finally round
3594  * to the next power of two.
3595  */
3596  (*hashset)->shift = 64;
3597  (*hashset)->shift -= (int)ceil(log(MAX(8.0, size / 0.9)) / log(2.0));
3598  nslots = (uint32_t)SCIPhashsetGetNSlots(*hashset);
3599  (*hashset)->nelements = 0;
3600 
3601  SCIP_ALLOC( BMSallocClearBlockMemoryArray(blkmem, &(*hashset)->slots, nslots) );
3602 
3603  return SCIP_OKAY;
3604 }
3605 
3606 /** frees the hash set */
3608  SCIP_HASHSET** hashset, /**< pointer to the hash set */
3609  BMS_BLKMEM* blkmem /**< block memory used to store hash set entries */
3610  )
3611 {
3612  BMSfreeBlockMemoryArray(blkmem, &(*hashset)->slots, SCIPhashsetGetNSlots(*hashset));
3613  BMSfreeBlockMemory(blkmem, hashset);
3614 }
3615 
3616 /** inserts new element into the hash set */
3618  SCIP_HASHSET* hashset, /**< hash set */
3619  BMS_BLKMEM* blkmem, /**< block memory used to store hash set entries */
3620  void* element /**< element to insert */
3621  )
3622 {
3623  assert(hashset != NULL);
3624  assert(hashset->slots != NULL);
3625 
3626  SCIP_CALL( hashsetCheckLoad(hashset, blkmem) );
3627 
3628  hashsetInsert(hashset, element);
3629 
3630  return SCIP_OKAY;
3631 }
3632 
3633 /** checks whether an element exists in the hash set */
3635  SCIP_HASHSET* hashset, /**< hash set */
3636  void* element /**< element to search for */
3637  )
3638 {
3639  uint32_t pos;
3640  uint32_t nslots;
3641  uint32_t mask;
3642  uint32_t elemdistance;
3643 
3644  assert(hashset != NULL);
3645  assert(hashset->slots != NULL);
3646 
3647  pos = hashSetDesiredPos(hashset, element);
3648  nslots = (uint32_t)SCIPhashsetGetNSlots(hashset);
3649  mask = nslots - 1;
3650  elemdistance = 0;
3651 
3652  while( TRUE ) /*lint !e716*/
3653  {
3654  uint32_t distance;
3655 
3656  /* found element */
3657  if( hashset->slots[pos] == element )
3658  return TRUE;
3659 
3660  /* slots is empty so element cannot be contained */
3661  if( hashset->slots[pos] == NULL )
3662  return FALSE;
3663 
3664  distance = ELEM_DISTANCE(pos);
3665  /* element can not be contained since otherwise we would have swapped it with this one during insert */
3666  if( elemdistance > distance )
3667  return FALSE;
3668 
3669  pos = (pos + 1) & mask;
3670  ++elemdistance;
3671  }
3672 }
3673 
3674 /** removes an element from the hash set, if it exists */
3676  SCIP_HASHSET* hashset, /**< hash set */
3677  void* element /**< origin to remove from the list */
3678  )
3679 {
3680  uint32_t pos;
3681  uint32_t nslots;
3682  uint32_t mask;
3683  uint32_t elemdistance;
3684 
3685  assert(hashset != NULL);
3686  assert(hashset->slots != NULL);
3687  assert(element != NULL);
3688 
3689  pos = hashSetDesiredPos(hashset, element);
3690  nslots = (uint32_t)SCIPhashsetGetNSlots(hashset);
3691  mask = nslots - 1;
3692  elemdistance = 0;
3693 
3694  while( TRUE ) /*lint !e716*/
3695  {
3696  uint32_t distance;
3697 
3698  /* found element */
3699  if( hashset->slots[pos] == element )
3700  break;
3701 
3702  /* slots is empty so element cannot be contained */
3703  if( hashset->slots[pos] == NULL )
3704  return SCIP_OKAY;
3705 
3706  distance = ELEM_DISTANCE(pos);
3707  /* element can not be contained since otherwise we would have swapped it with this one during insert */
3708  if( elemdistance > distance )
3709  return SCIP_OKAY;
3710 
3711  pos = (pos + 1) & mask;
3712  ++elemdistance;
3713  }
3714 
3715  assert(hashset->slots[pos] == element);
3716  assert(SCIPhashsetExists(hashset, element));
3717 
3718  /* remove element */
3719  --hashset->nelements;
3720 
3721  /* move other elements if necessary */
3722  while( TRUE ) /*lint !e716*/
3723  {
3724  uint32_t nextpos = (pos + 1) & mask;
3725 
3726  /* nothing to do since there is no chain that needs to be moved */
3727  if( hashset->slots[nextpos] == NULL )
3728  {
3729  hashset->slots[pos] = NULL;
3730  assert(!SCIPhashsetExists(hashset, element));
3731  return SCIP_OKAY;
3732  }
3733 
3734  /* check if the element is the start of a new chain and return if that is the case */
3735  if( hashSetDesiredPos(hashset, hashset->slots[nextpos]) == nextpos )
3736  {
3737  hashset->slots[pos] = NULL;
3738  assert(!SCIPhashsetExists(hashset, element));
3739  return SCIP_OKAY;
3740  }
3741 
3742  /* element should be moved to the left and next element needs to be checked */
3743  hashset->slots[pos] = hashset->slots[nextpos];
3744 
3745  pos = nextpos;
3746  }
3747 }
3748 
3749 /** prints statistics about hash set usage */
3751  SCIP_HASHSET* hashset, /**< hash set */
3752  SCIP_MESSAGEHDLR* messagehdlr /**< message handler */
3753  )
3754 {
3755  uint32_t maxprobelen = 0;
3756  uint64_t probelensum = 0;
3757  uint32_t nslots;
3758  uint32_t mask;
3759  uint32_t i;
3760 
3761  assert(hashset != NULL);
3762 
3763  nslots = (uint32_t)SCIPhashsetGetNSlots(hashset);
3764  mask = nslots - 1;
3765 
3766  /* compute the maximum and average probe length */
3767  for( i = 0; i < nslots; ++i )
3768  {
3769  if( hashset->slots[i] != NULL )
3770  {
3771  uint32_t probelen = ((hashSetDesiredPos(hashset, hashset->slots[i]) + nslots - i) & mask) + 1;
3772  probelensum += probelen;
3773  maxprobelen = MAX(probelen, maxprobelen);
3774  }
3775  }
3776 
3777  /* print general hash set statistics */
3778  SCIPmessagePrintInfo(messagehdlr, "%u hash entries, used %u/%u slots (%.1f%%)",
3779  (unsigned int)hashset->nelements, (unsigned int)hashset->nelements,
3780  (unsigned int)nslots, 100.0*(SCIP_Real)hashset->nelements/(SCIP_Real)(nslots));
3781 
3782  /* if not empty print average and maximum probe length */
3783  if( hashset->nelements > 0 )
3784  SCIPmessagePrintInfo(messagehdlr, ", avg. probe length is %.1f, max. probe length is %u",
3785  (SCIP_Real)(probelensum)/(SCIP_Real)hashset->nelements, (unsigned int)maxprobelen);
3786  SCIPmessagePrintInfo(messagehdlr, "\n");
3787 }
3788 
3789 /* In debug mode, the following methods are implemented as function calls to ensure
3790  * type validity.
3791  * In optimized mode, the methods are implemented as defines to improve performance.
3792  * However, we want to have them in the library anyways, so we have to undef the defines.
3793  */
3794 
3795 #undef SCIPhashsetIsEmpty
3796 #undef SCIPhashsetGetNElements
3797 #undef SCIPhashsetGetNSlots
3798 #undef SCIPhashsetGetSlots
3799 
3800 /** indicates whether a hash set has no entries */
3802  SCIP_HASHSET* hashset /**< hash set */
3803  )
3804 {
3805  return hashset->nelements == 0;
3806 }
3807 
3808 /** gives the number of elements in a hash set */
3810  SCIP_HASHSET* hashset /**< hash set */
3811  )
3812 {
3813  return (int)hashset->nelements;
3814 }
3815 
3816 /** gives the number of slots of a hash set */
3818  SCIP_HASHSET* hashset /**< hash set */
3819  )
3820 {
3821  return (int) (1u << (64 - hashset->shift));
3822 }
3823 
3824 /** gives the array of hash set slots; contains all elements in indetermined order and may contain NULL values */
3826  SCIP_HASHSET* hashset /**< hash set */
3827  )
3828 {
3829  return hashset->slots;
3830 }
3831 
3832 /** removes all entries in a hash set. */
3834  SCIP_HASHSET* hashset /**< hash set */
3835  )
3836 {
3837  BMSclearMemoryArray(hashset->slots, SCIPhashsetGetNSlots(hashset));
3838 
3839  hashset->nelements = 0;
3840 }
3841 
3842 /*
3843  * Dynamic Arrays
3844  */
3845 
3846 /** creates a dynamic array of real values */
3848  SCIP_REALARRAY** realarray, /**< pointer to store the real array */
3849  BMS_BLKMEM* blkmem /**< block memory */
3850  )
3851 {
3852  assert(realarray != NULL);
3853  assert(blkmem != NULL);
3854 
3855  SCIP_ALLOC( BMSallocBlockMemory(blkmem, realarray) );
3856  (*realarray)->blkmem = blkmem;
3857  (*realarray)->vals = NULL;
3858  (*realarray)->valssize = 0;
3859  (*realarray)->firstidx = -1;
3860  (*realarray)->minusedidx = INT_MAX;
3861  (*realarray)->maxusedidx = INT_MIN;
3862 
3863  return SCIP_OKAY;
3864 }
3865 
3866 /** creates a copy of a dynamic array of real values */
3868  SCIP_REALARRAY** realarray, /**< pointer to store the copied real array */
3869  BMS_BLKMEM* blkmem, /**< block memory */
3870  SCIP_REALARRAY* sourcerealarray /**< dynamic real array to copy */
3871  )
3872 {
3873  assert(realarray != NULL);
3874  assert(sourcerealarray != NULL);
3875 
3876  SCIP_CALL( SCIPrealarrayCreate(realarray, blkmem) );
3877  if( sourcerealarray->valssize > 0 )
3878  {
3879  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*realarray)->vals, sourcerealarray->vals, \
3880  sourcerealarray->valssize) );
3881  }
3882  (*realarray)->valssize = sourcerealarray->valssize;
3883  (*realarray)->firstidx = sourcerealarray->firstidx;
3884  (*realarray)->minusedidx = sourcerealarray->minusedidx;
3885  (*realarray)->maxusedidx = sourcerealarray->maxusedidx;
3886 
3887  return SCIP_OKAY;
3888 }
3889 
3890 /** frees a dynamic array of real values */
3892  SCIP_REALARRAY** realarray /**< pointer to the real array */
3893  )
3894 {
3895  assert(realarray != NULL);
3896  assert(*realarray != NULL);
3897 
3898  BMSfreeBlockMemoryArrayNull((*realarray)->blkmem, &(*realarray)->vals, (*realarray)->valssize);
3899  BMSfreeBlockMemory((*realarray)->blkmem, realarray);
3900 
3901  return SCIP_OKAY;
3902 }
3903 
3904 /** extends dynamic array to be able to store indices from minidx to maxidx */
3906  SCIP_REALARRAY* realarray, /**< dynamic real array */
3907  int arraygrowinit, /**< initial size of array */
3908  SCIP_Real arraygrowfac, /**< growing factor of array */
3909  int minidx, /**< smallest index to allocate storage for */
3910  int maxidx /**< largest index to allocate storage for */
3911  )
3912 {
3913  int nused;
3914  int nfree;
3915  int newfirstidx;
3916  int i;
3917 
3918  assert(realarray != NULL);
3919  assert(realarray->minusedidx == INT_MAX || realarray->firstidx >= 0);
3920  assert(realarray->maxusedidx == INT_MIN || realarray->firstidx >= 0);
3921  assert(realarray->minusedidx == INT_MAX || realarray->minusedidx >= realarray->firstidx);
3922  assert(realarray->maxusedidx == INT_MIN || realarray->maxusedidx < realarray->firstidx + realarray->valssize);
3923  assert(0 <= minidx);
3924  assert(minidx <= maxidx);
3925 
3926  minidx = MIN(minidx, realarray->minusedidx);
3927  maxidx = MAX(maxidx, realarray->maxusedidx);
3928  assert(0 <= minidx);
3929  assert(minidx <= maxidx);
3930 
3931  SCIPdebugMessage("extending realarray %p (firstidx=%d, size=%d, range=[%d,%d]) to range [%d,%d]\n",
3932  (void*)realarray, realarray->firstidx, realarray->valssize, realarray->minusedidx, realarray->maxusedidx, minidx, maxidx);
3933 
3934  /* check, whether we have to allocate additional memory, or shift the array */
3935  nused = maxidx - minidx + 1;
3936  if( nused > realarray->valssize )
3937  {
3938  SCIP_Real* newvals;
3939  int newvalssize;
3940 
3941  /* allocate new memory storage */
3942  newvalssize = calcGrowSize(arraygrowinit, arraygrowfac, nused);
3943  SCIP_ALLOC( BMSallocBlockMemoryArray(realarray->blkmem, &newvals, newvalssize) );
3944  nfree = newvalssize - nused;
3945  newfirstidx = minidx - nfree/2;
3946  newfirstidx = MAX(newfirstidx, 0);
3947  assert(newfirstidx <= minidx);
3948  assert(maxidx < newfirstidx + newvalssize);
3949 
3950  /* initialize memory array by copying old values and setting new values to zero */
3951  if( realarray->firstidx != -1 )
3952  {
3953  for( i = 0; i < realarray->minusedidx - newfirstidx; ++i )
3954  newvals[i] = 0.0;
3955 
3956  /* check for possible overflow or negative value */
3957  assert(realarray->maxusedidx - realarray->minusedidx + 1 > 0);
3958 
3959  BMScopyMemoryArray(&newvals[realarray->minusedidx - newfirstidx],
3960  &(realarray->vals[realarray->minusedidx - realarray->firstidx]),
3961  realarray->maxusedidx - realarray->minusedidx + 1); /*lint !e866 !e776*/
3962  for( i = realarray->maxusedidx - newfirstidx + 1; i < newvalssize; ++i )
3963  newvals[i] = 0.0;
3964  }
3965  else
3966  {
3967  for( i = 0; i < newvalssize; ++i )
3968  newvals[i] = 0.0;
3969  }
3970 
3971  /* free old memory storage, and set the new array parameters */
3972  BMSfreeBlockMemoryArrayNull(realarray->blkmem, &realarray->vals, realarray->valssize);
3973  realarray->vals = newvals;
3974  realarray->valssize = newvalssize;
3975  realarray->firstidx = newfirstidx;
3976  }
3977  else if( realarray->firstidx == -1 )
3978  {
3979  /* a sufficiently large memory storage exists, but it was cleared */
3980  nfree = realarray->valssize - nused;
3981  assert(nfree >= 0);
3982  realarray->firstidx = minidx - nfree/2;
3983  assert(realarray->firstidx <= minidx);
3984  assert(maxidx < realarray->firstidx + realarray->valssize);
3985 #ifndef NDEBUG
3986  for( i = 0; i < realarray->valssize; ++i )
3987  assert(realarray->vals[i] == 0.0);
3988 #endif
3989  }
3990  else if( minidx < realarray->firstidx )
3991  {
3992  /* a sufficiently large memory storage exists, but it has to be shifted to the right */
3993  nfree = realarray->valssize - nused;
3994  assert(nfree >= 0);
3995  newfirstidx = minidx - nfree/2;
3996  newfirstidx = MAX(newfirstidx, 0);
3997  assert(newfirstidx <= minidx);
3998  assert(maxidx < newfirstidx + realarray->valssize);
3999 
4000  if( realarray->minusedidx <= realarray->maxusedidx )
4001  {
4002  int shift;
4003 
4004  assert(realarray->firstidx <= realarray->minusedidx);
4005  assert(realarray->maxusedidx < realarray->firstidx + realarray->valssize);
4006 
4007  /* shift used part of array to the right */
4008  shift = realarray->firstidx - newfirstidx;
4009  assert(shift > 0);
4010  for( i = realarray->maxusedidx - realarray->firstidx; i >= realarray->minusedidx - realarray->firstidx; --i )
4011  {
4012  assert(0 <= i + shift && i + shift < realarray->valssize);
4013  realarray->vals[i + shift] = realarray->vals[i];
4014  }
4015  /* clear the formerly used head of the array */
4016  for( i = 0; i < shift; ++i )
4017  realarray->vals[realarray->minusedidx - realarray->firstidx + i] = 0.0;
4018  }
4019  realarray->firstidx = newfirstidx;
4020  }
4021  else if( maxidx >= realarray->firstidx + realarray->valssize )
4022  {
4023  /* a sufficiently large memory storage exists, but it has to be shifted to the left */
4024  nfree = realarray->valssize - nused;
4025  assert(nfree >= 0);
4026  newfirstidx = minidx - nfree/2;
4027  newfirstidx = MAX(newfirstidx, 0);
4028  assert(newfirstidx <= minidx);
4029  assert(maxidx < newfirstidx + realarray->valssize);
4030 
4031  if( realarray->minusedidx <= realarray->maxusedidx )
4032  {
4033  int shift;
4034 
4035  assert(realarray->firstidx <= realarray->minusedidx);
4036  assert(realarray->maxusedidx < realarray->firstidx + realarray->valssize);
4037 
4038  /* shift used part of array to the left */
4039  shift = newfirstidx - realarray->firstidx;
4040  assert(shift > 0);
4041  for( i = realarray->minusedidx - realarray->firstidx; i <= realarray->maxusedidx - realarray->firstidx; ++i )
4042  {
4043  assert(0 <= i - shift && i - shift < realarray->valssize);
4044  realarray->vals[i - shift] = realarray->vals[i];
4045  }
4046  /* clear the formerly used tail of the array */
4047  for( i = 0; i < shift; ++i )
4048  realarray->vals[realarray->maxusedidx - realarray->firstidx - i] = 0.0;
4049  }
4050  realarray->firstidx = newfirstidx;
4051  }
4052 
4053  assert(minidx >= realarray->firstidx);
4054  assert(maxidx < realarray->firstidx + realarray->valssize);
4055 
4056  return SCIP_OKAY;
4057 }
4058 
4059 /** clears a dynamic real array */
4061  SCIP_REALARRAY* realarray /**< dynamic real array */
4062  )
4063 {
4064  assert(realarray != NULL);
4065 
4066  SCIPdebugMessage("clearing realarray %p (firstidx=%d, size=%d, range=[%d,%d])\n",
4067  (void*)realarray, realarray->firstidx, realarray->valssize, realarray->minusedidx, realarray->maxusedidx);
4068 
4069  if( realarray->minusedidx <= realarray->maxusedidx )
4070  {
4071  assert(realarray->firstidx <= realarray->minusedidx);
4072  assert(realarray->maxusedidx < realarray->firstidx + realarray->valssize);
4073  assert(realarray->firstidx != -1);
4074  assert(realarray->valssize > 0);
4075 
4076  /* clear the used part of array */
4077  BMSclearMemoryArray(&realarray->vals[realarray->minusedidx - realarray->firstidx],
4078  realarray->maxusedidx - realarray->minusedidx + 1); /*lint !e866*/
4079 
4080  /* mark the array cleared */
4081  realarray->minusedidx = INT_MAX;
4082  realarray->maxusedidx = INT_MIN;
4083  }
4084  assert(realarray->minusedidx == INT_MAX);
4085  assert(realarray->maxusedidx == INT_MIN);
4086 
4087  return SCIP_OKAY;
4088 }
4089 
4090 /** gets value of entry in dynamic array */
4092  SCIP_REALARRAY* realarray, /**< dynamic real array */
4093  int idx /**< array index to get value for */
4094  )
4095 {
4096  assert(realarray != NULL);
4097  assert(idx >= 0);
4098 
4099  if( idx < realarray->minusedidx || idx > realarray->maxusedidx )
4100  return 0.0;
4101  else
4102  {
4103  assert(realarray->vals != NULL);
4104  assert(idx - realarray->firstidx >= 0);
4105  assert(idx - realarray->firstidx < realarray->valssize);
4106 
4107  return realarray->vals[idx - realarray->firstidx];
4108  }
4109 }
4110 
4111 /** sets value of entry in dynamic array */
4113  SCIP_REALARRAY* realarray, /**< dynamic real array */
4114  int arraygrowinit, /**< initial size of array */
4115  SCIP_Real arraygrowfac, /**< growing factor of array */
4116  int idx, /**< array index to set value for */
4117  SCIP_Real val /**< value to set array index to */
4118  )
4119 {
4120  assert(realarray != NULL);
4121  assert(idx >= 0);
4122 
4123  SCIPdebugMessage("setting realarray %p (firstidx=%d, size=%d, range=[%d,%d]) index %d to %g\n",
4124  (void*)realarray, realarray->firstidx, realarray->valssize, realarray->minusedidx, realarray->maxusedidx, idx, val);
4125 
4126  if( val != 0.0 )
4127  {
4128  /* extend array to be able to store the index */
4129  SCIP_CALL( SCIPrealarrayExtend(realarray, arraygrowinit, arraygrowfac, idx, idx) );
4130  assert(idx >= realarray->firstidx);
4131  assert(idx < realarray->firstidx + realarray->valssize);
4132 
4133  /* set the array value of the index */
4134  realarray->vals[idx - realarray->firstidx] = val;
4135 
4136  /* update min/maxusedidx */
4137  realarray->minusedidx = MIN(realarray->minusedidx, idx);
4138  realarray->maxusedidx = MAX(realarray->maxusedidx, idx);
4139  }
4140  else if( idx >= realarray->firstidx && idx < realarray->firstidx + realarray->valssize )
4141  {
4142  /* set the array value of the index to zero */
4143  realarray->vals[idx - realarray->firstidx] = 0.0;
4144 
4145  /* check, if we can tighten the min/maxusedidx */
4146  if( idx == realarray->minusedidx )
4147  {
4148  assert(realarray->maxusedidx >= 0);
4149  assert(realarray->maxusedidx < realarray->firstidx + realarray->valssize);
4150  do
4151  {
4152  realarray->minusedidx++;
4153  }
4154  while( realarray->minusedidx <= realarray->maxusedidx
4155  && realarray->vals[realarray->minusedidx - realarray->firstidx] == 0.0 );
4156 
4157  if( realarray->minusedidx > realarray->maxusedidx )
4158  {
4159  realarray->minusedidx = INT_MAX;
4160  realarray->maxusedidx = INT_MIN;
4161  }
4162  }
4163  else if( idx == realarray->maxusedidx )
4164  {
4165  assert(realarray->minusedidx >= 0);
4166  assert(realarray->minusedidx < realarray->maxusedidx);
4167  assert(realarray->maxusedidx < realarray->firstidx + realarray->valssize);
4168  do
4169  {
4170  realarray->maxusedidx--;
4171  assert(realarray->minusedidx <= realarray->maxusedidx);
4172  }
4173  while( realarray->vals[realarray->maxusedidx - realarray->firstidx] == 0.0 );
4174  }
4175  }
4176 
4177  return SCIP_OKAY;
4178 }
4179 
4180 /** increases value of entry in dynamic array */
4182  SCIP_REALARRAY* realarray, /**< dynamic real array */
4183  int arraygrowinit, /**< initial size of array */
4184  SCIP_Real arraygrowfac, /**< growing factor of array */
4185  int idx, /**< array index to increase value for */
4186  SCIP_Real incval /**< value to increase array index */
4187  )
4188 {
4189  SCIP_Real oldval;
4190 
4191  oldval = SCIPrealarrayGetVal(realarray, idx);
4192  if( oldval != SCIP_INVALID ) /*lint !e777*/
4193  return SCIPrealarraySetVal(realarray, arraygrowinit, arraygrowfac, idx, oldval + incval);
4194  else
4195  return SCIP_OKAY;
4196 }
4197 
4198 /** returns the minimal index of all stored non-zero elements */
4200  SCIP_REALARRAY* realarray /**< dynamic real array */
4201  )
4202 {
4203  assert(realarray != NULL);
4204 
4205  return realarray->minusedidx;
4206 }
4207 
4208 /** returns the maximal index of all stored non-zero elements */
4210  SCIP_REALARRAY* realarray /**< dynamic real array */
4211  )
4212 {
4213  assert(realarray != NULL);
4214 
4215  return realarray->maxusedidx;
4216 }
4217 
4218 /** creates a dynamic array of int values */
4220  SCIP_INTARRAY** intarray, /**< pointer to store the int array */
4221  BMS_BLKMEM* blkmem /**< block memory */
4222  )
4223 {
4224  assert(intarray != NULL);
4225  assert(blkmem != NULL);
4226 
4227  SCIP_ALLOC( BMSallocBlockMemory(blkmem, intarray) );
4228  (*intarray)->blkmem = blkmem;
4229  (*intarray)->vals = NULL;
4230  (*intarray)->valssize = 0;
4231  (*intarray)->firstidx = -1;
4232  (*intarray)->minusedidx = INT_MAX;
4233  (*intarray)->maxusedidx = INT_MIN;
4234 
4235  return SCIP_OKAY;
4236 }
4237 
4238 /** creates a copy of a dynamic array of int values */
4240  SCIP_INTARRAY** intarray, /**< pointer to store the copied int array */
4241  BMS_BLKMEM* blkmem, /**< block memory */
4242  SCIP_INTARRAY* sourceintarray /**< dynamic int array to copy */
4243  )
4244 {
4245  assert(intarray != NULL);
4246  assert(sourceintarray != NULL);
4247 
4248  SCIP_CALL( SCIPintarrayCreate(intarray, blkmem) );
4249  if( sourceintarray->valssize > 0 )
4250  {
4251  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*intarray)->vals, sourceintarray->vals, sourceintarray->valssize) );
4252  }
4253  (*intarray)->valssize = sourceintarray->valssize;
4254  (*intarray)->firstidx = sourceintarray->firstidx;
4255  (*intarray)->minusedidx = sourceintarray->minusedidx;
4256  (*intarray)->maxusedidx = sourceintarray->maxusedidx;
4257 
4258  return SCIP_OKAY;
4259 }
4260 
4261 /** frees a dynamic array of int values */
4263  SCIP_INTARRAY** intarray /**< pointer to the int array */
4264  )
4265 {
4266  assert(intarray != NULL);
4267  assert(*intarray != NULL);
4268 
4269  BMSfreeBlockMemoryArrayNull((*intarray)->blkmem, &(*intarray)->vals, (*intarray)->valssize);
4270  BMSfreeBlockMemory((*intarray)->blkmem, intarray);
4271 
4272  return SCIP_OKAY;
4273 }
4274 
4275 /** extends dynamic array to be able to store indices from minidx to maxidx */
4277  SCIP_INTARRAY* intarray, /**< dynamic int array */
4278  int arraygrowinit, /**< initial size of array */
4279  SCIP_Real arraygrowfac, /**< growing factor of array */
4280  int minidx, /**< smallest index to allocate storage for */
4281  int maxidx /**< largest index to allocate storage for */
4282  )
4283 {
4284  int nused;
4285  int nfree;
4286  int newfirstidx;
4287  int i;
4288 
4289  assert(intarray != NULL);
4290  assert(intarray->minusedidx == INT_MAX || intarray->firstidx >= 0);
4291  assert(intarray->maxusedidx == INT_MIN || intarray->firstidx >= 0);
4292  assert(intarray->minusedidx == INT_MAX || intarray->minusedidx >= intarray->firstidx);
4293  assert(intarray->maxusedidx == INT_MIN || intarray->maxusedidx < intarray->firstidx + intarray->valssize);
4294  assert(0 <= minidx);
4295  assert(minidx <= maxidx);
4296 
4297  minidx = MIN(minidx, intarray->minusedidx);
4298  maxidx = MAX(maxidx, intarray->maxusedidx);
4299  assert(0 <= minidx);
4300  assert(minidx <= maxidx);
4301 
4302  SCIPdebugMessage("extending intarray %p (firstidx=%d, size=%d, range=[%d,%d]) to range [%d,%d]\n",
4303  (void*)intarray, intarray->firstidx, intarray->valssize, intarray->minusedidx, intarray->maxusedidx, minidx, maxidx);
4304 
4305  /* check, whether we have to allocate additional memory, or shift the array */
4306  nused = maxidx - minidx + 1;
4307  if( nused > intarray->valssize )
4308  {
4309  int* newvals;
4310  int newvalssize;
4311 
4312  /* allocate new memory storage */
4313  newvalssize = calcGrowSize(arraygrowinit, arraygrowfac, nused);
4314  SCIP_ALLOC( BMSallocBlockMemoryArray(intarray->blkmem, &newvals, newvalssize) );
4315  nfree = newvalssize - nused;
4316  newfirstidx = minidx - nfree/2;
4317  newfirstidx = MAX(newfirstidx, 0);
4318  assert(newfirstidx <= minidx);
4319  assert(maxidx < newfirstidx + newvalssize);
4320 
4321  /* initialize memory array by copying old values and setting new values to zero */
4322  if( intarray->firstidx != -1 )
4323  {
4324  for( i = 0; i < intarray->minusedidx - newfirstidx; ++i )
4325  newvals[i] = 0;
4326 
4327  /* check for possible overflow or negative value */
4328  assert(intarray->maxusedidx - intarray->minusedidx + 1 > 0);
4329 
4330  BMScopyMemoryArray(&newvals[intarray->minusedidx - newfirstidx],
4331  &intarray->vals[intarray->minusedidx - intarray->firstidx],
4332  intarray->maxusedidx - intarray->minusedidx + 1); /*lint !e866 !e776*/
4333  for( i = intarray->maxusedidx - newfirstidx + 1; i < newvalssize; ++i )
4334  newvals[i] = 0;
4335  }
4336  else
4337  {
4338  for( i = 0; i < newvalssize; ++i )
4339  newvals[i] = 0;
4340  }
4341 
4342  /* free old memory storage, and set the new array parameters */
4343  BMSfreeBlockMemoryArrayNull(intarray->blkmem, &intarray->vals, intarray->valssize);
4344  intarray->vals = newvals;
4345  intarray->valssize = newvalssize;
4346  intarray->firstidx = newfirstidx;
4347  }
4348  else if( intarray->firstidx == -1 )
4349  {
4350  /* a sufficiently large memory storage exists, but it was cleared */
4351  nfree = intarray->valssize - nused;
4352  assert(nfree >= 0);
4353  intarray->firstidx = minidx - nfree/2;
4354  assert(intarray->firstidx <= minidx);
4355  assert(maxidx < intarray->firstidx + intarray->valssize);
4356 #ifndef NDEBUG
4357  for( i = 0; i < intarray->valssize; ++i )
4358  assert(intarray->vals[i] == 0);
4359 #endif
4360  }
4361  else if( minidx < intarray->firstidx )
4362  {
4363  /* a sufficiently large memory storage exists, but it has to be shifted to the right */
4364  nfree = intarray->valssize - nused;
4365  assert(nfree >= 0);
4366  newfirstidx = minidx - nfree/2;
4367  newfirstidx = MAX(newfirstidx, 0);
4368  assert(newfirstidx <= minidx);
4369  assert(maxidx < newfirstidx + intarray->valssize);
4370 
4371  if( intarray->minusedidx <= intarray->maxusedidx )
4372  {
4373  int shift;
4374 
4375  assert(intarray->firstidx <= intarray->minusedidx);
4376  assert(intarray->maxusedidx < intarray->firstidx + intarray->valssize);
4377 
4378  /* shift used part of array to the right */
4379  shift = intarray->firstidx - newfirstidx;
4380  assert(shift > 0);
4381  for( i = intarray->maxusedidx - intarray->firstidx; i >= intarray->minusedidx - intarray->firstidx; --i )
4382  {
4383  assert(0 <= i + shift && i + shift < intarray->valssize);
4384  intarray->vals[i + shift] = intarray->vals[i];
4385  }
4386  /* clear the formerly used head of the array */
4387  for( i = 0; i < shift; ++i )
4388  intarray->vals[intarray->minusedidx - intarray->firstidx + i] = 0;
4389  }
4390  intarray->firstidx = newfirstidx;
4391  }
4392  else if( maxidx >= intarray->firstidx + intarray->valssize )
4393  {
4394  /* a sufficiently large memory storage exists, but it has to be shifted to the left */
4395  nfree = intarray->valssize - nused;
4396  assert(nfree >= 0);
4397  newfirstidx = minidx - nfree/2;
4398  newfirstidx = MAX(newfirstidx, 0);
4399  assert(newfirstidx <= minidx);
4400  assert(maxidx < newfirstidx + intarray->valssize);
4401 
4402  if( intarray->minusedidx <= intarray->maxusedidx )
4403  {
4404  int shift;
4405 
4406  assert(intarray->firstidx <= intarray->minusedidx);
4407  assert(intarray->maxusedidx < intarray->firstidx + intarray->valssize);
4408 
4409  /* shift used part of array to the left */
4410  shift = newfirstidx - intarray->firstidx;
4411  assert(shift > 0);
4412  for( i = intarray->minusedidx - intarray->firstidx; i <= intarray->maxusedidx - intarray->firstidx; ++i )
4413  {
4414  assert(0 <= i - shift && i - shift < intarray->valssize);
4415  intarray->vals[i - shift] = intarray->vals[i];
4416  }
4417  /* clear the formerly used tail of the array */
4418  for( i = 0; i < shift; ++i )
4419  intarray->vals[intarray->maxusedidx - intarray->firstidx - i] = 0;
4420  }
4421  intarray->firstidx = newfirstidx;
4422  }
4423 
4424  assert(minidx >= intarray->firstidx);
4425  assert(maxidx < intarray->firstidx + intarray->valssize);
4426 
4427  return SCIP_OKAY;
4428 }
4429 
4430 /** clears a dynamic int array */
4432  SCIP_INTARRAY* intarray /**< dynamic int array */
4433  )
4434 {
4435  assert(intarray != NULL);
4436 
4437  SCIPdebugMessage("clearing intarray %p (firstidx=%d, size=%d, range=[%d,%d])\n",
4438  (void*)intarray, intarray->firstidx, intarray->valssize, intarray->minusedidx, intarray->maxusedidx);
4439 
4440  if( intarray->minusedidx <= intarray->maxusedidx )
4441  {
4442  assert(intarray->firstidx <= intarray->minusedidx);
4443  assert(intarray->maxusedidx < intarray->firstidx + intarray->valssize);
4444  assert(intarray->firstidx != -1);
4445  assert(intarray->valssize > 0);
4446 
4447  /* clear the used part of array */
4448  BMSclearMemoryArray(&intarray->vals[intarray->minusedidx - intarray->firstidx],
4449  intarray->maxusedidx - intarray->minusedidx + 1); /*lint !e866*/
4450 
4451  /* mark the array cleared */
4452  intarray->minusedidx = INT_MAX;
4453  intarray->maxusedidx = INT_MIN;
4454  }
4455  assert(intarray->minusedidx == INT_MAX);
4456  assert(intarray->maxusedidx == INT_MIN);
4457 
4458  return SCIP_OKAY;
4459 }
4460 
4461 /** gets value of entry in dynamic array */
4463  SCIP_INTARRAY* intarray, /**< dynamic int array */
4464  int idx /**< array index to get value for */
4465  )
4466 {
4467  assert(intarray != NULL);
4468  assert(idx >= 0);
4469 
4470  if( idx < intarray->minusedidx || idx > intarray->maxusedidx )
4471  return 0;
4472  else
4473  {
4474  assert(intarray->vals != NULL);
4475  assert(idx - intarray->firstidx >= 0);
4476  assert(idx - intarray->firstidx < intarray->valssize);
4477 
4478  return intarray->vals[idx - intarray->firstidx];
4479  }
4480 }
4481 
4482 /** sets value of entry in dynamic array */
4484  SCIP_INTARRAY* intarray, /**< dynamic int array */
4485  int arraygrowinit, /**< initial size of array */
4486  SCIP_Real arraygrowfac, /**< growing factor of array */
4487  int idx, /**< array index to set value for */
4488  int val /**< value to set array index to */
4489  )
4490 {
4491  assert(intarray != NULL);
4492  assert(idx >= 0);
4493 
4494  SCIPdebugMessage("setting intarray %p (firstidx=%d, size=%d, range=[%d,%d]) index %d to %d\n",
4495  (void*)intarray, intarray->firstidx, intarray->valssize, intarray->minusedidx, intarray->maxusedidx, idx, val);
4496 
4497  if( val != 0 )
4498  {
4499  /* extend array to be able to store the index */
4500  SCIP_CALL( SCIPintarrayExtend(intarray, arraygrowinit, arraygrowfac, idx, idx) );
4501  assert(idx >= intarray->firstidx);
4502  assert(idx < intarray->firstidx + intarray->valssize);
4503 
4504  /* set the array value of the index */
4505  intarray->vals[idx - intarray->firstidx] = val;
4506 
4507  /* update min/maxusedidx */
4508  intarray->minusedidx = MIN(intarray->minusedidx, idx);
4509  intarray->maxusedidx = MAX(intarray->maxusedidx, idx);
4510  }
4511  else if( idx >= intarray->firstidx && idx < intarray->firstidx + intarray->valssize )
4512  {
4513  /* set the array value of the index to zero */
4514  intarray->vals[idx - intarray->firstidx] = 0;
4515 
4516  /* check, if we can tighten the min/maxusedidx */
4517  if( idx == intarray->minusedidx )
4518  {
4519  assert(intarray->maxusedidx >= 0);
4520  assert(intarray->maxusedidx < intarray->firstidx + intarray->valssize);
4521  do
4522  {
4523  intarray->minusedidx++;
4524  }
4525  while( intarray->minusedidx <= intarray->maxusedidx
4526  && intarray->vals[intarray->minusedidx - intarray->firstidx] == 0 );
4527  if( intarray->minusedidx > intarray->maxusedidx )
4528  {
4529  intarray->minusedidx = INT_MAX;
4530  intarray->maxusedidx = INT_MIN;
4531  }
4532  }
4533  else if( idx == intarray->maxusedidx )
4534  {
4535  assert(intarray->minusedidx >= 0);
4536  assert(intarray->minusedidx < intarray->maxusedidx);
4537  assert(intarray->maxusedidx < intarray->firstidx + intarray->valssize);
4538  do
4539  {
4540  intarray->maxusedidx--;
4541  assert(intarray->minusedidx <= intarray->maxusedidx);
4542  }
4543  while( intarray->vals[intarray->maxusedidx - intarray->firstidx] == 0 );
4544  }
4545  }
4546 
4547  return SCIP_OKAY;
4548 }
4549 
4550 /** increases value of entry in dynamic array */
4552  SCIP_INTARRAY* intarray, /**< dynamic int array */
4553  int arraygrowinit, /**< initial size of array */
4554  SCIP_Real arraygrowfac, /**< growing factor of array */
4555  int idx, /**< array index to increase value for */
4556  int incval /**< value to increase array index */
4557  )
4558 {
4559  return SCIPintarraySetVal(intarray, arraygrowinit, arraygrowfac, idx, SCIPintarrayGetVal(intarray, idx) + incval);
4560 }
4561 
4562 /** returns the minimal index of all stored non-zero elements */
4564  SCIP_INTARRAY* intarray /**< dynamic int array */
4565  )
4566 {
4567  assert(intarray != NULL);
4568 
4569  return intarray->minusedidx;
4570 }
4571 
4572 /** returns the maximal index of all stored non-zero elements */
4574  SCIP_INTARRAY* intarray /**< dynamic int array */
4575  )
4576 {
4577  assert(intarray != NULL);
4578 
4579  return intarray->maxusedidx;
4580 }
4581 
4582 
4583 /** creates a dynamic array of bool values */
4585  SCIP_BOOLARRAY** boolarray, /**< pointer to store the bool array */
4586  BMS_BLKMEM* blkmem /**< block memory */
4587  )
4588 {
4589  assert(boolarray != NULL);
4590  assert(blkmem != NULL);
4591 
4592  SCIP_ALLOC( BMSallocBlockMemory(blkmem, boolarray) );
4593  (*boolarray)->blkmem = blkmem;
4594  (*boolarray)->vals = NULL;
4595  (*boolarray)->valssize = 0;
4596  (*boolarray)->firstidx = -1;
4597  (*boolarray)->minusedidx = INT_MAX;
4598  (*boolarray)->maxusedidx = INT_MIN;
4599 
4600  return SCIP_OKAY;
4601 }
4602 
4603 /** creates a copy of a dynamic array of bool values */
4605  SCIP_BOOLARRAY** boolarray, /**< pointer to store the copied bool array */
4606  BMS_BLKMEM* blkmem, /**< block memory */
4607  SCIP_BOOLARRAY* sourceboolarray /**< dynamic bool array to copy */
4608  )
4609 {
4610  assert(boolarray != NULL);
4611  assert(sourceboolarray != NULL);
4612 
4613  SCIP_CALL( SCIPboolarrayCreate(boolarray, blkmem) );
4614  if( sourceboolarray->valssize > 0 )
4615  {
4616  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*boolarray)->vals, sourceboolarray->vals, \
4617  sourceboolarray->valssize) );
4618  }
4619  (*boolarray)->valssize = sourceboolarray->valssize;
4620  (*boolarray)->firstidx = sourceboolarray->firstidx;
4621  (*boolarray)->minusedidx = sourceboolarray->minusedidx;
4622  (*boolarray)->maxusedidx = sourceboolarray->maxusedidx;
4623 
4624  return SCIP_OKAY;
4625 }
4626 
4627 /** frees a dynamic array of bool values */
4629  SCIP_BOOLARRAY** boolarray /**< pointer to the bool array */
4630  )
4631 {
4632  assert(boolarray != NULL);
4633  assert(*boolarray != NULL);
4634 
4635  BMSfreeBlockMemoryArrayNull((*boolarray)->blkmem, &(*boolarray)->vals, (*boolarray)->valssize);
4636  BMSfreeBlockMemory((*boolarray)->blkmem, boolarray);
4637 
4638  return SCIP_OKAY;
4639 }
4640 
4641 /** extends dynamic array to be able to store indices from minidx to maxidx */
4643  SCIP_BOOLARRAY* boolarray, /**< dynamic bool array */
4644  int arraygrowinit, /**< initial size of array */
4645  SCIP_Real arraygrowfac, /**< growing factor of array */
4646  int minidx, /**< smallest index to allocate storage for */
4647  int maxidx /**< largest index to allocate storage for */
4648  )
4649 {
4650  int nused;
4651  int nfree;
4652  int newfirstidx;
4653  int i;
4654 
4655  assert(boolarray != NULL);
4656  assert(boolarray->minusedidx == INT_MAX || boolarray->firstidx >= 0);
4657  assert(boolarray->maxusedidx == INT_MIN || boolarray->firstidx >= 0);
4658  assert(boolarray->minusedidx == INT_MAX || boolarray->minusedidx >= boolarray->firstidx);
4659  assert(boolarray->maxusedidx == INT_MIN || boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
4660  assert(0 <= minidx);
4661  assert(minidx <= maxidx);
4662 
4663  minidx = MIN(minidx, boolarray->minusedidx);
4664  maxidx = MAX(maxidx, boolarray->maxusedidx);
4665  assert(0 <= minidx);
4666  assert(minidx <= maxidx);
4667 
4668  SCIPdebugMessage("extending boolarray %p (firstidx=%d, size=%d, range=[%d,%d]) to range [%d,%d]\n",
4669  (void*)boolarray, boolarray->firstidx, boolarray->valssize, boolarray->minusedidx, boolarray->maxusedidx, minidx, maxidx);
4670 
4671  /* check, whether we have to allocate additional memory, or shift the array */
4672  nused = maxidx - minidx + 1;
4673  if( nused > boolarray->valssize )
4674  {
4675  SCIP_Bool* newvals;
4676  int newvalssize;
4677 
4678  /* allocate new memory storage */
4679  newvalssize = calcGrowSize(arraygrowinit, arraygrowfac, nused);
4680  SCIP_ALLOC( BMSallocBlockMemoryArray(boolarray->blkmem, &newvals, newvalssize) );
4681  nfree = newvalssize - nused;
4682  newfirstidx = minidx - nfree/2;
4683  newfirstidx = MAX(newfirstidx, 0);
4684  assert(newfirstidx <= minidx);
4685  assert(maxidx < newfirstidx + newvalssize);
4686 
4687  /* initialize memory array by copying old values and setting new values to zero */
4688  if( boolarray->firstidx != -1 )
4689  {
4690  for( i = 0; i < boolarray->minusedidx - newfirstidx; ++i )
4691  newvals[i] = FALSE;
4692 
4693  /* check for possible overflow or negative value */
4694  assert(boolarray->maxusedidx - boolarray->minusedidx + 1 > 0);
4695 
4696  BMScopyMemoryArray(&newvals[boolarray->minusedidx - newfirstidx],
4697  &boolarray->vals[boolarray->minusedidx - boolarray->firstidx],
4698  boolarray->maxusedidx - boolarray->minusedidx + 1); /*lint !e866 !e776*/
4699  for( i = boolarray->maxusedidx - newfirstidx + 1; i < newvalssize; ++i )
4700  newvals[i] = FALSE;
4701  }
4702  else
4703  {
4704  for( i = 0; i < newvalssize; ++i )
4705  newvals[i] = FALSE;
4706  }
4707 
4708  /* free old memory storage, and set the new array parameters */
4709  BMSfreeBlockMemoryArrayNull(boolarray->blkmem, &boolarray->vals, boolarray->valssize);
4710  boolarray->vals = newvals;
4711  boolarray->valssize = newvalssize;
4712  boolarray->firstidx = newfirstidx;
4713  }
4714  else if( boolarray->firstidx == -1 )
4715  {
4716  /* a sufficiently large memory storage exists, but it was cleared */
4717  nfree = boolarray->valssize - nused;
4718  assert(nfree >= 0);
4719  boolarray->firstidx = minidx - nfree/2;
4720  assert(boolarray->firstidx <= minidx);
4721  assert(maxidx < boolarray->firstidx + boolarray->valssize);
4722 #ifndef NDEBUG
4723  for( i = 0; i < boolarray->valssize; ++i )
4724  assert(boolarray->vals[i] == FALSE);
4725 #endif
4726  }
4727  else if( minidx < boolarray->firstidx )
4728  {
4729  /* a sufficiently large memory storage exists, but it has to be shifted to the right */
4730  nfree = boolarray->valssize - nused;
4731  assert(nfree >= 0);
4732  newfirstidx = minidx - nfree/2;
4733  newfirstidx = MAX(newfirstidx, 0);
4734  assert(newfirstidx <= minidx);
4735  assert(maxidx < newfirstidx + boolarray->valssize);
4736 
4737  if( boolarray->minusedidx <= boolarray->maxusedidx )
4738  {
4739  int shift;
4740 
4741  assert(boolarray->firstidx <= boolarray->minusedidx);
4742  assert(boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
4743 
4744  /* shift used part of array to the right */
4745  shift = boolarray->firstidx - newfirstidx;
4746  assert(shift > 0);
4747  for( i = boolarray->maxusedidx - boolarray->firstidx; i >= boolarray->minusedidx - boolarray->firstidx; --i )
4748  {
4749  assert(0 <= i + shift && i + shift < boolarray->valssize);
4750  boolarray->vals[i + shift] = boolarray->vals[i];
4751  }
4752  /* clear the formerly used head of the array */
4753  for( i = 0; i < shift; ++i )
4754  boolarray->vals[boolarray->minusedidx - boolarray->firstidx + i] = FALSE;
4755  }
4756  boolarray->firstidx = newfirstidx;
4757  }
4758  else if( maxidx >= boolarray->firstidx + boolarray->valssize )
4759  {
4760  /* a sufficiently large memory storage exists, but it has to be shifted to the left */
4761  nfree = boolarray->valssize - nused;
4762  assert(nfree >= 0);
4763  newfirstidx = minidx - nfree/2;
4764  newfirstidx = MAX(newfirstidx, 0);
4765  assert(newfirstidx <= minidx);
4766  assert(maxidx < newfirstidx + boolarray->valssize);
4767 
4768  if( boolarray->minusedidx <= boolarray->maxusedidx )
4769  {
4770  int shift;
4771 
4772  assert(boolarray->firstidx <= boolarray->minusedidx);
4773  assert(boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
4774 
4775  /* shift used part of array to the left */
4776  shift = newfirstidx - boolarray->firstidx;
4777  assert(shift > 0);
4778 
4779  assert(0 <= boolarray->minusedidx - boolarray->firstidx - shift);
4780  assert(boolarray->maxusedidx - boolarray->firstidx - shift < boolarray->valssize);
4781  BMSmoveMemoryArray(&(boolarray->vals[boolarray->minusedidx - boolarray->firstidx - shift]),
4782  &(boolarray->vals[boolarray->minusedidx - boolarray->firstidx]),
4783  boolarray->maxusedidx - boolarray->minusedidx + 1); /*lint !e866*/
4784 
4785  /* clear the formerly used tail of the array */
4786  for( i = 0; i < shift; ++i )
4787  boolarray->vals[boolarray->maxusedidx - boolarray->firstidx - i] = FALSE;
4788  }
4789  boolarray->firstidx = newfirstidx;
4790  }
4791 
4792  assert(minidx >= boolarray->firstidx);
4793  assert(maxidx < boolarray->firstidx + boolarray->valssize);
4794 
4795  return SCIP_OKAY;
4796 }
4797 
4798 /** clears a dynamic bool array */
4800  SCIP_BOOLARRAY* boolarray /**< dynamic bool array */
4801  )
4802 {
4803  assert(boolarray != NULL);
4804 
4805  SCIPdebugMessage("clearing boolarray %p (firstidx=%d, size=%d, range=[%d,%d])\n",
4806  (void*)boolarray, boolarray->firstidx, boolarray->valssize, boolarray->minusedidx, boolarray->maxusedidx);
4807 
4808  if( boolarray->minusedidx <= boolarray->maxusedidx )
4809  {
4810  assert(boolarray->firstidx <= boolarray->minusedidx);
4811  assert(boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
4812  assert(boolarray->firstidx != -1);
4813  assert(boolarray->valssize > 0);
4814 
4815  /* clear the used part of array */
4816  BMSclearMemoryArray(&boolarray->vals[boolarray->minusedidx - boolarray->firstidx],
4817  boolarray->maxusedidx - boolarray->minusedidx + 1); /*lint !e866*/
4818 
4819  /* mark the array cleared */
4820  boolarray->minusedidx = INT_MAX;
4821  boolarray->maxusedidx = INT_MIN;
4822  }
4823  assert(boolarray->minusedidx == INT_MAX);
4824  assert(boolarray->maxusedidx == INT_MIN);
4825 
4826  return SCIP_OKAY;
4827 }
4828 
4829 /** gets value of entry in dynamic array */
4831  SCIP_BOOLARRAY* boolarray, /**< dynamic bool array */
4832  int idx /**< array index to get value for */
4833  )
4834 {
4835  assert(boolarray != NULL);
4836  assert(idx >= 0);
4837 
4838  if( idx < boolarray->minusedidx || idx > boolarray->maxusedidx )
4839  return FALSE;
4840  else
4841  {
4842  assert(boolarray->vals != NULL);
4843  assert(idx - boolarray->firstidx >= 0);
4844  assert(idx - boolarray->firstidx < boolarray->valssize);
4845 
4846  return boolarray->vals[idx - boolarray->firstidx];
4847  }
4848 }
4849 
4850 /** sets value of entry in dynamic array */
4852  SCIP_BOOLARRAY* boolarray, /**< dynamic bool array */
4853  int arraygrowinit, /**< initial size of array */
4854  SCIP_Real arraygrowfac, /**< growing factor of array */
4855  int idx, /**< array index to set value for */
4856  SCIP_Bool val /**< value to set array index to */
4857  )
4858 {
4859  assert(boolarray != NULL);
4860  assert(idx >= 0);
4861 
4862  SCIPdebugMessage("setting boolarray %p (firstidx=%d, size=%d, range=[%d,%d]) index %d to %u\n",
4863  (void*)boolarray, boolarray->firstidx, boolarray->valssize, boolarray->minusedidx, boolarray->maxusedidx, idx, val);
4864 
4865  if( val != FALSE )
4866  {
4867  /* extend array to be able to store the index */
4868  SCIP_CALL( SCIPboolarrayExtend(boolarray, arraygrowinit, arraygrowfac, idx, idx) );
4869  assert(idx >= boolarray->firstidx);
4870  assert(idx < boolarray->firstidx + boolarray->valssize);
4871 
4872  /* set the array value of the index */
4873  boolarray->vals[idx - boolarray->firstidx] = val;
4874 
4875  /* update min/maxusedidx */
4876  boolarray->minusedidx = MIN(boolarray->minusedidx, idx);
4877  boolarray->maxusedidx = MAX(boolarray->maxusedidx, idx);
4878  }
4879  else if( idx >= boolarray->firstidx && idx < boolarray->firstidx + boolarray->valssize )
4880  {
4881  /* set the array value of the index to zero */
4882  boolarray->vals[idx - boolarray->firstidx] = FALSE;
4883 
4884  /* check, if we can tighten the min/maxusedidx */
4885  if( idx == boolarray->minusedidx )
4886  {
4887  assert(boolarray->maxusedidx >= 0);
4888  assert(boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
4889  do
4890  {
4891  boolarray->minusedidx++;
4892  }
4893  while( boolarray->minusedidx <= boolarray->maxusedidx
4894  && boolarray->vals[boolarray->minusedidx - boolarray->firstidx] == FALSE );
4895  if( boolarray->minusedidx > boolarray->maxusedidx )
4896  {
4897  boolarray->minusedidx = INT_MAX;
4898  boolarray->maxusedidx = INT_MIN;
4899  }
4900  }
4901  else if( idx == boolarray->maxusedidx )
4902  {
4903  assert(boolarray->minusedidx >= 0);
4904  assert(boolarray->minusedidx < boolarray->maxusedidx);
4905  assert(boolarray->maxusedidx < boolarray->firstidx + boolarray->valssize);
4906  do
4907  {
4908  boolarray->maxusedidx--;
4909  assert(boolarray->minusedidx <= boolarray->maxusedidx);
4910  }
4911  while( boolarray->vals[boolarray->maxusedidx - boolarray->firstidx] == FALSE );
4912  }
4913  }
4914 
4915  return SCIP_OKAY;
4916 }
4917 
4918 /** returns the minimal index of all stored non-zero elements */
4920  SCIP_BOOLARRAY* boolarray /**< dynamic bool array */
4921  )
4922 {
4923  assert(boolarray != NULL);
4924 
4925  return boolarray->minusedidx;
4926 }
4927 
4928 /** returns the maximal index of all stored non-zero elements */
4930  SCIP_BOOLARRAY* boolarray /**< dynamic bool array */
4931  )
4932 {
4933  assert(boolarray != NULL);
4934 
4935  return boolarray->maxusedidx;
4936 }
4937 
4938 
4939 /** creates a dynamic array of pointer values */
4941  SCIP_PTRARRAY** ptrarray, /**< pointer to store the ptr array */
4942  BMS_BLKMEM* blkmem /**< block memory */
4943  )
4944 {
4945  assert(ptrarray != NULL);
4946  assert(blkmem != NULL);
4947 
4948  SCIP_ALLOC( BMSallocBlockMemory(blkmem, ptrarray) );
4949  (*ptrarray)->blkmem = blkmem;
4950  (*ptrarray)->vals = NULL;
4951  (*ptrarray)->valssize = 0;
4952  (*ptrarray)->firstidx = -1;
4953  (*ptrarray)->minusedidx = INT_MAX;
4954  (*ptrarray)->maxusedidx = INT_MIN;
4955 
4956  return SCIP_OKAY;
4957 }
4958 
4959 /** creates a copy of a dynamic array of pointer values */
4961  SCIP_PTRARRAY** ptrarray, /**< pointer to store the copied ptr array */
4962  BMS_BLKMEM* blkmem, /**< block memory */
4963  SCIP_PTRARRAY* sourceptrarray /**< dynamic ptr array to copy */
4964  )
4965 {
4966  assert(ptrarray != NULL);
4967  assert(sourceptrarray != NULL);
4968 
4969  SCIP_CALL( SCIPptrarrayCreate(ptrarray, blkmem) );
4970  if( sourceptrarray->valssize > 0 )
4971  {
4972  SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*ptrarray)->vals, sourceptrarray->vals, sourceptrarray->valssize) );
4973  }
4974  (*ptrarray)->valssize = sourceptrarray->valssize;
4975  (*ptrarray)->firstidx = sourceptrarray->firstidx;
4976  (*ptrarray)->minusedidx = sourceptrarray->minusedidx;
4977  (*ptrarray)->maxusedidx = sourceptrarray->maxusedidx;
4978 
4979  return SCIP_OKAY;
4980 }
4981 
4982 /** frees a dynamic array of pointer values */
4984  SCIP_PTRARRAY** ptrarray /**< pointer to the ptr array */
4985  )
4986 {
4987  assert(ptrarray != NULL);
4988  assert(*ptrarray != NULL);
4989 
4990  BMSfreeBlockMemoryArrayNull((*ptrarray)->blkmem, &(*ptrarray)->vals, (*ptrarray)->valssize);
4991  BMSfreeBlockMemory((*ptrarray)->blkmem, ptrarray);
4992 
4993  return SCIP_OKAY;
4994 }
4995 
4996 /** extends dynamic array to be able to store indices from minidx to maxidx */
4998  SCIP_PTRARRAY* ptrarray, /**< dynamic ptr array */
4999  int arraygrowinit, /**< initial size of array */
5000  SCIP_Real arraygrowfac, /**< growing factor of array */
5001  int minidx, /**< smallest index to allocate storage for */
5002  int maxidx /**< largest index to allocate storage for */
5003  )
5004 {
5005  int nused;
5006  int nfree;
5007  int newfirstidx;
5008  int i;
5009 
5010  assert(ptrarray != NULL);
5011  assert(ptrarray->minusedidx == INT_MAX || ptrarray->firstidx >= 0);
5012  assert(ptrarray->maxusedidx == INT_MIN || ptrarray->firstidx >= 0);
5013  assert(ptrarray->minusedidx == INT_MAX || ptrarray->minusedidx >= ptrarray->firstidx);
5014  assert(ptrarray->maxusedidx == INT_MIN || ptrarray->maxusedidx < ptrarray->firstidx + ptrarray->valssize);
5015  assert(0 <= minidx);
5016  assert(minidx <= maxidx);
5017 
5018  minidx = MIN(minidx, ptrarray->minusedidx);
5019  maxidx = MAX(maxidx, ptrarray->maxusedidx);
5020  assert(0 <= minidx);
5021  assert(minidx <= maxidx);
5022 
5023  SCIPdebugMessage("extending ptrarray %p (firstidx=%d, size=%d, range=[%d,%d]) to range [%d,%d]\n",
5024  (void*)ptrarray, ptrarray->firstidx, ptrarray->valssize, ptrarray->minusedidx, ptrarray->maxusedidx, minidx, maxidx);
5025 
5026  /* check, whether we have to allocate additional memory, or shift the array */
5027  nused = maxidx - minidx + 1;
5028  if( nused > ptrarray->valssize )
5029  {
5030  void** newvals;
5031  int newvalssize;
5032 
5033  /* allocate new memory storage */
5034  newvalssize = calcGrowSize(arraygrowinit, arraygrowfac, nused);
5035  SCIP_ALLOC( BMSallocBlockMemoryArray(ptrarray->blkmem, &newvals, newvalssize) );
5036  nfree = newvalssize - nused;
5037  newfirstidx = minidx - nfree/2;
5038  newfirstidx = MAX(newfirstidx, 0);
5039  assert(newfirstidx <= minidx);
5040  assert(maxidx < newfirstidx + newvalssize);
5041 
5042  /* initialize memory array by copying old values and setting new values to zero */
5043  if( ptrarray->firstidx != -1 )
5044  {
5045  for( i = 0; i < ptrarray->minusedidx - newfirstidx; ++i )
5046  newvals[i] = NULL;
5047 
5048  /* check for possible overflow or negative value */
5049  assert(ptrarray->maxusedidx - ptrarray->minusedidx + 1 > 0);
5050 
5051  BMScopyMemoryArray(&newvals[ptrarray->minusedidx - newfirstidx],
5052  &(ptrarray->vals[ptrarray->minusedidx - ptrarray->firstidx]),
5053  ptrarray->maxusedidx - ptrarray->minusedidx + 1); /*lint !e866 !e776*/
5054  for( i = ptrarray->maxusedidx - newfirstidx + 1; i < newvalssize; ++i )
5055  newvals[i] = NULL;
5056  }
5057  else
5058  {
5059  for( i = 0; i < newvalssize; ++i )
5060  newvals[i] = NULL;
5061  }
5062 
5063  /* free old memory storage, and set the new array parameters */
5064  BMSfreeBlockMemoryArrayNull(ptrarray->blkmem, &ptrarray->vals, ptrarray->valssize);
5065  ptrarray->vals = newvals;
5066  ptrarray->valssize = newvalssize;
5067  ptrarray->firstidx = newfirstidx;
5068  }
5069  else if( ptrarray->firstidx == -1 )
5070  {
5071  /* a sufficiently large memory storage exists, but it was cleared */
5072  nfree = ptrarray->valssize - nused;
5073  assert(nfree >= 0);
5074  ptrarray->firstidx = minidx - nfree/2;
5075  assert(ptrarray->firstidx <= minidx);
5076  assert(maxidx < ptrarray->firstidx + ptrarray->valssize);
5077 #ifndef NDEBUG
5078  for( i = 0; i < ptrarray->valssize; ++i )
5079  assert(ptrarray->vals[i] == NULL);
5080 #endif
5081  }
5082  else if( minidx < ptrarray->firstidx )
5083  {
5084  /* a sufficiently large memory storage exists, but it has to be shifted to the right */
5085  nfree = ptrarray->valssize - nused;
5086  assert(nfree >= 0);
5087  newfirstidx = minidx - nfree/2;
5088  newfirstidx = MAX(newfirstidx, 0);
5089  assert(newfirstidx <= minidx);
5090  assert(maxidx < newfirstidx + ptrarray->valssize);
5091 
5092  if( ptrarray->minusedidx <= ptrarray->maxusedidx )
5093  {
5094  int shift;
5095 
5096  assert(ptrarray->firstidx <= ptrarray->minusedidx);
5097  assert(ptrarray->maxusedidx < ptrarray->firstidx + ptrarray->valssize);
5098 
5099  /* shift used part of array to the right */
5100  shift = ptrarray->firstidx - newfirstidx;
5101  assert(shift > 0);
5102  for( i = ptrarray->maxusedidx - ptrarray->firstidx; i >= ptrarray->minusedidx - ptrarray->firstidx; --i )
5103  {
5104  assert(0 <= i + shift && i + shift < ptrarray->valssize);
5105  ptrarray->vals[i + shift] = ptrarray->vals[i];
5106  }
5107  /* clear the formerly used head of the array */
5108  for( i = 0; i < shift; ++i )
5109  ptrarray->vals[ptrarray->minusedidx - ptrarray->firstidx + i] = NULL;
5110  }
5111  ptrarray->firstidx = newfirstidx;
5112  }
5113  else if( maxidx >= ptrarray->firstidx + ptrarray->valssize )
5114  {
5115  /* a sufficiently large memory storage exists, but it has to be shifted to the left */
5116  nfree = ptrarray->valssize - nused;
5117  assert(nfree >= 0);
5118  newfirstidx = minidx - nfree/2;
5119  newfirstidx = MAX(newfirstidx, 0);
5120  assert(newfirstidx <= minidx);
5121  assert(maxidx < newfirstidx + ptrarray->valssize);
5122 
5123  if( ptrarray->minusedidx <= ptrarray->maxusedidx )
5124  {
5125  int shift;
5126 
5127  assert(ptrarray->firstidx <= ptrarray->minusedidx);
5128  assert(ptrarray->maxusedidx < ptrarray->firstidx + ptrarray->valssize);
5129 
5130  /* shift used part of array to the left */
5131  shift = newfirstidx - ptrarray->firstidx;
5132  assert(shift > 0);
5133  for( i = ptrarray->minusedidx - ptrarray->firstidx; i <= ptrarray->maxusedidx - ptrarray->firstidx; ++i )
5134  {
5135  assert(0 <= i - shift && i - shift < ptrarray->valssize);
5136  ptrarray->vals[i - shift] = ptrarray->vals[i];
5137  }
5138  /* clear the formerly used tail of the array */
5139  for( i = 0; i < shift; ++i )
5140  ptrarray->vals[ptrarray->maxusedidx - ptrarray->firstidx - i] = NULL;
5141  }
5142  ptrarray->firstidx = newfirstidx;
5143  }
5144 
5145  assert(minidx >= ptrarray->firstidx);
5146  assert(maxidx < ptrarray->firstidx + ptrarray->valssize);
5147 
5148  return SCIP_OKAY;
5149 }
5150 
5151 /** clears a dynamic pointer array */
5153  SCIP_PTRARRAY* ptrarray /**< dynamic ptr array */
5154  )
5155 {
5156  assert(ptrarray != NULL);
5157 
5158  SCIPdebugMessage("clearing ptrarray %p (firstidx=%d, size=%d, range=[%d,%d])\n",
5159  (void*)ptrarray, ptrarray->firstidx, ptrarray->valssize, ptrarray->minusedidx, ptrarray->maxusedidx);
5160 
5161  if( ptrarray->minusedidx <= ptrarray->maxusedidx )
5162  {
5163  assert(ptrarray->firstidx <= ptrarray->minusedidx);
5164  assert(ptrarray->maxusedidx < ptrarray->firstidx + ptrarray->valssize);
5165  assert(ptrarray->firstidx != -1);
5166  assert(ptrarray->valssize > 0);
5167 
5168  /* clear the used part of array */
5169  BMSclearMemoryArray(&ptrarray->vals[ptrarray->minusedidx - ptrarray->firstidx],
5170  ptrarray->maxusedidx - ptrarray->minusedidx + 1); /*lint !e866*/
5171 
5172  /* mark the array cleared */
5173  ptrarray->minusedidx = INT_MAX;
5174  ptrarray->maxusedidx = INT_MIN;
5175  }
5176  assert(ptrarray->minusedidx == INT_MAX);
5177  assert(ptrarray->maxusedidx == INT_MIN);
5178 
5179  return SCIP_OKAY;
5180 }
5181 
5182 /** gets value of entry in dynamic array */
5184  SCIP_PTRARRAY* ptrarray, /**< dynamic ptr array */
5185  int idx /**< array index to get value for */
5186  )
5187 {
5188  assert(ptrarray != NULL);
5189  assert(idx >= 0);
5190 
5191  if( idx < ptrarray->minusedidx || idx > ptrarray->maxusedidx )
5192  return NULL;
5193  else
5194  {
5195  assert(ptrarray->vals != NULL);
5196  assert(idx - ptrarray->firstidx >= 0);
5197  assert(idx - ptrarray->firstidx < ptrarray->valssize);
5198 
5199  return ptrarray->vals[idx - ptrarray->firstidx];
5200  }
5201 }
5202 
5203 /** sets value of entry in dynamic array */
5205  SCIP_PTRARRAY* ptrarray, /**< dynamic ptr array */
5206  int arraygrowinit, /**< initial size of array */
5207  SCIP_Real arraygrowfac, /**< growing factor of array */
5208  int idx, /**< array index to set value for */
5209  void* val /**< value to set array index to */
5210  )
5211 {
5212  assert(ptrarray != NULL);
5213  assert(idx >= 0);
5214 
5215  SCIPdebugMessage("setting ptrarray %p (firstidx=%d, size=%d, range=[%d,%d]) index %d to %p\n",
5216  (void*)ptrarray, ptrarray->firstidx, ptrarray->valssize, ptrarray->minusedidx, ptrarray->maxusedidx, idx, val);
5217 
5218  if( val != NULL )
5219  {
5220  /* extend array to be able to store the index */
5221  SCIP_CALL( SCIPptrarrayExtend(ptrarray, arraygrowinit, arraygrowfac, idx, idx) );
5222  assert(idx >= ptrarray->firstidx);
5223  assert(idx < ptrarray->firstidx + ptrarray->valssize);
5224 
5225  /* set the array value of the index */
5226  ptrarray->vals[idx - ptrarray->firstidx] = val;
5227 
5228  /* update min/maxusedidx */
5229  ptrarray->minusedidx = MIN(ptrarray->minusedidx, idx);
5230  ptrarray->maxusedidx = MAX(ptrarray->maxusedidx, idx);
5231  }
5232  else if( idx >= ptrarray->firstidx && idx < ptrarray->firstidx + ptrarray->valssize )
5233  {
5234  /* set the array value of the index to zero */
5235  ptrarray->vals[idx - ptrarray->firstidx] = NULL;
5236 
5237  /* check, if we can tighten the min/maxusedidx */
5238  if( idx == ptrarray->minusedidx )
5239  {
5240  assert(ptrarray->maxusedidx >= 0);
5241  assert(ptrarray->maxusedidx < ptrarray->firstidx + ptrarray->valssize);
5242  do
5243  {
5244  ptrarray->minusedidx++;
5245  }
5246  while( ptrarray->minusedidx <= ptrarray->maxusedidx
5247  && ptrarray->vals[ptrarray->minusedidx - ptrarray->firstidx] == NULL );
5248  if( ptrarray->minusedidx > ptrarray->maxusedidx )
5249  {
5250  ptrarray->minusedidx = INT_MAX;
5251  ptrarray->maxusedidx = INT_MIN;
5252  }
5253  }
5254  else if( idx == ptrarray->maxusedidx )
5255  {
5256  assert(ptrarray->minusedidx >= 0);
5257  assert(ptrarray->minusedidx < ptrarray->maxusedidx);
5258  assert(ptrarray->maxusedidx < ptrarray->firstidx + ptrarray->valssize);
5259  do
5260  {
5261  ptrarray->maxusedidx--;
5262  assert(ptrarray->minusedidx <= ptrarray->maxusedidx);
5263  }
5264  while( ptrarray->vals[ptrarray->maxusedidx - ptrarray->firstidx] == NULL );
5265  }
5266  }
5267 
5268  return SCIP_OKAY;
5269 }
5270 
5271 /** returns the minimal index of all stored non-zero elements */
5273  SCIP_PTRARRAY* ptrarray /**< dynamic ptr array */
5274  )
5275 {
5276  assert(ptrarray != NULL);
5277 
5278  return ptrarray->minusedidx;
5279 }
5280 
5281 /** returns the maximal index of all stored non-zero elements */
5283  SCIP_PTRARRAY* ptrarray /**< dynamic ptr array */
5284  )
5285 {
5286  assert(ptrarray != NULL);
5287 
5288  return ptrarray->maxusedidx;
5289 }
5290 
5291 
5292 /*
5293  * Sorting algorithms
5294  */
5295 
5296 /** default comparer for integers */
5297 SCIP_DECL_SORTPTRCOMP(SCIPsortCompInt)
5298 {
5299  int value1;
5300  int value2;
5301 
5302  value1 = (int)(size_t)elem1;
5303  value2 = (int)(size_t)elem2;
5304 
5305  if( value1 < value2 )
5306  return -1;
5307 
5308  if( value2 < value1 )
5309  return 1;
5310 
5311  return 0;
5312 }
5313 
5314 /* first all upwards-sorting methods */
5315 
5316 /** sort an indexed element set in non-decreasing order, resulting in a permutation index array */
5318  int* perm, /**< pointer to store the resulting permutation */
5319  SCIP_DECL_SORTINDCOMP((*indcomp)), /**< data element comparator */
5320  void* dataptr, /**< pointer to data field that is given to the external compare method */
5321  int len /**< number of elements to be sorted (valid index range) */
5322  )
5323 {
5324  int pos;
5325 
5326  assert(indcomp != NULL);
5327  assert(len == 0 || perm != NULL);
5328 
5329  /* create identity permutation */
5330  for( pos = 0; pos < len; ++pos )
5331  perm[pos] = pos;
5332 
5333  SCIPsortInd(perm, indcomp, dataptr, len);
5334 }
5335 
5336 /* SCIPsortInd(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5337 #define SORTTPL_NAMEEXT Ind
5338 #define SORTTPL_KEYTYPE int
5339 #define SORTTPL_INDCOMP
5340 #include "scip/sorttpl.c" /*lint !e451*/
5341 
5342 
5343 /* SCIPsortPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5344 #define SORTTPL_NAMEEXT Ptr
5345 #define SORTTPL_KEYTYPE void*
5346 #define SORTTPL_PTRCOMP
5347 #include "scip/sorttpl.c" /*lint !e451*/
5348 
5349 
5350 /* SCIPsortPtrPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5351 #define SORTTPL_NAMEEXT PtrPtr
5352 #define SORTTPL_KEYTYPE void*
5353 #define SORTTPL_FIELD1TYPE void*
5354 #define SORTTPL_PTRCOMP
5355 #include "scip/sorttpl.c" /*lint !e451*/
5356 
5357 
5358 /* SCIPsortPtrReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5359 #define SORTTPL_NAMEEXT PtrReal
5360 #define SORTTPL_KEYTYPE void*
5361 #define SORTTPL_FIELD1TYPE SCIP_Real
5362 #define SORTTPL_PTRCOMP
5363 #include "scip/sorttpl.c" /*lint !e451*/
5364 
5365 
5366 /* SCIPsortPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5367 #define SORTTPL_NAMEEXT PtrInt
5368 #define SORTTPL_KEYTYPE void*
5369 #define SORTTPL_FIELD1TYPE int
5370 #define SORTTPL_PTRCOMP
5371 #include "scip/sorttpl.c" /*lint !e451*/
5372 
5373 
5374 /* SCIPsortPtrBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5375 #define SORTTPL_NAMEEXT PtrBool
5376 #define SORTTPL_KEYTYPE void*
5377 #define SORTTPL_FIELD1TYPE SCIP_Bool
5378 #define SORTTPL_PTRCOMP
5379 #include "scip/sorttpl.c" /*lint !e451*/
5380 
5381 
5382 /* SCIPsortPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5383 #define SORTTPL_NAMEEXT PtrIntInt
5384 #define SORTTPL_KEYTYPE void*
5385 #define SORTTPL_FIELD1TYPE int
5386 #define SORTTPL_FIELD2TYPE int
5387 #define SORTTPL_PTRCOMP
5388 #include "scip/sorttpl.c" /*lint !e451*/
5389 
5390 
5391 /* SCIPsortPtrRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5392 #define SORTTPL_NAMEEXT PtrRealInt
5393 #define SORTTPL_KEYTYPE void*
5394 #define SORTTPL_FIELD1TYPE SCIP_Real
5395 #define SORTTPL_FIELD2TYPE int
5396 #define SORTTPL_PTRCOMP
5397 #include "scip/sorttpl.c" /*lint !e451*/
5398 
5399 /* SCIPsortPtrRealRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5400 #define SORTTPL_NAMEEXT PtrRealRealInt
5401 #define SORTTPL_KEYTYPE void*
5402 #define SORTTPL_FIELD1TYPE SCIP_Real
5403 #define SORTTPL_FIELD2TYPE SCIP_Real
5404 #define SORTTPL_FIELD3TYPE int
5405 #define SORTTPL_PTRCOMP
5406 #include "scip/sorttpl.c" /*lint !e451*/
5407 
5408 /* SCIPsortPtrRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5409 #define SORTTPL_NAMEEXT PtrRealBool
5410 #define SORTTPL_KEYTYPE void*
5411 #define SORTTPL_FIELD1TYPE SCIP_Real
5412 #define SORTTPL_FIELD2TYPE SCIP_Bool
5413 #define SORTTPL_PTRCOMP
5414 #include "scip/sorttpl.c" /*lint !e451*/
5415 
5416 
5417 /* SCIPsortPtrPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5418 #define SORTTPL_NAMEEXT PtrPtrInt
5419 #define SORTTPL_KEYTYPE void*
5420 #define SORTTPL_FIELD1TYPE void*
5421 #define SORTTPL_FIELD2TYPE int
5422 #define SORTTPL_PTRCOMP
5423 #include "scip/sorttpl.c" /*lint !e451*/
5424 
5425 
5426 /* SCIPsortPtrPtrReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5427 #define SORTTPL_NAMEEXT PtrPtrReal
5428 #define SORTTPL_KEYTYPE void*
5429 #define SORTTPL_FIELD1TYPE void*
5430 #define SORTTPL_FIELD2TYPE SCIP_Real
5431 #define SORTTPL_PTRCOMP
5432 #include "scip/sorttpl.c" /*lint !e451*/
5433 
5434 
5435 /* SCIPsortPtrRealIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5436 #define SORTTPL_NAMEEXT PtrRealIntInt
5437 #define SORTTPL_KEYTYPE void*
5438 #define SORTTPL_FIELD1TYPE SCIP_Real
5439 #define SORTTPL_FIELD2TYPE int
5440 #define SORTTPL_FIELD3TYPE int
5441 #define SORTTPL_PTRCOMP
5442 #include "scip/sorttpl.c" /*lint !e451*/
5443 
5444 
5445 /* SCIPsortPtrPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5446 #define SORTTPL_NAMEEXT PtrPtrIntInt
5447 #define SORTTPL_KEYTYPE void*
5448 #define SORTTPL_FIELD1TYPE void*
5449 #define SORTTPL_FIELD2TYPE int
5450 #define SORTTPL_FIELD3TYPE int
5451 #define SORTTPL_PTRCOMP
5452 #include "scip/sorttpl.c" /*lint !e451*/
5453 
5454 
5455 /* SCIPsortPtrPtrRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5456 #define SORTTPL_NAMEEXT PtrPtrRealInt
5457 #define SORTTPL_KEYTYPE void*
5458 #define SORTTPL_FIELD1TYPE void*
5459 #define SORTTPL_FIELD2TYPE SCIP_Real
5460 #define SORTTPL_FIELD3TYPE int
5461 #define SORTTPL_PTRCOMP
5462 #include "scip/sorttpl.c" /*lint !e451*/
5463 
5464 
5465 /* SCIPsortPtrPtrRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5466 #define SORTTPL_NAMEEXT PtrPtrRealBool
5467 #define SORTTPL_KEYTYPE void*
5468 #define SORTTPL_FIELD1TYPE void*
5469 #define SORTTPL_FIELD2TYPE SCIP_Real
5470 #define SORTTPL_FIELD3TYPE SCIP_Bool
5471 #define SORTTPL_PTRCOMP
5472 #include "scip/sorttpl.c" /*lint !e451*/
5473 
5474 
5475 /* SCIPsortPtrPtrLongInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5476 #define SORTTPL_NAMEEXT PtrPtrLongInt
5477 #define SORTTPL_KEYTYPE void*
5478 #define SORTTPL_FIELD1TYPE void*
5479 #define SORTTPL_FIELD2TYPE SCIP_Longint
5480 #define SORTTPL_FIELD3TYPE int
5481 #define SORTTPL_PTRCOMP
5482 #include "scip/sorttpl.c" /*lint !e451*/
5483 
5484 
5485 /* SCIPsortPtrPtrLongIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5486 #define SORTTPL_NAMEEXT PtrPtrLongIntInt
5487 #define SORTTPL_KEYTYPE void*
5488 #define SORTTPL_FIELD1TYPE void*
5489 #define SORTTPL_FIELD2TYPE SCIP_Longint
5490 #define SORTTPL_FIELD3TYPE int
5491 #define SORTTPL_FIELD4TYPE int
5492 #define SORTTPL_PTRCOMP
5493 #include "scip/sorttpl.c" /*lint !e451*/
5494 
5495 
5496 /* SCIPsortReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5497 #define SORTTPL_NAMEEXT Real
5498 #define SORTTPL_KEYTYPE SCIP_Real
5499 #include "scip/sorttpl.c" /*lint !e451*/
5500 
5501 
5502 /* SCIPsortRealBoolPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5503 #define SORTTPL_NAMEEXT RealBoolPtr
5504 #define SORTTPL_KEYTYPE SCIP_Real
5505 #define SORTTPL_FIELD1TYPE SCIP_Bool
5506 #define SORTTPL_FIELD2TYPE void*
5507 #include "scip/sorttpl.c" /*lint !e451*/
5508 
5509 
5510 /* SCIPsortRealPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5511 #define SORTTPL_NAMEEXT RealPtr
5512 #define SORTTPL_KEYTYPE SCIP_Real
5513 #define SORTTPL_FIELD1TYPE void*
5514 #include "scip/sorttpl.c" /*lint !e451*/
5515 
5516 
5517 /* SCIPsortRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5518 #define SORTTPL_NAMEEXT RealInt
5519 #define SORTTPL_KEYTYPE SCIP_Real
5520 #define SORTTPL_FIELD1TYPE int
5521 #include "scip/sorttpl.c" /*lint !e451*/
5522 
5523 
5524 /* SCIPsortRealIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5525 #define SORTTPL_NAMEEXT RealIntInt
5526 #define SORTTPL_KEYTYPE SCIP_Real
5527 #define SORTTPL_FIELD1TYPE int
5528 #define SORTTPL_FIELD2TYPE int
5529 #include "scip/sorttpl.c" /*lint !e451*/
5530 
5531 
5532 /* SCIPsortRealIntLong(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5533 #define SORTTPL_NAMEEXT RealIntLong
5534 #define SORTTPL_KEYTYPE SCIP_Real
5535 #define SORTTPL_FIELD1TYPE int
5536 #define SORTTPL_FIELD2TYPE SCIP_Longint
5537 #include "scip/sorttpl.c" /*lint !e451*/
5538 
5539 
5540 /* SCIPsortRealIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5541 #define SORTTPL_NAMEEXT RealIntPtr
5542 #define SORTTPL_KEYTYPE SCIP_Real
5543 #define SORTTPL_FIELD1TYPE int
5544 #define SORTTPL_FIELD2TYPE void*
5545 #include "scip/sorttpl.c" /*lint !e451*/
5546 
5547 
5548 /* SCIPsortRealRealPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5549 #define SORTTPL_NAMEEXT RealRealPtr
5550 #define SORTTPL_KEYTYPE SCIP_Real
5551 #define SORTTPL_FIELD1TYPE SCIP_Real
5552 #define SORTTPL_FIELD2TYPE void*
5553 #include "scip/sorttpl.c" /*lint !e451*/
5554 
5555 
5556 /* SCIPsortRealLongRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5557 #define SORTTPL_NAMEEXT RealLongRealInt
5558 #define SORTTPL_KEYTYPE SCIP_Real
5559 #define SORTTPL_FIELD1TYPE SCIP_Longint
5560 #define SORTTPL_FIELD2TYPE SCIP_Real
5561 #define SORTTPL_FIELD3TYPE int
5562 #include "scip/sorttpl.c" /*lint !e451*/
5563 
5564 /* SCIPsortRealRealIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5565 #define SORTTPL_NAMEEXT RealRealIntInt
5566 #define SORTTPL_KEYTYPE SCIP_Real
5567 #define SORTTPL_FIELD1TYPE SCIP_Real
5568 #define SORTTPL_FIELD2TYPE int
5569 #define SORTTPL_FIELD3TYPE int
5570 #include "scip/sorttpl.c" /*lint !e451*/
5571 
5572 
5573 /* SCIPsortRealRealRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5574 #define SORTTPL_NAMEEXT RealRealRealInt
5575 #define SORTTPL_KEYTYPE SCIP_Real
5576 #define SORTTPL_FIELD1TYPE SCIP_Real
5577 #define SORTTPL_FIELD2TYPE SCIP_Real
5578 #define SORTTPL_FIELD3TYPE int
5579 #include "scip/sorttpl.c" /*lint !e451*/
5580 
5581 
5582 /* SCIPsortRealRealRealPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5583 #define SORTTPL_NAMEEXT RealRealRealPtr
5584 #define SORTTPL_KEYTYPE SCIP_Real
5585 #define SORTTPL_FIELD1TYPE SCIP_Real
5586 #define SORTTPL_FIELD2TYPE SCIP_Real
5587 #define SORTTPL_FIELD3TYPE void*
5588 #include "scip/sorttpl.c" /*lint !e451*/
5589 
5590 
5591 /* SCIPsortRealPtrPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5592 #define SORTTPL_NAMEEXT RealPtrPtrInt
5593 #define SORTTPL_KEYTYPE SCIP_Real
5594 #define SORTTPL_FIELD1TYPE void*
5595 #define SORTTPL_FIELD2TYPE void*
5596 #define SORTTPL_FIELD3TYPE int
5597 #include "scip/sorttpl.c" /*lint !e451*/
5598 
5599 
5600 /* SCIPsortRealPtrPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5601 #define SORTTPL_NAMEEXT RealPtrPtrIntInt
5602 #define SORTTPL_KEYTYPE SCIP_Real
5603 #define SORTTPL_FIELD1TYPE void*
5604 #define SORTTPL_FIELD2TYPE void*
5605 #define SORTTPL_FIELD3TYPE int
5606 #define SORTTPL_FIELD4TYPE int
5607 #include "scip/sorttpl.c" /*lint !e451*/
5608 
5609 
5610 /* SCIPsortRealRealRealBoolPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5611 #define SORTTPL_NAMEEXT RealRealRealBoolPtr
5612 #define SORTTPL_KEYTYPE SCIP_Real
5613 #define SORTTPL_FIELD1TYPE SCIP_Real
5614 #define SORTTPL_FIELD2TYPE SCIP_Real
5615 #define SORTTPL_FIELD3TYPE SCIP_Bool
5616 #define SORTTPL_FIELD4TYPE void*
5617 #include "scip/sorttpl.c" /*lint !e451*/
5618 
5619 
5620 /* SCIPsortRealRealRealBoolBoolPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5621 #define SORTTPL_NAMEEXT RealRealRealBoolBoolPtr
5622 #define SORTTPL_KEYTYPE SCIP_Real
5623 #define SORTTPL_FIELD1TYPE SCIP_Real
5624 #define SORTTPL_FIELD2TYPE SCIP_Real
5625 #define SORTTPL_FIELD3TYPE SCIP_Bool
5626 #define SORTTPL_FIELD4TYPE SCIP_Bool
5627 #define SORTTPL_FIELD5TYPE void*
5628 #include "scip/sorttpl.c" /*lint !e451*/
5629 
5630 
5631 /* SCIPsortInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5632 #define SORTTPL_NAMEEXT Int
5633 #define SORTTPL_KEYTYPE int
5634 #include "scip/sorttpl.c" /*lint !e451*/
5635 
5636 
5637 /* SCIPsortIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5638 #define SORTTPL_NAMEEXT IntInt
5639 #define SORTTPL_KEYTYPE int
5640 #define SORTTPL_FIELD1TYPE int
5641 #include "scip/sorttpl.c" /*lint !e451*/
5642 
5643 
5644 /* SCIPsortIntReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5645 #define SORTTPL_NAMEEXT IntReal
5646 #define SORTTPL_KEYTYPE int
5647 #define SORTTPL_FIELD1TYPE SCIP_Real
5648 #include "scip/sorttpl.c" /*lint !e451*/
5649 
5650 
5651 /* SCIPsortIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5652 #define SORTTPL_NAMEEXT IntPtr
5653 #define SORTTPL_KEYTYPE int
5654 #define SORTTPL_FIELD1TYPE void*
5655 #include "scip/sorttpl.c" /*lint !e451*/
5656 
5657 
5658 /* SCIPsortIntIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5659 #define SORTTPL_NAMEEXT IntIntInt
5660 #define SORTTPL_KEYTYPE int
5661 #define SORTTPL_FIELD1TYPE int
5662 #define SORTTPL_FIELD2TYPE int
5663 #include "scip/sorttpl.c" /*lint !e451*/
5664 
5665 
5666 /* SCIPsortIntIntLong(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5667 #define SORTTPL_NAMEEXT IntIntLong
5668 #define SORTTPL_KEYTYPE int
5669 #define SORTTPL_FIELD1TYPE int
5670 #define SORTTPL_FIELD2TYPE SCIP_Longint
5671 #include "scip/sorttpl.c" /*lint !e451*/
5672 
5673 /* SCIPsortIntRealLong(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5674 #define SORTTPL_NAMEEXT IntRealLong
5675 #define SORTTPL_KEYTYPE int
5676 #define SORTTPL_FIELD1TYPE SCIP_Real
5677 #define SORTTPL_FIELD2TYPE SCIP_Longint
5678 #include "scip/sorttpl.c" /*lint !e451*/
5679 
5680 
5681 /* SCIPsortIntIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5682 #define SORTTPL_NAMEEXT IntIntPtr
5683 #define SORTTPL_KEYTYPE int
5684 #define SORTTPL_FIELD1TYPE int
5685 #define SORTTPL_FIELD2TYPE void*
5686 #include "scip/sorttpl.c" /*lint !e451*/
5687 
5688 
5689 /* SCIPsortIntIntReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5690 #define SORTTPL_NAMEEXT IntIntReal
5691 #define SORTTPL_KEYTYPE int
5692 #define SORTTPL_FIELD1TYPE int
5693 #define SORTTPL_FIELD2TYPE SCIP_Real
5694 #include "scip/sorttpl.c" /*lint !e451*/
5695 
5696 
5697 /* SCIPsortIntPtrReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5698 #define SORTTPL_NAMEEXT IntPtrReal
5699 #define SORTTPL_KEYTYPE int
5700 #define SORTTPL_FIELD1TYPE void*
5701 #define SORTTPL_FIELD2TYPE SCIP_Real
5702 #include "scip/sorttpl.c" /*lint !e451*/
5703 
5704 
5705 /* SCIPsortIntIntIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5706 #define SORTTPL_NAMEEXT IntIntIntPtr
5707 #define SORTTPL_KEYTYPE int
5708 #define SORTTPL_FIELD1TYPE int
5709 #define SORTTPL_FIELD2TYPE int
5710 #define SORTTPL_FIELD3TYPE void*
5711 #include "scip/sorttpl.c" /*lint !e451*/
5712 
5713 /* SCIPsortIntIntIntReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5714 #define SORTTPL_NAMEEXT IntIntIntReal
5715 #define SORTTPL_KEYTYPE int
5716 #define SORTTPL_FIELD1TYPE int
5717 #define SORTTPL_FIELD2TYPE int
5718 #define SORTTPL_FIELD3TYPE SCIP_Real
5719 #include "scip/sorttpl.c" /*lint !e451*/
5720 
5721 /* SCIPsortIntPtrIntReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5722 #define SORTTPL_NAMEEXT IntPtrIntReal
5723 #define SORTTPL_KEYTYPE int
5724 #define SORTTPL_FIELD1TYPE void*
5725 #define SORTTPL_FIELD2TYPE int
5726 #define SORTTPL_FIELD3TYPE SCIP_Real
5727 #include "scip/sorttpl.c" /*lint !e451*/
5728 
5729 
5730 /* SCIPsortLong(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5731 #define SORTTPL_NAMEEXT Long
5732 #define SORTTPL_KEYTYPE SCIP_Longint
5733 #include "scip/sorttpl.c" /*lint !e451*/
5734 
5735 
5736 /* SCIPsortLongPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5737 #define SORTTPL_NAMEEXT LongPtr
5738 #define SORTTPL_KEYTYPE SCIP_Longint
5739 #define SORTTPL_FIELD1TYPE void*
5740 #include "scip/sorttpl.c" /*lint !e451*/
5741 
5742 
5743 /* SCIPsortLongPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5744 #define SORTTPL_NAMEEXT LongPtrInt
5745 #define SORTTPL_KEYTYPE SCIP_Longint
5746 #define SORTTPL_FIELD1TYPE void*
5747 #define SORTTPL_FIELD2TYPE int
5748 #include "scip/sorttpl.c" /*lint !e451*/
5749 
5750 
5751 /* SCIPsortLongPtrRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5752 #define SORTTPL_NAMEEXT LongPtrRealBool
5753 #define SORTTPL_KEYTYPE SCIP_Longint
5754 #define SORTTPL_FIELD1TYPE void*
5755 #define SORTTPL_FIELD2TYPE SCIP_Real
5756 #define SORTTPL_FIELD3TYPE SCIP_Bool
5757 #include "scip/sorttpl.c" /*lint !e451*/
5758 
5759 
5760 /* SCIPsortLongPtrRealRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5761 #define SORTTPL_NAMEEXT LongPtrRealRealBool
5762 #define SORTTPL_KEYTYPE SCIP_Longint
5763 #define SORTTPL_FIELD1TYPE void*
5764 #define SORTTPL_FIELD2TYPE SCIP_Real
5765 #define SORTTPL_FIELD3TYPE SCIP_Real
5766 #define SORTTPL_FIELD4TYPE SCIP_Bool
5767 #include "scip/sorttpl.c" /*lint !e451*/
5768 
5769 
5770 /* SCIPsortLongPtrRealRealIntBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5771 #define SORTTPL_NAMEEXT LongPtrRealRealIntBool
5772 #define SORTTPL_KEYTYPE SCIP_Longint
5773 #define SORTTPL_FIELD1TYPE void*
5774 #define SORTTPL_FIELD2TYPE SCIP_Real
5775 #define SORTTPL_FIELD3TYPE SCIP_Real
5776 #define SORTTPL_FIELD4TYPE int
5777 #define SORTTPL_FIELD5TYPE SCIP_Bool
5778 #include "scip/sorttpl.c" /*lint !e451*/
5779 
5780 
5781 /* SCIPsortLongPtrPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5782 #define SORTTPL_NAMEEXT LongPtrPtrInt
5783 #define SORTTPL_KEYTYPE SCIP_Longint
5784 #define SORTTPL_FIELD1TYPE void*
5785 #define SORTTPL_FIELD2TYPE void*
5786 #define SORTTPL_FIELD3TYPE int
5787 #include "scip/sorttpl.c" /*lint !e451*/
5788 
5789 
5790 /* SCIPsortLongPtrPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5791 #define SORTTPL_NAMEEXT LongPtrPtrIntInt
5792 #define SORTTPL_KEYTYPE SCIP_Longint
5793 #define SORTTPL_FIELD1TYPE void*
5794 #define SORTTPL_FIELD2TYPE void*
5795 #define SORTTPL_FIELD3TYPE int
5796 #define SORTTPL_FIELD4TYPE int
5797 #include "scip/sorttpl.c" /*lint !e451*/
5798 
5799 
5800 /* SCIPsortLongPtrPtrBoolInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5801 #define SORTTPL_NAMEEXT LongPtrPtrBoolInt
5802 #define SORTTPL_KEYTYPE SCIP_Longint
5803 #define SORTTPL_FIELD1TYPE void*
5804 #define SORTTPL_FIELD2TYPE void*
5805 #define SORTTPL_FIELD3TYPE SCIP_Bool
5806 #define SORTTPL_FIELD4TYPE int
5807 #include "scip/sorttpl.c" /*lint !e451*/
5808 
5809 
5810 /* SCIPsortPtrIntIntBoolBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5811 #define SORTTPL_NAMEEXT PtrIntIntBoolBool
5812 #define SORTTPL_KEYTYPE void*
5813 #define SORTTPL_FIELD1TYPE int
5814 #define SORTTPL_FIELD2TYPE int
5815 #define SORTTPL_FIELD3TYPE SCIP_Bool
5816 #define SORTTPL_FIELD4TYPE SCIP_Bool
5817 #define SORTTPL_PTRCOMP
5818 #include "scip/sorttpl.c" /*lint !e451*/
5819 
5820 
5821 /* SCIPsortIntPtrIntIntBoolBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5822 #define SORTTPL_NAMEEXT IntPtrIntIntBoolBool
5823 #define SORTTPL_KEYTYPE int
5824 #define SORTTPL_FIELD1TYPE void*
5825 #define SORTTPL_FIELD2TYPE int
5826 #define SORTTPL_FIELD3TYPE int
5827 #define SORTTPL_FIELD4TYPE SCIP_Bool
5828 #define SORTTPL_FIELD5TYPE SCIP_Bool
5829 #include "scip/sorttpl.c" /*lint !e451*/
5830 
5831 
5832 /* now all downwards-sorting methods */
5833 
5834 
5835 /** sort an indexed element set in non-increasing order, resulting in a permutation index array */
5837  int* perm, /**< pointer to store the resulting permutation */
5838  SCIP_DECL_SORTINDCOMP((*indcomp)), /**< data element comparator */
5839  void* dataptr, /**< pointer to data field that is given to the external compare method */
5840  int len /**< number of elements to be sorted (valid index range) */
5841  )
5842 {
5843  int pos;
5844 
5845  assert(indcomp != NULL);
5846  assert(len == 0 || perm != NULL);
5847 
5848  /* create identity permutation */
5849  for( pos = 0; pos < len; ++pos )
5850  perm[pos] = pos;
5851 
5852  SCIPsortDownInd(perm, indcomp, dataptr, len);
5853 }
5854 
5855 
5856 /* SCIPsortDownInd(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5857 #define SORTTPL_NAMEEXT DownInd
5858 #define SORTTPL_KEYTYPE int
5859 #define SORTTPL_INDCOMP
5860 #define SORTTPL_BACKWARDS
5861 #include "scip/sorttpl.c" /*lint !e451*/
5862 
5863 
5864 /* SCIPsortDownPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5865 #define SORTTPL_NAMEEXT DownPtr
5866 #define SORTTPL_KEYTYPE void*
5867 #define SORTTPL_PTRCOMP
5868 #define SORTTPL_BACKWARDS
5869 #include "scip/sorttpl.c" /*lint !e451*/
5870 
5871 
5872 /* SCIPsortDownPtrPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5873 #define SORTTPL_NAMEEXT DownPtrPtr
5874 #define SORTTPL_KEYTYPE void*
5875 #define SORTTPL_FIELD1TYPE void*
5876 #define SORTTPL_PTRCOMP
5877 #define SORTTPL_BACKWARDS
5878 #include "scip/sorttpl.c" /*lint !e451*/
5879 
5880 
5881 /* SCIPsortDownPtrReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5882 #define SORTTPL_NAMEEXT DownPtrReal
5883 #define SORTTPL_KEYTYPE void*
5884 #define SORTTPL_FIELD1TYPE SCIP_Real
5885 #define SORTTPL_PTRCOMP
5886 #define SORTTPL_BACKWARDS
5887 #include "scip/sorttpl.c" /*lint !e451*/
5888 
5889 
5890 /* SCIPsortDownPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5891 #define SORTTPL_NAMEEXT DownPtrInt
5892 #define SORTTPL_KEYTYPE void*
5893 #define SORTTPL_FIELD1TYPE int
5894 #define SORTTPL_PTRCOMP
5895 #define SORTTPL_BACKWARDS
5896 #include "scip/sorttpl.c" /*lint !e451*/
5897 
5898 /* SCIPsortDownPtrBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5899 #define SORTTPL_NAMEEXT DownPtrBool
5900 #define SORTTPL_KEYTYPE void*
5901 #define SORTTPL_FIELD1TYPE SCIP_Bool
5902 #define SORTTPL_PTRCOMP
5903 #define SORTTPL_BACKWARDS
5904 #include "scip/sorttpl.c" /*lint !e451*/
5905 
5906 /* SCIPsortDownPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5907 #define SORTTPL_NAMEEXT DownPtrIntInt
5908 #define SORTTPL_KEYTYPE void*
5909 #define SORTTPL_FIELD1TYPE int
5910 #define SORTTPL_FIELD2TYPE int
5911 #define SORTTPL_PTRCOMP
5912 #define SORTTPL_BACKWARDS
5913 #include "scip/sorttpl.c" /*lint !e451*/
5914 
5915 
5916 /* SCIPsortDownPtrRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5917 #define SORTTPL_NAMEEXT DownPtrRealInt
5918 #define SORTTPL_KEYTYPE void*
5919 #define SORTTPL_FIELD1TYPE SCIP_Real
5920 #define SORTTPL_FIELD2TYPE int
5921 #define SORTTPL_PTRCOMP
5922 #define SORTTPL_BACKWARDS
5923 #include "scip/sorttpl.c" /*lint !e451*/
5924 
5925 
5926 /* SCIPsortDownPtrRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5927 #define SORTTPL_NAMEEXT DownPtrRealBool
5928 #define SORTTPL_KEYTYPE void*
5929 #define SORTTPL_FIELD1TYPE SCIP_Real
5930 #define SORTTPL_FIELD2TYPE SCIP_Bool
5931 #define SORTTPL_PTRCOMP
5932 #define SORTTPL_BACKWARDS
5933 #include "scip/sorttpl.c" /*lint !e451*/
5934 
5935 
5936 /* SCIPsortDownPtrPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5937 #define SORTTPL_NAMEEXT DownPtrPtrInt
5938 #define SORTTPL_KEYTYPE void*
5939 #define SORTTPL_FIELD1TYPE void*
5940 #define SORTTPL_FIELD2TYPE int
5941 #define SORTTPL_PTRCOMP
5942 #define SORTTPL_BACKWARDS
5943 #include "scip/sorttpl.c" /*lint !e451*/
5944 
5945 
5946 /* SCIPsortDownPtrPtrReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5947 #define SORTTPL_NAMEEXT DownPtrPtrReal
5948 #define SORTTPL_KEYTYPE void*
5949 #define SORTTPL_FIELD1TYPE void*
5950 #define SORTTPL_FIELD2TYPE SCIP_Real
5951 #define SORTTPL_PTRCOMP
5952 #define SORTTPL_BACKWARDS
5953 #include "scip/sorttpl.c" /*lint !e451*/
5954 
5955 
5956 /* SCIPsortDownPtrRealIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5957 #define SORTTPL_NAMEEXT DownPtrRealIntInt
5958 #define SORTTPL_KEYTYPE void*
5959 #define SORTTPL_FIELD1TYPE SCIP_Real
5960 #define SORTTPL_FIELD2TYPE int
5961 #define SORTTPL_FIELD3TYPE int
5962 #define SORTTPL_PTRCOMP
5963 #define SORTTPL_BACKWARDS
5964 #include "scip/sorttpl.c" /*lint !e451*/
5965 
5966 
5967 /* SCIPsortDownPtrPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5968 #define SORTTPL_NAMEEXT DownPtrPtrIntInt
5969 #define SORTTPL_KEYTYPE void*
5970 #define SORTTPL_FIELD1TYPE void*
5971 #define SORTTPL_FIELD2TYPE int
5972 #define SORTTPL_FIELD3TYPE int
5973 #define SORTTPL_PTRCOMP
5974 #define SORTTPL_BACKWARDS
5975 #include "scip/sorttpl.c" /*lint !e451*/
5976 
5977 
5978 /* SCIPsortDownPtrPtrRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5979 #define SORTTPL_NAMEEXT DownPtrPtrRealInt
5980 #define SORTTPL_KEYTYPE void*
5981 #define SORTTPL_FIELD1TYPE void*
5982 #define SORTTPL_FIELD2TYPE SCIP_Real
5983 #define SORTTPL_FIELD3TYPE int
5984 #define SORTTPL_PTRCOMP
5985 #define SORTTPL_BACKWARDS
5986 #include "scip/sorttpl.c" /*lint !e451*/
5987 
5988 
5989 /* SCIPsortDownPtrPtrRealBool(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
5990 #define SORTTPL_NAMEEXT DownPtrPtrRealBool
5991 #define SORTTPL_KEYTYPE void*
5992 #define SORTTPL_FIELD1TYPE void*
5993 #define SORTTPL_FIELD2TYPE SCIP_Real
5994 #define SORTTPL_FIELD3TYPE SCIP_Bool
5995 #define SORTTPL_PTRCOMP
5996 #define SORTTPL_BACKWARDS
5997 #include "scip/sorttpl.c" /*lint !e451*/
5998 
5999 
6000 /* SCIPsortDownPtrPtrLongInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6001 #define SORTTPL_NAMEEXT DownPtrPtrLongInt
6002 #define SORTTPL_KEYTYPE void*
6003 #define SORTTPL_FIELD1TYPE void*
6004 #define SORTTPL_FIELD2TYPE SCIP_Longint
6005 #define SORTTPL_FIELD3TYPE int
6006 #define SORTTPL_PTRCOMP
6007 #define SORTTPL_BACKWARDS
6008 #include "scip/sorttpl.c" /*lint !e451*/
6009 
6010 
6011 /* SCIPsortDownPtrPtrLongIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6012 #define SORTTPL_NAMEEXT DownPtrPtrLongIntInt
6013 #define SORTTPL_KEYTYPE void*
6014 #define SORTTPL_FIELD1TYPE void*
6015 #define SORTTPL_FIELD2TYPE SCIP_Longint
6016 #define SORTTPL_FIELD3TYPE int
6017 #define SORTTPL_FIELD4TYPE int
6018 #define SORTTPL_PTRCOMP
6019 #define SORTTPL_BACKWARDS
6020 #include "scip/sorttpl.c" /*lint !e451*/
6021 
6022 
6023 /* SCIPsortDownReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6024 #define SORTTPL_NAMEEXT DownReal
6025 #define SORTTPL_KEYTYPE SCIP_Real
6026 #define SORTTPL_BACKWARDS
6027 #include "scip/sorttpl.c" /*lint !e451*/
6028 
6029 
6030 /* SCIPsortDownRealBoolPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6031 #define SORTTPL_NAMEEXT DownRealBoolPtr
6032 #define SORTTPL_KEYTYPE SCIP_Real
6033 #define SORTTPL_FIELD1TYPE SCIP_Bool
6034 #define SORTTPL_FIELD2TYPE void*
6035 #define SORTTPL_BACKWARDS
6036 #include "scip/sorttpl.c" /*lint !e451*/
6037 
6038 
6039 /* SCIPsortDownRealPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6040 #define SORTTPL_NAMEEXT DownRealPtr
6041 #define SORTTPL_KEYTYPE SCIP_Real
6042 #define SORTTPL_FIELD1TYPE void*
6043 #define SORTTPL_BACKWARDS
6044 #include "scip/sorttpl.c" /*lint !e451*/
6045 
6046 
6047 /* SCIPsortDownRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6048 #define SORTTPL_NAMEEXT DownRealInt
6049 #define SORTTPL_KEYTYPE SCIP_Real
6050 #define SORTTPL_FIELD1TYPE int
6051 #define SORTTPL_BACKWARDS
6052 #include "scip/sorttpl.c" /*lint !e451*/
6053 
6054 /* SCIPsortDownRealIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6055 #define SORTTPL_NAMEEXT DownRealIntInt
6056 #define SORTTPL_KEYTYPE SCIP_Real
6057 #define SORTTPL_FIELD1TYPE int
6058 #define SORTTPL_FIELD2TYPE int
6059 #define SORTTPL_BACKWARDS
6060 #include "scip/sorttpl.c" /*lint !e451*/
6061 
6062 /* SCIPsortDownRealIntLong(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6063 #define SORTTPL_NAMEEXT DownRealIntLong
6064 #define SORTTPL_KEYTYPE SCIP_Real
6065 #define SORTTPL_FIELD1TYPE int
6066 #define SORTTPL_FIELD2TYPE SCIP_Longint
6067 #define SORTTPL_BACKWARDS
6068 #include "scip/sorttpl.c" /*lint !e451*/
6069 
6070 
6071 /* SCIPsortDownRealIntPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6072 #define SORTTPL_NAMEEXT DownRealIntPtr
6073 #define SORTTPL_KEYTYPE SCIP_Real
6074 #define SORTTPL_FIELD1TYPE int
6075 #define SORTTPL_FIELD2TYPE void*
6076 #define SORTTPL_BACKWARDS
6077 #include "scip/sorttpl.c" /*lint !e451*/
6078 
6079 
6080 /* SCIPsortDownRealPtrPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6081 #define SORTTPL_NAMEEXT DownRealPtrPtr
6082 #define SORTTPL_KEYTYPE SCIP_Real
6083 #define SORTTPL_FIELD1TYPE void*
6084 #define SORTTPL_FIELD2TYPE void*
6085 #define SORTTPL_BACKWARDS
6086 #include "scip/sorttpl.c" /*lint !e451*/
6087 
6088 /* SCIPsortDownRealRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6089 #define SORTTPL_NAMEEXT DownRealRealInt
6090 #define SORTTPL_KEYTYPE SCIP_Real
6091 #define SORTTPL_FIELD1TYPE SCIP_Real
6092 #define SORTTPL_FIELD2TYPE int
6093 #define SORTTPL_BACKWARDS
6094 #include "scip/sorttpl.c" /*lint !e451*/
6095 
6096 /* SCIPsortDownRealRealPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6097 #define SORTTPL_NAMEEXT DownRealRealPtr
6098 #define SORTTPL_KEYTYPE SCIP_Real
6099 #define SORTTPL_FIELD1TYPE SCIP_Real
6100 #define SORTTPL_FIELD2TYPE void*
6101 #define SORTTPL_BACKWARDS
6102 #include "scip/sorttpl.c" /*lint !e451*/
6103 
6104 /* SCIPsortDownRealRealPtrPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6105 #define SORTTPL_NAMEEXT DownRealRealPtrPtr
6106 #define SORTTPL_KEYTYPE SCIP_Real
6107 #define SORTTPL_FIELD1TYPE SCIP_Real
6108 #define SORTTPL_FIELD2TYPE void*
6109 #define SORTTPL_FIELD3TYPE void*
6110 #define SORTTPL_BACKWARDS
6111 #include "scip/sorttpl.c" /*lint !e451*/
6112 
6113 
6114 /* SCIPsortDownRealLongRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6115 #define SORTTPL_NAMEEXT DownRealLongRealInt
6116 #define SORTTPL_KEYTYPE SCIP_Real
6117 #define SORTTPL_FIELD1TYPE SCIP_Longint
6118 #define SORTTPL_FIELD2TYPE SCIP_Real
6119 #define SORTTPL_FIELD3TYPE int
6120 #define SORTTPL_BACKWARDS
6121 #include "scip/sorttpl.c" /*lint !e451*/
6122 
6123 
6124 /* SCIPsortDownRealRealIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6125 #define SORTTPL_NAMEEXT DownRealRealIntInt
6126 #define SORTTPL_KEYTYPE SCIP_Real
6127 #define SORTTPL_FIELD1TYPE SCIP_Real
6128 #define SORTTPL_FIELD2TYPE int
6129 #define SORTTPL_FIELD3TYPE int
6130 #define SORTTPL_BACKWARDS
6131 #include "scip/sorttpl.c" /*lint !e451*/
6132 
6133 
6134 /* SCIPsortDownRealRealRealInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6135 #define SORTTPL_NAMEEXT DownRealRealRealInt
6136 #define SORTTPL_KEYTYPE SCIP_Real
6137 #define SORTTPL_FIELD1TYPE SCIP_Real
6138 #define SORTTPL_FIELD2TYPE SCIP_Real
6139 #define SORTTPL_FIELD3TYPE int
6140 #define SORTTPL_BACKWARDS
6141 #include "scip/sorttpl.c" /*lint !e451*/
6142 
6143 
6144 /* SCIPsortDownRealRealRealPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6145 #define SORTTPL_NAMEEXT DownRealRealRealPtr
6146 #define SORTTPL_KEYTYPE SCIP_Real
6147 #define SORTTPL_FIELD1TYPE SCIP_Real
6148 #define SORTTPL_FIELD2TYPE SCIP_Real
6149 #define SORTTPL_FIELD3TYPE void*
6150 #define SORTTPL_BACKWARDS
6151 #include "scip/sorttpl.c" /*lint !e451*/
6152 
6153 
6154 /* SCIPsortDownRealPtrPtrInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6155 #define SORTTPL_NAMEEXT DownRealPtrPtrInt
6156 #define SORTTPL_KEYTYPE SCIP_Real
6157 #define SORTTPL_FIELD1TYPE void*
6158 #define SORTTPL_FIELD2TYPE void*
6159 #define SORTTPL_FIELD3TYPE int
6160 #define SORTTPL_BACKWARDS
6161 #include "scip/sorttpl.c" /*lint !e451*/
6162 
6163 /* SCIPsortDownRealPtrPtrIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6164 #define SORTTPL_NAMEEXT DownRealPtrPtrIntInt
6165 #define SORTTPL_KEYTYPE SCIP_Real
6166 #define SORTTPL_FIELD1TYPE void*
6167 #define SORTTPL_FIELD2TYPE void*
6168 #define SORTTPL_FIELD3TYPE int
6169 #define SORTTPL_FIELD4TYPE int
6170 #define SORTTPL_BACKWARDS
6171 #include "scip/sorttpl.c" /*lint !e451*/
6172 
6173 
6174 /* SCIPsortDownRealRealRealBoolPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6175 #define SORTTPL_NAMEEXT DownRealRealRealBoolPtr
6176 #define SORTTPL_KEYTYPE SCIP_Real
6177 #define SORTTPL_FIELD1TYPE SCIP_Real
6178 #define SORTTPL_FIELD2TYPE SCIP_Real
6179 #define SORTTPL_FIELD3TYPE SCIP_Bool
6180 #define SORTTPL_FIELD4TYPE void*
6181 #define SORTTPL_BACKWARDS
6182 #include "scip/sorttpl.c" /*lint !e451*/
6183 
6184 
6185 /* SCIPsortDownRealRealRealBoolBoolPtr(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6186 #define SORTTPL_NAMEEXT DownRealRealRealBoolBoolPtr
6187 #define SORTTPL_KEYTYPE SCIP_Real
6188 #define SORTTPL_FIELD1TYPE SCIP_Real
6189 #define SORTTPL_FIELD2TYPE SCIP_Real
6190 #define SORTTPL_FIELD3TYPE SCIP_Bool
6191 #define SORTTPL_FIELD4TYPE SCIP_Bool
6192 #define SORTTPL_FIELD5TYPE void*
6193 #include "scip/sorttpl.c" /*lint !e451*/
6194 
6195 
6196 /* SCIPsortDownInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6197 #define SORTTPL_NAMEEXT DownInt
6198 #define SORTTPL_KEYTYPE int
6199 #define SORTTPL_BACKWARDS
6200 #include "scip/sorttpl.c" /*lint !e451*/
6201 
6202 
6203 /* SCIPsortDownIntInt(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6204 #define SORTTPL_NAMEEXT DownIntInt
6205 #define SORTTPL_KEYTYPE int
6206 #define SORTTPL_FIELD1TYPE int
6207 #define SORTTPL_BACKWARDS
6208 #include "scip/sorttpl.c" /*lint !e451*/
6209 
6210 
6211 /* SCIPsortDownIntIntReal(), SCIPsortedvecInsert...(), SCIPsortedvecDelPos...(), SCIPsortedvecFind...() via sort template */
6212 #define SORTTPL_NAMEEXT DownIntIntReal
6213 #define SORTTPL_KEYTYPE int
6214 #define SORTTPL_FIELD1TYPE int
6215 #define SORTTPL_FIELD2TYPE SCIP_Real
6216 #define SORTTPL_BACKWARDS
6217 #include "scip/sortt