1 /****************************************************************************/ 2 /* */ 3 /* This file is part of CONCORDE */ 4 /* */ 5 /* (c) Copyright 1995--1999 by David Applegate, Robert Bixby, */ 6 /* Vasek Chvatal, and William Cook */ 7 /* */ 8 /* Permission is granted for academic research use. For other uses, */ 9 /* contact the authors for licensing options. */ 10 /* */ 11 /* Use at your own risk. We make no guarantees about the */ 12 /* correctness or usefulness of this code. */ 13 /* */ 14 /****************************************************************************/ 15 16 /****************************************************************************/ 17 /****************************************************************************/ 18 /* */ 19 /* PROTOTYPES FOR FILES IN UTIL */ 20 /* */ 21 /****************************************************************************/ 22 /****************************************************************************/ 23 24 /****************************************************************************/ 25 /* */ 26 /* EXPORTED FUNCTIONS: */ 27 /* */ 28 /* CC_SAFE_MALLOC(nnum,type) */ 29 /* int nnum (the number of objects to be malloced) */ 30 /* data type (the sort of objects to be malloced) */ 31 /* RETURNS a pointer to the allocated space. If out of memory, */ 32 /* it prints an error message and returns NULL. */ 33 /* */ 34 /* CC_FREE(object,type) */ 35 /* type *object (pointer to previously allocated space) */ 36 /* data type (the sort of object) */ 37 /* ACTION: frees the memory and sets the object to NULL. */ 38 /* */ 39 /* CC_IFFREE(object,type) */ 40 /* type *object (pointer to previously allocated space) */ 41 /* data type (the sort of object) */ 42 /* ACTION: if *object is not NULL, frees the memory and sets */ 43 /* the object to NULL. */ 44 /* */ 45 /* CC_PTR_ALLOC_ROUTINE (type, functionname, chunklist, freelist) */ 46 /* data type (the sort of objects) */ 47 /* string functionname (the generated function) */ 48 /* CCbigchunkptr *chunklist (used to accumulate bigchunks) */ 49 /* type *freelist (used for the linked list of objects) */ 50 /* ACTION: Generates a function ("functionname") that returns */ 51 /* (type *) objects, keeping the free ones on freelist */ 52 /* and getting its space from calls to */ 53 /* CCutil_bigchunkalloc. */ 54 /* */ 55 /* CC_PTR_FREE_ROUTINE (type, functionname, freelist) */ 56 /* Parameters as above. */ 57 /* ACTION: Generates a function that adds an object to the */ 58 /* freelist. */ 59 /* */ 60 /* CC_PTR_FREE_LIST_ROUTINE (type, functionname, freefunction) */ 61 /* Parameters defined as above, with freefunction the function */ 62 /* generated by CC_PTR_FREE_ROUTINE. */ 63 /* ACTION: Generates a function to free a linked list of */ 64 /* objects using calls to freefunction. */ 65 /* */ 66 /* CC_PTR_FREE_WORLD_ROUTINE (type, functionname, chunklist, freelist) */ 67 /* Parameters defined as above. */ 68 /* ACTION: Generates a function that returns all of the */ 69 /* memory used in the CC_PTR_ALLOC_ROUTINE allocations */ 70 /* back to the global supply of CCbigchunkptrs. */ 71 /* */ 72 /* CC_PTR_LEAKS_ROUTINE (type, name, chunklist, freelist, field, */ 73 /* fieldtype) */ 74 /* As above, with "field" the name of a "fieldtype" field in the */ 75 /* object type that can be set to 0 or to 1. */ 76 /* ACTION: Generates a function that checks to see that we have */ 77 /* not leaked any of the objects. */ 78 /* */ 79 /* CC_PTR_STATUS_ROUTINE (type, name, chunklist, freelist) */ 80 /* ACTION: Like LEAKS, but does not check for duplicates (and so */ 81 /* does not corrupt the objects). */ 82 /* */ 83 /* NOTES: */ 84 /* These routines use the functions in allocrus.c. The PTR macros */ 85 /* generate the functions for allocating objects for linked lists. They */ 86 /* get their raw memory from the bigchunk supply, so foo_free_world */ 87 /* (generated by CC_PTR_FREE_WORLD_ROUTINE) should be called for each */ 88 /* type of linked object "foo" when closing down the local memory. */ 89 /* To use these functions, put the macros near the top of the file */ 90 /* before any calls to the functions (since the macros also write the */ 91 /* function prototypes). If you use CC_PTR_FREE_LIST_ROUTINE for foo, */ 92 /* you must also use CC_PTR_FREE_ROUTINE, and */ 93 /* CC_PTR_FREE_LIST_ROUTINE must be listed after CC_PTR_FREE_ROUTINE */ 94 /* (to get the prototype). */ 95 /* */ 96 /****************************************************************************/ 97 98 #ifndef __UTIL_H 99 #define __UTIL_H 100 101 #include "machdefs.h" 102 103 #define CCutil_MAXDOUBLE (1e30) 104 #define CCutil_MAXINT (2147483647) 105 106 #define CCcheck_rval(rval,msg) { \ 107 if ((rval)) { \ 108 fprintf (stderr, "%s\n", (msg)); \ 109 goto CLEANUP; \ 110 } \ 111 } 112 113 #define CCcheck_NULL(item,msg) { \ 114 if ((!item)) { \ 115 fprintf (stderr, "%s\n", (msg)); \ 116 rval = 1; \ 117 goto CLEANUP; \ 118 } \ 119 } 120 121 122 #define CC_SBUFFER_SIZE (4000) 123 #define CC_SFNAME_SIZE (32) 124 125 typedef struct CC_SFILE { 126 int status; 127 int desc; 128 int type; 129 int chars_in_buffer; 130 int current_buffer_char; /* only used for reading */ 131 int bits_in_last_char; /* writing: number of empty bits in 132 * buffer[chars_in_buffer]; 133 * reading: number of full bits in 134 * buffer[?] */ 135 int pos; 136 char fname[CC_SFNAME_SIZE]; 137 char hname[CC_SFNAME_SIZE]; 138 unsigned char buffer[CC_SBUFFER_SIZE]; 139 } CC_SFILE; 140 141 #ifdef CC_NETREADY 142 typedef struct CC_SPORT { 143 unsigned short port; 144 int t; 145 } CC_SPORT; 146 #endif /* CC_NETREADY */ 147 148 typedef struct CCrandstate { 149 int a; 150 int b; 151 int arr[55]; 152 } CCrandstate; 153 154 /****************************************************************************/ 155 /* */ 156 /* allocrus.c */ 157 /* */ 158 /****************************************************************************/ 159 160 /****************************************************************************/ 161 /* */ 162 /* MEMORY ALLOCATION MACROS */ 163 /* */ 164 /* TSP CODE */ 165 /* */ 166 /* */ 167 /* Written by: Applegate, Bixby, Chvatal, and Cook */ 168 /* Date: February 24, 1995 (cofeb24) */ 169 /* */ 170 /* */ 171 /****************************************************************************/ 172 173 #define CC_SAFE_MALLOC(nnum,type) \ 174 (type *) CCutil_allocrus (((size_t) (nnum)) * sizeof (type)) 175 176 #define CC_FREE(object,type) { \ 177 CCutil_freerus ((void *) (object)); \ 178 object = (type *) NULL; \ 179 } 180 181 #define CC_IFFREE(object,type) { \ 182 if ((object)) CC_FREE ((object),type); \ 183 } 184 185 #define CC_PTRWORLD_ALLOC_ROUTINE(type, ptr_alloc_r, ptr_bulkalloc_r) \ 186 \ 187 static int ptr_bulkalloc_r (CCptrworld *world, int nalloc) \ 188 { \ 189 CCbigchunkptr *bp; \ 190 int i; \ 191 int count = CC_BIGCHUNK / sizeof ( type ); \ 192 type *p; \ 193 \ 194 while (nalloc > 0) { \ 195 bp = CCutil_bigchunkalloc (); \ 196 if (bp == (CCbigchunkptr *) NULL) { \ 197 fprintf (stderr, "ptr alloc failed\n"); \ 198 return 1; \ 199 } \ 200 bp->next = world->chunklist ; \ 201 world->chunklist = bp; \ 202 \ 203 p = ( type * ) bp->this_one; \ 204 for (i=count-2; i>=0; i--) { \ 205 p[i].next = &p[i+1]; \ 206 } \ 207 p[count - 1].next = (type *) world->freelist; \ 208 world->freelist = (void *) p; \ 209 nalloc -= count; \ 210 } \ 211 return 0; \ 212 } \ 213 \ 214 static type *ptr_alloc_r (CCptrworld *world) \ 215 { \ 216 type *p; \ 217 \ 218 if (world->freelist == (void *) NULL) { \ 219 if (ptr_bulkalloc_r (world, 1)) { \ 220 fprintf (stderr, "ptr alloc failed\n"); \ 221 return ( type * ) NULL; \ 222 } \ 223 } \ 224 p = (type *) world->freelist ; \ 225 world->freelist = (void *) p->next; \ 226 \ 227 return p; \ 228 } 229 230 #define CC_PTRWORLD_FREE_ROUTINE(type, ptr_free_r) \ 231 \ 232 static void ptr_free_r (CCptrworld *world, type *p) \ 233 { \ 234 p->next = (type *) world->freelist ; \ 235 world->freelist = (void *) p; \ 236 } 237 238 #define CC_PTRWORLD_LISTADD_ROUTINE(type, entrytype, ptr_listadd_r, ptr_alloc_r) \ 239 \ 240 static int ptr_listadd_r (type **list, entrytype x, CCptrworld *world) \ 241 { \ 242 if (list != (type **) NULL) { \ 243 type *p = ptr_alloc_r (world); \ 244 \ 245 if (p == (type *) NULL) { \ 246 fprintf (stderr, "ptr list add failed\n"); \ 247 return 1; \ 248 } \ 249 p->this = x; \ 250 p->next = *list; \ 251 *list = p; \ 252 } \ 253 return 0; \ 254 } 255 256 #define CC_PTRWORLD_LISTFREE_ROUTINE(type, ptr_listfree_r, ptr_free_r) \ 257 \ 258 static void ptr_listfree_r (CCptrworld *world, type *p) \ 259 { \ 260 type *next; \ 261 \ 262 while (p != (type *) NULL) { \ 263 next = p->next; \ 264 ptr_free_r (world, p); \ 265 p = next; \ 266 } \ 267 } 268 269 #define CC_PTRWORLD_LEAKS_ROUTINE(type, ptr_leaks_r, field, fieldtype) \ 270 \ 271 static int ptr_leaks_r (CCptrworld *world, int *total, int *onlist) \ 272 { \ 273 int count = CC_BIGCHUNK / sizeof ( type ); \ 274 int duplicates = 0; \ 275 type * p; \ 276 CCbigchunkptr *bp; \ 277 \ 278 *total = 0; \ 279 *onlist = 0; \ 280 \ 281 for (bp = world->chunklist ; bp; bp = bp->next) \ 282 (*total) += count; \ 283 \ 284 for (p = (type *) world->freelist ; p; p = p->next) { \ 285 (*onlist)++; \ 286 p-> field = ( fieldtype ) 0; \ 287 } \ 288 for (p = (type *) world->freelist ; p; p = p->next) { \ 289 if ((unsigned long) p-> field == (unsigned long) (size_t) 1) \ 290 duplicates++; \ 291 else \ 292 p-> field = ( fieldtype ) (size_t) 1; \ 293 } \ 294 if (duplicates) { \ 295 fprintf (stderr, "WARNING: %d duplicates on ptr free list \n", \ 296 duplicates); \ 297 } \ 298 return *total - *onlist; \ 299 } 300 301 #define CC_PTRWORLD_ROUTINES(type, ptr_alloc_r, ptr_bulkalloc_r, ptr_free_r) \ 302 CC_PTRWORLD_ALLOC_ROUTINE (type, ptr_alloc_r, ptr_bulkalloc_r) \ 303 CC_PTRWORLD_FREE_ROUTINE (type, ptr_free_r) 304 305 #define CC_PTRWORLD_LIST_ROUTINES(type, entrytype, ptr_alloc_r, ptr_bulkalloc_r, ptr_free_r, ptr_listadd_r, ptr_listfree_r) \ 306 CC_PTRWORLD_ROUTINES (type, ptr_alloc_r, ptr_bulkalloc_r, ptr_free_r) \ 307 CC_PTRWORLD_LISTADD_ROUTINE (type, entrytype, ptr_listadd_r, ptr_alloc_r) \ 308 CC_PTRWORLD_LISTFREE_ROUTINE (type, ptr_listfree_r, ptr_free_r) 309 310 #define CC_BIGCHUNK ((int) ((1<<16) - sizeof (CCbigchunkptr) - 16)) 311 312 struct CCbigchunk; 313 314 typedef struct CCbigchunkptr { 315 void *this_one; 316 struct CCbigchunk *this_chunk; 317 struct CCbigchunkptr *next; 318 } CCbigchunkptr; 319 320 321 typedef struct CCptrworld { 322 int refcount; 323 void *freelist; 324 CCbigchunkptr *chunklist; 325 } CCptrworld; 326 327 328 329 void 330 *CCutil_allocrus (size_t size), 331 *CCutil_reallocrus (void *ptr, size_t size), 332 CCutil_freerus (void *p), 333 CCutil_bigchunkfree (CCbigchunkptr *bp), 334 CCptrworld_init (CCptrworld *world), 335 CCptrworld_add (CCptrworld *world), 336 CCptrworld_delete (CCptrworld *world); 337 338 int 339 CCutil_reallocrus_scale (void **pptr, int *pnnum, int count, double scale, 340 size_t size), 341 CCutil_reallocrus_count (void **pptr, int count, size_t size); 342 343 CCbigchunkptr 344 *CCutil_bigchunkalloc (void); 345 346 347 348 349 /****************************************************************************/ 350 /* */ 351 /* bgetopt.c */ 352 /* */ 353 /****************************************************************************/ 354 355 356 int 357 CCutil_bix_getopt (int argc, char **argv, const char *def, int *p_optind, 358 char **p_optarg); 359 360 361 #define CC_BIX_GETOPT_UNKNOWN -3038 362 363 364 365 /****************************************************************************/ 366 /* */ 367 /* dheaps_i.c */ 368 /* */ 369 /****************************************************************************/ 370 371 typedef struct CCdheap { 372 double *key; 373 int *entry; 374 int *loc; 375 int total_space; 376 int size; 377 } CCdheap; 378 379 380 void 381 CCutil_dheap_free (CCdheap *h), 382 CCutil_dheap_delete (CCdheap *h, int i), 383 CCutil_dheap_changekey (CCdheap *h, int i, double newkey); 384 385 int 386 CCutil_dheap_init (CCdheap *h, int k), 387 CCutil_dheap_resize (CCdheap *h, int newsize), 388 CCutil_dheap_findmin (CCdheap *h), 389 CCutil_dheap_deletemin (CCdheap *h), 390 CCutil_dheap_insert (CCdheap *h, int i); 391 392 393 394 /****************************************************************************/ 395 /* */ 396 /* edgeutil.c */ 397 /* */ 398 /****************************************************************************/ 399 400 typedef struct CCelist { 401 int ecount; 402 int *ends; 403 } CCelist; 404 405 typedef struct CCelistl { 406 int ecount; 407 int *ends; 408 int *len; 409 } CCelistl; 410 411 typedef struct CCelistw { 412 int ecount; 413 int *ends; 414 double *weight; 415 } CCelistw; 416 417 typedef struct CCelistlw { 418 int ecount; 419 int *ends; 420 int *len; 421 double *weight; 422 } CCelistlw; 423 424 void 425 CCelist_init (CCelist *elist), 426 CCelistl_init (CCelistl *elist), 427 CCelistw_init (CCelistw *elist), 428 CCelistlw_init (CCelistlw *elist), 429 CCelist_free (CCelist *elist), 430 CCelistl_free (CCelistl *elist), 431 CCelistw_free (CCelistw *elist), 432 CCelistlw_free (CCelistlw *elist); 433 434 int 435 CCelist_alloc (CCelist *elist, int ecount), 436 CCelistl_alloc (CCelistl *elist, int ecount), 437 CCelistw_alloc (CCelistw *elist, int ecount), 438 CCelistlw_alloc (CCelistlw *elist, int ecount), 439 CCutil_edge_to_cycle (int ncount, int *elist, int *yesno, int *cyc); 440 441 442 443 444 445 /****************************************************************************/ 446 /* */ 447 /* edgelen.c */ 448 /* */ 449 /****************************************************************************/ 450 451 /****************************************************************************/ 452 /* */ 453 /* Before defining CCUTIL_EDGELEN_FUNCTIONPTR, read the notes at the top */ 454 /* of edgelen.c, and carefully consider the consequences. You probably */ 455 /* do not want CCUTIL_EDGELEN_FUNCTIONPTR defined. */ 456 /* */ 457 /****************************************************************************/ 458 459 #undef CCUTIL_EDGELEN_FUNCTIONPTR 460 461 typedef struct CCdata_user { 462 double *x; 463 double *y; 464 } CCdata_user; 465 466 typedef struct CCdata_rhvector { 467 int dist_00; 468 int dist_01; 469 int dist_02; 470 int dist_12; 471 int dist_22; 472 double p; 473 int rhlength; 474 char *space; 475 char **vectors; 476 } CCdata_rhvector; 477 478 typedef struct CCdatagroup { 479 int (*edgelen) (int i, int j, struct CCdatagroup *dat); 480 double *x; 481 double *y; 482 double *z; 483 int **adj; 484 int *adjspace; 485 int **len; 486 int *lenspace; 487 int *degree; 488 int norm; 489 int dsjrand_param; 490 int default_len; /* for edges not in sparse graph */ 491 int sparse_ecount; /* number of edges in sparse graph */ 492 double gridsize; /* for toroidal norm */ 493 double dsjrand_factor; 494 CCdata_rhvector rhdat; 495 CCdata_user userdat; 496 int ndepot; /* used with the subdivision code */ 497 int orig_ncount; /* just ncount-ndepot */ 498 int *depotcost; /* cost from each node to the depot */ 499 int *orig_names; /* the nodes names from full problem */ 500 } CCdatagroup; 501 502 503 504 #ifdef CCUTIL_EDGELEN_FUNCTIONPTR 505 extern int 506 (*CCutil_dat_edgelen) (int i, int j, CCdatagroup *dat); 507 #else /* CCUTIL_EDGELEN_FUNCTIONPTR */ 508 int 509 CCutil_dat_edgelen (int i, int j, CCdatagroup *dat); 510 #endif /* CCUTIL_EDGELEN_FUNCTIONPTR */ 511 512 int 513 CCutil_dat_setnorm (CCdatagroup *dat, int norm); 514 515 void 516 CCutil_dat_getnorm (CCdatagroup *dat, int *norm), 517 CCutil_dsjrand_init (CCdatagroup *dat, int maxdist, int seed), 518 CCutil_init_datagroup (CCdatagroup *dat), 519 CCutil_freedatagroup (CCdatagroup *dat); 520 521 522 #define CC_KD_NORM_TYPE 128 /* Kdtrees work */ 523 #define CC_X_NORM_TYPE 256 /* Old nearest works */ 524 #define CC_JUNK_NORM_TYPE 512 /* Nothing works */ 525 526 #define CC_D2_NORM_SIZE 1024 /* x,y coordinates */ 527 #define CC_D3_NORM_SIZE 2048 /* x,y,z coordinates */ 528 #define CC_MATRIX_NORM_SIZE 4096 /* adj matrix */ 529 530 #define CC_NORM_BITS (CC_KD_NORM_TYPE | CC_X_NORM_TYPE | \ 531 CC_JUNK_NORM_TYPE) 532 #define CC_NORM_SIZE_BITS (CC_D2_NORM_SIZE | CC_D3_NORM_SIZE | \ 533 CC_MATRIX_NORM_SIZE) 534 535 #define CC_MAXNORM (0 | CC_KD_NORM_TYPE | CC_D2_NORM_SIZE) 536 #define CC_EUCLIDEAN_CEIL (1 | CC_KD_NORM_TYPE | CC_D2_NORM_SIZE) 537 #define CC_EUCLIDEAN (2 | CC_KD_NORM_TYPE | CC_D2_NORM_SIZE) 538 #define CC_EUCLIDEAN_3D (3 | CC_X_NORM_TYPE | CC_D3_NORM_SIZE) 539 #define CC_USER (4 | CC_JUNK_NORM_TYPE | 0) 540 #define CC_ATT (5 | CC_X_NORM_TYPE | CC_D2_NORM_SIZE) 541 #define CC_GEOGRAPHIC (6 | CC_X_NORM_TYPE | CC_D2_NORM_SIZE) 542 #define CC_MATRIXNORM (7 | CC_JUNK_NORM_TYPE | CC_MATRIX_NORM_SIZE) 543 #define CC_DSJRANDNORM (8 | CC_JUNK_NORM_TYPE | 0) 544 #define CC_CRYSTAL (9 | CC_X_NORM_TYPE | CC_D3_NORM_SIZE) 545 #define CC_SPARSE (10 | CC_JUNK_NORM_TYPE | 0) 546 #define CC_RHMAP1 (11 | CC_JUNK_NORM_TYPE | 0) 547 #define CC_RHMAP2 (12 | CC_JUNK_NORM_TYPE | 0) 548 #define CC_RHMAP3 (13 | CC_JUNK_NORM_TYPE | 0) 549 #define CC_RHMAP4 (14 | CC_JUNK_NORM_TYPE | 0) 550 #define CC_RHMAP5 (15 | CC_JUNK_NORM_TYPE | 0) 551 #define CC_EUCTOROIDAL (16 | CC_JUNK_NORM_TYPE | CC_D2_NORM_SIZE) 552 #define CC_GEOM (17 | CC_X_NORM_TYPE | CC_D2_NORM_SIZE) 553 #define CC_MANNORM (18 | CC_KD_NORM_TYPE | CC_D2_NORM_SIZE) 554 #define CC_SUBDIVISION (99 | CC_JUNK_NORM_TYPE | 0) 555 556 #define CC_GEOGRAPHIC_SCALE (6378.388 * 3.14 / 180.0) /* see edgelen.c */ 557 #define CC_GEOM_SCALE (6378388.0 * 3.14 / 180.0) /* see edgelen.c */ 558 #define CC_ATT_SCALE (.31622) /* sqrt(1/10) */ 559 560 /* Distances CC_RHMAP1 through CC_RHMAP5 are for an application to */ 561 /* radiation hybrid mapping in genetics, explained in: Agarwala R, */ 562 /* Applegate DL, Maglott D, Schuler GD, Schaffer AA: A Fast and Scalable */ 563 /* Radiation Hybrid Map Construction and Integration Strategy. Genome */ 564 /* Research, 10:350-364, 2000. The correspondence to the distance function */ 565 /* terms used in that paper is: CC_RMAP1 (weighted_ocb), CC_RHMAP2 */ 566 /* (normalized_mle), CC_RHMAP3 (base_mle), CC_RHMAP4 (extended_mle), */ 567 /* CC_RHMAP5 (normalized_ocb) */ 568 569 /* For X-NORMS, scales are such that |x[i] - x[j]| * scale <= edgelen(i,j). */ 570 /* Geographic is slightly off, since the fractional part of x[i] is really */ 571 /* really minutes, not fractional degrees. */ 572 573 574 575 576 /****************************************************************************/ 577 /* */ 578 /* edgemap.c */ 579 /* */ 580 /****************************************************************************/ 581 582 typedef struct CCutil_edgeinf { 583 int ends[2]; 584 int val; 585 struct CCutil_edgeinf *next; 586 } CCutil_edgeinf; 587 588 typedef struct CCutil_edgehash { 589 CCutil_edgeinf **table; 590 CCptrworld edgeinf_world; 591 unsigned int size; 592 unsigned int mult; 593 } CCutil_edgehash; 594 595 596 int 597 CCutil_edgehash_init (CCutil_edgehash *h, int size), 598 CCutil_edgehash_add (CCutil_edgehash *h, int end1, int end2, int val), 599 CCutil_edgehash_set (CCutil_edgehash *h, int end1, int end2, int val), 600 CCutil_edgehash_del (CCutil_edgehash *h, int end1, int end2), 601 CCutil_edgehash_find (CCutil_edgehash *h, int end1, int end2, int *val), 602 CCutil_edgehash_getall (CCutil_edgehash *h, int *ecount, int **elist, 603 int **elen); 604 605 void 606 CCutil_edgehash_delall (CCutil_edgehash *h), 607 CCutil_edgehash_free (CCutil_edgehash *h); 608 609 610 /****************************************************************************/ 611 /* */ 612 /* eunion.c */ 613 /* */ 614 /****************************************************************************/ 615 616 int 617 CCutil_edge_file_union (int ncount, int nfiles, char **flist, int *ecount, 618 int **elist, int **elen, int *foundtour, double *besttourlen); 619 620 621 622 /****************************************************************************/ 623 /* */ 624 /* fastread.c */ 625 /* */ 626 /****************************************************************************/ 627 628 629 int 630 CCutil_readint (FILE *f); 631 632 633 634 635 636 /****************************************************************************/ 637 /* */ 638 /* genhash.c */ 639 /* */ 640 /****************************************************************************/ 641 642 struct CCgenhash_elem; 643 644 typedef struct CCgenhash { 645 int nelem; 646 int maxelem; 647 int size; 648 int (*hcmp) (void *key1, void *key2, void *u_data); 649 unsigned int (*hfunc) (void *key, void *u_data); 650 void *u_data; 651 double maxdensity; 652 double lowdensity; 653 CCptrworld elem_world; 654 struct CCgenhash_elem **table; 655 } CCgenhash; 656 657 typedef struct CCgenhash_iter { 658 int i; 659 struct CCgenhash_elem *next; 660 } CCgenhash_iter; 661 662 663 int 664 CCutil_genhash_init (CCgenhash *h, int size, int (*hcmp) (void *key1, 665 void *key2, void *u_data), unsigned int (*hfunc) (void *key, 666 void *u_data), void *u_data, double maxdensity, double lowdensity), 667 CCutil_genhash_insert (CCgenhash *h, void *key, void *data), 668 CCutil_genhash_insert_h (CCgenhash *h, unsigned int hashval, void *key, 669 void *data), 670 CCutil_genhash_replace (CCgenhash *h, void *key, void *data), 671 CCutil_genhash_replace_h (CCgenhash *h, unsigned int hashval, void *key, 672 void *data), 673 CCutil_genhash_delete (CCgenhash *h, void *key), 674 CCutil_genhash_delete_h (CCgenhash *h, unsigned int hashval, void *key); 675 676 unsigned int 677 CCutil_genhash_hash (CCgenhash *h, void *key); 678 679 void 680 *CCutil_genhash_lookup (CCgenhash *h, void *key), 681 *CCutil_genhash_lookup_h (CCgenhash *h, unsigned int hashval, void *key), 682 *CCutil_genhash_next (CCgenhash *h, CCgenhash_iter *iter, void **key, 683 int *keysize); 684 685 void 686 CCutil_genhash_u_data (CCgenhash *h, void *u_data), 687 CCutil_genhash_free (CCgenhash *h, void (*freefunc)(void *key, void *data, 688 void *u_data)), 689 CCutil_genhash_start (CCgenhash *h, CCgenhash_iter *iter); 690 691 692 693 694 695 /****************************************************************************/ 696 /* */ 697 /* getdata.c */ 698 /* */ 699 /****************************************************************************/ 700 701 #define CC_MASTER_NO_DAT 100 702 #define CC_MASTER_DAT 101 703 704 void 705 CCutil_cycle_len (int ncount, CCdatagroup *dat, int *cycle, double *len); 706 707 int 708 CCutil_getdata (char *datname, int binary_in, int innorm, int *ncount, 709 CCdatagroup *dat, int gridsize, int allow_dups, CCrandstate *rstate), 710 CCutil_writedata (char *datname, int binary_out, int ncount, 711 CCdatagroup *dat), 712 CCutil_putmaster (char *mastername, int ncount, CCdatagroup *dat, 713 int *perm), 714 CCutil_writemaster (CC_SFILE *out, int ncount, CCdatagroup *dat, 715 int *perm), 716 CCutil_getmaster (char *mastername, int *ncount, CCdatagroup *dat, 717 int **perm), 718 CCutil_readmaster (CC_SFILE *in, int *ncount, CCdatagroup *dat, 719 int **perm), 720 CCutil_getnodeweights (char *weightname, int ncount, int weight_limit, 721 double **wcoord, CCrandstate *rstate), 722 CCutil_gettsplib (char *datname, int *ncount, CCdatagroup *dat), 723 CCutil_writetsplib (const char *fname, int ncount, CCdatagroup *dat), 724 CCutil_datagroup_perm (int ncount, CCdatagroup *dat, int *perm), 725 CCutil_copy_datagroup (int ncount, CCdatagroup *indat, CCdatagroup *outdat), 726 CCutil_getedgelist (int ncount, char *fname, int *ecount, int **elist, 727 int **elen, int binary_in), 728 CCutil_getedgelist_n (int *ncount, char *fname, int *ecount, int **elist, 729 int **elen, int binary_in), 730 CCutil_genedgelist (int ncount, int ecount, int **elist, int **elen, 731 CCdatagroup *dat, int maxlen, CCrandstate *rstate), 732 CCutil_getcycle_tsplib (int ncount, char *cyclename, int *outcycle), 733 CCutil_getcycle_edgelist (int ncount, char *cyclename, int *outcycle, 734 int binary_in), 735 CCutil_getcycle (int ncount, char *cyclename, int *outcycle, 736 int binary_in), 737 CCutil_getedges_double (int *ncount, char *fname, int *ecount, int **elist, 738 double **elen, int binary_in), 739 CCutil_writeedges (int ncount, char *outedgename, int ecount, int *elist, 740 CCdatagroup *dat, int binary_out), 741 CCutil_writecycle_edgelist (int ncount, char *outedgename, int *cycle, 742 CCdatagroup *dat, int binary_out), 743 CCutil_writecycle (int ncount, char *outcyclename, int *cycle, 744 int binary_out), 745 CCutil_writeedges_int (int ncount, char *outedgename, int ecount, 746 int *elist, int *elen, int binary_out), 747 CCutil_writeedges_double (int ncount, char *outedgename, int ecount, 748 int *elist, double *elen, int binary_out), 749 CCutil_tri2dat (int ncount, int *elen, CCdatagroup *dat), 750 CCutil_graph2dat_matrix (int ncount, int ecount, int *elist, int *elen, 751 int defaultlen, CCdatagroup *dat), 752 CCutil_graph2dat_sparse (int ncount, int ecount, int *elist, int *elen, 753 int defaultlen, CCdatagroup *dat), 754 CCutil_get_sparse_dat_edges (int ncount, CCdatagroup *dat, int *ecount, 755 int **elist, int **elen), 756 CCutil_sparse_strip_edges (CCdatagroup *dat, int in_ecount, int *in_elist, 757 int *in_elen, int *ecount, int **elist, int **elen), 758 CCutil_sparse_real_tour (int ncount, CCdatagroup *dat, int *cyc, 759 int *yesno); 760 761 762 763 764 /****************************************************************************/ 765 /* */ 766 /* priority.c */ 767 /* */ 768 /****************************************************************************/ 769 770 typedef struct CCpriority { 771 CCdheap heap; 772 union CCpri_data { 773 void *data; 774 int next; 775 } *pri_info; 776 int space; 777 int freelist; 778 } CCpriority; 779 780 781 void 782 CCutil_priority_free (CCpriority *pri), 783 CCutil_priority_delete (CCpriority *pri, int handle), 784 CCutil_priority_changekey (CCpriority *pri, int handle, double newkey), 785 *CCutil_priority_findmin (CCpriority *pri, double *keyval), 786 *CCutil_priority_deletemin (CCpriority *pri, double *keyval); 787 788 int 789 CCutil_priority_init (CCpriority *pri, int k), 790 CCutil_priority_insert (CCpriority *pri, void *data, double keyval); 791 792 793 794 /****************************************************************************/ 795 /* */ 796 /* safe_io.c */ 797 /* */ 798 /****************************************************************************/ 799 800 801 CC_SFILE 802 *CCutil_sopen (const char *f, const char *s), 803 *CCutil_sdopen (int d, const char *s); 804 805 int 806 CCutil_swrite (CC_SFILE *f, char *buf, int size), 807 CCutil_swrite_bits (CC_SFILE *f, int x, int xbits), 808 CCutil_swrite_ubits (CC_SFILE *f, unsigned int x, int xbits), 809 CCutil_swrite_char (CC_SFILE *f, char x), 810 CCutil_swrite_string (CC_SFILE *f, const char *x), 811 CCutil_swrite_short (CC_SFILE *f, short x), 812 CCutil_swrite_ushort (CC_SFILE *f, unsigned short x), 813 CCutil_swrite_int (CC_SFILE *f, int x), 814 CCutil_swrite_uint (CC_SFILE *f, unsigned int x), 815 CCutil_swrite_double (CC_SFILE *f, double x), 816 CCutil_sread (CC_SFILE *f, char *buf, int size), 817 CCutil_sread_bits (CC_SFILE *f, int *x, int xbits), 818 CCutil_sread_ubits (CC_SFILE *f, unsigned int *x, int xbits), 819 CCutil_sread_char (CC_SFILE *f, char *x), 820 CCutil_sread_string (CC_SFILE *f, char *x, int maxlen), 821 CCutil_sread_short (CC_SFILE *f, short *x), 822 CCutil_sread_ushort (CC_SFILE *f, unsigned short *x), 823 CCutil_sread_short_r (CC_SFILE *f, short *x), 824 CCutil_sread_int (CC_SFILE *f, int *x), 825 CCutil_sread_uint (CC_SFILE *f, unsigned int *x), 826 CCutil_sread_int_r (CC_SFILE *f, int *x), 827 CCutil_sread_double (CC_SFILE *f, double *x), 828 CCutil_sread_double_r (CC_SFILE *f, double *x), 829 CCutil_sflush (CC_SFILE *f), 830 CCutil_stell (CC_SFILE *f), 831 CCutil_sseek (CC_SFILE *f, int offset), 832 CCutil_srewind (CC_SFILE *f), 833 CCutil_sclose (CC_SFILE *f), 834 CCutil_sbits (unsigned int x), 835 CCutil_sdelete_file (const char *fname), 836 CCutil_sdelete_file_backup (const char *fname); 837 838 #ifdef CC_NETREADY 839 CC_SFILE 840 *CCutil_snet_open (const char *hname, unsigned short p), 841 *CCutil_snet_receive (CC_SPORT *s); 842 843 CC_SPORT 844 *CCutil_snet_listen (unsigned short p); 845 846 void 847 CCutil_snet_unlisten (CC_SPORT *s); 848 849 #endif /* CC_NETREADY */ 850 851 852 853 854 855 /****************************************************************************/ 856 /* */ 857 /* signal.c */ 858 /* */ 859 /****************************************************************************/ 860 861 #define CCutil_SIGHUP 1 /* HangUp */ 862 #define CCutil_SIGINT 2 /* Interrupt */ 863 #define CCutil_SIGQUIT 3 /* Quit */ 864 #define CCutil_SIGILL 4 /* Illegal instruction */ 865 #define CCutil_SIGTRAP 5 /* Trace trap */ 866 #define CCutil_SIGABRT 6 /* Abort */ 867 #define CCutil_SIGEMT 7 /* Emulator trap */ 868 #define CCutil_SIGFPE 8 /* Floating point exception */ 869 #define CCutil_SIGKILL 9 /* Kill process */ 870 #define CCutil_SIGBUS 10 /* Bus error */ 871 #define CCutil_SIGSEGV 11 /* Segmentation fault */ 872 #define CCutil_SIGSYS 12 /* Illegal argument to system call */ 873 #define CCutil_SIGPIPE 13 /* Pipe */ 874 #define CCutil_SIGALRM 14 /* Alarm */ 875 #define CCutil_SIGTERM 15 /* Terminate */ 876 #define CCutil_SIGUSR1 16 /* User signal 1 */ 877 #define CCutil_SIGUSR2 17 /* User signal 2 */ 878 #define CCutil_SIGCHLD 18 /* Child condition change */ 879 #define CCutil_SIGPWR 19 /* Power fail */ 880 #define CCutil_SIGWINCH 20 /* Window size changes */ 881 #define CCutil_SIGURG 21 /* Urgent condition on IO channel*/ 882 #define CCutil_SIGIO 22 /* IO possible */ 883 #define CCutil_SIGSTOP 23 /* Stop */ 884 #define CCutil_SIGTSTP 24 /* Tty stop */ 885 #define CCutil_SIGCONT 25 /* Continue */ 886 #define CCutil_SIGTTIN 26 /* Tty background read */ 887 #define CCutil_SIGTTOU 27 /* Tty background write */ 888 #define CCutil_SIGVTALRM 28 /* Virtual timer alarm */ 889 #define CCutil_SIGPROF 29 /* Profiling timer alarm */ 890 #define CCutil_SIGXCPU 30 /* CPU limit exceeded */ 891 #define CCutil_SIGXFSZ 31 /* File size limit exceeded */ 892 #define CCutil_SIGSTKFLT 32 /* Stack fault */ 893 #define CCutil_SIGIOT 33 /* IOT instruction */ 894 #define CCutil_SIGPOLL 34 /* Pollable event */ 895 #define CCutil_SIGMSG 35 /* Message available */ 896 #define CCutil_SIGDANGER 36 /* System crash imminent */ 897 #define CCutil_SIGMIGRATE 37 /* Migrate process */ 898 #define CCutil_SIGPRE 38 /* Programming exception */ 899 #define CCutil_SIGVIRT 39 /* Second virtual time alarm */ 900 #define CCutil_MAXSIG 39 901 902 903 typedef void (*CCutil_handler)(int signum); 904 905 int 906 CCutil_signal_handler (int ccsignum, CCutil_handler handler), 907 CCutil_signal_default (int ccsignum), 908 CCutil_signal_ignore (int ccsignum), 909 CCutil_sig_to_ccsig (int signum); 910 911 void 912 CCutil_signal_init (void), 913 CCutil_handler_fatal (int signum), 914 CCutil_handler_warn (int signum), 915 CCutil_handler_exit (int signum); 916 917 918 919 920 /****************************************************************************/ 921 /* */ 922 /* sortrus.c */ 923 /* */ 924 /****************************************************************************/ 925 926 927 void 928 CCutil_int_array_quicksort (int *len, int n), 929 CCutil_int_perm_quicksort (int *perm, int *len, int n), 930 CCutil_double_perm_quicksort (int *perm, double *len, int n), 931 CCutil_rselect (int *arr, int l, int r, int m, double *coord, 932 CCrandstate *rstate); 933 934 char 935 *CCutil_linked_radixsort (char *data, char *datanext, char *dataval, 936 int valsize); 937 938 939 /****************************************************************************/ 940 /* */ 941 /* subdiv.c */ 942 /* */ 943 /****************************************************************************/ 944 945 #define CC_SUBDIV_PORT ((unsigned short) 32141) 946 #define CC_SUBGATE_PORT ((unsigned short) 32143) 947 #define CCutil_FILE_NAME_LEN (128) 948 949 typedef struct CCsubdiv { 950 double xrange[2]; 951 double yrange[2]; 952 int cnt; 953 int id; 954 double bound; 955 int status; 956 } CCsubdiv; 957 958 typedef struct CCsubdiv_lkh { 959 int id; 960 int cnt; 961 int start; 962 double origlen; 963 double newlen; 964 int status; 965 } CCsubdiv_lkh; 966 967 968 int 969 CCutil_karp_partition (int ncount, CCdatagroup *dat, int partsize, 970 int *p_scount, CCsubdiv **p_slist, int ***partlist, 971 CCrandstate *rstate), 972 CCutil_write_subdivision_index (char *problabel, int ncount, int scount, 973 CCsubdiv *slist), 974 CCutil_read_subdivision_index (char *index_name, char **p_problabel, 975 int *p_ncount, int *p_scount, CCsubdiv **p_slist), 976 CCutil_write_subdivision_lkh_index (char *problabel, int ncount, 977 int scount, CCsubdiv_lkh *slist, double tourlen), 978 CCutil_read_subdivision_lkh_index (char *index_name, char **p_problabel, 979 int *p_ncount, int *p_scount, CCsubdiv_lkh **p_slist, 980 double *p_tourlen); 981 982 983 /****************************************************************************/ 984 /* */ 985 /* urandom.c */ 986 /* */ 987 /****************************************************************************/ 988 989 /* since urandom's generator does everything modulo CC_PRANDMAX, if two 990 * seeds are congruent mod x and x|CC_PRANDMAX, then the resulting numbers 991 * will be congruent mod x. One example was if CC_PRANDMAX = 1000000000 and 992 * urandom is used to generate a point set from a 1000x1000 grid, seeds 993 * congruent mod 1000 generate the same point set. 994 * 995 * For this reason, we use 1000000007 (a prime) 996 */ 997 #define CC_PRANDMAX 1000000007 998 999 void 1000 CCutil_sprand (int seed, CCrandstate *r); 1001 1002 int 1003 CCutil_lprand (CCrandstate *r); 1004 1005 double 1006 CCutil_normrand (CCrandstate *r); 1007 1008 1009 1010 1011 1012 /****************************************************************************/ 1013 /* */ 1014 /* util.c */ 1015 /* */ 1016 /****************************************************************************/ 1017 1018 1019 char 1020 *CCutil_strchr (char *s, int c), 1021 *CCutil_strrchr (char *s, int c), 1022 *CCutil_strdup (const char *s), 1023 *CCutil_strdup2 (const char *s); 1024 1025 const char 1026 *CCutil_strchr_c (const char *s, int c), 1027 *CCutil_strrchr_c (const char *s, int c); 1028 1029 unsigned int 1030 CCutil_nextprime (unsigned int x); 1031 1032 int 1033 CCutil_our_gcd (int a, int b), 1034 CCutil_our_lcm (int a, int b), 1035 CCutil_print_command (int ac, char **av); 1036 1037 void 1038 CCutil_readstr (FILE *f, char *s, int len), 1039 CCutil_printlabel (void); 1040 1041 1042 1043 1044 1045 /****************************************************************************/ 1046 /* */ 1047 /* zeit.c */ 1048 /* */ 1049 /****************************************************************************/ 1050 1051 typedef struct CCutil_timer { 1052 double szeit; 1053 double cum_zeit; 1054 char name[40]; 1055 int count; 1056 } CCutil_timer; 1057 1058 1059 double 1060 CCutil_zeit (void), 1061 CCutil_real_zeit (void), 1062 CCutil_stop_timer (CCutil_timer *t, int printit), 1063 CCutil_total_timer (CCutil_timer *t, int printit); 1064 1065 1066 void 1067 CCutil_init_timer (CCutil_timer *t, const char *name), 1068 CCutil_start_timer (CCutil_timer *t), 1069 CCutil_suspend_timer (CCutil_timer *t), 1070 CCutil_resume_timer (CCutil_timer *t); 1071 1072 1073 1074 #endif /* __UTIL_H */ 1075