@@ -111,11 +111,11 @@ static bool TopoSort(DumpableObject **objs,
111
111
static void addHeapElement (int val ,int * heap ,int heapLength );
112
112
static int removeHeapElement (int * heap ,int heapLength );
113
113
static void findDependencyLoops (DumpableObject * * objs ,int nObjs ,int totObjs );
114
- static bool findLoop (DumpableObject * obj ,
114
+ static int findLoop (DumpableObject * obj ,
115
115
DumpId startPoint ,
116
+ bool * processed ,
116
117
DumpableObject * * workspace ,
117
- int depth ,
118
- int * newDepth );
118
+ int depth );
119
119
static void repairDependencyLoop (DumpableObject * * loop ,
120
120
int nLoop );
121
121
static void describeDumpableObject (DumpableObject * obj ,
@@ -506,56 +506,50 @@ static void
506
506
findDependencyLoops (DumpableObject * * objs ,int nObjs ,int totObjs )
507
507
{
508
508
/*
509
- * We use a workspace array, the initial part of which stores objects
510
- * already processed, and the rest of which is used as temporary space to
511
- * try to build a loop in.This is convenient because we do not care
512
- * about loops involving already-processed objects (see notes above); we
513
- * can easily reject such loops in findLoop() because of this
514
- * representation.After we identify and process a loop, we can add it to
515
- * the initial part of the workspace just by moving the boundary pointer.
516
- *
517
- * When we determine that an object is not part of any interesting loop,
518
- * we also add it to the initial part of the workspace. This is not
519
- * necessary for correctness, but saves later invocations of findLoop()
520
- * from uselessly chasing references to such an object.
521
- *
522
- * We make the workspace large enough to hold all objects in the original
523
- * universe. This is probably overkill, but it's provably enough space...
509
+ * We use two data structures here. One is a bool array processed[],
510
+ * which is indexed by dump ID and marks the objects already processed
511
+ * during this invocation of findDependencyLoops(). The other is a
512
+ * workspace[] array of DumpableObject pointers, in which we try to build
513
+ * lists of objects constituting loops. We make workspace[] large enough
514
+ * to hold all the objects, which is huge overkill in most cases but could
515
+ * theoretically be necessary if there is a single dependency chain
516
+ * linking all the objects.
524
517
*/
518
+ bool * processed ;
525
519
DumpableObject * * workspace ;
526
- int initiallen ;
527
520
bool fixedloop ;
528
521
int i ;
529
522
523
+ processed = (bool * )pg_calloc (getMaxDumpId ()+ 1 ,sizeof (bool ));
530
524
workspace = (DumpableObject * * )pg_malloc (totObjs * sizeof (DumpableObject * ));
531
- initiallen = 0 ;
532
525
fixedloop = false;
533
526
534
527
for (i = 0 ;i < nObjs ;i ++ )
535
528
{
536
529
DumpableObject * obj = objs [i ];
537
- int newlen ;
530
+ int looplen ;
531
+ int j ;
538
532
539
- workspace [ initiallen ] = NULL ; /* see test below */
533
+ looplen = findLoop ( obj , obj -> dumpId , processed , workspace , 0 );
540
534
541
- if (findLoop ( obj , obj -> dumpId , workspace , initiallen , & newlen ) )
535
+ if (looplen > 0 )
542
536
{
543
- /* Found a loop of length newlen - initiallen */
544
- repairDependencyLoop (& workspace [initiallen ],newlen - initiallen );
545
- /* Add loop members to workspace */
546
- initiallen = newlen ;
537
+ /* Found a loop, repair it */
538
+ repairDependencyLoop (workspace ,looplen );
547
539
fixedloop = true;
540
+ /* Mark loop members as processed */
541
+ for (j = 0 ;j < looplen ;j ++ )
542
+ processed [workspace [j ]-> dumpId ]= true;
548
543
}
549
544
else
550
545
{
551
546
/*
552
- *Didn't find a loop, but add this object to workspace anyway,
553
- *unless it's already present. We piggyback on the test that
554
- * findLoop()already did: it won't have tentatively added obj to
555
- *workspace if it's already present .
547
+ *There's no loop starting at this object, but mark it processed
548
+ *anyway. This is not necessary for correctness, but saves later
549
+ *invocations of findLoop()from uselessly chasing references to
550
+ *such an object .
556
551
*/
557
- if (workspace [initiallen ]== obj )
558
- initiallen ++ ;
552
+ processed [obj -> dumpId ]= true;
559
553
}
560
554
}
561
555
@@ -564,45 +558,51 @@ findDependencyLoops(DumpableObject **objs, int nObjs, int totObjs)
564
558
exit_horribly (modulename ,"could not identify dependency loop\n" );
565
559
566
560
free (workspace );
561
+ free (processed );
567
562
}
568
563
569
564
/*
570
565
* Recursively search for a circular dependency loop that doesn't include
571
- * anyexisting workspace members .
566
+ * anyalready-processed objects .
572
567
*
573
568
*obj: object we are examining now
574
569
*startPoint: dumpId of starting object for the hoped-for circular loop
575
- *workspace[]: work array for previously processed and current objects
570
+ *processed[]: flag array marking already-processed objects
571
+ *workspace[]: work array in which we are building list of loop members
576
572
*depth: number of valid entries in workspace[] at call
577
- *newDepth: if successful, set to new number of workspace[] entries
578
573
*
579
- * On success,*newDepth isset and workspace[]entries depth..*newDepth-1
580
- *are filled with pointers to the members of the loop.
574
+ * On success,the length of the loop isreturned, and workspace[]is filled
575
+ * with pointers to the members of the loop. On failure, we return 0 .
581
576
*
582
577
* Note: it is possible that the given starting object is a member of more
583
578
* than one cycle; if so, we will find an arbitrary one of the cycles.
584
579
*/
585
- static bool
580
+ static int
586
581
findLoop (DumpableObject * obj ,
587
582
DumpId startPoint ,
583
+ bool * processed ,
588
584
DumpableObject * * workspace ,
589
- int depth ,
590
- int * newDepth )
585
+ int depth )
591
586
{
592
587
int i ;
593
588
594
589
/*
595
- * Reject if obj is already present in workspace. This test serves three
596
- * purposes: it prevents us from finding loops that overlap
597
- * previously-processed loops, it prevents us from going into infinite
598
- * recursion if we are given a startPoint object that links to a cycle
599
- * it's not a member of, and it guarantees that we can't overflow the
600
- * allocated size of workspace[].
590
+ * Reject if obj is already processed. This test prevents us from finding
591
+ * loops that overlap previously-processed loops.
592
+ */
593
+ if (processed [obj -> dumpId ])
594
+ return 0 ;
595
+
596
+ /*
597
+ * Reject if obj is already present in workspace. This test prevents us
598
+ * from going into infinite recursion if we are given a startPoint object
599
+ * that links to a cycle it's not a member of, and it guarantees that we
600
+ * can't overflow the allocated size of workspace[].
601
601
*/
602
602
for (i = 0 ;i < depth ;i ++ )
603
603
{
604
604
if (workspace [i ]== obj )
605
- return false ;
605
+ return 0 ;
606
606
}
607
607
608
608
/*
@@ -616,10 +616,7 @@ findLoop(DumpableObject *obj,
616
616
for (i = 0 ;i < obj -> nDeps ;i ++ )
617
617
{
618
618
if (obj -> dependencies [i ]== startPoint )
619
- {
620
- * newDepth = depth ;
621
- return true;
622
- }
619
+ return depth ;
623
620
}
624
621
625
622
/*
@@ -628,18 +625,20 @@ findLoop(DumpableObject *obj,
628
625
for (i = 0 ;i < obj -> nDeps ;i ++ )
629
626
{
630
627
DumpableObject * nextobj = findObjectByDumpId (obj -> dependencies [i ]);
628
+ int newDepth ;
631
629
632
630
if (!nextobj )
633
631
continue ;/* ignore dependencies on undumped objects */
634
- if (findLoop (nextobj ,
635
- startPoint ,
636
- workspace ,
637
- depth ,
638
- newDepth ))
639
- return true;
632
+ newDepth = findLoop (nextobj ,
633
+ startPoint ,
634
+ processed ,
635
+ workspace ,
636
+ depth );
637
+ if (newDepth > 0 )
638
+ return newDepth ;
640
639
}
641
640
642
- return false ;
641
+ return 0 ;
643
642
}
644
643
645
644
/*