1 /* Copyright 2004,2007-2015 IPB, Universite de Bordeaux, INRIA & CNRS 2 ** 3 ** This file is part of the Scotch software package for static mapping, 4 ** graph partitioning and sparse matrix ordering. 5 ** 6 ** This software is governed by the CeCILL-C license under French law 7 ** and abiding by the rules of distribution of free software. You can 8 ** use, modify and/or redistribute the software under the terms of the 9 ** CeCILL-C license as circulated by CEA, CNRS and INRIA at the following 10 ** URL: "http://www.cecill.info". 11 ** 12 ** As a counterpart to the access to the source code and rights to copy, 13 ** modify and redistribute granted by the license, users are provided 14 ** only with a limited warranty and the software's author, the holder of 15 ** the economic rights, and the successive licensors have only limited 16 ** liability. 17 ** 18 ** In this respect, the user's attention is drawn to the risks associated 19 ** with loading, using, modifying and/or developing or reproducing the 20 ** software by the user in light of its specific status of free software, 21 ** that may mean that it is complicated to manipulate, and that also 22 ** therefore means that it is reserved for developers and experienced 23 ** professionals having in-depth computer knowledge. Users are therefore 24 ** encouraged to load and test the software's suitability as regards 25 ** their requirements in conditions enabling the security of their 26 ** systems and/or data to be ensured and, more generally, to use and 27 ** operate it in the same conditions as regards security. 28 ** 29 ** The fact that you are presently reading this means that you have had 30 ** knowledge of the CeCILL-C license and that you accept its terms. 31 */ 32 /************************************************************/ 33 /** **/ 34 /** NAME : common.h **/ 35 /** **/ 36 /** AUTHORS : Francois PELLEGRINI **/ 37 /** David GOUDIN **/ 38 /** Pascal HENON **/ 39 /** Pierre RAMET **/ 40 /** Cedric CHEVALIER (v5.0) **/ 41 /** Sebastien FOURESTIER (v6.0) **/ 42 /** **/ 43 /** FUNCTION : Part of a parallel direct block solver. **/ 44 /** These lines are the common data **/ 45 /** declarations for all modules. **/ 46 /** **/ 47 /** DATES : # Version 0.0 : from : 08 may 1998 **/ 48 /** to : 08 jan 2001 **/ 49 /** # Version 1.0 : from : 06 jun 2002 **/ 50 /** to : 06 jun 2002 **/ 51 /** # Version 2.0 : from : 13 jun 2005 **/ 52 /** to : 01 jul 2008 **/ 53 /** # Version 5.1 : from : 09 nov 2008 **/ 54 /** to : 23 nov 2010 **/ 55 /** # Version 6.0 : from : 03 mar 2011 **/ 56 /** to 01 mar 2015 **/ 57 /** **/ 58 /************************************************************/ 59 60 #define COMMON_H 61 62 /* 63 ** The includes. 64 */ 65 66 #ifndef _XOPEN_SOURCE 67 #define _XOPEN_SOURCE 600 68 #endif /* _XOPEN_SOURCE */ 69 #ifndef __USE_XOPEN2K 70 #define __USE_XOPEN2K /* For POSIX pthread_barrier_t */ 71 #endif /* __USE_XOPEN2K */ 72 73 #include <ctype.h> 74 #include <fcntl.h> /* Fow Windows _pipe () call */ 75 #include <math.h> 76 #include <memory.h> 77 #include <stdio.h> 78 #include <stdarg.h> 79 #include <stdlib.h> 80 #if (((defined __STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)) || (defined HAVE_STDINT_H)) 81 #include <stdint.h> 82 #endif /* (((defined __STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)) || (defined HAVE_STDINT_H)) */ 83 #ifdef HAVE_MALLOC_H 84 #include <malloc.h> /* Deprecated, but required on some old systems */ 85 #endif /* HAVE_MALLOC_H */ 86 #include <string.h> 87 #include <strings.h> 88 #include <time.h> /* For the effective calls to clock () */ 89 #include <limits.h> 90 #include <float.h> 91 #include <sys/types.h> 92 #if ((defined COMMON_TIMING_OLD) || (defined HAVE_SYS_TIME_H)) 93 #include <sys/time.h> 94 #endif /* ((defined COMMON_TIMING_OLD) || (defined HAVE_SYS_TIME_H)) */ 95 #if ((defined COMMON_TIMING_OLD) || (defined HAVE_SYS_RESOURCE_H)) 96 #include <sys/resource.h> 97 #endif /* ((defined COMMON_TIMING_OLD) || (defined HAVE_SYS_RESOURCE_H)) */ 98 #if ((defined COMMON_WINDOWS) || (defined HAVE_WINDOWS_H)) 99 #include <io.h> /* For _pipe () */ 100 #include <stddef.h> /* For intptr_t */ 101 #include <windows.h> 102 #endif /* ((defined COMMON_WINDOWS) || (defined HAVE_WINDOWS_H)) */ 103 #if ((! defined COMMON_WINDOWS) && (! defined HAVE_NOT_UNISTD_H)) 104 #include <unistd.h> 105 #endif /* ((! defined COMMON_WINDOWS) && (! defined HAVE_NOT_UNISTD_H)) */ 106 107 #ifdef SCOTCH_PTSCOTCH 108 #include <mpi.h> 109 #endif /* SCOTCH_PTSCOTCH */ 110 111 #if ((defined COMMON_PTHREAD) || (defined SCOTCH_PTHREAD)) 112 #include <pthread.h> 113 #endif /* ((defined COMMON_PTHREAD) || (defined SCOTCH_PTHREAD)) */ 114 115 /* 116 ** Working definitions. 117 */ 118 119 #ifdef COMMON_MEMORY_TRACE 120 #define memAlloc(size) memAllocRecord ((size) | 8) 121 #define memRealloc(ptr,size) memReallocRecord ((ptr), ((size) | 8)) 122 #define memFree(ptr) (memFreeRecord ((void *) (ptr)), 0) 123 #else /* COMMON_MEMORY_TRACE */ 124 #define memAlloc(size) malloc ((size) | 8) /* For platforms which return NULL for malloc(0) */ 125 #define memRealloc(ptr,size) realloc ((ptr),((size) | 8)) 126 #define memFree(ptr) (free ((char *) (ptr)), 0) 127 #endif /* COMMON_MEMORY_TRACE */ 128 129 #define memSet(ptr,val,siz) memset ((void *) (ptr), (val), (siz)) 130 #define memCpy(dst,src,siz) memcpy ((void *) (dst), (void *) (src), (siz)) 131 #define memMov(dst,src,siz) memmove ((void *) (dst), (void *) (src), (siz)) 132 133 #define MIN(x,y) (((x) < (y)) ? (x) : (y)) 134 #define MAX(x,y) (((x) < (y)) ? (y) : (x)) 135 #define ABS(x) MAX ((x), -(x)) 136 #define SIGN(x) (((x) < 0) ? -1 : 1) 137 138 /* 139 ** Handling of generic types. 140 */ 141 142 #if (((defined __STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)) || (defined HAVE_UINT_T)) 143 #define UINT32 uint32_t 144 #else /* (((defined __STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)) || (defined HAVE_UINT_T)) */ 145 #define UINT32 u_int32_t 146 #endif /* (((defined __STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)) || (defined HAVE_UINT_T)) */ 147 148 #ifndef INT /* If type not externally overriden */ 149 #ifdef INTSIZE32 150 #define INT int32_t 151 #define UINT UINT32 152 #define COMM_INT MPI_INTEGER4 153 #define INTSTRING "%d" 154 #else /* INTSIZE32 */ 155 #ifdef INTSIZE64 156 #define INT int64_t 157 #if (((defined __STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)) || (defined HAVE_UINT_T)) 158 #define UINT uint64_t 159 #else /* (((defined __STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)) || (defined HAVE_UINT_T)) */ 160 #define UINT u_int64_t 161 #endif /* (((defined __STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)) || (defined HAVE_UINT_T)) */ 162 #define COMM_INT MPI_LONG_LONG 163 #define INTSTRING "%lld" 164 #else /* INTSIZE64 */ 165 #ifdef LONG /* Better not use it */ 166 #define INT long /* Long integer type */ 167 #define UINT unsigned long 168 #define COMM_INT MPI_LONG 169 #define INTSTRING "%ld" 170 #else /* LONG */ 171 #define INT int /* Default integer type */ 172 #define UINT unsigned int 173 #define COMM_INT MPI_INT /* Generic MPI integer type */ 174 #define INTSTRING "%d" 175 #endif /* LONG */ 176 #endif /* INTSIZE64 */ 177 #endif /* INTSIZE32 */ 178 #endif /* INT */ 179 180 #ifndef IDX /* If type not externally overriden */ 181 #ifdef IDXSIZE32 182 #define IDX int32_t 183 #else /* IDXSIZE32 */ 184 #ifdef IDXSIZE64 185 #define IDX int64_t 186 #else /* IDXSIZE64 */ 187 #define IDX INT 188 #endif /* IDXSIZE64 */ 189 #endif /* IDXSIZE32 */ 190 #endif /* IDX */ 191 192 #ifndef INTSIZEBITS 193 #define INTSIZEBITS (sizeof (INT) << 3) 194 #endif /* INTSIZEBITS */ 195 196 #define INTVALMAX ((INT) (((UINT) 1 << (INTSIZEBITS - 1)) - 1)) 197 198 #define byte unsigned char /* Byte type */ 199 #ifndef BYTE 200 #define BYTE byte 201 #endif /* BYTE */ 202 #ifndef COMM_BYTE 203 #define COMM_BYTE MPI_BYTE 204 #endif /* COMM_BYTE */ 205 #define COMM_PART COMM_BYTE 206 207 /* 208 ** Handling of pseudo-random numbers. 209 */ 210 211 /* The pseudo-random state structure. It is 212 based on a Mersenne twister generator, also 213 referred to as MT19937. */ 214 215 typedef struct IntRandState_ { 216 UINT32 randtab[624]; /* State vector */ 217 int randnum; /* Index value */ 218 } IntRandState; 219 220 /* 221 ** Handling of flag arrays. 222 */ 223 224 #define flagSize(n) (((n) + (sizeof (int) << 3) - 1) / (sizeof (int) << 3)) 225 #define flagVal(a,n) (((a)[(n) / (sizeof (int) << 3)] >> ((n) & ((sizeof (int) << 3) - 1))) & 1) 226 #define flagSet(a,n) (a)[(n) / (sizeof (int) << 3)] |= (1 << ((n) & ((sizeof (int) << 3) - 1))) 227 228 /* 229 ** Handling of timers. 230 */ 231 232 /** The clock type. **/ 233 234 typedef struct Clock_ { 235 double time[2]; /*+ The start and accumulated times +*/ 236 } Clock; 237 238 /* 239 ** Handling of Windows constructs. 240 */ 241 242 #if defined COMMON_WINDOWS 243 #define pipe(fd) _pipe (fd, 32768, O_BINARY) 244 #endif /* COMMON_WINDOWS */ 245 246 /* 247 ** Handling of threads. 248 */ 249 250 /** The thread creation flags **/ 251 252 #define THREADNONE 0x0000 /* Thread capabilities */ 253 254 #define THREADHASBARRIER 0x0001 255 256 #define THREADCANBARRIER THREADHASBARRIER 257 #define THREADCANSCAN THREADHASBARRIER 258 #define THREADCANREDUCE THREADHASBARRIER 259 260 /** The thread barrier structure and routines **/ 261 262 #ifdef COMMON_PTHREAD_BARRIER 263 264 #ifndef PTHREAD_BARRIER_SERIAL_THREAD 265 #define PTHREAD_BARRIER_SERIAL_THREAD -1 266 #endif /* PTHREAD_BARRIER_SERIAL_THREAD */ 267 268 typedef struct ThreadBarrier_ { 269 int thrdnbr; /*+ Number of threads to wait for +*/ 270 volatile int thrdcur; /*+ Number of threads currently blocked +*/ 271 volatile int instnum; /*+ Number of barrier instance +*/ 272 pthread_mutex_t mutedat; 273 pthread_cond_t conddat; 274 } ThreadBarrier; 275 276 int threadBarrierDestroy (ThreadBarrier *); 277 int threadBarrierInit (ThreadBarrier *, void *, int); /* Thread attribute not used */ 278 int threadBarrierWait (ThreadBarrier *); 279 280 #else /* COMMON_PTHREAD_BARRIER */ 281 282 #define ThreadBarrier pthread_barrier_t 283 284 #define threadBarrierDestroy pthread_barrier_destroy 285 #define threadBarrierInit pthread_barrier_init 286 #define threadBarrierWait pthread_barrier_wait 287 288 #endif /* COMMON_PTHREAD_BARRIER */ 289 290 #define threadBarrier(t) threadBarrierWait (&(((ThreadGroupHeader *) (((ThreadHeader *) (void *) (t))->grouptr))->barrdat)) 291 292 /** The thread service routines auxiliary function types **/ 293 294 typedef int (* ThreadLaunchJoinFunc) (void * const, void * const); 295 typedef int (* ThreadLaunchStartFunc) (void * const); 296 typedef void (* ThreadReduceFunc) (void * const, void * const, void * const); 297 typedef void (* ThreadScanFunc) (void * const, void * const, void * const, const int); 298 299 /** The thread group header block. **/ 300 301 typedef struct ThreadGroupHeader_ { 302 #if ((defined COMMON_PTHREAD) || (defined SCOTCH_PTHREAD)) 303 int flagval; /*+ Thread block flags +*/ 304 size_t datasiz; /*+ Size of data array cell +*/ 305 int thrdnbr; /*+ Number of threads +*/ 306 ThreadLaunchStartFunc stafptr; /*+ Pointer to start routine +*/ 307 ThreadLaunchJoinFunc joifptr; /*+ Pointer to join routine +*/ 308 ThreadBarrier barrdat; /*+ Barrier data structure +*/ 309 #endif /* ((defined COMMON_PTHREAD) || (defined SCOTCH_PTHREAD)) */ 310 } ThreadGroupHeader; 311 312 /** The thread header block. **/ 313 314 typedef struct ThreadHeader_ { 315 void * grouptr; /*+ Pointer to thread group +*/ 316 #if ((defined COMMON_PTHREAD) || (defined SCOTCH_PTHREAD)) 317 pthread_t thidval; /*+ Thread ID +*/ 318 int thrdnum; /*+ Thread instance number +*/ 319 #endif /* ((defined COMMON_PTHREAD) || (defined SCOTCH_PTHREAD)) */ 320 } ThreadHeader; 321 322 /** The number of threads **/ 323 324 #ifdef SCOTCH_PTHREAD 325 326 #ifndef SCOTCH_PTHREAD_NUMBER 327 #define SCOTCH_PTHREAD_NUMBER 1 328 #endif /* SCOTCH_PTHREAD_NUMBER */ 329 330 #else /* SCOTCH_PTHREAD */ 331 332 #ifdef SCOTCH_PTHREAD_NUMBER 333 #undef SCOTCH_PTHREAD_NUMBER 334 #endif /* SCOTCH_PTHREAD_NUMBER */ 335 #define SCOTCH_PTHREAD_NUMBER 1 336 337 #endif /* SCOTCH_PTHREAD */ 338 339 /* 340 ** Handling of files. 341 */ 342 343 /** The file structure. **/ 344 345 typedef struct File_ { 346 char * modeptr; /*+ Opening mode +*/ 347 char * nameptr; /*+ File name +*/ 348 FILE * fileptr; /*+ File pointer +*/ 349 char * dataptr; /*+ Array to free +*/ 350 } File; 351 352 /* 353 ** Function prototypes. 354 */ 355 356 void * memAllocGroup (void **, ...); 357 void * memReallocGroup (void *, ...); 358 void * memOffset (void *, ...); 359 #ifdef COMMON_MEMORY_TRACE 360 void * memAllocRecord (size_t); 361 void * memReallocRecord (void * const, size_t); 362 void memFreeRecord (void * const); 363 IDX memCur (); /* What is internally an intptr_t has to be turned into an interface type */ 364 IDX memMax (); 365 #endif /* COMMON_MEMORY_TRACE */ 366 367 void usagePrint (FILE * const, const char (* [])); 368 369 void fileBlockInit (File * const, const int); 370 int fileBlockOpen (File * const, const int); 371 int fileBlockOpenDist (File * const, const int, const int, const int, const int); 372 void fileBlockClose (File * const, const int); 373 FILE * fileCompress (FILE * const, const int); 374 int fileCompressType (const char * const); 375 FILE * fileUncompress (FILE * const, const int); 376 int fileUncompressType (const char * const); 377 int fileNameDistExpand (char ** const, const int, const int, const int); 378 379 void errorProg (const char * const); 380 void errorPrint (const char * const, ...); 381 void errorPrintW (const char * const, ...); 382 383 int intLoad (FILE * const, INT * const); 384 int intSave (FILE * const, const INT); 385 void intAscn (INT * const, const INT, const INT); 386 void intPerm (INT * const, const INT); 387 void intRandInit (void); 388 void intRandProc (int); 389 void intRandReset (void); 390 void intRandSeed (INT); 391 #ifndef COMMON_RANDOM_SYSTEM 392 INT intRandVal (INT); 393 #endif /* COMMON_RANDOM_SYSTEM */ 394 void intSort1asc1 (void * const, const INT); 395 void intSort2asc1 (void * const, const INT); 396 void intSort2asc2 (void * const, const INT); 397 void intSort3asc1 (void * const, const INT); 398 void intSort3asc2 (void * const, const INT); 399 INT intSearchDicho (const INT * const, const INT, const INT, const INT); 400 INT intGcd (INT, INT); 401 402 void clockInit (Clock * const); 403 void clockStart (Clock * const); 404 void clockStop (Clock * const); 405 double clockVal (Clock * const); 406 double clockGet (void); 407 408 void stringSubst (char * const, const char * const, const char * const); 409 410 #ifdef COMMON_PTHREAD 411 int threadLaunch (void * const, void * const, const size_t, int (*) (void *), int (*) (void *, void *), const int, const int); 412 void threadReduce (void * const, void * const, ThreadReduceFunc const, const int); 413 void threadScan (void * const, void * const, ThreadScanFunc const); 414 #endif /* COMMON_PTHREAD */ 415 416 /* 417 ** Macro definitions. 418 */ 419 420 #define clockInit(clk) ((clk)->time[0] = (clk)->time[1] = 0) 421 #define clockStart(clk) ((clk)->time[0] = clockGet ()) 422 #define clockStop(clk) ((clk)->time[1] += (clockGet () - (clk)->time[0])) 423 #define clockVal(clk) ((clk)->time[1]) 424 425 #define fileBlockFile(b,i) ((b)[i].fileptr) 426 #define fileBlockMode(b,i) ((b)[i].modeptr) 427 #define fileBlockName(b,i) ((b)[i].nameptr) 428 429 #ifdef COMMON_RANDOM_SYSTEM 430 #ifdef COMMON_RANDOM_RAND 431 #define intRandVal(ival) ((INT) (((UINT) rand ()) % ((UINT) (ival)))) 432 #else /* COMMON_RANDOM_RAND */ 433 #define intRandVal(ival) ((INT) (((UINT) random ()) % ((UINT) (ival)))) 434 #endif /* COMMON_RANDOM_RAND */ 435 #endif /* COMMON_RANDOM_SYSTEM */ 436 437 #define DATASIZE(n,p,i) ((INT) (((n) + ((p) - 1 - (i))) / (p))) 438 #define DATASCAN(n,p,i) ((i) * ((INT) (n) / (INT) (p)) + (((i) > ((n) % (p))) ? ((n) % (p)) : (i))) 439 440 #define FORTRAN(nu,nl,pl,pc) FORTRAN2(REPLACE(nu),REPLACE(nl),pl,pc) 441 #define FORTRAN2(nu,nl,pl,pc) \ 442 void nu pl; \ 443 void nl pl \ 444 { nu pc; } \ 445 void GLUE(nl,_) pl \ 446 { nu pc; } \ 447 void GLUE(nl,__) pl \ 448 { nu pc; } \ 449 void nu pl 450 451 #define REPLACE(s) s 452 #define GLUE(p,s) p##s 453 454 #define STRINGIFY2(n) #n 455 #define STRINGIFY(n) STRINGIFY2(n) 456