Assignment 9, due Apr. 6

On every assignment, write your name legibly as it appears on your University ID and on the class list! Assignments are due at the start of class on the day indicated (usually Friday). Exceptions will be by advance arrangement unless there is what insurance companies call "an act of God" (something outside your control). Homework must be turned in on paper, either in class or in the instructor's mailbox. Never push late work under someone's door!

1. Background: Consider the following code for a buddy-system, written in comment-free C-like form, but using the type word as a universal type that serves both as an integer and as as a pointer to a word object, thus eliminating any vestage of type safety but making the code easier to read:

   #define FREEMAX -----
   word freelists[FREEMAX]
   
   word buddyalloc( word i ) {
       if (i >= FREEMAX) {
           return NULL;
       } else if (freelists[i] == NULL)
           word p = buddyalloc(i + 1);
           if (p != NULL) {
               word b = p | (1 << i);
               *b = NULL;
               freelists[i] = b;
           }
           return p;
       } else {
           word p = freelists[i];
           freelists[i] = *p;
           return p;
       }
   }
   

   A problem: This is not legal C. In C, pointers must have a specific type that is not an integer type. Rewrite this code as legal C, using an appropriate integer for integers, an appropriate pointer type for pointers, and explicit casting to convert between types where needed. Note that the include file <stdint.h> includes the integer type intptr_t that is guaranteed to be the same number of bits as a pointer. (1 point)

2. Background: Consider the following partial definition of a boundary tag storage allocation system:

   #define STATUSFREE 0
   #define STATUSUSED 1
   struct tag {
       struct tag * next;
       int status;
   };
   
   struct tag * heap;
   
   void free( void * p ) {
       struct tag * ptag = ((struct tag *)p) - 1; /****/
       ptag -> status = STATUSFREE;
   }
   
   void * malloc( size_t s ) {
       struct tag * ptag = heap;
       for (;;) { /* loop exit is by return */
           if (ptag == NULL) return NULL;
           if (ptag->status == STATUSFREE) {
               struct tag * pnext = ptag->next;
               while (pnext->status == STATUSFREE) {
                   pnext = pnext->next;
               }
               ptag->next = pnext;
           }
           ----- block of missing code -----
           ptag = ptag->next;
       }
       return NULL;
   

   a) One line above is marked with a comment /****/. Explain how this line guarantees that the tag and the user's block of memory do not overlap. This hinges on an eccentric feature of C (and C++) array semantics. (0.5 points)

   b) Concisely describe the initial structure of the heap? How many tags are in the heap, which tag does the pointer heap point to, and how are these tags linked, which pointers are NULL and what are the status fields of the tags? (0.5 points)

   c) Describe the block policy decisions inherent in this heap manager. Is it lazy or prompt? Is it first-fit or best-fit? (0.5 points)

   d) What does the missing block of code do? (0.5 points)