Listing 4

#if 0  /* REQUIRED DEFINITIONS */
  #define MPOOLQ_CELL_T int  /* some signed type */
#endif

#include "circ_arr.h"

typedef struct {
  MPOOLQ_CELL_T *base, *end;
  union {
    volatile MPOOLQ_CELL_T * volatile w;
    volatile MPOOLQ_CELL_T * volatile const r;
    volatile MPOOLQ_CELL_T * const l;
  } head, tail;
  int size;
} MPOOLQ_T;

#ifndef MPOOLQ_USER_T
  #define MPOOLQ_USER_T char
#endif
#define MPOOLQ_UUS_PER_CELL \
  (sizeof (MPOOLQ_CELL_T) / sizeof (MPOOLQ_USER_T))
#define MPOOLQ_UU_TO_CELLS( n ) (((n)+1) / MPOOLQ_UUS_PER_CELL)
#define MPOOLQ_CELLS_TO_UU( n ) ((n) * MPOOLQ_UUS_PER_CELL)

#define MPOOLQ_BLK_SIZE( blk ) \
  (((volatile MPOOLQ_CELL_T *) (blk)) [-1])

/* Producers (allocator and related functions) */
#define MPOOLQ_CREATE_HOLE( p, ctail ) ( \
  (ctail) [0] = -((p)->end - (ctail)), \
  (p)->tail.w = (p)->base \
)

static inline
void *mpoolq_alloc (MPOOLQ_T *p, MPOOLQ_CELL_T UUs) {
  MPOOLQ_CELL_T cells = MPOOLQ_UU_TO_CELLS (UUs);
  volatile MPOOLQ_CELL_T *head = p->head.r,
                         *old_tail = p->tail.l;
  volatile MPOOLQ_CELL_T *end = old_tail + cells + 1;

  if (end >= head) {
    if (head > old_tail) return NULL;
    else {
      if (! (end < p->end
             || (end == p->end && head != p->base)))
      {  /* actually wrap around */
        if ((end = p->base + cells + 1) >= head)
          return NULL;
        old_tail = MPOOLQ_CREATE_HOLE (p, old_tail);
        end = old_tail + cells + 1;
      }
    }
  }

  *old_tail = UUs;
  p->tail.w = CIRC_ARR_WRAP_END (end, p->base, p->end);
  return (void *) (1 + old_tail);
}

static inline MPOOLQ_CELL_T mpoolq_lavail_cells (MPOOLQ_T *p) {
  volatile MPOOLQ_CELL_T *head = p->head.r, *tail = p->tail.l;
  if (tail + 1 == p->end) {
    if (head == p->base) return 0;
    tail = MPOOLQ_CREATE_HOLE (p, tail);
  }
  return
    CIRC_ARR_DS_LAVAIL (p->base, p->end, head, tail, p->size);
}


/* Consumers */

/* changes *blk to the address of the next allocated block, if
   any, or the tail ptr; returns TRUE if a block was found */
static inline
BOOL mpoolq_next_blk (const MPOOLQ_T *p, MPOOLQ_CELL_T **blk) {
  MPOOLQ_CELL_T n;
  for (;; *blk = CIRC_ARR_WRAP_END (*blk+n, p->base, p->end)) {
    if (*blk == p->tail.r) return FALSE;
    if ((n = - (*blk) [0]) <= 0) return TRUE;
  }
}

static inline BOOL mpoolq_empty (MPOOLQ_T *p) {
  MPOOLQ_CELL_T *blk = (MPOOLQ_CELL_T *) p->head.l;
  BOOL empty = mpoolq_next_blk (p, &blk);
  p->head.w = blk;
  return empty;
}

#define MPOOLQ_OLDEST( p ) \
  (mpoolq_empty (p) ? NULL : (void *) (p)->head.l + 1)

static inline void mpoolq_free (MPOOLQ_T *p, void *blk) {
  MPOOLQ_BLK_SIZE (blk) = - MPOOLQ_BLK_CELLS (blk) - 1;
  mpoolq_empty (p);  /* calls mpoolq_next_blk() */
}