diff options
Diffstat (limited to 'firmware/include/buflib.h')
-rw-r--r-- | firmware/include/buflib.h | 319 |
1 files changed, 319 insertions, 0 deletions
diff --git a/firmware/include/buflib.h b/firmware/include/buflib.h new file mode 100644 index 0000000000..db7b5ec50a --- /dev/null +++ b/firmware/include/buflib.h | |||
@@ -0,0 +1,319 @@ | |||
1 | /*************************************************************************** | ||
2 | * __________ __ ___. | ||
3 | * Open \______ \ ____ ____ | | _\_ |__ _______ ___ | ||
4 | * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ / | ||
5 | * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < < | ||
6 | * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \ | ||
7 | * \/ \/ \/ \/ \/ | ||
8 | * $Id$ | ||
9 | * | ||
10 | * This is a memory allocator designed to provide reasonable management of free | ||
11 | * space and fast access to allocated data. More than one allocator can be used | ||
12 | * at a time by initializing multiple contexts. | ||
13 | * | ||
14 | * Copyright (C) 2009 Andrew Mahone | ||
15 | * Copyright (C) 2011 Thomas Martitz | ||
16 | * | ||
17 | * This program is free software; you can redistribute it and/or | ||
18 | * modify it under the terms of the GNU General Public License | ||
19 | * as published by the Free Software Foundation; either version 2 | ||
20 | * of the License, or (at your option) any later version. | ||
21 | * | ||
22 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY | ||
23 | * KIND, either express or implied. | ||
24 | * | ||
25 | ****************************************************************************/ | ||
26 | |||
27 | #ifndef _BUFLIB_H_ | ||
28 | #define _BUFLIB_H_ | ||
29 | #include <stdint.h> | ||
30 | #include <stdbool.h> | ||
31 | #include <string.h> | ||
32 | |||
33 | /* enable single block debugging */ | ||
34 | #define BUFLIB_DEBUG_BLOCK_SINGLE | ||
35 | |||
36 | union buflib_data | ||
37 | { | ||
38 | intptr_t val; | ||
39 | char name[1]; /* actually a variable sized string */ | ||
40 | struct buflib_callbacks* ops; | ||
41 | char* alloc; | ||
42 | union buflib_data *handle; | ||
43 | }; | ||
44 | |||
45 | struct buflib_context | ||
46 | { | ||
47 | union buflib_data *handle_table; | ||
48 | union buflib_data *first_free_handle; | ||
49 | union buflib_data *last_handle; | ||
50 | union buflib_data *first_free_block; | ||
51 | union buflib_data *buf_start; | ||
52 | union buflib_data *alloc_end; | ||
53 | bool compact; | ||
54 | }; | ||
55 | |||
56 | /** | ||
57 | * Callbacks used by the buflib to inform allocation that compaction | ||
58 | * is happening (before data is moved) | ||
59 | * | ||
60 | * Note that buflib tries to move to satisfy new allocations before shrinking. | ||
61 | * So if you have something to resize try to do it outside of the callback. | ||
62 | * | ||
63 | * Regardless of the above, if the allocation is SHRINKABLE, but not | ||
64 | * MUST_NOT_MOVE buflib will move the allocation before even attempting to | ||
65 | * shrink. | ||
66 | */ | ||
67 | struct buflib_callbacks { | ||
68 | /** | ||
69 | * This is called before data is moved. Use this to fix up any cached | ||
70 | * pointers pointing to inside the allocation. The size is unchanged. | ||
71 | * | ||
72 | * This is not needed if you don't cache the data pointer (but always | ||
73 | * call buflib_get_data()) and don't pass pointer to the data to yielding | ||
74 | * functions. | ||
75 | * | ||
76 | * handle: The corresponding handle | ||
77 | * current: The current start of the allocation | ||
78 | * new: The new start of the allocation, after data movement | ||
79 | * | ||
80 | * Return: Return BUFLIB_CB_OK, or BUFLIB_CB_CANNOT_MOVE if movement | ||
81 | * is impossible at this moment. | ||
82 | * | ||
83 | * If NULL: this allocation must not be moved around by the buflib when | ||
84 | * compation occurs | ||
85 | */ | ||
86 | int (*move_callback)(int handle, void* current, void* new); | ||
87 | /** | ||
88 | * This is called when the buflib desires to shrink a buffer | ||
89 | * in order to satisfy new allocation. This happens when buflib runs | ||
90 | * out of memory, e.g. because buflib_alloc_maximum() was called. | ||
91 | * Move data around as you need to make space and call core_shrink() as | ||
92 | * appropriate from within the callback to complete the shrink operation. | ||
93 | * buflib will not move data as part of shrinking. | ||
94 | * | ||
95 | * hint: bit mask containing hints on how shrinking is desired (see below) | ||
96 | * handle: The corresponding handle | ||
97 | * start: The old start of the allocation | ||
98 | * | ||
99 | * Return: Return BUFLIB_CB_OK, or BUFLIB_CB_CANNOT_SHRINK if shirinking | ||
100 | * is impossible at this moment. | ||
101 | * | ||
102 | * if NULL: this allocation cannot be resized. | ||
103 | * It is recommended that allocation that must not move are | ||
104 | * at least shrinkable | ||
105 | */ | ||
106 | int (*shrink_callback)(int handle, unsigned hints, void* start, size_t old_size); | ||
107 | }; | ||
108 | |||
109 | #define BUFLIB_SHRINK_POS_MASK ((1<<0|1<<1)<<30) | ||
110 | #define BUFLIB_SHRINK_SIZE_MASK (~BUFLIB_SHRINK_POS_MASK) | ||
111 | #define BUFLIB_SHRINK_POS_FRONT (1u<<31) | ||
112 | #define BUFLIB_SHRINK_POS_BACK (1u<<30) | ||
113 | |||
114 | /** | ||
115 | * Possible return values for the callbacks, some of them can cause | ||
116 | * compaction to fail and therefore new allocations to fail | ||
117 | */ | ||
118 | /* Everything alright */ | ||
119 | #define BUFLIB_CB_OK 0 | ||
120 | /* Tell buflib that moving failed. Buflib may retry to move at any point */ | ||
121 | #define BUFLIB_CB_CANNOT_MOVE 1 | ||
122 | /* Tell buflib that resizing failed, possibly future making allocations fail */ | ||
123 | #define BUFLIB_CB_CANNOT_SHRINK 1 | ||
124 | |||
125 | /** | ||
126 | * Initializes buflib with a caller allocated context instance and memory pool. | ||
127 | * | ||
128 | * The buflib_context instance needs to be passed to every other buflib | ||
129 | * function. It's should be considered opaque, even though it is not yet | ||
130 | * (that's to make inlining core_get_data() possible). The documentation | ||
131 | * of the other functions will not describe the context | ||
132 | * instance paramter further as it's obligatory. | ||
133 | * | ||
134 | * context: The new buflib instance to be initialized, allocated by the caller | ||
135 | * size: The size of the memory pool | ||
136 | */ | ||
137 | void buflib_init(struct buflib_context *context, void *buf, size_t size); | ||
138 | |||
139 | |||
140 | /** | ||
141 | * Returns how many bytes left the buflib has to satisfy allocations. | ||
142 | * | ||
143 | * This function does not yet consider possible compaction so there might | ||
144 | * be more space left. This may change in the future. | ||
145 | * | ||
146 | * Returns: The number of bytes left in the memory pool. | ||
147 | */ | ||
148 | size_t buflib_available(struct buflib_context *ctx); | ||
149 | |||
150 | |||
151 | /** | ||
152 | * Allocates memory from buflib's memory pool | ||
153 | * | ||
154 | * size: How many bytes to allocate | ||
155 | * | ||
156 | * Returns: An integer handle identifying this allocation | ||
157 | */ | ||
158 | int buflib_alloc(struct buflib_context *context, size_t size); | ||
159 | |||
160 | |||
161 | /** | ||
162 | * Allocates memory from the buflib's memory pool with additional callbacks | ||
163 | * and flags | ||
164 | * | ||
165 | * name: A string identifier giving this allocation a name | ||
166 | * size: How many bytes to allocate | ||
167 | * ops: a struct with pointers to callback functions (see above) | ||
168 | * | ||
169 | * Returns: An integer handle identifying this allocation | ||
170 | */ | ||
171 | int buflib_alloc_ex(struct buflib_context *ctx, size_t size, const char *name, | ||
172 | struct buflib_callbacks *ops); | ||
173 | |||
174 | |||
175 | /** | ||
176 | * Gets all available memory from buflib, for temporary use. | ||
177 | * | ||
178 | * Since this effectively makes all future allocations fail (unless | ||
179 | * another allocation is freed in the meantime), you should definitely provide | ||
180 | * a shrink callback if you plan to hold the buffer for a longer period. This | ||
181 | * will allow buflib to permit allocations by shrinking the buffer returned by | ||
182 | * this function. | ||
183 | * | ||
184 | * Note that this currently gives whatever buflib_available() returns. However, | ||
185 | * do not depend on this behavior, it may change. | ||
186 | * | ||
187 | * name: A string identifier giving this allocation a name | ||
188 | * size: The actual size will be returned into size | ||
189 | * ops: a struct with pointers to callback functions | ||
190 | * | ||
191 | * Returns: An integer handle identifying this allocation | ||
192 | */ | ||
193 | int buflib_alloc_maximum(struct buflib_context* ctx, const char* name, | ||
194 | size_t *size, struct buflib_callbacks *ops); | ||
195 | |||
196 | /** | ||
197 | * Queries the data pointer for the given handle. It's actually a cheap | ||
198 | * operation, don't hesitate using it extensivly. | ||
199 | * | ||
200 | * Notice that you need to re-query after every direct or indirect yield(), | ||
201 | * because compaction can happen by other threads which may get your data | ||
202 | * moved around (or you can get notified about changes by callbacks, | ||
203 | * see further above). | ||
204 | * | ||
205 | * handle: The handle corresponding to the allocation | ||
206 | * | ||
207 | * Returns: The start pointer of the allocation | ||
208 | */ | ||
209 | static inline void* buflib_get_data(struct buflib_context *context, int handle) | ||
210 | { | ||
211 | return (void*)(context->handle_table[-handle].alloc); | ||
212 | } | ||
213 | |||
214 | /** | ||
215 | * Shrink the memory allocation associated with the given handle | ||
216 | * Mainly intended to be used with the shrink callback, but it can also | ||
217 | * be called outside as well, e.g. to give back buffer space allocated | ||
218 | * with buflib_alloc_maximum(). | ||
219 | * | ||
220 | * Note that you must move/copy data around yourself before calling this, | ||
221 | * buflib will not do this as part of shrinking. | ||
222 | * | ||
223 | * handle: The handle identifying this allocation | ||
224 | * new_start: the new start of the allocation | ||
225 | * new_size: the new size of the allocation | ||
226 | * | ||
227 | * Returns: true if shrinking was successful. Otherwise it returns false, | ||
228 | * without having modified memory. | ||
229 | * | ||
230 | */ | ||
231 | bool buflib_shrink(struct buflib_context *ctx, int handle, void* newstart, size_t new_size); | ||
232 | |||
233 | /** | ||
234 | * Frees memory associated with the given handle | ||
235 | * | ||
236 | * Returns: 0 (to invalidate handles in one line) | ||
237 | */ | ||
238 | int buflib_free(struct buflib_context *context, int handle); | ||
239 | |||
240 | /** | ||
241 | * Moves the underlying buflib buffer up by size bytes (as much as | ||
242 | * possible for size == 0) without moving the end. This effectively | ||
243 | * reduces the available space by taking away managable space from the | ||
244 | * front. This space is not available for new allocations anymore. | ||
245 | * | ||
246 | * To make space available in the front, everything is moved up. | ||
247 | * It does _NOT_ call the move callbacks | ||
248 | * | ||
249 | * | ||
250 | * size: size in bytes to move the buffer up (take away). The actual | ||
251 | * bytes moved is returned in this | ||
252 | * Returns: The new start of the underlying buflib buffer | ||
253 | */ | ||
254 | void* buflib_buffer_out(struct buflib_context *ctx, size_t *size); | ||
255 | |||
256 | /** | ||
257 | * Moves the underlying buflib buffer down by size bytes without | ||
258 | * moving the end. This grows the buflib buffer by adding space to the front. | ||
259 | * The new bytes are available for new allocations. | ||
260 | * | ||
261 | * Everything is moved down, and the new free space will be in the middle. | ||
262 | * It does _NOT_ call the move callbacks. | ||
263 | * | ||
264 | * size: size in bytes to move the buffer down (new free space) | ||
265 | */ | ||
266 | void buflib_buffer_in(struct buflib_context *ctx, int size); | ||
267 | |||
268 | /* debugging */ | ||
269 | |||
270 | /** | ||
271 | * Returns the name, as given to core_alloc() and core_allloc_ex(), of the | ||
272 | * allocation associated with the given handle | ||
273 | * | ||
274 | * handle: The handle indicating the allocation | ||
275 | * | ||
276 | * Returns: A pointer to the string identifier of the allocation | ||
277 | */ | ||
278 | const char* buflib_get_name(struct buflib_context *ctx, int handle); | ||
279 | |||
280 | /** | ||
281 | * Prints an overview of all current allocations with the help | ||
282 | * of the passed printer helper | ||
283 | * | ||
284 | * This walks only the handle table and prints only valid allocations | ||
285 | * | ||
286 | * Only available if BUFLIB_DEBUG_BLOCKS is defined | ||
287 | */ | ||
288 | void buflib_print_allocs(struct buflib_context *ctx, void (*print)(int, const char*)); | ||
289 | |||
290 | /** | ||
291 | * Prints an overview of all blocks in the buflib buffer, allocated | ||
292 | * or unallocated, with the help pf the passted printer helper | ||
293 | * | ||
294 | * This walks the entire buffer and prints unallocated space also. | ||
295 | * The output is also different from buflib_print_allocs(). | ||
296 | * | ||
297 | * Only available if BUFLIB_DEBUG_BLOCKS is defined | ||
298 | */ | ||
299 | void buflib_print_blocks(struct buflib_context *ctx, void (*print)(int, const char*)); | ||
300 | |||
301 | /** | ||
302 | * Gets the number of blocks in the entire buffer, allocated or unallocated | ||
303 | * | ||
304 | * Only available if BUFLIB_DEBUG_BLOCK_SIGNLE is defined | ||
305 | */ | ||
306 | int buflib_get_num_blocks(struct buflib_context *ctx); | ||
307 | |||
308 | /** | ||
309 | * Print information about a single block as indicated by block_num | ||
310 | * into buf | ||
311 | * | ||
312 | * buflib_get_num_blocks() beforehand to get the total number of blocks, | ||
313 | * as passing an block_num higher than that is undefined | ||
314 | * | ||
315 | * Only available if BUFLIB_DEBUG_BLOCK_SIGNLE is defined | ||
316 | */ | ||
317 | void buflib_print_block_at(struct buflib_context *ctx, int block_num, | ||
318 | char* buf, size_t bufsize); | ||
319 | #endif | ||