2.9 Structure of Static Objects

Static variables are commonly used in the C implementation of a data structure as an object. The data structure and all the functions that access it are placed in a single source file, and the data structure is defined outside any function. The data structure has the static attribute, giving it internal linkage: it is private to that source file. Any references to the data structure outside the file are made through the access functions ( methods , in object-oriented terminology) defined within the file. The actual details of the data structure should be invisible to the outside world so that a change in the internal implementation does not require a change to the calling program. You can often make an object thread-safe by placing locking mechanisms in its access functions without affecting outside callers .

This section develops an implementation of a list object organized according to the type of static structure just described. Each element of the list consists of a time and a string of arbitrary length. The user can store items in the list object and traverse the list object to examine the contents of the list. The user may not modify data that has already been put in the list. This list object is useful for logging operations such as keeping a list of commands executed by a program.

The requirements make the implementation of the list both challenging and interesting. Since the user cannot modify data items once they are inserted, the implementation must make sure that no caller has access to a pointer to an item stored in the list. To satisfy this requirement, the implementation adds to the list a pointer to a copy of the string rather than a pointer to the original string. Also, when the user retrieves data from the list, the implementation returns a pointer to a copy of the data rather than a pointer to the actual data. In the latter case, the caller is responsible for freeing the memory occupied by the copy.

The trickiest part of the implementation is the traversal of the list. During a traversal, the list must save the current position to know where to start the next request. We do not want to do this the way strtok does, since this approach would make the list object unsafe for multiple simultaneous traversals. We also do not want to use the strtok_r strategy, which requires the calling program to provide a location for storing a pointer to the next entry in the list. This pointer would allow the calling program to modify entries in the list, a feature we have ruled out in the specification.

We solve this problem by providing the caller with a key value to use in traversing the list. The list object keeps an array of pointers to items in the list indexed by the key. The memory used by these pointers should be freed or reused when the key is no longer needed so that the implementation does not consume unnecessary memory resources.

Program 2.6 shows the listlib.h file containing the prototypes of the four access functions: accessdata , adddata , getdata and freekey . The data_t structure holds a time_t value ( time ) and a pointer to a character string of undetermined length ( string ). Programs that use the list must include the listlib.h header file.

Program 2.6 listlib.h

The header file listlib.h .

 #include <time.h> typedef struct data_struct {      time_t time;      char *string; } data_t; int accessdata(void); int adddata(data_t data); int freekey(int key); int getdata(int key, data_t *datap); 

Program 2.7 shows an implementation of the list object. The adddata function inserts a copy of the data item at the end of the list. The getdata function copies the next item in the traversal of the list into a user-supplied buffer of type data_t . The getdata function allocates memory for the copy of the string field of this data buffer, and the caller is responsible for freeing it.

The accessdata function returns an integer key for traversing the data list. Each key value produces an independent traversal starting from the beginning of the list. When the key is no longer needed, the caller can free the key resources by calling freekey . The key is also freed when the getdata function gives a NULL pointer for the string field of *datap to signify that there are no more entries to examine. Do not call freekey once you have reached the end of the list .

If successful, accessdata returns a valid nonnegative key. The other three functions return 0 if successful. If unsuccessful , these functions return “1 and set errno .

Program 2.7 listlib.c

A list object implementation .

 #include <errno.h> #include <stdlib.h> #include <string.h> #include "listlib.h" #define TRAV_INIT_SIZE 8 typedef struct list_struct {      data_t item;      struct list_struct *next; } list_t; static list_t endlist; static list_t *headptr = NULL; static list_t *tailptr = NULL; static list_t **travptrs = NULL; static int travptrs_size = 0; int accessdata(void) {              /* return a nonnegative key if successful */    int i;    list_t **newptrs;    if (headptr == NULL) {             /* can't access a completely empty list */       errno = EINVAL;       return -1;    }    if (travptrs_size == 0) {                               /* first traversal */       travptrs = (list_t **)calloc(TRAV_INIT_SIZE, sizeof(list_t *));       if (travptrs == NULL)     /* couldn't allocate space for traversal keys */          return -1;       travptrs[0] = headptr;       travptrs_size = TRAV_INIT_SIZE;       return 0;    }    for (i = 0; i < travptrs_size; i++) {    /* look for an empty slot for key */       if (travptrs[i] == NULL) {          travptrs[i] = headptr;          return i;       }    }    newptrs = realloc(travptrs, 2*travptrs_size*sizeof(list_t *));    if (newptrs == NULL)        /* couldn't expand the array of traversal keys */       return -1;    travptrs = newptrs;    travptrs[travptrs_size] = headptr;    travptrs_size *= 2;    return travptrs_size/2; } int adddata(data_t data) {   /* allocate node for data and add to end of list */    list_t *newnode;    int nodesize;    nodesize = sizeof(list_t) + strlen(data.string) + 1;    if ((newnode = (list_t *)(malloc(nodesize))) == NULL) /* couldn't add node */       return -1;    newnode->item.time = data.time;    newnode->item.string = (char *)newnode + sizeof(list_t);    strcpy(newnode->item.string, data.string);    newnode->next = NULL;    if (headptr == NULL)       headptr = newnode;    else       tailptr->next = newnode;    tailptr = newnode;    return 0; } int getdata(int key, data_t *datap) { /* copy next item and set datap->string */    list_t *t;    if ( (key < 0)  (key >= travptrs_size)  (travptrs[key] == NULL) ) {       errno = EINVAL;       return -1;    }    if (travptrs[key] == &endlist) { /* end of list, set datap->string to NULL */       datap->string = NULL;       travptrs[key] = NULL;       return 0;       /* reaching end of list natural condition, not an error */    }    t = travptrs[key];    datap->string = (char *)malloc(strlen(t->item.string) + 1);    if (datap->string == NULL) /* couldn't allocate space for returning string */       return -1;    datap->time = t->item.time;    strcpy(datap->string, t->item.string);    if (t->next == NULL)       travptrs[key] = &endlist;    else       travptrs[key] = t->next;    return 0; } int freekey(int key) {                /* free list entry corresponding to key */    if ( (key < 0)  (key >= travptrs_size) ) {           /* key out of range */       errno = EINVAL;       return -1;    }    travptrs[key] = NULL;    return 0; } 

The implementation of Program 2.7 does not assume an upper bound on the length of the string field of data_t . The adddata function appends to its internal list structure a node containing a copy of data . The malloc function allocates space for both the list_t and its string data in a contiguous block. The only way that adddata can fail is if malloc fails. The accessdata function also fails if there are not sufficient resources to provide an additional access stream. The freekey function fails if the key passed is not valid or has already been freed. Finally, getdata fails if the key is not valid. Reaching the end of a list during traversal is a natural occurrence rather than an error. The getdata function sets the string field of *datap to NULL to indicate the end.

The implementation in Program 2.7 uses a key that is just an index into an array of traversal pointers. The implementation allocates the array dynamically with a small initial size. When the number of traversal streams exceeds the size of the array, accessdata calls realloc to expand the array.

The data structures for the object and the code for the access functions of listlib are in a single file. Several later projects use this list object or one that is similar. In an object representation, outside callers should not have access to the internal representation of the object. For example, they should not be aware that the object uses a linked list rather than an array or other implementation of the abstract data structure.

The implementation of Program 2.7 allows nested or recursive calls to correctly add data to the list or to independently traverse the list. However, the functions have critical sections that must be protected in a multithreaded environment. Sections 13.2.3 and 13.6 discuss how this can be done.

Exercise 2.21

What happens if you try to access an empty list in Program 2.7?

Answer:

The accessdata returns “1, indicating an error.

Program 2.8 executes commands and keeps an internal history, using the list data object of Program 2.7. The program takes an optional command-line argument, history . If history is present, the program outputs a history of commands run thus far whenever the program reads the string "history" from standard input.

Program 2.8 calls runproc to run the command and showhistory to display the history of commands that were run. The program uses fgets instead of gets to prevent a buffer overrun on input. MAX_CANON is a constant specifying the maximum number of bytes in a terminal input line. If MAX_CANON is not defined in limits.h , then the maximum line length depends on the particular device and the program sets the value to 8192 bytes.

Program 2.9 shows the source file containing the runproc and showhistory functions. When runproc successfully executes a command, it adds a node to the history list by calling adddata . The showhistory function displays the contents of each node in the list by calling the getdata function. After displaying the string in a data item, showhistory function frees the memory allocated by the getdata call. The showhistory function does not call freekey explicitly because it does a complete traversal of the list.

Program 2.8 keeplog.c

A main program that reads commands from standard input and executes them .

 #include <limits.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #ifndef MAX_CANON #define MAX_CANON 8192 #endif int runproc(char *cmd); void showhistory(FILE *f); int main(int argc, char *argv[]) {    char cmd[MAX_CANON];    int history = 1;    if (argc == 1)       history = 0;    else if ((argc > 2)  strcmp(argv[1], "history")) {       fprintf(stderr, "Usage: %s [history]\n", argv[0]);       return 1;    }    while(fgets(cmd, MAX_CANON, stdin) != NULL) {       if (*(cmd + strlen(cmd) - 1) == '\n')           *(cmd + strlen(cmd) - 1) = 0;       if (history && !strcmp(cmd, "history"))          showhistory(stdout);       else if (runproc(cmd)) {          perror("Failed to execute command");          break;       }    }    printf("\n\n>>>>>>The list of commands executed is:\n");    showhistory(stdout);    return 0; } 

The runproc function of Program 2.9 calls the system function to execute a command. The runproc function returns 0 if the command can be executed. If the command cannot be executed, runproc returns “1 with errno set.

The system function passes the command parameter to a command processor for execution. It behaves as if a child process were created with fork and the child process invoked sh with execl .

  SYNOPSIS  #include <stdlib.h>   int system(const char *command);  POSIX:CX  

If command is NULL , the system function always returns a nonzero value to mean that a command language interpreter is available. If command is not NULL , system returns the termination status of the command language interpreter after the execution of command . If system could not fork a child or get the termination status, it returns “1 and sets errno . A zero termination status generally indicates successful completion.

Program 2.9 keeploglib.c

The file keeploglib.c .

 #include <stdio.h> #include <stdlib.h> #include "listlib.h" int runproc(char *cmd) { /* execute cmd; store cmd and time in history list */    data_t execute;    if (time(&(execute.time)) == -1)       return -1;    execute.string = cmd;    if (system(cmd) == -1)           /* command could not be executed at all */       return -1;    return adddata(execute); } void showhistory(FILE *f) {        /* output the history list of the file f */    data_t data;    int key;    key = accessdata();    if (key == -1) {       fprintf(f, "No history\n");       return;    }    while (!getdata(key, &data) && (data.string != NULL)) {       fprintf(f, "Command: %s\nTime: %s\n", data.string, ctime(&(data.time)));       free(data.string);    } }