[PATCH] posix: Reimplement POSIX Key manager to use a red-black tree.

[Ashi]

Hi, All. The patch is updated according to Sebastian's comments.

Cheers,
Zhongwei


On Fri, Aug 2, 2013 at 7:01 PM, Ashi <ashi08104 at gmail.com> wrote:

>
>
>
> On Fri, Aug 2, 2013 at 2:38 PM, Sebastian Huber <
> sebastian.huber at embedded-brains.de> wrote:
>
>> On 2013-08-02 03:03, Ashi wrote:
>>
>>>
>>>         +  /** This field points to parent freechain node */
>>>         +  POSIX_Keys_Freechain_node *fc_node_ptr;
>>>
>>>
>>>     I don't think we need this fc_node_ptr.
>>>
>>> Do you mean use a 'Container' macro instead?
>>>
>>
>> Not necessarily, see below.
>>
>>
>>>
>>>         +  /** This field is the POSIX key used as an rbtree key */
>>>         +  pthread_key_t key;
>>>         +  /** This field is the Thread id also used as an rbtree key */
>>>         +  Objects_Id thread_id;
>>>         +  /** This field points to the POSIX key value of specific
>>> thread */
>>>         +  void *value;
>>>         +}  POSIX_Keys_Rbtree_node;
>>>
>>>
>>>     I would call this POSIX_Keys_Key_value_pair.
>>>
>>>         +
>>>         +/**
>>>         + * @brief POSIX_Keys_Freechain is used in Freechain structure
>>>         + */
>>>         +typedef struct {
>>>         +    Freechain_Control super_fc;
>>>         +    size_t bump_count;
>>>         +} POSIX_Keys_Freechain;
>>>         +
>>>         +/**
>>>         + * @brief POSIX_Keys_Freechain_node is freechain node
>>>         + */
>>>         +struct POSIX_Keys_Freechain_node___**struct {
>>>
>>>         +  Chain_Node ch_node;
>>>         +  POSIX_Keys_Rbtree_node rb_node;
>>>         +};
>>>
>>>
>>>     Why not use POSIX_Keys_Rbtree_node directly?
>>>
>>> Since every freechain node needs a Chain_Node in its first field. There
>>> is a
>>> Chain_Node in  POSIX_Keys_Rbtree_node, but it is used in each thread's
>>> key
>>> value chain. So I add a Chain_Node to POSIX_Keys_Rbtree_node.
>>>
>>
>> The key value pairs on the free chain are unused, thus not part of other
>> data structures.  So basically you can cast an unused object to any type
>> provided it has enough storage.
>
> Cool! I see. I didn't realise the whole key value pairs is actually unused
> until it moves from Freechain to POSIX key value pair.
>
>>
>>
>> --
>> Sebastian Huber, embedded brains GmbH
>>
>> Address : Dornierstr. 4, D-82178 Puchheim, Germany
>> Phone   : +49 89 189 47 41-16
>> Fax     : +49 89 189 47 41-09
>> E-Mail  : sebastian.huber at embedded-**brains.de<sebastian.huber at embedded-brains.de>
>> PGP     : Public key available on request.
>>
>> Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/devel/attachments/20130804/42c87dc9/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: improve-POSIX-Key-manager-cpukit_v2.patch
Type: application/octet-stream
Size: 31375 bytes
Desc: not available
URL: <http://lists.rtems.org/pipermail/devel/attachments/20130804/42c87dc9/attachment-0002.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: improve-POSIX-Key-manager-testsuites_v2.patch
Type: application/octet-stream
Size: 45273 bytes
Desc: not available
URL: <http://lists.rtems.org/pipermail/devel/attachments/20130804/42c87dc9/attachment-0003.obj>