C/the.ansi.c.programming.language/notes.accompany.ansi.c/homework/PS5a.html

   1 <!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
   2 <html>
   3 <head>
   4 <link rev="owner" href="mailto:scs@eskimo.com">
   5 <link rev="made" href="mailto:scs@eskimo.com">
   6 <title>Assignment #5 Answers</title>
   7 </head>
   8 <body>
   9 <H1>Assignment #5 Answers</H1>
  10
  11
  12
  13
  14
  15 <B>Intermediate C Programming
  16 <br>
  17 <br>
  18 UW Experimental College
  19 </B><br>
  20 <br>
  21 <B>Assignment #5 ANSWERS
  22 </B><br>
  23 <br>
  24 <p>Exercise 2.
  25 <I>If you didn't use dynamically-allocated memory
  26 to hold long object and room descriptions,
  27 make that change now.
  28 </I><p>See the published answer to
  29
  30 assignment 2, exercise 2.
  31 <p>Exercise 3.
  32 <I>Rewrite <TT>newobject</TT>
  33 and <TT>newroom</TT>
  34 to dynamically allocate new structures,
  35 rather than parceling them out of
  36 the static <TT>objects</TT> and <TT>rooms</TT> arrays.
  37 </I><p>Rewriting <TT>newobject</TT> in <TT>object.c</TT>
  38 is easy enough:
  39 <pre>
  40 struct object *
  41 newobject(char *name)
  42 {
  43 struct object *objp;
  44
  45 objp = chkmalloc(sizeof(struct object));
  46
  47 strcpy(objp-&gt;name, name);
  48 objp-&gt;lnext = NULL;
  49 objp-&gt;attrs = NULL;
  50 objp-&gt;contents = NULL;
  51 objp-&gt;desc = NULL;
  52
  53 return objp;
  54 }
  55 </pre>
  56 <p>However, it isn't quite so simple for <TT>newroom</TT>,
  57 because we need a way of looking through all the rooms
  58 we've got,
  59 for example in the <TT>findroom</TT> function.
  60 Therefore, we can't allocate room structures in isolation.
  61 <p>As suggested in the assignment,
  62 one possibility is
  63 to keep a linked list of all rooms allocated,
  64 by adding
  65 an extra ``next'' field
  66 to <TT>struct room</TT> in <TT>game.h</TT>:
  67 <pre>
  68 struct room
  69         {
  70         char name[MAXNAME];
  71         struct object *contents;
  72         struct room *exits[NEXITS];
  73         char *desc;                     /* long description */
  74         struct room *next;              /* list of all rooms */
  75         };
  76 </pre>
  77 Now I can rewrite <TT>newroom</TT> in <TT>rooms.c</TT>:
  78 <pre>
  79 static struct room *roomlist = NULL;
  80
  81 struct room *
  82 newroom(char *name)
  83 {
  84 struct room *roomp;
  85 int i;
  86
  87 roomp = chkmalloc(sizeof(struct room));
  88
  89 roomp-&gt;next = roomlist;              /* splice into list of all rooms */
  90 roomlist = roomp;
  91
  92 strcpy(roomp-&gt;name, name);
  93 roomp-&gt;contents = NULL;
  94 for(i = 0; i &lt; NEXITS; i++)
  95         roomp-&gt;exits[i] = NULL;
  96 roomp-&gt;desc = NULL;
  97
  98 return roomp;
  99 }
 100 </pre>
 101 Splicing the new room into the list of all rooms is straightforward.
 102 <p><TT>findroom</TT> must be rewritten slightly,
 103 to walk over the new room list rather than the old rooms array:
 104 <pre>
 105 struct room *
 106 findroom(char *name)
 107 {
 108 struct room *roomp;
 109
 110 for(roomp = roomlist; roomp != NULL; roomp = roomp-&gt;next)
 111         {
 112         if(strcmp(roomp-&gt;name, name) == 0)
 113                 return roomp;
 114         }
 115
 116 return NULL;
 117 }
 118 </pre>
 119 <p>We also have to decide what to do with the <TT>getentryroom</TT> function.
 120 (This is the function that gets called to decide
 121 which room the actor should initially be placed in.)
 122 It used to return,
 123 rather arbitrarily,
 124 the first room in the <TT>rooms</TT> array,
 125 which always happened to correspond to the first room in the data file,
 126 which was a reasonable choice.
 127 If we make the obvious change to <TT>getentryroom</TT>,
 128 and have it return the ``first'' room in the new room list:
 129 <pre>
 130 struct room *
 131 getentryroom(void)
 132 {
 133 return roomlist;        /* temporary */
 134 }
 135 </pre>
 136 it will <em>not</em> be so reasonable a choice,
 137 because our easy implementation of the list-splicing code
 138 in <TT>newroom</TT> above
 139 adds new rooms to the head of the list,
 140 such that the first room added,
 141 i.e. the first room in the data file,
 142 ends up at the end of the list.
 143 Depending on what your data file looks like,
 144 the game with the modifications shown so far will start out
 145 by dumping the player unceremoniously onto the back porch or into the basement
 146 (which might actually end up being an advantage for the player,
 147 if the basement tunnel is where the treasure is!).
 148 <p>If you wish,
 149 you can rewrite <TT>newroom</TT> to place new rooms at the end of the list,
 150 or <TT>getentryroom</TT> to return the tail of the list,
 151 to solve this problem.
 152 However, a better fix
 153 would be to allow the data file
 154 to explicitly specify what the entry room should be,
 155 rather than making the game code assume anything.
 156 We'll leave that for another exercise.
 157 <p>Exercise 4.
 158 <I>Improve the code in <TT>io.c</TT>
 159 so that room exit lists can be placed directly in the room descriptions,
 160 rather than at the end.
 161 </I><p>The basic change is to the <TT>parsedatafile</TT> function.
 162 Whereas it used to parse lines at the end of the data file like
 163 <pre>
 164         roomexits kitchen s:hall e:stairway n:porch
 165 </pre>
 166 we'll now make it parse lines like
 167 <pre>
 168         exit s hall
 169         exit e stairway
 170         exit n porch
 171 </pre>
 172 which will occur within the description of the particular room
 173 (in this case, the kitchen)
 174 itself.
 175 (I've simplified things
 176 by putting three exits on three separate lines
 177 and eliminating the colon syntax;
 178 there was no particular reason
 179 for me to have done it in that more complicated way in the first place.)
 180 <p>Here is the new code for <TT>parsedatafile</TT>:
 181 <pre>
 182         else if(strcmp(av[0], "exit") == 0)
 183                 {
 184                 struct room *roomp;
 185                 if(ac &lt; 3)
 186                         {
 187                         fprintf(stderr, "missing exit or room name\n");
 188                         continue;
 189                         }
 190                 if(currentroom == NULL)
 191                         {
 192                         fprintf(stderr, "exit not in room\n");
 193                         continue;
 194                         }
 195                 roomp = findroom(av[2]);
 196                 if(roomp != NULL)
 197                         {
 198                         /* already have room, so connect */
 199                         connectexit(currentroom, av[1], roomp);
 200                         }
 201                 else    {
 202                         /* haven't seen room yet; stash for later */
 203                         stashexit(currentroom, av[1], av[2]);
 204                         }
 205                 }
 206 </pre>
 207 This makes use of two auxiliary functions:
 208 <pre>
 209 static void
 210 connectexit(struct room *room, char *dirname, struct room *nextroom)
 211 {
 212 int dir;
 213
 214 if(strcmp(dirname, "n") == 0)
 215         dir = NORTH;
 216 else if(strcmp(dirname, "e") == 0)
 217         dir = EAST;
 218 else if(strcmp(dirname, "w") == 0)
 219         dir = WEST;
 220 else if(strcmp(dirname, "s") == 0)
 221         dir = SOUTH;
 222 else if(strcmp(dirname, "ne") == 0)
 223         dir = NORTHEAST;
 224 else if(strcmp(dirname, "se") == 0)
 225         dir = SOUTHEAST;
 226 else if(strcmp(dirname, "nw") == 0)
 227         dir = NORTHWEST;
 228 else if(strcmp(dirname, "sw") == 0)
 229         dir = SOUTHWEST;
 230 else if(strcmp(dirname, "u") == 0)
 231         dir = UP;
 232 else if(strcmp(dirname, "d") == 0)
 233         dir = DOWN;
 234 else    {
 235         fprintf(stderr, "no such direction \"%s\"\n", dirname);
 236         return;
 237         }
 238
 239 room-&gt;exits[dir] = nextroom;
 240 }
 241
 242 struct stashedexit
 243         {
 244         struct room *room;
 245         char *dirname;
 246         char *nextroom;
 247         struct stashedexit *next;
 248         };
 249
 250 static struct stashedexit *stashedexits = NULL;
 251
 252 static void
 253 stashexit(struct room *room, char *dirname, char *nextroom)
 254 {
 255 struct stashedexit *ep = chkmalloc(sizeof(struct stashedexit));
 256 ep-&gt;room = room;
 257 ep-&gt;dirname = chkstrdup(dirname);
 258 ep-&gt;nextroom = chkstrdup(nextroom);
 259 ep-&gt;next = stashedexits;
 260 stashedexits = ep;
 261 }
 262 </pre>
 263 The <TT>stashexit</TT> function builds a linked list of stashed exits,
 264 allocating a new instance of the new <TT>struct stashedexit</TT>
 265 for each one,
 266 each containing the room pointer
 267
 268 and the names of the exit direction and destination room.
 269 (The strings must also be copied to dynamically-allocated memory,
 270 because on entry to <TT>stashexit</TT>
 271 they are pointers back into
 272 the <TT>line</TT> or <TT>line2</TT> array in <TT>parsedatafile</TT>,
 273 and those strings will be overwritten
 274 when we read the next line in the data file.)
 275 <p>Finally, we must arrange to resolve the stashed exits
 276 when we're done reading the data file
 277 and have had a chance to see the descriptions for all the rooms.
 278 Here is the change to the <TT>readdatafile</TT> function:
 279 <pre>
 280 static void connectexit(struct room *, char *, struct room *);
 281 static void stashexit(struct room *, char *, char *);
 282 static void resolveexits(void);
 283
 284 readdatafile()
 285 {
 286 char *datfile = "dungeon.dat";
 287 FILE *fp = fopen(datfile, "r");
 288 if(fp == NULL)
 289         {
 290         fprintf(stderr, "can't open %s\n", datfile);
 291         return FALSE;
 292         }
 293
 294 parsedatafile(fp);
 295 resolveexits();
 296 fclose(fp);
 297 return TRUE;
 298 }
 299 </pre>
 300 <p>And here is the third auxiliary function:
 301 <pre>
 302 static void
 303 resolveexits()
 304 {
 305 struct stashedexit *ep, *nextep;
 306
 307 for(ep = stashedexits; ep != NULL; ep = nextep)
 308         {
 309         struct room *roomp = findroom(ep-&gt;nextroom);
 310         if(roomp == NULL)
 311                 fprintf(stderr, "still no such room \"%s\"\n", ep-&gt;nextroom);
 312         else    connectexit(ep-&gt;room, ep-&gt;dirname, roomp);
 313
 314         nextep = ep-&gt;next;
 315         free(ep-&gt;dirname);
 316         free(ep-&gt;nextroom);
 317         free(ep);
 318         }
 319
 320 stashedexits = NULL;
 321 }
 322 </pre>
 323 One aspect of this last function deserves mention.
 324 Why does it not use a more usual list-traversal loop,
 325 such as
 326 <pre>
 327         for(ep = stashedexits; ep != NULL; ep = ep-&gt;next)
 328 </pre>
 329 What's with that temporary variable <TT>nextep</TT>?
 330 This loop is doing two things at once:
 331 traversing the linked list
 332 in order
 333 to resolve the stashed exits,
 334 <em>and</em> freeing the list as it goes.
 335 But when it frees the node
 336 (the <TT>struct stashedexit</TT>)
 337 it's working on,
 338 it also frees--and hence loses--the
 339 <TT>next</TT> pointer which that structure contains!
 340 Therefore,
 341 it makes a copy of the <TT>next</TT> pointer
 342 <em>before</em> it frees the structure.
 343 <hr>
 344 <hr>
 345 <p>
 346 This page by <a href="http://www.eskimo.com/~scs/">Steve Summit</a>
 347 // <a href="copyright.html">Copyright</a> 1995-9
 348 // <a href="mailto:scs@eskimo.com">mail feedback</a>
 349 </p>
 350 </body>
 351 </html>