1extern void abort (void); 2 3typedef struct PgHdr PgHdr; 4typedef unsigned char u8; 5struct PgHdr { 6 unsigned int pgno; 7 PgHdr *pNextHash, *pPrevHash; 8 PgHdr *pNextFree, *pPrevFree; 9 PgHdr *pNextAll; 10 u8 inJournal; 11 short int nRef; 12 PgHdr *pDirty, *pPrevDirty; 13 unsigned int notUsed; 14}; 15 16static inline PgHdr *merge_pagelist(PgHdr *pA, PgHdr *pB) 17{ 18 PgHdr result; 19 PgHdr *pTail; 20 pTail = &result; 21 while( pA && pB ){ 22 if( pA->pgno<pB->pgno ){ 23 pTail->pDirty = pA; 24 pTail = pA; 25 pA = pA->pDirty; 26 }else{ 27 pTail->pDirty = pB; 28 pTail = pB; 29 pB = pB->pDirty; 30 } 31 } 32 if( pA ){ 33 pTail->pDirty = pA; 34 }else if( pB ){ 35 pTail->pDirty = pB; 36 }else{ 37 pTail->pDirty = 0; 38 } 39 return result.pDirty; 40} 41 42PgHdr * __attribute__((noinline)) sort_pagelist(PgHdr *pIn) 43{ 44 PgHdr *a[25], *p; 45 int i; 46 __builtin_memset (a, 0, sizeof (a)); 47 while( pIn ){ 48 p = pIn; 49 pIn = p->pDirty; 50 p->pDirty = 0; 51 for(i=0; i<25 -1; i++){ 52 if( a[i]==0 ){ 53 a[i] = p; 54 break; 55 }else{ 56 p = merge_pagelist(a[i], p); 57 a[i] = 0; 58 } 59 } 60 if( i==25 -1 ){ 61 a[i] = merge_pagelist(a[i], p); 62 } 63 } 64 p = a[0]; 65 for(i=1; i<25; i++){ 66 p = merge_pagelist (p, a[i]); 67 } 68 return p; 69} 70 71int main() 72{ 73 PgHdr a[5]; 74 PgHdr *p; 75 a[0].pgno = 5; 76 a[0].pDirty = &a[1]; 77 a[1].pgno = 4; 78 a[1].pDirty = &a[2]; 79 a[2].pgno = 1; 80 a[2].pDirty = &a[3]; 81 a[3].pgno = 3; 82 a[3].pDirty = 0; 83 p = sort_pagelist (&a[0]); 84 if (p->pDirty == p) 85 abort (); 86 return 0; 87} 88