pool.c

   1 #include <assert.h>
   2 #include <stdarg.h>
   3 //#include <stdio.h> // temporary
   4 #include <stdlib.h>
   5 #include "pool.h"
   6
   7 #define MOVEABLE_POOL 1
   8 #ifdef MOVEABLE_POOL
   9 #define TRY_BLOCKER 1
  10 #endif
  11
  12 #ifndef NDEBUG
  13 void check_invariants(struct pool_head *head) {
  14   int avail;
  15   struct pool_item *p;
  16
  17   avail = head->item.base - head->item.limit;
  18   for (p = head->item.next; p != &head->item; p = p->next) {
  19     assert(p->prev->next == p && p->next->prev == p);
  20     assert(p->base >= p->prev->limit && p->limit <= p->next->base);
  21     avail += p->base - p->limit;
  22   }
  23   assert(avail == head->avail);
  24 }
  25 #endif
  26
  27 void pool_init(
  28   struct pool_head *head,
  29   int base,
  30   int limit,
  31   void (*move)(struct pool_item *item, int new_base),
  32   void (*move_up)(struct pool_item *item, int new_limit)
  33 ) {
  34   head->item.prev = &head->item;
  35   head->item.next = &head->item;
  36   head->item.base = limit; // note: swapped
  37   head->item.limit = base; // note: swapped
  38   head->avail = limit - base;
  39   head->move = move;
  40   head->move_up = move_up;
  41 #ifndef NDEBUG
  42  check_invariants(head);
  43 #endif
  44 }
  45
  46 bool pool_alloc(
  47   struct pool_head *head,
  48   struct pool_item *item,
  49   int size,
  50   int mode,
  51   ...
  52 ) {
  53   int size_change, gap;
  54   va_list ap;
  55   int new_base, new_limit, avail;
  56   bool dir;
  57   struct pool_item *p, *q;
  58 #ifdef TRY_BLOCKER
  59   struct pool_item *r, *target_item;
  60   int target_size;
  61 #endif
  62   int base_offset, limit_offset;
  63
  64   // check mode
  65   size_change = size;
  66   if (mode & POOL_ALLOC_MODE_REALLOC) {
  67     // realloc, item must be already allocated
  68     assert(item->prev && item->next);
  69     size_change += item->base - item->limit;
  70
  71     // calculate new spot if block is extended not moved
  72     va_start(ap, mode);
  73     new_base = item->base - va_arg(ap, int);
  74     va_end(ap);
  75     new_limit = new_base + size;
  76 #ifndef TRY_BLOCKER
  77     if (new_base >= item->prev->limit && new_limit <= item->next->base)
  78       goto resize;
  79 #endif
  80   }
  81 #ifndef NDEBUG
  82   else {
  83     // alloc, item must not be already allocated
  84     assert(item->prev == NULL && item->next == NULL);
  85   }
  86 #endif
  87
  88   // check size, disregarding fragmentation
  89   avail = head->avail - size_change;
  90   if (avail < 0)
  91     return false;
  92
  93   // work in specified direction, then reverse
  94   dir = (mode & POOL_ALLOC_MODE_LAST_FIT) != 0;
  95   while (true) {
  96     p = &head->item;
  97     q = &head->item;
  98
  99 #ifdef TRY_BLOCKER
 100 blocker_test:
 101     // enter here when either blocker has changed
 102     target_item = item;
 103     target_size = size;
 104  //printf("a target_size %d\n", target_size);
 105     if (mode & POOL_ALLOC_MODE_REALLOC) {
 106       if (new_base >= item->prev->limit && new_limit <= item->next->base)
 107         goto resize;
 108
 109       if (mode & POOL_ALLOC_MODE_MOVEABLE) {
 110         // check both blockers to see if smaller than item
 111         r = item->prev;
 112         if (new_base < r->limit && r != &head->item) {
 113           gap = r->limit - r->base;
 114           if (gap < target_size) {
 115             target_item = r;
 116             target_size = gap;
 117  //printf("b target_size %d\n", target_size);
 118           }
 119         }
 120
 121         r = item->next;
 122         if (new_limit > r->base && r != &head->item) {
 123           gap = r->limit - r->base;
 124           if (gap < target_size) {
 125             target_item = r;
 126             target_size = gap;
 127  //printf("c target_size %d\n", target_size);
 128           }
 129         }
 130       }
 131     }
 132 #endif
 133
 134     while (true) {
 135  //printf("avail %d\n", avail);
 136       // advance, so that p, q are before/after gap
 137       if (!dir) {
 138         p = q;
 139         q = p->next;
 140         if (q == item) {
 141           // skip our own item for gap calculation
 142           q = q->next;
 143
 144 #ifdef MOVEABLE_POOL
 145           // if non-moveable, do our own item specially then reverse direction
 146           if (mode & POOL_ALLOC_MODE_MOVEABLE)
 147             break;
 148 #endif
 149         }
 150  //printf("forw %p(%d)->%p(%d)\n", p, p->limit, q, q->base);
 151       }
 152       else {
 153         q = p;
 154         p = q->prev;
 155         if (p == item) {
 156           // skip our own item for gap calculation
 157           p = p->prev;
 158
 159 #ifdef MOVEABLE_POOL
 160           // if non-moveable, do our own item specially then reverse direction
 161           if (mode & POOL_ALLOC_MODE_MOVEABLE)
 162             break;
 163 #endif
 164         }
 165  //printf("back %p(%d)->%p(%d)\n", p, p->limit, q, q->base);
 166       }
 167
 168       // see if target fits in current gap
 169       gap = q->base - p->limit;
 170 #ifdef TRY_BLOCKER
 171       if (target_size <= gap) {
 172  //printf("target\n");
 173         if (target_item == item)
 174           goto found;
 175
 176         assert(mode & POOL_ALLOC_MODE_MOVEABLE);
 177         if (!dir) {
 178           assert(head->move);
 179           head->move(target_item, p->limit);
 180           target_item->limit += p->limit - target_item->base;
 181           target_item->base = p->limit;
 182         }
 183         else {
 184           assert(head->move_up);
 185           head->move_up(target_item, q->base);
 186           target_item->base += q->base - target_item->limit;
 187           target_item->limit = q->base;
 188         }
 189
 190         // remove from list
 191         target_item->prev->next = target_item->next;
 192         target_item->next->prev = target_item->prev;
 193         if (!dir)
 194           q = p->next;
 195         else
 196           p = q->prev;
 197
 198         // insert into list at found position
 199         target_item->prev = p;
 200         p->next = target_item;
 201         target_item->next = q;
 202         q->prev = target_item;
 203
 204         p = target_item;
 205         q = target_item;
 206         goto blocker_test;
 207       }
 208 #else
 209       if (size <= gap)
 210         goto found;
 211 #endif
 212
 213       // see if gap can be left alone
 214       avail -= gap;
 215       if (avail < 0) {
 216 #ifdef MOVEABLE_POOL
 217         if (!(mode & POOL_ALLOC_MODE_MOVEABLE))
 218           return false;
 219         avail += gap;
 220
 221  //printf("compact\n");
 222         if (!dir) {
 223           assert(head->move);
 224           head->move(q, p->limit);
 225           q->limit += p->limit - q->base;
 226           q->base = p->limit;
 227         }
 228         else {
 229           assert(head->move_up);
 230           head->move_up(p, q->base);
 231           p->base += q->base - p->limit;
 232           p->limit = q->base;
 233         }
 234
 235         // if we have just moved the target, then the target is
 236         // no longer valid and we should go to blocker_test, but
 237         // the loop is about to terminate anyway => don't bother
 238 #else
 239         return false;
 240 #endif
 241       }
 242
 243       assert((dir ? p : q) != &head->item);
 244     }
 245  //printf("done %p(%d)->%p(%d)\n", p, p->limit, q, q->base);
 246
 247     // have compacted up from bottom and reached our item,
 248     // or compacted down from top and reached our item
 249     // (test is slightly different here, as we will ignore
 250     // our item for the purpose of calculating the gap)
 251     gap = q->base - p->limit;
 252     if (size <= gap)
 253       goto found;
 254
 255     dir = !dir;
 256  //printf("dir changed to %d\n", dir);
 257     assert(dir != ((mode & POOL_ALLOC_MODE_LAST_FIT) != 0));
 258   }
 259
 260 found:
 261  //printf("found\n");
 262   // before clobbering the in-place position calculation,
 263   // figure out how much each end is truncated or extended
 264   // (if non-zero, one of these was passed as a parameter)
 265   base_offset = item->base - new_base;
 266   limit_offset = item->limit - new_limit;
 267
 268   // align ourself in found spot
 269   // (try to allow future extension in desired direction)
 270   if ((mode & POOL_ALLOC_MODE_LAST_FIT) == 0) {
 271     new_base = p->limit;
 272     new_limit = new_base + size;
 273   }
 274   else {
 275     new_limit = q->base;
 276     new_base = new_limit - size;
 277   }
 278
 279   if (mode & POOL_ALLOC_MODE_REALLOC) {
 280     // move ourself into found spot
 281     // (throw away truncated parts before calling move routine)
 282     assert(head->move && head->move_up);
 283     if (base_offset < 0) {
 284       item->base -= base_offset;
 285       base_offset = 0;
 286     }
 287     if (limit_offset > 0) {
 288       item->limit -= limit_offset;
 289       limit_offset = 0;
 290     }
 291     base_offset += new_base;
 292     gap = base_offset - item->base; // amount to move by
 293     if (gap < 0)
 294       head->move(item, base_offset);
 295     else if (gap > 0)
 296       head->move_up(item, limit_offset + new_limit);
 297
 298     // remove from list
 299     item->prev->next = item->next;
 300     item->next->prev = item->prev;
 301   }
 302
 303   // insert into list at found position
 304   item->prev = p;
 305   p->next = item;
 306   item->next = q;
 307   q->prev = item;
 308
 309 resize:
 310  //printf("fits %p(%d)->%p(%d) [%d,%d)\n", item->prev, item->prev->limit, item->next, item->next->base, new_base, new_limit);
 311   item->base = new_base;
 312   item->limit = new_limit;
 313
 314   // keep track of total allocation
 315   head->avail -= size_change;
 316 #ifndef NDEBUG
 317  check_invariants(head);
 318 #endif
 319   return true;
 320 }
 321
 322 void pool_free(struct pool_head *head, struct pool_item *item) {
 323   // item must be already allocated
 324   assert(item->prev && item->next);
 325
 326   // remove from list
 327   item->prev->next = item->next;
 328   item->next->prev = item->prev;
 329 #ifndef NDEBUG
 330   item->prev = NULL;
 331   item->next = NULL;
 332 #endif
 333
 334   // keep track of total allocation
 335   head->avail += item->limit - item->base;
 336 #ifndef NDEBUG
 337  check_invariants(head);
 338 #endif
 339 }