Use -O not -O3: reduces ccan/tdb test time from 24 to 18 seconds.
[ccan] / ccan / block_pool / block_pool.c
1 /*
2         Copyright (c) 2009  Joseph A. Adams
3         All rights reserved.
4         
5         Redistribution and use in source and binary forms, with or without
6         modification, are permitted provided that the following conditions
7         are met:
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.
15         
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.
26 */
27
28 #include "block_pool.h"
29 #include <stdlib.h>
30 #include <stdio.h>
31 #include <string.h>
32
33 //must be a power of 2
34 #define BLOCK_SIZE 4096
35
36 struct block {
37         size_t remaining;
38         size_t size;
39         char *data;
40 };
41
42 struct block_pool {
43         size_t count;
44         size_t alloc; //2^n - 1, where n is an integer > 1
45         struct block *block;
46         
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)
49 };
50
51 static int destructor(struct block_pool *bp) {
52         struct block *block = bp->block;
53         size_t d = bp->count;
54         
55         for (;d--;block++)
56                 free(block->data);
57         free(bp->block);
58         
59         return 0;
60 }
61
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);
65         
66         bp->count = 0;
67         bp->alloc = 7;
68         bp->block = malloc(bp->alloc * sizeof(struct block));
69         
70         return bp;
71 }
72
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);
77         return b->data;
78 }
79
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) {
82         if (needed < 256)
83                 b->size = 256;
84         else
85                 b->size = (needed+(BLOCK_SIZE-1)) & ~(BLOCK_SIZE-1);
86         b->remaining = b->size - needed;
87         b->data = malloc(b->size);
88         return b->data;
89 }
90
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;
94         
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;
99                 
100                 return ret;
101         }
102         
103         return NULL;
104 }
105
106 #define L(node) (node+node+1)
107 #define R(node) (node+node+2)
108 #define P(node) ((node-1)>>1)
109
110 #define V(node) (bp->block[node].remaining)
111
112 static void percolate_down(struct block_pool *bp, size_t node) {
113         size_t child = L(node);
114         struct block tmp;
115         
116         //get the maximum child
117         if (child >= bp->count)
118                 return;
119         if (child+1 < bp->count && V(child+1) > V(child))
120                 child++;
121         
122         if (V(child) <= V(node))
123                 return;
124         
125         tmp = bp->block[node];
126         bp->block[node] = bp->block[child];
127         bp->block[child] = tmp;
128         
129         percolate_down(bp, child);
130 }
131
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);
135         struct block tmp;
136         
137         if (node<3 || V(parent) >= V(node))
138                 return;
139         
140         tmp = bp->block[node];
141         bp->block[node] = bp->block[parent];
142         bp->block[parent] = tmp;
143         
144         percolate_up(bp, parent);
145 }
146
147 void *block_pool_alloc_align(struct block_pool *bp, size_t size, size_t align) {
148         void *ret;
149         
150         if (align)
151                 align--;
152         
153         //if there aren't any blocks, make a new one
154         if (!bp->count) {
155                 bp->count = 1;
156                 return new_block_tiny(bp->block, size);
157         }
158         
159         //try the root block
160         ret = try_block(bp->block, size, align);
161         if (ret)
162                 return ret;
163         
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);
167         if (ret)
168                 return ret;
169         
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;
174                 bp->alloc++;
175                 bp->block = realloc(bp->block, bp->alloc * sizeof(struct block));
176         }
177         ret = new_block(bp->block+(bp->count++), size);
178         
179         //fix the heap after adding the new block
180         percolate_up(bp, bp->count-1);
181         
182         return ret;
183 }
184
185 #undef L
186 #undef R
187 #undef P
188 #undef V
189
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);
193         
194         memcpy(ret, str, size);
195         return ret;
196 }