[rtems commit] rbheap: New files
Sebastian Huber
sebh at rtems.org
Wed Apr 11 09:23:14 UTC 2012
Module: rtems
Branch: master
Commit: e75263083e83cac921475d0a89d8b3b398f9b902
Changeset: http://git.rtems.org/rtems/commit/?id=e75263083e83cac921475d0a89d8b3b398f9b902
Author: Sebastian Huber <sebastian.huber at embedded-brains.de>
Date: Tue Apr 10 11:19:39 2012 +0200
rbheap: New files
In the Red-Black Tree Heap the administration data structures are not
contained in the managed memory area. This can be used for example in a
task stack allocator which protects the task stacks from access by other
tasks.
---
cpukit/sapi/Makefile.am | 3 +-
cpukit/sapi/include/rtems/rbheap.h | 130 +++++++
cpukit/sapi/preinstall.am | 4 +
cpukit/sapi/src/rbheap.c | 277 ++++++++++++++
testsuites/libtests/Makefile.am | 1 +
testsuites/libtests/configure.ac | 1 +
testsuites/libtests/rbheap01/Makefile.am | 19 +
testsuites/libtests/rbheap01/init.c | 571 +++++++++++++++++++++++++++++
testsuites/libtests/rbheap01/rbheap01.doc | 11 +
testsuites/libtests/rbheap01/rbheap01.scn | 2 +
10 files changed, 1018 insertions(+), 1 deletions(-)
diff --git a/cpukit/sapi/Makefile.am b/cpukit/sapi/Makefile.am
index 9b7ad53..4536280 100644
--- a/cpukit/sapi/Makefile.am
+++ b/cpukit/sapi/Makefile.am
@@ -16,6 +16,7 @@ include_rtems_HEADERS += include/rtems/init.h
include_rtems_HEADERS += include/rtems/io.h
include_rtems_HEADERS += include/rtems/mptables.h
include_rtems_HEADERS += include/rtems/cbs.h
+include_rtems_HEADERS += include/rtems/rbheap.h
include_rtems_HEADERS += include/rtems/rbtree.h
include_rtems_HEADERS += include/rtems/sptables.h
@@ -38,7 +39,7 @@ libsapi_a_SOURCES = src/debug.c src/extension.c src/extensioncreate.c \
src/iounregisterdriver.c src/iowrite.c src/posixapi.c \
src/rtemsapi.c src/extensiondata.c src/getversionstring.c \
src/chainappendnotify.c src/chaingetnotify.c src/chaingetwait.c \
- src/chainprependnotify.c
+ src/chainprependnotify.c src/rbheap.c
libsapi_a_CPPFLAGS = $(AM_CPPFLAGS)
include $(srcdir)/preinstall.am
diff --git a/cpukit/sapi/include/rtems/rbheap.h b/cpukit/sapi/include/rtems/rbheap.h
new file mode 100644
index 0000000..be1eec6
--- /dev/null
+++ b/cpukit/sapi/include/rtems/rbheap.h
@@ -0,0 +1,130 @@
+/**
+ * @file
+ *
+ * @ingroup RBHeap
+ *
+ * @brief Red-Black Tree Heap API.
+ */
+
+/*
+ * Copyright (c) 2012 embedded brains GmbH. All rights reserved.
+ *
+ * embedded brains GmbH
+ * Obere Lagerstr. 30
+ * 82178 Puchheim
+ * Germany
+ * <rtems at embedded-brains.de>
+ *
+ * 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_RBHEAP_H
+#define _RTEMS_RBHEAP_H
+
+#include <rtems.h>
+#include <rtems/chain.h>
+#include <rtems/rbtree.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+ * @defgroup RBHeap Red-Black Tree Heap
+ *
+ * @brief Red-Black Tree Heap API.
+ *
+ * In the Red-Black Tree Heap the administration data structures are not
+ * contained in the managed memory area. This can be used for example in a
+ * task stack allocator which protects the task stacks from access by other
+ * tasks.
+ *
+ * @{
+ */
+
+typedef struct {
+ rtems_chain_node chain_node;
+ rtems_rbtree_node tree_node;
+ uintptr_t begin;
+ uintptr_t size;
+} rtems_rbheap_page;
+
+typedef struct rtems_rbheap_control rtems_rbheap_control;
+
+typedef void (*rtems_rbheap_extend_page_pool)(rtems_rbheap_control *control);
+
+struct rtems_rbheap_control {
+ rtems_chain_control free_chain;
+ rtems_chain_control pool_chain;
+ rtems_rbtree_control page_tree;
+ uintptr_t page_alignment;
+ rtems_rbheap_extend_page_pool extend_page_pool;
+ void *handler_arg;
+};
+
+rtems_status_code rtems_rbheap_initialize(
+ rtems_rbheap_control *control,
+ void *area_begin,
+ uintptr_t area_size,
+ uintptr_t page_alignment,
+ rtems_rbheap_extend_page_pool extend_page_pool,
+ void *handler_arg
+);
+
+void *rtems_rbheap_allocate(rtems_rbheap_control *control, size_t size);
+
+rtems_status_code rtems_rbheap_free(rtems_rbheap_control *control, void *ptr);
+
+static inline rtems_chain_control *rtems_rbheap_get_pool_chain(
+ rtems_rbheap_control *control
+)
+{
+ return &control->pool_chain;
+}
+
+static inline void rtems_rbheap_set_extend_page_pool(
+ rtems_rbheap_control *control,
+ rtems_rbheap_extend_page_pool extend_page_pool
+)
+{
+ control->extend_page_pool = extend_page_pool;
+}
+
+static inline void *rtems_rbheap_get_handler_arg(
+ const rtems_rbheap_control *control
+)
+{
+ return control->handler_arg;
+}
+
+static inline void rtems_rbheap_set_handler_arg(
+ rtems_rbheap_control *control,
+ void *handler_arg
+)
+{
+ control->handler_arg = handler_arg;
+}
+
+void rtems_rbheap_extend_page_pool_never(rtems_rbheap_control *control);
+
+void rtems_rbheap_extend_page_pool_with_malloc(rtems_rbheap_control *control);
+
+/** @} */
+
+/* Private API */
+
+#define rtems_rbheap_page_of_node(node) \
+ rtems_rbtree_container_of(node, rtems_rbheap_page, tree_node)
+
+static inline bool rtems_rbheap_is_page_free(const rtems_rbheap_page *page)
+{
+ return !rtems_chain_is_node_off_chain(&page->chain_node);
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTEMS_RBHEAP_H */
diff --git a/cpukit/sapi/preinstall.am b/cpukit/sapi/preinstall.am
index 5ce9966..e7c8e2a 100644
--- a/cpukit/sapi/preinstall.am
+++ b/cpukit/sapi/preinstall.am
@@ -64,6 +64,10 @@ $(PROJECT_INCLUDE)/rtems/cbs.h: include/rtems/cbs.h $(PROJECT_INCLUDE)/rtems/$(d
$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/cbs.h
PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/cbs.h
+$(PROJECT_INCLUDE)/rtems/rbheap.h: include/rtems/rbheap.h $(PROJECT_INCLUDE)/rtems/$(dirstamp)
+ $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/rbheap.h
+PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/rbheap.h
+
$(PROJECT_INCLUDE)/rtems/rbtree.h: include/rtems/rbtree.h $(PROJECT_INCLUDE)/rtems/$(dirstamp)
$(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/rbtree.h
PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/rbtree.h
diff --git a/cpukit/sapi/src/rbheap.c b/cpukit/sapi/src/rbheap.c
new file mode 100644
index 0000000..7986325
--- /dev/null
+++ b/cpukit/sapi/src/rbheap.c
@@ -0,0 +1,277 @@
+/**
+ * @file
+ *
+ * @ingroup RBHeap
+ *
+ * @brief Red-Black Tree Heap implementation.
+ */
+
+/*
+ * Copyright (c) 2012 embedded brains GmbH. All rights reserved.
+ *
+ * embedded brains GmbH
+ * Obere Lagerstr. 30
+ * 82178 Puchheim
+ * Germany
+ * <rtems at embedded-brains.de>
+ *
+ * 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/rbheap.h>
+
+#include <stdlib.h>
+
+static uintptr_t align_up(uintptr_t page_alignment, uintptr_t value)
+{
+ uintptr_t excess = value % page_alignment;
+
+ if (excess > 0) {
+ value += page_alignment - excess;
+ }
+
+ return value;
+}
+
+static uintptr_t align_down(uintptr_t page_alignment, uintptr_t value)
+{
+ uintptr_t excess = value % page_alignment;
+
+ return value - excess;
+}
+
+static int page_compare(const rtems_rbtree_node *a, const rtems_rbtree_node *b)
+{
+ const rtems_rbheap_page *left = rtems_rbheap_page_of_node(a);
+ const rtems_rbheap_page *right = rtems_rbheap_page_of_node(b);
+
+ return (int) (left->begin - right->begin);
+}
+
+static rtems_rbheap_page *get_page(rtems_rbheap_control *control)
+{
+ rtems_chain_control *pool_chain = &control->pool_chain;
+ rtems_chain_node *page = rtems_chain_get(pool_chain);
+
+ if (page == NULL) {
+ (*control->extend_page_pool)(control);
+ page = rtems_chain_get(pool_chain);
+ }
+
+ return (rtems_rbheap_page *) page;
+}
+
+static void add_to_chain(
+ rtems_chain_control *chain,
+ rtems_rbheap_page *page
+)
+{
+ rtems_chain_prepend_unprotected(chain, &page->chain_node);
+}
+
+static void insert_into_tree(
+ rtems_rbtree_control *tree,
+ rtems_rbheap_page *page
+)
+{
+ _RBTree_Insert_unprotected(tree, &page->tree_node);
+}
+
+rtems_status_code rtems_rbheap_initialize(
+ rtems_rbheap_control *control,
+ void *area_begin,
+ uintptr_t area_size,
+ uintptr_t page_alignment,
+ rtems_rbheap_extend_page_pool extend_page_pool,
+ void *handler_arg
+)
+{
+ rtems_status_code sc = RTEMS_SUCCESSFUL;
+
+ if (page_alignment > 0) {
+ uintptr_t begin = (uintptr_t) area_begin;
+ uintptr_t end = begin + area_size;
+ uintptr_t aligned_begin = align_up(page_alignment, begin);
+ uintptr_t aligned_end = align_down(page_alignment, end);
+
+ if (begin < end && begin <= aligned_begin && aligned_begin < aligned_end) {
+ rtems_chain_control *free_chain = &control->free_chain;
+ rtems_rbtree_control *page_tree = &control->page_tree;
+ rtems_rbheap_page *first = NULL;
+
+ rtems_chain_initialize_empty(free_chain);
+ rtems_chain_initialize_empty(&control->pool_chain);
+ rtems_rbtree_initialize_empty(page_tree, page_compare, true);
+ control->page_alignment = page_alignment;
+ control->handler_arg = handler_arg;
+ control->extend_page_pool = extend_page_pool;
+
+ first = get_page(control);
+ if (first != NULL) {
+ first->begin = aligned_begin;
+ first->size = aligned_end - aligned_begin;
+ add_to_chain(free_chain, first);
+ insert_into_tree(page_tree, first);
+ } else {
+ sc = RTEMS_NO_MEMORY;
+ }
+ } else {
+ sc = RTEMS_INVALID_ADDRESS;
+ }
+ } else {
+ sc = RTEMS_INVALID_NUMBER;
+ }
+
+ return sc;
+}
+
+static rtems_rbheap_page *search_free_page(
+ rtems_chain_control *free_chain,
+ size_t size
+)
+{
+ rtems_chain_node *current = rtems_chain_first(free_chain);
+ const rtems_chain_node *tail = rtems_chain_tail(free_chain);
+ rtems_rbheap_page *big_enough = NULL;
+
+ while (current != tail && big_enough == NULL) {
+ rtems_rbheap_page *free_page = (rtems_rbheap_page *) current;
+
+ if (free_page->size >= size) {
+ big_enough = free_page;
+ }
+
+ current = rtems_chain_next(current);
+ }
+
+ return big_enough;
+}
+
+void *rtems_rbheap_allocate(rtems_rbheap_control *control, size_t size)
+{
+ void *ptr = NULL;
+ rtems_chain_control *free_chain = &control->free_chain;
+ rtems_rbtree_control *page_tree = &control->page_tree;
+ uintptr_t page_alignment = control->page_alignment;
+ uintptr_t aligned_size = align_up(page_alignment, size);
+
+ if (size > 0 && size <= aligned_size) {
+ rtems_rbheap_page *free_page = search_free_page(free_chain, aligned_size);
+
+ if (free_page != NULL) {
+ uintptr_t free_size = free_page->size;
+
+ if (free_size > aligned_size) {
+ rtems_rbheap_page *new_page = get_page(control);
+
+ if (new_page != NULL) {
+ uintptr_t new_free_size = free_size - aligned_size;
+
+ free_page->size = new_free_size;
+ new_page->begin = free_page->begin + new_free_size;
+ new_page->size = aligned_size;
+ rtems_chain_set_off_chain(&new_page->chain_node);
+ insert_into_tree(page_tree, new_page);
+ ptr = (void *) new_page->begin;
+ }
+ } else {
+ rtems_chain_extract_unprotected(&free_page->chain_node);
+ rtems_chain_set_off_chain(&free_page->chain_node);
+ ptr = (void *) free_page->begin;
+ }
+ }
+ }
+
+ return ptr;
+}
+
+#define NULL_PAGE rtems_rbheap_page_of_node(NULL)
+
+static rtems_rbheap_page *find(rtems_rbtree_control *page_tree, uintptr_t key)
+{
+ rtems_rbheap_page page = { .begin = key };
+
+ return rtems_rbheap_page_of_node(
+ _RBTree_Find_unprotected(page_tree, &page.tree_node)
+ );
+}
+
+static rtems_rbheap_page *get_next(
+ const rtems_rbtree_control *page_tree,
+ const rtems_rbheap_page *page,
+ RBTree_Direction dir
+)
+{
+ return rtems_rbheap_page_of_node(
+ _RBTree_Next_unprotected(page_tree, &page->tree_node, dir)
+ );
+}
+
+static void check_and_merge(
+ rtems_chain_control *free_chain,
+ rtems_rbtree_control *page_tree,
+ rtems_rbheap_page *a,
+ rtems_rbheap_page *b
+)
+{
+ if (b != NULL_PAGE && rtems_rbheap_is_page_free(b)) {
+ if (b->begin < a->begin) {
+ rtems_rbheap_page *t = a;
+
+ a = b;
+ b = t;
+ }
+
+ a->size += b->size;
+ rtems_chain_extract_unprotected(&b->chain_node);
+ add_to_chain(free_chain, b);
+ _RBTree_Extract_unprotected(page_tree, &b->tree_node);
+ }
+}
+
+rtems_status_code rtems_rbheap_free(rtems_rbheap_control *control, void *ptr)
+{
+ rtems_status_code sc = RTEMS_SUCCESSFUL;
+ rtems_chain_control *free_chain = &control->free_chain;
+ rtems_rbtree_control *page_tree = &control->page_tree;
+ rtems_rbheap_page *page = find(page_tree, (uintptr_t) ptr);
+
+ if (page != NULL_PAGE) {
+ if (!rtems_rbheap_is_page_free(page)) {
+ rtems_rbheap_page *pred = get_next(page_tree, page, RBT_LEFT);
+ rtems_rbheap_page *succ = get_next(page_tree, page, RBT_RIGHT);
+
+ check_and_merge(free_chain, page_tree, page, succ);
+ add_to_chain(free_chain, page);
+ check_and_merge(free_chain, page_tree, page, pred);
+ } else {
+ sc = RTEMS_INCORRECT_STATE;
+ }
+ } else {
+ sc = RTEMS_INVALID_ID;
+ }
+
+ return sc;
+}
+
+void rtems_rbheap_extend_page_pool_never(rtems_rbheap_control *control)
+{
+ /* Do nothing */
+}
+
+void rtems_rbheap_extend_page_pool_with_malloc(rtems_rbheap_control *control)
+{
+ rtems_rbheap_page *page = malloc(sizeof(*page));
+
+ if (page != NULL) {
+ rtems_chain_control *pool_chain = rtems_rbheap_get_pool_chain(control);
+
+ add_to_chain(pool_chain, page);
+ }
+}
diff --git a/testsuites/libtests/Makefile.am b/testsuites/libtests/Makefile.am
index 9521825..e964608 100644
--- a/testsuites/libtests/Makefile.am
+++ b/testsuites/libtests/Makefile.am
@@ -5,6 +5,7 @@
ACLOCAL_AMFLAGS = -I ../aclocal
SUBDIRS = POSIX
+SUBDIRS += rbheap01
SUBDIRS += flashdisk01
SUBDIRS += bspcmdline01 cpuuse devfs01 devfs02 devfs03 devfs04 \
diff --git a/testsuites/libtests/configure.ac b/testsuites/libtests/configure.ac
index d1ce374..f04ab0b 100644
--- a/testsuites/libtests/configure.ac
+++ b/testsuites/libtests/configure.ac
@@ -43,6 +43,7 @@ AM_CONDITIONAL(NETTESTS,test "$rtems_cv_RTEMS_NETWORKING" = "yes")
# Explicitly list all Makefiles here
AC_CONFIG_FILES([Makefile
+rbheap01/Makefile
syscall01/Makefile
flashdisk01/Makefile
block01/Makefile
diff --git a/testsuites/libtests/rbheap01/Makefile.am b/testsuites/libtests/rbheap01/Makefile.am
new file mode 100644
index 0000000..9bad9c0
--- /dev/null
+++ b/testsuites/libtests/rbheap01/Makefile.am
@@ -0,0 +1,19 @@
+rtems_tests_PROGRAMS = rbheap01
+rbheap01_SOURCES = init.c
+
+dist_rtems_tests_DATA = rbheap01.scn rbheap01.doc
+
+include $(RTEMS_ROOT)/make/custom/@RTEMS_BSP at .cfg
+include $(top_srcdir)/../automake/compile.am
+include $(top_srcdir)/../automake/leaf.am
+
+AM_CPPFLAGS += -I$(top_srcdir)/../support/include
+
+LINK_OBJS = $(rbheap01_OBJECTS)
+LINK_LIBS = $(rbheap01_LDLIBS)
+
+rbheap01$(EXEEXT): $(rbheap01_OBJECTS) $(rbheap01_DEPENDENCIES)
+ @rm -f rbheap01$(EXEEXT)
+ $(make-exe)
+
+include $(top_srcdir)/../automake/local.am
diff --git a/testsuites/libtests/rbheap01/init.c b/testsuites/libtests/rbheap01/init.c
new file mode 100644
index 0000000..a66cc24
--- /dev/null
+++ b/testsuites/libtests/rbheap01/init.c
@@ -0,0 +1,571 @@
+/*
+ * Copyright (c) 2012 embedded brains GmbH. All rights reserved.
+ *
+ * embedded brains GmbH
+ * Obere Lagerstr. 30
+ * 82178 Puchheim
+ * Germany
+ * <rtems at embedded-brains.de>
+ *
+ * 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.h>
+#include <rtems/rbheap.h>
+
+#define PAGE_SIZE 1024
+
+#define PAGE_COUNT 8
+
+static char area [PAGE_SIZE * PAGE_COUNT + PAGE_SIZE - 1];
+
+static rtems_rbheap_page pages [PAGE_COUNT];
+
+static void extend_page_pool(rtems_rbheap_control *control)
+{
+ rtems_chain_control *pool_chain = rtems_rbheap_get_pool_chain(control);
+
+ rtems_rbheap_set_extend_page_pool(
+ control,
+ rtems_rbheap_extend_page_pool_never
+ );
+
+ rtems_chain_initialize(
+ pool_chain,
+ pages,
+ PAGE_COUNT,
+ sizeof(pages [0])
+ );
+}
+
+static uintptr_t idx(const rtems_rbheap_page *page)
+{
+ uintptr_t base = (uintptr_t) area;
+ uintptr_t excess = base % PAGE_SIZE;
+
+ if (excess > 0) {
+ base += PAGE_SIZE - excess;
+ }
+
+ return (page->begin - base) / PAGE_SIZE;
+}
+
+typedef struct {
+ const uintptr_t *index_current;
+ const uintptr_t *index_end;
+ const bool *free_current;
+ const bool *free_end;
+} page_visitor_context;
+
+static bool page_visitor(
+ const RBTree_Node *node,
+ RBTree_Direction dir,
+ void *visitor_arg
+)
+{
+ rtems_rbheap_page *page = rtems_rbheap_page_of_node(node);
+ page_visitor_context *context = visitor_arg;
+
+ rtems_test_assert(context->index_current != context->index_end);
+ rtems_test_assert(context->free_current != context->free_end);
+
+ rtems_test_assert(idx(page) == *context->index_current);
+ rtems_test_assert(rtems_rbheap_is_page_free(page) == *context->free_current);
+
+ ++context->index_current;
+ ++context->free_current;
+
+ return false;
+}
+
+static void test_init_page_alignment(void)
+{
+ rtems_status_code sc = RTEMS_SUCCESSFUL;
+ rtems_rbheap_control control;
+
+ sc = rtems_rbheap_initialize(
+ &control,
+ area,
+ sizeof(area),
+ 0,
+ extend_page_pool,
+ NULL
+ );
+ rtems_test_assert(sc == RTEMS_INVALID_NUMBER);
+}
+
+static void test_init_begin_greater_than_end(void)
+{
+ rtems_status_code sc = RTEMS_SUCCESSFUL;
+ rtems_rbheap_control control;
+
+ sc = rtems_rbheap_initialize(
+ &control,
+ (void *) PAGE_SIZE,
+ (uintptr_t) -PAGE_SIZE,
+ PAGE_SIZE,
+ extend_page_pool,
+ NULL
+ );
+ rtems_test_assert(sc == RTEMS_INVALID_ADDRESS);
+}
+
+static void test_init_begin_greater_than_aligned_begin(void)
+{
+ rtems_status_code sc = RTEMS_SUCCESSFUL;
+ rtems_rbheap_control control;
+
+ sc = rtems_rbheap_initialize(
+ &control,
+ (void *) -(PAGE_SIZE / 2),
+ PAGE_SIZE,
+ PAGE_SIZE,
+ extend_page_pool,
+ NULL
+ );
+ rtems_test_assert(sc == RTEMS_INVALID_ADDRESS);
+}
+
+static void test_init_aligned_begin_greater_than_aligned_end(void)
+{
+ rtems_status_code sc = RTEMS_SUCCESSFUL;
+ rtems_rbheap_control control;
+
+ sc = rtems_rbheap_initialize(
+ &control,
+ (void *) PAGE_SIZE,
+ PAGE_SIZE / 2,
+ PAGE_SIZE,
+ extend_page_pool,
+ NULL
+ );
+ rtems_test_assert(sc == RTEMS_INVALID_ADDRESS);
+}
+
+static void test_init_empty_page_pool(void)
+{
+ rtems_status_code sc = RTEMS_SUCCESSFUL;
+ rtems_rbheap_control control;
+
+ sc = rtems_rbheap_initialize(
+ &control,
+ (void *) PAGE_SIZE,
+ PAGE_SIZE,
+ PAGE_SIZE,
+ rtems_rbheap_extend_page_pool_never,
+ NULL
+ );
+ rtems_test_assert(sc == RTEMS_NO_MEMORY);
+}
+
+static void test_page_tree(
+ const rtems_rbheap_control *control,
+ const uintptr_t *index_begin,
+ const uintptr_t *index_end,
+ const bool *free_begin,
+ const bool *free_end
+)
+{
+ page_visitor_context context = {
+ .index_current = index_begin,
+ .index_end = index_end,
+ .free_current = free_begin,
+ .free_end = free_end
+ };
+
+ _RBTree_Iterate_unprotected(
+ &control->page_tree,
+ RBT_RIGHT,
+ page_visitor,
+ &context
+ );
+}
+
+#define TEST_PAGE_TREE(control, indices, frees) \
+ test_page_tree( \
+ control, \
+ indices, \
+ &indices [sizeof(indices) / sizeof(indices [0])], \
+ frees, \
+ &frees [sizeof(frees) / sizeof(frees [0])] \
+ )
+
+static void test_init_successful(rtems_rbheap_control *control)
+{
+ static const uintptr_t indices [] = {
+ 0
+ };
+ static const bool frees [] = {
+ true
+ };
+
+ rtems_status_code sc = RTEMS_SUCCESSFUL;
+
+ sc = rtems_rbheap_initialize(
+ control,
+ area,
+ sizeof(area),
+ PAGE_SIZE,
+ extend_page_pool,
+ NULL
+ );
+ rtems_test_assert(sc == RTEMS_SUCCESSFUL);
+
+ TEST_PAGE_TREE(control, indices, frees);
+}
+
+static void test_alloc_and_free_one(void)
+{
+ static const uintptr_t indices_0 [] = {
+ 0,
+ PAGE_COUNT - 1
+ };
+ static const bool frees_0 [] = {
+ true,
+ false
+ };
+ static const uintptr_t indices_1 [] = {
+ 0
+ };
+ static const bool frees_1 [] = {
+ true,
+ };
+
+ rtems_status_code sc = RTEMS_SUCCESSFUL;
+ rtems_rbheap_control control;
+ void *ptr = NULL;
+
+ test_init_successful(&control);
+
+ ptr = rtems_rbheap_allocate(&control, PAGE_SIZE);
+ rtems_test_assert(ptr != NULL);
+
+ TEST_PAGE_TREE(&control, indices_0, frees_0);
+
+ sc = rtems_rbheap_free(&control, ptr);
+ rtems_test_assert(sc == RTEMS_SUCCESSFUL);
+
+ TEST_PAGE_TREE(&control, indices_1, frees_1);
+}
+
+static void test_alloc_zero(void)
+{
+ static const uintptr_t indices [] = {
+ 0
+ };
+ static const bool frees [] = {
+ true
+ };
+
+ rtems_rbheap_control control;
+ void *ptr = NULL;
+
+ test_init_successful(&control);
+
+ ptr = rtems_rbheap_allocate(&control, 0);
+ rtems_test_assert(ptr == NULL);
+
+ TEST_PAGE_TREE(&control, indices, frees);
+}
+
+static void test_alloc_huge_page(void)
+{
+ static const uintptr_t indices [] = {
+ 0
+ };
+ static const bool frees [] = {
+ true
+ };
+
+ rtems_rbheap_control control;
+ void *ptr = NULL;
+
+ test_init_successful(&control);
+
+ ptr = rtems_rbheap_allocate(&control, (PAGE_COUNT + 1) * PAGE_SIZE);
+ rtems_test_assert(ptr == NULL);
+
+ TEST_PAGE_TREE(&control, indices, frees);
+}
+
+static void test_alloc_one_page(void)
+{
+ static const uintptr_t indices_0 [] = {
+ 0
+ };
+ static const bool frees_0 [] = {
+ false
+ };
+ static const uintptr_t indices_1 [] = {
+ 0
+ };
+ static const bool frees_1 [] = {
+ true,
+ };
+
+ rtems_status_code sc = RTEMS_SUCCESSFUL;
+ rtems_rbheap_control control;
+ void *ptr = NULL;
+
+ test_init_successful(&control);
+
+ ptr = rtems_rbheap_allocate(&control, PAGE_COUNT * PAGE_SIZE);
+ rtems_test_assert(ptr != NULL);
+
+ TEST_PAGE_TREE(&control, indices_0, frees_0);
+
+ sc = rtems_rbheap_free(&control, ptr);
+ rtems_test_assert(sc == RTEMS_SUCCESSFUL);
+
+ TEST_PAGE_TREE(&control, indices_1, frees_1);
+}
+
+static void test_alloc_many_pages(void)
+{
+ static const uintptr_t indices_0 [] = {
+ 0,
+ 1,
+ 2,
+ 3,
+ 4,
+ 5,
+ 6,
+ 7
+ };
+ static const bool frees_0 [] = {
+ false,
+ false,
+ false,
+ false,
+ false,
+ false,
+ false,
+ false
+ };
+ static const uintptr_t indices_1 [] = {
+ 0
+ };
+ static const bool frees_1 [] = {
+ true,
+ };
+
+ rtems_status_code sc = RTEMS_SUCCESSFUL;
+ rtems_rbheap_control control;
+ void *ptr [PAGE_COUNT];
+ void *null = NULL;
+ int i = 0;
+
+ test_init_successful(&control);
+
+ for (i = 0; i < PAGE_COUNT; ++i) {
+ ptr [i] = rtems_rbheap_allocate(&control, PAGE_SIZE);
+ rtems_test_assert(ptr [i] != NULL);
+ }
+
+ TEST_PAGE_TREE(&control, indices_0, frees_0);
+
+ null = rtems_rbheap_allocate(&control, PAGE_SIZE);
+ rtems_test_assert(null == NULL);
+
+ TEST_PAGE_TREE(&control, indices_0, frees_0);
+
+ for (i = 0; i < PAGE_COUNT; ++i) {
+ sc = rtems_rbheap_free(&control, ptr [i]);
+ rtems_test_assert(sc == RTEMS_SUCCESSFUL);
+ }
+
+ TEST_PAGE_TREE(&control, indices_1, frees_1);
+}
+
+static void test_free_invalid(void)
+{
+ rtems_status_code sc = RTEMS_SUCCESSFUL;
+ rtems_rbheap_control control;
+
+ test_init_successful(&control);
+
+ sc = rtems_rbheap_free(&control, NULL);
+ rtems_test_assert(sc == RTEMS_INVALID_ID);
+}
+
+static void test_free_double(void)
+{
+ rtems_status_code sc = RTEMS_SUCCESSFUL;
+ rtems_rbheap_control control;
+ void *ptr = NULL;
+
+ test_init_successful(&control);
+
+ ptr = rtems_rbheap_allocate(&control, PAGE_COUNT * PAGE_SIZE);
+ rtems_test_assert(ptr != NULL);
+
+ sc = rtems_rbheap_free(&control, ptr);
+ rtems_test_assert(sc == RTEMS_SUCCESSFUL);
+
+ sc = rtems_rbheap_free(&control, ptr);
+ rtems_test_assert(sc == RTEMS_INCORRECT_STATE);
+}
+
+enum {
+ LOW,
+ LEFT,
+ MIDDLE,
+ RIGHT,
+ HIGH
+};
+
+static void test_free_merge_left_or_right(bool left)
+{
+ static const uintptr_t indices_0 [] = {
+ 0,
+ 3,
+ 4,
+ 5,
+ 6,
+ 7
+ };
+ static const bool frees_0 [] = {
+ true,
+ false,
+ false,
+ false,
+ false,
+ false
+ };
+ static const uintptr_t indices_1_left [] = {
+ 0,
+ 3,
+ 4,
+ 5,
+ 6,
+ 7
+ };
+ static const bool frees_1_left [] = {
+ true,
+ false,
+ true,
+ false,
+ false,
+ false
+ };
+ static const uintptr_t indices_1_right [] = {
+ 0,
+ 3,
+ 4,
+ 5,
+ 6,
+ 7
+ };
+ static const bool frees_1_right [] = {
+ true,
+ false,
+ false,
+ false,
+ true,
+ false
+ };
+ static const uintptr_t indices_2_left [] = {
+ 0,
+ 3,
+ 4,
+ 6,
+ 7
+ };
+ static const bool frees_2_left [] = {
+ true,
+ false,
+ true,
+ false,
+ false
+ };
+ static const uintptr_t indices_2_right [] = {
+ 0,
+ 3,
+ 4,
+ 5,
+ 7
+ };
+ static const bool frees_2_right [] = {
+ true,
+ false,
+ false,
+ true,
+ false
+ };
+
+ rtems_status_code sc = RTEMS_SUCCESSFUL;
+ rtems_rbheap_control control;
+ void *ptr [HIGH + 1];
+ int dir = left ? LEFT : RIGHT;
+ int i = 0;
+
+ test_init_successful(&control);
+
+ for (i = sizeof(ptr) / sizeof(ptr [0]) - 1; i >= 0; --i) {
+ ptr [i] = rtems_rbheap_allocate(&control, PAGE_SIZE);
+ rtems_test_assert(ptr [i] != NULL);
+ }
+
+ TEST_PAGE_TREE(&control, indices_0, frees_0);
+
+ sc = rtems_rbheap_free(&control, ptr [dir]);
+ rtems_test_assert(sc == RTEMS_SUCCESSFUL);
+
+ if (left) {
+ TEST_PAGE_TREE(&control, indices_1_left, frees_1_left);
+ } else {
+ TEST_PAGE_TREE(&control, indices_1_right, frees_1_right);
+ }
+
+ sc = rtems_rbheap_free(&control, ptr [MIDDLE]);
+ rtems_test_assert(sc == RTEMS_SUCCESSFUL);
+
+ if (left) {
+ TEST_PAGE_TREE(&control, indices_2_left, frees_2_left);
+ } else {
+ TEST_PAGE_TREE(&control, indices_2_right, frees_2_right);
+ }
+}
+
+static void Init(rtems_task_argument arg)
+{
+ puts("\n\n*** TEST RBHEAP 1 ***");
+
+ test_init_page_alignment();
+ test_init_begin_greater_than_end();
+ test_init_begin_greater_than_aligned_begin();
+ test_init_aligned_begin_greater_than_aligned_end();
+ test_init_empty_page_pool();
+ test_alloc_and_free_one();
+ test_alloc_zero();
+ test_alloc_huge_page();
+ test_alloc_one_page();
+ test_alloc_many_pages();
+ test_free_invalid();
+ test_free_double();
+ test_free_merge_left_or_right(true);
+ test_free_merge_left_or_right(false);
+
+ puts("*** END OF TEST RBHEAP 1 ***");
+
+ rtems_test_exit(0);
+}
+
+#define CONFIGURE_APPLICATION_NEEDS_CLOCK_DRIVER
+#define CONFIGURE_APPLICATION_NEEDS_CONSOLE_DRIVER
+
+#define CONFIGURE_MAXIMUM_TASKS 1
+
+#define CONFIGURE_RTEMS_INIT_TASKS_TABLE
+
+#define CONFIGURE_INIT
+
+#include <rtems/confdefs.h>
diff --git a/testsuites/libtests/rbheap01/rbheap01.doc b/testsuites/libtests/rbheap01/rbheap01.doc
new file mode 100644
index 0000000..f8dd07e
--- /dev/null
+++ b/testsuites/libtests/rbheap01/rbheap01.doc
@@ -0,0 +1,11 @@
+This file describes the directives and concepts tested by this test set.
+
+test set name: rbheap01
+
+directives:
+
+ TBD
+
+concepts:
+
+ TBD
diff --git a/testsuites/libtests/rbheap01/rbheap01.scn b/testsuites/libtests/rbheap01/rbheap01.scn
new file mode 100644
index 0000000..ddbc9b3
--- /dev/null
+++ b/testsuites/libtests/rbheap01/rbheap01.scn
@@ -0,0 +1,2 @@
+*** TEST RBHEAP 1 ***
+*** END OF TEST RBHEAP 1 ***
More information about the vc
mailing list