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 void *mp_spread_internal(struct mempool *pool, void *p, uns size);
 108
 109 static inline uns
 110 mp_idx(struct mempool *pool, void *ptr)
 111 {
 112   return ptr == pool->last_big;
 113 }
 114
 115 /* Open a new growing buffer (at least <size> bytes long).
 116  * If the <size> is zero, the resulting pointer is undefined,
 117  * but it may be safely reallocated or used as the parameter
 118  * to other functions below.
 119  *
 120  * The resulting pointer is always aligned to a multiple of
 121  * CPU_STRUCT_ALIGN bytes and this condition remains true also
 122  * after future reallocations. There is an unaligned version as well.
 123  *
 124  * Keep in mind that you can't make any other <pool> allocations
 125  * before you "close" the growing buffer with mp_end().
 126  */
 127 void *mp_start(struct mempool *pool, uns size);
 128 void *mp_start_noalign(struct mempool *pool, uns size);
 129
 130 /* Inlined version of mp_start() */
 131 static inline void *
 132 mp_start_fast(struct mempool *pool, uns size)
 133 {
 134   uns avail = pool->state.free[0] & ~(CPU_STRUCT_ALIGN - 1);
 135   if (size <= avail)
 136     {
 137       pool->idx = 0;
 138       pool->state.free[0] = avail;
 139       return pool->state.last[0] - avail;
 140     }
 141   else
 142     return mp_start_internal(pool, size);
 143 }
 144
 145 /* Inlined version of mp_start_noalign() */
 146 static inline void *
 147 mp_start_fast_noalign(struct mempool *pool, uns size)
 148 {
 149   if (size <= pool->state.free[0])
 150     {
 151       pool->idx = 0;
 152       return pool->state.last[0] - pool->state.free[0];
 153     }
 154   else
 155     return mp_start_internal(pool, size);
 156 }
 157
 158 /* Return start pointer of the growing buffer allocated by mp_start() or a similar function */
 159 static inline void *
 160 mp_ptr(struct mempool *pool)
 161 {
 162   return pool->state.last[pool->idx] - pool->state.free[pool->idx];
 163 }
 164
 165 /* Return the number of bytes available for extending the growing buffer */
 166 static inline uns
 167 mp_avail(struct mempool *pool)
 168 {
 169   return pool->state.free[pool->idx];
 170 }
 171
 172 /* Grow the buffer allocated by mp_start() to be at least <size> bytes long
 173  * (<size> may be less than mp_avail(), even zero). Reallocated buffer may
 174  * change its starting position. The content will be unchanged to the minimum
 175  * of the old and new sizes; newly allocated memory will be uninitialized.
 176  * Multiple calls to mp_grow have amortized linear cost wrt. the maximum value of <size>. */
 177 static inline void *
 178 mp_grow(struct mempool *pool, uns size)
 179 {
 180   return (size <= mp_avail(pool)) ? mp_ptr(pool) : mp_grow_internal(pool, size);
 181 }
 182
 183 /* Grow the buffer by at least one byte -- equivalent to mp_grow(pool, mp_avail(pool) + 1) */
 184 static inline void *
 185 mp_expand(struct mempool *pool)
 186 {
 187   return mp_grow_internal(pool, mp_avail(pool) + 1);
 188 }
 189
 190 /* Ensure that there is at least <size> bytes free after <p>, if not, reallocate and adjust <p>. */
 191 static inline void *
 192 mp_spread(struct mempool *pool, void *p, uns size)
 193 {
 194   return (((uns)(pool->state.last[pool->idx] - p) >= size) ? p : mp_spread_internal(pool, p, size));
 195 }
 196
 197 /* Close the growing buffer. The <end> must point just behind the data, you want to keep
 198  * allocated (so it can be in the interval [mp_ptr(pool), mp_ptr(pool) + mp_avail(pool)]).
 199  * Returns a pointer to the beginning of the just closed block. */
 200 static inline void *
 201 mp_end(struct mempool *pool, void *end)
 202 {
 203   void *p = mp_ptr(pool);
 204   pool->state.free[pool->idx] = pool->state.last[pool->idx] - end;
 205   return p;
 206 }
 207
 208 /* Return size in bytes of the last allocated memory block (with mp_alloc*() or mp_end()). */
 209 static inline uns
 210 mp_size(struct mempool *pool, void *ptr)
 211 {
 212   uns idx = mp_idx(pool, ptr);
 213   return pool->state.last[idx] - ptr - pool->state.free[idx];
 214 }
 215
 216 /* Open the last memory block (allocated with mp_alloc*() or mp_end())
 217  * for growing and return its size in bytes. The contents and the start pointer
 218  * remain unchanged. Do not forget to call mp_end() to close it. */
 219 uns mp_open(struct mempool *pool, void *ptr);
 220
 221 /* Inlined version of mp_open() */
 222 static inline uns
 223 mp_open_fast(struct mempool *pool, void *ptr)
 224 {
 225   pool->idx = mp_idx(pool, ptr);
 226   uns size = pool->state.last[pool->idx] - ptr - pool->state.free[pool->idx];
 227   pool->state.free[pool->idx] += size;
 228   return size;
 229 }
 230
 231 /* Reallocate the last memory block (allocated with mp_alloc*() or mp_end())
 232  * to the new <size>. Behavior is similar to mp_grow(), but the resulting
 233  * block is closed. */
 234 void *mp_realloc(struct mempool *pool, void *ptr, uns size);
 235
 236 /* The same as mp_realloc(), but fills the additional bytes (if any) with zeroes */
 237 void *mp_realloc_zero(struct mempool *pool, void *ptr, uns size);
 238
 239 /* Inlined version of mp_realloc() */
 240 static inline void *
 241 mp_realloc_fast(struct mempool *pool, void *ptr, uns size)
 242 {
 243   mp_open_fast(pool, ptr);
 244   ptr = mp_grow(pool, size);
 245   mp_end(pool, ptr + size);
 246   return ptr;
 247 }
 248
 249
 250 /*** Usage as a stack ***/
 251
 252 /* Save the current state of a memory pool.
 253  * Do not call this function with an opened growing buffer. */
 254 static inline void
 255 mp_save(struct mempool *pool, struct mempool_state *state)
 256 {
 257   *state = pool->state;
 258   pool->state.next = state;
 259 }
 260
 261 /* Save the current state to a newly allocated mempool_state structure.
 262  * Do not call this function with an opened growing buffer. */
 263 struct mempool_state *mp_push(struct mempool *pool);
 264
 265 /* Restore the state saved by mp_save() or mp_push() and free all
 266  * data allocated after that point (including the state structure itself).
 267  * You can't reallocate the last memory block from the saved state. */
 268 void mp_restore(struct mempool *pool, struct mempool_state *state);
 269
 270 /* Restore the state saved by the last call to mp_push().
 271  * mp_pop() and mp_push() works as a stack so you can push more states safely. */
 272 void mp_pop(struct mempool *pool);
 273
 274
 275 /*** mempool-str.c ***/
 276
 277 char *mp_strdup(struct mempool *, const char *) LIKE_MALLOC;
 278 void *mp_memdup(struct mempool *, const void *, uns) LIKE_MALLOC;
 279 char *mp_multicat(struct mempool *, ...) LIKE_MALLOC SENTINEL_CHECK;
 280 static inline char * LIKE_MALLOC
 281 mp_strcat(struct mempool *mp, const char *x, const char *y)
 282 {
 283   return mp_multicat(mp, x, y, NULL);
 284 }
 285 char *mp_strjoin(struct mempool *p, char **a, uns n, uns sep) LIKE_MALLOC;
 286
 287
 288 /*** mempool-fmt.c ***/
 289
 290 char *mp_printf(struct mempool *mp, const char *fmt, ...) FORMAT_CHECK(printf,2,3) LIKE_MALLOC;
 291 char *mp_vprintf(struct mempool *mp, const char *fmt, va_list args) LIKE_MALLOC;
 292 char *mp_printf_append(struct mempool *mp, char *ptr, const char *fmt, ...) FORMAT_CHECK(printf,3,4);
 293 char *mp_vprintf_append(struct mempool *mp, char *ptr, const char *fmt, va_list args);
 294
 295 #endif