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