Thread View: gnu.gcc.bug
1 messages
1 total messages
Started by Matthew S. Levine
Sun, 24 Nov 1996 00:00
cc1 gets signal 11 (segfault)
Author: Matthew S. Levine
Date: Sun, 24 Nov 1996 00:00
Date: Sun, 24 Nov 1996 00:00
4410 lines
49515 bytes
49515 bytes
I seem to be lucky enough to have a program that crashes cc1.
My program is malformed, but gcc still shouldn't crash.
The problem:
% gcc -O -c blah.c
pst.c: In function `pst_pack':
pst.c:248: parse error before `;'
gcc: Internal compiler error: program cc1 got fatal signal 11
This does not happen without -O.
My system:
% uname -a
Linux slip-mslevine 2.0.21 #8-pre-2.0 Fri Oct 4 17:24:44 EDT 1996 i586
% gcc -v
Reading specs from /usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/specs
gcc version 2.7.2.1
No changes were made to the source, and no interesting options were
given to configure. Current libc version is 5.4.7. File dates suggest
that gcc was compiled with libc 5.3.12.
The bad file blah.c (which is already processed by gcc -E):
-------------- snip, snip ----------------------------------------
# 1 "pst.c"
# 1 "/usr/include/stdio.h" 1 3
# 1 "/usr/include/features.h" 1 3
# 1 "/usr/include/sys/cdefs.h" 1 3
# 1 "/usr/include/features.h" 1 3
# 136 "/usr/include/features.h" 3
# 24 "/usr/include/sys/cdefs.h" 2 3
# 50 "/usr/include/sys/cdefs.h" 3
# 100 "/usr/include/sys/cdefs.h" 3
typedef long double __long_double_t;
# 128 "/usr/include/sys/cdefs.h" 3
# 134 "/usr/include/features.h" 2 3
# 31 "/usr/include/stdio.h" 2 3
# 1 "/usr/include/libio.h" 1 3
# 1 "/usr/include/_G_config.h" 1 3
typedef long _G_clock_t;
typedef unsigned short _G_dev_t;
typedef long int _G_fpos_t;
typedef unsigned short _G_gid_t;
typedef unsigned long _G_ino_t;
typedef unsigned short _G_mode_t;
typedef unsigned short _G_nlink_t;
typedef long _G_off_t;
typedef int _G_pid_t;
typedef int _G_ptrdiff_t;
typedef unsigned long _G_sigset_t;
typedef unsigned int _G_size_t;
typedef long _G_time_t;
typedef unsigned short _G_uid_t;
typedef long int _G_wchar_t;
typedef int _G_ssize_t;
typedef int _G_wint_t;
typedef void * _G_va_list;
typedef int _G_int8_t __attribute__((__mode__(__QI__)));
typedef unsigned int _G_uint8_t __attribute__((__mode__(__QI__)));
typedef int _G_int16_t __attribute__((__mode__(__HI__)));
typedef unsigned int _G_uint16_t __attribute__((__mode__(__HI__)));
typedef int _G_int32_t __attribute__((__mode__(__SI__)));
typedef unsigned int _G_uint32_t __attribute__((__mode__(__SI__)));
typedef int _G_int64_t __attribute__((__mode__(__DI__)));
typedef unsigned int _G_uint64_t __attribute__((__mode__(__DI__)));
# 30 "/usr/include/libio.h" 2 3
# 51 "/usr/include/libio.h" 3
# 63 "/usr/include/libio.h" 3
struct _IO_lock_t {
void *ptr;
short int field1;
short int field2;
};
struct _IO_jump_t; struct _IO_FILE;
struct _IO_marker {
struct _IO_marker *_next;
struct _IO_FILE *_sbuf;
int _pos;
# 176 "/usr/include/libio.h" 3
};
struct _IO_FILE {
int _flags;
char* _IO_read_ptr;
char* _IO_read_end;
char* _IO_read_base;
char* _IO_write_base;
char* _IO_write_ptr;
char* _IO_write_end;
char* _IO_buf_base;
char* _IO_buf_end;
char *_IO_save_base;
char *_IO_backup_base;
char *_IO_save_end;
struct _IO_marker *_markers;
struct _IO_FILE *_chain;
int _fileno;
int _blksize;
_G_off_t _offset;
unsigned short _cur_column;
char _unused;
char _shortbuf[1];
struct _IO_lock_t _IO_lock;
};
typedef struct _IO_FILE _IO_FILE;
struct _IO_FILE_plus;
extern struct _IO_FILE_plus _IO_stdin_, _IO_stdout_, _IO_stderr_;
extern int __underflow (_IO_FILE*) ;
extern int __uflow (_IO_FILE*) ;
extern int __overflow (_IO_FILE*, int) ;
extern int _IO_vfscanf (_IO_FILE*, const char*, _G_va_list , int*) ;
extern int _IO_vfprintf (_IO_FILE*, const char*, _G_va_list ) ;
extern _G_ssize_t _IO_padn (_IO_FILE *, int, _G_ssize_t ) ;
extern _G_size_t _IO_sgetn (_IO_FILE *, void*, _G_size_t ) ;
extern _G_fpos_t _IO_seekoff (_IO_FILE*, _G_off_t , int, int) ;
extern _G_fpos_t _IO_seekpos (_IO_FILE*, _G_fpos_t , int) ;
extern void _IO_free_backup_area (_IO_FILE*) ;
# 34 "/usr/include/stdio.h" 2 3
typedef _G_size_t size_t;
typedef struct _IO_FILE FILE;
typedef _G_fpos_t fpos_t;
extern FILE *stdin, *stdout, *stderr;
# 102 "/usr/include/stdio.h" 3
extern void clearerr (FILE*) ;
extern int fclose (FILE*) ;
extern int feof (FILE*) ;
extern int ferror (FILE*) ;
extern int fflush (FILE*) ;
extern int fgetc (FILE *) ;
extern int fgetpos (FILE* fp, fpos_t *pos) ;
extern char* fgets (char*, int, FILE*) ;
extern FILE* fopen (__const char*, __const char*) ;
extern int fprintf (FILE*, __const char* format, ...) ;
extern int fputc (int, FILE*) ;
extern int fputs (__const char *str, FILE *fp) ;
extern size_t fread (void*, size_t, size_t, FILE*) ;
extern FILE* freopen (__const char*, __const char*, FILE*) ;
extern int fscanf (FILE *fp, __const char* format, ...) ;
extern int fseek (FILE* fp, long int offset, int whence) ;
extern int fsetpos (FILE* fp, __const fpos_t *pos) ;
extern long int ftell (FILE* fp) ;
extern size_t fwrite (__const void*, size_t, size_t, FILE*) ;
extern int getc (FILE *) ;
extern int getchar (void) ;
extern char* gets (char*) ;
extern void perror (__const char *) ;
extern int printf (__const char* format, ...) ;
extern int putc (int, FILE *) ;
extern int putchar (int) ;
extern int puts (__const char *str) ;
extern int remove (__const char*) ;
extern int rename (__const char* _old, __const char* _new) ;
extern void rewind (FILE*) ;
extern int scanf (__const char* format, ...) ;
extern void setbuf (FILE*, char*) ;
extern void setlinebuf (FILE*) ;
extern void setbuffer (FILE*, char*, int) ;
extern int setvbuf (FILE*, char*, int mode, size_t size) ;
extern int sprintf (char*, __const char* format, ...) ;
extern int sscanf (__const char* string, __const char* format, ...) ;
extern FILE* tmpfile (void) ;
extern char* tmpnam (char*) ;
extern int ungetc (int c, FILE* fp) ;
extern int vfprintf (FILE *fp, char __const *fmt0, _G_va_list) ;
extern int vprintf (char __const *fmt, _G_va_list) ;
extern int vsprintf (char* string, __const char* format, _G_va_list) ;
extern int vfscanf (FILE*, __const char *, _G_va_list) ;
extern int vscanf (__const char *, _G_va_list) ;
extern int vsscanf (__const char *, __const char *, _G_va_list) ;
extern int getw (FILE*) ;
extern int putw (int, FILE*) ;
extern char* tempnam (__const char *__dir, __const char *__pfx) ;
extern int sys_nerr;
extern char *sys_errlist[];
extern int _sys_nerr;
extern char *_sys_errlist[];
extern void psignal (int __sig, __const char *__s) ;
extern _G_ssize_t getdelim (char **, size_t *, int, FILE*) ;
extern int snprintf (char *, size_t, const char *, ...) ;
extern int vsnprintf (char *, size_t, const char *, _G_va_list) ;
extern int asprintf (char **, const char *, ...) ;
extern int vasprintf (char **, const char *, _G_va_list) ;
extern FILE *fdopen (int, __const char *) ;
extern int fileno (FILE*) ;
extern FILE* popen (__const char*, __const char*) ;
extern int pclose (FILE*) ;
extern char *ctermid (char *__buf) ;
extern char *cuserid (char * __buf) ;
extern int __underflow (struct _IO_FILE*) ;
extern int __overflow (struct _IO_FILE*, int) ;
# 234 "/usr/include/stdio.h" 3
# 4 "pst.c" 2
# 1 "/usr/include/stdlib.h" 1 3
# 1 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/stddef.h" 1 3
# 17 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/stddef.h" 3
# 59 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/stddef.h" 3
# 129 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/stddef.h" 3
# 180 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/stddef.h" 3
typedef long int wchar_t;
# 288 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/stddef.h" 3
# 34 "/usr/include/stdlib.h" 2 3
# 1 "/usr/include/errno.h" 1 3
# 1 "/usr/include/linux/errno.h" 1 3
# 1 "/usr/include/asm/errno.h" 1 3
# 4 "/usr/include/linux/errno.h" 2 3
# 14 "/usr/include/linux/errno.h" 3
# 27 "/usr/include/errno.h" 2 3
extern int sys_nerr;
extern char *sys_errlist[];
extern int _sys_nerr;
extern char *_sys_errlist[];
extern void perror (__const char* __s) ;
extern char* strerror (int __errno) ;
extern int errno;
# 42 "/usr/include/stdlib.h" 2 3
typedef struct
{
int quot;
int rem;
} div_t;
typedef struct
{
long int quot;
long int rem;
} ldiv_t;
extern double atof (__const char *__nptr) ;
extern int atoi (__const char *__nptr) ;
extern long int atol (__const char *__nptr) ;
extern long long int atoq (__const char *__nptr) ;
extern float strtof (__const char *__nptr, char **__endptr) ;
extern double strtod (__const char *__nptr, char **__endptr) ;
extern __long_double_t strtold (__const char *__nptr, char **__endptr) ;
extern long int strtol (__const char *__nptr, char **__endptr,
int __base) ;
extern unsigned long int strtoul (__const char *__nptr,
char **__endptr, int __base) ;
extern long long int strtoq (__const char *__nptr, char **__endptr,
int __base) ;
extern unsigned long long int strtouq (__const char *__nptr,
char **__endptr, int __base) ;
extern double __strtod_internal (__const char *__nptr,
char **__endptr, int __group);
extern float __strtof_internal (__const char *__nptr, char **__endptr,
int __group);
extern __long_double_t __strtold_internal (__const char *__nptr,
char **__endptr, int __group);
extern long int __strtol_internal (__const char *__nptr, char **__endptr,
int __base, int __group);
extern unsigned long int __strtoul_internal (__const char *__nptr,
char **__endptr, int __base,
int __group);
extern long long int __strtoq_internal (__const char *__nptr, char **__endptr,
int __base, int __group);
extern unsigned long long int __strtouq_internal (__const char *__nptr,
char **__endptr, int __base,
int __group);
# 170 "/usr/include/stdlib.h" 3
extern int rand (void) ;
extern void srand (unsigned int __seed) ;
extern long int __random (void) ;
extern void __srandom (unsigned int __seed) ;
extern void * __initstate (unsigned int __seed, void * __statebuf,
size_t __statelen) ;
extern void * __setstate (void * __statebuf) ;
extern long int random (void) ;
extern void srandom (unsigned int __seed) ;
extern void * initstate (unsigned int __seed, void * __statebuf,
size_t __statelen) ;
extern void * setstate (void * __statebuf) ;
# 214 "/usr/include/stdlib.h" 3
extern void * malloc (size_t __size) ;
extern void * realloc (void * __ptr, size_t __size) ;
extern void * calloc (size_t __nmemb, size_t __size) ;
extern void free (void * __ptr) ;
extern void cfree (void * __ptr) ;
# 1 "/usr/include/alloca.h" 1 3
# 1 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/stddef.h" 1 3
# 17 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/stddef.h" 3
# 59 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/stddef.h" 3
# 129 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/stddef.h" 3
# 180 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/stddef.h" 3
# 256 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/stddef.h" 3
# 288 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/stddef.h" 3
# 24 "/usr/include/alloca.h" 2 3
extern void * __alloca (size_t __size) ;
# 234 "/usr/include/stdlib.h" 2 3
extern void * valloc (size_t __size) ;
extern void abort (void) ;
extern int atexit (void (*__func) (void)) ;
extern int on_exit (void (*__func) (int __status, void * __arg),
void * __arg) ;
extern void exit (int __status) ;
extern char *getenv (__const char *__name) ;
extern int putenv (__const char *__string) ;
extern int setenv (__const char *__name, __const char *__value,
int __replace) ;
extern int system (__const char *__command) ;
typedef int (*__compar_fn_t) (__const void * , __const void * ) ;
typedef __compar_fn_t comparison_fn_t;
extern void * bsearch (__const void * __key, __const void * __base,
size_t __nmemb, size_t __size,
__compar_fn_t __compar) ;
extern void qsort (void * __base, size_t __nmemb, size_t __size,
__compar_fn_t __compar) ;
# 314 "/usr/include/stdlib.h" 3
extern int abs (int __x) ;
extern long int labs (long int __x) ;
extern div_t div (int __numer, int __denom) ;
extern ldiv_t ldiv (long int __numer, long int __denom) ;
extern int mblen (__const char *__s, size_t __n) ;
extern int mbtowc (wchar_t * __pwc, __const char *__s, size_t __n) ;
extern int wctomb (char *__s, wchar_t __wchar) ;
extern size_t mbstowcs (wchar_t * __pwcs, __const char *__s, size_t __n) ;
extern size_t wcstombs (char *__s, __const wchar_t * __pwcs, size_t __n) ;
# 375 "/usr/include/stdlib.h" 3
extern char **environ;
extern char **__environ;
extern char* ecvt (double __value, size_t __ndigit, int *__decpt,
int *__sign) ;
extern char* fcvt (double __value, size_t __ndigit, int *__decpt,
int *__sign) ;
extern char* gcvt (double __value, size_t __ndigit, char *__buf) ;
extern double drand48 (void) ;
extern double erand48 (unsigned short int __xsubi[3]) ;
extern long int lrand48 (void) ;
extern long int nrand48 (unsigned short int __xsubi[3]) ;
extern long int mrand48 (void) ;
extern long int jrand48 (unsigned short int __xsubi[3]) ;
extern void srand48 (long int __seedval) ;
extern unsigned short int
*seed48 (unsigned short int __seed16v[3]) ;
extern void lcong48 (unsigned short int __param[7]) ;
extern int setenv (__const char *__name, __const char *__value,
int __overwrite) ;
extern void unsetenv (__const char *__name) ;
struct qelem {
struct qelem *q_forw;
struct qelem *q_back;
char q_data[1];
};
extern void insque (struct qelem *__elem, struct qelem *__prev) ;
extern void remque (struct qelem *__elem) ;
# 5 "pst.c" 2
# 1 "/usr/include/math.h" 1 3
extern double acos (double __x) ;
extern double asin (double __x) ;
extern double atan (double __x) __attribute__ ((const)) ;
extern double atan2 (double __y, double __x) __attribute__ ((const)) ;
extern double cos (double __x) __attribute__ ((const)) ;
extern double sin (double __x) __attribute__ ((const)) ;
extern double tan (double __x) __attribute__ ((const)) ;
extern double cosh (double __x) __attribute__ ((const)) ;
extern double sinh (double __x) __attribute__ ((const)) ;
extern double tanh (double __x) __attribute__ ((const)) ;
extern double acosh (double __x) ;
extern double asinh (double __x) ;
extern double atanh (double __x) ;
extern double exp (double __x) __attribute__ ((const)) ;
extern double frexp (double __x, int *__exp) ;
extern double ldexp (double __x, int __exp) ;
extern double log (double __x) ;
extern double log10 (double __x) ;
extern double expm1 (double __x) __attribute__ ((const)) ;
extern double log1p (double __x) ;
extern double modf (double __x, double *__iptr) ;
extern double pow (double __x, double __y) ;
extern double sqrt (double __x) ;
extern double cbrt (double __x) __attribute__ ((const)) ;
extern double ceil (double __x) __attribute__ ((const)) ;
extern double fabs (double __x) __attribute__ ((const)) ;
extern double floor (double __x) __attribute__ ((const)) ;
extern double fmod (double __x, double __y) __attribute__ ((const)) ;
extern int __isinf (double __value) __attribute__ ((const)) ;
extern int __isnan (double __value) __attribute__ ((const)) ;
extern int __finite (double __value) __attribute__ ((const)) ;
extern double __infnan (int __error) ;
extern long double __infnanl (int __error) ;
extern double __copysign (double __x,
double __y) __attribute__ ((const)) ;
extern __long_double_t __copysignl (__long_double_t __x,
__long_double_t __y )
__attribute__ ((const)) ;
extern double __rint (double __x) __attribute__ ((const)) ;
extern double rint (double __x) __attribute__ ((const)) ;
extern double hypot (double __x, double __y) __attribute__ ((const)) ;
extern int isinf (double __value) __attribute__ ((const)) ;
extern int isinfl (__long_double_t __value) __attribute__ ((const)) ;
extern int isnan (double __value) __attribute__ ((const)) ;
extern int isnanl (__long_double_t __value) __attribute__ ((const)) ;
extern int finite (double __value) __attribute__ ((const)) ;
extern double infnan (int __error) __attribute__ ((const)) ;
extern __long_double_t infnanl (int __error) __attribute__ ((const)) ;
extern double copysign (double __x,
double __y) __attribute__ ((const)) ;
extern __long_double_t copysignl (__long_double_t __x,
__long_double_t __y)
__attribute__ ((const)) ;
extern double drem (double __x, double __y) __attribute__ ((const)) ;
# 210 "/usr/include/math.h" 3
extern double pow2 (double __x) __attribute__ ((const)) ;
extern double pow10 (double __x) __attribute__ ((const)) ;
extern double erf (double __x) __attribute__ ((const)) ;
extern double erfc (double __x) __attribute__ ((const)) ;
extern double j0 (double __x) __attribute__ ((const)) ;
extern double j1 (double __x) __attribute__ ((const)) ;
extern double jn (int __n, double __x) __attribute__ ((const)) ;
extern double lgamma (double __x) ;
extern double y0 (double __x) __attribute__ ((const)) ;
extern double y1 (double __x) __attribute__ ((const)) ;
extern double yn (int __n, double __x) __attribute__ ((const)) ;
extern __long_double_t acosl (__long_double_t __x) ;
extern __long_double_t asinl (__long_double_t __x) ;
extern __long_double_t atanl (__long_double_t __x) ;
extern __long_double_t cosl (__long_double_t __x) ;
extern __long_double_t sinl (__long_double_t __x) ;
extern __long_double_t tanl (__long_double_t __x) ;
extern __long_double_t acoshl (__long_double_t __x) ;
extern __long_double_t asinhl (__long_double_t __x) ;
extern __long_double_t atanhl (__long_double_t __x) ;
extern __long_double_t coshl (__long_double_t __x) ;
extern __long_double_t sinhl (__long_double_t __x) ;
extern __long_double_t tanhl (__long_double_t __x) ;
extern __long_double_t expl (__long_double_t __x) ;
extern __long_double_t expm1l (__long_double_t __x) __attribute__ ((const)) ;
extern __long_double_t frexpl (__long_double_t __value, int *__exp) ;
extern __long_double_t ldexpl (__long_double_t __x, int __exp) ;
extern __long_double_t logl (__long_double_t __x) ;
extern __long_double_t log10l (__long_double_t __x) ;
extern __long_double_t modfl (__long_double_t __value, __long_double_t * __ip) ;
extern __long_double_t powl (__long_double_t __x, __long_double_t __y) ;
extern __long_double_t sqrtl (__long_double_t __x) ;
extern __long_double_t atan2l (__long_double_t __y, __long_double_t __x) ;
extern __long_double_t hypotl (__long_double_t __x, __long_double_t __y) __attribute__ ((const)) ;
extern __long_double_t erfl (__long_double_t __x) ;
extern __long_double_t erfcl (__long_double_t __x) ;
extern __long_double_t lgammal (__long_double_t __x) ;
extern __long_double_t j0l (__long_double_t __x) ;
extern __long_double_t y0l (__long_double_t __x) ;
extern __long_double_t j1l (__long_double_t __x) ;
extern __long_double_t y1l (__long_double_t __x) ;
extern __long_double_t jnl (int __n, __long_double_t __x) ;
extern __long_double_t ynl (int __n, __long_double_t __x) ;
extern __long_double_t cbrtl (__long_double_t __x) ;
extern __long_double_t log1pl (__long_double_t __x) ;
extern __long_double_t log2l (__long_double_t __x) ;
extern __long_double_t pow2l (__long_double_t __x) ;
extern __long_double_t pow10l (__long_double_t __x) ;
extern __long_double_t ceill (__long_double_t __x) __attribute__ ((const)) ;
extern __long_double_t fabsl (__long_double_t __x) __attribute__ ((const)) ;
extern __long_double_t floorl (__long_double_t __x) __attribute__ ((const)) ;
extern __long_double_t fmodl (__long_double_t __x,
__long_double_t __y) __attribute__ ((const)) ;
extern int __isinfl (__long_double_t __value) __attribute__ ((const)) ;
extern int __isnanl (__long_double_t __value) __attribute__ ((const)) ;
extern int signgam;
extern int signgaml;
# 1 "/usr/include/huge_val.h" 1 3
# 1 "/usr/include/endian.h" 1 3
# 1 "/usr/include/bytesex.h" 1 3
# 34 "/usr/include/endian.h" 2 3
# 27 "/usr/include/huge_val.h" 2 3
# 322 "/usr/include/math.h" 2 3
# 1 "/usr/include/nan.h" 1 3
# 86 "/usr/include/nan.h" 3
# 326 "/usr/include/math.h" 2 3
# 1 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/float.h" 1 3
union __convert_long_double {
unsigned __convert_long_double_i[4];
long double __convert_long_double_d;
};
# 329 "/usr/include/math.h" 2 3
# 1 "/usr/include/values.h" 1 3
# 110 "/usr/include/values.h" 3
# 183 "/usr/include/values.h" 3
# 330 "/usr/include/math.h" 2 3
# 1 "/usr/include/ieee754.h" 1 3
union ieee754_double
{
double d;
struct
{
unsigned int mantissa1:32;
unsigned int mantissa0:20;
unsigned int exponent:11;
unsigned int negative:1;
} ieee;
struct
{
unsigned int mantissa1:32;
unsigned int mantissa0:19;
unsigned int quiet_nan:1;
unsigned int exponent:11;
unsigned int negative:1;
} ieee_nan;
};
# 1 "/usr/include/i386/ieeefp.h" 1 3
union i387_float
{
float f;
struct
{
unsigned int mantissa:23;
unsigned int exponent:8;
unsigned int negative:1;
} i387;
struct
{
unsigned int mantissa:22;
unsigned int quiet_nan:1;
unsigned int exponent:8;
unsigned int negative:1;
} i387_nan;
};
# 69 "/usr/include/ieee754.h" 2 3
# 393 "/usr/include/math.h" 2 3
# 1 "/usr/include/ieee854.h" 1 3
union ieee854_double
{
long double d;
struct
{
unsigned int mantissa1:32;
unsigned int mantissa0:32;
unsigned int exponent:15;
unsigned int negative:1;
unsigned int empty:16;
} ieee;
struct
{
# 58 "/usr/include/ieee854.h" 3
unsigned int mantissa1:32;
unsigned int mantissa0:30;
unsigned int quiet_nan:1;
unsigned int one:1;
unsigned int exponent:15;
unsigned int negative:1;
unsigned int empty:16;
} ieee_nan;
};
# 394 "/usr/include/math.h" 2 3
extern __inline double __copysign (double __x,
double __y)
{
union ieee754_double *__ux = (union ieee754_double *) &__x;
union ieee754_double *__uy = (union ieee754_double *) &__y;
__ux->ieee.negative = __uy->ieee.negative;
return __x;
}
extern __inline __long_double_t __copysignl (__long_double_t __x, __long_double_t __y )
{
union ieee854_double *__ux = (union ieee854_double *) &__x;
union ieee854_double *__uy = (union ieee854_double *) &__y;
__ux->ieee.negative = __uy->ieee.negative;
return __x;
}
# 6 "pst.c" 2
# 1 "/usr/include/string.h" 1 3
# 1 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/stddef.h" 1 3
# 17 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/stddef.h" 3
# 59 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/stddef.h" 3
# 129 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/stddef.h" 3
# 180 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/stddef.h" 3
# 256 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/stddef.h" 3
# 288 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/stddef.h" 3
# 33 "/usr/include/string.h" 2 3
extern void * memmove (void * __dest, __const void * __src,
size_t __n) ;
extern void * __memccpy (void * __dest, __const void * __src,
int __c, size_t __n) ;
extern void * memccpy (void * __dest, __const void * __src,
int __c, size_t __n) ;
extern void * memset (void * __s, int __c, size_t __n) ;
extern void * memchr (__const void * __s, int __c, size_t __n) ;
extern char *strcpy (char *__dest, __const char *__src) ;
extern char *strncpy (char *__dest, __const char *__src, size_t __n) ;
extern char *strcat (char *__dest, __const char *__src) ;
extern char *strncat (char *__dest, __const char *__src, size_t __n) ;
extern int strcmp (__const char *__s1, __const char *__s2) ;
extern int strncmp (__const char *__s1, __const char *__s2, size_t __n) ;
extern int strcoll (__const char *__s1, __const char *__s2) ;
extern size_t strxfrm (char *__dest, __const char *__src, size_t __n) ;
extern char *strdup (__const char *__s) ;
extern char *strchr (__const char *__s, int __c) ;
extern char *strrchr (__const char *__s, int __c) ;
extern size_t strcspn (__const char *__s, __const char *__reject) ;
extern size_t strspn (__const char *__s, __const char *__accept) ;
extern char *strpbrk (__const char *__s, __const char *__accept) ;
extern char *strstr (__const char *__haystack, __const char *__needle) ;
extern char *strtok (char *__s, __const char *__delim) ;
extern void * memmem (__const void * __haystack,
size_t __haystacklen,
__const void * __needle,
size_t __needlelen) ;
extern size_t strlen (__const char *__s) ;
extern char *strerror (int __errnum) ;
extern char *index (__const char *__s, int __c) ;
extern char *rindex (__const char *__s, int __c) ;
# 149 "/usr/include/string.h" 3
extern void bcopy (__const void * __src, void * __dest, int __n) ;
extern void bzero (void * __s, int __n) ;
extern int bcmp (__const void * __s1, __const void * __s2, int __n) ;
extern int ffs (int __i) ;
extern int strcasecmp (__const char *__s1, __const char *__s2) ;
extern char *strsep (char **__stringp, __const char *__delim) ;
extern int strncasecmp (__const char *__s1, __const char *__s2,
size_t __n) ;
extern char *strsignal (int __sig) ;
extern char *stpcpy (char *__dest, __const char *__src) ;
extern char *__stpncpy (char *__dest, __const char *__src, size_t __n) ;
extern char *stpncpy (char *__dest, __const char *__src, size_t __n) ;
extern char *strfry (char *__string) ;
extern void * memfrob (void * __s, size_t __n) ;
extern void swab (__const void * __from, void * __to,
size_t __nbytes) ;
# 7 "pst.c" 2
# 1 "pst.h" 1
# 1 "types.h" 1
# 1 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/limits.h" 1 3
# 1 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/syslimits.h" 1 3
# 1 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/limits.h" 1 3
# 109 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/limits.h" 3
# 1 "/usr/include/limits.h" 1 3
# 1 "/usr/include/posix1_lim.h" 1 3
# 1 "/usr/include/linux/limits.h" 1 3
# 72 "/usr/include/posix1_lim.h" 2 3
# 30 "/usr/include/limits.h" 2 3
# 1 "/usr/include/posix2_lim.h" 1 3
# 34 "/usr/include/limits.h" 2 3
# 53 "/usr/include/limits.h" 3
# 115 "/usr/include/limits.h" 3
# 138 "/usr/include/limits.h" 3
# 112 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/limits.h" 2 3
# 7 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/syslimits.h" 2 3
# 11 "/usr/lib/gcc-lib/i586-unknown-linux/2.7.2.1/include/limits.h" 2 3
# 11 "types.h" 2
# 1 "fprintfll.h" 1
int fprintfll(FILE *fp, char *format, long long int val);
# 35 "types.h" 2
typedef long long int weight_t;
typedef double heap_weight;
# 86 "types.h"
typedef
struct arcSt
{
weight_t cap ;
struct nodeSt *head;
struct arcSt *rev;
struct arcSt *next;
struct arcSt *prev;
struct arcSt *s_next;
int s_cap;
double usage;
double cost;
}
arc;
typedef
struct nodeSt
{
arc *first;
arc *last;
# 129 "types.h"
unsigned int pr34scanned:1;
float age;
struct nodeSt *leader;
weight_t cap;
arc *auxArc;
heap_weight key;
int heap_pos;
int name;
weight_t capdown;
weight_t rho;
weight_t rhodown;
weight_t cutdown;
struct nodeSt *parent;
arc *s_first;
} node;
# 199 "types.h"
# 8 "pst.h" 2
typedef struct tedge
{
arc *a;
struct tedge *t_next;
} tedge;
typedef struct tree
{
int name;
double wt;
tedge **t_first;
tedge *tedge_alloc;
} tree;
typedef struct packing
{
double wt;
int k;
tree *trees;
double lambda;
int treealloc;
} *packing;
extern int packCnt;
packing pst_pack(node *root, int n, int m, int c, double epsilon, packing p);
void free_packing(packing p);
# 8 "pst.c" 2
# 1 "graphutil.h" 1
# 1 "memassert.h" 1
# 8 "graphutil.h" 2
# 56 "graphutil.h"
# 75 "graphutil.h"
extern weight_t minCap;
extern int currentN;
extern node *nodes,
*sentinelNode;
extern node **leaders,
**__leader_node;
extern arc *arcs,
*sentinel_arc;
extern int newMinCut;
extern float dtime;
extern int edgeScanCnt;
void printGraph(void);
void printCut(void);
void saveTrivialCut (node *v);
node *findLeader ( node *v );
void deleteExtras ( node *v );
void freegraph(void);
void parse(int *n_ad, int *m_ad);
# 9 "pst.c" 2
# 1 "heap.h" 1
typedef struct heap_st
{
long size;
node **node;
} *heap;
heap makeHeap( int n );
void clearHeap( heap h );
char nonEmptyH( heap h );
void increaseKey( heap h, node *node_i, heap_weight key_i );
void hInsert( heap h, node *node_i );
node *extractMax( heap h);
void freeHeap( heap h );
extern inline heap makeHeap( int n )
{
heap h;
{ if (( h = (heap)malloc(sizeof(struct heap_st)) )== ((void *)0) ) {fprintf(((_IO_FILE*)(&_IO_stderr_)) , "Memory exhausted at " "heap.h" ":%d " "h = (heap)malloc(sizeof(struct heap_st))" "\n", 42); exit(1); } } ;
h->size = 0;
{ if (( h->node = (node **)calloc(( n+1 ), sizeof(node*)) )== ((void *)0) ) {fprintf(((_IO_FILE*)(&_IO_stderr_)) , "Memory exhausted at " "heap.h" ":%d " "h->node = (node **)calloc(( n+1 ), sizeof(node*))" "\n", 44); exit(1); } } ;
return h;
}
extern inline void clearHeap( heap h )
{
h->size=0;
}
extern inline char nonEmptyH( heap h )
{
return h->size > 0;
}
extern inline void increaseKey( heap h, node *node_i, heap_weight key_i )
{
int current_pos, new_pos;
node *node_k;
for ( current_pos = node_i->heap_pos;
current_pos > 0;
current_pos = new_pos
)
{
new_pos = ( current_pos - 1 ) / 3 ;
node_k = h->node[new_pos];
if ( key_i <= node_k->key ) break;
{ h ->node[ current_pos ] = node_k ; node_k -> heap_pos = current_pos ;} ;
}
{ h ->node[ current_pos ] = node_i ; node_i -> heap_pos = current_pos ;} ;
}
extern inline void hInsert( heap h, node *node_i )
{
{ h ->node[ h->size ] = node_i ; node_i -> heap_pos = h->size ;} ;
h->size++;
increaseKey ( h, node_i, node_i->key );
}
extern inline node *extractMax( heap h)
{
node *node_0, *node_k;
int pos, new_pos, current_pos, last_pos;
heap_weight key_k, key_min;
node_0 = h->node[0];
node_0 -> heap_pos = -1 ;
h->size-- ;
if ( h->size > 0 )
{
node_k = h->node [ h->size ];
key_k = node_k -> key;
current_pos = 0;
while ( 1 )
{
new_pos = current_pos * 3 + 1;
if ( new_pos >= h->size ) break;
key_min = h->node[new_pos] -> key;
last_pos = new_pos + 3 ;
if ( last_pos > h->size ) last_pos = h->size;
for ( pos = new_pos + 1; pos < last_pos; pos ++ )
{
if ( h->node[pos] -> key > key_min )
{
new_pos = pos;
key_min = h->node[pos]->key;
}
}
if ( key_k >= key_min ) break;
{ h ->node[ current_pos ] = h->node[new_pos] ; h->node[new_pos] -> heap_pos = current_pos ;} ;
current_pos = new_pos;
}
{ h ->node[ current_pos ] = node_k ; node_k -> heap_pos = current_pos ;} ;
}
return node_0;
}
extern inline void freeHeap( heap h )
{
free(h->node);
free(h);
}
# 10 "pst.c" 2
# 1 "random.h" 1
void SetRandom(long seed);
long Random(long a, long b);
double DblUnitRandom(void);
void RandomPermute(int iMac, int rgi[ ]);
# 11 "pst.c" 2
double dfs(node *v);
double evalSigma(double sigma, double alpha);
static inline void AddTreeArc(tree *t, node *v, arc *a);
extern heap h;
int packCnt;
static packing ans;
static int C;
packing pst_pack(node *root, int n, int m, int c, double epsilon, packing ans2)
{
double lambda0;
double lambda;
double alpha;
double sigma;
double yb;
double yAx;
double Cy;
node *v;
arc *a;
tree *t, *tt1, tt2;
double tmp, newsigma, val, val2, omsigma, pwt;
double ts, eps, e, ep, em;
int i, iter=1;
ans = ans2;
if (ans == ((void *)0) )
{
{ if (( ans = (packing)malloc(sizeof(struct packing)) )== ((void *)0) ) {fprintf(((_IO_FILE*)(&_IO_stderr_)) , "Memory exhausted at " "pst.c" ":%d " "ans = (packing)malloc(sizeof(struct packing))" "\n", 70); exit(1); } } ;
{ if (( ans->trees = (tree *)malloc((c+1)*sizeof(tree)) )== ((void *)0) ) {fprintf(((_IO_FILE*)(&_IO_stderr_)) , "Memory exhausted at " "pst.c" ":%d " "ans->trees = (tree *)malloc((c+1)*sizeof(tree))" "\n", 71); exit(1); } } ;
for(i=0; i<c+1; i++)
{
{ if (( ans->trees[i].t_first = (struct tedge **)
malloc(n*sizeof(struct tedge*)) )== ((void *)0) ) {fprintf(((_IO_FILE*)(&_IO_stderr_)) , "Memory exhausted at " "pst.c" ":%d " "ans->trees[i].t_first = (struct tedge **) malloc(n*sizeof(struct tedge*))" "\n", 75); exit(1); } } ;
{ if (( ans->trees[i].tedge_alloc = (struct tedge *)
malloc(n*sizeof(struct tedge)) )== ((void *)0) ) {fprintf(((_IO_FILE*)(&_IO_stderr_)) , "Memory exhausted at " "pst.c" ":%d " "ans->trees[i].tedge_alloc = (struct tedge *) malloc(n*sizeof(struct tedge))" "\n", 77); exit(1); } } ;
ans->trees[i].name = i;
ans->trees[i].wt = 0;
}
ans->treealloc = c;
}
ans->k = 0;
if (c > ans->treealloc)
{
{ if (( ans->trees = (tree *)realloc(ans->trees, (c+1)*sizeof(tree)) )== ((void *)0) ) {fprintf(((_IO_FILE*)(&_IO_stderr_)) , "Memory exhausted at " "pst.c" ":%d " "ans->trees = (tree *)realloc(ans->trees, (c+1)*sizeof(tree))" "\n", 86); exit(1); } } ;
for(i=ans->treealloc+1; i<c+1; i++)
{
{ if (( ans->trees[i].t_first = (struct tedge **)
calloc(n, sizeof(struct tedge*)) )== ((void *)0) ) {fprintf(((_IO_FILE*)(&_IO_stderr_)) , "Memory exhausted at " "pst.c" ":%d " "ans->trees[i].t_first = (struct tedge **) calloc(n, sizeof(struct tedge*))" "\n", 90); exit(1); } } ;
{ if (( ans->trees[i].tedge_alloc = (struct tedge *)
malloc(n*sizeof(struct tedge)) )== ((void *)0) ) {fprintf(((_IO_FILE*)(&_IO_stderr_)) , "Memory exhausted at " "pst.c" ":%d " "ans->trees[i].tedge_alloc = (struct tedge *) malloc(n*sizeof(struct tedge))" "\n", 92); exit(1); } } ;
ans->trees[i].name = i;
ans->trees[i].wt = 0;
}
ans->treealloc = c;
}
C = c;
t = ans->trees;
memset(t->t_first, 0, n*sizeof(tedge *));
t->wt = c;
lambda=0;
for ( __leader_node=leaders; ( v =*__leader_node) != ((void *)0) ; __leader_node++)
{
for( a = v ->s_first; a != ((void *)0) ; a = a ->s_next)
{
a->cost = a->s_cap;
a->usage = 0;
}
v->key = - 1.79769313486231570e+308 ;
v->auxArc = ((void *)0) ;
hInsert(h, v);
}
root->key = 1.79769313486231570e+308 ;
increaseKey(h, root, 1.79769313486231570e+308 );
v = extractMax(h);
for( a = v ->s_first; a != ((void *)0) ; a = a ->s_next)
if (a->cost > a->head->key)
{
a->head->key = a->cost;
increaseKey(h, a->head, a->cost);
a->head->auxArc = (( a )->rev) ;
}
while (nonEmptyH(h))
{
v=extractMax(h);
if (v->key == - 1.79769313486231570e+308 )
{
printf("pst given disconnected graph\n");
ans->lambda = 1.79769313486231570e+308 ;
clearHeap(h);
return ans;
}
AddTreeArc(t, v->auxArc->head, (( v->auxArc )->rev) );
tmp = c/(double)v->auxArc->s_cap;
v->auxArc->usage = tmp;
(( v->auxArc )->rev) ->usage = tmp;
if (tmp > lambda) lambda = tmp;
v->key = 1.79769313486231570e+308 ;
for( a = v ->s_first; a != ((void *)0) ; a = a ->s_next)
if (a->cost > a->head->key)
{
a->head->key = a->cost;
increaseKey(h, a->head, a->cost);
a->head->auxArc = (( a )->rev) ;
}
}
lambda0 = lambda;
ans->k++;
while (1)
{
alpha = 4*log(2*m/epsilon)/(lambda0*epsilon);
sigma = epsilon/(4*alpha*c);
do
{
iter++;
yAx = 0; yb = 0; Cy = 0;
for ( __leader_node=leaders; ( v =*__leader_node) != ((void *)0) ; __leader_node++)
{
for( a = v ->s_first; a != ((void *)0) ; a = a ->s_next)
if ((( v )->name) > (( a->head )->name) )
{
a->cost = exp(alpha*a->usage);
yb += a->cost;
yAx += a->cost*a->usage;
a->cost = -a->cost;
(( a )->rev) ->cost = a->cost;
}
v->key = - 1.79769313486231570e+308 ;
v->auxArc = ((void *)0) ;
hInsert(h, v);
}
t = ans->trees+ans->treealloc;
memset(t->t_first, 0, n*sizeof(tedge *));
root->key = 0;
increaseKey(h, root, 0);
v = extractMax(h);
for( a = v ->s_first; a != ((void *)0) ; a = a ->s_next)
if (a->cost > a->head->key)
{
a->head->key = a->cost;
increaseKey(h, a->head, a->cost);
a->head->auxArc = (( a )->rev) ;
}
while (nonEmptyH(h))
{
v=extractMax(h);
AddTreeArc(t, v->auxArc->head, (( v->auxArc )->rev) );
Cy -= v->auxArc->cost*c/(double)v->auxArc->s_cap;
v->key = 0;
for( a = v ->s_first; a != ((void *)0) ; a = a ->s_next)
if (a->cost > a->head->key)
{
a->head->key = a->cost;
increaseKey(h, a->head, a->cost);
a->head->auxArc = (( a )->rev) ;
}
}
# 231 "pst.c"
newsigma = sigma;
do
{
ts = newsigma;
eps = .001*newsigma;
e = evalSigma(newsigma, alpha);
ep = evalSigma(newsigma+eps, alpha);
em = evalSigma(newsigma-eps, alpha);
newsigma -= eps*(ep-e)/(ep+em-2*e);
ts /= newsigma;
} while ( (ts < .999|| ts > 1.001));
if (newsigma < sigma) newsigma = sigma;
for(newsigma=sigma; newsigma<=1; newsigma+=sigma)
printf("%.3e\n", evalSigma(newsigma, alpha);
return ans;
omsigma = 1-newsigma;
lambda *= omsigma;
t->wt = c*newsigma;
for ( __leader_node=leaders; ( v =*__leader_node) != ((void *)0) ; __leader_node++)
for( a = v ->s_first; a != ((void *)0) ; a = a ->s_next)
if ((( v )->name) > (( a->head )->name) )
{
a->usage *= omsigma;
if (v->auxArc == a || a->head->auxArc == (( a )->rev) )
{
tmp = c/(double)a->s_cap*newsigma;
a->usage += tmp;
if (a->usage > lambda) lambda = a->usage;
}
(( a )->rev) ->usage = a->usage;
}
pwt = c;
tt1 = ans->trees+ans->treealloc;
for( t = ans ->trees; t - ans ->trees< ans ->k; t ++)
{
t->wt *= omsigma;
tmp = DblUnitRandom();
if (tmp < tt1->wt/pwt)
{
tt2 = *t;
*t = *tt1;
*tt1 = tt2;
}
pwt -= t->wt;
}
if (ans->k < c)
{
tt2 = *(ans->trees+ans->k);
*(ans->trees+ans->k) = *tt1;
*tt1 = tt2;
ans->k++;
}
if ((yAx-Cy) <= epsilon*(yAx+lambda*yb))
{
ans->lambda = lambda;
printf("c pst iters: %d lambda: %f\n", iter, lambda);
return ans;
}
} while(2*lambda > lambda0);
}
return ((void *)0) ;
}
void free_packing(packing p)
{
int i;
for(i=0; i<p->treealloc+1; i++)
{
free(p->trees[i].t_first);
free(p->trees[i].tedge_alloc);
}
free(p->trees);
free(p);
}
static inline void AddTreeArc(tree *t, node *v, arc *a)
{
tedge *e = t->tedge_alloc+ (( a->head )->name) ;
e->a = a;
e->t_next = t->t_first[(( v )->name) ];
t->t_first[(( v )->name) ] = e;
}
double evalSigma(double sigma, double alpha)
{
double omsigma = 1-sigma;
double cost = 0;
double tmp;
node *v;
arc *a;
for ( __leader_node=leaders; ( v =*__leader_node) != ((void *)0) ; __leader_node++)
for( a = v ->s_first; a != ((void *)0) ; a = a ->s_next)
if ((( v )->name) > (( a->head )->name) )
{
tmp = a->usage*omsigma;
if (v->auxArc == a || a->head->auxArc == (( a )->rev) )
tmp += C/(double)a->s_cap*sigma;
cost += exp(alpha*tmp);
}
return cost;
}
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads