score: Add freechain

10 files changed, 419 insertions, 0 deletions

diff --git a/cpukit/score/Makefile.am b/cpukit/score/Makefile.am
index 817ad886e3..06b6f11c23 100644
--- a/cpukit/score/Makefile.am
+++ b/cpukit/score/Makefile.am
@@ -36,6 +36,7 @@ include_rtems_score_HEADERS += include/rtems/score/protectedheap.h
 include_rtems_score_HEADERS += include/rtems/score/interr.h
 include_rtems_score_HEADERS += include/rtems/score/isr.h
 include_rtems_score_HEADERS += include/rtems/score/isrlevel.h
+include_rtems_score_HEADERS += include/rtems/score/freechain.h
 include_rtems_score_HEADERS += include/rtems/score/object.h
 include_rtems_score_HEADERS += include/rtems/score/percpu.h
 include_rtems_score_HEADERS += include/rtems/score/priority.h
@@ -257,6 +258,9 @@ libscore_a_SOURCES += src/pheapallocate.c \
     src/pheapgetblocksize.c src/pheapgetfreeinfo.c src/pheapgetinfo.c \
     src/pheapinit.c src/pheapresizeblock.c src/pheapwalk.c src/pheapiterate.c
 
+## FREECHAIN_C_FILES
+libscore_a_SOURCES += src/freechain.c
+
 ## RBTREE_C_FILES
 libscore_a_SOURCES += src/rbtree.c \
     src/rbtreeextract.c src/rbtreefind.c src/rbtreefindheader.c \
diff --git a/cpukit/score/include/rtems/score/freechain.h b/cpukit/score/include/rtems/score/freechain.h
new file mode 100644
index 0000000000..d59de06319
--- /dev/null
+++ b/cpukit/score/include/rtems/score/freechain.h
@@ -0,0 +1,108 @@
+/**
+ * @file
+ *
+ * @ingroup ScoreFreechain
+ *
+ * @brief Freechain Handler API
+ */
+/*
+ * Copyright (c) 2013 Gedare Bloom.
+ *
+ * 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_SCORE_FREECHAIN_H
+#define _RTEMS_SCORE_FREECHAIN_H
+
+#include <stdbool.h>
+
+#include <rtems/score/chain.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+ * @defgroup ScoreFreechain Freechain Handler
+ *
+ * @ingroup Score
+ *
+ * The Freechain Handler is used to manage a chain of nodes, of which size can
+ * automatically increase when there is no free node left. This handler
+ * provides one data structure: Freechain_Control.
+ *
+ * @{
+ */
+
+typedef struct Freechain_Control Freechain_Control;
+
+/**
+ * @brief Extends the freechain.
+ *
+ * @param[in] freechain The freechain control.
+ *
+ * @retval true The freechain contains now at least one node.
+ * @retval false Otherwise.
+ */
+typedef bool ( *Freechain_Extend )( Freechain_Control *freechain );
+
+/**
+ * @typedef Freechain_Control
+ *
+ * This is used to manage freechain's nodes.
+ */
+struct Freechain_Control {
+  Chain_Control     Freechain;
+  Freechain_Extend  extend;
+};
+
+/**
+ * @brief Initializes a freechain.
+ *
+ * This routine initializes the freechain control structure to manage a chain
+ * of nodes.  In case the freechain is empty the extend handler is called to
+ * get more nodes.
+ *
+ * @param[in,out] freechain The freechain control to initialize.
+ * @param[in] extend The extend handler.  It is called by _Freechain_Get() in
+ * case the freechain is empty.
+ */
+void _Freechain_Initialize(
+  Freechain_Control *freechain,
+  Freechain_Extend   extend
+);
+
+/**
+ * @brief Gets a node from the freechain.
+ *
+ * @param[in,out] freechain The freechain control.
+ *
+ * @retval NULL The freechain is empty and the extend operation failed.
+ * @retval otherwise Pointer to a node.  The node ownership passes to the
+ * caller.
+ */
+void *_Freechain_Get(
+  Freechain_Control *freechain
+);
+
+/**
+ * @brief Puts a node back onto the freechain.
+ *
+ * @param[in,out] freechain The freechain control.
+ * @param[in] node The node to put back.
+ */
+void _Freechain_Put(
+  Freechain_Control *freechain,
+  void              *node
+);
+
+/**@}*/
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
+/* end of include file */
diff --git a/cpukit/score/preinstall.am b/cpukit/score/preinstall.am
index 740e58e014..3bfc582830 100644
--- a/cpukit/score/preinstall.am
+++ b/cpukit/score/preinstall.am
@@ -127,6 +127,10 @@ $(PROJECT_INCLUDE)/rtems/score/isrlevel.h: include/rtems/score/isrlevel.h $(PROJ
 	$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/isrlevel.h
 PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/isrlevel.h
 
+$(PROJECT_INCLUDE)/rtems/score/freechain.h: include/rtems/score/freechain.h $(PROJECT_INCLUDE)/rtems/score/$(dirstamp)
+	$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/freechain.h
+PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/freechain.h
+
 $(PROJECT_INCLUDE)/rtems/score/object.h: include/rtems/score/object.h $(PROJECT_INCLUDE)/rtems/score/$(dirstamp)
 	$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/score/object.h
 PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/score/object.h
diff --git a/cpukit/score/src/freechain.c b/cpukit/score/src/freechain.c
new file mode 100644
index 0000000000..101a11e001
--- /dev/null
+++ b/cpukit/score/src/freechain.c
@@ -0,0 +1,47 @@
+/**
+ * @file
+ *
+ * @ingroup ScoreFreechain
+ *
+ * @brief Freechain Handler Implementation
+ */
+
+/*
+ * Copyright (c) 2013 Gedare Bloom.
+ *
+ * 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
+  #include "config.h"
+#endif
+
+#include <rtems/score/freechain.h>
+#include <rtems/score/chainimpl.h>
+
+void _Freechain_Initialize(
+    Freechain_Control *freechain,
+    Freechain_Extend   extend
+)
+{
+  _Chain_Initialize_empty( &freechain->Freechain );
+  freechain->extend = extend;
+}
+
+void *_Freechain_Get(Freechain_Control *freechain)
+{
+  if ( _Chain_Is_empty( &freechain->Freechain ) ) {
+    if ( !( *freechain->extend )( freechain ) ) {
+      return NULL;
+    }
+  }
+
+  return _Chain_Get_first_unprotected( &freechain->Freechain );
+}
+
+void _Freechain_Put( Freechain_Control *freechain, void *node )
+{
+  _Chain_Prepend_unprotected( &freechain->Freechain, node );
+}
diff --git a/testsuites/sptests/Makefile.am b/testsuites/sptests/Makefile.am
index 8e61968f40..e40dbab007 100644
--- a/testsuites/sptests/Makefile.am
+++ b/testsuites/sptests/Makefile.am
@@ -20,6 +20,7 @@ SUBDIRS = \
     spfatal15 spfatal16 spfatal17 spfatal18 spfatal19 spfatal20 \
     spfatal22 spfatal23 spfatal24 spfatal25 \
     spfifo01 spfifo02 spfifo03 spfifo04 spfifo05 \
+    spfreechain01 \
     spintrcritical01 spintrcritical02 spintrcritical03 spintrcritical04 \
     spintrcritical05 spintrcritical06 spintrcritical07 spintrcritical08 \
     spintrcritical09 spintrcritical10 spintrcritical11 spintrcritical12 \
diff --git a/testsuites/sptests/configure.ac b/testsuites/sptests/configure.ac
index db44659d30..d39ddf1e05 100644
--- a/testsuites/sptests/configure.ac
+++ b/testsuites/sptests/configure.ac
@@ -165,6 +165,7 @@ spfifo02/Makefile
 spfifo03/Makefile
 spfifo04/Makefile
 spfifo05/Makefile
+spfreechain01/Makefile
 spintrcritical01/Makefile
 spintrcritical02/Makefile
 spintrcritical03/Makefile
diff --git a/testsuites/sptests/spfreechain01/Makefile.am b/testsuites/sptests/spfreechain01/Makefile.am
new file mode 100644
index 0000000000..9e5eba2ad4
--- /dev/null
+++ b/testsuites/sptests/spfreechain01/Makefile.am
@@ -0,0 +1,20 @@
+
+rtems_tests_PROGRAMS = spfreechain01
+spfreechain01_SOURCES = init.c
+
+dist_rtems_tests_DATA = spfreechain01.scn
+dist_rtems_tests_DATA += spfreechain01.doc
+
+include $(RTEMS_ROOT)/make/custom/@RTEMS_BSP@.cfg
+include $(top_srcdir)/../automake/compile.am
+include $(top_srcdir)/../automake/leaf.am
+
+
+AM_CPPFLAGS += -I$(top_srcdir)/../support/include
+
+LINK_OBJS = $(spfreechain01_OBJECTS)
+LINK_LIBS = $(spfreechain01_LDLIBS)
+
+spfreechain01$(EXEEXT): $(spfreechain01_OBJECTS) $(spfreechain01_DEPENDENCIES)
+	@rm -f spfreechain01$(EXEEXT)
+	$(make-exe)
diff --git a/testsuites/sptests/spfreechain01/init.c b/testsuites/sptests/spfreechain01/init.c
new file mode 100644
index 0000000000..16c7c9ff43
--- /dev/null
+++ b/testsuites/sptests/spfreechain01/init.c
@@ -0,0 +1,196 @@
+/*
+ * Copyright (c) 2013 Zhongwei Yao.
+ *
+ *  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.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <tmacros.h>
+#include <rtems/score/chainimpl.h>
+#include <rtems/score/freechain.h>
+#include <rtems/score/wkspace.h>
+#include <rtems/malloc.h>
+
+/* forward declarations to avoid warnings */
+rtems_task Init(rtems_task_argument argument);
+bool my_freechain_extend_with_nothing( Freechain_Control *freechain );
+bool my_freechain_extend_heap( Freechain_Control *freechain );
+bool my_freechain_extend_workspace( Freechain_Control *freechain );
+void my_freechain_init_heap( Freechain_Control *freechain );
+void my_freechain_init_workspace( Freechain_Control *freechain );
+
+typedef struct {
+  Freechain_Control super_fc;
+  size_t bump_count;
+} MyFreechain;
+
+typedef struct {
+  Chain_Node ch_node;
+  int x;
+} test_node;
+
+bool my_freechain_extend_with_nothing( Freechain_Control *freechain )
+{
+    return NULL;
+}
+
+/* user defined extend handle, it allocates memory on heap. */
+bool my_freechain_extend_heap( Freechain_Control *freechain )
+{
+  MyFreechain *self = (MyFreechain *)freechain;
+  size_t node_size = sizeof(test_node);
+  size_t size = self->bump_count * node_size;
+  int i;
+  test_node *nodes = malloc(size);
+
+  if (!nodes) {
+    printf( "INIT - Unable to allocate free chain of size: %d\n", size );
+    return NULL;
+  }
+
+  puts( "INIT - Allocate node from heap in user defined freechain extend"
+        " - OK" );
+  for ( i = 0; i < self->bump_count; i++ ) {
+      _Freechain_Put(freechain,
+                          nodes + i * node_size);
+  }
+  return true;
+}
+
+/* user defined extend handle, it allocates memory on workspace. */
+bool my_freechain_extend_workspace( Freechain_Control *freechain )
+{
+  MyFreechain *self = (MyFreechain *)freechain;
+  size_t node_size = sizeof(test_node);
+  size_t size = self->bump_count * node_size;
+  int i;
+  test_node *nodes = _Workspace_Allocate(size);
+
+  if (!nodes) {
+    printf( "INIT - Unable to allocate free chain of size: %d\n", size );
+    return NULL;
+  }
+
+  puts( "INIT - Allocate node from workspace in user defined freechain extend"
+        " - OK" );
+
+  for ( i = 0; i < self->bump_count; i++ ) {
+      _Freechain_Put(freechain,
+                          nodes + i * node_size);
+  }
+  return true;
+}
+
+void my_freechain_init_heap( Freechain_Control *freechain )
+{
+  MyFreechain *self = (MyFreechain *)freechain;
+  self->bump_count = 5;
+  size_t size = self->bump_count * sizeof(test_node);
+  test_node *nodes = malloc(size);
+
+  _Chain_Initialize(
+    &freechain->Freechain,
+    nodes,
+    self->bump_count,
+    sizeof(test_node)
+    );
+}
+
+void my_freechain_init_workspace( Freechain_Control *freechain )
+{
+  MyFreechain *self = (MyFreechain *)freechain;
+  self->bump_count = 7;
+  size_t size = self->bump_count * sizeof(test_node);
+  test_node *nodes = _Workspace_Allocate(size);
+
+  _Chain_Initialize(
+    &freechain->Freechain,
+    nodes,
+    self->bump_count,
+    sizeof(test_node)
+    );
+}
+
+rtems_task Init(
+  rtems_task_argument ignored
+                )
+{
+    puts( "*** START OF RTEMS FREECHAIN API TEST ***" );
+
+    test_node *test_node_p;
+    MyFreechain myfc;
+    Freechain_Control *fc_p = (Freechain_Control *)&myfc;
+    int i;
+
+    /* check whether freechain put and get works correctly*/
+    _Freechain_Initialize(fc_p,
+                          &my_freechain_extend_with_nothing);
+    my_freechain_init_heap(fc_p);
+
+    puts( "INIT - Get node from freechain - OK" );
+    test_node_p = (test_node *)_Freechain_Get(fc_p);
+    test_node_p->x = 1;
+
+    puts( "INIT - Put node back to freechain - OK" );
+    _Freechain_Put(fc_p, (void *)test_node_p);
+
+    puts( "INIT - Verify freechain node put and get - OK" );
+    test_node_p = (test_node *)_Freechain_Get(fc_p);
+    if(test_node_p->x != 1) {
+      puts( "INIT - ERROR ON FREECHAIN GET AND PUT" );
+      rtems_test_exit(0);
+    }
+
+    /* check whether freechain extend handle on heap works correctly */
+    _Freechain_Initialize(fc_p,
+                          &my_freechain_extend_heap);
+    my_freechain_init_heap(fc_p);
+
+    puts( "INIT - Get more than intialized nodes from freechain on heap - OK" );
+
+    for ( i = 0; i < myfc.bump_count * 2; i++ ) {
+        test_node_p = (test_node *)_Freechain_Get(fc_p);
+        if (!test_node_p) {
+            puts( "INIT - Get node from freechain failed - FAILED" );
+            rtems_test_exit(0);
+        }
+    }
+
+    /* check whether freechain extend handle in workspace works correctly */
+    _Freechain_Initialize(fc_p,
+                          &my_freechain_extend_workspace);
+    my_freechain_init_workspace(fc_p);
+
+    puts( "INIT - Get more than intialized nodes from freechain in workspace"
+          " - OK" );
+
+    for ( i = 0; i < myfc.bump_count * 2; i++ ) {
+        test_node_p = (test_node *)_Freechain_Get(fc_p);
+        if (!test_node_p) {
+            puts( "INIT - Get node from freechain failed - FAILED" );
+            rtems_test_exit(0);
+        }
+    }
+
+    puts( "*** END OF RTEMS FREECHAIN API TEST ***" );
+    rtems_test_exit(0);
+}
+
+/* configuration information */
+
+#define CONFIGURE_APPLICATION_NEEDS_CONSOLE_DRIVER
+#define CONFIGURE_APPLICATION_DOES_NOT_NEED_CLOCK_DRIVER
+
+#define CONFIGURE_MEMORY_OVERHEAD sizeof(test_node)
+#define CONFIGURE_RTEMS_INIT_TASKS_TABLE
+#define CONFIGURE_MAXIMUM_TASKS 1
+
+#define CONFIGURE_INIT
+#include <rtems/confdefs.h>
+
+/* global variables */
diff --git a/testsuites/sptests/spfreechain01/spfreechain01.doc b/testsuites/sptests/spfreechain01/spfreechain01.doc
new file mode 100644
index 0000000000..62bfb57466
--- /dev/null
+++ b/testsuites/sptests/spfreechain01/spfreechain01.doc
@@ -0,0 +1,29 @@
+#  COPYRIGHT (c) 2013.
+#  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.
+#
+
+This file describes the directives and concepts tested by this test set.
+
+test set name:  spfreechain01
+
+directives:
+
+  _Freechain_Initialize
+  _Freechain_Put_node
+  _Freechain_Get_node
+  my_freechain_extend_with_nothing
+  my_freechain_extend_heap
+  my_freechain_extend_workspace
+
+concepts:
+
++ Ensure that the freechain operations listed above behave as defined.
++ Define 3 freechain extension handles, they are:
+  my_freechain_extend_with_nothing: a dummy extension handle, do nothing
+  my_freechain_extend_heap: an extension handle allocates memory from heap
+  my_freechain_extend_workspace: an extension handle allocates memory from workspace
++ Ensure that the freechain is extended correctly by user provided extension handles
diff --git a/testsuites/sptests/spfreechain01/spfreechain01.scn b/testsuites/sptests/spfreechain01/spfreechain01.scn
new file mode 100644
index 0000000000..e65e90a6e3
--- /dev/null
+++ b/testsuites/sptests/spfreechain01/spfreechain01.scn
@@ -0,0 +1,9 @@
+*** START OF RTEMS FREECHAIN API TEST ***
+INIT - Get node from freechain - OK
+INIT - Put node to freechain - OK
+INIT - Verify freechain node put and get - OK
+INIT - Get more than intialized nodes from freechain on heap - OK
+INIT - Allocate node from heap in user defined freechain extend - OK
+INIT - Get more than intialized nodes from freechain in workspace - OK
+INIT - Allocate node from workspace in user defined freechain extend - OK
+*** END OF RTEMS FREECHAIN API TEST ***
\ No newline at end of file