2 Copyright (c) 2009 Joseph A. Adams
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions
8 1. Redistributions of source code must retain the above copyright
9 notice, this list of conditions and the following disclaimer.
10 2. Redistributions in binary form must reproduce the above copyright
11 notice, this list of conditions and the following disclaimer in the
12 documentation and/or other materials provided with the distribution.
13 3. The name of the author may not be used to endorse or promote products
14 derived from this software without specific prior written permission.
16 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19 IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 #include "block_pool.h"
33 //must be a power of 2
34 #define BLOCK_SIZE 4096
44 size_t alloc; //2^n - 1, where n is an integer > 1
47 //blocks are arranged in a max-heap by the .remaining field
48 // (except the root block does not percolate down until it is filled)
51 static int destructor(struct block_pool *bp) {
52 struct block *block = bp->block;
62 struct block_pool *block_pool_new(void *ctx) {
63 struct block_pool *bp = talloc(ctx, struct block_pool);
64 talloc_set_destructor(bp, destructor);
68 bp->block = malloc(bp->alloc * sizeof(struct block));
73 static void *new_block(struct block *b, size_t needed) {
74 b->size = (needed+(BLOCK_SIZE-1)) & ~(BLOCK_SIZE-1);
75 b->remaining = b->size - needed;
76 b->data = malloc(b->size);
80 //for the first block, keep the memory usage low in case it's the only block.
81 static void *new_block_tiny(struct block *b, size_t needed) {
85 b->size = (needed+(BLOCK_SIZE-1)) & ~(BLOCK_SIZE-1);
86 b->remaining = b->size - needed;
87 b->data = malloc(b->size);
91 static void *try_block(struct block *b, size_t size, size_t align) {
92 size_t offset = b->size - b->remaining;
93 offset = (offset+align) & ~align;
95 if (b->size-offset >= size) {
96 //good, we can use this block
97 void *ret = b->data + offset;
98 b->remaining = b->size-offset-size;
106 #define L(node) (node+node+1)
107 #define R(node) (node+node+2)
108 #define P(node) ((node-1)>>1)
110 #define V(node) (bp->block[node].remaining)
112 static void percolate_down(struct block_pool *bp, size_t node) {
113 size_t child = L(node);
116 //get the maximum child
117 if (child >= bp->count)
119 if (child+1 < bp->count && V(child+1) > V(child))
122 if (V(child) <= V(node))
125 tmp = bp->block[node];
126 bp->block[node] = bp->block[child];
127 bp->block[child] = tmp;
129 percolate_down(bp, child);
132 //note: percolates up to either 1 or 2 as a root
133 static void percolate_up(struct block_pool *bp, size_t node) {
134 size_t parent = P(node);
137 if (node<3 || V(parent) >= V(node))
140 tmp = bp->block[node];
141 bp->block[node] = bp->block[parent];
142 bp->block[parent] = tmp;
144 percolate_up(bp, parent);
147 void *block_pool_alloc_align(struct block_pool *bp, size_t size, size_t align) {
153 //if there aren't any blocks, make a new one
156 return new_block_tiny(bp->block, size);
160 ret = try_block(bp->block, size, align);
164 //root block is filled, percolate down and try the biggest one
165 percolate_down(bp, 0);
166 ret = try_block(bp->block, size, align);
170 //the biggest wasn't big enough; we need a new block
171 if (bp->count >= bp->alloc) {
172 //make room for another block
173 bp->alloc += bp->alloc;
175 bp->block = realloc(bp->block, bp->alloc * sizeof(struct block));
177 ret = new_block(bp->block+(bp->count++), size);
179 //fix the heap after adding the new block
180 percolate_up(bp, bp->count-1);
190 char *block_pool_strdup(struct block_pool *bp, const char *str) {
191 size_t size = strlen(str)+1;
192 char *ret = block_pool_alloc_align(bp, size, 1);
194 memcpy(ret, str, size);