tdb2: don't cancel transactions on lock failures in tdb1 backend.
[ccan] / ccan / block_pool / block_pool.c
1 /*
2  * Copyright (C) 2009 Joseph Adams <joeyadams3.14159@gmail.com>
3  *
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:
10  *
11  * The above copyright notice and this permission notice shall be included in
12  * all copies or substantial portions of the Software.
13  *
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
20  * THE SOFTWARE.
21  */
22
23 #include "block_pool.h"
24 #include <stdlib.h>
25 #include <stdio.h>
26 #include <string.h>
27
28 //must be a power of 2
29 #define BLOCK_SIZE 4096
30
31 struct block {
32         size_t remaining;
33         size_t size;
34         char *data;
35 };
36
37 struct block_pool {
38         size_t count;
39         size_t alloc; //2^n - 1, where n is an integer > 1
40         struct block *block;
41         
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)
44 };
45
46 static int destructor(struct block_pool *bp) {
47         struct block *block = bp->block;
48         size_t d = bp->count;
49         
50         for (;d--;block++)
51                 free(block->data);
52         free(bp->block);
53         
54         return 0;
55 }
56
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);
60         
61         bp->count = 0;
62         bp->alloc = 7;
63         bp->block = malloc(bp->alloc * sizeof(struct block));
64         
65         return bp;
66 }
67
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);
72         return b->data;
73 }
74
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) {
77         if (needed < 256)
78                 b->size = 256;
79         else
80                 b->size = (needed+(BLOCK_SIZE-1)) & ~(BLOCK_SIZE-1);
81         b->remaining = b->size - needed;
82         b->data = malloc(b->size);
83         return b->data;
84 }
85
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;
89         
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;
94                 
95                 return ret;
96         }
97         
98         return NULL;
99 }
100
101 #define L(node) (node+node+1)
102 #define R(node) (node+node+2)
103 #define P(node) ((node-1)>>1)
104
105 #define V(node) (bp->block[node].remaining)
106
107 static void percolate_down(struct block_pool *bp, size_t node) {
108         size_t child = L(node);
109         struct block tmp;
110         
111         //get the maximum child
112         if (child >= bp->count)
113                 return;
114         if (child+1 < bp->count && V(child+1) > V(child))
115                 child++;
116         
117         if (V(child) <= V(node))
118                 return;
119         
120         tmp = bp->block[node];
121         bp->block[node] = bp->block[child];
122         bp->block[child] = tmp;
123         
124         percolate_down(bp, child);
125 }
126
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);
130         struct block tmp;
131         
132         if (node<3 || V(parent) >= V(node))
133                 return;
134         
135         tmp = bp->block[node];
136         bp->block[node] = bp->block[parent];
137         bp->block[parent] = tmp;
138         
139         percolate_up(bp, parent);
140 }
141
142 void *block_pool_alloc_align(struct block_pool *bp, size_t size, size_t align) {
143         void *ret;
144         
145         if (align)
146                 align--;
147         
148         //if there aren't any blocks, make a new one
149         if (!bp->count) {
150                 bp->count = 1;
151                 return new_block_tiny(bp->block, size);
152         }
153         
154         //try the root block
155         ret = try_block(bp->block, size, align);
156         if (ret)
157                 return ret;
158         
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);
162         if (ret)
163                 return ret;
164         
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;
169                 bp->alloc++;
170                 bp->block = realloc(bp->block, bp->alloc * sizeof(struct block));
171         }
172         ret = new_block(bp->block+(bp->count++), size);
173         
174         //fix the heap after adding the new block
175         percolate_up(bp, bp->count-1);
176         
177         return ret;
178 }
179
180 #undef L
181 #undef R
182 #undef P
183 #undef V
184
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);
188         
189         memcpy(ret, str, size);
190         return ret;
191 }