C/the.ansi.c.programming.language/notes.accompany.ansi.c/homework/PS5.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</title>
   7 </head>
   8 <body>
   9 <H1>Assignment #5</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
  22 </B><p><B>Handouts:
  23 </B></p><p><a href="PS5.html">Assignment #5</a>
  24 <br><a href="PS4a.html">Assignment #4 Answers</a>
  25 <br><a href="http://www.eskimo.com/~scs/cclass/int/sx7.html">Class Notes, Chapter 21</a>
  26 <br><a href="http://www.eskimo.com/~scs/cclass/int/sx8.html">Class Notes, Chapter 22</a>
  27 <p><B>Exercises:
  28 </B></p><OL><li>Bit-masks
  29 (such as the <TT>attrs</TT> field
  30 we added to the object structure last time)
  31 are a perfectly reasonable data structure to use
  32 for keeping track of a relatively small,
  33 well-defined set of attributes.
  34 However,
  35 as we've already seen,
  36 once we start trying to keep track of
  37 the qualities and states of various objects in the game,
  38 we quickly find ourselves using a welter of attributes.
  39 There aren't enough bits in an <TT>int</TT>
  40 (or even a <TT>long int</TT>)
  41 to keep track of all the attributes we might eventually want.
  42 Furthermore,
  43 it becomes a nuisance
  44 to have to <TT>#define</TT> a new mask in <TT>game.h</TT>
  45 every time we invent a new attribute,
  46 and to add another <TT>if</TT> clause
  47 to <TT>parsedatafile</TT> in <TT>io.c</TT>
  48 to map the <TT>attribute</TT> line in the data file
  49 (a string)
  50 to the corresponding mask constant.
  51 <br>
  52 <br>
  53 Therefore, after using it for only a week or two,
  54 we're going to rip out the bitmask-based attribute scheme
  55 and replace it with something more open-ended and flexible.
  56 Any object may have a list of attributes,
  57 with each attribute represented by an arbitrary string.
  58 We'll write a few functions for
  59 setting, testing, and clearing these attributes,
  60 so that they'll be convenient
  61 for the rest of the program to manipulate.
  62 While we're at it,
  63 we'll get some
  64 more
  65 practice doing dynamic memory allocation
  66 and using linked lists.
  67 <br>
  68 <br>
  69 Since,
  70 under this new scheme,
  71 an object may have arbitrarily many attributes,
  72 and since each attribute will be an arbitrary-length string,
  73 we won't be able to use fixed-size data structures.
  74 We'll use dynamically-allocated ones, instead,
  75 which means that we'll be calling <TT>malloc</TT> a lot.
  76 A cardinal rule of using <TT>malloc</TT> is that you <em>must</em>
  77 check its return value to make sure that it did not return a null pointer.
  78 If the program ever runs out of memory,
  79 or some other problem causes <TT>malloc</TT> to return a null pointer,
  80 and if your program accidentally uses that null pointer
  81 as if it points to usable memory,
  82 your program can and will fail in mysterious ways.
  83 If, on the other hand,
  84 you check <TT>malloc</TT>'s return value,
  85 and print a distinct error message when it fails,
  86 you'll at least know more or less exactly what the problem is.
  87 <br>
  88 <br>
  89 If you have many places in your program
  90 where you're doing dynamic allocation,
  91 it may become a nuisance
  92 to have to check return values at all of those places.
  93 Therefore,
  94 a popular strategy is to implement
  95 a <dfn>wrapper function</dfn> around <TT>malloc</TT>.
  96 The one we'll be using looks like this:
  97 <pre>
  98 #include &lt;stdio.h&gt;
  99 #include &lt;stdlib.h&gt;
 100 #include "chkmalloc.h"
 101
 102 void *
 103 chkmalloc(size_t sz)
 104 {
 105 void *ret = malloc(sz);
 106 if(ret == NULL)
 107         {
 108         fprintf(stderr, "Out of memory\n");
 109         exit(EXIT_FAILURE);
 110         }
 111 return ret;
 112 }
 113 </pre>
 114 All <TT>chkmalloc</TT> does is call <TT>malloc</TT>,
 115 check its return value,
 116 and return it if it's not <TT>NULL</TT>.
 117 (<TT>size_t</TT> is an ANSI C type for representing the sizes of objects,
 118 and <TT>void *</TT> is the generic pointer type
 119 which <TT>malloc</TT> and related functions return.)
 120 But since <TT>chkmalloc</TT> never returns a null pointer,
 121 its caller never has to check,
 122 but can begin using the pointer immediately.
 123 <TT>chkmalloc</TT> can guarantee never to return a null pointer
 124 not because it implements some kind of a magical infinite memory space,
 125 but rather
 126
 127 because it simply exits,
 128 after printing an error message,
 129 if <TT>malloc</TT> fails.
 130 Thus, all tests for <TT>malloc</TT> failures
 131 (and our strategy for dealing with
 132 those failures)
 133 are centralized in <TT>chkmalloc()</TT>.
 134 <br>
 135 <br>
 136 The ``strategy'' of printing an error message and exiting
 137 when <TT>malloc</TT> fails is an expedient one,
 138 but it would not be ideal for all programs.
 139 It assumes that
 140 (a) an actual out-of-memory condition is unlikely, and
 141 (b) the program won't have any cleanup to do
 142 and won't mind if it's summarily terminated.
 143 This strategy would <em>not</em>,
 144 for example,
 145 be acceptable for a text editor:
 146 the editor might use arbitrary amounts of memory when editing a large file,
 147 and the user would certainly <em>not</em> appreciate being dumped out,
 148 without having the opportunity to save any work,
 149 after trying to add
 150 (say) the 1,000,001st character
 151 to a huge file
 152 which had just been typed in from scratch
 153 over many hours.
 154 However, for our little adventure game,
 155 this is a perfectly adequate strategy,
 156 for now at least.
 157 <br>
 158 <br>
 159 You might argue that,
 160 if out-of-memory conditions are unlikely,
 161 we might as well skip <TT>chkmalloc</TT>,
 162 call <TT>malloc</TT> directly,
 163 and not check its return value.
 164 This would be a bad idea,
 165 because while actual out-of-memory conditions may be rare,
 166 other kinds of <TT>malloc</TT> failures are not so rare,
 167 especially in a program under development.
 168 If you misuse the memory which <TT>malloc</TT> gives you,
 169 perhaps by asking for 16 bytes of memory
 170 and then writing 17 characters to it
 171 (and this is all too easy to do),
 172 <TT>malloc</TT> tends to notice,
 173 or at least to be broken by your carelessness,
 174 and will return a null pointer next time you call it.
 175 When <TT>malloc</TT> returns a null pointer for this reason,
 176 it can be difficult to track down the actual error
 177 (because it typically occurred
 178 somewhere in your code <em>before</em> the call to <TT>malloc</TT>
 179 that failed),
 180 but if we blindly used the null pointer which <TT>malloc</TT>
 181 returned to us,
 182 we'd only defer the eventual crash even farther,
 183 and it might be quite mysterious,
 184 much more so than a definitive ``out of memory'' message.
 185 Therefore,
 186 using a wrapper function like <TT>chkmalloc</TT> is a definite improvement,
 187 because we get error messages as soon as <TT>malloc</TT> fails,
 188 and we don't have to scatter tests all through our code to get them.
 189 <br>
 190 <br>
 191 All we do have to do,
 192 anywhere we call <TT>chkmalloc</TT>,
 193 is <TT>#include "chkmalloc.h"</TT>,
 194 which contains <TT>chkmalloc</TT>'s external function prototype declaration,
 195 as well as a second convenience function
 196 which we'll meet in a minute:
 197 <pre>
 198 extern void *chkmalloc(size_t);
 199 extern char *chkstrdup(char *);
 200 </pre>
 201 Both <TT>chkmalloc.c</TT> and <TT>chkmalloc.h</TT>
 202 are in the <TT>week5</TT> subdirectory of the source directories.
 203 <br>
 204 <br>
 205 With <TT>chkmalloc</TT> in hand,
 206 we can begin implementing the new attribute scheme.
 207 First, we define this list structure:
 208 <pre>
 209 struct list
 210         {
 211         char *item;
 212         struct list *next;
 213         };
 214 </pre>
 215 <br>
 216 <br>
 217 Then, we rewrite the object structure to use a list,
 218 instead of an <TT>unsigned int</TT>,
 219 for <TT>attrs</TT>:
 220 <pre>
 221 struct object
 222         {
 223         char name[MAXNAME];
 224         struct list *attrs;
 225         struct object *contents;        /* contents (if container) */
 226         struct object *lnext;           /* next in list of contained objects */
 227                                         /* (i.e. in this object's container) */
 228         char *desc;                     /* long description */
 229         };
 230 #define Iscontainer(o) hasattr(o, "container")
 231 #define Isopen(o) hasattr(o, "open")
 232 </pre>
 233 Notice that we have also rewritten the
 234 <TT>Iscontainer()</TT> and <TT>Isopen()</TT>
 235 macros,
 236 to use the new <TT>hasattr</TT> function,
 237 which we'll see in a minute.
 238 (This suggests another benefit of having used those macros:
 239 none of the code that ``called''
 240 <TT>Iscontainer()</TT> or <TT>Isopen()</TT>
 241 will need rewriting.
 242 As we'll see,
 243 though,
 244 the code that has been using raw bit operations
 245 to test and set the other attributes
 246 will need rewriting.)
 247 The old attribute bits (<TT>CONTAINER</TT>, <TT>OPEN</TT>, etc.)
 248 are no longer needed.
 249 <br>
 250 <br>
 251 We rewrite the <TT>newobject</TT> function in <TT>object.c</TT>
 252 slightly,
 253 to initialize <TT>attrs</TT> to a null pointer:
 254 <pre>
 255 struct object *
 256 newobject(char *name)
 257 {
 258 struct object *objp;
 259
 260 if(nobjects &gt;= MAXOBJECTS)
 261         {
 262         fprintf(stderr, "too many objects\n");
 263         exit(1);
 264         }
 265
 266 objp = &amp;objects[nobjects++];
 267
 268 strcpy(objp-&gt;name, name);
 269 objp-&gt;lnext = NULL;
 270 objp-&gt;attrs = NULL;
 271 objp-&gt;contents = NULL;
 272 objp-&gt;desc = NULL;
 273
 274 return objp;
 275 }
 276 </pre>
 277 (Actually, we could have left it as <TT>objp-&gt;attrs = 0</TT>,
 278 because 0 is also an acceptable null pointer constant.)
 279 <br>
 280 <br>
 281 Now,
 282 here are the three new functions for testing, setting, and
 283 clearing (``unsetting'')
 284 attribute strings:
 285 <pre>
 286 /* see if the object has the attribute */
 287
 288 int
 289 hasattr(struct object *objp, char *attr)
 290 {
 291 struct list *lp;
 292
 293 for(lp = objp-&gt;attrs; lp != NULL; lp = lp-&gt;next)
 294         {
 295         if(strcmp(lp-&gt;item, attr) == 0)
 296                 return TRUE;
 297         }
 298
 299 return FALSE;
 300 }
 301
 302 /* set an attribute of an object (if it's not set already) */
 303
 304 void
 305 setattr(struct object *objp, char *attr)
 306 {
 307 struct list *lp;
 308
 309 if(hasattr(objp, attr))
 310         return;
 311
 312 lp = chkmalloc(sizeof(struct list));
 313
 314 lp-&gt;item = chkstrdup(attr);
 315 lp-&gt;next = objp-&gt;attrs;
 316 objp-&gt;attrs = lp;
 317 }
 318
 319 /* clear an attribute of an object */
 320
 321 void
 322 unsetattr(struct object *objp, char *attr)
 323 {
 324 struct list *lp;
 325 struct list *prevlp;
 326
 327 for(lp = objp-&gt;attrs; lp != NULL; lp = lp-&gt;next)
 328         {
 329         if(strcmp(lp-&gt;item, attr) == 0)
 330                 {
 331                 if(lp == objp-&gt;attrs)
 332                         objp-&gt;attrs = lp-&gt;next;
 333                 else    prevlp-&gt;next = lp-&gt;next;
 334                 free(lp-&gt;item);
 335                 free(lp);
 336                 return;
 337                 }
 338         prevlp = lp;
 339         }
 340 }
 341 </pre>
 342 (These functions are in the file <TT>object.xc</TT>
 343 in the <TT>week5</TT> subdirectory.)
 344 <br>
 345 <br>
 346 <TT>hasattr</TT> returns <TT>TRUE</TT> if an object has a certain
 347 attribute;
 348 it simply searches through the object's attribute list
 349 looking for a matching string.
 350 <TT>setattr</TT> sets an attribute;
 351 if the object does not already have the attribute,
 352 <TT>setattr</TT> allocates a new list structure,
 353 by allocating a new list node,
 354 allocating and copying the string,
 355 and splicing the new node into the attribute list.
 356 <TT>unsetattr</TT> clears an attribute by finding it in the list
 357 and freeing both the list node structure and the string
 358 (if a matching attribute is found).
 359 <br>
 360 <br>
 361 To explain the call to <TT>chkstrdup</TT> in <TT>setattr</TT>,
 362 we must say and think a little more about memory allocation.
 363 It turns out that,
 364 to be on the safe side,
 365 <TT>setattr</TT> must allocate memory for the string defining the attribute.
 366 It cannot assume that the string which was passed to it
 367 was allocated in such a way
 368 that it would be guaranteed to persist
 369 for the life of this attribute on this object.
 370 For example,
 371 when we're reading a data file,
 372 the passed-in attribute string will be sitting
 373 in a buffer holding one line we've just read from the data file,
 374 and
 375 that buffer
 376 will be overwritten when we read the next line.
 377 Even if the passed-in string <em>were</em> allocated
 378 in such a way that it would stick around,
 379 <TT>setattr</TT> still couldn't use it directly,
 380 but would still have to make a copy,
 381 because <TT>unsetattr</TT> is always going to free the string,
 382 so <TT>setattr</TT> better have allocated it.
 383 Many times, the string passed to <TT>setattr</TT> will be
 384 a pointer to a string constant in the source code,
 385 and if <TT>setattr</TT> simply copied the pointer
 386 rather than allocating and copying the string,
 387 <TT>unsetattr</TT> might later try to free that pointer,
 388 an operation which would fail since the pointer wasn't originally
 389 obtained from <TT>malloc</TT>.
 390 <br>
 391 <br>
 392 <TT>setattr</TT> could call <TT>strlen</TT>
 393 to get the length of the string,
 394 add 1 for the terminating <TT>\0</TT>,
 395 call <TT>malloc</TT> or <TT>chkmalloc</TT>,
 396 and copy the string in,
 397 but since this is a common pattern
 398 (and since it's easy to forget to add 1),
 399 we encapsulate it in the function <TT>chkstrdup</TT>.
 400 <TT>chkstrdup</TT> accepts a string,
 401 and returns a pointer to <TT>malloc</TT>'ed memory
 402 holding a copy of the string.
 403 The ``<TT>chk</TT>'' in its name reflects the fact that,
 404 like <TT>chkmalloc</TT>,
 405 it never returns a null pointer,
 406 even when <TT>malloc</TT> fails.
 407 Here is <TT>chkstrdup</TT>'s definition:
 408 <pre>
 409 #include &lt;string.h&gt;
 410
 411 char *
 412 chkstrdup(char *str)
 413 {
 414 char *ret = chkmalloc(strlen(str) + 1);
 415 strcpy(ret, str);
 416 return ret;
 417 }
 418 </pre>
 419 (<TT>chkstrdup</TT> is also in <TT>chkmalloc.c</TT>.)
 420 <br>
 421 <br>
 422 Now that we have the <TT>hasattr</TT>, <TT>setattr</TT>,
 423 and <TT>unsetattr</TT> functions,
 424 we unfortunately have quite a few changes to make.
 425 Everywhere we have the pattern
 426 <pre>
 427         <I>object</I>-&gt;attrs &amp; <I>ATTRIBUTE</I>
 428 </pre>
 429 (where <I>object</I> is any <TT>struct object</TT> pointer
 430 and <I>ATTRIBUTE</I> is any attribute),
 431 we must replace it with
 432 <pre>
 433         hasattr(<I>object</I>, "<I>attribute</I>")
 434 </pre>
 435 Everywhere we have the pattern
 436 <pre>
 437         <I>object</I>-&gt;attrs |= <I>ATTRIBUTE</I>
 438 </pre>
 439 we must replace it with
 440 <pre>
 441         setattr(<I>object</I>, "<I>attribute</I>")
 442 </pre>
 443 And everywhere we have the pattern
 444 <pre>
 445         <I>object</I>-&gt;attrs &amp;= ~<I>ATTRIBUTE</I>
 446 </pre>
 447 we must replace it with
 448 <pre>
 449         unsetattr(<I>object</I>, "<I>attribute</I>")
 450 </pre>
 451 (As we mentioned, though,
 452 anywhere we ``call''
 453 the <TT>Iscontainer()</TT> or <TT>Isopen()</TT> macros
 454 to test the <TT>CONTAINER</TT> or <TT>OPEN</TT> attributes,
 455 we won't have to change anything.)
 456 <br>
 457 <br>
 458 Finally,
 459 the attribute-reading code in <TT>io.c</TT> is considerably simplified.
 460 Here is the relevant code from <TT>parsedatafile</TT>:
 461 <pre>
 462         else if(strcmp(av[0], "attribute") == 0)
 463                 {
 464                 if(currentobject == NULL)
 465                         continue;
 466                 setattr(currentobject, av[1]);
 467                 }
 468 </pre>
 469 <br>
 470 <br>
 471 So, exercise 1
 472 (which all of this text so far has been an elaborate prelude to)
 473 is to add the functions and source files mentioned so far,
 474 change all of the code that uses <TT>attrs</TT> to use the new
 475 <TT>hasattr</TT>, <TT>setattr</TT>,
 476 and <TT>unsetattr</TT> functions
 477 (the changes should be confined to <TT>commands.c</TT>,
 478 and to one line in <TT>object.c</TT>),
 479 and make sure that the program still works.
 480 <li>If you didn't use dynamically-allocated memory
 481 to hold long object and room descriptions,
 482 make that change now.
 483 <li>Rewrite <TT>newobject</TT> in <TT>object.c</TT>
 484 and <TT>newroom</TT> in <TT>rooms.c</TT>
 485 to dynamically allocate
 486 new structures,
 487 rather than parceling them out of
 488 the static <TT>objects</TT> and <TT>rooms</TT> arrays.
 489 (Eliminate those arrays.)
 490 <br>
 491 <br>
 492 Eliminating the <TT>rooms</TT> array has one unintended consequence.
 493 Although using arrays
 494 to hold the objects and rooms
 495 was generally a nuisance in the long run,
 496 we did take advantage of it in one situation:
 497 during the initial setup of the dungeon,
 498 while reading the data file,
 499 we hooked up named room exits to other rooms
 500 bu calling the <TT>findroom</TT> function.
 501 <TT>findroom</TT> had to be able to find a named room anywhere in the dungeon,
 502 which meant that it needed a way to scan through the list of all rooms.
 503 When rooms were held in an array,
 504 scanning through the array was easy.
 505 When we move to dynamically allocated room structures,
 506 we must preserve this ability.
 507 <br>
 508 <br>
 509 The fact that what we need is the ability to
 510 ``scan through the list of all rooms''
 511 suggests the solution:
 512 we'll keep a linked list of all the rooms.
 513 We don't need to define and implement a new list structure or anything;
 514 we can just add a ``next'' pointer to <TT>struct room</TT>.
 515 This next pointer won't be used for any purpose
 516 which the user playing the game will be able to see--as
 517 far as the user is concerned,
 518 the only connections
 519 (pointers)
 520 between rooms are the ones described by the room's explicit exits.
 521 This new <TT>next</TT> field for <TT>struct room</TT>
 522 will be for our own, internal, behind-the-scenes use,
 523 so that we can implement this list of all rooms.
 524 <li>Improve the code in <TT>io.c</TT>
 525 so that room exit lists can be placed directly in the room descriptions,
 526 rather than at the end.
 527 If an exit refers to a room you've already seen,
 528 you can hook up the exit immediately.
 529 But if the exit refers to a room you haven't seen yet,
 530 you'll have to allocate some temporary data structure
 531 to keep track of the source room, direction, and destination.
 532 Then, after you've read the entire data file,
 533 you can go back through that list of unresolved exits,
 534 since all of the destinations <em>should</em> exist by that point.
 535 (If any don't, you can print an error message.)
 536 </OL><hr>
 537 <hr>
 538 <p>
 539 This page by <a href="http://www.eskimo.com/~scs/">Steve Summit</a>
 540 // <a href="copyright.html">Copyright</a> 1995-9
 541 // <a href="mailto:scs@eskimo.com">mail feedback</a>
 542 </p>
 543 </body>
 544 </html>