1  extern void abort (void);
       2  
       3  typedef struct PgHdr PgHdr;
       4  typedef unsigned char u8;
       5  struct 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  
      16  static 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  
      42  PgHdr * __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  
      71  int 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  }