This patch introduces a highly-shareable version of AVL trees both for RTL usage and for ARM3's MM_AVL_TABLE/MMADDRESS_NODE structures used by VADs on Windows (and soon, ReactOS):
[RTL]: Uncouple generic table from AVL table implementation into its own avltable.c
[RTL]: Get rid of "Austin" and fix prototypes of AVL table functions.
[RTL]: Re-implement AVL table functions, sharing as much code as possible with the SPLAY tree implementation which is pretty decent. Lookup, insert, enumeration are implemented, but not delete.
[RTL]: Make large part of the RTL AVL package into its own "support" file that can work both with MMADDRESS_NODE and RTL_BALANCED_LINKS structures. The former is used by ARM3 for VADs.
[NTOS]: Implement basic VAD AVL tree routines (Insert, LookupEmpty, GetPrevious, CheckForConflict, Locate). This is enough to insert VADs, find a free address range, and locate a VAD by address. No delete yet
Thanks to Timo Kreuzer for some clever definitions, Knuth for his genius, several online C implementations for ideas, the HPI kernel blog for insight on how Windows does it, and others.
svn path=/trunk/; revision=48173
14 files changed: