[GSoC]use hash/map in POSIX key and Classic notepad

Gedare Bloom gedare at rtems.org
Wed Apr 4 01:38:49 UTC 2012

On Tue, Apr 3, 2012 at 6:08 PM, Chris Johns <chrisj at rtems.org> wrote:
> On 2/04/12 4:21 AM, Joel Sherrill wrote:
>>  From phone. I don't know how using rbtree would impact memory allocation
>> in the sense of when allocations occur but since if the tree stays balanced,
>> that may be a viable implementation.
>> Or a hash... I know the problem and don't claim to know the perfect
>> solution. :)
> Maybe this is something the project could focus on. Looking at both and
> seeing how they stack up against each other.

Using the rbtree you don't need a hash since you can use thread ids
directly (I think?); using a hash you still need some structure to map
into for insert/search of key data, such as a tree or an array of
linked lists. The time complexity of the different map algorithms is
what matters most here. The usual hash+array solution is theoretically
quite bad in the worst case; leveraging properties about the threads
themselves might make it better. One problem that I see with using an
rbtree (or array+chain) is that the Key.Values will need to embed an
rbtree_node (or chain_node) along with the user data (void*).

I agree that evaluating different solutions for creating and finding
the Key data should be part of this project, and also determining
whether its possible to frontload some costs to key creation.

> Chris
> _______________________________________________
> rtems-devel mailing list
> rtems-devel at rtems.org
> http://www.rtems.org/mailman/listinfo/rtems-devel

More information about the users mailing list