CS61B Lecture #30Administrative: Preliminary grading run tonight.Today:• Enumerated Types• Preprocessing• Function pointers• How Things Work: Dynamic method selection• How Things Work: Storage allocationLast modified: Wed Dec 5 15:40:17 2001 CS61B: Lecture #30 1Enumerated Types• In Java, you’ve seen several instances of symbolicconstants representing integer values:–TT EOF, TT EOL, TT WORD, etc. in StreamTokenizer.–RED PIECE, BLUE PIECE in AmazonsConstants.• Problem with this design: no type safety– Could mistakenly useTT EOF as argument to setPiecemethod in AmazonsBoardModel.• Solution: enumerated type.• Example: Alternative definition from Project #3.typedef enum { EMPTY, SPEAR, RED_PIECE, BLUE_PIECE }SquareContents;• EMPTY, etc., are symbolic integer constants. By de-fault, automatically chooses distinct values.• In C design, enumerated types are a kind of int, butdecent compilers will warn if you try to mix them up.Last modified: Wed Dec 5 15:40:17 2001 CS61B: Lecture #30 2Preprocessing: Macros• First step in translating C programs is to subjectthem tomacro processing.•Macro:A construct defined as purely textual sub-stitution• Simple form, no arguments:#define EOF (-1)#define loop while (1)• After these definitions, all instances of EOF and loopreplaced by text of their definitionsloop { | while (1) {c = getchar (); | c = getchar ();if (c == EOF) | if (c == (-1))break; | break;} | }• Complex form, with arguments:#define new(Type) (Type*) malloc (sizeof (Type))• Here, arguments are substituted, too:new(int) | (int*) malloc (sizeof(int))• In older programs, macros often used to define con-stants or toinlinefunctions; these particular usesare no longer encouraged.Last modified: Wed Dec 5 15:40:17 2001 CS61B: Lecture #30 3Preprocessing: Conditional Compilation• The preprocessor can alsoconditionally includetext.• Often used to adapt to different configuration op-tions or machine architectures.#if defined(SUN)#include <procfs.h>#else#include <sys/ptrace.h>#endif• The symbols used in the conditions are macro defini-tions only; preprocessor doesn’t know about ordinaryvariables.Last modified: Wed Dec 5 15:40:17 2001 CS61B: Lecture #30 4Function Pointers• In Java, used things like Comparators to serve inplace of predicates and other functions.• Like Scheme, C has pointers to functions as values.• Unlike Scheme, C functions are all “outer level”—notnested inside other functions.• Syntax is pretty intimidating:/** The maximum value in A[0 .. N-1], using COMPARE to define* the ordering: COMPARE (x,y) < 0 if x is before y, >0 if x* after y, ==0 if x and y are equivalent. */int max (int A[], int N, int (*compare)(int, int)) {int i, val;val = A[0];for (i = 1; i < N; i += 1)if (compare (val, A[i]) < 0) val = A[i];return val;}• Calling:X = max (B, 100, myCompare);Last modified: Wed Dec 5 15:40:17 2001 CS61B: Lecture #30 5Under the Hood: Method SelectionProblem: How do Java implementations get x.f() tocall the rightf function?• Consider Java types like theseclass Parent { class Child extends Parent {int x; int y;int f (int z) { int f (int z) {return z + x; return z - y;} }} void g (void) { }}• Internally, we see something like this:struct TypeInfoParent { | struct TypeInfoChild {char* typeName; | char* typeName;int (*f)(int); | int (*f)(int);}; | void (*g)(void);| };struct Parent { | struct Child {TypeInfoParent* _type;| TypeInfoChild* _type;int x; | int x;}; | int y;| };Last modified: Wed Dec 5 15:40:17 2001 CS61B: Lecture #30 6Setting Up the Type Information• Define functionsint f_Parent (struct Parent* this, int z) {return z + this->x;}int f_Child (struct Parent* this0, int z) {struct Child* this = (struct Child*) this0;return z - this->y;}void g_Child (struct Child* this) { }• Set up descriptors for each type.struct TypeInfoParent ParentInfo = { "Parent", f_Parent };struct TypeInfoChild ChildInfo ={ "Child", f_Child, g_Child };• Creating Parent and Child objects:struct Parent *p0, *c0;p0 = new(struct Parent);c0 = (struct Parent*) new(struct Child);p0->_type = &ParentInfo;((struct Child*) c0)->_type = &ChildInfo;• Calling f through a struct Parent: Java call c0.f(42)becomes (c0->_type.f)(c0, 42).Last modified: Wed Dec 5 15:40:17 2001 CS61B: Lecture #30 7Observations• This design makes certain assumptions that are notreally valid C, but that work anyway.• Assumes we can use struct Parent* to point at astruct Child* and a struct TypeInfoParent* topoint to astruct TypeInfoChild*.• Because of how machines work, these assumptionsworkifthe fields of Parent and TypeInfoParentare also the first fields of Child and TypeInfoChild.Last modified: Wed Dec 5 15:40:17 2001 CS61B: Lecture #30 8Under the Hood: Storage Allocation• To make malloc work, we again rely on “cheating.”• Storage is allocated out of (essentially) a large chararray, which is returned by primitive system func-tions (sbrk in UNIX).• Here’s a simple-minded example:char* space =something primitive;int spaceLeft =initial size ofspace;void* malloc (int N) {void* val;if (N <= 0) N = 8; /* Allocate at least 8 bytes */N = (N+7) & ~7; /* Round up to multiple of 8 */val = (void*) space;space += N;return val;}• The char* pointer is later converted back from void*to some other type, often different from char*.• Again, because of how computers memory is orga-nized, this justs works.Last modified: Wed Dec 5 15:40:17 2001 CS61B: Lecture #30
View Full Document