This patch introduces a highly-shareable version of AVL trees both for RTL usage...
authorSir Richard <sir_richard@svn.reactos.org>
Thu, 22 Jul 2010 01:41:45 +0000 (01:41 +0000)
committerSir Richard <sir_richard@svn.reactos.org>
Thu, 22 Jul 2010 01:41:45 +0000 (01:41 +0000)
commit40e4bc04b54c3b7614f9d80ff8b7f381fd1bec6e
tree8d81260779a68807ad5c828a7d4d8471f0ee3404
parent23e18538f16e7e6aa95fdf3e00490fc333da1118
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:
reactos/lib/rtl/austin/avl.c [deleted file]
reactos/lib/rtl/austin/avl.h [deleted file]
reactos/lib/rtl/austin/macros.h [deleted file]
reactos/lib/rtl/austin/tree.c [deleted file]
reactos/lib/rtl/austin/tree.h [deleted file]
reactos/lib/rtl/austin/udict.h [deleted file]
reactos/lib/rtl/avlsupp.c [new file with mode: 0644]
reactos/lib/rtl/avltable.c [new file with mode: 0644]
reactos/lib/rtl/generictable.c
reactos/lib/rtl/rtl.rbuild
reactos/lib/rtl/rtlavl.h [new file with mode: 0644]
reactos/ntoskrnl/mm/ARM3/miavl.h [new file with mode: 0644]
reactos/ntoskrnl/mm/ARM3/vadnode.c [new file with mode: 0644]
reactos/ntoskrnl/ntoskrnl-generic.rbuild