Memory Allocation for Lists

When we are calling malloc directly in applications such as Program-3.9 or 3.11, all the calls request memory blocks of the same size. This case is typical, and an alternate method of keeping track of memory available for allocation immediately suggests itself: Simply use a linked list. All nodes that are not on any list that is in use can be kept together on a single linked list. We refer to this list as the free list. When we need to allocate space for a node, we get it by deleting it from the free list; when we remove a node from any of our lists, we dispose of it by inserting it onto the free list.

1. List-processing interface

// Program-3.12 list.h
#ifndef LIST_INTERFACE
#define LIST_INTERFACE
typedef struct node* link;
struct node {
    int item;
    link next;
}

void initNodes(int);
link newNode(int);
void freeNode(link);
void insertNext(link);
link deleteNext(link);
link Next(link);
int Item(link);

#endif

We declares some functions for allocating and freeing memory for list nodes.

initNodes is for the convenience of the implementation. Next and Item function allow clients to use lists without dependence upon implementation details.

2. Implementation

// list.c
// Program 3.14
#include "list.h"

#include <stdlib.h>

link freeList;

void initNodes(int N) {
  freeList = malloc((N + 1) * sizeof(*freeList));
  for (int i = 0; i < N + 1; i++) {
    freeList[i].next = &freeList[i];
  }
  freeList[N].next = NULL;
}

link newNode(int i) {
  link x = deleteNext(freeList);
  x->item = i;
  x->next = x;
  return x;
}

void freeNode(link x) { insertNext(freeList, x); }

void insertNext(link x, link t) {
  t->next = x->next;
  x->next = t;
}

link deleteNext(link x) {
  link t = x->next;
  x->next = t->next;
  return t;
}

link Next(link x) { return x->next; }

int Item(link x) { return x->item; }

We build a free list that is initialized to the maximum number of nodes that our program will use, all linked together. When a client program allocates a node, we remove that node from the free list; when a client program free a node, we link that node in to the free list.

By convention, client programs do not refer to list nodes except through function calls, and nodes returned to client programs have self-links. These conventions provide some measure of protection against referencing undefined pointers.

3. List allocation for the Josephus problem

#include <stdio.h>
#include <stdlib.h>

#include "list.h"

int main(int argc, char* argv[]) {
  int N = atoi(argv[1]);
  int M = atoi(argv[2]);

  initNodes(N);
  link x = newNode(1);
  for (int i = 2; i < N + 1; i++) {
    link t = newNode(i);
    insertNext(x, t);
    x = t;
  }

  for (; x != Next(x);) {
    for (int i = 1; i < M; i++) {
      x = Next(x);
    }
    freeNode(deleteNext(x));
  }
  printf("%d\n", Item(x));
}

This program for the Josephus problem is an example of a client program utilizing the list-processing primitives declared in program 3.12 and implementation in 3.14.

Programs that can make advantage of specialized knowledge about an application often are more efficient than general-purpose programs for the same task. Memory allocation is no exception to this maxim.

An algorithm that has to handle storage request of varying sizes cannot know that we are always going to be making request for blocks of one fixed size, and therefore cannot take advantage of that fact.

Paradoxically, another reason to avoid general-purpose library functions is that doing so makes programs more portable -- we can protect ourselves or when we move to a different system.

Exercises

• 3.47

Reference

1. Algorithms in C