Chuck Allison is a regular columnist with CUJ and a software architect for the Family History Department of the Church of Jesus Christ of Latter Day Saints Church Headquarters in Salt Lake City. He has a B.S. and M.S. in mathematics, has been programming since 1975, and has been teaching and developing in C since 1984. His current interest is object-oriented technology and education. He is a member of X3J16, the ANSI C++ Standards Committee. Chuck can be reached on the Internet at 72640.1507@compuserve.com.
As a C/C++ programmer you need to worry about three types of internal storage: automatic, static, and dynamic. When you define automatic variables inside a block, most compilers generate code to allocate space for those variables on the program stack. When execution leaves a block, the stack pointer moves back up to where it was before that block was entered, in effect destroying that block's automatic variables. When execution reenters the block, it creates all automatic variables afresh, with the same initial values as before. Static objects are declared either at file scope or inside a block with the static specifier. They reside at a fixed location in the program's data space and are initialized once at program startup.
Dynamic objects are created at run time by special library function calls and reside on the heap, a special data area set aside for user-controlled, run-time memory allocation. When you request heap space for an object you get an address in return. The system reserves the memory at that address for your use until you're through with it. In this article I will discuss common C/C++ techniques for using dynamic memory.
Ragged Arrays
The heap comes in handy when you don't know at compile time how much space you will need to store an object, or how many objects you will need. For example, a common practice in processing text files allocates separate heap space for each line of text, storing the address of each heap space in an array of pointers to char. The program in Listing 1 reads up to MAXLINES lines of text into memory and sorts them in ascending order using qsort. As the program reads each line, it calls malloc, a <stdlib.h> function, to get enough heap space to hold the line and its terminating null byte. The program stores the address that malloc returns in the array strings[]. This flexible storage mechanism is called a ragged array, because it only allocates the memory required by each line of text, as illustrated by Figure 1.
Although this scheme imposes an overhead penalty of one pointer per line, it's likely to be more efficient than a two-dimensional storage scheme with a large line length, as in Figure 2.
When you are through with dynamic memory, send its address as a parameter to free which makes the space available for reuse by any future calls to malloc. (For an explanation of the qsort function, see Code Capsules: "Sorting with qsort," CUJ, April, 1993, p. 107.)
Using the Heap in Standard C
The standard header <stdlib.h> declares four functions for using dynamic memory:
1. void *malloc(size_t siz) — Returns a pointer to the first of siz bytes. Used for allocating single objects.
2. void *calloc(size_t nelems, size_t elem_size) — Returns a pointer to nelems*elem_size bytes, initialized to zero. Used for allocating arrays of objects.
3. void *realloc(void *ptr, size_t siz) — Used to expand or shrink a heap allocation. ptr must have originated from a previous call to malloc or calloc, except that if ptr is null, the result is the same as malloc(siz). If there is enough space for the new allocation, realloc copies the original data to the new location, then returns the new address.
4. void free(void *ptr) — Makes previously allocated heap memory available for reuse. ptr must have been returned by a previous call to one of the above allocation functions. free(NULL) is a no-op.
The three allocation functions return a null pointer if the amount of memory requested is not available.
The program in Listing 2 and Listing 3 illustrates all four functions. This program extends the traditional argc/argv mechanism for reading command-line arguments by allowing you to specify files of arguments. Any program argument that begins with the '@' character names an indirect file, i.e., a file that contains more arguments. For example, the command
getargs @arg.datcauses the system to read file arg.dat for more arguments. Such command files can be nested (see Listing 4 through Listing 6) .The arglist function returns a pointer to a dynamically-sized, ragged array of strings, which is the fully-expanded list of program arguments. The function free_args frees all of the memory used in the creation of the array.
arglist uses calloc to dynamically allocate an array large enough to hold argc-1 arguments, the original number of arguments on the command line. arglist calls add to insert a new argument into the list. If the array is full, add calls realloc to increase the size of the array by a predetermined amount (CHUNK). add calls malloc to place all argument strings on the heap. The function expand processes indirect file arguments. Since indirect files can be nested, expand is a recursive function. If there are no indirect file arguments, then realloc never gets called.
Dynamic Data Structures
Dynamic memory allocation eases the creation of data structures that change at run time, such as lists and trees. Such data structures usually contain a pointer to their own type (sometimes called a self-referential pointer) to connect components of the structure together. For example, the definition of a linked-list node looks like this:
struct List { /* Put data components here: */ int num; /* etc. */ /* Here's the link: */ struct List *next; };Figure 3 depicts the topology of a linkedlist in memory.A null link means nothing follows. You call malloc and free respectively to create and delete nodes as needed at run time. A linked-list is especially efficient for insert and delete operations, since you don't have to shuffle elements to create or delete gaps like you do with arrays.
A binary search tree is a non-linear data structure suitable for storing ordered data for fast retrieval. Each node in the tree contains two self-referential pointers:
struct Tree { /* Data here */ char *data; /* etc. */ /* Links here */ struct Tree *left; struct Tree *right; };By convention, all items to the left of a tree node precede it in sort order, and the ones to the right sort after it. For example, the words "little boy blue come blow your horn" might result in the binary search tree shown in Figure 4. This arrangement makes the following binary search algorithm faster than a sequential search:
struct Tree *search(char *s, struct Tree *tp) { if (tp == NULL) return NULL; /* not found */ else if (strcmp(s,tp->data) > 0) return search(s,tp->right); else if (strcmp(s,tp->data) < 0) return search(s,tp->left); else return tp; /* found it */ }To print the items in sorted order, you do an end-order traversal of the tree, which recursively processes the left subtree, the root node, then the right subtree:
void print_tree(struct Tree *tp) { if (tp) { print_tree(tp->left); puts(tp->data); print_tree(tp->right); } }(If this puzzles you, review your favorite book on data structures. Mine is The Design And Analysis Of Computer Algorithms, by Aho, Hopcroft, and Ullman, Addison-Wesley, 1974.)The program in Listing 7 uses both of these data structures to create a cross-reference listing of words in a text file. Each word occupies a distinct node in a binary search tree. A list of line numbers accompanies each word to indicate where in the text the word appears. Sample output is in Listing 8.
Managing the Heap
Have you ever wondered how the heap management system knows how much memory to release when you call free(p)? Since you don't tell it, it must keep that information somewhere. In most systems that somewhere is right before the block pointed at by p, so instead of getting the block shown in Figure 5a, you're really getting an extra prepended block (usually a few bytes), as shown in Figure 5b. This overhead can be rather costly when you allocate a large number of small objects.
Another phenomenon that occurs is fragmentation. After allocating many objects and then deleting some, gaps appear in the heap, as shown in Figure 6. Although the heap contains enough combined space for another object, since the space is not contiguous, the allocation may fail.
A relatively painless way to sidestep these problems is to allocate a large pool of memory and manage it yourself. The cross-reference program in Listing 9 maintains a separate pool for the tree and list. The key to its use is the following union:
union List_shell { union List_shell *next; List dummy; };The function init_list_pool allocates an array of List_shell objects, which are the same size as a list node. init_list_pool then connects each object together in linked-list fashion, with free_list_ptr pointing to the first array element, as shown in Figure 7.No space is wasted because the List_shell structure overlays a List object. You replace calls to malloc in the original program with calls to get_list_node, which returns the next free object and updates free_list_ptr. All of the above applies to pools of tree nodes, of course.
Exercise
The program in Listing 9 has two limitations: 1) the pools are fixed in size, and 2) the code for the list and tree pools is identical, except for names and sizes of objects, which is a waste of good logic. Write a generic memory pool manager with the following interface:
Pool *pool_create(size_t elem_size, size_t init_alloc, size_t extent);Creates a pool to manage elements of size elem_size. Allocates init-alloc elements initially.
void *pool_get_elem(Pool *p);Returns a pointer to the next free element in the pool, and updates the free pointer. Increases the pool by extent elements as needed.
void pool_release_elem(Pool *p, void *elem);Returns an element to the pool.
void pool_free(Pool *p);Releases all the memory used by the pool.My solution will appear next month.
C++ and Memory Management
As an alternative to the memory management functions in <stdlib.h>, C++ offers the new and delete operators. To dynamically create a List node in C++, you could do this:
List *list_p = new List;which corresponds to a call to malloc. If you want an array of nodes instead, do this:
List *list_array_p = new List[LIST_CHUNK];which is similar to calloc, except you don't have to compute the number of bytes yourself. Since new is an operator, and not a function call, the compiler can compute the amount of memory needed, so you don't have to. When you are through with these objects, use the delete operator to release the dynamic memory:
delete list_p; // delete an object delete [] list_array_p; // delete an arrayIt is important to use the array version to free an array allocation. One important reason is that if the type of object you are deleting has a destructor, the system will call that destructor for each element of the array only if you use delete []. (See Listing 10 and Listing 11. )The class definition in Listing 12 encapsulates the functionality of the argument list processing program in Listing 3. The implementation in Listing 13 uses new and delete in place of malloc, calloc, realloc, and free, as appropriate. Since there is no equivalent of realloc in C++, Arglist::add() does an explicit new followed by a copy and a delete to accomplish the same thing. The sample program in Listing 14 shows how to create multiple Arglist objects.
Let Class Libraries Do The Work
The key feature of the standard C++ string class is memory management. The string class handles the details of dynamic memory so you don't have to. The version of the Arglist class in Listing 15 and 16 uses arrays of strings instead of arrays of pointers to char so I don't have to allocate individual strings on the heap myself. (Note: Listing 15 through Listing 18 are specific to the Borland C++ compiler.)
Better yet is to use a container class that implements dynamic arrays, like Borland's TArrayAsVector<> template class. The following statement from Listing 17 instantiates a dynamic array of strings:
TArrayAsVector<string> args;The constructor for TArrayAsVector requires an upper bound, lower bound, and reallocation amount, so I pass these in the member initialization list in Listing 18:
Arglist::Arglist(/* ... */) : args(arg_count,0,CHUNK)The following TArrayAsVector<class T> member functions do everything I need:
size_t GetItemsInContainer(); T operator[](size_t); int Add(const T&);In order to use the string or dynamic array implementations, you only need to change the header file included in Listing 14.
Summary
Dynamic memory allocation provides the support that flexible data structures require. You may need to do your own heap management, however, to avoid undue overhead or memory fragmentation. Next month I'll explore memory management in C++ more deeply, including how to handle out-of-memory exceptions and overloading new and delete both globally and on a per-class basis.
Figure 1 A ragged array of strings
Figure 2 An array of strings implemented as a 2-D array of characters
Figure 3 Topology of a linked list
Figure 4 A binary search tree for the phrase "little boy blue come blow your horn"
Figure 5 Allocation of memory (a) typically results in prepended bytes (b)
Figure 6 Heap fragmentation resulting from multiple allocation and deallocation
Figure 7 A memory pool that minimizes waste of space
Listing 1 A sort program that uses ragged arrays
/* sort.c: Sort strings */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #define MAXLINES 1024 static int scomp(const void *, const void *); main(int argc, char *argv[]) { int i, n; char *strings[MAXLINES], buf[BUFSIZ]; if (argc > 1) assert(freopen(argv[1],"r",stdin)); /* Read lines into dynamic memory */ for (n = 0; n < MAXLINES && fgets(buf,BUFSIZ,stdin); ++n) { strings[n]: malloc(strlen(buf)+1); assert(strings[n]); strcpy(strings[n],buf); } qsort(strings, n, sizeof strings[0], scomp); /* Free memory */ for (i = 0; i < n; ++i) { fputs(strings[i],stdout); free(strings[i]); } return 0; } static int scomp(const void *p1, const void *p2) { char *a = * (char **) p1; char *b = * (char **) p2; return strcmp(a,b); } /* End of File */
Listing 2 A program that reads arguments from files
/* getargs.c: Reads files of arguments */ #include <stdio.h> extern char**arglist(int,char**,int *); extern void free_arglist(int,char **); main(int argc, char *argv[]) { int i, nargs; char **args = arglist(--argc,++argv,&nargs); for (i = 0; i < nargs; ++i) printf("%d: %s\n",i,args[i]); free_arglist(nargs,args); return 0; } /* Sample Execution: c:> getargs @arg.dat 0: little 1: lamb 2: where 3: no 4: one 5: along 6: came 7: a 8: spider 9: has 10: gone 11: before 12: little 13: lamb */ /* End of File */
Listing 3 Supporting functions for the program in Listing 2
/* arglist.c: Recursively reads arguments from files */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #define CHUNK 10 /* Reallocation amount */ static char **args; /* The argument list */ static int nleft; /* Unused argument slots */ static int nargs; /* Number of arguments */ /* Private Functions */ static void expand(FILE *f); static void add(char *arg); char **arglist(int old_nargs, char **old_args, int *new_nargs) { int i; /* Initial Allocation */ args= calloc(old_nargs,sizeof(char *)); assert(args); nleft = old_nargs; nargs = 0; /* Process each command-line argument */ for (i = 0; i < old_nargs; ++i) if (old_args[i][0] == '@') { /* Open file of arguments */ FILE *f = fopen(old_args[i]+1,"r"); if(f) { expand(f); fclose(f); } } else add(old_args[i]); *new_nargs = nargs; return args; } void free_arglist(int n, char **av) { int i; for (i = 0; i <n; ++ i) free(av[i]); free(av); } static void expand(FILE *f) { char token[BUFSIZ]; while (fscanf(f,"%s",token) == 1) if (token[0] == '@') { FILE *g = fopen(token+1,"r"); if (g) { expand(g); fclose(g); } } else add(token); } static void add(char *arg) { if (nleft == 0) { /* Expand argument list */ args = realloc(args,(nargs+CHUNK) * sizeof(char *)); assert(args); nleft = CHUNK; } /* Allocate space for and store argument */ args[nargs] = malloc(strlen(arg) + 1); assert(args[nargs]); strcpy(args[nargs++], arg); --nleft; } /* End of File */
Listing 4 Input file arg.dat
little lamb @arg2.dat little lamb
Listing 5 Input file arg2.dat
where no one @arg3.dat has gone before
Listing 6 Input file arg3.dat
along came a spider
Listing 7 A program that uses a binary tree and linked lists to cross-reference words in a text file
/* xref.c: Prints line numbers where each word occurs */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #define WORD_WIDTH 15 /* Node structure for each list of line numbers */ struct* List { int lnum: struct List *next; }; typedef struct List List; /* Node structure for tree of distinct words */ struct Tree { char word[WORD_WIDTH]; List *lstptr; struct Tree *left,*right; }; typeder struct Tree Tree; /* Tree and list functions */ Tree *addword(Tree *, char *); List *addline(List *, int): Tree *find_node(Tree *, char *); void print_tree(Tree *t); void print_list(List *); in* ndistinct = 0; main(int argc, char *argy[]) { char linebuf[BUFSIZ]; Tree *words = NULL; int lineno = 0; /* Do optional input redirection */ if (argc > 1) assert(freopen(argv[1],"r",stdin)); /* 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); return 0; } Tree *addword(Tree *tp, char *word) { if (tp == NULL) { /* Add new entry */ ++ndistinct; tp = malloc(sizeof(Tree)); 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 = malloc(sizeof(List)); 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) { const 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; } /* End of File */
Listing 8 The result of executing xref.c on its own source
No. of distinct words: 107 Add : 76 Append : 95 BUFSIZ : 37 46 Do : 41 Binary : 138 INDENT : 123 132 Inorder : 112 List : 10 13 15 21 28 31 91 96 120 NULL : 38 46 55 62 74 80 81 93 99 110 127 131 . . . (This portion not shown) . . . tp : 72 74 78 79 80 81 83 84 85 86 88 108 110 113 114 115 116 136 139 140 141 142 144 traversal : 112 tree : 17 typedef : 15 24 v : 49 void : 30 31 108 120 where : 1 while : 46 55 word : 1 20 54 72 79 83 84 85 86 114 138 139 141 wordptr : 48 55 59 60 words : 17 38 59 60 67 68 xref : 1
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 */
Listing 10 Demonstrates behavior of operator delete
#include <iostream.h> class T { public: T() {cout << "Default constructor" << end1:} ~T(){cout << "Destructor" << endl;} }; main() { T *p = new T[3]; delete [] p; return 0; } /* Output: Default constructor Default constructor Default constructor Destructor Destructor Destructor */ /* End of File */
Listing 11 Demonstrates why you shouldn't use operator delete with arrays
#include <iostream. h> class T { public: T() {cout << "Default constructor" << endl;} ~T(){cout << "Destructor" << endl;} }; main() { T *p = new T[3]; delete p; /* CHANGED */ return 0; } /* Output: Default constructor Default constructor Default constructor Destructor Null Pointer Assignment */ /* End of File */
Listing 12 Definiton of class Arglist — a class to process argument lists
#include <stddef.h> class Arglist { public: Arglist(size_t, char **); ~Arglist(); size_t count() const; const char * const operator[](size_t) const; private: enum (CHUNK = 10}: char **args; size_t used; size_t available; void expand(char *); void add(char *); }; inline size_t Arglist::count() const { return used; } inline const char * const Arglist::operator[](sizet_i) const { return args[i]; } /* End of File */
Listing 13 Implementation of class Arglist
#include <fstream.h> #include <string.h> #include "arglist.h" Arglist::Arglist(size_t arg_count, char **arg_vec) { args = new char*[arg_count]; available = argcount; used = 0; // INVARIANT: available+used == amount allocated for (int i = 0; i < arg_count; ++i) if (arg_vec[i][0] == '@') expand(arg_vec[i]+1); else add(arg_vec[i]); } Arglist::~Arglist() { for (int i = 0; i < used; ++i) delete [] args[i]; delete [] args; } void Arglist::expand(char *fname) { ifstream f(fname); const size_t BUFSIZ: 64; char token[BUFSIZ]; while (f >> token) if (token[0] == '@') expand(token+1); else add(token); } void Arglist::add(char *arg) { if (!available) { /* Grow argument list */ char **new_args = new char*[used + CHUNK]; for (int i = 0; i < used; ++i) new_args[i] = args[i]; delete [] args; args = new_args; available = CHUNK; } /* Allocate space for and store argument */ args[used] = new char[strlen(arg) + 1]; strcpy(args[used++], arg); --available; } /* End of File */
Listing 14 A program that creates multiple Arglist objects
#include <iostream.h> #include "arglist.h" main(int argc, char *argv[]) { Arglist args(--argc,++argv); for (int i = 0; i < args.count(); ++i) cout << i << ": "<< args[i] << endl; cout << endl; char *more_args[]: {"@arg2.dat"}; Arglist args2(1,more_args); for (i = 0; i < args2.count();++i) cout << i << ": "<< args2[i] << endl; return 0; } /* Sample Execution: 0: little 1: lamb 2: where 3: no 4: one 5: along 6: came 7: a 8: spider 9: has 10: gone 11: before 12: little 13: lamb 0: where 1: no 2: one 3: along 4: came 5: a 6: spider 7: has 8: gone 9: before */ /* End of File */
Listing 15 An Arglist class that uses arrays of string objects
#include <stddef.h> #include <cstring.h> class Arglist { public: Arglist(size_t, char **); ~Arglist(); size_t count() const; const string& operator[](size_t) const; private: enum {CHUNK: 10}; string *args; size_t used; size_t available: void expand(char *); void add(char *); }; inline size_t Arglist::count() const { return used; } inline const string& Arglist::operator[](size_t i) const { return args[i]; } /* End of File */
Listing 16 Out-of-line member Functions of Arglist in Listing 15
#include <fstream.h> #include <cstring.h> #include "arglist2.h" Arglist::Arglist(size_t arg_count, char **arg_vec) { args = new string[arg_count]; available = arg_count; used = 0; // INVARIANT: available+used == amount allocated for (int i = 0; i < arg_count; ++i) if (arg_vec[i][0] := '@') expand(arg_vec[i]+1); else add(arg_vec[i]); } Arglist::~Arglist() { delete [] args; } void Arglist::expand(char *fname) { ifstream f(fname); const size_t BUFSIZ: 64; char token[BUFSIZ]; while (f >> token) if (token[0] == '@') expand(token+1); else add(token); } void Arglist::add(char *arg) { if (!available) { /* Grow argument list */ string *new_args: new string[used + CHUNK]; for (int i = 0; i < used; ++i) new_args[i] = args[i]; args = new args; available = CHUNK; } args[used++]: arg; --available; } /* End of File */
Listing 17 An Arglist class that uses a container class
#include <stddef.h> #include <cstring.h> #include <classlib/arrays.h> class Arglist { public: Arglist(size_t, char **); size_t count() const; const string& operator[](size_t) const; private: enum {CHUNK = 10}; TArrayAsVector<string> args; void expand(char *); void add(char *); }; inline size_t Arglist::count() const { return args.GetItemsInContainer(); } inline const string& Arglist::operator[](size_t i) const { return args[i]; } inline void Arglist::add(char *arg) { args.Add(string(arg)); } /* End of File */
Listing 18 Out-of-line member functions for the Arglist class in Listing 17
#include <fstream.h> #include "arglist3.h" Arglist::Arglist(size_t arg_count, char **arg_vec) : args(arg_count,0,CHUNK) { for (int i = 0; i < arg_count; ++i) if (arg_vec[i][0] == '@') expand(arg_vec[i]+1); else add(arg_vec[i]); } void Arglist::expand(char *fname) { ifstream f(fname); const size_t BUFSIZ = 64; char token[BUFSIZ]; while (f >> token) if (token[0] == '@') expand(token+1); else add(token); } /* End of File */