Assignment #5

Intermediate C Programming

UW Experimental College


Assignment #5

Handouts:

Assignment #5
Assignment #4 Answers
Class Notes, Chapter 21
Class Notes, Chapter 22

Exercises:

  1. Bit-masks (such as the attrs field we added to the object structure last time) are a perfectly reasonable data structure to use for keeping track of a relatively small, well-defined set of attributes. However, as we've already seen, once we start trying to keep track of the qualities and states of various objects in the game, we quickly find ourselves using a welter of attributes. There aren't enough bits in an int (or even a long int) to keep track of all the attributes we might eventually want. Furthermore, it becomes a nuisance to have to #define a new mask in game.h every time we invent a new attribute, and to add another if clause to parsedatafile in io.c to map the attribute line in the data file (a string) to the corresponding mask constant.

    Therefore, after using it for only a week or two, we're going to rip out the bitmask-based attribute scheme and replace it with something more open-ended and flexible. Any object may have a list of attributes, with each attribute represented by an arbitrary string. We'll write a few functions for setting, testing, and clearing these attributes, so that they'll be convenient for the rest of the program to manipulate. While we're at it, we'll get some more practice doing dynamic memory allocation and using linked lists.

    Since, under this new scheme, an object may have arbitrarily many attributes, and since each attribute will be an arbitrary-length string, we won't be able to use fixed-size data structures. We'll use dynamically-allocated ones, instead, which means that we'll be calling malloc a lot. A cardinal rule of using malloc is that you must check its return value to make sure that it did not return a null pointer. If the program ever runs out of memory, or some other problem causes malloc to return a null pointer, and if your program accidentally uses that null pointer as if it points to usable memory, your program can and will fail in mysterious ways. If, on the other hand, you check malloc's return value, and print a distinct error message when it fails, you'll at least know more or less exactly what the problem is.

    If you have many places in your program where you're doing dynamic allocation, it may become a nuisance to have to check return values at all of those places. Therefore, a popular strategy is to implement a wrapper function around malloc. The one we'll be using looks like this:
    #include <stdio.h>
    #include <stdlib.h>
    #include "chkmalloc.h"
    
    void *
    chkmalloc(size_t sz)
    {
    void *ret = malloc(sz);
    if(ret == NULL)
    	{
    	fprintf(stderr, "Out of memory\n");
    	exit(EXIT_FAILURE);
    	}
    return ret;
    }
    
    All chkmalloc does is call malloc, check its return value, and return it if it's not NULL. (size_t is an ANSI C type for representing the sizes of objects, and void * is the generic pointer type which malloc and related functions return.) But since chkmalloc never returns a null pointer, its caller never has to check, but can begin using the pointer immediately. chkmalloc can guarantee never to return a null pointer not because it implements some kind of a magical infinite memory space, but rather because it simply exits, after printing an error message, if malloc fails. Thus, all tests for malloc failures (and our strategy for dealing with those failures) are centralized in chkmalloc().

    The ``strategy'' of printing an error message and exiting when malloc fails is an expedient one, but it would not be ideal for all programs. It assumes that (a) an actual out-of-memory condition is unlikely, and (b) the program won't have any cleanup to do and won't mind if it's summarily terminated. This strategy would not, for example, be acceptable for a text editor: the editor might use arbitrary amounts of memory when editing a large file, and the user would certainly not appreciate being dumped out, without having the opportunity to save any work, after trying to add (say) the 1,000,001st character to a huge file which had just been typed in from scratch over many hours. However, for our little adventure game, this is a perfectly adequate strategy, for now at least.

    You might argue that, if out-of-memory conditions are unlikely, we might as well skip chkmalloc, call malloc directly, and not check its return value. This would be a bad idea, because while actual out-of-memory conditions may be rare, other kinds of malloc failures are not so rare, especially in a program under development. If you misuse the memory which malloc gives you, perhaps by asking for 16 bytes of memory and then writing 17 characters to it (and this is all too easy to do), malloc tends to notice, or at least to be broken by your carelessness, and will return a null pointer next time you call it. When malloc returns a null pointer for this reason, it can be difficult to track down the actual error (because it typically occurred somewhere in your code before the call to malloc that failed), but if we blindly used the null pointer which malloc returned to us, we'd only defer the eventual crash even farther, and it might be quite mysterious, much more so than a definitive ``out of memory'' message. Therefore, using a wrapper function like chkmalloc is a definite improvement, because we get error messages as soon as malloc fails, and we don't have to scatter tests all through our code to get them.

    All we do have to do, anywhere we call chkmalloc, is #include "chkmalloc.h", which contains chkmalloc's external function prototype declaration, as well as a second convenience function which we'll meet in a minute:
    extern void *chkmalloc(size_t);
    extern char *chkstrdup(char *);
    
    Both chkmalloc.c and chkmalloc.h are in the week5 subdirectory of the source directories.

    With chkmalloc in hand, we can begin implementing the new attribute scheme. First, we define this list structure:
    struct list
    	{
    	char *item;
    	struct list *next;
    	};
    


    Then, we rewrite the object structure to use a list, instead of an unsigned int, for attrs:
    struct object
    	{
    	char name[MAXNAME];
    	struct list *attrs;
    	struct object *contents;	/* contents (if container) */
    	struct object *lnext;		/* next in list of contained objects */
    					/* (i.e. in this object's container) */
    	char *desc;			/* long description */
    	};
    #define Iscontainer(o) hasattr(o, "container")
    #define Isopen(o) hasattr(o, "open")
    
    Notice that we have also rewritten the Iscontainer() and Isopen() macros, to use the new hasattr function, which we'll see in a minute. (This suggests another benefit of having used those macros: none of the code that ``called'' Iscontainer() or Isopen() will need rewriting. As we'll see, though, the code that has been using raw bit operations to test and set the other attributes will need rewriting.) The old attribute bits (CONTAINER, OPEN, etc.) are no longer needed.

    We rewrite the newobject function in object.c slightly, to initialize attrs to a null pointer:
    struct object *
    newobject(char *name)
    {
    struct object *objp;
    
    if(nobjects >= MAXOBJECTS)
    	{
    	fprintf(stderr, "too many objects\n");
    	exit(1);
    	}
    
    objp = &objects[nobjects++];
    
    strcpy(objp->name, name);
    objp->lnext = NULL;
    objp->attrs = NULL;
    objp->contents = NULL;
    objp->desc = NULL;
    
    return objp;
    }
    
    (Actually, we could have left it as objp->attrs = 0, because 0 is also an acceptable null pointer constant.)

    Now, here are the three new functions for testing, setting, and clearing (``unsetting'') attribute strings:
    /* see if the object has the attribute */
    
    int
    hasattr(struct object *objp, char *attr)
    {
    struct list *lp;
    
    for(lp = objp->attrs; lp != NULL; lp = lp->next)
    	{
    	if(strcmp(lp->item, attr) == 0)
    		return TRUE;
    	}
    
    return FALSE;
    }
    
    /* set an attribute of an object (if it's not set already) */
    
    void
    setattr(struct object *objp, char *attr)
    {
    struct list *lp;
    
    if(hasattr(objp, attr))
    	return;
    
    lp = chkmalloc(sizeof(struct list));
    
    lp->item = chkstrdup(attr);
    lp->next = objp->attrs;
    objp->attrs = lp;
    }
    
    /* clear an attribute of an object */
    
    void
    unsetattr(struct object *objp, char *attr)
    {
    struct list *lp;
    struct list *prevlp;
    
    for(lp = objp->attrs; lp != NULL; lp = lp->next)
    	{
    	if(strcmp(lp->item, attr) == 0)
    		{
    		if(lp == objp->attrs)
    			objp->attrs = lp->next;
    		else	prevlp->next = lp->next;
    		free(lp->item);
    		free(lp);
    		return;
    		}
    	prevlp = lp;
    	}
    }
    
    (These functions are in the file object.xc in the week5 subdirectory.)

    hasattr returns TRUE if an object has a certain attribute; it simply searches through the object's attribute list looking for a matching string. setattr sets an attribute; if the object does not already have the attribute, setattr allocates a new list structure, by allocating a new list node, allocating and copying the string, and splicing the new node into the attribute list. unsetattr clears an attribute by finding it in the list and freeing both the list node structure and the string (if a matching attribute is found).

    To explain the call to chkstrdup in setattr, we must say and think a little more about memory allocation. It turns out that, to be on the safe side, setattr must allocate memory for the string defining the attribute. It cannot assume that the string which was passed to it was allocated in such a way that it would be guaranteed to persist for the life of this attribute on this object. For example, when we're reading a data file, the passed-in attribute string will be sitting in a buffer holding one line we've just read from the data file, and that buffer will be overwritten when we read the next line. Even if the passed-in string were allocated in such a way that it would stick around, setattr still couldn't use it directly, but would still have to make a copy, because unsetattr is always going to free the string, so setattr better have allocated it. Many times, the string passed to setattr will be a pointer to a string constant in the source code, and if setattr simply copied the pointer rather than allocating and copying the string, unsetattr might later try to free that pointer, an operation which would fail since the pointer wasn't originally obtained from malloc.

    setattr could call strlen to get the length of the string, add 1 for the terminating \0, call malloc or chkmalloc, and copy the string in, but since this is a common pattern (and since it's easy to forget to add 1), we encapsulate it in the function chkstrdup. chkstrdup accepts a string, and returns a pointer to malloc'ed memory holding a copy of the string. The ``chk'' in its name reflects the fact that, like chkmalloc, it never returns a null pointer, even when malloc fails. Here is chkstrdup's definition:
    #include <string.h>
    
    char *
    chkstrdup(char *str)
    {
    char *ret = chkmalloc(strlen(str) + 1);
    strcpy(ret, str);
    return ret;
    }
    
    (chkstrdup is also in chkmalloc.c.)

    Now that we have the hasattr, setattr, and unsetattr functions, we unfortunately have quite a few changes to make. Everywhere we have the pattern
    	object->attrs & ATTRIBUTE
    
    (where object is any struct object pointer and ATTRIBUTE is any attribute), we must replace it with
    	hasattr(object, "attribute")
    
    Everywhere we have the pattern
    	object->attrs |= ATTRIBUTE
    
    we must replace it with
    	setattr(object, "attribute")
    
    And everywhere we have the pattern
    	object->attrs &= ~ATTRIBUTE
    
    we must replace it with
    	unsetattr(object, "attribute")
    
    (As we mentioned, though, anywhere we ``call'' the Iscontainer() or Isopen() macros to test the CONTAINER or OPEN attributes, we won't have to change anything.)

    Finally, the attribute-reading code in io.c is considerably simplified. Here is the relevant code from parsedatafile:
    	else if(strcmp(av[0], "attribute") == 0)
    		{
    		if(currentobject == NULL)
    			continue;
    		setattr(currentobject, av[1]);
    		}
    


    So, exercise 1 (which all of this text so far has been an elaborate prelude to) is to add the functions and source files mentioned so far, change all of the code that uses attrs to use the new hasattr, setattr, and unsetattr functions (the changes should be confined to commands.c, and to one line in object.c), and make sure that the program still works.
  2. If you didn't use dynamically-allocated memory to hold long object and room descriptions, make that change now.
  3. Rewrite newobject in object.c and newroom in rooms.c to dynamically allocate new structures, rather than parceling them out of the static objects and rooms arrays. (Eliminate those arrays.)

    Eliminating the rooms array has one unintended consequence. Although using arrays to hold the objects and rooms was generally a nuisance in the long run, we did take advantage of it in one situation: during the initial setup of the dungeon, while reading the data file, we hooked up named room exits to other rooms by calling the findroom function. findroom had to be able to find a named room anywhere in the dungeon, which meant that it needed a way to scan through the list of all rooms. When rooms were held in an array, scanning through the array was easy. When we move to dynamically allocated room structures, we must preserve this ability.

    The fact that what we need is the ability to ``scan through the list of all rooms'' suggests the solution: we'll keep a linked list of all the rooms. We don't need to define and implement a new list structure or anything; we can just add a ``next'' pointer to struct room. This next pointer won't be used for any purpose which the user playing the game will be able to see--as far as the user is concerned, the only connections (pointers) between rooms are the ones described by the room's explicit exits. This new next field for struct room will be for our own, internal, behind-the-scenes use, so that we can implement this list of all rooms.
  4. Improve the code in io.c so that room exit lists can be placed directly in the room descriptions, rather than at the end. If an exit refers to a room you've already seen, you can hook up the exit immediately. But if the exit refers to a room you haven't seen yet, you'll have to allocate some temporary data structure to keep track of the source room, direction, and destination. Then, after you've read the entire data file, you can go back through that list of unresolved exits, since all of the destinations should exist by that point. (If any don't, you can print an error message.)


This page by Steve Summit // Copyright 1995-9 // mail feedback