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