DOC PREVIEW
Berkeley COMPSCI 61C - Homework

This preview shows page 1-2 out of 7 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS61CL Fall 2009 Homework 5. Due 11:59 Wed 9/30. Create a directory ~cs61cl-xx/hw5 and place one file in it for each problem. Prob1.txt will be an annotated version of what appears below. The others, prob2.s, prob3.s, prob4.s will be mips assembly language files that run correctly under MARS. Problem 1. On the following page you will find a print out of a solution to table.c of hw3 with the lines numbered. In this problem we will use that example to learn a bit about testing methodology. All too often in CS lab course people write all the code put it together and hope it works. It never does. An alternative approach is proceed systematically testing portions as you go. A good test should “cover” each and every line of code. For example, the following simple program int main ( ) { struct table * t = initTable ( ); printf ("empty table:\n"); printTable (t, stdout); return 0; } Tests lines 43-47, 120-122, 125-126. Get out your highlighter and check it. 1.a Which lines are tested if we expand this to int main ( ) { struct table * t = initTable ( ); printf ("empty table:\n"); printTable (t, stdout); t = addDef ("def", 6, t); printf ("def before use:\n"); printTable (t, stdout); return 0; } Answer: 1.b.The following expands this to cover the rest of function add use. In the comment for each new line of code, indicate the additional lines it covers and the case it checks. int main ( ) { struct table * t = initTable ( ); printf ("empty table:\n"); printTable (t, stdout); t = addDef ("def", 6, t); t = addDef (“eef”, 7, t); t = addDef (“bef”, 8, t); # t = addDef ("def", 9, t); # printTable (t, stdout); return 0; }1.c The following expands this to cover all of addUse and add_useNode. In the comment for each new line of code, indicate the additional lines it covers and the case it checks. int main ( ) { struct table * t = initTable ( ); printf ("empty table:\n"); printTable (t, stdout); t = addDef ("def", 6, t); t = addDef (“eef”, 7, t); t = addDef (“bef”, 8, t); t = addDef ("def", 9, t); t = addUse ("def", 10, t); # # t = addUse ("def", 11, t); # # t = addUse ("undef", 12, t); # # t = addUse ("aa_undef", 12, t); # printTable (t, stdout); t = initTable ( ); t = addUse ("undef", 12, t); # addUse undefined completely empty printTable (t, stdout); return 0; }1 #include <stdlib.h> 2 #include <stdio.h> 3 #include <string.h> 4 #include "table.h" 5 6 /* 7 A symbol table is an ordered linked list of table elements. 8 Each element contains the name of the symbol, the line number at which 9 it was defined (-1 if no definition has yet been processed), and the 10 sequence of line numbers in which the symbol was used. 11 */ 12 13 struct useNode { 14 int pos; 15 struct useNode *next; 16 }; 17 18 struct useNode *add_useNode (struct useNode *head, int pos) { 19 struct useNode *t = head; 20 struct useNode *n = malloc(sizeof(struct useNode)); 21 n->pos = pos; 22 n->next = NULL; 23 if (t == NULL) return n; /* new entry is entire list */ 24 while (t->next) t = t->next; /* add entry to the end of the list */ 25 t->next = n; 26 return head; 27 }; 28 29 struct tableElement { 30 char *symbolName; 31 int defPos; 32 struct useNode *uses; 33 struct tableElement *next; 34 }; 35 36 struct table { 37 struct tableElement * head; 38 }; 39 40 /* 41 Returns an empty table. 42 */ 43 struct table * initTable ( ) { 44 struct table *rtn = malloc (sizeof (struct table)); 45 rtn->head = NULL; 46 return rtn; 47 } 48 49 struct tableElement *newElement(char *symbol, int def, struct tableElement *next) { 50 struct tableElement *n = malloc (sizeof (struct tableElement)); 51 n->symbolName = (char *) malloc (strlen (symbol) + 1); 52 strcpy (n->symbolName, symbol); 53 n->defPos = def; 54 n->uses = NULL;; 55 n->next = next; 56 return n; 57 } 58 59 /* 60 Returns the result of adding a definition for the given symbol 61 in the line with the given number to the table. 62 */ 63 struct table *addDef (char * symbol, int lineNum, struct table *symbols) {64 struct tableElement *n; 65 struct tableElement *prev = NULL; 66 struct tableElement *p = symbols->head; 67 if (p == NULL) { /* Start new list */ 68 n = newElement(symbol,lineNum,p); 69 symbols->head = n; 70 } else { /* Locate point before insertion */ 71 while (p && (strcmp(symbol,p->symbolName)>0)) { 72 prev = p; 73 p = p->next; 74 } 75 if (p && (strcmp(symbol,p->symbolName)==0)) p->defPos = lineNum; 76 else { 77 n = newElement(symbol,lineNum,p); 78 n->next = p; 79 if (prev) prev->next = n; 80 else symbols->head = n; 81 } 82 } 83 return symbols; 84 } 85 86 /* returns the result of adding a use of the given table in the line 87 with the given number to the table */ 88 struct table *addUse (char * symbol, int lineNum, struct table *symbols) { 89 struct tableElement *n; 90 struct tableElement *prev = NULL; 91 struct tableElement *p = symbols->head; 92 /* Find point of insertion or update */ 93 while (p && (strcmp(symbol,p->symbolName)>0)) { 94 prev = p; 95 p = p->next; 96 } 97 98 if (p && (strcmp(symbol,p->symbolName)==0)) /* Already defined */ 99 p->uses = add_useNode(p->uses, lineNum); /* Add use */ 100 else { 101 n = newElement(symbol, -1, p); /* Create undef entry */ 102 n->uses = add_useNode (n->uses, lineNum); 103 n->next = p; 104 if (prev) prev->next = n; 105 else symbols->head = n; 106 } 107 return symbols; 108 } 109 110 void printTableElem (struct tableElement * elem, FILE * out) { 111 struct useNode *u = elem->uses; 112 fprintf (out, "%s\t%d", elem->symbolName, elem->defPos); 113 while (u) { 114 fprintf (out, "\t%d", u->pos); 115 u = u->next; 116 } 117 fprintf (out, "\n"); 118 } 119 120 void printTable (struct table *symbols, FILE * out) { 121 struct tableElement *p = symbols->head; 122 while (p) { 123 printTableElem (p, out); 124 p = p->next; 125 } 126 }Problem 2. The complete the code for the function PrintIntArray so that it prints each element of the array passed to it by calling printInt. Be sure to set up a correct stack frame and respect the register conventions


View Full Document

Berkeley COMPSCI 61C - Homework

Documents in this Course
SIMD II

SIMD II

8 pages

Midterm

Midterm

7 pages

Lecture 7

Lecture 7

31 pages

Caches

Caches

7 pages

Lecture 9

Lecture 9

24 pages

Lecture 1

Lecture 1

28 pages

Lecture 2

Lecture 2

25 pages

VM II

VM II

4 pages

Midterm

Midterm

10 pages

Load more
Download Homework
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Homework and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Homework 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?