ben 2004/05/10 12:51:03
Modified: hooks apr_hooks.c
Log:
Drag forward topological sort changes.
Revision Changes Path
1.51 +28 -3 apr-util/hooks/apr_hooks.c
Index: apr_hooks.c
===================================================================
RCS file: /home/cvs/apr-util/hooks/apr_hooks.c,v
retrieving revision 1.50
retrieving revision 1.51
diff -u -r1.50 -r1.51
--- apr_hooks.c 13 Feb 2004 09:55:26 -0000 1.50
+++ apr_hooks.c 10 May 2004 19:51:03 -0000 1.51
@@ -126,6 +126,15 @@
return pData;
}
+/* Topologically sort, dragging out-of-order items to the front. Note that
+ this tends to preserve things that want to be near the front better, and
+ changing that behaviour might compromise some of Apache's behaviour (in
+ particular, mod_log_forensic might otherwise get pushed to the end, and
+ core.c's log open function used to end up at the end when pushing items
+ to the back was the methedology). Also note that the algorithm could
+ go back to its original simplicity by sorting from the back instead of
+ the front.
+*/
static TSort *tsort(TSort *pData,int nItems)
{
int nTotal;
@@ -138,8 +147,23 @@
for(n=0 ; ; ++n) {
if(n == nItems)
assert(0); /* we have a loop... */
- if(!pData[n].pNext && !pData[n].nPredecessors)
- break;
+ if(!pData[n].pNext) {
+ if(pData[n].nPredecessors) {
+ for(k=0 ; ; ++k) {
+ assert(k < nItems);
+ if(pData[n].ppPredecessors[k])
+ break;
+ }
+ for(i=0 ; ; ++i) {
+ assert(i < nItems);
+ if(&pData[i] == pData[n].ppPredecessors[k]) {
+ n=i-1;
+ break;
+ }
+ }
+ } else
+ break;
+ }
}
if(pTail)
pTail->pNext=&pData[n];
@@ -148,9 +172,10 @@
pTail=&pData[n];
pTail->pNext=pTail; /* fudge it so it looks linked */
for(i=0 ; i < nItems ; ++i)
- for(k=0 ; pData[i].ppPredecessors[k] ; ++k)
+ for(k=0 ; k < nItems ; ++k)
if(pData[i].ppPredecessors[k] == &pData[n]) {
--pData[i].nPredecessors;
+ pData[i].ppPredecessors[k]=NULL;
break;
}
}
