[PATCH] posix: Reimplement POSIX Key manager to use a red-black tree.
Sebastian Huber
sebastian.huber at embedded-brains.de
Thu Aug 1 07:53:25 UTC 2013
Hello Ashi,
thanks for your update.
On 2013-07-31 15:03, Ashi wrote:
> diff --git a/cpukit/posix/include/rtems/posix/config.h b/cpukit/posix/include/rtems/posix/config.h
> index 104bd84..2c76cc1 100644
> --- a/cpukit/posix/include/rtems/posix/config.h
> +++ b/cpukit/posix/include/rtems/posix/config.h
> @@ -51,6 +51,7 @@ typedef struct {
> uint32_t maximum_mutexes;
> uint32_t maximum_condition_variables;
> uint32_t maximum_keys;
> + uint32_t maximum_key_pairs;
I would call this maximum_key_value_pairs.
> uint32_t maximum_timers;
> uint32_t maximum_queued_signals;
> uint32_t maximum_message_queues;
> diff --git a/cpukit/posix/include/rtems/posix/key.h b/cpukit/posix/include/rtems/posix/key.h
> index 6d2ebff..d2c51bd 100644
> --- a/cpukit/posix/include/rtems/posix/key.h
> +++ b/cpukit/posix/include/rtems/posix/key.h
> @@ -1,6 +1,6 @@
> /**
> * @file
> - *
> + *
> * @brief POSIX Key Private Support
> *
> * This include file contains all the private support information for
> @@ -8,24 +8,30 @@
> */
>
> /*
> - * COPYRIGHT (c) 1989-2011.
> - * On-Line Applications Research Corporation (OAR).
> + * Copyright (c) 2012 Zhongwei Yao.
> + * COPYRIGHT (c) 1989-2011.
> + * On-Line Applications Research Corporation (OAR).
> *
> - * The license and distribution terms for this file may be
> - * found in the file LICENSE in this distribution or at
> - *http://www.rtems.com/license/LICENSE.
> + * The license and distribution terms for this file may be
> + * found in the file LICENSE in this distribution or at
> + *http://www.rtems.com/license/LICENSE.
> */
>
> #ifndef _RTEMS_POSIX_KEY_H
> #define _RTEMS_POSIX_KEY_H
>
> +#include <rtems/score/object.h>
> +#include <rtems/score/rbtree.h>
> +#include <rtems/score/chain.h>
> +#include <rtems/score/chainimpl.h>
> +#include <rtems/score/freechain.h>
> #include <rtems/score/objectimpl.h>
The xyzimpl.h files include the zyz.h files. So the object.h and chain.h
includes are superfluous.
>
> /**
> * @defgroup POSIX_KEY POSIX Key
> *
> * @ingroup POSIXAPI
> - *
> + *
> */
> /**@{**/
>
> @@ -34,40 +40,93 @@ extern "C" {
> #endif
>
> /**
> - * This is the data Structure used to manage a POSIX key.
> - *
> - * NOTE: The Values is a table indexed by the index portion of the
> - * ID of the currently executing thread.
> + * Forward declaretion
> + */
> +typedef struct POSIX_Keys_Freechain_node_struct POSIX_Keys_Freechain_node;
> +
> +/**
> + * @brief The rbtree node used to manage a POSIX key and value.
> + */
> +typedef struct {
> + /** This field is the chain node structure. */
> + Chain_Node ch_node;
> + /** This field is the rbtree node structure. */
> + RBTree_Node rb_node;
It would be nice to have field names that describe the purpose of the nodes,
e.g. Key_values_per_thread_node and Key_value_lookup_node.
> + /** This field points to parent freechain node */
> + POSIX_Keys_Freechain_node *fc_node_ptr;
I don't think we need this fc_node_ptr.
> + /** 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?
> +
> +/**
> + * @brief The data structure used to manage a POSIX key.
> */
> typedef struct {
> /** This field is the Object control structure. */
> Objects_Control Object;
> - /** This field points to the optional destructor method. */
> - void (*destructor)( void * );
> - /** This field points to the values per thread. */
> - void **Values[ OBJECTS_APIS_LAST + 1 ];
> -} POSIX_Keys_Control;
> + /** This field is the data destructor. */
> + void (*destructor) (void *);
> + } POSIX_Keys_Control;
>
> /**
> - * The following defines the information control block used to manage
> - * this class of objects.
> + * @brief The information control block used to manage this class of objects.
> */
> POSIX_EXTERN Objects_Information _POSIX_Keys_Information;
>
> /**
> - * @brief POSIX keys manager initialization.
> + * @brief The rbtree control block used to manage all key values
> + */
> +POSIX_EXTERN RBTree_Control _POSIX_Keys_Rbtree;
I would call this _POSIX_Keys_Key_value_lookup_tree.
[...]
> diff --git a/cpukit/posix/src/key.c b/cpukit/posix/src/key.c
> index 6eace26..71d6a8d 100644
> --- a/cpukit/posix/src/key.c
> +++ b/cpukit/posix/src/key.c
> @@ -6,12 +6,13 @@
> */
>
> /*
> - * COPYRIGHT (c) 1989-2008.
> - * On-Line Applications Research Corporation (OAR).
> + * Copyright (c) 2012 Zhongwei Yao.
> + * COPYRIGHT (c) 1989-2008.
> + * On-Line Applications Research Corporation (OAR).
> *
> - * The license and distribution terms for this file may be
> - * found in the file LICENSE in this distribution or at
> - *http://www.rtems.com/license/LICENSE.
> + * The license and distribution terms for this file may be
> + * found in the file LICENSE in this distribution or at
> + *http://www.rtems.com/license/LICENSE.
> */
>
> #if HAVE_CONFIG_H
> @@ -29,19 +30,116 @@
> #include <rtems/score/thread.h>
> #include <rtems/score/wkspace.h>
> #include <rtems/posix/key.h>
> +#include <rtems/score/rbtree.h>
> +#include <rtems/score/chain.h>
> +#include <rtems/score/freechain.h>
>
> -/*
> - * _POSIX_Key_Manager_initialization
> - *
> - * DESCRIPTION:
> - *
> - * This routine performs the initialization necessary for this manager.
> +/* forward declarations to avoid warnings */
> +void _POSIX_Keys_Keypool_init(void);
> +bool _POSIX_Keys_Freechain_extend(Freechain_Control *freechain);
> +void _POSIX_Keys_Freechain_init(Freechain_Control *freechain);
Never place declarations of global functions in a source file.
[...]
> + /**
> + * delete all nodes belongs to the_key from the rbtree and chain.
> + */
> + p = _RBTree_Container_of( iter, POSIX_Keys_Rbtree_node, rb_node );
> + while ( p->key == the_key->Object.id ) {
> + next = _RBTree_Next_unprotected( iter, RBT_RIGHT );
> + _RBTree_Extract_unprotected( &_POSIX_Keys_Rbtree, iter );
> + _Chain_Extract_unprotected( &p->ch_node );
> + /* append the node to _POSIX_Keys_Keypool */
> + _Freechain_Put( (Freechain_Control *)&_POSIX_Keys_Keypool,
> + ( void * ) p->fc_node_ptr);
[...]
Please avoid casts like this. Use _Freechain_Put(
&_POSIX_Keys_Keypool.super_fc, ...) instead.
--
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
PGP : Public key available on request.
Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.
More information about the devel
mailing list