block_pool.c

   1 #include <assert.h>
   2 #include <stdio.h> // temporary
   3 #include <stdlib.h>
   4 #include <string.h>
   5 #include "block_pool.h"
   6 #include "rassert.h"
   7
   8 static uint8_t masks[8] = {0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80};
   9 static uint8_t bits[8] = {1, 2, 4, 8, 0x10, 0x20, 0x40, 0x80};
  10
  11 void block_pool_init(struct block_pool *block_pool, int n_blocks) {
  12   block_pool->n_blocks = n_blocks;
  13   block_pool->n_bitmap = (n_blocks + 7) >> 3;
  14   block_pool->bitmap = malloc(block_pool->n_bitmap);
  15   rassert(block_pool->bitmap);
  16   memset(block_pool->bitmap, 0xff, block_pool->n_bitmap);
  17   if (n_blocks & 7)
  18     block_pool->bitmap[n_blocks >> 3] =
  19       ~masks[n_blocks & 7];
  20   block_pool->next = 0;
  21   block_pool->avail = n_blocks;
  22 }
  23
  24 // note: size argument can be negative, indicates a no-op
  25 bool block_pool_alloc(struct block_pool *block_pool, int *table, int size) {
  26   int i, j, k;
  27   uint8_t c;
  28
  29   if (block_pool->avail < size)
  30     return false;
  31
  32   for (i = 0; i < size; ++i) {
  33     j = block_pool->next >> 3;
  34     c = block_pool->bitmap[j] & masks[block_pool->next & 7];
  35     goto loop_entry;
  36     for (; j < block_pool->n_bitmap; ++j) {
  37       c = block_pool->bitmap[j];
  38     loop_entry:
  39       if (c) goto found;
  40     }
  41 #if 1
  42     for (j = 0; ; ++j) {
  43       assert(j <= block_pool->next >> 3);
  44       c = block_pool->bitmap[j];
  45       if (c) goto found;
  46     }
  47 #else
  48     k = (block_pool->next >> 3) + 1;
  49     for (j = 0; j < k; ++j) {
  50       c = block_pool->bitmap[j];
  51       if (c) goto found;
  52     }
  53     core_block_free(table, i);
  54     return false;
  55 #endif
  56
  57   found:
  58     for (k = 0; (c & 1) == 0; ++k)
  59       c >>= 1;
  60     block_pool->bitmap[j] &= ~bits[k];
  61     block_pool->next = (j << 3) | k;
  62
  63 #ifndef NDEBUG // makes us remove the following line in gen.sh as appropriate
  64     assert(table[i] == 0x55555555);
  65 #endif
  66  //printf("block_pool %p table+i %p alloc %d\n", block_pool, table + i, block_pool->next);
  67     table[i] = block_pool->next++;
  68     if (block_pool->next >= block_pool->n_blocks)
  69       block_pool->next = 0;
  70   }
  71
  72   block_pool->avail -= i;
  73   return true;
  74 }
  75
  76 // note: size argument can be negative, indicates a no-op
  77 void block_pool_free(struct block_pool *block_pool, int *table, int size) {
  78   int i, j, k;
  79
  80   for (i = 0; i < size; ++i) {
  81     j = table[i];
  82  //printf("block_pool %p table+i %p free %d\n", block_pool, table + i, j);
  83     assert(j >= 0 && j < block_pool->n_blocks);
  84     k = j & 7;
  85     j >>= 3;
  86     assert((block_pool->bitmap[j] & bits[k]) == 0);
  87     block_pool->bitmap[j] |= bits[k];
  88 #ifndef NDEBUG
  89     table[i] = 0x55555555;
  90 #endif
  91   }
  92
  93   block_pool->avail += i;
  94 }