lib/mempool.h

   1 /*
   2  *      UCW Library -- Memory Pools
   3  *
   4  *      (c) 1997--2005 Martin Mares <mj@ucw.cz>
   5  *      (c) 2007 Pavel Charvat <pchar@ucw.cz>
   6  *
   7  *      This software may be freely distributed and used according to the terms
   8  *      of the GNU Lesser General Public License.
   9  */
  10
  11 #ifndef _UCW_POOLS_H
  12 #define _UCW_POOLS_H
  13
  14 /* Memory pool state (see mp_push(), ...) */
  15 struct mempool_state {
  16   uns free[2];
  17   void *last[2];
  18   struct mempool_state *next;
  19 };
  20
  21 /* Memory pool */
  22 struct mempool {
  23   struct mempool_state state;
  24   void *unused, *last_big;
  25   uns chunk_size, threshold, idx;
  26 };
  27
  28 /* Statistics (see mp_stats()) */
  29 struct mempool_stats {
  30   uns total_size;                       /* Real allocated size in bytes */
  31   uns chain_count[3];                   /* Number of allocated chunks in small/big/unused chains */
  32   uns chain_size[3];                    /* Size of allocated chunks in small/big/unused chains */
  33 };
  34
  35 /* Initialize a given mempool structure. Chunk size must be in the interval [1, UINT_MAX / 2] */
  36 void mp_init(struct mempool *pool, uns chunk_size);
  37
  38 /* Allocate and initialize a new memory pool. See mp_init for chunk size limitations. */
  39 struct mempool *mp_new(uns chunk_size);
  40
  41 /* Cleanup mempool initialized by mp_init or mp_new */
  42 void mp_delete(struct mempool *pool);
  43
  44 /* Free all data on a memory pool (saves some empty chunks for later allocations) */
  45 void mp_flush(struct mempool *pool);
  46
  47 /* Compute some statistics for debug purposes. See the definition of the mempool_stats structure. */
  48 void mp_stats(struct mempool *pool, struct mempool_stats *stats);
  49
  50
  51 /*** Allocation routines ***/
  52
  53 /* For internal use only, do not call directly */
  54 void *mp_alloc_internal(struct mempool *pool, uns size) LIKE_MALLOC;
  55
  56 /* The function allocates new <size> bytes on a given memory pool.
  57  * If the <size> is zero, the resulting pointer is undefined,
  58  * but it may be safely reallocated or used as the parameter
  59  * to other functions below.
  60  *
  61  * The resulting pointer is always aligned to a multiple of
  62  * CPU_STRUCT_ALIGN bytes and this condition remains true also
  63  * after future reallocations.
  64  */
  65 void *mp_alloc(struct mempool *pool, uns size);
  66
  67 /* The same as mp_alloc, but the result may not be aligned */
  68 void *mp_alloc_noalign(struct mempool *pool, uns size);
  69
  70 /* The same as mp_alloc, but fills the newly allocated data with zeroes */
  71 void *mp_alloc_zero(struct mempool *pool, uns size);
  72
  73 /* Inlined version of mp_alloc() */
  74 static inline void *
  75 mp_alloc_fast(struct mempool *pool, uns size)
  76 {
  77   uns avail = pool->state.free[0] & ~(CPU_STRUCT_ALIGN - 1);
  78   if (size <= avail)
  79     {
  80       pool->state.free[0] = avail - size;
  81       return pool->state.last[0] - avail;
  82     }
  83   else
  84     return mp_alloc_internal(pool, size);
  85 }
  86
  87 /* Inlined version of mp_alloc_noalign() */
  88 static inline void *
  89 mp_alloc_fast_noalign(struct mempool *pool, uns size)
  90 {
  91   if (size <= pool->state.free[0])
  92     {
  93       void *ptr = pool->state.last[0] - pool->state.free[0];
  94       pool->state.free[0] -= size;
  95       return ptr;
  96     }
  97   else
  98     return mp_alloc_internal(pool, size);
  99 }
 100
 101
 102 /*** Usage as a growing buffer ***/
 103
 104 /* For internal use only, do not call directly */
 105 void *mp_start_internal(struct mempool *pool, uns size) LIKE_MALLOC;
 106 void *mp_grow_internal(struct mempool *pool, uns size);
 107
 108 static inline uns
 109 mp_idx(struct mempool *pool, void *ptr)
 110 {
 111   return ptr == pool->last_big;
 112 }
 113
 114 /* Open a new growing buffer (at least <size> bytes long).
 115  * If the <size> is zero, the resulting pointer is undefined,
 116  * but it may be safely reallocated or used as the parameter
 117  * to other functions below.
 118  *
 119  * The resulting pointer is always aligned to a multiple of
 120  * CPU_STRUCT_ALIGN bytes and this condition remains true also
 121  * after future reallocations. There is an unaligned version as well.
 122  *
 123  * Keep in mind that you can't make any other <pool> allocations
 124  * before you "close" the growing buffer with mp_end().
 125  */
 126 void *mp_start(struct mempool *pool, uns size);
 127 void *mp_start_noalign(struct mempool *pool, uns size);
 128
 129 /* Inlined version of mp_start() */
 130 static inline void *
 131 mp_start_fast(struct mempool *pool, uns size)
 132 {
 133   uns avail = pool->state.free[0] & ~(CPU_STRUCT_ALIGN - 1);
 134   if (size <= avail)
 135     {
 136       pool->idx = 0;
 137       pool->state.free[0] = avail;
 138       return pool->state.last[0] - avail;
 139     }
 140   else
 141     return mp_start_internal(pool, size);
 142 }
 143
 144 /* Inlined version of mp_start_noalign() */
 145 static inline void *
 146 mp_start_fast_noalign(struct mempool *pool, uns size)
 147 {
 148   if (size <= pool->state.free[0])
 149     {
 150       pool->idx = 0;
 151       return pool->state.last[0] - pool->state.free[0];
 152     }
 153   else
 154     return mp_start_internal(pool, size);
 155 }
 156
 157 /* Return start pointer of the growing buffer allocated by mp_start() or a similar function */
 158 static inline void *
 159 mp_ptr(struct mempool *pool)
 160 {
 161   return pool->state.last[pool->idx] - pool->state.free[pool->idx];
 162 }
 163
 164 /* Return the number of bytes available for extending the growing buffer */
 165 static inline uns
 166 mp_avail(struct mempool *pool)
 167 {
 168   return pool->state.free[pool->idx];
 169 }
 170
 171 /* Grow the buffer allocated by mp_start() to be at least <size> bytes long
 172  * (<size> may be less than mp_avail(), even zero). Reallocated buffer may
 173  * change its starting position. The content will be unchanged to the minimum
 174  * of the old and new sizes; newly allocated memory will be uninitialized.
 175  * Multiple calls to mp_grow have amortized linear cost wrt. the maximum value of <size>. */
 176 static inline void *
 177 mp_grow(struct mempool *pool, uns size)
 178 {
 179   return (size <= mp_avail(pool)) ? mp_ptr(pool) : mp_grow_internal(pool, size);
 180 }
 181
 182 /* Grow the buffer by at least one byte -- equivalent to mp_grow(pool, mp_avail(pool) + 1) */
 183 static inline void *
 184 mp_expand(struct mempool *pool)
 185 {
 186   return mp_grow_internal(pool, mp_avail(pool) + 1);
 187 }
 188
 189 /* Close the growing buffer. The <end> must point just behind the data, you want to keep
 190  * allocated (so it can be in the interval [mp_ptr(pool), mp_ptr(pool) + mp_avail(pool)]). */
 191 static inline void
 192 mp_end(struct mempool *pool, void *end)
 193 {
 194   pool->state.free[pool->idx] = pool->state.last[pool->idx] - end;
 195 }
 196
 197 /* Return size in bytes of the last allocated memory block (with mp_alloc*() or mp_end()). */
 198 static inline uns
 199 mp_size(struct mempool *pool, void *ptr)
 200 {
 201   uns idx = mp_idx(pool, ptr);
 202   return pool->state.last[idx] - ptr - pool->state.free[idx];
 203 }
 204
 205 /* Open the last memory block (allocated with mp_alloc*() or mp_end())
 206  * for growing and return its size in bytes. The contents and the start pointer
 207  * remain unchanged. Do not forget to call mp_end() to close it. */
 208 uns mp_open(struct mempool *pool, void *ptr);
 209
 210 /* Inlined version of mp_open() */
 211 static inline uns
 212 mp_open_fast(struct mempool *pool, void *ptr)
 213 {
 214   pool->idx = mp_idx(pool, ptr);
 215   uns size = pool->state.last[pool->idx] - ptr - pool->state.free[pool->idx];
 216   pool->state.free[pool->idx] += size;
 217   return size;
 218 }
 219
 220 /* Reallocate the last memory block (allocated with mp_alloc*() or mp_end())
 221  * to the new <size>. Behavior is similar to mp_grow(), but the resulting
 222  * block is closed. */
 223 void *mp_realloc(struct mempool *pool, void *ptr, uns size);
 224
 225 /* The same as mp_realloc(), but fills the additional bytes (if any) with zeroes */
 226 void *mp_realloc_zero(struct mempool *pool, void *ptr, uns size);
 227
 228 /* Inlined version of mp_realloc() */
 229 static inline void *
 230 mp_realloc_fast(struct mempool *pool, void *ptr, uns size)
 231 {
 232   mp_open_fast(pool, ptr);
 233   ptr = mp_grow(pool, size);
 234   mp_end(pool, ptr + size);
 235   return ptr;
 236 }
 237
 238
 239 /*** Usage as a stack ***/
 240
 241 /* Save the current state of a memory pool.
 242  * Do not call this function with an opened growing buffer. */
 243 static inline void
 244 mp_save(struct mempool *pool, struct mempool_state *state)
 245 {
 246   *state = pool->state;
 247   pool->state.next = state;
 248 }
 249
 250 /* Save the current state to a newly allocated mempool_state structure.
 251  * Do not call this function with an opened growing buffer. */
 252 struct mempool_state *mp_push(struct mempool *pool);
 253
 254 /* Restore the state saved by mp_save() or mp_push() and free all
 255  * data allocated after that point (including the state structure itself).
 256  * You can't reallocate the last memory block from the saved state. */
 257 void mp_restore(struct mempool *pool, struct mempool_state *state);
 258
 259 /* Restore the state saved by the last call to mp_push().
 260  * mp_pop() and mp_push() works as a stack so you can push more states safely. */
 261 void mp_pop(struct mempool *pool);
 262
 263
 264 /*** mempool-str.c ***/
 265
 266 char *mp_strdup(struct mempool *, char *) LIKE_MALLOC;
 267 void *mp_memdup(struct mempool *, void *, uns) LIKE_MALLOC;
 268 char *mp_multicat(struct mempool *, ...) LIKE_MALLOC SENTINEL_CHECK;
 269 static inline char * LIKE_MALLOC
 270 mp_strcat(struct mempool *mp, char *x, char *y)
 271 {
 272   return mp_multicat(mp, x, y, NULL);
 273 }
 274 char *mp_strjoin(struct mempool *p, char **a, uns n, uns sep) LIKE_MALLOC;
 275
 276
 277 /*** mempool-fmt.c ***/
 278
 279 char *mp_printf(struct mempool *mp, const char *fmt, ...) FORMAT_CHECK(printf,2,3) LIKE_MALLOC;
 280 char *mp_vprintf(struct mempool *mp, const char *fmt, va_list args) LIKE_MALLOC;
 281 char *mp_printf_append(struct mempool *mp, char *ptr, const char *fmt, ...) FORMAT_CHECK(printf,3,4);
 282 char *mp_vprintf_append(struct mempool *mp, char *ptr, const char *fmt, va_list args);
 283
 284 #endif