#include <stdio.h>
#include <stdlib.h>
#include <ntddk.h>
#include <app.avl.h>
RTL_GENERIC_COMPARE_RESULTS
CompareRoutine(
__in struct _RTL_AVL_TABLE *Table,
__in PVOID FirstStruct,
__in PVOID SecondStruct
)
{
int i, j, k1, k2;
appBLOCK A1, A2;
A1 = ((struct appTRIPLET*)FirstStruct)->A;
k1 = ((struct appTRIPLET*)FirstStruct)->k;
A2 = ((struct appTRIPLET*)SecondStruct)->A;
k2 = ((struct appTRIPLET*)SecondStruct)->k;
if (k1 == 1 && (A1 >= A2 && A1 < A2 + k2)) return GenericEqual;
if (k2 == 1 && (A2 >= A1 && A2 < A1 + k1)) return GenericEqual;
if (A1 > A2) return GenericGreaterThan;
if (A1 < A2) return GenericLessThan;
return GenericEqual;
}
PVOID
Allocate_Routine(
__in struct _RTL_AVL_TABLE *Table,
__in CLONG ByteSize
)
{
void *temp;
temp = malloc(ByteSize);
return temp;
}
VOID
FreeRoutine(
__in struct _RTL_AVL_TABLE *Table,
__in PVOID Buffer
)
{
free(Buffer);
}
appTRIPLET*
addNode(appBLOCK A, appBLOCK B, appNUMBER k, PRTL_AVL_TABLE Table)
{
appTRIPLET T = {A, B, k}, *ptr;
BOOLEAN ok;
ptr = RtlInsertElementGenericTableAvl(Table, &T, sizeof(T), &ok);
return ptr;
}
BOOLEAN
existNode(appBLOCK A, PRTL_AVL_TABLE Table)
{
appTRIPLET T, *P;
T.A = A;
T.k = 1;
P = (appTRIPLET*)RtlLookupElementGenericTableAvl(Table, &T);
if(P == NULL) return FALSE;
return TRUE;
}
appTRIPLET*
findNode(appBLOCK A, PRTL_AVL_TABLE Table)
{
appTRIPLET T, *P;
T.A = A;
T.k = 1;
P = RtlLookupElementGenericTableAvl(Table, &T);
return P;
}
BOOLEAN
deleteNode(appBLOCK A, PRTL_AVL_TABLE Table)
{
BOOLEAN ok;
appTRIPLET *P = findNode(A, Table);
ok = RtlDeleteElementGenericTableAvl(Table, P);
return ok;
}
appTRIPLET*
nextNode(appBLOCK A, PRTL_AVL_TABLE Table)
{
appTRIPLET *ptr, *temp;
PVOID restart;
temp = findNode(A, Table);
if(temp != NULL)
{
restart = (PVOID)((char*)(temp) - 0x20);
ptr = (appTRIPLET*)RtlEnumerateGenericTableWithoutSplayingAvl(Table, &restart);
return ptr;
}
temp = addNode(A, (appBLOCK)NULL, 1, Table);
restart = (PVOID)((char*)(temp) - 0x20);
ptr = (appTRIPLET*)RtlEnumerateGenericTableWithoutSplayingAvl(Table, &restart);
deleteNode(A, Table);
return ptr;
}
appBLOCK
checkNode(appBLOCK A, PRTL_AVL_TABLE Table)
{
appTRIPLET T, *P = findNode(A, Table);
if(P == NULL) return (appBLOCK)NULL;
return P->B + (A - P->A);
}
appTRIPLET**
checkArrNode(appBLOCK A, appNUMBER k, PRTL_AVL_TABLE Table)
{
ULONG i;
appBLOCK checkPoint;
appTRIPLET PointLeft, PointRight,
*IterLeft, *IterRight,
*EdgeLeft, *EdgeRight,
*EdgeInnerLeft, *EdgeInnerRight,
*tmp, *ptr,
**Buffer;
PVOID restart;
BOOLEAN ok;
//Searching points
PointLeft.A = A;
PointLeft.k = 1;
PointRight.A = A + k - 1;
PointRight.k = 1;
//Check edge points
if(!existNode(PointLeft.A, Table) || !existNode(PointRight.A - 1, Table))
{
return NULL;
}
//Iterate crossing intervals, check interruptions
IterLeft = findNode(PointLeft.A, Table);
IterRight = nextNode(PointRight.A, Table);
EdgeLeft = IterLeft;
EdgeRight = findNode(PointRight.A, Table);
restart = (PVOID)((char*)(IterLeft) - 0x20);
ptr = IterLeft;
checkPoint = ptr->A;
for(i = 0; ptr != IterRight; i++)
{
if(ptr->A != checkPoint)
{
return NULL;
}
checkPoint += ptr->k;
ptr = nextNode(ptr->A, Table);
}
//Allocate memory, insert pointers
Buffer = (appTRIPLET**) malloc(sizeof(appTRIPLET*) * (i + 3));
EdgeInnerLeft = (appTRIPLET* ) malloc(sizeof(appTRIPLET ));
EdgeInnerRight = (appTRIPLET* ) malloc(sizeof(appTRIPLET ));
//Left Edge
restart = (PVOID)((char*)(IterLeft) - 0x20);
ptr = IterLeft;
if(IterLeft->A == A && IterLeft->k == k) // case 1
{
free(EdgeInnerLeft);
printf("Buffer[%d] = NULL\n", i); Buffer[i] = NULL;
printf("Buffer[%d] = ptr\n", i+1); Buffer[i+1] = ptr;
printf("Buffer[%d] = NULL\n", i+2); Buffer[i+2] = NULL;
printf("Buffer[%d] = NULL\n", i+3); Buffer[i+3] = NULL;
return Buffer;
}
else
if(A < IterLeft->A + IterLeft->k || A + k < IterLeft->A + IterLeft->k) // case 2 3 4
{
EdgeInnerLeft->A = A;
EdgeInnerLeft->B = IterLeft->B + (A - IterLeft->A);
EdgeInnerLeft->k = k;
printf("Buffer[%d] = NULL\n", i); Buffer[i] = EdgeInnerLeft;
printf("Buffer[%d] = NULL\n", i+1); Buffer[i+1] = NULL;
printf("Buffer[%d] = NULL\n", i+2); Buffer[i+2] = NULL;
printf("Buffer[%d] = NULL\n", i+3); Buffer[i+3] = NULL;
Return Buffer;
}
// case 5 6 7 8
EdgeInnerLeft->A = A;
EdgeInnerLeft->B = IterLeft->B + (A - IterLeft->A);
EdgeInnerLeft->k = IterLeft->k - (A - IterLeft->A);
printf("Buffer[%d] = EdgeInnerLeft\n", i); Buffer[i] = EdgeInnerLeft;
i++;
printf("Buffer[%d] = NULL\n", i); Buffer[i] = NULL;
//Middle
for(i = 0; ptr != IterRight; i++, ptr = nextNode(ptr->A, Table))
{
else
if(nextNode(ptr->A, Table) == IterRight)
{
printf("Buffer[%d] = NULL\n", i); Buffer[i] = NULL;
i++;
if(A == ptr->A)
{
free(EdgeInnerRight);
}
else
if(A + k == ptr->A + ptr->k)
{
free(EdgeInnerRight);
printf("Buffer[%d] = ptr\n", i); Buffer[i] = ptr;
i++;
}
else
{
EdgeInnerRight->A = ptr->A;
EdgeInnerRight->B = ptr->B;
EdgeInnerRight->k = A + k - ptr->A;
printf("Buffer[%d] = EdgeInnerRight\n", i); Buffer[i] = EdgeInnerRight;
i++;
}
printf("Buffer[%d] = NULL\n", i); Buffer[i] = NULL;
break;
}
else
{
printf("Buffer[%d] = ptr\n", i); Buffer[i] = ptr;
}
}
//Right Edge
printf("---Buffer[0]->A = %d\n", Buffer[0]->A);
printf("return Buffer\n\n"); return Buffer;
}
BOOLEAN
mapNode(appBLOCK A, appBLOCK B, appNUMBER k, PRTL_AVL_TABLE Table)
{
BOOLEAN ok;
appTRIPLET New,
PointLeft, PointRight,
*IterLeft, *IterRight,
*EdgeLeft, *EdgeRight,
EdgeOuterLeft, EdgeOuterRight,
*tmp, *ptr;
PVOID restart;
//Find the edge intervals
PointLeft.A = A;
PointLeft.k = 1;
PointRight.A = A + k;
PointRight.k = 1;
if(existNode(PointLeft.A, Table))
{
IterLeft = findNode(PointLeft.A, Table);
EdgeLeft = IterLeft;
}
else
{
IterLeft = nextNode(PointLeft.A, Table);
EdgeLeft = NULL;
}
if(existNode(PointRight.A, Table))
{
EdgeRight = findNode(PointRight.A, Table);
IterRight = nextNode(PointRight.A, Table);
}
else
{
IterRight = nextNode(PointRight.A, Table);
EdgeRight = NULL;
}
//Split edge intervals
if(EdgeLeft != NULL)
{
EdgeOuterLeft.A = EdgeLeft->A;
EdgeOuterLeft.B = EdgeLeft->B;
EdgeOuterLeft.k = PointLeft.A - EdgeLeft->A;
// EdgeLeft = &EdgeOuterLeft;
}
if(EdgeRight != NULL)
{
EdgeOuterRight.A = PointRight.A;
EdgeOuterRight.B = EdgeRight->B + (PointRight.A - EdgeRight->A);
EdgeOuterRight.k = (EdgeRight->A + EdgeRight->k) - PointRight.A;
// EdgeRight = &PointRight;
}
// Delete crossing intervals
restart = (PVOID)((char*)(IterLeft) - 0x20);
for(ptr = IterLeft; ptr != IterRight; )
{
tmp = ptr;
ptr = nextNode(ptr->A, Table);
RtlDeleteElementGenericTableAvl(Table, tmp);
}
//Add the main interval
New.A = A;
New.B = B;
New.k = k;
RtlInsertElementGenericTableAvl(Table, &New, sizeof(New), &ok);
//Add the splitted intervals
if(EdgeLeft != NULL) addNode(EdgeOuterLeft.A, EdgeOuterLeft.B, EdgeOuterLeft.k, Table);
if(EdgeRight != NULL) addNode(EdgeOuterRight.A, EdgeOuterRight.B, EdgeOuterRight.k, Table);
return ok;
}
BOOLEAN
unmapNode(appBLOCK A, appNUMBER k, PRTL_AVL_TABLE Table)
{
BOOLEAN ok;
mapNode(A, (appBLOCK)NULL, k, Table);
ok = deleteNode(A, Table);
return ok;
}