rbheap: API changes and documentation

1 files changed, 95 insertions, 94 deletions

diff --git a/cpukit/sapi/src/rbheap.c b/cpukit/sapi/src/rbheap.c
index 798632520d..7facf4f9af 100644
--- a/cpukit/sapi/src/rbheap.c
+++ b/cpukit/sapi/src/rbheap.c
@@ -28,96 +28,96 @@
 
 #include <stdlib.h>
 
-static uintptr_t align_up(uintptr_t page_alignment, uintptr_t value)
+static uintptr_t align_up(uintptr_t alignment, uintptr_t value)
 {
-  uintptr_t excess = value % page_alignment;
+  uintptr_t excess = value % alignment;
 
   if (excess > 0) {
-    value += page_alignment - excess;
+    value += alignment - excess;
   }
 
   return value;
 }
 
-static uintptr_t align_down(uintptr_t page_alignment, uintptr_t value)
+static uintptr_t align_down(uintptr_t alignment, uintptr_t value)
 {
-  uintptr_t excess = value % page_alignment;
+  uintptr_t excess = value % alignment;
 
   return value - excess;
 }
 
-static int page_compare(const rtems_rbtree_node *a, const rtems_rbtree_node *b)
+static int chunk_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);
+  const rtems_rbheap_chunk *left = rtems_rbheap_chunk_of_node(a);
+  const rtems_rbheap_chunk *right = rtems_rbheap_chunk_of_node(b);
 
   return (int) (left->begin - right->begin);
 }
 
-static rtems_rbheap_page *get_page(rtems_rbheap_control *control)
+static rtems_rbheap_chunk *get_chunk(rtems_rbheap_control *control)
 {
-  rtems_chain_control *pool_chain = &control->pool_chain;
-  rtems_chain_node *page = rtems_chain_get(pool_chain);
+  rtems_chain_control *chain = &control->spare_descriptor_chain;
+  rtems_chain_node *chunk = rtems_chain_get_unprotected(chain);
 
-  if (page == NULL) {
-    (*control->extend_page_pool)(control);
-    page = rtems_chain_get(pool_chain);
+  if (chunk == NULL) {
+    (*control->extend_descriptors)(control);
+    chunk = rtems_chain_get_unprotected(chain);
   }
 
-  return (rtems_rbheap_page *) page;
+  return (rtems_rbheap_chunk *) chunk;
 }
 
 static void add_to_chain(
   rtems_chain_control *chain,
-  rtems_rbheap_page *page
+  rtems_rbheap_chunk *chunk
 )
 {
-  rtems_chain_prepend_unprotected(chain, &page->chain_node);
+  rtems_chain_prepend_unprotected(chain, &chunk->chain_node);
 }
 
 static void insert_into_tree(
   rtems_rbtree_control *tree,
-  rtems_rbheap_page *page
+  rtems_rbheap_chunk *chunk
 )
 {
-  _RBTree_Insert_unprotected(tree, &page->tree_node);
+  _RBTree_Insert_unprotected(tree, &chunk->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,
+  uintptr_t alignment,
+  rtems_rbheap_extend_descriptors extend_descriptors,
   void *handler_arg
 )
 {
   rtems_status_code sc = RTEMS_SUCCESSFUL;
 
-  if (page_alignment > 0) {
+  if (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);
+    uintptr_t aligned_begin = align_up(alignment, begin);
+    uintptr_t aligned_end = align_down(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_control *free_chain = &control->free_chunk_chain;
+      rtems_rbtree_control *chunk_tree = &control->chunk_tree;
+      rtems_rbheap_chunk *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;
+      rtems_chain_initialize_empty(&control->spare_descriptor_chain);
+      rtems_rbtree_initialize_empty(chunk_tree, chunk_compare, true);
+      control->alignment = alignment;
       control->handler_arg = handler_arg;
-      control->extend_page_pool = extend_page_pool;
+      control->extend_descriptors = extend_descriptors;
 
-      first = get_page(control);
+      first = get_chunk(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);
+        insert_into_tree(chunk_tree, first);
       } else {
         sc = RTEMS_NO_MEMORY;
       }
@@ -131,20 +131,20 @@ rtems_status_code rtems_rbheap_initialize(
   return sc;
 }
 
-static rtems_rbheap_page *search_free_page(
+static rtems_rbheap_chunk *search_free_chunk(
   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;
+  rtems_rbheap_chunk *big_enough = NULL;
 
   while (current != tail && big_enough == NULL) {
-    rtems_rbheap_page *free_page = (rtems_rbheap_page *) current;
+    rtems_rbheap_chunk *free_chunk = (rtems_rbheap_chunk *) current;
 
-    if (free_page->size >= size) {
-      big_enough = free_page;
+    if (free_chunk->size >= size) {
+      big_enough = free_chunk;
     }
 
     current = rtems_chain_next(current);
@@ -156,34 +156,34 @@ static rtems_rbheap_page *search_free_page(
 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);
+  rtems_chain_control *free_chain = &control->free_chunk_chain;
+  rtems_rbtree_control *chunk_tree = &control->chunk_tree;
+  uintptr_t alignment = control->alignment;
+  uintptr_t aligned_size = align_up(alignment, size);
 
   if (size > 0 && size <= aligned_size) {
-    rtems_rbheap_page *free_page = search_free_page(free_chain, aligned_size);
+    rtems_rbheap_chunk *free_chunk = search_free_chunk(free_chain, aligned_size);
 
-    if (free_page != NULL) {
-      uintptr_t free_size = free_page->size;
+    if (free_chunk != NULL) {
+      uintptr_t free_size = free_chunk->size;
 
       if (free_size > aligned_size) {
-        rtems_rbheap_page *new_page = get_page(control);
+        rtems_rbheap_chunk *new_chunk = get_chunk(control);
 
-        if (new_page != NULL) {
+        if (new_chunk != 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;
+          free_chunk->size = new_free_size;
+          new_chunk->begin = free_chunk->begin + new_free_size;
+          new_chunk->size = aligned_size;
+          rtems_chain_set_off_chain(&new_chunk->chain_node);
+          insert_into_tree(chunk_tree, new_chunk);
+          ptr = (void *) new_chunk->begin;
         }
       } else {
-        rtems_chain_extract_unprotected(&free_page->chain_node);
-        rtems_chain_set_off_chain(&free_page->chain_node);
-        ptr = (void *) free_page->begin;
+        rtems_chain_extract_unprotected(&free_chunk->chain_node);
+        rtems_chain_set_off_chain(&free_chunk->chain_node);
+        ptr = (void *) free_chunk->begin;
       }
     }
   }
@@ -191,38 +191,38 @@ void *rtems_rbheap_allocate(rtems_rbheap_control *control, size_t size)
   return ptr;
 }
 
-#define NULL_PAGE rtems_rbheap_page_of_node(NULL)
+#define NULL_PAGE rtems_rbheap_chunk_of_node(NULL)
 
-static rtems_rbheap_page *find(rtems_rbtree_control *page_tree, uintptr_t key)
+static rtems_rbheap_chunk *find(rtems_rbtree_control *chunk_tree, uintptr_t key)
 {
-  rtems_rbheap_page page = { .begin = key };
+  rtems_rbheap_chunk chunk = { .begin = key };
 
-  return rtems_rbheap_page_of_node(
-    _RBTree_Find_unprotected(page_tree, &page.tree_node)
+  return rtems_rbheap_chunk_of_node(
+    _RBTree_Find_unprotected(chunk_tree, &chunk.tree_node)
   );
 }
 
-static rtems_rbheap_page *get_next(
-  const rtems_rbtree_control *page_tree,
-  const rtems_rbheap_page *page,
+static rtems_rbheap_chunk *get_next(
+  const rtems_rbtree_control *chunk_tree,
+  const rtems_rbheap_chunk *chunk,
   RBTree_Direction dir
 )
 {
-  return rtems_rbheap_page_of_node(
-    _RBTree_Next_unprotected(page_tree, &page->tree_node, dir)
+  return rtems_rbheap_chunk_of_node(
+    _RBTree_Next_unprotected(chunk_tree, &chunk->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
+  rtems_rbtree_control *chunk_tree,
+  rtems_rbheap_chunk *a,
+  rtems_rbheap_chunk *b
 )
 {
-  if (b != NULL_PAGE && rtems_rbheap_is_page_free(b)) {
+  if (b != NULL_PAGE && rtems_rbheap_is_chunk_free(b)) {
     if (b->begin < a->begin) {
-      rtems_rbheap_page *t = a;
+      rtems_rbheap_chunk *t = a;
 
       a = b;
       b = t;
@@ -231,47 +231,48 @@ static void check_and_merge(
     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);
+    _RBTree_Extract_unprotected(chunk_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);
+
+  if (ptr != NULL) {
+    rtems_chain_control *free_chain = &control->free_chunk_chain;
+    rtems_rbtree_control *chunk_tree = &control->chunk_tree;
+    rtems_rbheap_chunk *chunk = find(chunk_tree, (uintptr_t) ptr);
+
+    if (chunk != NULL_PAGE) {
+      if (!rtems_rbheap_is_chunk_free(chunk)) {
+        rtems_rbheap_chunk *pred = get_next(chunk_tree, chunk, RBT_LEFT);
+        rtems_rbheap_chunk *succ = get_next(chunk_tree, chunk, RBT_RIGHT);
+
+        check_and_merge(free_chain, chunk_tree, chunk, succ);
+        add_to_chain(free_chain, chunk);
+        check_and_merge(free_chain, chunk_tree, chunk, pred);
+      } else {
+        sc = RTEMS_INCORRECT_STATE;
+      }
     } else {
-      sc = RTEMS_INCORRECT_STATE;
+      sc = RTEMS_INVALID_ID;
     }
-  } else {
-    sc = RTEMS_INVALID_ID;
   }
 
   return sc;
 }
 
-void rtems_rbheap_extend_page_pool_never(rtems_rbheap_control *control)
+void rtems_rbheap_extend_descriptors_never(rtems_rbheap_control *control)
 {
   /* Do nothing */
 }
 
-void rtems_rbheap_extend_page_pool_with_malloc(rtems_rbheap_control *control)
+void rtems_rbheap_extend_descriptors_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);
+  rtems_rbheap_chunk *chunk = malloc(sizeof(*chunk));
 
-    add_to_chain(pool_chain, page);
+  if (chunk != NULL) {
+    rtems_rbheap_add_to_spare_descriptor_chain(control, chunk);
   }
 }