summaryrefslogtreecommitdiffstats
path: root/firmware/buflib.c
diff options
context:
space:
mode:
authorThomas Martitz <kugel@rockbox.org>2011-09-09 15:35:14 +0000
committerThomas Martitz <kugel@rockbox.org>2011-09-09 15:35:14 +0000
commitf7cff8bd69adf6f6345fc1d7742f62d5a919ecde (patch)
treef02905ff8d40cf2eef2f15fafba5f3e20d7ed6d1 /firmware/buflib.c
parent0dcbc6cd5d4d40b37f7dbc38a944bfe28901f6e0 (diff)
downloadrockbox-f7cff8bd69adf6f6345fc1d7742f62d5a919ecde.tar.gz
rockbox-f7cff8bd69adf6f6345fc1d7742f62d5a919ecde.tar.bz2
rockbox-f7cff8bd69adf6f6345fc1d7742f62d5a919ecde.zip
Buflib: Stop caching the first unallocated block. It has little benefit but is complicated to keep up-to-date.
git-svn-id: svn://svn.rockbox.org/rockbox/trunk@30487 a1c6a512-1295-4272-9138-f99709370657
Diffstat (limited to 'firmware/buflib.c')
-rw-r--r--firmware/buflib.c85
1 files changed, 42 insertions, 43 deletions
diff --git a/firmware/buflib.c b/firmware/buflib.c
index ac8cdc864c..0dfbdf6f49 100644
--- a/firmware/buflib.c
+++ b/firmware/buflib.c
@@ -89,9 +89,10 @@
#define BDEBUGF(...) do { } while(0)
#endif
-static union buflib_data*
-find_block_before(struct buflib_context *ctx, union buflib_data* block,
- bool is_free);
+static union buflib_data* find_first_free(struct buflib_context *ctx);
+static union buflib_data* find_block_before(struct buflib_context *ctx,
+ union buflib_data* block,
+ bool is_free);
/* Initialize buffer manager */
void
buflib_init(struct buflib_context *ctx, void *buf, size_t size)
@@ -105,7 +106,6 @@ buflib_init(struct buflib_context *ctx, void *buf, size_t size)
ctx->handle_table = bd_buf + size;
ctx->last_handle = bd_buf + size;
ctx->first_free_handle = bd_buf + size - 1;
- ctx->first_free_block = bd_buf;
ctx->buf_start = bd_buf;
/* A marker is needed for the end of allocated data, to make sure that it
* does not collide with the handle table, and to detect end-of-buffer.
@@ -226,11 +226,12 @@ static bool
buflib_compact(struct buflib_context *ctx)
{
BDEBUGF("%s(): Compacting!\n", __func__);
- union buflib_data *block;
+ union buflib_data *block,
+ *first_free = find_first_free(ctx);
int shift = 0, len;
/* Store the results of attempting to shrink the handle table */
bool ret = handle_table_shrink(ctx);
- for(block = ctx->first_free_block; block < ctx->alloc_end; block += len)
+ for(block = first_free; block < ctx->alloc_end; block += len)
{
len = block->val;
/* This block is free, add its length to the shift value */
@@ -241,41 +242,41 @@ buflib_compact(struct buflib_context *ctx)
continue;
}
/* attempt to fill any hole */
- if (-ctx->first_free_block->val > block->val)
+ if (-first_free->val >= block->val)
{
- intptr_t size = ctx->first_free_block->val;
+ intptr_t size = -first_free->val;
union buflib_data* next_block = block + block->val;
- if (move_block(ctx, block, ctx->first_free_block - block))
+ if (move_block(ctx, block, first_free - block))
{
- /* moving was successful. Mark the next block as the new
- * first_free_block and merge it with the free space
- * that the move created */
+ /* moving was successful. Move alloc_end down if necessary */
if (ctx->alloc_end == next_block)
ctx->alloc_end = block;
- ctx->first_free_block += block->val;
- ctx->first_free_block->val = size + block->val;
+ /* Mark the block behind the just moved as free
+ * be careful to not overwrite an existing block */
+ if (size != block->val)
+ {
+ first_free += block->val;
+ first_free->val = block->val - size; /* negative */
+ }
continue;
}
}
/* attempt move the allocation by shift */
if (shift)
{
- /* failing to move creates a hole, therefore mark this
- * block as not allocated anymore and move first_free_block up */
+ /* failing to move creates a hole,
+ * therefore mark this block as not allocated */
+ union buflib_data* target_block = block + shift;
if (!move_block(ctx, block, shift))
{
- union buflib_data* hole = block + shift;
- hole->val = shift;
- if (ctx->first_free_block > hole)
- ctx->first_free_block = hole;
+ target_block->val = shift; /* this is a hole */
shift = 0;
}
- /* if move was successful, the just moved block is now
- * possibly in place of the first free one, so move this thing up */
- else if (ctx->first_free_block == block+shift)
- {
- ctx->first_free_block += ctx->first_free_block->val;
- ctx->first_free_block->val = shift;
+ else
+ { /* need to update the next free block, since the above hole
+ * handling might make shift 0 before alloc_end is reached */
+ union buflib_data* new_free = target_block + target_block->val;
+ new_free->val = shift;
}
}
}
@@ -283,9 +284,6 @@ buflib_compact(struct buflib_context *ctx)
* been freed.
*/
ctx->alloc_end += shift;
- /* only move first_free_block up if it wasn't already by a hole */
- if (ctx->first_free_block > ctx->alloc_end)
- ctx->first_free_block = ctx->alloc_end;
ctx->compact = true;
return ret || shift;
}
@@ -345,7 +343,6 @@ buflib_buffer_shift(struct buflib_context *ctx, int shift)
for (handle = ctx->last_handle; handle < ctx->handle_table; handle++)
if (handle->alloc)
handle->alloc += shift;
- ctx->first_free_block += shift;
ctx->buf_start += shift;
ctx->alloc_end += shift;
}
@@ -443,7 +440,7 @@ buffer_alloc:
/* need to re-evaluate last before the loop because the last allocation
* possibly made room in its front to fit this, so last would be wrong */
last = false;
- for (block = ctx->first_free_block;;block += block_len)
+ for (block = find_first_free(ctx);;block += block_len)
{
/* If the last used block extends all the way to the handle table, the
* block "after" it doesn't have a header. Because of this, it's easier
@@ -499,8 +496,6 @@ buffer_alloc:
/* If we have just taken the first free block, the next allocation search
* can save some time by starting after this block.
*/
- if (block == ctx->first_free_block)
- ctx->first_free_block += size;
block += size;
/* alloc_end must be kept current if we're taking the last block. */
if (last)
@@ -512,6 +507,20 @@ buffer_alloc:
return ctx->handle_table - handle;
}
+static union buflib_data*
+find_first_free(struct buflib_context *ctx)
+{
+ union buflib_data* ret = ctx->buf_start;
+ while(ret < ctx->alloc_end)
+ {
+ if (ret->val < 0)
+ break;
+ ret += ret->val;
+ }
+ /* ret is now either a free block or the same as alloc_end, both is fine */
+ return ret;
+}
+
/* Finds the free block before block, and returns NULL if it's not free */
static union buflib_data*
find_block_before(struct buflib_context *ctx, union buflib_data* block,
@@ -577,11 +586,6 @@ buflib_free(struct buflib_context *ctx, int handle_num)
}
handle_free(ctx, handle);
handle->alloc = NULL;
- /* If this block is before first_free_block, it becomes the new starting
- * point for free-block search.
- */
- if (block < ctx->first_free_block)
- ctx->first_free_block = block;
return 0; /* unconditionally */
}
@@ -668,8 +672,6 @@ buflib_shrink(struct buflib_context* ctx, int handle, void* new_start, size_t ne
union buflib_data *free_before = find_block_before(ctx, block, true);
if (free_before)
free_before->val += block->val;
- else if (ctx->first_free_block > block)
- ctx->first_free_block = block;
/* We didn't handle size changes yet, assign block to the new one
* the code below the wants block whether it changed or not */
@@ -690,9 +692,6 @@ buflib_shrink(struct buflib_context* ctx, int handle, void* new_start, size_t ne
/* must be negative to indicate being unallocated */
new_next_block->val = new_next_block - old_next_block;
}
- /* update first_free_block for the newly created free space */
- if (ctx->first_free_block > new_next_block)
- ctx->first_free_block = new_next_block;
}
return true;