LXR 6.1/​cpukit/​sapi/​src/​rbheap.c	Source navigation Diff markup Identifier search General search
	Version: 6.1 Revert   Change

File indexing completed on 2025-05-11 08:24:22

 /* SPDX-License-Identifier: BSD-2-Clause */
 
 /**
  * @file
  *
  * @ingroup RTEMSAPIRBHeap
  *
  * @brief This source file contains the implementation of
  *   rtems_rbheap_allocate(), rtems_rbheap_extend_descriptors_never(),
  *   rtems_rbheap_extend_descriptors_with_malloc(), rtems_rbheap_free(), and
  *   rtems_rbheap_initialize().
  */
 
 /*
  * Copyright (C) 2012, 2015 embedded brains GmbH & Co. KG
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
  *
  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  * POSSIBILITY OF SUCH DAMAGE.
  */
 
 #ifdef HAVE_CONFIG_H
 #include "config.h"
 #endif
 
 #include <rtems/rbheap.h>
 
 #include <stdlib.h>
 
 static uintptr_t align_up(uintptr_t alignment, uintptr_t value)
 {
   uintptr_t excess = value % alignment;
 
   if (excess > 0) {
     value += alignment - excess;
   }
 
   return value;
 }
 
 static uintptr_t align_down(uintptr_t alignment, uintptr_t value)
 {
   uintptr_t excess = value % alignment;
 
   return value - excess;
 }
 
 static rtems_rbtree_compare_result chunk_compare(
   const rtems_rbtree_node *a,
   const rtems_rbtree_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 (rtems_rbtree_compare_result)
     ((left->begin >> 1) - (right->begin >> 1));
 }
 
 static rtems_rbheap_chunk *get_chunk(rtems_rbheap_control *control)
 {
   rtems_chain_control *chain = &control->spare_descriptor_chain;
   rtems_chain_node *chunk = rtems_chain_get_unprotected(chain);
 
   if (chunk == NULL) {
     (*control->extend_descriptors)(control);
     chunk = rtems_chain_get_unprotected(chain);
   }
 
   return (rtems_rbheap_chunk *) chunk;
 }
 
 static void add_to_chain(
   rtems_chain_control *chain,
   rtems_rbheap_chunk *chunk
 )
 {
   rtems_chain_initialize_node(&chunk->chain_node);
   rtems_chain_prepend_unprotected(chain, &chunk->chain_node);
 }
 
 static void insert_into_tree(
   rtems_rbtree_control *tree,
   rtems_rbheap_chunk *chunk
 )
 {
   rtems_rbtree_insert(tree, &chunk->tree_node, chunk_compare, true);
 }
 
 rtems_status_code rtems_rbheap_initialize(
   rtems_rbheap_control *control,
   void *area_begin,
   uintptr_t area_size,
   uintptr_t alignment,
   rtems_rbheap_extend_descriptors extend_descriptors,
   void *handler_arg
 )
 {
   rtems_status_code sc = RTEMS_SUCCESSFUL;
   uintptr_t begin = (uintptr_t) area_begin;
   uintptr_t end = begin + area_size;
   uintptr_t aligned_begin;
   uintptr_t aligned_end;
 
   /*
    * Ensure that the alignment is at least two, so that we can keep
    * chunk_compare() that simple.
    */
   alignment = alignment < 2 ? 2 : alignment;
 
   aligned_begin = align_up(alignment, begin);
   aligned_end = align_down(alignment, end);
 
   if (begin < end && begin <= aligned_begin && aligned_begin < aligned_end) {
     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->spare_descriptor_chain);
     rtems_rbtree_initialize_empty(chunk_tree);
     control->alignment = alignment;
     control->handler_arg = handler_arg;
     control->extend_descriptors = extend_descriptors;
 
     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(chunk_tree, first);
     } else {
       sc = RTEMS_NO_MEMORY;
     }
   } else {
     sc = RTEMS_INVALID_ADDRESS;
   }
 
   return sc;
 }
 
 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_chunk *big_enough = NULL;
 
   while (current != tail && big_enough == NULL) {
     rtems_rbheap_chunk *free_chunk = (rtems_rbheap_chunk *) current;
 
     if (free_chunk->size >= size) {
       big_enough = free_chunk;
     }
 
     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_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_chunk *free_chunk = search_free_chunk(free_chain, aligned_size);
 
     if (free_chunk != NULL) {
       uintptr_t free_size = free_chunk->size;
 
       if (free_size > aligned_size) {
         rtems_rbheap_chunk *new_chunk = get_chunk(control);
 
         if (new_chunk != NULL) {
           uintptr_t new_free_size = free_size - aligned_size;
 
           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_chunk->chain_node);
         rtems_chain_set_off_chain(&free_chunk->chain_node);
         ptr = (void *) free_chunk->begin;
       }
     }
   }
 
   return ptr;
 }
 
 #define NULL_PAGE rtems_rbheap_chunk_of_node(NULL)
 
 static rtems_rbheap_chunk *find(rtems_rbtree_control *chunk_tree, uintptr_t key)
 {
   rtems_rbheap_chunk chunk = { .begin = key };
 
   return rtems_rbheap_chunk_of_node(
     rtems_rbtree_find(chunk_tree, &chunk.tree_node, chunk_compare, true)
   );
 }
 
 static rtems_rbheap_chunk *pred(const rtems_rbheap_chunk *chunk)
 {
   return rtems_rbheap_chunk_of_node(
     rtems_rbtree_predecessor(&chunk->tree_node)
   );
 }
 
 static rtems_rbheap_chunk *succ(const rtems_rbheap_chunk *chunk)
 {
   return rtems_rbheap_chunk_of_node(
     rtems_rbtree_successor(&chunk->tree_node)
   );
 }
 
 static void check_and_merge(
   rtems_rbheap_control *control,
   rtems_rbheap_chunk *a,
   rtems_rbheap_chunk *b,
   rtems_rbheap_chunk *c
 )
 {
   if (c != NULL_PAGE && rtems_rbheap_is_chunk_free(c)) {
     a->size += b->size;
     rtems_chain_extract_unprotected(&b->chain_node);
     rtems_rbheap_add_to_spare_descriptor_chain(control, b);
     rtems_rbtree_extract(&control->chunk_tree, &b->tree_node);
   }
 }
 
 rtems_status_code rtems_rbheap_free(rtems_rbheap_control *control, void *ptr)
 {
   rtems_status_code sc = RTEMS_SUCCESSFUL;
 
   if (ptr != NULL) {
     rtems_rbheap_chunk *chunk = find(&control->chunk_tree, (uintptr_t) ptr);
 
     if (chunk != NULL_PAGE) {
       if (!rtems_rbheap_is_chunk_free(chunk)) {
         rtems_rbheap_chunk *other;
 
         add_to_chain(&control->free_chunk_chain, chunk);
         other = succ(chunk);
         check_and_merge(control, chunk, other, other);
         other = pred(chunk);
         check_and_merge(control, other, chunk, other);
       } else {
         sc = RTEMS_INCORRECT_STATE;
       }
     } else {
       sc = RTEMS_INVALID_ID;
     }
   }
 
   return sc;
 }
 
 void rtems_rbheap_extend_descriptors_never(rtems_rbheap_control *control)
 {
   /* Do nothing */
 }
 
 void rtems_rbheap_extend_descriptors_with_malloc(rtems_rbheap_control *control)
 {
   rtems_rbheap_chunk *chunk = malloc(sizeof(*chunk));
 
   if (chunk != NULL) {
     rtems_rbheap_add_to_spare_descriptor_chain(control, chunk);
   }
 }

This page was automatically generated by the 2.3.7 LXR engine. The LXR team