2 * Copyright (C) 2009 Joseph Adams <joeyadams3.14159@gmail.com>
4 * Permission is hereby granted, free of charge, to any person obtaining a copy
5 * of this software and associated documentation files (the "Software"), to deal
6 * in the Software without restriction, including without limitation the rights
7 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 * copies of the Software, and to permit persons to whom the Software is
9 * furnished to do so, subject to the following conditions:
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
23 #include "block_pool.h"
28 //must be a power of 2
29 #define BLOCK_SIZE 4096
39 size_t alloc; //2^n - 1, where n is an integer > 1
42 //blocks are arranged in a max-heap by the .remaining field
43 // (except the root block does not percolate down until it is filled)
46 static int destructor(struct block_pool *bp) {
47 struct block *block = bp->block;
57 struct block_pool *block_pool_new(void *ctx) {
58 struct block_pool *bp = talloc(ctx, struct block_pool);
59 talloc_set_destructor(bp, destructor);
63 bp->block = malloc(bp->alloc * sizeof(struct block));
68 static void *new_block(struct block *b, size_t needed) {
69 b->size = (needed+(BLOCK_SIZE-1)) & ~(BLOCK_SIZE-1);
70 b->remaining = b->size - needed;
71 b->data = malloc(b->size);
75 //for the first block, keep the memory usage low in case it's the only block.
76 static void *new_block_tiny(struct block *b, size_t needed) {
80 b->size = (needed+(BLOCK_SIZE-1)) & ~(BLOCK_SIZE-1);
81 b->remaining = b->size - needed;
82 b->data = malloc(b->size);
86 static void *try_block(struct block *b, size_t size, size_t align) {
87 size_t offset = b->size - b->remaining;
88 offset = (offset+align) & ~align;
90 if (b->size-offset >= size) {
91 //good, we can use this block
92 void *ret = b->data + offset;
93 b->remaining = b->size-offset-size;
101 #define L(node) (node+node+1)
102 #define R(node) (node+node+2)
103 #define P(node) ((node-1)>>1)
105 #define V(node) (bp->block[node].remaining)
107 static void percolate_down(struct block_pool *bp, size_t node) {
108 size_t child = L(node);
111 //get the maximum child
112 if (child >= bp->count)
114 if (child+1 < bp->count && V(child+1) > V(child))
117 if (V(child) <= V(node))
120 tmp = bp->block[node];
121 bp->block[node] = bp->block[child];
122 bp->block[child] = tmp;
124 percolate_down(bp, child);
127 //note: percolates up to either 1 or 2 as a root
128 static void percolate_up(struct block_pool *bp, size_t node) {
129 size_t parent = P(node);
132 if (node<3 || V(parent) >= V(node))
135 tmp = bp->block[node];
136 bp->block[node] = bp->block[parent];
137 bp->block[parent] = tmp;
139 percolate_up(bp, parent);
142 void *block_pool_alloc_align(struct block_pool *bp, size_t size, size_t align) {
148 //if there aren't any blocks, make a new one
151 return new_block_tiny(bp->block, size);
155 ret = try_block(bp->block, size, align);
159 //root block is filled, percolate down and try the biggest one
160 percolate_down(bp, 0);
161 ret = try_block(bp->block, size, align);
165 //the biggest wasn't big enough; we need a new block
166 if (bp->count >= bp->alloc) {
167 //make room for another block
168 bp->alloc += bp->alloc;
170 bp->block = realloc(bp->block, bp->alloc * sizeof(struct block));
172 ret = new_block(bp->block+(bp->count++), size);
174 //fix the heap after adding the new block
175 percolate_up(bp, bp->count-1);
185 char *block_pool_strdup(struct block_pool *bp, const char *str) {
186 size_t size = strlen(str)+1;
187 char *ret = block_pool_alloc_align(bp, size, 1);
189 memcpy(ret, str, size);