Unlimited objects support for POSIX keys

This patch enables unlimited model in POSIX key manger and have a decent
runtime on POSIX key searching, adding and deleting operations.  Memory
overhead is lower than current implementation when the size of key and key
value becomes big.

1 files changed, 70 insertions, 20 deletions

diff --git a/cpukit/posix/include/rtems/posix/key.h b/cpukit/posix/include/rtems/posix/key.h
index 6d2ebff6fd..ee5b573c9b 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,28 @@
  */
 
 /*
- *  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/rbtree.h>
+#include <rtems/score/chainimpl.h>
+#include <rtems/score/freechain.h>
 #include <rtems/score/objectimpl.h>
 
 /**
  * @defgroup POSIX_KEY POSIX Key
  *
  * @ingroup POSIXAPI
- * 
+ *
  */
 /**@{**/
 
@@ -34,40 +38,86 @@ 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.
+ * @brief The rbtree node used to manage a POSIX key and value.
+ */
+typedef struct {
+  /** This field is the chain node structure. */
+  Chain_Node Key_values_per_thread_node;
+  /** This field is the rbtree node structure. */
+  RBTree_Node Key_value_lookup_node;
+  /** 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_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 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_Key_value_lookup_tree;
+
+/**
+ * @brief This freechain is used as a memory pool for POSIX_Keys_Key_value_pair.
+ */
+POSIX_EXTERN POSIX_Keys_Freechain _POSIX_Keys_Keypool;
+
+/**
+ * @brief POSIX key manager initialization.
  *
  * This routine performs the initialization necessary for this manager.
  */
 void _POSIX_Key_Manager_initialization(void);
 
 /**
+ * @brief POSIX key Freechain extend handle
+ *
+ * This routine extend freechain node, which is called in freechain_get
+ * automatically.
+ */
+bool _POSIX_Keys_Freechain_extend(Freechain_Control *freechain);
+
+/**
+ * @brief POSIX keys Red-Black tree node comparison.
+ *
+ * This routine compares the rbtree node
+ */
+int _POSIX_Keys_Key_value_lookup_tree_compare_function(
+  const RBTree_Node *node1,
+  const RBTree_Node *node2
+);
+
+/**
  * @brief Create thread-specific data POSIX key.
  *
  * This function executes all the destructors associated with the thread's
  * keys.  This function will execute until all values have been set to NULL.
  *
- * @param[in] thread is a pointer to the thread whose keys should have 
+ * @param[in] thread is a pointer to the thread whose keys should have
  *            all their destructors run.
  *
  * NOTE: This is the routine executed when a thread exits to