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

[Gedare Bloom]

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