1/* BEGIN LICENSE BLOCK 2 * Version: CMPL 1.1 3 * 4 * The contents of this file are subject to the Cisco-style Mozilla Public 5 * License Version 1.1 (the "License"); you may not use this file except 6 * in compliance with the License. You may obtain a copy of the License 7 * at www.eclipse-clp.org/license. 8 * 9 * Software distributed under the License is distributed on an "AS IS" 10 * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See 11 * the License for the specific language governing rights and limitations 12 * under the License. 13 * 14 * The Original Code is The ECLiPSe Constraint Logic Programming System. 15 * The Initial Developer of the Original Code is Cisco Systems, Inc. 16 * Portions created by the Initial Developer are 17 * Copyright (C) 1997-2006 Cisco Systems, Inc. All Rights Reserved. 18 * 19 * Contributor(s): Joachim Schimpf, IC-Parc 20 * 21 * END LICENSE BLOCK */ 22/*---------------------------------------------------------------------- 23* System: ECLiPSe Constraint Logic Programming System 24* Version: $Id: edge_finder.c,v 1.1 2006/09/23 01:53:26 snovello Exp $ 25*----------------------------------------------------------------------*/ 26 27/* 28 * Description: Edge-finder in C 29 * Nuijten's algorithms 30 * 31 * Author: J.Schimpf, IC-Parc 32 * 33 */ 34 35#include "eclipse.h" 36 37#ifdef STDC_HEADERS 38#include <stdlib.h> /* for malloc() */ 39#endif 40 41#define BOUND2 42#define BOUND3 43#define SET_BOOLEANS 44 45#ifndef NULL 46#define NULL 0 47#endif 48 49#define DOMAIN_MINF (-10000000) 50#define DOMAIN_PINF (10000000) 51 52#define OPT_QUADR 0 53#define OPT_CUBIC 1 /* bit-significant */ 54#define OPT_BOOLS 2 /* bit-significant */ 55 56typedef struct { 57 long est, lst; /* earliest/latest start time */ 58 long ect, lct; /* earliest/latest completion time */ 59 long size; /* size (resource usage) */ 60 long sz; /* size index */ 61 long dur; /* (min) duration */ 62 long area; /* area, ie. size*duration */ 63 long lb, ub; /* new bounds on start time */ 64} task_t; 65 66typedef struct { 67 task_t **asc_lct; /* [ntasks] */ 68 task_t **asc_est; /* [ntasks] */ 69 task_t *tasks; /* [ntasks] */ 70 long *sizes; /* [ntasks], only nsizes used */ 71 long *_G; /* [ntasks*nsizes_max], may get reallocated */ 72 long *ECT; /* [ntasks], also LST */ 73 long ntasks; 74 long nsizes; /* number of valid entries in sizes[] */ 75 long nsizes_max; /* tracks the maximum of nsizes */ 76 long some_size_changed; /* bool: one or more tasks changed size */ 77 long capacity; 78 long refcnt; 79 long option; 80} ef_t; 81 82#define G(i) (ef->_G + (i)*ef->nsizes) 83#define Size(j) (ef->sizes[j]) 84#define LST ECT 85#define DELTA ECT 86#define TaskNr(t) ((t)-ef->tasks) 87 88static void _ef_desc_free(); 89static t_ext_ptr _ef_desc_copy(); 90static pword _ef_desc_get(); 91 92static t_ext_type ef_desc = { 93 _ef_desc_free, 94 _ef_desc_copy, 95 NULL,NULL,NULL,NULL, 96 _ef_desc_copy, 97 _ef_desc_get, 98 NULL 99}; 100 101 102static void 103_ef_desc_free(obj) 104t_ext_ptr obj; 105{ 106 ef_t *ef = (ef_t *)obj; 107 if (--ef->refcnt == 0) 108 { 109 free(ef->tasks); 110 free(ef->asc_est); 111 free(ef->asc_lct); 112 free(ef->sizes); 113 free(ef->ECT); 114 if (ef->_G) 115 free(ef->_G); 116 free(ef); 117 } 118} 119 120static t_ext_ptr 121_ef_desc_copy(obj) 122t_ext_ptr obj; 123{ 124 ((ef_t *)obj)->refcnt++; 125 return obj; 126} 127 128static pword 129_ef_desc_get(obj, i) 130t_ext_ptr obj; 131int i; 132{ 133 return ec_term(ec_did("task",2), 134/* 135 return ec_term(ec_did("task",9), 136 ec_long(((ef_t *) obj)->tasks[i].est), 137 ec_long(((ef_t *) obj)->tasks[i].lst), 138 ec_long(((ef_t *) obj)->tasks[i].ect), 139 ec_long(((ef_t *) obj)->tasks[i].lct), 140 ec_long(((ef_t *) obj)->tasks[i].sz), 141 ec_long(((ef_t *) obj)->tasks[i].dur), 142 ec_long(((ef_t *) obj)->tasks[i].area), 143*/ 144 ec_long(((ef_t *) obj)->tasks[i].lb), 145 ec_long(((ef_t *) obj)->tasks[i].ub) 146 ); 147} 148 149int 150ec_init_ef( /* +N, +Capacity, +Option, -EfHandle */ ) 151{ 152 ef_t *ef; 153 long i,n,cap,opt; 154 155 if (ec_get_long(ec_arg(1), &n) != PSUCCEED) 156 return TYPE_ERROR; 157 if (ec_get_long(ec_arg(2), &cap) != PSUCCEED) 158 return TYPE_ERROR; 159 if (n <= 0) 160 return RANGE_ERROR; 161 if (ec_get_long(ec_arg(3), &opt) != PSUCCEED) 162 return TYPE_ERROR; 163 164 ef = (ef_t *) malloc(n*sizeof(ef_t)); 165 ef->tasks = (task_t *) malloc(n*sizeof(task_t)); 166 ef->asc_lct = (task_t **) malloc(n*sizeof(task_t*)); 167 ef->asc_est = (task_t **) malloc(n*sizeof(task_t*)); 168 ef->sizes = (long *) malloc(n*sizeof(long)); 169 ef->ECT = (long *) malloc(n*sizeof(long)); 170 for (i=0; i<n; i++) 171 { 172 ef->asc_lct[i] = ef->asc_est[i] = &ef->tasks[i]; 173 ef->tasks[i].sz = n; /* uninit */ 174 } 175 ef->capacity = cap; 176 ef->ntasks = n; 177 ef->nsizes = ef->nsizes_max = 0; 178 ef->_G = NULL; 179 ef->refcnt = 1; 180 ef->option = opt; 181 ef->some_size_changed = 1; 182 183 return ec_unify_arg(4, ec_handle(&ef_desc, (t_ext_ptr)ef)); 184} 185 186int 187ec_init_task( /*EfHandle,I,Est,Lst,Ect,Lct,Sz,Dur,Area*/ ) 188{ 189 ef_t *ef; 190 long i, size; 191 192 if (ec_get_handle(ec_arg(1), &ef_desc, (t_ext_ptr*)&ef) != PSUCCEED || 193 ec_get_long(ec_arg(2), &i) != PSUCCEED || 194 ec_get_long(ec_arg(3), &ef->tasks[i].est) != PSUCCEED || 195 ec_get_long(ec_arg(4), &ef->tasks[i].lst) != PSUCCEED || 196 ec_get_long(ec_arg(5), &ef->tasks[i].ect) != PSUCCEED || 197 ec_get_long(ec_arg(6), &ef->tasks[i].lct) != PSUCCEED || 198 ec_get_long(ec_arg(7), &size) != PSUCCEED || 199 ec_get_long(ec_arg(8), &ef->tasks[i].dur) != PSUCCEED || 200 ec_get_long(ec_arg(9), &ef->tasks[i].area) != PSUCCEED 201 ) 202 { 203 return TYPE_ERROR; 204 } 205 206 ef->tasks[i].lb = ef->tasks[i].est; 207 ef->tasks[i].ub = ef->tasks[i].lst; 208 209 if (!ef->some_size_changed && size != ef->tasks[i].size) 210 ef->some_size_changed = 1; 211 ef->tasks[i].size = size; 212 213 return PSUCCEED; 214} 215 216static void 217_construct_size_table(ef) 218ef_t *ef; 219{ 220 long i; 221 ef->nsizes = 0; 222 for (i=0; i<ef->ntasks; ++i) 223 { 224 long j = 0; /* lookup */ 225 while (j < ef->nsizes && ef->tasks[i].size != Size(j)) 226 ++j; 227 if (j == ef->nsizes) /* new size */ 228 { 229 Size(j) = ef->tasks[i].size; 230 ++ef->nsizes; 231 } 232 ef->tasks[i].sz = j; 233 } 234 if (ef->nsizes > ef->nsizes_max) 235 { 236 /* we have more sizes than ever: need a bigger array for G */ 237 ef->nsizes_max = ef->nsizes; 238 if (ef->_G) 239 ef->_G = (long*) realloc(ef->_G, sizeof(long)*ef->nsizes_max*ef->ntasks); 240 else 241 ef->_G = (long*) malloc(sizeof(long)*ef->nsizes_max*ef->ntasks); 242 } 243 ef->some_size_changed = 0; 244 return; 245} 246 247static int 248_asc_lct(t1, t2) 249task_t **t1, **t2; 250{ 251 return (*t1)->lct > (*t2)->lct ? 1 : (*t1)->lct < (*t2)->lct ? -1 : 0; 252} 253 254static int 255_asc_est(t1, t2) 256task_t **t1, **t2; 257{ 258 return (*t1)->est > (*t2)->est ? 1 : (*t1)->est < (*t2)->est ? -1 : 0; 259} 260 261#define upd_max(max, expr) {\ 262 long _tmp = (expr);\ 263 if (_tmp > max) max = _tmp;\ 264} 265 266#define upd_min(min, expr) {\ 267 long _tmp = (expr);\ 268 if (_tmp < min) min = _tmp;\ 269} 270 271#define upd_max_f(max, expr) {\ 272 double _tmp = (expr);\ 273 if (_tmp > max) max = _tmp;\ 274} 275 276#define upd_min_f(min, expr) {\ 277 double _tmp = (expr);\ 278 if (_tmp < min) min = _tmp;\ 279} 280 281#define Before(ti,tj) {\ 282 int err = _before(ef, bools, ti, tj);\ 283 if (err != PSUCCEED) return err;\ 284} 285 286 287/* Set boolean such that Ti is before tj */ 288 289static int 290_before(ef, bools, ti, tj) 291ef_t *ef; 292pword bools; 293task_t *ti, *tj; 294{ 295 int err, idx; 296 long zero_one; 297 pword var; 298 int i = TaskNr(ti); 299 int j = TaskNr(tj); 300 if (i < j) { idx = j*(j-1)/2+i+1; zero_one = 0; } 301 else if (i > j) { idx = i*(i-1)/2+j+1; zero_one = 1; } 302 else return RANGE_ERROR; 303 err = ec_get_arg(idx, bools, &var); 304 if (err != PSUCCEED) 305 return err; 306 return ec_unify(var, ec_long(zero_one)); 307} 308 309int 310ec_ef_disj( /* EfHandle */ ) 311{ 312 ef_t *ef; 313 int y, x, i; 314 long g, h, p; 315 task_t **X, **Y; 316 pword bools; 317 bools = ec_arg(2); 318 319 if (ec_get_handle(ec_arg(1), &ef_desc, (t_ext_ptr*)&ef) != PSUCCEED) 320 return TYPE_ERROR; 321 322 if (ec_get_nil(bools) != PSUCCEED) 323 ef->option |= OPT_BOOLS; 324 325 if (ef->some_size_changed) 326 _construct_size_table(ef); 327 328 qsort((void*) (ef->asc_lct), ef->ntasks, sizeof(task_t*), _asc_lct); 329 qsort((void*) (ef->asc_est), ef->ntasks, sizeof(task_t*), _asc_est); 330 331 Y = ef->asc_lct; 332 X = ef->asc_est; 333 for (y = 0; y < ef->ntasks; ++y) /* asc lct */ 334 { 335 if (y == ef->ntasks-1 || Y[y]->lct != Y[y+1]->lct) 336 { 337 p = 0; 338 g = DOMAIN_MINF; 339#ifdef BOUND2 340 ef->ECT[ef->ntasks-1] = DOMAIN_PINF; 341#endif 342 343 for (i = ef->ntasks-1; i >= 0; --i) /* desc est */ 344 { 345 if (X[i]->lct <= Y[y]->lct) 346 { 347 p += X[i]->dur; 348 upd_max(g, X[i]->est + p); 349 if (g > Y[y]->lct) 350 return PFAIL; 351#ifdef BOUND2 352 upd_min(ef->ECT[i], X[i]->ect); 353#endif 354 } 355 ef->_G[i] = g; 356#ifdef BOUND2 357 if (i > 0) 358 ef->ECT[i-1] = ef->ECT[i]; 359#endif 360 } 361 362 h = DOMAIN_MINF; 363 for (x = 0; x < ef->ntasks; ++x) /* asc est */ 364 { 365 if (X[x]->lct > Y[y]->lct) 366 { 367 if (X[x]->est + p + X[x]->dur > Y[y]->lct) 368 { 369 upd_max(X[x]->lb, ef->_G[x]); 370#ifdef SET_BOOLEANS 371 if (ef->option & OPT_BOOLS) 372 { 373 int v; 374 for (v = x+1; v < ef->ntasks && X[v]->est < Y[y]->lct; ++v) 375 { 376 if (X[v]->lct <= Y[y]->lct) 377 Before(X[v],X[x]); 378 } 379 } 380#endif 381 } 382 if (h + X[x]->dur > Y[y]->lct) 383 { 384 upd_max(X[x]->lb, g); 385#ifdef SET_BOOLEANS 386 if (ef->option & OPT_BOOLS) 387 { 388 int v; 389 for (v = 0; v < ef->ntasks && X[v]->est < Y[y]->lct; ++v) 390 { 391 if (X[v]->lct <= Y[y]->lct) 392 Before(X[v],X[x]); 393 } 394 } 395#endif 396 } 397 } 398 else 399 { 400 upd_max(h, X[x]->est + p); 401 p -= X[x]->dur; 402 } 403#ifdef BOUND2 404 if (ef->option & OPT_CUBIC) 405 { 406 int w; 407 /* duration of those that must start later than w and 408 * finish before y */ 409 long Pp = p + X[x]->dur; 410 /* what remains if x is first: */ 411 long avail = Y[y]->lct - X[x]->est; 412 for (w = x-1; w >= 0; --w) /* desc est */ 413 { 414 if (X[w]->lct <= Y[y]->lct) 415 { 416 if (ef->ECT[w] <= X[x]->est) 417 break; 418 Pp += X[w]->dur; 419 if (Pp > avail) 420 /* x can't be first, must be after w */ 421 upd_max(X[x]->lb, ef->ECT[w]); 422 } 423 } 424 } 425#endif 426 } 427 } 428 } 429 430 Y = ef->asc_est; 431 X = ef->asc_lct; 432 for (y = ef->ntasks-1; y >= 0; --y) /* desc est */ 433 { 434 if (y == 0 || Y[y]->est != Y[y-1]->est) 435 { 436 p = 0; 437 g = DOMAIN_PINF; 438#ifdef BOUND2 439 ef->LST[0] = DOMAIN_MINF; 440#endif 441 442 for (i = 0; i < ef->ntasks; ++i) /* asc lct */ 443 { 444 if (X[i]->est >= Y[y]->est) 445 { 446 p += X[i]->dur; 447 upd_min(g, X[i]->lct - p); 448 if (g < Y[y]->est) 449 return PFAIL; 450#ifdef BOUND2 451 upd_max(ef->LST[i], X[i]->lst); 452#endif 453 } 454 ef->_G[i] = g; 455#ifdef BOUND2 456 if (i < ef->ntasks-1) 457 ef->LST[i+1] = ef->LST[i]; 458#endif 459 } 460 461 h = DOMAIN_PINF; 462 for (x = ef->ntasks-1; x >= 0; --x) /* desc lct */ 463 { 464 if (X[x]->est < Y[y]->est) 465 { 466 if (X[x]->lct - p - X[x]->dur < Y[y]->est) 467 { 468 upd_min(X[x]->ub, ef->_G[x] - X[x]->dur); 469#ifdef SET_BOOLEANS 470 if (ef->option & OPT_BOOLS) 471 { 472 int v; 473 for (v = x-1; v >= 0 && X[v]->lct > Y[y]->est; --v) 474 { 475 if (X[v]->est >= Y[y]->est) 476 Before(X[x],X[v]); 477 } 478 } 479#endif 480 } 481 if (h - X[x]->dur < Y[y]->est) 482 { 483 upd_min(X[x]->ub, g - X[x]->dur); 484#ifdef SET_BOOLEANS 485 if (ef->option & OPT_BOOLS) 486 { 487 int v; 488 for (v = ef->ntasks-1; v >= 0 && X[v]->lct > Y[y]->est; --v) 489 { 490 if (X[v]->est >= Y[y]->est) 491 Before(X[x],X[v]); 492 } 493 } 494#endif 495 } 496 } 497 else 498 { 499 upd_min(h, X[x]->lct - p); 500 p -= X[x]->dur; 501 } 502#ifdef BOUND2 503 if (ef->option & OPT_CUBIC) 504 { 505 int w; 506 long Pp = p + X[x]->dur; 507 long avail = X[x]->lct - Y[y]->est; 508 for (w = x+1; w < ef->ntasks; ++w) /* asc lct */ 509 { 510 if (X[w]->est >= Y[y]->est) 511 { 512 if (ef->LST[w] >= X[x]->lct) 513 break; 514 Pp += X[w]->dur; 515 if (Pp > avail) 516 upd_min(X[x]->ub, ef->LST[w] - X[x]->dur); 517 } 518 } 519 } 520#endif 521 } 522 } 523 } 524 return PSUCCEED; 525} 526 527int 528ec_ef_cum( /* EfHandle */ ) 529{ 530 ef_t *ef; 531 int y, x, i, j; 532 long l, Ar, cap; 533 long *g; 534 double H; 535 task_t **X, **Y; 536 537 if (ec_get_handle(ec_arg(1), &ef_desc, (t_ext_ptr*)&ef) != PSUCCEED) 538 return TYPE_ERROR; 539 540 if (ef->some_size_changed) 541 _construct_size_table(ef); 542 543 cap = ef->capacity; 544 545 qsort((void*) (ef->asc_lct), ef->ntasks, sizeof(task_t*), _asc_lct); 546 qsort((void*) (ef->asc_est), ef->ntasks, sizeof(task_t*), _asc_est); 547 548 Y = ef->asc_lct; 549 X = ef->asc_est; 550 for (y = 0; y < ef->ntasks; ++y) /* asc lct */ 551 { 552 if (y == ef->ntasks-1 || Y[y]->lct != Y[y+1]->lct) 553 { 554 /* 555 * We are looking at all task intervals ending at Y[y]->lct 556 */ 557 558 Ar = 0; 559 l = DOMAIN_MINF; 560 g = G(ef->ntasks-1); /* first i in next loop */ 561 for (j = 0; j < ef->nsizes; ++j) 562 g[j] = DOMAIN_MINF; 563#ifdef BOUND2 564 ef->ECT[ef->ntasks-1] = DOMAIN_PINF; 565#endif 566 567 for (i = ef->ntasks-1; i >= 0; --i) /* desc est */ 568 { 569 if (X[i]->lct <= Y[y]->lct) 570 { 571 /* 572 * We are looking at the task interval between 573 * X[i]->est .. Y[y]->lct (the actual upper end is l). 574 * We compute g[sz] which is a lower bound for the 575 * start time of a task of size sz which starts 576 * after this task interval. 577 */ 578 579 Ar += X[i]->area; 580 if (X[i]->est + (Ar-1+cap)/cap > Y[y]->lct) 581 return PFAIL; 582#ifdef BOUND2 583 upd_min(ef->ECT[i], X[i]->ect); 584#endif 585 upd_max(l, X[i]->lct); 586 for (j = 0; j < ef->nsizes; ++j) 587 { 588 long size_j = Size(j); 589 long rest = Ar - (l-X[i]->est) * (cap-size_j); 590 if (rest > 0) 591 upd_max(g[j], X[i]->est + (rest-1+size_j)/size_j); 592 } 593 } 594 if (i > 0) /* init g for the next iteration */ 595 { 596 for (j = 0; j < ef->nsizes; ++j) 597 G(i-1)[j] = g[j]; 598 g = G(i-1); 599#ifdef BOUND2 600 ef->ECT[i-1] = ef->ECT[i]; 601#endif 602 } 603 } 604 605 /* We have now 606 * Ar area of the largest task interval ending at Y[y]->lct 607 * (we reconstruct the smaller ones by subtracting). 608 * G[i,sz] For each task interval X[i]->est..Y[y]->lct and 609 * each size sz of possible subsequent task: a lower 610 * bound on the start time of such a subsequent task. 611 * (the G[i] for tasks not belonging to the task 612 * intervals have the same contents as the next 613 * subsequent member). 614 */ 615 /* 616 * H is an obvious lower bound on the start times, computed by 617 * assuming that all tasks in a task interval are packed to the 618 * and executed with full capacity (fuly elastic relaxation). 619 * This is a float because we can't round up and we would lose 620 * information by rounding down. 621 */ 622 H = (double) DOMAIN_MINF; 623 for (x = 0; x < ef->ntasks; ++x) /* asc est */ 624 { 625 if (X[x]->lct > Y[y]->lct) 626 { 627 /* X[x] is a task not belonging to the 628 * task intervals under consideration 629 */ 630 if (Ar + X[x]->area > (Y[y]->lct - X[x]->est) * cap) 631 { 632 /* 633 * X[x] must be after all tasks between 634 * X[x]->est..Y[y]->lct. 635 * We could set ordering booleans here. 636 */ 637 /* Apply lower bound G on starting time */ 638 upd_max(X[x]->lb, G(x)[X[x]->sz]); 639 } 640 641 /* If X[x] doesn't fit in before Y[y]->lct, it 642 * must start after _all_ tasks before Y[y]->lct 643 */ 644 if (H + ((double) X[x]->area)/cap > Y[y]->lct) 645 { 646 upd_max(X[x]->lb, g[X[x]->sz]); 647 } 648#ifdef BOUND3 649 if ((ef->option & OPT_CUBIC) && Ar > 0) 650 { 651 long Arp = Ar; 652 /* find the next member k of the task interval */ 653 int k = x; 654 while (X[k]->lct > Y[y]->lct) 655 ++k; 656 while (Arp > 0 && X[k]->est < X[x]->ect) 657 { 658 if (Arp + (X[x]->ect - X[k]->est) * Size(X[x]->sz) 659 > (Y[y]->lct - X[k]->est) * cap) 660 { 661 upd_max(X[x]->lb, G(x)[X[x]->sz]); 662 } 663 Arp -= X[k]->area; 664 ++k; 665 if (Arp > 0) 666 while (X[k]->lct > Y[y]->lct) 667 ++k; 668 } 669 } 670#endif 671 } 672 else /* X[x] is a member of some task interval */ 673 { 674 upd_max_f(H, X[x]->est + ((double) Ar)/cap); 675 Ar -= X[x]->area; 676 } 677#ifdef BOUND2 678 if (ef->option & OPT_CUBIC) 679 { 680 int w; 681 /* area of tasks w..y without x */ 682 long Arp = Ar; 683 /* what remains if x is first: */ 684 long ect_x = X[x]->ect < Y[y]->lct ? X[x]->ect : Y[y]->lct; 685 for (w = x-1; w >= 0; --w) /* desc est */ 686 { 687 if (X[w]->lct <= Y[y]->lct) 688 { 689 if (ef->ECT[w] <= X[x]->est) 690 break; 691 Arp += X[w]->area; 692 if (Arp + (ect_x - X[w]->est) * Size(X[x]->sz) 693 > (Y[y]->lct - X[w]->est) * cap) 694 /* x can't be first, must be after w */ 695 upd_max(X[x]->lb, ef->ECT[w]); 696 } 697 } 698 } 699#endif 700 } 701 } 702 } 703 704 Y = ef->asc_est; 705 X = ef->asc_lct; 706 for (y = ef->ntasks-1; y >= 0; --y) /* desc est */ 707 { 708 if (y == 0 || Y[y]->est != Y[y-1]->est) 709 { 710 Ar = 0; 711 l = DOMAIN_PINF; 712 g = G(0); /* first i in next loop */ 713 for (j = 0; j < ef->nsizes; ++j) 714 g[j] = DOMAIN_PINF; 715#ifdef BOUND2 716 ef->LST[0] = DOMAIN_MINF; 717#endif 718 719 for (i = 0; i < ef->ntasks; ++i) /* asc lct */ 720 { 721 if (X[i]->est >= Y[y]->est) 722 { 723 Ar += X[i]->area; 724 if (X[i]->lct - (Ar-1+cap)/cap < Y[y]->est) 725 return PFAIL; 726#ifdef BOUND2 727 upd_max(ef->LST[i], X[i]->lst); 728#endif 729 upd_min(l, X[i]->est); 730 for (j = 0; j < ef->nsizes; ++j) 731 { 732 long size_j = Size(j); 733 long rest = Ar - (X[i]->lct-l) * (cap-size_j); 734 if (rest > 0) 735 upd_min(g[j], X[i]->lct - (rest-1+size_j)/size_j); 736 } 737 } 738 if (i < ef->ntasks-1) 739 { 740 for (j = 0; j < ef->nsizes; ++j) 741 G(i+1)[j] = g[j]; 742 g = G(i+1); 743#ifdef BOUND2 744 ef->LST[i+1] = ef->LST[i]; 745#endif 746 } 747 } 748 749 H = (double) DOMAIN_PINF; 750 for (x = ef->ntasks-1; x >= 0; --x) /* desc lct */ 751 { 752 if (X[x]->est < Y[y]->est) 753 { 754 if (Ar + X[x]->area > (X[x]->lct - Y[y]->est) * cap) 755 upd_min(X[x]->ub, G(x)[X[x]->sz] - X[x]->dur); 756 757 if (H - ((double) X[x]->area)/cap < Y[y]->est) 758 upd_min(X[x]->ub, g[X[x]->sz] - X[x]->dur); 759#ifdef BOUND3 760 if ((ef->option & OPT_CUBIC) && Ar > 0) 761 { 762 long Arp = Ar; 763 int k = x; 764 while (X[k]->est < Y[y]->est) 765 --k; 766 while (Arp > 0 && X[k]->lct > X[x]->lst) 767 { 768 if (Arp + (X[k]->lct - X[x]->lst) * Size(X[x]->sz) 769 > (X[k]->lct - Y[y]->est) * cap) 770 { 771 upd_min(X[x]->ub, G(x)[X[x]->sz] - X[x]->dur); 772 } 773 Arp -= X[k]->area; 774 --k; 775 if (Arp > 0) 776 while (X[k]->est < Y[y]->est) 777 --k; 778 } 779 } 780#endif 781 } 782 else 783 { 784 upd_min_f(H, X[x]->lct - ((double) Ar)/cap); 785 Ar -= X[x]->area; 786 } 787#ifdef BOUND2 788 if (ef->option & OPT_CUBIC) 789 { 790 int w; 791 long Arp = Ar; 792 long lst_x = X[x]->lst > Y[y]->est ? X[x]->lst : Y[y]->est; 793 for (w = x+1; w < ef->ntasks; ++w) /* asc lct */ 794 { 795 if (X[w]->est >= Y[y]->est) 796 { 797 if (ef->LST[w] >= X[x]->lct) 798 break; 799 Arp += X[w]->area; 800 if (Arp + (X[w]->lct - lst_x) * Size(X[x]->sz) 801 > (X[w]->lct - Y[y]->est) * cap) 802 upd_min(X[x]->ub, ef->LST[w] - X[x]->dur); 803 } 804 } 805 } 806#endif 807 } 808 } 809 } 810 return PSUCCEED; 811} 812 813 814int 815ec_ef_quad( /* EfHandle */ ) 816{ 817 ef_t *ef; 818 int i, j, k; 819 task_t **Y; 820 long Sjk; 821 long Pjk; 822 long delta; 823 824 if (ec_get_handle(ec_arg(1), &ef_desc, (t_ext_ptr*)&ef) != PSUCCEED) 825 return TYPE_ERROR; 826 827 qsort((void*) (ef->asc_lct), ef->ntasks, sizeof(task_t*), _asc_lct); 828 829 Y = ef->asc_lct; 830 for (j = 0; j < ef->ntasks; ++j) /* asc lct */ 831 { 832 Pjk = 0; 833 delta = DOMAIN_PINF; 834 for (k = 0; k <= j; ++k) 835 { 836 if (Y[k]->lst >= Y[j]->lst) 837 Pjk += Y[k]->dur; 838 /* Sjk = DOMAIN_MINF; upd_min(delta, Y[k]->lct - Sjk); */ 839 ef->DELTA[k] = delta; 840 } 841 for (; k < ef->ntasks; ++k) 842 { 843 if (Y[k]->lst >= Y[j]->lst) 844 Pjk += Y[k]->dur; 845 Sjk = Pjk; 846 upd_min(delta, Y[k]->lct - Sjk); 847 ef->DELTA[k] = delta; 848 } 849 850 for (i = 0; i < ef->ntasks; ++i) 851 { 852 if (Y[i]->lst < Y[j]->lst) 853 { 854 if (Y[i]->lst > delta) 855 upd_max(Y[i]->lb, Y[j]->lst); 856 } 857 else 858 { 859 if ((i>0 && Y[i]->lst > ef->DELTA[i-1]) || Y[i]->est > delta) 860 upd_max(Y[i]->lb, Y[j]->lst); 861 } 862 } 863 } 864 865#if 0 866 qsort((void*) (ef->asc_est), ef->ntasks, sizeof(task_t*), _asc_est); 867 868 Y = ef->asc_est; 869 for (y = ef->ntasks-1; y >= 0; --y) /* desc est */ 870 { 871 872 } 873#endif 874 875 return PSUCCEED; 876} 877