Windows System Software -- Consulting, Training, Development -- Unique Expertise, Guaranteed Results

Sept/Oct 2019 Issue of The NT Insider available


Download PDF here: http://insider.osr.com/2019/ntinsider_2019_01.pdf

It’s a particularly BIG issue, too: 40 pages of technical goodness, ranging from WDF to Minifilters. Check it out.
Before Posting...
Please check out the Community Guidelines in the Announcements and Administration Category.

Re: Need to Sample source for _RTL_AVL_TABLE

Gabriel_BerceaGabriel_Bercea Member - All Emails Posts: 482
You can checkout the "AvScan File System Minifilter Driver" sample from
Microsoft. It uses tables to maintain a per file stream state cache in.
Also make sure you very carefully read the documentation. There are a few
things that are tricky and you might miss at first read, especially if your
table contain pointers that you might need to free before deleting the item
in the table.
Use verifier to make sure you are not leaking anything either by forgetting
to free or by not synchronizing properly.

Regards,
Gabriel
www.kasardia.com

On Wed, Jul 20, 2016 at 9:11 AM, wrote:

> I need to implement Page table in KMDF bus driver. In that I should
> maintain the pages i AVL Tree .
>
> I have gone through msdn . In this link :
> https://msdn.microsoft.com/en-us/library/windows/hardware/ff553327(v=vs.85).aspx
> ,a list of relevant routines for this tree has been given.
>
> But it will be very useful , if I get any sample source ,so that I can
> make it out clear understanding and how such routines are used.
>
> Because ,in the AVL initialization Routine itself am confused a lot. It
> is having completion .allocate,free routines. The parameters for such
> routines are quite confusing.
>
> How such Routines should be used? AM not much clear about it.
>
> So,can anyone tell me where can i get the sample source for this AVL Tree
> implementation.
>
> ---
> NTDEV is sponsored by OSR
>
> Visit the list online at: <
> http://www.osronline.com/showlists.cfm?list=ntdev>;
>
> MONTHLY seminars on crash dump analysis, WDF, Windows internals and
> software drivers!
> Details at
>
> To unsubscribe, visit the List Server section of OSR Online at <
> http://www.osronline.com/page.cfm?name=ListServer>;
>



--
Bercea. G.

Cheers,
Gabriel

Comments

  • Jamey_KirbyJamey_Kirby Member - All Emails Posts: 438
    AVL is a bit heavy. If you want something just as fast, open source, and
    extremely easy to understand, try my kernel-mode skiplist implementation. I
    modeled it to use nearly the same interface semantics as RTL_GENERIC_TABLE.
    It is available on GitHub. https://github.com/jameykirby/public

    On Thu, Jul 21, 2016 at 7:10 PM wrote:

    > At one point, The Microsoft's AVL tree implementation was the one described
    > in Knuth, "The Art of Computer Programming, Volume 3, Sorting and
    > Searching".
    >
    > I don't know if that has changed over time but the important think is that
    > the implementation is exported to usermode with NTDLL.DLL. You can test the
    > API in usermode with large collections of data. The WIN32 UI and the
    > console
    > are probably easier to use for this purpose. Here is a header (AVL.H) you
    > can
    > use to test the API:
    >
    > /* AVL.H
    >
    > Copyright (c) Microsoft Corporation. All rights reserved.
    >
    > For testing purpose only !
    >
    > This material was copied from the WDK's NTDDK.H header
    > to use Microsoft's AVL tree implementation in usermode.
    >
    > Functions whose prototype begins with NTSYSAPI are exported
    > by NTDLL.DLL. ntdll.lib must be added to the list of libraries
    > imported by the project or any (.c or .cpp) source file that
    > calls one of these functions must contain the line:
    >
    > #pragma comment(lib,"ntdll.lib")
    >
    > */
    >
    >
    > #ifndef __AVL_TREE_HEADER
    > #define __AVL_TREE_HEADER
    >
    > /* We need Windows Internal defs and typedefs here*/
    > #include
    >
    > #ifdef __cplusplus
    > extern "C" {
    > #endif
    >
    > //AVL Tree defs and typedefs
    >
    > typedef enum _RTL_GENERIC_COMPARE_RESULTS {
    > GenericLessThan,
    > GenericGreaterThan,
    > GenericEqual
    > } RTL_GENERIC_COMPARE_RESULTS;
    >
    > typedef
    > RTL_GENERIC_COMPARE_RESULTS
    > NTAPI
    > RTL_AVL_COMPARE_ROUTINE (
    > _In_ struct _RTL_AVL_TABLE *Table,
    > _In_ PVOID FirstStruct,
    > _In_ PVOID SecondStruct
    > );
    > typedef RTL_AVL_COMPARE_ROUTINE *PRTL_AVL_COMPARE_ROUTINE;
    >
    > typedef
    > PVOID
    > NTAPI
    > RTL_AVL_ALLOCATE_ROUTINE (
    > _In_ struct _RTL_AVL_TABLE *Table,
    > _In_ ULONG ByteSize
    > );
    > typedef RTL_AVL_ALLOCATE_ROUTINE *PRTL_AVL_ALLOCATE_ROUTINE;
    >
    > typedef
    > VOID
    > NTAPI
    > RTL_AVL_FREE_ROUTINE (
    > _In_ struct _RTL_AVL_TABLE *Table,
    > _In_ PVOID Buffer
    > );
    > typedef RTL_AVL_FREE_ROUTINE *PRTL_AVL_FREE_ROUTINE;
    >
    > typedef struct _RTL_BALANCED_LINKS {
    > struct _RTL_BALANCED_LINKS *Parent;
    > struct _RTL_BALANCED_LINKS *LeftChild;
    > struct _RTL_BALANCED_LINKS *RightChild;
    > CHAR Balance;
    > UCHAR Reserved[3];
    > } RTL_BALANCED_LINKS;
    > typedef RTL_BALANCED_LINKS *PRTL_BALANCED_LINKS;
    >
    > typedef struct _RTL_AVL_TABLE {
    > RTL_BALANCED_LINKS BalancedRoot;
    > PVOID OrderedPointer;
    > ULONG WhichOrderedElement;
    > ULONG NumberGenericTableElements;
    > ULONG DepthOfTree;
    > PRTL_BALANCED_LINKS RestartKey;
    > ULONG DeleteCount;
    > PRTL_AVL_COMPARE_ROUTINE CompareRoutine;
    > PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine;
    > PRTL_AVL_FREE_ROUTINE FreeRoutine;
    > PVOID TableContext;
    > } RTL_AVL_TABLE;
    > typedef RTL_AVL_TABLE *PRTL_AVL_TABLE;
    >
    > NTSYSAPI
    > VOID
    > NTAPI
    > RtlInitializeGenericTableAvl (
    > _Out_ PRTL_AVL_TABLE Table,
    > _In_ PRTL_AVL_COMPARE_ROUTINE CompareRoutine,
    > _In_ PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine,
    > _In_ PRTL_AVL_FREE_ROUTINE FreeRoutine,
    > _In_opt_ PVOID TableContext
    > );
    >
    > NTSYSAPI
    > PVOID
    > NTAPI
    > RtlInsertElementGenericTableAvl (
    > _In_ PRTL_AVL_TABLE Table,
    > _In_reads_bytes_(BufferSize) PVOID Buffer,
    > _In_ ULONG BufferSize,
    > _Out_opt_ PBOOLEAN NewElement
    > );
    >
    > NTSYSAPI
    > BOOLEAN
    > NTAPI
    > RtlDeleteElementGenericTableAvl (
    > _In_ PRTL_AVL_TABLE Table,
    > _In_ PVOID Buffer
    > );
    >
    > NTSYSAPI
    > VOID
    > NTAPI
    > RtlDeleteElementGenericTableAvlEx (
    > _In_ PRTL_AVL_TABLE Table,
    > _In_ PVOID NodeOrParent
    > );
    >
    > NTSYSAPI
    > PVOID
    > NTAPI
    > RtlLookupElementGenericTableAvl (
    > _In_ PRTL_AVL_TABLE Table,
    > _In_ PVOID Buffer
    > );
    >
    > NTSYSAPI
    > PVOID
    > NTAPI
    > RtlEnumerateGenericTableAvl (
    > _In_ PRTL_AVL_TABLE Table,
    > _In_ BOOLEAN Restart
    > );
    >
    > NTSYSAPI
    > PVOID
    > NTAPI
    > RtlEnumerateGenericTableWithoutSplayingAvl (
    > _In_ PRTL_AVL_TABLE Table,
    > _Inout_ PVOID *RestartKey
    > );
    >
    > NTSYSAPI
    > ULONG
    > NTAPI
    > RtlNumberGenericTableElementsAvl (
    > _In_ PRTL_AVL_TABLE Table
    > );
    >
    > #ifdef __cplusplus
    > }
    > #endif
    >
    > #endif //#ifndef __AVL_TREE_HEADER
    > //AVL.H ends here.
    >
    > ======================================
    >
    > The allocate and free routines are simple. You just have to do
    > what you are supposed to do: allocating a chunk of memory of the given
    > size and freeing memory:
    >
    > PVOID
    > NTAPI
    > AllocateRoutine (
    > _In_ struct _RTL_AVL_TABLE *Table,
    > _In_ ULONG ByteSize
    > ){
    > return
    > HeapAlloc(GetProcessHeap(),HEAP_ZERO_MEMORY,(SIZE_T)ByteSize);
    > }
    >
    > VOID
    > NTAPI
    > FreeRoutine(
    > _In_ struct _RTL_AVL_TABLE *Table,
    > _In_ PVOID Buffer
    > ){
    > HeapFree(GetProcessHeap(),0,Buffer);
    > }
    >
    > The compare function is dependant on the data type of the node you insert
    > in the tree.
    > For example if you insert nodes of the following type:
    >
    > typedef struct _MYNODE{
    > UINT Index;
    > LPTSTR Name;
    > } MYNODE, *PMYNODE;
    >
    > and if the Index field is used to compare nodes than the compare routine
    > would be:
    >
    > RTL_GENERIC_COMPARE_RESULTS
    > NTAPI CompareRoutine (
    > _In_ struct _RTL_AVL_TABLE *Table,
    > _In_ PVOID FirstStruct,
    > _In_ PVOID SecondStruct
    > ){
    > PMYNODE Node1, Node2;
    >
    > Node1 = (PMYNODE)FirstStruct;
    > Node2 = (PMYNODE)SecondStruct;
    >
    > if(Node1->Index > Node2->Index){
    > return GenericGreaterThan;
    > }
    > else if(Node1->Index < Node2->Index){
    > return GenericLessThan;
    > }
    >
    > return GenericEqual;
    > }
    >
    > Note that strings can be compared as well (lexicographical or dictionary
    > order)
    > and could be used for indexing purpose. But for large collections, working
    > with
    > string hashes is probably better and a hashing function is required.
    >
    >
    >
    >
    >
    >
    >
    >
    >
    > ---
    > NTDEV is sponsored by OSR
    >
    > Visit the list online at: <
    > http://www.osronline.com/showlists.cfm?list=ntdev>;
    >
    > MONTHLY seminars on crash dump analysis, WDF, Windows internals and
    > software drivers!
    > Details at
    >
    > To unsubscribe, visit the List Server section of OSR Online at <
    > http://www.osronline.com/page.cfm?name=ListServer>;
    >
  • MBondMBond Member - All Emails Posts: 846
    It is well known that amongst all binary trees, AVL is a compromise. I suspect that the engineers at Microsoft chose this one because is exactly that.

    Their counterparts in the SQL server team long ago made the choice to use b-trees instead (which are not binary however confusing the name). IMHO, primarily because of the relative ease of writing the data structures to disk in an atomic way ? and I stress relative ease

    Skiplists are not a tree at all, but a modified form of a queue or linked list. They are especially useful if the data added to the list is in a particular order and the cost of comparison between elements is high. Depending on the depth of the skip, and the distribution of data, and the access pattern, they can improve performance dramatically since often far fewer comparisons are required to find the desired data. Order of elements is especially important when using skiplists as they are totally ineffective on lists with arbitrary order.

    Again, depending upon the data insertion and access patterns, as well as the relative cost of comparisons, there are many different data structures that may be better or worse for a particular purpose. This is no new wisdom.

    If the OP has already decided to use the AVL APIs (DDIs) presumably he _knows_ that his particular usage pattern will benefit from this kind of data structure. We may presume that at least his boss suspects that the usage pattern will benefit from this. It may be possible to use an alternate data structure to a greater effect, but we have no possible way to know. One important factor is that AFAIK the only data structures that have built-in implementations in Windows for KM are the linked list and the AVL tree. I have no problem implementing generic data structures in KM, but others may wish to rely on the built-in functions as they have been well tested and peer reviewed

    Sent from Mail for Windows 10

    From: Jamey Kirby
    Sent: July 24, 2016 3:34 PM
    To: Windows System Software Devs Interest List
    Subject: Re: [ntdev] Need to Sample source for _RTL_AVL_TABLE

    AVL is a bit heavy. If you want something just as fast, open source, and extremely easy to understand, try my kernel-mode skiplist implementation. I modeled it to use nearly the same interface semantics as RTL_GENERIC_TABLE. It is available on GitHub. https://github.com/jameykirby/public

    On Thu, Jul 21, 2016 at 7:10 PM > wrote:
    At one point, The Microsoft's AVL tree implementation was the one described
    in Knuth, "The Art of Computer Programming, Volume 3, Sorting and Searching".

    I don't know if that has changed over time but the important think is that
    the implementation is exported to usermode with NTDLL.DLL. You can test the
    API in usermode with large collections of data. The WIN32 UI and the console
    are probably easier to use for this purpose. Here is a header (AVL.H) you can
    use to test the API:

    /* AVL.H

    Copyright (c) Microsoft Corporation. All rights reserved.

    For testing purpose only !

    This material was copied from the WDK's NTDDK.H header
    to use Microsoft's AVL tree implementation in usermode.

    Functions whose prototype begins with NTSYSAPI are exported
    by NTDLL.DLL. ntdll.lib must be added to the list of libraries
    imported by the project or any (.c or .cpp) source file that
    calls one of these functions must contain the line:

    #pragma comment(lib,"ntdll.lib")

    */


    #ifndef __AVL_TREE_HEADER
    #define __AVL_TREE_HEADER

    /* We need Windows Internal defs and typedefs here*/
    #include

    #ifdef __cplusplus
    extern "C" {
    #endif

    //AVL Tree defs and typedefs

    typedef enum _RTL_GENERIC_COMPARE_RESULTS {
    GenericLessThan,
    GenericGreaterThan,
    GenericEqual
    } RTL_GENERIC_COMPARE_RESULTS;

    typedef
    RTL_GENERIC_COMPARE_RESULTS
    NTAPI
    RTL_AVL_COMPARE_ROUTINE (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ PVOID FirstStruct,
    _In_ PVOID SecondStruct
    );
    typedef RTL_AVL_COMPARE_ROUTINE *PRTL_AVL_COMPARE_ROUTINE;

    typedef
    PVOID
    NTAPI
    RTL_AVL_ALLOCATE_ROUTINE (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ ULONG ByteSize
    );
    typedef RTL_AVL_ALLOCATE_ROUTINE *PRTL_AVL_ALLOCATE_ROUTINE;

    typedef
    VOID
    NTAPI
    RTL_AVL_FREE_ROUTINE (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ PVOID Buffer
    );
    typedef RTL_AVL_FREE_ROUTINE *PRTL_AVL_FREE_ROUTINE;

    typedef struct _RTL_BALANCED_LINKS {
    struct _RTL_BALANCED_LINKS *Parent;
    struct _RTL_BALANCED_LINKS *LeftChild;
    struct _RTL_BALANCED_LINKS *RightChild;
    CHAR Balance;
    UCHAR Reserved[3];
    } RTL_BALANCED_LINKS;
    typedef RTL_BALANCED_LINKS *PRTL_BALANCED_LINKS;

    typedef struct _RTL_AVL_TABLE {
    RTL_BALANCED_LINKS BalancedRoot;
    PVOID OrderedPointer;
    ULONG WhichOrderedElement;
    ULONG NumberGenericTableElements;
    ULONG DepthOfTree;
    PRTL_BALANCED_LINKS RestartKey;
    ULONG DeleteCount;
    PRTL_AVL_COMPARE_ROUTINE CompareRoutine;
    PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine;
    PRTL_AVL_FREE_ROUTINE FreeRoutine;
    PVOID TableContext;
    } RTL_AVL_TABLE;
    typedef RTL_AVL_TABLE *PRTL_AVL_TABLE;

    NTSYSAPI
    VOID
    NTAPI
    RtlInitializeGenericTableAvl (
    _Out_ PRTL_AVL_TABLE Table,
    _In_ PRTL_AVL_COMPARE_ROUTINE CompareRoutine,
    _In_ PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine,
    _In_ PRTL_AVL_FREE_ROUTINE FreeRoutine,
    _In_opt_ PVOID TableContext
    );

    NTSYSAPI
    PVOID
    NTAPI
    RtlInsertElementGenericTableAvl (
    _In_ PRTL_AVL_TABLE Table,
    _In_reads_bytes_(BufferSize) PVOID Buffer,
    _In_ ULONG BufferSize,
    _Out_opt_ PBOOLEAN NewElement
    );

    NTSYSAPI
    BOOLEAN
    NTAPI
    RtlDeleteElementGenericTableAvl (
    _In_ PRTL_AVL_TABLE Table,
    _In_ PVOID Buffer
    );

    NTSYSAPI
    VOID
    NTAPI
    RtlDeleteElementGenericTableAvlEx (
    _In_ PRTL_AVL_TABLE Table,
    _In_ PVOID NodeOrParent
    );

    NTSYSAPI
    PVOID
    NTAPI
    RtlLookupElementGenericTableAvl (
    _In_ PRTL_AVL_TABLE Table,
    _In_ PVOID Buffer
    );

    NTSYSAPI
    PVOID
    NTAPI
    RtlEnumerateGenericTableAvl (
    _In_ PRTL_AVL_TABLE Table,
    _In_ BOOLEAN Restart
    );

    NTSYSAPI
    PVOID
    NTAPI
    RtlEnumerateGenericTableWithoutSplayingAvl (
    _In_ PRTL_AVL_TABLE Table,
    _Inout_ PVOID *RestartKey
    );

    NTSYSAPI
    ULONG
    NTAPI
    RtlNumberGenericTableElementsAvl (
    _In_ PRTL_AVL_TABLE Table
    );

    #ifdef __cplusplus
    }
    #endif

    #endif //#ifndef __AVL_TREE_HEADER
    //AVL.H ends here.

    ======================================

    The allocate and free routines are simple. You just have to do
    what you are supposed to do: allocating a chunk of memory of the given
    size and freeing memory:

    PVOID
    NTAPI
    AllocateRoutine (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ ULONG ByteSize
    ){
    return HeapAlloc(GetProcessHeap(),HEAP_ZERO_MEMORY,(SIZE_T)ByteSize);
    }

    VOID
    NTAPI
    FreeRoutine(
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ PVOID Buffer
    ){
    HeapFree(GetProcessHeap(),0,Buffer);
    }

    The compare function is dependant on the data type of the node you insert in the tree.
    For example if you insert nodes of the following type:

    typedef struct _MYNODE{
    UINT Index;
    LPTSTR Name;
    } MYNODE, *PMYNODE;

    and if the Index field is used to compare nodes than the compare routine would be:

    RTL_GENERIC_COMPARE_RESULTS
    NTAPI CompareRoutine (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ PVOID FirstStruct,
    _In_ PVOID SecondStruct
    ){
    PMYNODE Node1, Node2;

    Node1 = (PMYNODE)FirstStruct;
    Node2 = (PMYNODE)SecondStruct;

    if(Node1->Index > Node2->Index){
    return GenericGreaterThan;
    }
    else if(Node1->Index < Node2->Index){
    return GenericLessThan;
    }

    return GenericEqual;
    }

    Note that strings can be compared as well (lexicographical or dictionary order)
    and could be used for indexing purpose. But for large collections, working with
    string hashes is probably better and a hashing function is required.









    ---
    NTDEV is sponsored by OSR

    Visit the list online at:

    MONTHLY seminars on crash dump analysis, WDF, Windows internals and software drivers!
    Details at

    To unsubscribe, visit the List Server section of OSR Online at
    --- NTDEV is sponsored by OSR Visit the list online at: MONTHLY seminars on crash dump analysis, WDF, Windows internals and software drivers! Details at To unsubscribe, visit the List Server section of OSR Online at
  • Jamey_KirbyJamey_Kirby Member - All Emails Posts: 438
    Order of elements is especially important when using skiplists as
    they are totally ineffective on lists with arbitrary order. wrote:

    > It is well known that amongst all binary trees, AVL is a compromise. I
    > suspect that the engineers at Microsoft chose this one because is exactly
    > that.
    >
    >
    >
    > Their counterparts in the SQL server team long ago made the choice to use
    > b-trees instead (which are not binary however confusing the name). IMHO,
    > primarily because of the relative ease of writing the data structures to
    > disk in an atomic way – and I stress relative ease
    >
    >
    >
    > Skiplists are not a tree at all, but a modified form of a queue or linked
    > list. They are especially useful if the data added to the list is in a
    > particular order and the cost of comparison between elements is high.
    > Depending on the depth of the skip, and the distribution of data, and the
    > access pattern, they can improve performance dramatically since often far
    > fewer comparisons are required to find the desired data. Order of elements
    > is especially important when using skiplists as they are totally
    > ineffective on lists with arbitrary order.
    >
    >
    >
    > Again, depending upon the data insertion and access patterns, as well as
    > the relative cost of comparisons, there are many different data structures
    > that may be better or worse for a particular purpose. This is no new
    > wisdom.
    >
    >
    >
    > If the OP has already decided to use the AVL APIs (DDIs) presumably he _
    > *knows*_ that his particular usage pattern will benefit from this kind of
    > data structure. We may presume that at least his boss suspects that the
    > usage pattern will benefit from this. It may be possible to use an
    > alternate data structure to a greater effect, but we have no possible way
    > to know. One important factor is that AFAIK the only data structures that
    > have built-in implementations in Windows for KM are the linked list and the
    > AVL tree. I have no problem implementing generic data structures in KM,
    > but others may wish to rely on the built-in functions as they have been
    > well tested and peer reviewed
    >
    >
    >
    > Sent from Mail for
    > Windows 10
    >
    >
    >
    > *From: *Jamey Kirby
    > *Sent: *July 24, 2016 3:34 PM
    > *To: *Windows System Software Devs Interest List
    > *Subject: *Re: [ntdev] Need to Sample source for _RTL_AVL_TABLE
    >
    >
    > AVL is a bit heavy. If you want something just as fast, open source, and
    > extremely easy to understand, try my kernel-mode skiplist implementation. I
    > modeled it to use nearly the same interface semantics as RTL_GENERIC_TABLE.
    > It is available on GitHub. https://github.com/jameykirby/public
    >
    > On Thu, Jul 21, 2016 at 7:10 PM wrote:
    >
    >> At one point, The Microsoft's AVL tree implementation was the one
    >> described
    >> in Knuth, "The Art of Computer Programming, Volume 3, Sorting and
    >> Searching".
    >>
    >> I don't know if that has changed over time but the important think is that
    >> the implementation is exported to usermode with NTDLL.DLL. You can test
    >> the
    >> API in usermode with large collections of data. The WIN32 UI and the
    >> console
    >> are probably easier to use for this purpose. Here is a header (AVL.H) you
    >> can
    >> use to test the API:
    >>
    >> /* AVL.H
    >>
    >> Copyright (c) Microsoft Corporation. All rights reserved.
    >>
    >> For testing purpose only !
    >>
    >> This material was copied from the WDK's NTDDK.H header
    >> to use Microsoft's AVL tree implementation in usermode.
    >>
    >> Functions whose prototype begins with NTSYSAPI are exported
    >> by NTDLL.DLL. ntdll.lib must be added to the list of libraries
    >> imported by the project or any (.c or .cpp) source file that
    >> calls one of these functions must contain the line:
    >>
    >> #pragma comment(lib,"ntdll.lib")
    >>
    >> */
    >>
    >>
    >> #ifndef __AVL_TREE_HEADER
    >> #define __AVL_TREE_HEADER
    >>
    >> /* We need Windows Internal defs and typedefs here*/
    >> #include
    >>
    >> #ifdef __cplusplus
    >> extern "C" {
    >> #endif
    >>
    >> //AVL Tree defs and typedefs
    >>
    >> typedef enum _RTL_GENERIC_COMPARE_RESULTS {
    >> GenericLessThan,
    >> GenericGreaterThan,
    >> GenericEqual
    >> } RTL_GENERIC_COMPARE_RESULTS;
    >>
    >> typedef
    >> RTL_GENERIC_COMPARE_RESULTS
    >> NTAPI
    >> RTL_AVL_COMPARE_ROUTINE (
    >> _In_ struct _RTL_AVL_TABLE *Table,
    >> _In_ PVOID FirstStruct,
    >> _In_ PVOID SecondStruct
    >> );
    >> typedef RTL_AVL_COMPARE_ROUTINE *PRTL_AVL_COMPARE_ROUTINE;
    >>
    >> typedef
    >> PVOID
    >> NTAPI
    >> RTL_AVL_ALLOCATE_ROUTINE (
    >> _In_ struct _RTL_AVL_TABLE *Table,
    >> _In_ ULONG ByteSize
    >> );
    >> typedef RTL_AVL_ALLOCATE_ROUTINE *PRTL_AVL_ALLOCATE_ROUTINE;
    >>
    >> typedef
    >> VOID
    >> NTAPI
    >> RTL_AVL_FREE_ROUTINE (
    >> _In_ struct _RTL_AVL_TABLE *Table,
    >> _In_ PVOID Buffer
    >> );
    >> typedef RTL_AVL_FREE_ROUTINE *PRTL_AVL_FREE_ROUTINE;
    >>
    >> typedef struct _RTL_BALANCED_LINKS {
    >> struct _RTL_BALANCED_LINKS *Parent;
    >> struct _RTL_BALANCED_LINKS *LeftChild;
    >> struct _RTL_BALANCED_LINKS *RightChild;
    >> CHAR Balance;
    >> UCHAR Reserved[3];
    >> } RTL_BALANCED_LINKS;
    >> typedef RTL_BALANCED_LINKS *PRTL_BALANCED_LINKS;
    >>
    >> typedef struct _RTL_AVL_TABLE {
    >> RTL_BALANCED_LINKS BalancedRoot;
    >> PVOID OrderedPointer;
    >> ULONG WhichOrderedElement;
    >> ULONG NumberGenericTableElements;
    >> ULONG DepthOfTree;
    >> PRTL_BALANCED_LINKS RestartKey;
    >> ULONG DeleteCount;
    >> PRTL_AVL_COMPARE_ROUTINE CompareRoutine;
    >> PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine;
    >> PRTL_AVL_FREE_ROUTINE FreeRoutine;
    >> PVOID TableContext;
    >> } RTL_AVL_TABLE;
    >> typedef RTL_AVL_TABLE *PRTL_AVL_TABLE;
    >>
    >> NTSYSAPI
    >> VOID
    >> NTAPI
    >> RtlInitializeGenericTableAvl (
    >> _Out_ PRTL_AVL_TABLE Table,
    >> _In_ PRTL_AVL_COMPARE_ROUTINE CompareRoutine,
    >> _In_ PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine,
    >> _In_ PRTL_AVL_FREE_ROUTINE FreeRoutine,
    >> _In_opt_ PVOID TableContext
    >> );
    >>
    >> NTSYSAPI
    >> PVOID
    >> NTAPI
    >> RtlInsertElementGenericTableAvl (
    >> _In_ PRTL_AVL_TABLE Table,
    >> _In_reads_bytes_(BufferSize) PVOID Buffer,
    >> _In_ ULONG BufferSize,
    >> _Out_opt_ PBOOLEAN NewElement
    >> );
    >>
    >> NTSYSAPI
    >> BOOLEAN
    >> NTAPI
    >> RtlDeleteElementGenericTableAvl (
    >> _In_ PRTL_AVL_TABLE Table,
    >> _In_ PVOID Buffer
    >> );
    >>
    >> NTSYSAPI
    >> VOID
    >> NTAPI
    >> RtlDeleteElementGenericTableAvlEx (
    >> _In_ PRTL_AVL_TABLE Table,
    >> _In_ PVOID NodeOrParent
    >> );
    >>
    >> NTSYSAPI
    >> PVOID
    >> NTAPI
    >> RtlLookupElementGenericTableAvl (
    >> _In_ PRTL_AVL_TABLE Table,
    >> _In_ PVOID Buffer
    >> );
    >>
    >> NTSYSAPI
    >> PVOID
    >> NTAPI
    >> RtlEnumerateGenericTableAvl (
    >> _In_ PRTL_AVL_TABLE Table,
    >> _In_ BOOLEAN Restart
    >> );
    >>
    >> NTSYSAPI
    >> PVOID
    >> NTAPI
    >> RtlEnumerateGenericTableWithoutSplayingAvl (
    >> _In_ PRTL_AVL_TABLE Table,
    >> _Inout_ PVOID *RestartKey
    >> );
    >>
    >> NTSYSAPI
    >> ULONG
    >> NTAPI
    >> RtlNumberGenericTableElementsAvl (
    >> _In_ PRTL_AVL_TABLE Table
    >> );
    >>
    >> #ifdef __cplusplus
    >> }
    >> #endif
    >>
    >> #endif //#ifndef __AVL_TREE_HEADER
    >> //AVL.H ends here.
    >>
    >> ======================================
    >>
    >> The allocate and free routines are simple. You just have to do
    >> what you are supposed to do: allocating a chunk of memory of the given
    >> size and freeing memory:
    >>
    >> PVOID
    >> NTAPI
    >> AllocateRoutine (
    >> _In_ struct _RTL_AVL_TABLE *Table,
    >> _In_ ULONG ByteSize
    >> ){
    >> return
    >> HeapAlloc(GetProcessHeap(),HEAP_ZERO_MEMORY,(SIZE_T)ByteSize);
    >> }
    >>
    >> VOID
    >> NTAPI
    >> FreeRoutine(
    >> _In_ struct _RTL_AVL_TABLE *Table,
    >> _In_ PVOID Buffer
    >> ){
    >> HeapFree(GetProcessHeap(),0,Buffer);
    >> }
    >>
    >> The compare function is dependant on the data type of the node you insert
    >> in the tree.
    >> For example if you insert nodes of the following type:
    >>
    >> typedef struct _MYNODE{
    >> UINT Index;
    >> LPTSTR Name;
    >> } MYNODE, *PMYNODE;
    >>
    >> and if the Index field is used to compare nodes than the compare routine
    >> would be:
    >>
    >> RTL_GENERIC_COMPARE_RESULTS
    >> NTAPI CompareRoutine (
    >> _In_ struct _RTL_AVL_TABLE *Table,
    >> _In_ PVOID FirstStruct,
    >> _In_ PVOID SecondStruct
    >> ){
    >> PMYNODE Node1, Node2;
    >>
    >> Node1 = (PMYNODE)FirstStruct;
    >> Node2 = (PMYNODE)SecondStruct;
    >>
    >> if(Node1->Index > Node2->Index){
    >> return GenericGreaterThan;
    >> }
    >> else if(Node1->Index < Node2->Index){
    >> return GenericLessThan;
    >> }
    >>
    >> return GenericEqual;
    >> }
    >>
    >> Note that strings can be compared as well (lexicographical or dictionary
    >> order)
    >> and could be used for indexing purpose. But for large collections,
    >> working with
    >> string hashes is probably better and a hashing function is required.
    >>
    >>
    >>
    >>
    >>
    >>
    >>
    >>
    >>
    >> ---
    >> NTDEV is sponsored by OSR
    >>
    >> Visit the list online at: <
    >> http://www.osronline.com/showlists.cfm?list=ntdev>;
    >>
    >> MONTHLY seminars on crash dump analysis, WDF, Windows internals and
    >> software drivers!
    >> Details at
    >>
    >> To unsubscribe, visit the List Server section of OSR Online at <
    >> http://www.osronline.com/page.cfm?name=ListServer>;
    >>
    > --- NTDEV is sponsored by OSR Visit the list online at: MONTHLY seminars
    > on crash dump analysis, WDF, Windows internals and software drivers!
    > Details at To unsubscribe, visit the List Server section of OSR Online at
    >
    > ---
    > NTDEV is sponsored by OSR
    >
    > Visit the list online at: <
    > http://www.osronline.com/showlists.cfm?list=ntdev>;
    >
    > MONTHLY seminars on crash dump analysis, WDF, Windows internals and
    > software drivers!
    > Details at
    >
    > To unsubscribe, visit the List Server section of OSR Online at <
    > http://www.osronline.com/page.cfm?name=ListServer>;
    >
  • Maxim_S._ShatskihMaxim_S._Shatskih Member Posts: 10,396
    If you delete a lot, then maybe red-black tree is better then AVL one.

    That's why most STL implementations use RB trees for sets and maps.

    --
    Maxim S. Shatskih
    Microsoft MVP on File System And Storage
    xxxxx@storagecraft.com
    http://www.storagecraft.com
    "Marion Bond" wrote in message news:xxxxx@ntdev...
    It is well known that amongst all binary trees, AVL is a compromise. I suspect that the engineers at Microsoft chose this one because is exactly that.



    Their counterparts in the SQL server team long ago made the choice to use b-trees instead (which are not binary however confusing the name). IMHO, primarily because of the relative ease of writing the data structures to disk in an atomic way ? and I stress relative ease



    Skiplists are not a tree at all, but a modified form of a queue or linked list. They are especially useful if the data added to the list is in a particular order and the cost of comparison between elements is high. Depending on the depth of the skip, and the distribution of data, and the access pattern, they can improve performance dramatically since often far fewer comparisons are required to find the desired data. Order of elements is especially important when using skiplists as they are totally ineffective on lists with arbitrary order.



    Again, depending upon the data insertion and access patterns, as well as the relative cost of comparisons, there are many different data structures that may be better or worse for a particular purpose. This is no new wisdom.



    If the OP has already decided to use the AVL APIs (DDIs) presumably he _knows_ that his particular usage pattern will benefit from this kind of data structure. We may presume that at least his boss suspects that the usage pattern will benefit from this. It may be possible to use an alternate data structure to a greater effect, but we have no possible way to know. One important factor is that AFAIK the only data structures that have built-in implementations in Windows for KM are the linked list and the AVL tree. I have no problem implementing generic data structures in KM, but others may wish to rely on the built-in functions as they have been well tested and peer reviewed



    Sent from Mail for Windows 10



    From: Jamey Kirby
    Sent: July 24, 2016 3:34 PM
    To: Windows System Software Devs Interest List
    Subject: Re: [ntdev] Need to Sample source for _RTL_AVL_TABLE



    AVL is a bit heavy. If you want something just as fast, open source, and extremely easy to understand, try my kernel-mode skiplist implementation. I modeled it to use nearly the same interface semantics as RTL_GENERIC_TABLE. It is available on GitHub. https://github.com/jameykirby/public


    On Thu, Jul 21, 2016 at 7:10 PM wrote:

    At one point, The Microsoft's AVL tree implementation was the one described
    in Knuth, "The Art of Computer Programming, Volume 3, Sorting and Searching".

    I don't know if that has changed over time but the important think is that
    the implementation is exported to usermode with NTDLL.DLL. You can test the
    API in usermode with large collections of data. The WIN32 UI and the console
    are probably easier to use for this purpose. Here is a header (AVL.H) you can
    use to test the API:

    /* AVL.H

    Copyright (c) Microsoft Corporation. All rights reserved.

    For testing purpose only !

    This material was copied from the WDK's NTDDK.H header
    to use Microsoft's AVL tree implementation in usermode.

    Functions whose prototype begins with NTSYSAPI are exported
    by NTDLL.DLL. ntdll.lib must be added to the list of libraries
    imported by the project or any (.c or .cpp) source file that
    calls one of these functions must contain the line:

    #pragma comment(lib,"ntdll.lib")

    */


    #ifndef __AVL_TREE_HEADER
    #define __AVL_TREE_HEADER

    /* We need Windows Internal defs and typedefs here*/
    #include

    #ifdef __cplusplus
    extern "C" {
    #endif

    //AVL Tree defs and typedefs

    typedef enum _RTL_GENERIC_COMPARE_RESULTS {
    GenericLessThan,
    GenericGreaterThan,
    GenericEqual
    } RTL_GENERIC_COMPARE_RESULTS;

    typedef
    RTL_GENERIC_COMPARE_RESULTS
    NTAPI
    RTL_AVL_COMPARE_ROUTINE (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ PVOID FirstStruct,
    _In_ PVOID SecondStruct
    );
    typedef RTL_AVL_COMPARE_ROUTINE *PRTL_AVL_COMPARE_ROUTINE;

    typedef
    PVOID
    NTAPI
    RTL_AVL_ALLOCATE_ROUTINE (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ ULONG ByteSize
    );
    typedef RTL_AVL_ALLOCATE_ROUTINE *PRTL_AVL_ALLOCATE_ROUTINE;

    typedef
    VOID
    NTAPI
    RTL_AVL_FREE_ROUTINE (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ PVOID Buffer
    );
    typedef RTL_AVL_FREE_ROUTINE *PRTL_AVL_FREE_ROUTINE;

    typedef struct _RTL_BALANCED_LINKS {
    struct _RTL_BALANCED_LINKS *Parent;
    struct _RTL_BALANCED_LINKS *LeftChild;
    struct _RTL_BALANCED_LINKS *RightChild;
    CHAR Balance;
    UCHAR Reserved[3];
    } RTL_BALANCED_LINKS;
    typedef RTL_BALANCED_LINKS *PRTL_BALANCED_LINKS;

    typedef struct _RTL_AVL_TABLE {
    RTL_BALANCED_LINKS BalancedRoot;
    PVOID OrderedPointer;
    ULONG WhichOrderedElement;
    ULONG NumberGenericTableElements;
    ULONG DepthOfTree;
    PRTL_BALANCED_LINKS RestartKey;
    ULONG DeleteCount;
    PRTL_AVL_COMPARE_ROUTINE CompareRoutine;
    PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine;
    PRTL_AVL_FREE_ROUTINE FreeRoutine;
    PVOID TableContext;
    } RTL_AVL_TABLE;
    typedef RTL_AVL_TABLE *PRTL_AVL_TABLE;

    NTSYSAPI
    VOID
    NTAPI
    RtlInitializeGenericTableAvl (
    _Out_ PRTL_AVL_TABLE Table,
    _In_ PRTL_AVL_COMPARE_ROUTINE CompareRoutine,
    _In_ PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine,
    _In_ PRTL_AVL_FREE_ROUTINE FreeRoutine,
    _In_opt_ PVOID TableContext
    );

    NTSYSAPI
    PVOID
    NTAPI
    RtlInsertElementGenericTableAvl (
    _In_ PRTL_AVL_TABLE Table,
    _In_reads_bytes_(BufferSize) PVOID Buffer,
    _In_ ULONG BufferSize,
    _Out_opt_ PBOOLEAN NewElement
    );

    NTSYSAPI
    BOOLEAN
    NTAPI
    RtlDeleteElementGenericTableAvl (
    _In_ PRTL_AVL_TABLE Table,
    _In_ PVOID Buffer
    );

    NTSYSAPI
    VOID
    NTAPI
    RtlDeleteElementGenericTableAvlEx (
    _In_ PRTL_AVL_TABLE Table,
    _In_ PVOID NodeOrParent
    );

    NTSYSAPI
    PVOID
    NTAPI
    RtlLookupElementGenericTableAvl (
    _In_ PRTL_AVL_TABLE Table,
    _In_ PVOID Buffer
    );

    NTSYSAPI
    PVOID
    NTAPI
    RtlEnumerateGenericTableAvl (
    _In_ PRTL_AVL_TABLE Table,
    _In_ BOOLEAN Restart
    );

    NTSYSAPI
    PVOID
    NTAPI
    RtlEnumerateGenericTableWithoutSplayingAvl (
    _In_ PRTL_AVL_TABLE Table,
    _Inout_ PVOID *RestartKey
    );

    NTSYSAPI
    ULONG
    NTAPI
    RtlNumberGenericTableElementsAvl (
    _In_ PRTL_AVL_TABLE Table
    );

    #ifdef __cplusplus
    }
    #endif

    #endif //#ifndef __AVL_TREE_HEADER
    //AVL.H ends here.

    ======================================

    The allocate and free routines are simple. You just have to do
    what you are supposed to do: allocating a chunk of memory of the given
    size and freeing memory:

    PVOID
    NTAPI
    AllocateRoutine (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ ULONG ByteSize
    ){
    return HeapAlloc(GetProcessHeap(),HEAP_ZERO_MEMORY,(SIZE_T)ByteSize);
    }

    VOID
    NTAPI
    FreeRoutine(
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ PVOID Buffer
    ){
    HeapFree(GetProcessHeap(),0,Buffer);
    }

    The compare function is dependant on the data type of the node you insert in the tree.
    For example if you insert nodes of the following type:

    typedef struct _MYNODE{
    UINT Index;
    LPTSTR Name;
    } MYNODE, *PMYNODE;

    and if the Index field is used to compare nodes than the compare routine would be:

    RTL_GENERIC_COMPARE_RESULTS
    NTAPI CompareRoutine (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ PVOID FirstStruct,
    _In_ PVOID SecondStruct
    ){
    PMYNODE Node1, Node2;

    Node1 = (PMYNODE)FirstStruct;
    Node2 = (PMYNODE)SecondStruct;

    if(Node1->Index > Node2->Index){
    return GenericGreaterThan;
    }
    else if(Node1->Index < Node2->Index){
    return GenericLessThan;
    }

    return GenericEqual;
    }

    Note that strings can be compared as well (lexicographical or dictionary order)
    and could be used for indexing purpose. But for large collections, working with
    string hashes is probably better and a hashing function is required.









    ---
    NTDEV is sponsored by OSR

    Visit the list online at:

    MONTHLY seminars on crash dump analysis, WDF, Windows internals and software drivers!
    Details at

    To unsubscribe, visit the List Server section of OSR Online at

    --- NTDEV is sponsored by OSR Visit the list online at: MONTHLY seminars on crash dump analysis, WDF, Windows internals and software drivers! Details at To unsubscribe, visit the List Server section of OSR Online at
  • MBondMBond Member - All Emails Posts: 846
    Perhaps we are crossing terms here, but I can?t see how random number generators have any relation to skiplists. Skiplists, as I know them, are like linked lists but they have additional pointers to items that are ?further on? in the list ? allowing an iterator looking for a specific item (or items) to arrive there more rapidly if the items in the list are in some kind of order. If the items in the list are in an arbitrary order, then the skip pointers don?t help at all since they cannot help you to skip over elements if it is uncertain that the ones being skipped will be ?less than? the next checked node.

    Perhaps there is another kind of skiplist that I am unaware of, or other algorithms for their use, but if the entire list is in arbitrary order it seems unclear how there is any benefit from the skipping.

    If the list is in a specific order, then it is certainly possible to use bifurcations (random or binary) to find a certain item (or range) with performance similar to any tree ? and if the cost of a comparison between elements is high, it can be much better.


    Sent from Mail for Windows 10

    From: Jamey Kirby
    Sent: July 24, 2016 7:37 PM
    To: Windows System Software Devs Interest List
    Subject: Re: [ntdev] Need to Sample source for _RTL_AVL_TABLE

    Order of elements is especially important when using skiplists as they are totally ineffective on lists with arbitrary order.> wrote:
    It is well known that amongst all binary trees, AVL is a compromise. I suspect that the engineers at Microsoft chose this one because is exactly that.

    Their counterparts in the SQL server team long ago made the choice to use b-trees instead (which are not binary however confusing the name). IMHO, primarily because of the relative ease of writing the data structures to disk in an atomic way ? and I stress relative ease

    Skiplists are not a tree at all, but a modified form of a queue or linked list. They are especially useful if the data added to the list is in a particular order and the cost of comparison between elements is high. Depending on the depth of the skip, and the distribution of data, and the access pattern, they can improve performance dramatically since often far fewer comparisons are required to find the desired data. Order of elements is especially important when using skiplists as they are totally ineffective on lists with arbitrary order.

    Again, depending upon the data insertion and access patterns, as well as the relative cost of comparisons, there are many different data structures that may be better or worse for a particular purpose. This is no new wisdom.

    If the OP has already decided to use the AVL APIs (DDIs) presumably he _knows_ that his particular usage pattern will benefit from this kind of data structure. We may presume that at least his boss suspects that the usage pattern will benefit from this. It may be possible to use an alternate data structure to a greater effect, but we have no possible way to know. One important factor is that AFAIK the only data structures that have built-in implementations in Windows for KM are the linked list and the AVL tree. I have no problem implementing generic data structures in KM, but others may wish to rely on the built-in functions as they have been well tested and peer reviewed

    Sent from Mail for Windows 10

    From: Jamey Kirby
    Sent: July 24, 2016 3:34 PM
    To: Windows System Software Devs Interest List
    Subject: Re: [ntdev] Need to Sample source for _RTL_AVL_TABLE

    AVL is a bit heavy. If you want something just as fast, open source, and extremely easy to understand, try my kernel-mode skiplist implementation. I modeled it to use nearly the same interface semantics as RTL_GENERIC_TABLE. It is available on GitHub. https://github.com/jameykirby/public

    On Thu, Jul 21, 2016 at 7:10 PM > wrote:
    At one point, The Microsoft's AVL tree implementation was the one described
    in Knuth, "The Art of Computer Programming, Volume 3, Sorting and Searching".

    I don't know if that has changed over time but the important think is that
    the implementation is exported to usermode with NTDLL.DLL. You can test the
    API in usermode with large collections of data. The WIN32 UI and the console
    are probably easier to use for this purpose. Here is a header (AVL.H) you can
    use to test the API:

    /* AVL.H

    Copyright (c) Microsoft Corporation. All rights reserved.

    For testing purpose only !

    This material was copied from the WDK's NTDDK.H header
    to use Microsoft's AVL tree implementation in usermode.

    Functions whose prototype begins with NTSYSAPI are exported
    by NTDLL.DLL. ntdll.lib must be added to the list of libraries
    imported by the project or any (.c or .cpp) source file that
    calls one of these functions must contain the line:

    #pragma comment(lib,"ntdll.lib")

    */


    #ifndef __AVL_TREE_HEADER
    #define __AVL_TREE_HEADER

    /* We need Windows Internal defs and typedefs here*/
    #include

    #ifdef __cplusplus
    extern "C" {
    #endif

    //AVL Tree defs and typedefs

    typedef enum _RTL_GENERIC_COMPARE_RESULTS {
    GenericLessThan,
    GenericGreaterThan,
    GenericEqual
    } RTL_GENERIC_COMPARE_RESULTS;

    typedef
    RTL_GENERIC_COMPARE_RESULTS
    NTAPI
    RTL_AVL_COMPARE_ROUTINE (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ PVOID FirstStruct,
    _In_ PVOID SecondStruct
    );
    typedef RTL_AVL_COMPARE_ROUTINE *PRTL_AVL_COMPARE_ROUTINE;

    typedef
    PVOID
    NTAPI
    RTL_AVL_ALLOCATE_ROUTINE (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ ULONG ByteSize
    );
    typedef RTL_AVL_ALLOCATE_ROUTINE *PRTL_AVL_ALLOCATE_ROUTINE;

    typedef
    VOID
    NTAPI
    RTL_AVL_FREE_ROUTINE (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ PVOID Buffer
    );
    typedef RTL_AVL_FREE_ROUTINE *PRTL_AVL_FREE_ROUTINE;

    typedef struct _RTL_BALANCED_LINKS {
    struct _RTL_BALANCED_LINKS *Parent;
    struct _RTL_BALANCED_LINKS *LeftChild;
    struct _RTL_BALANCED_LINKS *RightChild;
    CHAR Balance;
    UCHAR Reserved[3];
    } RTL_BALANCED_LINKS;
    typedef RTL_BALANCED_LINKS *PRTL_BALANCED_LINKS;

    typedef struct _RTL_AVL_TABLE {
    RTL_BALANCED_LINKS BalancedRoot;
    PVOID OrderedPointer;
    ULONG WhichOrderedElement;
    ULONG NumberGenericTableElements;
    ULONG DepthOfTree;
    PRTL_BALANCED_LINKS RestartKey;
    ULONG DeleteCount;
    PRTL_AVL_COMPARE_ROUTINE CompareRoutine;
    PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine;
    PRTL_AVL_FREE_ROUTINE FreeRoutine;
    PVOID TableContext;
    } RTL_AVL_TABLE;
    typedef RTL_AVL_TABLE *PRTL_AVL_TABLE;

    NTSYSAPI
    VOID
    NTAPI
    RtlInitializeGenericTableAvl (
    _Out_ PRTL_AVL_TABLE Table,
    _In_ PRTL_AVL_COMPARE_ROUTINE CompareRoutine,
    _In_ PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine,
    _In_ PRTL_AVL_FREE_ROUTINE FreeRoutine,
    _In_opt_ PVOID TableContext
    );

    NTSYSAPI
    PVOID
    NTAPI
    RtlInsertElementGenericTableAvl (
    _In_ PRTL_AVL_TABLE Table,
    _In_reads_bytes_(BufferSize) PVOID Buffer,
    _In_ ULONG BufferSize,
    _Out_opt_ PBOOLEAN NewElement
    );

    NTSYSAPI
    BOOLEAN
    NTAPI
    RtlDeleteElementGenericTableAvl (
    _In_ PRTL_AVL_TABLE Table,
    _In_ PVOID Buffer
    );

    NTSYSAPI
    VOID
    NTAPI
    RtlDeleteElementGenericTableAvlEx (
    _In_ PRTL_AVL_TABLE Table,
    _In_ PVOID NodeOrParent
    );

    NTSYSAPI
    PVOID
    NTAPI
    RtlLookupElementGenericTableAvl (
    _In_ PRTL_AVL_TABLE Table,
    _In_ PVOID Buffer
    );

    NTSYSAPI
    PVOID
    NTAPI
    RtlEnumerateGenericTableAvl (
    _In_ PRTL_AVL_TABLE Table,
    _In_ BOOLEAN Restart
    );

    NTSYSAPI
    PVOID
    NTAPI
    RtlEnumerateGenericTableWithoutSplayingAvl (
    _In_ PRTL_AVL_TABLE Table,
    _Inout_ PVOID *RestartKey
    );

    NTSYSAPI
    ULONG
    NTAPI
    RtlNumberGenericTableElementsAvl (
    _In_ PRTL_AVL_TABLE Table
    );

    #ifdef __cplusplus
    }
    #endif

    #endif //#ifndef __AVL_TREE_HEADER
    //AVL.H ends here.

    ======================================

    The allocate and free routines are simple. You just have to do
    what you are supposed to do: allocating a chunk of memory of the given
    size and freeing memory:

    PVOID
    NTAPI
    AllocateRoutine (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ ULONG ByteSize
    ){
    return HeapAlloc(GetProcessHeap(),HEAP_ZERO_MEMORY,(SIZE_T)ByteSize);
    }

    VOID
    NTAPI
    FreeRoutine(
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ PVOID Buffer
    ){
    HeapFree(GetProcessHeap(),0,Buffer);
    }

    The compare function is dependant on the data type of the node you insert in the tree.
    For example if you insert nodes of the following type:

    typedef struct _MYNODE{
    UINT Index;
    LPTSTR Name;
    } MYNODE, *PMYNODE;

    and if the Index field is used to compare nodes than the compare routine would be:

    RTL_GENERIC_COMPARE_RESULTS
    NTAPI CompareRoutine (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ PVOID FirstStruct,
    _In_ PVOID SecondStruct
    ){
    PMYNODE Node1, Node2;

    Node1 = (PMYNODE)FirstStruct;
    Node2 = (PMYNODE)SecondStruct;

    if(Node1->Index > Node2->Index){
    return GenericGreaterThan;
    }
    else if(Node1->Index < Node2->Index){
    return GenericLessThan;
    }

    return GenericEqual;
    }

    Note that strings can be compared as well (lexicographical or dictionary order)
    and could be used for indexing purpose. But for large collections, working with
    string hashes is probably better and a hashing function is required.









    ---
    NTDEV is sponsored by OSR

    Visit the list online at:

    MONTHLY seminars on crash dump analysis, WDF, Windows internals and software drivers!
    Details at

    To unsubscribe, visit the List Server section of OSR Online at
    --- NTDEV is sponsored by OSR Visit the list online at: MONTHLY seminars on crash dump analysis, WDF, Windows internals and software drivers! Details at To unsubscribe, visit the List Server section of OSR Online at

    ---
    NTDEV is sponsored by OSR

    Visit the list online at:

    MONTHLY seminars on crash dump analysis, WDF, Windows internals and software drivers!
    Details at

    To unsubscribe, visit the List Server section of OSR Online at
    --- NTDEV is sponsored by OSR Visit the list online at: MONTHLY seminars on crash dump analysis, WDF, Windows internals and software drivers! Details at To unsubscribe, visit the List Server section of OSR Online at
  • MBondMBond Member - All Emails Posts: 846
    RB trees have their own set of flaws ? the largest underreported one is the assumption of entirely symmetric memory access and the very CPU cache unfriendly behaviours that can ensue ? this is also true of most tree implementations and does not necessarily reflect poorly on this one as the current _state of the art_ has exactly these problems. This can be even worse on NUMA machines and no current production OS provides an adequate facility to identify or resolve these problems IMHO

    Large CPU caches reduce the severity of the impact of data structures that have poor locality of reference, and indeed this is a secondary effect when compared with the efficiency of the algorithms, but even still secondary effects can still play a substantial role.

    A significantly better tree algorithm that can be both compare and cache efficient does exist but I am not at liberty to disclose any of its details. I may flatter myself by mentioning it, but as the cancer doctors will shortly decide if my demise is imminent or at some protracted point in the future, I don?t care so much

    In keeping with these challenges, I did buy a tablet (a surface) and learned to type left handed so that I can keep supplying all of the form members some increasingly erratic posts on religious, political, moral and by the way technical issues too. I apologise in advance to all of those whom I have learned from for squandering that wisdom

    As these issues are totally OT, I hope we can get some better ones soon.

    In the remote event that anyone wants to know about binary tree stability on cache coherent NUMA machines spanning millions of nodes in Windows KM, let me know and I?ll work on writing something that may make sense.


    Sent from Mail for Windows 10

    From: Maxim S. Shatskih
    Sent: July 25, 2016 6:55 AM
    To: Windows System Software Devs Interest List
    Subject: Re:[ntdev] Need to Sample source for _RTL_AVL_TABLE

    If you delete a lot, then maybe red-black tree is better then AVL one.

    That's why most STL implementations use RB trees for sets and maps.

    --
    Maxim S. Shatskih
    Microsoft MVP on File System And Storage
    xxxxx@storagecraft.com
    http://www.storagecraft.com
    "Marion Bond" > wrote in message news:xxxxx@ntdev...
    It is well known that amongst all binary trees, AVL is a compromise. I suspect that the engineers at Microsoft chose this one because is exactly that.

    Their counterparts in the SQL server team long ago made the choice to use b-trees instead (which are not binary however confusing the name). IMHO, primarily because of the relative ease of writing the data structures to disk in an atomic way ? and I stress relative ease

    Skiplists are not a tree at all, but a modified form of a queue or linked list. They are especially useful if the data added to the list is in a particular order and the cost of comparison between elements is high. Depending on the depth of the skip, and the distribution of data, and the access pattern, they can improve performance dramatically since often far fewer comparisons are required to find the desired data. Order of elements is especially important when using skiplists as they are totally ineffective on lists with arbitrary order.

    Again, depending upon the data insertion and access patterns, as well as the relative cost of comparisons, there are many different data structures that may be better or worse for a particular purpose. This is no new wisdom.

    If the OP has already decided to use the AVL APIs (DDIs) presumably he _knows_ that his particular usage pattern will benefit from this kind of data structure. We may presume that at least his boss suspects that the usage pattern will benefit from this. It may be possible to use an alternate data structure to a greater effect, but we have no possible way to know. One important factor is that AFAIK the only data structures that have built-in implementations in Windows for KM are the linked list and the AVL tree. I have no problem implementing generic data structures in KM, but others may wish to rely on the built-in functions as they have been well tested and peer reviewed

    Sent from Mail for Windows 10

    From: Jamey Kirby
    Sent: July 24, 2016 3:34 PM
    To: Windows System Software Devs Interest List
    Subject: Re: [ntdev] Need to Sample source for _RTL_AVL_TABLE

    AVL is a bit heavy. If you want something just as fast, open source, and extremely easy to understand, try my kernel-mode skiplist implementation. I modeled it to use nearly the same interface semantics as RTL_GENERIC_TABLE. It is available on GitHub. https://github.com/jameykirby/public

    On Thu, Jul 21, 2016 at 7:10 PM > wrote:
    At one point, The Microsoft's AVL tree implementation was the one described
    in Knuth, "The Art of Computer Programming, Volume 3, Sorting and Searching".

    I don't know if that has changed over time but the important think is that
    the implementation is exported to usermode with NTDLL.DLL. You can test the
    API in usermode with large collections of data. The WIN32 UI and the console
    are probably easier to use for this purpose. Here is a header (AVL.H) you can
    use to test the API:

    /* AVL.H

    Copyright (c) Microsoft Corporation. All rights reserved.

    For testing purpose only !

    This material was copied from the WDK's NTDDK.H header
    to use Microsoft's AVL tree implementation in usermode.

    Functions whose prototype begins with NTSYSAPI are exported
    by NTDLL.DLL. ntdll.lib must be added to the list of libraries
    imported by the project or any (.c or .cpp) source file that
    calls one of these functions must contain the line:

    #pragma comment(lib,"ntdll.lib")

    */


    #ifndef __AVL_TREE_HEADER
    #define __AVL_TREE_HEADER

    /* We need Windows Internal defs and typedefs here*/
    #include

    #ifdef __cplusplus
    extern "C" {
    #endif

    //AVL Tree defs and typedefs

    typedef enum _RTL_GENERIC_COMPARE_RESULTS {
    GenericLessThan,
    GenericGreaterThan,
    GenericEqual
    } RTL_GENERIC_COMPARE_RESULTS;

    typedef
    RTL_GENERIC_COMPARE_RESULTS
    NTAPI
    RTL_AVL_COMPARE_ROUTINE (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ PVOID FirstStruct,
    _In_ PVOID SecondStruct
    );
    typedef RTL_AVL_COMPARE_ROUTINE *PRTL_AVL_COMPARE_ROUTINE;

    typedef
    PVOID
    NTAPI
    RTL_AVL_ALLOCATE_ROUTINE (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ ULONG ByteSize
    );
    typedef RTL_AVL_ALLOCATE_ROUTINE *PRTL_AVL_ALLOCATE_ROUTINE;

    typedef
    VOID
    NTAPI
    RTL_AVL_FREE_ROUTINE (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ PVOID Buffer
    );
    typedef RTL_AVL_FREE_ROUTINE *PRTL_AVL_FREE_ROUTINE;

    typedef struct _RTL_BALANCED_LINKS {
    struct _RTL_BALANCED_LINKS *Parent;
    struct _RTL_BALANCED_LINKS *LeftChild;
    struct _RTL_BALANCED_LINKS *RightChild;
    CHAR Balance;
    UCHAR Reserved[3];
    } RTL_BALANCED_LINKS;
    typedef RTL_BALANCED_LINKS *PRTL_BALANCED_LINKS;

    typedef struct _RTL_AVL_TABLE {
    RTL_BALANCED_LINKS BalancedRoot;
    PVOID OrderedPointer;
    ULONG WhichOrderedElement;
    ULONG NumberGenericTableElements;
    ULONG DepthOfTree;
    PRTL_BALANCED_LINKS RestartKey;
    ULONG DeleteCount;
    PRTL_AVL_COMPARE_ROUTINE CompareRoutine;
    PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine;
    PRTL_AVL_FREE_ROUTINE FreeRoutine;
    PVOID TableContext;
    } RTL_AVL_TABLE;
    typedef RTL_AVL_TABLE *PRTL_AVL_TABLE;

    NTSYSAPI
    VOID
    NTAPI
    RtlInitializeGenericTableAvl (
    _Out_ PRTL_AVL_TABLE Table,
    _In_ PRTL_AVL_COMPARE_ROUTINE CompareRoutine,
    _In_ PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine,
    _In_ PRTL_AVL_FREE_ROUTINE FreeRoutine,
    _In_opt_ PVOID TableContext
    );

    NTSYSAPI
    PVOID
    NTAPI
    RtlInsertElementGenericTableAvl (
    _In_ PRTL_AVL_TABLE Table,
    _In_reads_bytes_(BufferSize) PVOID Buffer,
    _In_ ULONG BufferSize,
    _Out_opt_ PBOOLEAN NewElement
    );

    NTSYSAPI
    BOOLEAN
    NTAPI
    RtlDeleteElementGenericTableAvl (
    _In_ PRTL_AVL_TABLE Table,
    _In_ PVOID Buffer
    );

    NTSYSAPI
    VOID
    NTAPI
    RtlDeleteElementGenericTableAvlEx (
    _In_ PRTL_AVL_TABLE Table,
    _In_ PVOID NodeOrParent
    );

    NTSYSAPI
    PVOID
    NTAPI
    RtlLookupElementGenericTableAvl (
    _In_ PRTL_AVL_TABLE Table,
    _In_ PVOID Buffer
    );

    NTSYSAPI
    PVOID
    NTAPI
    RtlEnumerateGenericTableAvl (
    _In_ PRTL_AVL_TABLE Table,
    _In_ BOOLEAN Restart
    );

    NTSYSAPI
    PVOID
    NTAPI
    RtlEnumerateGenericTableWithoutSplayingAvl (
    _In_ PRTL_AVL_TABLE Table,
    _Inout_ PVOID *RestartKey
    );

    NTSYSAPI
    ULONG
    NTAPI
    RtlNumberGenericTableElementsAvl (
    _In_ PRTL_AVL_TABLE Table
    );

    #ifdef __cplusplus
    }
    #endif

    #endif //#ifndef __AVL_TREE_HEADER
    //AVL.H ends here.

    ======================================

    The allocate and free routines are simple. You just have to do
    what you are supposed to do: allocating a chunk of memory of the given
    size and freeing memory:

    PVOID
    NTAPI
    AllocateRoutine (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ ULONG ByteSize
    ){
    return HeapAlloc(GetProcessHeap(),HEAP_ZERO_MEMORY,(SIZE_T)ByteSize);
    }

    VOID
    NTAPI
    FreeRoutine(
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ PVOID Buffer
    ){
    HeapFree(GetProcessHeap(),0,Buffer);
    }

    The compare function is dependant on the data type of the node you insert in the tree.
    For example if you insert nodes of the following type:

    typedef struct _MYNODE{
    UINT Index;
    LPTSTR Name;
    } MYNODE, *PMYNODE;

    and if the Index field is used to compare nodes than the compare routine would be:

    RTL_GENERIC_COMPARE_RESULTS
    NTAPI CompareRoutine (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ PVOID FirstStruct,
    _In_ PVOID SecondStruct
    ){
    PMYNODE Node1, Node2;

    Node1 = (PMYNODE)FirstStruct;
    Node2 = (PMYNODE)SecondStruct;

    if(Node1->Index > Node2->Index){
    return GenericGreaterThan;
    }
    else if(Node1->Index < Node2->Index){
    return GenericLessThan;
    }

    return GenericEqual;
    }

    Note that strings can be compared as well (lexicographical or dictionary order)
    and could be used for indexing purpose. But for large collections, working with
    string hashes is probably better and a hashing function is required.









    ---
    NTDEV is sponsored by OSR

    Visit the list online at:

    MONTHLY seminars on crash dump analysis, WDF, Windows internals and software drivers!
    Details at

    To unsubscribe, visit the List Server section of OSR Online at
    --- NTDEV is sponsored by OSR Visit the list online at: MONTHLY seminars on crash dump analysis, WDF, Windows internals and software drivers! Details at To unsubscribe, visit the List Server section of OSR Online at

    ---
    NTDEV is sponsored by OSR

    Visit the list online at:

    MONTHLY seminars on crash dump analysis, WDF, Windows internals and software drivers!
    Details at

    To unsubscribe, visit the List Server section of OSR Online at
  • MBondMBond Member - All Emails Posts: 846
    It would be better I thing if the moderators would lock my account so that I don?t post any more drivel like this

    Sent from Mail for Windows 10

    From: Marion Bond
    Sent: July 25, 2016 8:13 PM
    To: Windows System Software Devs Interest List
    Subject: RE: [ntdev] Need to Sample source for _RTL_AVL_TABLE

    RB trees have their own set of flaws ? the largest underreported one is the assumption of entirely symmetric memory access and the very CPU cache unfriendly behaviours that can ensue ? this is also true of most tree implementations and does not necessarily reflect poorly on this one as the current _state of the art_ has exactly these problems. This can be even worse on NUMA machines and no current production OS provides an adequate facility to identify or resolve these problems IMHO

    Large CPU caches reduce the severity of the impact of data structures that have poor locality of reference, and indeed this is a secondary effect when compared with the efficiency of the algorithms, but even still secondary effects can still play a substantial role.

    A significantly better tree algorithm that can be both compare and cache efficient does exist but I am not at liberty to disclose any of its details. I may flatter myself by mentioning it, but as the cancer doctors will shortly decide if my demise is imminent or at some protracted point in the future, I don?t care so much

    In keeping with these challenges, I did buy a tablet (a surface) and learned to type left handed so that I can keep supplying all of the form members some increasingly erratic posts on religious, political, moral and by the way technical issues too. I apologise in advance to all of those whom I have learned from for squandering that wisdom

    As these issues are totally OT, I hope we can get some better ones soon.

    In the remote event that anyone wants to know about binary tree stability on cache coherent NUMA machines spanning millions of nodes in Windows KM, let me know and I?ll work on writing something that may make sense.


    Sent from Mail for Windows 10

    From: Maxim S. Shatskih
    Sent: July 25, 2016 6:55 AM
    To: Windows System Software Devs Interest List
    Subject: Re:[ntdev] Need to Sample source for _RTL_AVL_TABLE

    If you delete a lot, then maybe red-black tree is better then AVL one.

    That's why most STL implementations use RB trees for sets and maps.

    --
    Maxim S. Shatskih
    Microsoft MVP on File System And Storage
    xxxxx@storagecraft.com
    http://www.storagecraft.com
    "Marion Bond" > wrote in message news:xxxxx@ntdev...
    It is well known that amongst all binary trees, AVL is a compromise. I suspect that the engineers at Microsoft chose this one because is exactly that.

    Their counterparts in the SQL server team long ago made the choice to use b-trees instead (which are not binary however confusing the name). IMHO, primarily because of the relative ease of writing the data structures to disk in an atomic way ? and I stress relative ease

    Skiplists are not a tree at all, but a modified form of a queue or linked list. They are especially useful if the data added to the list is in a particular order and the cost of comparison between elements is high. Depending on the depth of the skip, and the distribution of data, and the access pattern, they can improve performance dramatically since often far fewer comparisons are required to find the desired data. Order of elements is especially important when using skiplists as they are totally ineffective on lists with arbitrary order.

    Again, depending upon the data insertion and access patterns, as well as the relative cost of comparisons, there are many different data structures that may be better or worse for a particular purpose. This is no new wisdom.

    If the OP has already decided to use the AVL APIs (DDIs) presumably he _knows_ that his particular usage pattern will benefit from this kind of data structure. We may presume that at least his boss suspects that the usage pattern will benefit from this. It may be possible to use an alternate data structure to a greater effect, but we have no possible way to know. One important factor is that AFAIK the only data structures that have built-in implementations in Windows for KM are the linked list and the AVL tree. I have no problem implementing generic data structures in KM, but others may wish to rely on the built-in functions as they have been well tested and peer reviewed

    Sent from Mail for Windows 10

    From: Jamey Kirby
    Sent: July 24, 2016 3:34 PM
    To: Windows System Software Devs Interest List
    Subject: Re: [ntdev] Need to Sample source for _RTL_AVL_TABLE

    AVL is a bit heavy. If you want something just as fast, open source, and extremely easy to understand, try my kernel-mode skiplist implementation. I modeled it to use nearly the same interface semantics as RTL_GENERIC_TABLE. It is available on GitHub. https://github.com/jameykirby/public

    On Thu, Jul 21, 2016 at 7:10 PM > wrote:
    At one point, The Microsoft's AVL tree implementation was the one described
    in Knuth, "The Art of Computer Programming, Volume 3, Sorting and Searching".

    I don't know if that has changed over time but the important think is that
    the implementation is exported to usermode with NTDLL.DLL. You can test the
    API in usermode with large collections of data. The WIN32 UI and the console
    are probably easier to use for this purpose. Here is a header (AVL.H) you can
    use to test the API:

    /* AVL.H

    Copyright (c) Microsoft Corporation. All rights reserved.

    For testing purpose only !

    This material was copied from the WDK's NTDDK.H header
    to use Microsoft's AVL tree implementation in usermode.

    Functions whose prototype begins with NTSYSAPI are exported
    by NTDLL.DLL. ntdll.lib must be added to the list of libraries
    imported by the project or any (.c or .cpp) source file that
    calls one of these functions must contain the line:

    #pragma comment(lib,"ntdll.lib")

    */


    #ifndef __AVL_TREE_HEADER
    #define __AVL_TREE_HEADER

    /* We need Windows Internal defs and typedefs here*/
    #include

    #ifdef __cplusplus
    extern "C" {
    #endif

    //AVL Tree defs and typedefs

    typedef enum _RTL_GENERIC_COMPARE_RESULTS {
    GenericLessThan,
    GenericGreaterThan,
    GenericEqual
    } RTL_GENERIC_COMPARE_RESULTS;

    typedef
    RTL_GENERIC_COMPARE_RESULTS
    NTAPI
    RTL_AVL_COMPARE_ROUTINE (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ PVOID FirstStruct,
    _In_ PVOID SecondStruct
    );
    typedef RTL_AVL_COMPARE_ROUTINE *PRTL_AVL_COMPARE_ROUTINE;

    typedef
    PVOID
    NTAPI
    RTL_AVL_ALLOCATE_ROUTINE (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ ULONG ByteSize
    );
    typedef RTL_AVL_ALLOCATE_ROUTINE *PRTL_AVL_ALLOCATE_ROUTINE;

    typedef
    VOID
    NTAPI
    RTL_AVL_FREE_ROUTINE (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ PVOID Buffer
    );
    typedef RTL_AVL_FREE_ROUTINE *PRTL_AVL_FREE_ROUTINE;

    typedef struct _RTL_BALANCED_LINKS {
    struct _RTL_BALANCED_LINKS *Parent;
    struct _RTL_BALANCED_LINKS *LeftChild;
    struct _RTL_BALANCED_LINKS *RightChild;
    CHAR Balance;
    UCHAR Reserved[3];
    } RTL_BALANCED_LINKS;
    typedef RTL_BALANCED_LINKS *PRTL_BALANCED_LINKS;

    typedef struct _RTL_AVL_TABLE {
    RTL_BALANCED_LINKS BalancedRoot;
    PVOID OrderedPointer;
    ULONG WhichOrderedElement;
    ULONG NumberGenericTableElements;
    ULONG DepthOfTree;
    PRTL_BALANCED_LINKS RestartKey;
    ULONG DeleteCount;
    PRTL_AVL_COMPARE_ROUTINE CompareRoutine;
    PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine;
    PRTL_AVL_FREE_ROUTINE FreeRoutine;
    PVOID TableContext;
    } RTL_AVL_TABLE;
    typedef RTL_AVL_TABLE *PRTL_AVL_TABLE;

    NTSYSAPI
    VOID
    NTAPI
    RtlInitializeGenericTableAvl (
    _Out_ PRTL_AVL_TABLE Table,
    _In_ PRTL_AVL_COMPARE_ROUTINE CompareRoutine,
    _In_ PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine,
    _In_ PRTL_AVL_FREE_ROUTINE FreeRoutine,
    _In_opt_ PVOID TableContext
    );

    NTSYSAPI
    PVOID
    NTAPI
    RtlInsertElementGenericTableAvl (
    _In_ PRTL_AVL_TABLE Table,
    _In_reads_bytes_(BufferSize) PVOID Buffer,
    _In_ ULONG BufferSize,
    _Out_opt_ PBOOLEAN NewElement
    );

    NTSYSAPI
    BOOLEAN
    NTAPI
    RtlDeleteElementGenericTableAvl (
    _In_ PRTL_AVL_TABLE Table,
    _In_ PVOID Buffer
    );

    NTSYSAPI
    VOID
    NTAPI
    RtlDeleteElementGenericTableAvlEx (
    _In_ PRTL_AVL_TABLE Table,
    _In_ PVOID NodeOrParent
    );

    NTSYSAPI
    PVOID
    NTAPI
    RtlLookupElementGenericTableAvl (
    _In_ PRTL_AVL_TABLE Table,
    _In_ PVOID Buffer
    );

    NTSYSAPI
    PVOID
    NTAPI
    RtlEnumerateGenericTableAvl (
    _In_ PRTL_AVL_TABLE Table,
    _In_ BOOLEAN Restart
    );

    NTSYSAPI
    PVOID
    NTAPI
    RtlEnumerateGenericTableWithoutSplayingAvl (
    _In_ PRTL_AVL_TABLE Table,
    _Inout_ PVOID *RestartKey
    );

    NTSYSAPI
    ULONG
    NTAPI
    RtlNumberGenericTableElementsAvl (
    _In_ PRTL_AVL_TABLE Table
    );

    #ifdef __cplusplus
    }
    #endif

    #endif //#ifndef __AVL_TREE_HEADER
    //AVL.H ends here.

    ======================================

    The allocate and free routines are simple. You just have to do
    what you are supposed to do: allocating a chunk of memory of the given
    size and freeing memory:

    PVOID
    NTAPI
    AllocateRoutine (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ ULONG ByteSize
    ){
    return HeapAlloc(GetProcessHeap(),HEAP_ZERO_MEMORY,(SIZE_T)ByteSize);
    }

    VOID
    NTAPI
    FreeRoutine(
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ PVOID Buffer
    ){
    HeapFree(GetProcessHeap(),0,Buffer);
    }

    The compare function is dependant on the data type of the node you insert in the tree.
    For example if you insert nodes of the following type:

    typedef struct _MYNODE{
    UINT Index;
    LPTSTR Name;
    } MYNODE, *PMYNODE;

    and if the Index field is used to compare nodes than the compare routine would be:

    RTL_GENERIC_COMPARE_RESULTS
    NTAPI CompareRoutine (
    _In_ struct _RTL_AVL_TABLE *Table,
    _In_ PVOID FirstStruct,
    _In_ PVOID SecondStruct
    ){
    PMYNODE Node1, Node2;

    Node1 = (PMYNODE)FirstStruct;
    Node2 = (PMYNODE)SecondStruct;

    if(Node1->Index > Node2->Index){
    return GenericGreaterThan;
    }
    else if(Node1->Index < Node2->Index){
    return GenericLessThan;
    }

    return GenericEqual;
    }

    Note that strings can be compared as well (lexicographical or dictionary order)
    and could be used for indexing purpose. But for large collections, working with
    string hashes is probably better and a hashing function is required.









    ---
    NTDEV is sponsored by OSR

    Visit the list online at:

    MONTHLY seminars on crash dump analysis, WDF, Windows internals and software drivers!
    Details at

    To unsubscribe, visit the List Server section of OSR Online at
    --- NTDEV is sponsored by OSR Visit the list online at: MONTHLY seminars on crash dump analysis, WDF, Windows internals and software drivers! Details at To unsubscribe, visit the List Server section of OSR Online at

    ---
    NTDEV is sponsored by OSR

    Visit the list online at:

    MONTHLY seminars on crash dump analysis, WDF, Windows internals and software drivers!
    Details at

    To unsubscribe, visit the List Server section of OSR Online at

    ---
    NTDEV is sponsored by OSR

    Visit the list online at:

    MONTHLY seminars on crash dump analysis, WDF, Windows internals and software drivers!
    Details at

    To unsubscribe, visit the List Server section of OSR Online at
  • Tim_RobertsTim_Roberts Member - All Emails Posts: 13,103
    Marion Bond wrote:
    >
    >
    > It would be better I thing if the moderators would lock my account so
    > that I don’t post any more drivel like this
    >

    That's the funniest thing I read today. If only our political nominees
    felt this way.

    --
    Tim Roberts, xxxxx@probo.com
    Providenza & Boekelheide, Inc.

    Tim Roberts, [email protected]
    Providenza & Boekelheide, Inc.

  • Prokash_Sinha-1Prokash_Sinha-1 Member - All Emails Posts: 1,214
    Marion, not sure why you wrote this !!. .

    BTW, I was following the thread casually. Needless to say, we all pray
    for you ...

    When Jemmy said it is a skip list, the randomized data comes for testing
    the performance and compare against AVL, if I read his stmt correctly !
    The lists within those ranges are not totally ( or randomly) unordered,
    it is some form of bucketing, we all know this :)

    I'm still not sure if the OP is looking for user mode or inside the
    kernel. Not even sure what it means by "very large set of data". Say for
    example it is zillions of data that needs to be searched, then there are
    not of questions arises like you mentioned about cache awareness, how
    many threads/processes can collaboratively take a shot at it, etc.

    Like anything else here, it is important to have a rough idea about the
    environment the algorithm would be working.

    I'm sure there are lots of survey papers ( more pragmatics one), that
    can shed some lights on it. For example, map-reduce came to tackle huge
    data overload when searching for some match/potential match etc. And
    again there are very clear discussions on it. One pointer is "Beautiful
    Code".

    FWIW ...

    Pro


    On 07/25/2016 06:24 PM, Tim Roberts wrote:
    > Marion Bond wrote:
    >>
    >> It would be better I thing if the moderators would lock my account so
    >> that I don’t post any more drivel like this
    >>
    > That's the funniest thing I read today. If only our political nominees
    > felt this way.
    >
  • anton_bassovanton_bassov Member Posts: 5,052
    > It is well known that amongst all binary trees, AVL is a compromise.



    Well, any binary tree offers some form of a compromise between the speed of locating an item and the one of inserting/deleting the one. In this sense unbalanced tree and AVL one are two extremes. In the former case, adding and removing items is really easy and fast, but locating the one in some cases may be as bad as performing this task on a linked list, i.e. you may have to examine all the entries in it. This is what going to happen if you enter the data that increases/decreases monotonously, into an unbalanced binary tree.



    AVL tree is another extreme - it guarantees logarithmic performance upon locating any particular item, but insertions and deletions are relatively expensive, because re-balancing AVL tree happens to be not the easiest task one would imagine.



    In this sense, the true compromise is RB tree - compared to AVL tree, it is easier to re-balance, but, at the same time, it guarantees that the longest path in a tree is at most twice as long as the shortest one, which implies almost logarithmic performance upon locating data.



    > Their counterparts in the SQL server team long ago made the choice to use b-trees
    >instead (which are not binary however confusing the name).


    Well, B-tree is a totally different thing. It makes sense to use it when reading and writing a block of entries bears exactly the same cost, in terms of performance, as reading or writing a single entry, and the cost of examining all entries in a block is almost negligible. This is why B-trees are so popular in the world of databases and file systems.....



    > Again, depending upon the data insertion and access patterns, as well as the relative
    > cost of comparisons, there are many different data structures that may be better or worse
    > for a particular purpose.


    This is, probably, the most reasonable statement on this thread in so far......


    Anton Bassov
  • Maxim_S._ShatskihMaxim_S._Shatskih Member Posts: 10,396
    > AVL tree is another extreme - it guarantees logarithmic performance upon locating any particular
    >item, but insertions and deletions are relatively expensive, because re-balancing AVL tree happens
    >to be not the easiest task one would imagine.

    Fixed small time (like 3 turns) on insert, and logarithmic (turns up to the tree root) on delete.

    RB tree: IIRC 3 turns on insert and 4 turns on delete. The downside is that it can be imbalanced up to 2 times.

    > In this sense, the true compromise is RB tree - compared to AVL tree, it is easier to re-balance,

    On inserts - no. Only on deletes.

    It is only better if you delete a lot. Around 15 years ago I've measured it.

    > Well, B-tree is a totally different thing.

    First of all, the SQL's data structure needs to be serializable to disk at block level. B-tree perfectly fits this.

    --
    Maxim S. Shatskih
    Microsoft MVP on File System And Storage
    xxxxx@storagecraft.com
    http://www.storagecraft.com
  • anton_bassovanton_bassov Member Posts: 5,052
    > Fixed small time (like 3 turns) on insert,

    This is just a rotation per se. However, before you can perform the one you have to traverse the tree until you find a node whose grandparent is unbalanced, which means that you may have to go all the way up to the root. At this point you will have to perform, depending on the situation, either a single rotation or a double one....


    http://www.dcs.gla.ac.uk/~pat/52233/slides/AVLTrees1x1.pdf



    In other words, it is not as simple as it seems to be at the first glance - in some cases it may be as bad as a deletion.....



    Anton Bassov
  • Jamey_KirbyJamey_Kirby Member - All Emails Posts: 438
    I ran across this today, and remembering this thread, I thought I would
    post a link.
    http://stackoverflow.com/questions/256511/skip-list-vs-binary-tree


    On Tue, Jul 26, 2016 at 8:56 PM wrote:

    > > Fixed small time (like 3 turns) on insert,
    >
    > This is just a rotation per se. However, before you can perform the one
    > you have to traverse the tree until you find a node whose grandparent is
    > unbalanced, which means that you may have to go all the way up to the root.
    > At this point you will have to perform, depending on the situation, either
    > a single rotation or a double one....
    >
    >
    > http://www.dcs.gla.ac.uk/~pat/52233/slides/AVLTrees1x1.pdf
    >
    >
    >
    > In other words, it is not as simple as it seems to be at the first glance
    > - in some cases it may be as bad as a deletion.....
    >
    >
    >
    > Anton Bassov
    >
    > ---
    > NTDEV is sponsored by OSR
    >
    > Visit the list online at: <
    > http://www.osronline.com/showlists.cfm?list=ntdev>;
    >
    > MONTHLY seminars on crash dump analysis, WDF, Windows internals and
    > software drivers!
    > Details at
    >
    > To unsubscribe, visit the List Server section of OSR Online at <
    > http://www.osronline.com/page.cfm?name=ListServer>;
    >
  • Peter_Viscarola_(OSR)Peter_Viscarola_(OSR) Administrator Posts: 7,443
    Thanks, Jamey.

    I have a DL List that I currently maintain in order... I'm saving the idea of changing it to a skip list for an update. The problem is that I'm working very hard to be memory-efficient with my structures. Sigh... Size vs speed strikes again,eh?

    Peter
    OSR
    @OSRDrivers

    Peter Viscarola
    OSR
    @OSRDrivers

Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Upcoming OSR Seminars
Writing WDF Drivers 21 Oct 2019 OSR Seminar Space & ONLINE
Internals & Software Drivers 18 Nov 2019 Dulles, VA
Kernel Debugging 30 Mar 2020 OSR Seminar Space
Developing Minifilters 27 Apr 2020 OSR Seminar Space & ONLINE