struct rb_root{} implementation in Windows

NTDEV
1

Hi Experts,

While am porting the linux device driver to Windows, I came across this struct rb_root and struct rb_node Implementation in linux.

While creating a table for the page table , they used these kind of stuffs to handle the page table.

How do I can make use of such structures functionality in Windows.

AS it is a linux structure, I do try to understand what is rb_root and rb_node and all. But am not sure of such functionality in windows.

Please give your inputs.

Thanks in Advance
Janaki

2

You can use Adelson-Velsky/Landis (AVL) tree.
It is in Runtime Library Routines:
https://msdn.microsoft.com/en-us/library/windows/hardware/hh406465(v=vs.85).aspx

Adam

3

xxxxx@gmail.com wrote:

While am porting the linux device driver to Windows, I came across this struct rb_root and struct rb_node Implementation in linux.

While creating a table for the page table , they used these kind of stuffs to handle the page table.

How do I can make use of such structures functionality in Windows.

AS it is a linux structure, I do try to understand what is rb_root and rb_node and all. But am not sure of such functionality in windows.

You really need to be careful about “porting” Linux drivers to Windows.
The kernel philosophies are different enough that you cannot do a simple
line-by-line translation. You need to think about what the driver is
DOING, and then learn how to DO that in Windows.

“rb_root” and “rb_node” are the Linux kernel implementation of a
red/black tree. It’s the same fundamental data structure used by
std::map in the standard C++ library.

Nothing in the Windows kernel uses a red/black tree. You need to figure
out what they are storing in the tree, and implement it using the data
structures that are available. Sadly, the Windows kernel is woefully
lacking in data structure options.

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