git.ozlabs.org Git - ccan/blob - 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 }