buddy/mpool.h

   1 #ifndef MPOOL_H_
   2 #define MPOOL_H_
   3
   4 #include <stdlib.h>
   5 #include <sys/queue.h>
   6
   7 /*#define MPOOL_DEBUG*/
   8 #define MPOOL_STATS
   9
  10 #ifdef MPOOL_DEBUG
  11 #define DPRINTF(a) printf a
  12 #else
  13 #define DPRINTF(a)
  14 #endif
  15
  16 /* `flags' bits in blknode data structure */
  17 #define MPOOL_NODE_AVAIL  (1 << 0)    /* If not set, node is reserved, else available */
  18 #define MPOOL_NODE_LR     (1 << 1)    /* If not set, node is left buddy, else right buddy */
  19 #define MPOOL_NODE_PARENT (1 << 2)    /* If not set, parent is left buddy, else right buddy */
  20
  21 #define MPOOL_BLOCK_USED   0    /* Block is used */
  22 #define MPOOL_BLOCK_AVAIL  1    /* Block is available */
  23 #define MPOOL_BLOCK_LEFT   2    /* Block is left buddy */
  24 #define MPOOL_BLOCK_RIGHT  3    /* Block is right buddy */
  25 #define MPOOL_BLOCK_PARENT 4    /* Block's parent is right buddy */
  26
  27 /* Macro definitions */
  28 #define MPOOL_MARK_AVAIL(pnode) pnode->flags |= MPOOL_NODE_AVAIL
  29 #define MPOOL_MARK_USED(pnode) pnode->flags &= ~MPOOL_NODE_AVAIL
  30 #define MPOOL_MARK_LEFT(pnode) pnode->flags &= ~MPOOL_NODE_LR
  31 #define MPOOL_MARK_RIGHT(pnode) pnode->flags |= MPOOL_NODE_LR
  32
  33 #define MPOOL_IS_AVAIL(pnode) ((pnode->flags & MPOOL_NODE_AVAIL) != 0)
  34 #define MPOOL_IS_USED(pnode)  ((pnode->flags & MPOOL_NODE_AVAIL) == 0)
  35 #define MPOOL_IS_LEFT(pnode)  ((pnode->flags & MPOOL_NODE_LR) == 0)
  36 #define MPOOL_IS_RIGHT(pnode) ((pnode->flags & MPOOL_NODE_LR) != 0)
  37
  38 /* This macro is provided for easy initialization of a blknode structure */
  39 #define MPOOL_BLOCK_INIT(_node, _base, _ptr, _avail, _lr, _parent, _logsize) \
  40     do {                                                                \
  41         _node = _base;                                                  \
  42         _node->ptr = _ptr;                                              \
  43         _node->logsize = _logsize;                                      \
  44                                                                         \
  45         /* Availability */                                              \
  46         if ((_avail) == MPOOL_BLOCK_AVAIL)                              \
  47             _node->flags |= MPOOL_NODE_AVAIL;                           \
  48         else                                                            \
  49             _node->flags &= ~MPOOL_NODE_AVAIL;                          \
  50                                                                         \
  51         /* Left-Right relationship */                                   \
  52         if ((_lr) == MPOOL_BLOCK_RIGHT)                                 \
  53             _node->flags |= MPOOL_NODE_LR;                              \
  54         else                                                            \
  55             _node->flags &= ~MPOOL_NODE_LR;                             \
  56                                                                         \
  57         /* Parent L-R relationship */                                   \
  58         if ((_parent) == MPOOL_BLOCK_PARENT)                            \
  59             _node->flags |= MPOOL_NODE_PARENT;                          \
  60         else                                                            \
  61             _node->flags &= ~MPOOL_NODE_PARENT;                         \
  62     } while(0)
  63
  64 typedef struct blknode {
  65     unsigned char flags;    /* availability, left-right buddiness, inheritance */
  66     size_t logsize;         /* logarithm of size with base 2 */
  67     void *ptr;              /* pointer to beginning of free block (what mpool_alloc() returns) */
  68     LIST_ENTRY(blknode) next_chunk;
  69 } blknode_t;
  70
  71 typedef struct mpool {
  72     void *mem;
  73     size_t nblocks;       /* nblocks = logsize + 1 */
  74     size_t maxlogsize;    /* logarithm of maximum size of chunk with base 2 */
  75     size_t minlogsize;    /* logarithm of minimum size of chunk with base 2 */
  76 #ifdef MPOOL_STATS
  77     size_t nsplits;       /* number of splits made */
  78     size_t nmerges;       /* number of merges made */
  79 #endif
  80     LIST_HEAD(blkhead, blknode) *blktable;
  81 } mpool_t;
  82
  83 typedef struct blkhead blkhead_t;
  84
  85 typedef enum {
  86     MPOOL_OK,
  87     MPOOL_EBADVAL,
  88     MPOOL_ENOMEM,
  89     MPOOL_ERANGE
  90 } mpret_t;
  91
  92 /* Function prototypes */
  93 mpret_t mpool_init(mpool_t **mpool, size_t maxlogsize, size_t minlogsize);
  94 void *mpool_alloc(mpool_t *mpool, size_t blksize);
  95 void mpool_free(mpool_t *mpool, void *ptr);
  96 void mpool_destroy(mpool_t *mpool);
  97
  98 #endif    /* MPOOL_H_ */