source: rtems/cpukit/score/include/rtems/score/heap.h @ 03f2154e

4.104.114.84.95
Last change on this file since 03f2154e was 03f2154e, checked in by Joel Sherrill <joel.sherrill@…>, on 04/22/97 at 17:20:27

headers updated to reflect new style copyright notice as part
of switching to the modified GNU GPL.

  • Property mode set to 100644
File size: 6.0 KB
Line 
1/*  heap.h
2 *
3 *  This include file contains the information pertaining to the Heap
4 *  Handler.  A heap is a doubly linked list of variable size
5 *  blocks which are allocated using the first fit method.  Garbage
6 *  collection is performed each time a block is returned to the heap by
7 *  coalescing neighbor blocks.  Control information for both allocated
8 *  and unallocated blocks is contained in the heap space.  A heap header
9 *  contains control information for the heap.
10 *
11 *  COPYRIGHT (c) 1989-1997.
12 *  On-Line Applications Research Corporation (OAR).
13 *  Copyright assigned to U.S. Government, 1994.
14 *
15 *  The license and distribution terms for this file may in
16 *  the file LICENSE in this distribution or at
17 *  http://www.OARcorp.com/rtems/license.html.
18 *
19 *  $Id$
20 */
21
22#ifndef __RTEMS_HEAP_h
23#define __RTEMS_HEAP_h
24
25#ifdef __cplusplus
26extern "C" {
27#endif
28
29/*
30 *  Status codes for heap_extend
31 */
32
33typedef enum {
34  HEAP_EXTEND_SUCCESSFUL,
35  HEAP_EXTEND_ERROR,
36  HEAP_EXTEND_NOT_IMPLEMENTED
37}  Heap_Extend_status;
38
39/*
40 *  Constants used in the size/used field of each heap block to
41 *  indicate when a block is free or in use.
42 */
43
44#define HEAP_BLOCK_USED    1           /* indicates block is in use */
45#define HEAP_BLOCK_FREE    0           /* indicates block is free */
46
47/*
48 *  The size/used field value for the dummy front and back flags.
49 */
50
51#define HEAP_DUMMY_FLAG    (0 + HEAP_BLOCK_USED)
52
53/*
54 *  The following constants reflect various requirements of the
55 *  heap data structures which impact the management of a heap.
56 *
57 * NOTE:   Because free block overhead is greater than used block
58 *         overhead AND a portion of the allocated space is from
59 *         the extra free block overhead, the absolute lower bound
60 *         of the minimum fragment size is equal to the size of
61 *         the free block overhead.
62 */
63
64#define HEAP_OVERHEAD \
65  (sizeof( unsigned32 ) * 2)         /* size dummy first and last blocks */
66#define HEAP_BLOCK_USED_OVERHEAD \
67  (sizeof( void * ) * 2)             /* num bytes overhead in used block */
68#define HEAP_MINIMUM_SIZE \
69  (HEAP_OVERHEAD + sizeof (Heap_Block))
70                                     /* min number of bytes the user may */
71                                     /*   specify for the heap size      */
72
73/*
74 *  The following defines the data structure used to manage
75 *  individual blocks in a heap.   When the block is allocated, the
76 *  next and previous fields are not used by the Heap Handler
77 *  and thus the address returned for the block starts at
78 *  the address of the next field.
79 *
80 *  NOTE:  The next and previous pointers are only valid when the
81 *         block is free.  Caution must be exercised to insure that
82 *         allocated blocks are large enough to contain them and
83 *         that they are not accidentally overwritten when the
84 *         block is actually allocated.
85 */
86
87typedef struct Heap_Block_struct Heap_Block;
88
89struct Heap_Block_struct {
90  unsigned32  back_flag;   /* size and status of prev block */
91  unsigned32  front_flag;  /* size and status of block */
92  Heap_Block *next;        /* pointer to next block */
93  Heap_Block *previous;    /* pointer to previous block */
94};
95
96/*
97 *  The following defines the control block used to manage each heap.
98 *
99 *  NOTE:
100 *
101 *  This structure is layed out such that it can be used a a dummy
102 *  first and last block on the free block chain.  The extra padding
103 *  insures the dummy last block is the correct size.
104 *
105 *  The first Heap_Block starts at first while the second starts at
106 *  final.  This is effectively the same trick as is used in the Chain
107 *  Handler.
108 */
109
110typedef struct {
111  Heap_Block *start;       /* first valid block address in heap */
112  Heap_Block *final;       /* last valid block address in heap */
113
114  Heap_Block *first;       /* pointer to first block in heap */
115  Heap_Block *permanent_null;  /* always NULL pointer */
116  Heap_Block *last;        /* pointer to last block in heap */
117  unsigned32  page_size;   /* allocation unit */
118  unsigned32  reserved;
119}   Heap_Control;
120
121/*
122 *  _Heap_Initialize
123 *
124 *  DESCRIPTION:
125 *
126 *  This routine initializes the_heap record to manage the
127 *  contiguous heap of size bytes which starts at starting_address.
128 *  Blocks of memory are allocated from the heap in multiples of
129 *  page_size byte units.
130 */
131
132unsigned32 _Heap_Initialize(
133  Heap_Control *the_heap,
134  void         *starting_address,
135  unsigned32    size,
136  unsigned32    page_size
137);
138
139/*
140 *  _Heap_Extend
141 *
142 *  DESCRIPTION:
143 *
144 *  This routine grows the_heap memory area using the size bytes which
145 *  begin at starting_address.
146 */
147
148Heap_Extend_status _Heap_Extend(
149  Heap_Control *the_heap,
150  void         *starting_address,
151  unsigned32    size,
152  unsigned32   *amount_extended
153);
154
155/*
156 *  _Heap_Allocate
157 *
158 *  DESCRIPTION:
159 *
160 *  DESCRIPTION:
161 *
162 *  This function attempts to allocate a block of size bytes from
163 *  the_heap.  If insufficient memory is free in the_heap to allocate
164 *  a  block of the requested size, then NULL is returned.
165 */
166
167void *_Heap_Allocate(
168  Heap_Control *the_heap,
169  unsigned32    size
170);
171
172/*
173 *  _Heap_Size_of_user_area
174 *
175 *  DESCRIPTION:
176 *
177 *  This kernel routine sets size to the size of the given heap block.
178 *  It returns TRUE if the starting_address is in the heap, and FALSE
179 *  otherwise.
180 */
181
182boolean _Heap_Size_of_user_area(
183  Heap_Control        *the_heap,
184  void                *starting_address,
185  unsigned32          *size
186);
187
188/*
189 *  _Heap_Free
190 *
191 *  DESCRIPTION:
192 *
193 *  This routine returns the block of memory which begins
194 *  at starting_address to the_heap.  Any coalescing which is
195 *  possible with the freeing of this routine is performed.
196 */
197
198boolean _Heap_Free(
199  Heap_Control *the_heap,
200  void         *start_address
201);
202
203/*
204 *  _Heap_Walk
205 *
206 *  DESCRIPTION:
207 *
208 *  This routine walks the heap to verify its integrity.
209 */
210
211void _Heap_Walk(
212  Heap_Control *the_heap,
213  int           source,
214  boolean       do_dump
215);
216
217#ifndef __RTEMS_APPLICATION__
218#include <rtems/score/heap.inl>
219#endif
220
221#ifdef __cplusplus
222}
223#endif
224
225#endif
226/* end of include file */
Note: See TracBrowser for help on using the repository browser.