Block allocation

Free-lists do reduce the number of calls to malloc(). However, it is possible to further reduce the number of calls by allocating arrays instead of individual elements.

We start off by adding the following structure to the implementation file.


	/* T.c */
	#define	ALLOC_NUM_T	512

	struct alloc_T {
	  struct alloc_T *	at_next;
	  T			at_elems[ALLOC_NUM_T];
	};

	static struct alloc_T *	lcl_alloc_list_T = 0;
	/* and the various accessor macros */

Then we modify the make_T() function from the previous section as follows:


	T *
	make_T(
		/* ... */
		)
	{
	  T *			newT;

	  if( lcl_free_list_T == 0 ) {
	    struct alloc_T *	at;
	    int			i;
	    T *			nextT;
	    T *			prevT;

	    at = xalloc(struct T);
	    next_alloc_T(at) = lcl_alloc_list_T;
	    lcl_alloc_list_T = at;

	    prevT = 0;
	    for( i = 0; i < NUM_ALLOC_T; i++ ) {
	      nextT = &elems_alloc_T(at)[i];
	      next_free_T(nextT) = prevT;
	      prevT = nextT;
	    }
	    lcl_free_list_T = prevT;
	  }

	  /* we should also deal with the no memory left case */
	  newT = lcl_free_list_T;
	  lcl_free_list_T = next_free_T(newT);

	  /* ... */
	  return newT;
	}

There is one additional advantage to using array allocation; it reduces the amount of memory lost in the header for all the objects lost. There is one disadvantage to using array allocation; it is no longer possible to release all memory on the free list.

One of the other things that is no longer possible to do is to use the memory checking technique described previously. Instead, we have to use the following function.


	int
	is_oftype_T(
		T *	ptr
		)
	{
	  struct alloc_T *	at;
	  unsigned		off;

	  for( at = lcl_alloc_T; at; at = next_alloc_T(at) ) {
	    off = ptr - elems_alloc_T(at);
	    if( off < NUM_ALLOC_T ) {
	      return 1;
	    }
	  }
	  return 0;
	}


Next Prev Main Top Feedback