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