OSDev.org

Ok, finally I got my radix/patrica tree implemented But I think that the algo can be optimized. Maybe someone has an idea how I can make it even faster?!

I also need an idea how I can move the strings, which are used in the tree, to another location (out of the elf file into kernel space) without having the strings more than one time in kernel space. The problem here is, that I don´t know if I have a string in kernel space or not. So I started to only move those strings, where the node has a value != 0 and then I parse the tree again and get the addr of the strings where the value is == 0. But this doesn´t work

Edit::

I solved the problem with moving the strings. I just have to traverse the tree in postorder.

I learned that my implementation isn´t a patricia tree, but I´ve written a new one and used as a starting point an implementation from sedgewick (which doesn´t work with strings ). But there has to be an error in my code, because it doesn´t work if I use it for my kernel symbols. In my little test case it works as expected!

Please have a look and ask if you don´t understand a line or the algo, maybe so we can find the error!

I just finished my working (it works for my kernel symbol table, so I think that it is working) implementation of a patricia tree!