Add Book to My BookshelfPurchase This Book Online

Chapter 2 - Utility Routines

UNIX Systems Programming for SVR4
David A. Curry
 Copyright © 1996 O'Reilly & Associates, Inc.

Dynamic Memory Allocation
Dynamic memory allocation allows a program to allocate memory for data storage as needed. By using dynamic memory allocation instead of pre-allocated arrays, programs can be more flexible in the amount of data they can handle and more efficient by using only the memory they need.
The basic dynamic memory functions provided by all versions of UNIX are malloc and free:
      #include <stdlib.h>
      void *malloc(size_t size);
      void free(void *ptr);
malloc attempts to allocate size bytes of memory and returns a pointer to the allocated block, or a null pointer if the request could not be satisfied. The memory is aligned for any use, meaning that any data type can be stored in it (many hardware architectures are picky about certain data types, especially floating-point numbers, beginning at addresses that are multiples of some power of two, usually four).
free releases memory that was previously allocated by malloc or one of the other memory allocation functions described later in this section. The memory is not actually released by the process (removed from its address space), but it is marked as available for reuse by future calls to the allocation functions.
After calling free, the memory pointed to by ptr is no longer guaranteed to be valid, and the results of accessing this memory are undefined. Nevertheless, you will often see code fragments such as this used to free dynamically allocated linked lists:
while (ptr != NULL) {
     free(ptr);
     ptr = ptr->next;
}
In most implementations of malloc and free, this works acceptably, because free just performs bookkeeping tasks and doesn't actually do anything to the freed memory. However, the previous example is technically incorrect, and does not work in certain implementations. Here is a more portable (and correct) way to do the same thing:
      while (ptr != NULL) {
          nextptr = ptr->next;
          free(ptr);
          ptr = nextptr;
      }
When allocating an array of items, you can use the calloc function instead of malloc:
      #include <stdlib.h>
      void *calloc(size_t nelem, size_t elsize);
calloc allocates nelem contiguous elements of memory, each of size elsize and returns a pointer to the first element, or a null pointer if the request could not be satisfied. This is identical to calling malloc as follows:
      ptr = malloc(nelem * elsize);
Using calloc would be pointless, except that calloc initializes the memory it allocates to zero, a service not performed by malloc. (Initialize to zero means all the bits are set to zero; this is not necessarily the same thing as 0 or 0.0 as far as the variable's data type is concerned.)
To increase the size of a previously allocated memory segment, use the realloc function:
      #include <stdlib.h>
      void *realloc(void *ptr, size_t size);
ptr is a pointer to a segment of memory returned by a previous call to malloc, calloc, or realloc, and size is the desired new size, in bytes. realloc returns a pointer to the new memory segment, or a null pointer if the request cannot be satisfied. Note that in order to satisfy a request, realloc may have to copy the existing block pointed to by ptr to a new (larger) area in memory. This means that after a call to realloc, any variables pointing into the old block may be invalid.
For the specific purpose of saving a string in dynamically allocated memory, most modern UNIX systems provide a function called strdup:
      #include <string.h>
      char *strdup(const char *s);
strdup allocates a block of memory large enough to hold s, copies s into it, and returns a pointer to the saved string, or a null pointer if no memory could be allocated. This is particularly useful for saving strings of arbitrary length (such as those entered in response to prompts from the program) without having to preallocate many arrays of the largest possible size. If you are writing a program that has to be portable to older UNIX systems, you can include the following implementation of strdup for portability:
      #include <string.h>
      char *
      strdup(char *s)
      {
          char *p;
          if ((p = (char *) malloc(strlen(s) + 1)) != NULL)
              strcpy(p, s);
          return(p);
      }
Look at Examples 2-1 and Example 2-2 for a moment, and notice that they both work on only a predefined number of lines (the NSTRINGS constant). This is fine for the examples in this chapter, which used fairly small files. But, if you were to use these programs on larger files, they would only sort the first NSTRINGS lines of the file, and not even read in the rest of the file. Up to a point, you can simply increase the value of NSTRINGS to handle larger files, but after a while this becomes too cumbersome. It would be extremely inefficient to allocate enough memory to handle a 1,000,000-line file every time, even when you are normally sorting files that are much smaller.
Example 2-10 shows a reworked version of Example2-2 that uses dynamic memory allocation to allow the program to work on files of any arbitrary size (up to the maximum amount of memory available to a single program on your machine).
Example 2-10:  bsort-malloc
#include <stdlib.h>
#include <string.h>
void    bubbleSort(char **, int);
void    outputLine(char *);
char    *inputLine(void);
int
main(int argc, char **argv)
{
    char *line;
    char **strptrs = NULL;
    int n, nstrings, nstrptrs;
    nstrings = 0;
    nstrptrs = 0;
    /*
     * For each line in the input...
     */
    while ((line = inputLine()) != NULL) {
        /*
         * If we're full up, allocate some more pointers.
         */
        if (nstrings == nstrptrs) {
            if (nstrptrs == 0) {
                nstrptrs = 8;
                strptrs = malloc(nstrptrs * sizeof(char *));
            }
            else {
                nstrptrs += 8;
                strptrs = realloc(strptrs, nstrptrs * sizeof(char *));
            }
            if (strptrs == NULL) {
                outputLine("out of memory.");
                exit(1);
            }
        }
        /*
         * Save a pointer to the line, stored in dynamically
         * allocated memory.
         */
        strptrs[nstrings++] = strdup(line);
    }
    /*
     * Sort the strings.
     */
    bubbleSort(strptrs, nstrings);
    /*
     * Print the strings and free the memory.
     */
    for (n = 0; n < nstrings; n++) {
        outputLine(strptrs[n]);
        free(strptrs[n]);
    }
    free(strptrs);
    exit(0);
}
/*
* bubbleSort - implementation of the standard bubble sort algorithm.
*/
void
bubbleSort(char **strings, int nstrings)
{
    int i, j;
    char *tmp;
    int notdone;
    j = nstrings;
    notdone = 1;
    while (notdone) {
        notdone = 0;
        j = j - 1;
        for (i = 0; i < j; i++) {
            /*
             * Use strcmp() to compare the strings
             * alphabetically.
             */
            if (strcmp(strings[i], strings[i+1]) > 0) {
                tmp = strings[i+1];
                strings[i+1] = strings[i];
                strings[i] = tmp;
                notdone = 1;
            }
        }
    }
}
As each line is read in, it is saved in dynamically allocated memory with a call to strdup. The return values from strdup are saved in dynamically allocated memory, too. Initially, an array of eight pointers is allocated with malloc, and then as more pointers are needed, they are allocated eight more at a time with realloc. After sorting the lines, the strings allocated by strdup are freed as they are printed out, and then the array of pointers is freed. (It is not necessary to free memory before exiting, because the operating system does it automatically, but it is aesthetically pleasing from a programming style viewpoint to do so.)
Porting Notes
Before ANSI C, most versions of malloc, calloc, and realloc were declared to return pointers of type char * instead of type void *. This can cause portability problems if you declare the functions yourself; it is always better to use the appropriate include file instead and then typecast as appropriate. Unfortunately, before the ANSI C standard specified that these functions are declared in stdlib.h, various vendors used different include files to declare them. Often a malloc.h exists, but if it doesn't, you may have to search for the proper file.
Another memory allocation function, alloca, deserves special mention here:
   void *alloca(size_t size);
Like malloc, alloca returns a pointer to size bytes of memory, or a null pointer if the memory is unavailable. However, unlike malloc, which allocates the memory from the program's data segment, alloca allocates it from the program's stack segment. Thus, when the current function returns, the memory is automatically freed by being popped off the stack. This simplifies bookkeeping for programs that allocate large amounts of memory in numerous places. Unfortunately, it is also a portability nightmare. The implementation of alloca is very machine-, compiler-, and, most of all, system-dependent. Some hardware architectures cannot implement it all. For this reason, alloca should never be used by a program that must be portable to many different systems.

Previous SectionNext Section
Books24x7.com, Inc © 2000 –  Feedback