Scippy

SCIP

Solving Constraint Integer Programs

struct_misc.h
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-2017 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 email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file struct_misc.h
17  * @ingroup INTERNALAPI
18  * @brief miscellaneous datastructures
19  * @author Tobias Achterberg
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #ifndef __SCIP_STRUCT_MISC_H__
25 #define __SCIP_STRUCT_MISC_H__
26 
27 
28 #include "scip/def.h"
29 #include "blockmemshell/memory.h"
30 #include "scip/type_misc.h"
31 
32 #ifdef __cplusplus
33 extern "C" {
34 #endif
35 
36 /** data structure for sparse solutions */
38 {
39  SCIP_VAR** vars; /**< variables */
40  SCIP_Longint* lbvalues; /**< array of lower bounds */
41  SCIP_Longint* ubvalues; /**< array of upper bounds */
42  int nvars; /**< number of variables */
43 };
44 
45 /** (circular) Queue data structure */
46 struct SCIP_Queue
47 {
48  SCIP_Real sizefac; /**< memory growing factor */
49  void** slots; /**< array of element slots */
50  int firstfree; /**< first free slot */
51  int firstused; /**< first used slot */
52  int size; /**< total number of available element slots */
53 };
54 
55 /** priority queue data structure
56  * Elements are stored in an array, which grows dynamically in size as new elements are added to the queue.
57  * The ordering is done through a pointer comparison function.
58  * The array is organized as follows. The root element (that is the "best" element $r$ with $r <= x$ for all $x$)
59  * is stored in position 0. The children of an element at position $p$ are stored at positions $q_1 = 2*p+1$ and
60  * $q_2 = 2*p+2$. That means, the parent of the element at position $q$ is at position $p = (q-1)/2$.
61  * At any time, the condition holds that $p <= q$ for each parent $p$ and its children $q$.
62  * Insertion and removal of single elements needs time $O(log n)$.
63  */
65 {
66  SCIP_Real sizefac; /**< memory growing factor */
67  SCIP_DECL_SORTPTRCOMP((*ptrcomp)); /**< compares two data elements */
68  void** slots; /**< array of element slots */
69  int len; /**< number of used element slots */
70  int size; /**< total number of available element slots */
71 };
72 
73 /** hash table data structure */
75 {
76  SCIP_DECL_HASHGETKEY((*hashgetkey)); /**< gets the key of the given element */
77  SCIP_DECL_HASHKEYEQ ((*hashkeyeq)); /**< returns TRUE iff both keys are equal */
78  SCIP_DECL_HASHKEYVAL((*hashkeyval)); /**< returns the hash value of the key */
79  BMS_BLKMEM* blkmem; /**< block memory used to store hash map entries */
80  void* userptr; /**< user pointer */
81  void** slots; /**< slots of the hash table */
82  uint32_t* hashes; /**< hash values of elements stored in slots */
83  uint32_t shift; /**< power such that 2^(32-shift) == nslots */
84  uint32_t mask; /**< mask used for fast modulo, i.e. nslots - 1 */
85  uint32_t nelements; /**< number of elements in the hashtable */
86 };
87 
88 /** element list to store single elements of a hash table */
90 {
91  void* element; /**< this element */
92  SCIP_MULTIHASHLIST* next; /**< rest of the hash table list */
93 };
94 
95 /** multihash table data structure */
97 {
98  SCIP_DECL_HASHGETKEY((*hashgetkey)); /**< gets the key of the given element */
99  SCIP_DECL_HASHKEYEQ ((*hashkeyeq)); /**< returns TRUE iff both keys are equal */
100  SCIP_DECL_HASHKEYVAL((*hashkeyval)); /**< returns the hash value of the key */
101  BMS_BLKMEM* blkmem; /**< block memory used to store hash map entries */
102  SCIP_MULTIHASHLIST** lists; /**< multihash table lists of the hash table */
103  int nlists; /**< number of lists stored in the hash table */
104  void* userptr; /**< user pointer */
105  SCIP_Longint nelements; /**< number of elements in the hashtable */
106 };
107 
108 typedef union {
109  void* ptr; /**< pointer image */
110  SCIP_Real real; /**< real image */
112 
113 /** hash map entry */
115 {
116  void* origin; /**< origin of element */
117  SCIP_HASHMAPIMAGE image; /**< image of element */
118 };
119 
120 /** hash map data structure to map pointers on pointers */
122 {
123  BMS_BLKMEM* blkmem; /**< block memory used to store hash map entries */
124  SCIP_HASHMAPENTRY* slots; /**< buffer for hashmap entries */
125  uint32_t* hashes; /**< hashes of elements */
126  uint32_t shift; /**< power such that 2^(32-shift) == nslots */
127  uint32_t mask; /**< mask used for fast modulo, i.e. nslots - 1 */
128  uint32_t nelements; /**< number of elements in the hashtable */
129 };
130 
131 /** dynamic array for storing real values */
133 {
134  BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */
135  SCIP_Real* vals; /**< array values */
136  int valssize; /**< size of vals array */
137  int firstidx; /**< index of first element in vals array */
138  int minusedidx; /**< index of first non zero element in vals array */
139  int maxusedidx; /**< index of last non zero element in vals array */
140 };
141 
142 /** dynamic array for storing int values */
144 {
145  BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */
146  int* vals; /**< array values */
147  int valssize; /**< size of vals array */
148  int firstidx; /**< index of first element in vals array */
149  int minusedidx; /**< index of first non zero element in vals array */
150  int maxusedidx; /**< index of last non zero element in vals array */
151 };
152 
153 /** dynamic array for storing bool values */
155 {
156  BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */
157  SCIP_Bool* vals; /**< array values */
158  int valssize; /**< size of vals array */
159  int firstidx; /**< index of first element in vals array */
160  int minusedidx; /**< index of first non zero element in vals array */
161  int maxusedidx; /**< index of last non zero element in vals array */
162 };
163 
164 /** dynamic array for storing pointers */
166 {
167  BMS_BLKMEM* blkmem; /**< block memory that stores the vals array */
168  void** vals; /**< array values */
169  int valssize; /**< size of vals array */
170  int firstidx; /**< index of first element in vals array */
171  int minusedidx; /**< index of first non zero element in vals array */
172  int maxusedidx; /**< index of last non zero element in vals array */
173 };
174 
175 /** resource activity */
177 {
178  SCIP_VAR* var; /**< start time variable of the activity */
179  int duration; /**< duration of the activity */
180  int demand; /**< demand of the activity */
181 };
182 
183 /** resource profile */
185 {
186  int* timepoints; /**< time point array */
187  int* loads; /**< array holding the load for each time point */
188  int capacity; /**< capacity of the resource profile */
189  int ntimepoints; /**< current number of entries */
190  int arraysize; /**< current array size */
191 };
192 
193 /** digraph structure to store and handle graphs */
195 {
196  int** successors; /**< adjacency list: for each node (first dimension) list of all successors */
197  void*** arcdata; /**< arc data corresponding to the arcs to successors given by the successors array */
198  void** nodedata; /**< data for each node of graph */
199  int* successorssize; /**< sizes of the successor lists for the nodes */
200  int* nsuccessors; /**< number of successors stored in the adjacency lists of the nodes */
201  int* components; /**< array to store the node indices of the components, one component after the other */
202  int* componentstarts; /**< array to store the start indices of the components in the components array */
203  int ncomponents; /**< number of undirected components stored */
204  int componentstartsize; /**< size of array componentstarts */
205  int nnodes; /**< number of nodes, nodes should be numbered from 0 to nnodes-1 */
206 };
207 
208 /** binary node data structure for binary tree */
210 {
211  SCIP_BTNODE* parent; /**< pointer to the parent node */
212  SCIP_BTNODE* left; /**< pointer to the left child node */
213  SCIP_BTNODE* right; /**< pointer to the right child node */
214  void* dataptr; /**< user pointer */
215 };
216 
217 /** binary search tree data structure */
218 struct SCIP_Bt
219 {
220  SCIP_BTNODE* root; /**< pointer to the dummy root node; root is left child */
221  BMS_BLKMEM* blkmem; /**< block memory used to store tree nodes */
222 };
223 
224 /** data structure for incremental linear regression of data points (X_i, Y_i) */
226 {
227  SCIP_Real intercept; /**< the current axis intercept of the regression */
228  SCIP_Real slope; /**< the current slope of the regression */
229  SCIP_Real meanx; /**< mean of all X observations */
230  SCIP_Real meany; /**< mean of all Y observations */
231  SCIP_Real sumxy; /**< accumulated sum of all products X * Y */
232  SCIP_Real variancesumx; /**< incremental variance term for X observations */
233  SCIP_Real variancesumy; /**< incremental variance term for Y observations */
234  SCIP_Real corrcoef; /**< correlation coefficient of X and Y */
235  int nobservations; /**< number of observations so far */
236 };
237 
238 /** random number generator data */
240 {
241  uint32_t seed; /**< start seed */
242  uint32_t xor_seed; /**< Xorshift seed */
243  uint32_t mwc_seed; /**< Multiply-with-carry seed */
244  uint32_t cst_seed; /**< constant seed */
245  BMS_BLKMEM* blkmem; /**< block memory */
246 };
247 
248 #ifdef __cplusplus
249 }
250 #endif
251 
252 #endif
uint32_t * hashes
Definition: struct_misc.h:125
SCIP_BTNODE * parent
Definition: struct_misc.h:211
void ** slots
Definition: struct_misc.h:81
SCIP_Real * vals
Definition: struct_misc.h:135
BMS_BLKMEM * blkmem
Definition: struct_misc.h:79
void *** arcdata
Definition: struct_misc.h:197
#define SCIP_DECL_HASHKEYVAL(x)
Definition: type_misc.h:160
type definitions for miscellaneous datastructures
uint32_t shift
Definition: struct_misc.h:126
BMS_BLKMEM * blkmem
Definition: struct_misc.h:221
SCIP_Real intercept
Definition: struct_misc.h:227
void ** nodedata
Definition: struct_misc.h:198
int firstfree
Definition: struct_misc.h:50
#define SCIP_DECL_HASHGETKEY(x)
Definition: type_misc.h:154
int * componentstarts
Definition: struct_misc.h:202
uint32_t * hashes
Definition: struct_misc.h:82
uint32_t mwc_seed
Definition: struct_misc.h:243
uint32_t mask
Definition: struct_misc.h:84
uint32_t cst_seed
Definition: struct_misc.h:244
uint32_t nelements
Definition: struct_misc.h:85
SCIP_VAR ** vars
Definition: struct_misc.h:39
SCIP_MULTIHASHLIST ** lists
Definition: struct_misc.h:102
void * dataptr
Definition: struct_misc.h:214
SCIP_Real corrcoef
Definition: struct_misc.h:234
BMS_BLKMEM * blkmem
Definition: struct_misc.h:123
void * userptr
Definition: struct_misc.h:80
SCIP_BTNODE * root
Definition: struct_misc.h:220
int ** successors
Definition: struct_misc.h:196
void ** slots
Definition: struct_misc.h:68
SCIP_Real meany
Definition: struct_misc.h:230
BMS_BLKMEM * blkmem
Definition: struct_misc.h:134
BMS_BLKMEM * blkmem
Definition: struct_misc.h:145
SCIP_BTNODE * left
Definition: struct_misc.h:212
BMS_BLKMEM * blkmem
Definition: struct_misc.h:245
int * timepoints
Definition: struct_misc.h:186
uint32_t mask
Definition: struct_misc.h:127
SCIP_Real variancesumx
Definition: struct_misc.h:232
SCIP_Real sizefac
Definition: struct_misc.h:66
SCIP_Longint * lbvalues
Definition: struct_misc.h:40
uint32_t shift
Definition: struct_misc.h:83
SCIP_Real slope
Definition: struct_misc.h:228
uint32_t xor_seed
Definition: struct_misc.h:242
SCIP_Bool * vals
Definition: struct_misc.h:157
int * components
Definition: struct_misc.h:201
#define SCIP_Bool
Definition: def.h:61
SCIP_Real variancesumy
Definition: struct_misc.h:233
void ** slots
Definition: struct_misc.h:49
int * successorssize
Definition: struct_misc.h:199
SCIP_Longint * ubvalues
Definition: struct_misc.h:41
SCIP_Real sumxy
Definition: struct_misc.h:231
SCIP_Real meanx
Definition: struct_misc.h:229
#define SCIP_DECL_SORTPTRCOMP(x)
Definition: type_misc.h:151
SCIP_HASHMAPENTRY * slots
Definition: struct_misc.h:124
SCIP_BTNODE * right
Definition: struct_misc.h:213
#define SCIP_Real
Definition: def.h:135
int componentstartsize
Definition: struct_misc.h:204
uint32_t nelements
Definition: struct_misc.h:128
BMS_BLKMEM * blkmem
Definition: struct_misc.h:101
BMS_BLKMEM * blkmem
Definition: struct_misc.h:156
#define SCIP_Longint
Definition: def.h:120
#define SCIP_DECL_HASHKEYEQ(x)
Definition: type_misc.h:157
void ** vals
Definition: struct_misc.h:168
SCIP_MULTIHASHLIST * next
Definition: struct_misc.h:92
BMS_BLKMEM * blkmem
Definition: struct_misc.h:167
int * nsuccessors
Definition: struct_misc.h:200
SCIP_Longint nelements
Definition: struct_misc.h:105
SCIP_Real sizefac
Definition: struct_misc.h:48
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:392
SCIP_HASHMAPIMAGE image
Definition: struct_misc.h:117
int firstused
Definition: struct_misc.h:51
memory allocation routines