source: rtems/cpukit/sapi/src/rbheap.c @ c499856

4.11
Last change on this file since c499856 was c499856, checked in by Chris Johns <chrisj@…>, on Mar 20, 2014 at 9:10:47 PM

Change all references of rtems.com to rtems.org.

  • Property mode set to 100644
File size: 6.9 KB
Line 
1/**
2 * @file
3 *
4 * @ingroup RBHeap
5 *
6 * @brief Red-Black Tree Heap implementation.
7 */
8
9/*
10 * Copyright (c) 2012 embedded brains GmbH.  All rights reserved.
11 *
12 *  embedded brains GmbH
13 *  Obere Lagerstr. 30
14 *  82178 Puchheim
15 *  Germany
16 *  <rtems@embedded-brains.de>
17 *
18 * The license and distribution terms for this file may be
19 * found in the file LICENSE in this distribution or at
20 * http://www.rtems.org/license/LICENSE.
21 */
22
23#if HAVE_CONFIG_H
24  #include "config.h"
25#endif
26
27#include <rtems/rbheap.h>
28
29#include <stdlib.h>
30
31static uintptr_t align_up(uintptr_t alignment, uintptr_t value)
32{
33  uintptr_t excess = value % alignment;
34
35  if (excess > 0) {
36    value += alignment - excess;
37  }
38
39  return value;
40}
41
42static uintptr_t align_down(uintptr_t alignment, uintptr_t value)
43{
44  uintptr_t excess = value % alignment;
45
46  return value - excess;
47}
48
49static int chunk_compare(const rtems_rbtree_node *a, const rtems_rbtree_node *b)
50{
51  const rtems_rbheap_chunk *left = rtems_rbheap_chunk_of_node(a);
52  const rtems_rbheap_chunk *right = rtems_rbheap_chunk_of_node(b);
53
54  return (int) (left->begin - right->begin);
55}
56
57static rtems_rbheap_chunk *get_chunk(rtems_rbheap_control *control)
58{
59  rtems_chain_control *chain = &control->spare_descriptor_chain;
60  rtems_chain_node *chunk = rtems_chain_get_unprotected(chain);
61
62  if (chunk == NULL) {
63    (*control->extend_descriptors)(control);
64    chunk = rtems_chain_get_unprotected(chain);
65  }
66
67  return (rtems_rbheap_chunk *) chunk;
68}
69
70static void add_to_chain(
71  rtems_chain_control *chain,
72  rtems_rbheap_chunk *chunk
73)
74{
75  rtems_chain_prepend_unprotected(chain, &chunk->chain_node);
76}
77
78static void insert_into_tree(
79  rtems_rbtree_control *tree,
80  rtems_rbheap_chunk *chunk
81)
82{
83  _RBTree_Insert(tree, &chunk->tree_node);
84}
85
86rtems_status_code rtems_rbheap_initialize(
87  rtems_rbheap_control *control,
88  void *area_begin,
89  uintptr_t area_size,
90  uintptr_t alignment,
91  rtems_rbheap_extend_descriptors extend_descriptors,
92  void *handler_arg
93)
94{
95  rtems_status_code sc = RTEMS_SUCCESSFUL;
96
97  if (alignment > 0) {
98    uintptr_t begin = (uintptr_t) area_begin;
99    uintptr_t end = begin + area_size;
100    uintptr_t aligned_begin = align_up(alignment, begin);
101    uintptr_t aligned_end = align_down(alignment, end);
102
103    if (begin < end && begin <= aligned_begin && aligned_begin < aligned_end) {
104      rtems_chain_control *free_chain = &control->free_chunk_chain;
105      rtems_rbtree_control *chunk_tree = &control->chunk_tree;
106      rtems_rbheap_chunk *first = NULL;
107
108      rtems_chain_initialize_empty(free_chain);
109      rtems_chain_initialize_empty(&control->spare_descriptor_chain);
110      rtems_rbtree_initialize_empty(chunk_tree, chunk_compare, true);
111      control->alignment = alignment;
112      control->handler_arg = handler_arg;
113      control->extend_descriptors = extend_descriptors;
114
115      first = get_chunk(control);
116      if (first != NULL) {
117        first->begin = aligned_begin;
118        first->size = aligned_end - aligned_begin;
119        add_to_chain(free_chain, first);
120        insert_into_tree(chunk_tree, first);
121      } else {
122        sc = RTEMS_NO_MEMORY;
123      }
124    } else {
125      sc = RTEMS_INVALID_ADDRESS;
126    }
127  } else {
128    sc = RTEMS_INVALID_NUMBER;
129  }
130
131  return sc;
132}
133
134static rtems_rbheap_chunk *search_free_chunk(
135  rtems_chain_control *free_chain,
136  size_t size
137)
138{
139  rtems_chain_node *current = rtems_chain_first(free_chain);
140  const rtems_chain_node *tail = rtems_chain_tail(free_chain);
141  rtems_rbheap_chunk *big_enough = NULL;
142
143  while (current != tail && big_enough == NULL) {
144    rtems_rbheap_chunk *free_chunk = (rtems_rbheap_chunk *) current;
145
146    if (free_chunk->size >= size) {
147      big_enough = free_chunk;
148    }
149
150    current = rtems_chain_next(current);
151  }
152
153  return big_enough;
154}
155
156void *rtems_rbheap_allocate(rtems_rbheap_control *control, size_t size)
157{
158  void *ptr = NULL;
159  rtems_chain_control *free_chain = &control->free_chunk_chain;
160  rtems_rbtree_control *chunk_tree = &control->chunk_tree;
161  uintptr_t alignment = control->alignment;
162  uintptr_t aligned_size = align_up(alignment, size);
163
164  if (size > 0 && size <= aligned_size) {
165    rtems_rbheap_chunk *free_chunk = search_free_chunk(free_chain, aligned_size);
166
167    if (free_chunk != NULL) {
168      uintptr_t free_size = free_chunk->size;
169
170      if (free_size > aligned_size) {
171        rtems_rbheap_chunk *new_chunk = get_chunk(control);
172
173        if (new_chunk != NULL) {
174          uintptr_t new_free_size = free_size - aligned_size;
175
176          free_chunk->size = new_free_size;
177          new_chunk->begin = free_chunk->begin + new_free_size;
178          new_chunk->size = aligned_size;
179          rtems_chain_set_off_chain(&new_chunk->chain_node);
180          insert_into_tree(chunk_tree, new_chunk);
181          ptr = (void *) new_chunk->begin;
182        }
183      } else {
184        rtems_chain_extract_unprotected(&free_chunk->chain_node);
185        rtems_chain_set_off_chain(&free_chunk->chain_node);
186        ptr = (void *) free_chunk->begin;
187      }
188    }
189  }
190
191  return ptr;
192}
193
194#define NULL_PAGE rtems_rbheap_chunk_of_node(NULL)
195
196static rtems_rbheap_chunk *find(rtems_rbtree_control *chunk_tree, uintptr_t key)
197{
198  rtems_rbheap_chunk chunk = { .begin = key };
199
200  return rtems_rbheap_chunk_of_node(
201    _RBTree_Find(chunk_tree, &chunk.tree_node)
202  );
203}
204
205static rtems_rbheap_chunk *get_next(
206  const rtems_rbheap_chunk *chunk,
207  RBTree_Direction dir
208)
209{
210  return rtems_rbheap_chunk_of_node(
211    _RBTree_Next(&chunk->tree_node, dir)
212  );
213}
214
215static void check_and_merge(
216  rtems_chain_control *free_chain,
217  rtems_rbtree_control *chunk_tree,
218  rtems_rbheap_chunk *a,
219  rtems_rbheap_chunk *b
220)
221{
222  if (b != NULL_PAGE && rtems_rbheap_is_chunk_free(b)) {
223    if (b->begin < a->begin) {
224      rtems_rbheap_chunk *t = a;
225
226      a = b;
227      b = t;
228    }
229
230    a->size += b->size;
231    rtems_chain_extract_unprotected(&b->chain_node);
232    add_to_chain(free_chain, b);
233    _RBTree_Extract(chunk_tree, &b->tree_node);
234  }
235}
236
237rtems_status_code rtems_rbheap_free(rtems_rbheap_control *control, void *ptr)
238{
239  rtems_status_code sc = RTEMS_SUCCESSFUL;
240
241  if (ptr != NULL) {
242    rtems_chain_control *free_chain = &control->free_chunk_chain;
243    rtems_rbtree_control *chunk_tree = &control->chunk_tree;
244    rtems_rbheap_chunk *chunk = find(chunk_tree, (uintptr_t) ptr);
245
246    if (chunk != NULL_PAGE) {
247      if (!rtems_rbheap_is_chunk_free(chunk)) {
248        rtems_rbheap_chunk *pred = get_next(chunk, RBT_LEFT);
249        rtems_rbheap_chunk *succ = get_next(chunk, RBT_RIGHT);
250
251        check_and_merge(free_chain, chunk_tree, chunk, succ);
252        add_to_chain(free_chain, chunk);
253        check_and_merge(free_chain, chunk_tree, chunk, pred);
254      } else {
255        sc = RTEMS_INCORRECT_STATE;
256      }
257    } else {
258      sc = RTEMS_INVALID_ID;
259    }
260  }
261
262  return sc;
263}
264
265void rtems_rbheap_extend_descriptors_never(rtems_rbheap_control *control)
266{
267  /* Do nothing */
268}
269
270void rtems_rbheap_extend_descriptors_with_malloc(rtems_rbheap_control *control)
271{
272  rtems_rbheap_chunk *chunk = malloc(sizeof(*chunk));
273
274  if (chunk != NULL) {
275    rtems_rbheap_add_to_spare_descriptor_chain(control, chunk);
276  }
277}
Note: See TracBrowser for help on using the repository browser.