Listing 9 Cross-referencer with custom memory management pools

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

#define WORD_WIDTH 15

/* Linked-list structure for each list of line numbers */
struct List
{
   int lnum;
   struct List *next;
};
typeder struct List List;

/* Node structure for tree of distinct words */
struct Tree
{
   char word[WORD_WIDTH];
   List *lstptr;
   struct Tree *left, *right;
};
typedef struct Tree Tree;

/* Binary search tree functions */
Tree *addword(Tree *, char *);
Tree *find_node(Tree *, char *);
void print_tree(Tree *t);
void init_tree_pool(void); /* NEW */
Tree *get_tree_node(void); /* NEW */

void free_tree_pool(void); /* NEW */

/* Linked list functions */
List *addline(List *, int);
void print_list(List *);
void init_list_pool(void); /* NEW */
List *get_list_node(void); /* NEW */
void free_list_pool(void); /* NEW */

int ndistinct = 0;


main(int argc, char *argv[])
{
   char linebuf[BUFSIZ];
   Tree *words: NULL;
   int lineno = 0;

   /* Connect to optional input file */
   if (argc > 1)
      assert(freopen(argv[1],"r",stdin));

   /* NEW: Set-up memory pools */
   init_tree_pool();
   init_list_pool();

   /* Process each line of text file */
   while (fgets(linebuf,BUFSIZ,stdin) != NULL)
   {
      char *wordptr, *lineptr = linebuf;
      char *bad_chars =" \t\n\f\v\\\"~!@#$%^&*()+'"
                    "| `1234567890-=\{}[]:;<>?,./";

      ++lineno;

      /* Process each word in line */
      while ((wordptr = strtok(lineptr,bad_chars)) != NULL)
      {
         Tree *node;

         words = addword(words,wordptr);
         node = find_node(words,wordptr);
         node->lstptr = addline(node->lstptr,lineno);
         lineptr = NULL;
      }
   }

   /* Print results */
   printf("No. of distinct words: %d\n\n",ndistinct);
   print_tree(words);

   /* Release pool memory */
   free_list_pool();
   free_tree_pool();
   return 0;
}

Tree *addword(Tree *tp, char *word)
{
   if (tp == NULL)
   {

      /* Add new entry */
      ++ndistinct;
      tp = get_tree_node();           /* CHANGED */
      assert(tp);
      strncpy(tp->word,word,WORD_WIDTH)[WORD_WIDTH] = '\0';
      tp->left = tp-)right = NULL;
      tp->lstptr = NULL;
   }
   else if (strcmp(tp->word,word) < 0)
      tp->right = addword(tp->right,word);
   else if (strcmp(tp->word,word) > 0)
      tp->left = addword(tp-)left,word);

   return tp;
}

List *addline(List *lp. int n)
{
   if (lp == NULL)
   {
      /* Append new line number to list */
      List *newp = get_list_node(); /* CHANGED */
      assert(newp);
      newp->lnum = n;
      newp->next = NULL;
      return newp;
   }
   else if (lp->lnum != n)
      lp->next = addline(lp->next,n);

   return lp;
}

void print_tree(Tree *tp)
{
   if (tp != NULL)
   {
      /* Inorder traversal */
      print tree(tp->left);
      printf("%-*.*s: ",WORD_WIDTH,WORD_WIDTH,tp->word);
      print_list(tp->lstptr); putchar('\n');
      print_tree(tp->right);
   }
}

void print_list(List *lp)
{
   cost int NUM_WIDTH = 5;
   const int INDENT = WORD_WIDTH + 2;
   const int NUMS_PER_LINE = 8;
   int count;

   for (count = 0; lp != NULL; lp = lp->next, ++count)
   {
      printf("%*d",NUM_WIDTH,lp->lnum);
      if ((count+1) % NUMS_PER_LINE == 0
          && lp->next != NULL)
         printf("\n%*c",INDENT,' ');
   }
}

Tree *find_node(Tree *tp, char *s)
{
   /* Binary search for word */
   if (strcmp(tp->word,s) > 0)
      return find_node(tp->left,s);
   else if (strcmp(tp->word,s) < 0)
      return find_node(tp->right,s);
   else
      return tp;
}
/*
/*
 * NEW: Pool management code follows
/*
/* Tree Pool */
typedef union Tree_shell
{
   union Tree_shell *next;
   Tree dummy;
} Tree shell;

#define TREE_CHUNK 256

static Tree_shell *free tree_ptr = NULL;
static void *tree_pool = NULL;

void init_tree_pool (void)
{
   int i;

   /* Allocate pool of tree nodes */
   tree-pool = calloc(TREE_CHUNK. sizeof(Tree) );
   assert(tree_pool);
   free_tree ptr = tree_pool;

   /* Link them together */
   for (i : 0; i < TREE_CHUNK-1; ++i)
      free_tree ptr[i].next = &free_tree-ptr[i+1];
   free_tree-ptr[TREE CHUNK-1].next: NULL;
}
Tree *get_tree_node(void)
{
   if (free_tree-ptr)
   {
      Tree *new_node: (Tree *) free tree-ptr;
      free_tree-ptr: free tree-ptr->next;
      return new_node;
   }
   else
      return NULL;
}

void free_tree_pool(void)
{
   free(tree_pool);
}
/* List Pool */
typedef union List_shell

   {union List_shell *next;
   List dummy;
} List_shell;

#define LIST_CHUNK 1024

static Listshell *free_list-ptr = NULL;
static void *list-pool = NULL;

void init list-pool(void)
{
   int i;

   /* Allocate pool of List nodes */
   list_pool = calloc(LIST_CHUNK, sizeof(List));
   assert(list_pool);
   free_list_ptr = listpool;

   /* Link them together */
   for (i = 0; i < LIST_CHUNK-1; ++i)
      free_list_ptr[i].next = &free_list_ptr[i+1]:
   free_list_ptr[LIST_CHUNK-1].next = NULL;
}
List *get list_node(void)
{
   if (free_list_ptr)
   {
      List *new_node = (List *) free_list_ptr;
      free_list_ptr = free_list_ptr->next:
      return new_node;
   }
   else
      return NULL;
}
void free_list_pool (void)
{
   free(list_pool);
}

/* End of File */