2.5 Memory Allocation

The standard C library functions malloc() and free() are the usual way to obtain and release memory for dynamic data structures like tables. Most users will be satisfied if libavl uses these routines for memory management. On the other hand, some users will want to supply their own methods for allocating and freeing memory, perhaps even different methods from table to table. For these users' benefit, each table is associated with a memory allocator, which provides functions for memory allocation and deallocation. This allocator has the same form in each table implementation. It looks like this:

5. <Memory allocator 5> =
#ifndef LIBAVL_ALLOCATOR
#define LIBAVL_ALLOCATOR
/* Memory allocator. */
struct libavl_allocator 
  {
    void *(*libavl_malloc) (struct libavl_allocator *, size_t libavl_size);
    void (*libavl_free) (struct libavl_allocator *, void *libavl_block);
  };
#endif

This code is included in 14, 99, and 649.

Members of struct libavl_allocator have the same interfaces as the like-named standard C library functions, except that they are each additionally passed a pointer to the struct libavl_allocator * itself as their first argument. The table implementations never call tbl_malloc() with a zero size or tbl_free() with a null pointer block.

The struct libavl_allocator type is shared between all of libavl's modules, so its name begins with libavl_, not with the specific module prefix that we've been representing generically here as tbl_. This makes it possible for a program to use a single allocator with multiple libavl table modules, without the need to declare instances of different structures.

The default allocator is just a wrapper around malloc() and free(). Here it is:

6. <Default memory allocation functions 6> =
/* Allocates size bytes of space using malloc(). 
   Returns a null pointer if allocation fails. */
void *
tbl_malloc (struct libavl_allocator *allocator, size_t size) 
{
  assert (allocator != NULL && size > 0);
  return malloc (size);
}

/* Frees block. */
void 
tbl_free (struct libavl_allocator *allocator, void *block) 
{
  assert (allocator != NULL && block != NULL);
  free (block);
}

/* Default memory allocator that uses malloc() and free(). */
struct libavl_allocator tbl_allocator_default = 
  {
    tbl_malloc, 
    tbl_free
  };

This code is included in 29, 145, 196, 251, 300, 336, 375, 418, 455, 489, 522, 554, and 649.

The default allocator comes along with header file declarations:

7. <Default memory allocator header 7> =
/* Default memory allocator. */
extern struct libavl_allocator tbl_allocator_default;
void *tbl_malloc (struct libavl_allocator *, size_t);
void tbl_free (struct libavl_allocator *, void *);

This code is included in 14 and 649.

See also:  [FSF 1999], nodes “Malloc Examples” and “Changing Block Size”.

Exercises:

1. This structure is named with a libavl_ prefix because it is shared among all of libavl's module. Other types are shared among libavl modules, too, such as tbl_item_func. Why don't the names of these other types also begin with libavl_? [answer]

2. Supply an alternate allocator, still using malloc() and free(), that prints an error message to stderr and aborts program execution when memory allocation fails. [answer]

*3. Some kinds of allocators may need additional arguments. For instance, if memory for each table is taken from a separate Apache-style “memory pool”, then a pointer to the pool structure is needed. Show how this can be done without modifying existing types. [answer]