+ /*
+ * analyze cycles to determine breakup
+ */
+cycleanalyze()
+{
+ arctype **cyclestack;
+ arctype **stkp;
+ arctype **arcpp;
+ arctype **endlist;
+ arctype *arcp;
+ nltype *nlp;
+ cltype *clp;
+ bool ret;
+ bool done;
+ int size;
+ int cycleno;
+
+ /*
+ * calculate the size of the cycle, and find nodes that
+ * exit the cycle as they are desirable targets to cut
+ * some of their parents
+ */
+ for ( done = TRUE , cycleno = 1 ; cycleno <= ncycle ; cycleno++ ) {
+ size = 0;
+ for (nlp = cyclenl[ cycleno ] . cnext; nlp; nlp = nlp -> cnext) {
+ size += 1;
+ nlp -> parentcnt = 0;
+ nlp -> flags &= ~HASCYCLEXIT;
+ for ( arcp = nlp -> parents; arcp; arcp = arcp -> arc_parentlist ) {
+ nlp -> parentcnt += 1;
+ if ( arcp -> arc_parentp -> cycleno != cycleno )
+ nlp -> flags |= HASCYCLEXIT;
+ }
+ }
+ if ( size <= cyclethreshold )
+ continue;
+ done = FALSE;
+ cyclestack = (arctype **) calloc( size + 1 , sizeof( arctype *) );
+ if ( cyclestack == 0 ) {
+ fprintf( stderr , "%s: No room for %d bytes of cycle stack\n" ,
+ whoami , ( size + 1 ) * sizeof( arctype * ) );
+ return;
+ }
+# ifdef DEBUG
+ if ( debug & BREAKCYCLE ) {
+ printf( "[cycleanalyze] starting cycle %d of %d, size %d\n" ,
+ cycleno , ncycle , size );
+ }
+# endif DEBUG
+ for ( nlp = cyclenl[ cycleno ] . cnext ; nlp ; nlp = nlp -> cnext ) {
+ stkp = &cyclestack[0];
+ nlp -> flags |= CYCLEHEAD;
+ ret = descend ( nlp , cyclestack , stkp );
+ nlp -> flags &= ~CYCLEHEAD;
+ if ( ret == FALSE )
+ break;
+ }
+ free( cyclestack );
+ if ( cyclecnt > 0 ) {
+ compresslist();
+ for ( clp = cyclehead ; clp ; ) {
+ endlist = &clp -> list[ clp -> size ];
+ for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
+ (*arcpp) -> arc_cyclecnt--;
+ cyclecnt--;
+ clp = clp -> next;
+ free( clp );
+ }
+ cyclehead = 0;
+ }
+ }
+# ifdef DEBUG
+ if ( debug & BREAKCYCLE ) {
+ printf("%s visited %d, viable %d, newcycle %d, oldcycle %d\n",
+ "[doarcs]" , visited , viable , newcycle , oldcycle);
+ }
+# endif DEBUG
+ return( done );
+}
+
+descend( node , stkstart , stkp )
+ nltype *node;
+ arctype **stkstart;
+ arctype **stkp;
+{
+ arctype *arcp;
+ bool ret;
+
+ for ( arcp = node -> children ; arcp ; arcp = arcp -> arc_childlist ) {
+# ifdef DEBUG
+ visited++;
+# endif DEBUG
+ if ( arcp -> arc_childp -> cycleno != node -> cycleno
+ || ( arcp -> arc_childp -> flags & VISITED )
+ || ( arcp -> arc_flags & DEADARC ) )
+ continue;
+# ifdef DEBUG
+ viable++;
+# endif DEBUG
+ *stkp = arcp;
+ if ( arcp -> arc_childp -> flags & CYCLEHEAD ) {
+ if ( addcycle( stkstart , stkp ) == FALSE )
+ return( FALSE );
+ continue;
+ }
+ arcp -> arc_childp -> flags |= VISITED;
+ ret = descend( arcp -> arc_childp , stkstart , stkp + 1 );
+ arcp -> arc_childp -> flags &= ~VISITED;
+ if ( ret == FALSE )
+ return( FALSE );
+ }
+}
+
+addcycle( stkstart , stkend )
+ arctype **stkstart;
+ arctype **stkend;
+{
+ arctype **arcpp;
+ arctype **stkloc;
+ arctype **stkp;
+ arctype **endlist;
+ arctype *minarc;
+ arctype *arcp;
+ cltype *clp;
+ int size;
+
+ size = stkend - stkstart + 1;
+ if ( size <= 1 )
+ return( TRUE );
+ for ( arcpp = stkstart , minarc = *arcpp ; arcpp <= stkend ; arcpp++ ) {
+ if ( *arcpp > minarc )
+ continue;
+ minarc = *arcpp;
+ stkloc = arcpp;
+ }
+ for ( clp = cyclehead ; clp ; clp = clp -> next ) {
+ if ( clp -> size != size )
+ continue;
+ stkp = stkloc;
+ endlist = &clp -> list[ size ];
+ for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) {
+ if ( *stkp++ != *arcpp )
+ break;
+ if ( stkp > stkend )
+ stkp = stkstart;
+ }
+ if ( arcpp == endlist ) {
+# ifdef DEBUG
+ oldcycle++;
+# endif DEBUG
+ return( TRUE );
+ }
+ }
+ clp = (cltype *)
+ calloc( 1 , sizeof ( cltype ) + ( size - 1 ) * sizeof( arctype * ) );
+ if ( clp == 0 ) {
+ fprintf( stderr , "%s: No room for %d bytes of subcycle storage\n" ,
+ whoami , sizeof ( cltype ) + ( size - 1 ) * sizeof( arctype * ) );
+ return( FALSE );
+ }
+ stkp = stkloc;
+ endlist = &clp -> list[ size ];
+ for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ ) {
+ arcp = *arcpp = *stkp++;
+ if ( stkp > stkend )
+ stkp = stkstart;
+ arcp -> arc_cyclecnt++;
+ if ( ( arcp -> arc_flags & ONLIST ) == 0 ) {
+ arcp -> arc_flags |= ONLIST;
+ arcp -> arc_next = archead;
+ archead = arcp;
+ }
+ }
+ clp -> size = size;
+ clp -> next = cyclehead;
+ cyclehead = clp;
+# ifdef DEBUG
+ newcycle++;
+ if ( debug & SUBCYCLELIST ) {
+ printsubcycle( clp );
+ }
+# endif DEBUG
+ cyclecnt++;
+ if ( cyclecnt >= CYCLEMAX )
+ return( FALSE );
+ return( TRUE );
+}
+
+compresslist()
+{
+ cltype *clp;
+ cltype **prev;
+ arctype **arcpp;
+ arctype **endlist;
+ arctype *arcp;
+ arctype *maxarcp;
+ arctype *maxexitarcp;
+ arctype *maxwithparentarcp;
+ arctype *maxnoparentarcp;
+ int maxexitcnt;
+ int maxwithparentcnt;
+ int maxnoparentcnt;
+ char *type;
+
+ maxexitcnt = 0;
+ maxwithparentcnt = 0;
+ maxnoparentcnt = 0;
+ for ( endlist = &archead , arcp = archead ; arcp ; ) {
+ if ( arcp -> arc_cyclecnt == 0 ) {
+ arcp -> arc_flags &= ~ONLIST;
+ *endlist = arcp -> arc_next;
+ arcp -> arc_next = 0;
+ arcp = *endlist;
+ continue;
+ }
+ if ( arcp -> arc_childp -> flags & HASCYCLEXIT ) {
+ if ( arcp -> arc_cyclecnt > maxexitcnt ||
+ ( arcp -> arc_cyclecnt == maxexitcnt &&
+ arcp -> arc_cyclecnt < maxexitarcp -> arc_count ) ) {
+ maxexitcnt = arcp -> arc_cyclecnt;
+ maxexitarcp = arcp;
+ }
+ } else if ( arcp -> arc_childp -> parentcnt > 1 ) {
+ if ( arcp -> arc_cyclecnt > maxwithparentcnt ||
+ ( arcp -> arc_cyclecnt == maxwithparentcnt &&
+ arcp -> arc_cyclecnt < maxwithparentarcp -> arc_count ) ) {
+ maxwithparentcnt = arcp -> arc_cyclecnt;
+ maxwithparentarcp = arcp;
+ }
+ } else {
+ if ( arcp -> arc_cyclecnt > maxnoparentcnt ||
+ ( arcp -> arc_cyclecnt == maxnoparentcnt &&
+ arcp -> arc_cyclecnt < maxnoparentarcp -> arc_count ) ) {
+ maxnoparentcnt = arcp -> arc_cyclecnt;
+ maxnoparentarcp = arcp;
+ }
+ }
+ endlist = &arcp -> arc_next;
+ arcp = arcp -> arc_next;
+ }
+ if ( maxexitcnt > 0 ) {
+ /*
+ * first choice is edge leading to node with out-of-cycle parent
+ */
+ maxarcp = maxexitarcp;
+# ifdef DEBUG
+ type = "exit";
+# endif DEBUG
+ } else if ( maxwithparentcnt > 0 ) {
+ /*
+ * second choice is edge leading to node with at least one
+ * other in-cycle parent
+ */
+ maxarcp = maxwithparentarcp;
+# ifdef DEBUG
+ type = "internal";
+# endif DEBUG
+ } else {
+ /*
+ * last choice is edge leading to node with only this arc as
+ * a parent (as it will now be orphaned)
+ */
+ maxarcp = maxnoparentarcp;
+# ifdef DEBUG
+ type = "orphan";
+# endif DEBUG
+ }
+ maxarcp -> arc_flags |= DEADARC;
+ maxarcp -> arc_childp -> parentcnt -= 1;
+ maxarcp -> arc_childp -> npropcall -= maxarcp -> arc_count;
+# ifdef DEBUG
+ if ( debug & BREAKCYCLE ) {
+ printf( "%s delete %s arc: %s (%d) -> %s from %d cycle(s)\n" ,
+ "[compresslist]" , type , maxarcp -> arc_parentp -> name ,
+ maxarcp -> arc_count , maxarcp -> arc_childp -> name ,
+ maxarcp -> arc_cyclecnt );
+ }
+# endif DEBUG
+ printf( "\t%s to %s with %d calls\n" , maxarcp -> arc_parentp -> name ,
+ maxarcp -> arc_childp -> name , maxarcp -> arc_count );
+ prev = &cyclehead;
+ for ( clp = cyclehead ; clp ; ) {
+ endlist = &clp -> list[ clp -> size ];
+ for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
+ if ( (*arcpp) -> arc_flags & DEADARC )
+ break;
+ if ( arcpp == endlist ) {
+ prev = &clp -> next;
+ clp = clp -> next;
+ continue;
+ }
+ for ( arcpp = clp -> list ; arcpp < endlist ; arcpp++ )
+ (*arcpp) -> arc_cyclecnt--;
+ cyclecnt--;
+ *prev = clp -> next;
+ clp = clp -> next;
+ free( clp );
+ }
+}
+
+#ifdef DEBUG
+printsubcycle( clp )
+ cltype *clp;
+{
+ arctype **arcpp;
+ arctype **endlist;
+
+ arcpp = clp -> list;
+ printf( "%s <cycle %d>\n" , (*arcpp) -> arc_parentp -> name ,
+ (*arcpp) -> arc_parentp -> cycleno ) ;
+ for ( endlist = &clp -> list[ clp -> size ]; arcpp < endlist ; arcpp++ )
+ printf( "\t(%d) -> %s\n" , (*arcpp) -> arc_count ,
+ (*arcpp) -> arc_childp -> name ) ;
+}
+#endif DEBUG
+
projects / unix-history / commitdiff