CIS*2750 Lecture 5: Advanced C Programming PDF

CIS*2750 Lecture 5: Advanced C Programming Some material from Expert C Programming: Deep C Secrets by Peter van der Linden Based on CIS*2750 notes from previous generations of CIS*2750 instructors  Topics Scope of symbol names 4 avours Precedence of operators...

CIS*2750 Lecture 5: Advanced C Programming Some material from Expert C Programming: Deep C Secrets by Peter van der Linden Based on CIS*2750 notes from previous generations of CIS*2750 instructors  Topics Scope of symbol names 4 avours Precedence of operators associativity syntax of declarations with multiple operators fl Scope, Access Control, Storage Class Most programming languages separate the concepts of scope, access control, and storage class to some extent Variable scope is the region over which you can access a variable by name. In other words, scope de nes where a variable is "visible" E.g. Variables declared within a method are only visible within that method (local scope) Storage class determines how long the symbol - e.g. variable - stays "alive" Access control determines who can access a symbol that is visible to everyone fi Scope vs Access Control Most modern languages give us additional control for accessibility of functions/methods, as well as some of the variables For example, in Java we have 4 access levels for methods and class/instance variables private, protected, package-level (default), public So a class variable - that has class-wide scope - is visible to all classes/objects within a program, but we can make it inaccessible to various other classes through the use of access control e.g. private to make it visible only to the objects of that class Scope in C C has no access control as such - everything is "public" - but we have some control over who can see a speci c variable There are 4 types of scope: Program scope … widest File scope Function scope Block scope … narrowest fi Scoping Principle Always de ne a symbol in the narrowest scope that works Reasons? Same as for controlling access in OO programming - error prevention and, to a lesser extent, security fi 1. Program Scope The variable is accessible by all source les that make up the executable. In C, all functions Global (extern) variables fi Program Symbol Concepts Names used for data and functions variable name, typedef, enum, struct ( elds), class (data members, methods), and more De nition: where the named thing “lives” actual memory location of data or function Reference: some use of the thing by name load/store, call: must be “resolved” to location Declaration: tells compiler about the name compiler can verify that references are correct fi fi Examples int max(int a, int b); // function prototype declaration int main(){... float sum = 0.0; // variable definition sum = sum*10 + max(x,y); // references ^store ^load ^call... } // function definition int max(int a, int b) { return a>b? a : b; } // if this definition was up top before the reference, the definition // would serve as a declaration, too External Symbols Program scope symbols are passed to linker (ref. Lecture 2a) in a.o le External de nition, “extdef” External reference, “extref” In linked executable, for each external symbol: Exactly one extdef, or else we get an error: “unde ned external”, “multiply de ned external” Any number of extrefs substituted with nal memory address of symbol fi fi fi fi “Externals” Having “program scope” (external symbols) is a common requirement assembly language all kinds of programming languages allows big program to be linked together out of small modules Each language has own convention for designating extdef & extref Using Program Scope in C: function extdef: void insertBack(List* list, void* toBeAdded){…} de nition only appears in one.c le (LinkedListAPI.c) declaration: void insertBack(List* list, void* toBeAdded); seems to appear only once, in LinkedListAPI.h however, prototype declaration (LinkedListAPI.h) is actually included in many.c les we use include guards to prevent recursive re-declarations extref: insertBack(list, data); call - de nitely happens in multiple les fi fi Using Program Scope in C: variable extdef: FILE* inputfile; de nition only appears in one.c, outside any function can initialize: type varname = initial_value; declaration: extern FILE* inputfile; declaration appears anywhere in a le, in/outside functions extref: fclose(inputfile); appears anywhere we use the variable fi fi Using Program Scope You have to decide when to use program scope In general, variables should never be globally accessible by the end user Program scope functions should be part of the program's public interface Try to avoid program scope for internal functions, if possible  2. File Scope A variable or a function is accessible from its declaration (de nition) point to the end of the le. In C, static things that are global within a le, but not the whole program CAUTION: static keyword has multiple uses! If variable de ned outside any function… would normally be “program scope” (global) static keyword keeps de nition from being passed to linker → doesn’t become external fi fi fi fi Using File Scope The le scope in C sits somewhere between private and package-level in Java File scope is perfect for "internal-use-only" functions Can be used for variables, but you really should avoid variables that are global to a le Keep variables local to each function body (local scope) and pass them as function arguments instead Global variables ( le or program scope) are usually a bad idea - they lead to hard-to- nd errors fi fi 3. Function Scope Accessible throughout a function. In C, only goto labels have function scope; therefore you will never see them “Throughout” means you can jump ahead: goto bummer; … bummer: printf(“Outta here!”); 4. Block (local) Scope The variable is accessible after its declaration point to the end of the block in which it was declared. Remember, a block is anything between {} braces In C, variables declared within a block - e.g. the body of a function or a loop - are local variables. I will usually use the terms local scope and block scope interchangeably Includes: function’s parameters local variables declared in a function loop counters declared in a for (int i = 0; …) statements variables declared within the loop or branching statement body What Happens? func() { int a = 11; { int b = 10; } printf(“%d %d\n”,a,b); } Won’t work! The variable b is inside a block and therefore is not visible to the rest of the function.  What Happens? newfunc() { int a = 11; { int b = 10; printf ( “%d\n”,b); } printf ( “%d\n”,a); } Fixed! Using local variables - badly! As a rule, declare variables with the narrowest scope E.g. loop counters can be declared right in the for-loop statement Temporary variables used only inside one loop can be declared within that loop Move a variable to a wider local scope only when necessary Avoid using the same variable name in overlapping scopes - i.e. shadowing Bad example void func(){ int x = 7; for (int i = 0; i < 10; i++){ int x = i;// The "outer" x never changes } }  Scope vs. Storage Class Storage class applies to where & how long variable is kept Di erent from scope - i.e. who can see a variable Typically, variable scope and storage class are unrelated to each other C is a bit weird, since declaring a variable static a ects both its storage and its scope! ff Automatic Storage Associated with functions Arguments Local variables inside function - or inside any other block remember, a block is stu between a pair of {}s Fresh temporary copy created on the stack every time function called Copy can be initialized (same value each time) Copy goes away when function returns to caller Allows recursion to work! ff Automatic Storage - warning Never return pointers to automatic variables! Remember, the auto variable goes away when the scope ends / function returns So by returning a pointer to an automatic variable, we return a pointer to memory that has be freed! To make the matters worse, this will sometimes "work" Automatic Storage - BAD example char* func(){ char x; //Do stuff with x return x; } int main(void){ char* s = func(); printf("%s\n", s); } This might print something useful. Or it might not. Never do this! Static Storage static storage: Means there is only one instance of variable in executable program Applies to program scope (global variables) “static” le scope variables “static” local variables If you add static keyword, a variable is not global anymore - it is restricted to le scope The static keyword changes local variable from automatic to static storage class Initialization e ective once, when program started fi ff Static Storage Typically, the only static variables are the ones we want to restrict to le scope Occasionally we want to have a function that "remembers" its local value between function calls In that case, we declare a variable with local (block) scope, and static storage For example, we want to create a constructor-style function that allocates a struct: a 2D point We want to keep track of how many structs were allocated, i.e. how many times the function was called we can create an internal counter in the function: static int count = 0; Example: static storage #include #include typedef struct { float x; float y; } Point2D; Point2D* createPoint2D(){ static int count = 0; Point2D* tmp = malloc(sizeof(Point2D)); if (tmp != NULL){ printf("Allocated %d structs\n", ++count); } return tmp; } Example: static storage int main(void){ Point2D* p1 = createPoint2D(); //Prints Allocated 1 structs Point2D* p2 = createPoint2D(); //Prints Allocated 2 structs Point2D* p3 = createPoint2D(); //Prints Allocated 3 structs return 0; } Global / external storage Program scope variables exist as long as the program is running Example (all in one.c file) int i; // Program scope, program storage static int j; func( int k ) { int m; // Block/local scope, automatic storage static int x; // Block/local scope, static storage } Dynamic Storage Third class of storage, contrasted with static and automatic Created (temporarily) on the heap via malloc(), calloc(), realloc() Must be explicitly freed via free() Address (pointer) has to go in some variable That variable has scope and storage class itself If dynamic storage is not explicitly freed, it typically exists even after the program terminates We often have to reboot/log out to clear un-freed memory TL;DR: General rules of scope and access Keep variables local, use the narrowest scope No program scope variables Few to no le scope variables Only the necessary functions with program-level access Give the internal, utility functions le-scope, if possible Only return pointers to dynamically allocated storage Never return pointer to automatic (statically allocated) variables from functions Always remember to manually free dynamically allocated storage fi fi Precedence of Operators Operator precedence determines the order in which operators are evaluated x = 25 * a + c / 2.1 Operators are used to calculate values for both numeric and pointer expressions Operators also have an associativity which is used to determine which operands are grouped with similar operators. Associativity Applies with 2 or more operators of same precedence: A op1 B op2 C op3 D Answers question: Which op is done rst? Associativity can be either Left-to-Right or Right-to-Left fi Associativity Left-to-Right (AKA left associative) is most common a + b – c; The + and – operators are both evaluated left-to-right so the expression is “a plus b, then subtract c” Equivalent to: (a + b) – c; Associativity Right-to-Left (AKA right associative) is rare a = b = c = 1; This expression is read “assign c to b, then to a” Equivalent to: a = (b = (c = 1)); Only meaningful because in C, assignment operator is an expression, resulting in a value In some other languages, e.g. Swift, assignment operator does not return a value Problems with Precedence The precedence of some operators produces problems when they create behaviours which are unexpected Don’t get clever, use parentheses Problems with Precedence Pointer to structure: *p.f Expectation: the member f of what p points to: (*p).f Actually: means *(p.f) p.f gives a compile error if p is a pointer Why?. is higher precedence than * Note: The -> operator was made to correct this. p->f Problems with Precedence int *ap[] Expectation: ap is a ptr to an array of ints int (*ap)[] Actually: ap is an array of pointers-to-int int *(ap[]) Why? [] is higher precedence than * Note: usually found in declarations. Problems with Precedence int *fp() Expectation: fp is a ptr to a function returning an int: int (*fp)() Actually: fp is a function returning a ptr-to-int: int *(fp()) Why? () is higher than * Note: usually found in declarations This is particularly bad, since in C, f() means a function with a variable number of arguments - not a function with no arguments If you want a pointer to a function that has no arguments and returns an int, declare int (*fp)(void) Problems with Precedence c = getchar() != EOF Expectation: ( c = getchar() ) != EOF Actually: c = (getchar() != EOF) c is set equal to the true/false value Why? comparators == and != have higher precedence than assignment Fix: ( c = getchar() ) != EOF Solution to Precedence Problems When in doubt, use parentheses Better still, always use parentheses You may not be in doubt, but the next reader could be Resist the temptation to write “clever” code - you might impress yourself at the time, but You will hate yourself later Your coworkers/teammates will hate you as well All other aspects being equal, always strive for clarity and readability CIS*2750 Lecture 5b: C odds and ends - types and typedefs, enumerated types searching with predicates Based on CIS*2750 notes from previous generations of CIS*2750 instructors Review: typedefs When we are dealing with large-scale software development - modules, libraries, etc. - we often have to de ne new types - so let's remember how to de ne them in C The typedef operator can be used to create aliases or shorthand notations for existing C types Typedefs do not really create new types - they are used to give existing types a new name (alias). The intent is to make code more readable and easier to write. typedef ; Syntax: keyword type new name (alias) fi Typedef Examples Consider the following de nition: struct Vec2 { float x, y; }; This de nes a new type - a structure We refer to this type as struct Vec2 in our code, e.g.: struct Vec2 u = { 0, 1 }; struct Vec2 v = { 1, 0 }; fi fi Typedef Examples We can use a typedef now: struct Vec2 { float x, y; }; typedef struct Vec2 Vector; This de nes a structure (struct Vec2) and an alias (Vector), which allows us write this: Vector u = { 0, 1 }; Vector v = { 1, 0 }; Instead of this: struct Vec2 u = { 0, 1 }; struct Vec2 v = { 1, 0 }; fi Typedef Examples The following does exactly what we did on the previous slide, but in a single statement: typedef struct Vec2 { float x, y; } Vector; Again, we can write this: Vector u = { 0, 1 }; Vector v = { 1, 0 }; instead of this: struct Vec2 u = { 0, 1 }; struct Vec2 v = { 1, 0 }; Typedef Examples The name of the alias can be the same as the name of the structure: typedef struct Vec2 { float x, y; } Vec2; Now, we can write this: Vec2 u = { 0, 1 }; Vec2 v = { 1, 0 }; instead of this: struct Vec2 u = { 0, 1 }; struct Vec2 v = { 1, 0 }; In this case, we simply created a “shorthand” notation for struct Vec2.  Types Types will be a continuous theme in this course You've been using them since you started programming in C We will de ne what a type actually is later in the course Since we are using a typed programming language, we might as well use types to our advantage Make the code more readable O oad some of the error checking onto the compiler Build good programming habits that will be useful when using languages with stronger type systems Using types correctly also helps you avoid precision issues Remember, ints are precise, but oats are often NOT ffl fi fl Rules for using types Always pick the appropriate type for the job and use the most speci c type ("narrowest") type For example: use an int instead, say, oat, if you need to store counts, lengths, and other inherently integer values use the C bool type instead of int if your value is always true or false Outside of C, this will also let you use a compiler to keep you from making accidental mistakes For example, language with strict type rules will not allow you to assign an int to a boolean variable will not allow you to assign a signed int to an unsigned int fl Rules for using types Create new, speci c types that help you model and solve a problem For example, let's say you need to store an array of 2D vectors fi Solution 1: use existing types We de ne a 2D array of oats We do not know array size at compile time, so we have to use pointers/malloc //declaration and memory allocation float** vectors; vectors = malloc(numVec*sizeof(float*)); for (int i = 0; i < numVec; i++){ vectors[i] = malloc(2*sizeof(float)); } //use for (int i = 0; i < numVec; i++){ vectors[i] = xVal; vectors[i] = yVal; } //Deallocation for (int i = 0; i < numVec; i++){ free(vectors[i]); } free(vectors); fi fl Solution 2: use a dedicated type We can use Vec2 we've de ned earlier Again, we do not know array size at compile time, so we use malloc typedef struct Vec2 { float x, y; } Vec2; //allocation Vec2* vectors = malloc(numVec*sizeof(Vec2)); //Use for (int i = 0; i < numVec; i++){ vectors[i].x = xVal; vectors[i].y = yVal; } //Deallocation free(vectors); fi  Analysis Advantages of Solution 2 E ciency: Solution 1 makes numVec calls to malloc() and numVec calls to free, Solution 2 uses one malloc and one free We use less memory (why?) Reliability: less manual memory management usually means fewer errors and less time spend debugging Readability we know what vectors[i].x is we have to guess what vectors[i] is The 2D array is n×2. What if it were 2×n? ffi Analysis Advantages of Solution 2 Maintainability and information hiding If we want to change the storage type from float to double, In Solution 1 we have to change multiple lines of code (every array declaration, all malloc calls) In Solution 2 we have to change only one line typedef struct Vec2 { double x, y; } Vec2; Moral of the story Types are useful, so let's use them! Reminder: enumerated types Enumerations De nition: an enumeration, also called enum or enumerated type, is a data type consisting of a nite set of named values. The values are internally represented as integers, at lest in C and closely related languages. When eclaring an enumeration: enum CardSuit {CLUBS, DIAMONDS,HEARTS, SPADES}; Each of the four elements (a.k.a. enumerants) is assigned a unique integer value. By default, the rst element (CLUBS) is assigned the value 0, and subsequent elements are given incremental integer values (DIAMONDS=1, HEARTS=2, SPADES=3). fi fi fi Enumerations It is possible to override the default value assignments using explicit assignments at de nition time In the following, all elements are given custom values: enum CardSuit {CLUBS = 1, DIAMONDS = 2, HEARTS = 4, SPADES = 8}; Enumerations We do not have to specify all values. If some values are omitted, the compiler will “ ll in the blanks” using the incremental numbering scheme. For example: enum CardSuit {CLUBS, DIAMONDS, HEARTS = 100, SPADES}; Here, CLUBS is assigned the default value 0, DIAMONDS becomes 1, HEARTS is given the custom value 100, and SPADES becomes 101. Enumerations Enumerations are used to represent simple symbolic information such as classifying the “type” of an object. Because enumerants are represented by integers, they can be used in arithmetic expressions just like other integer data types. This is unlike the Java enums, where enums are considered separate types from integers. To declare an enum variable, use the following syntax: enum CardSuit mysuit = CLUBS; The leading enum keyword, followed by the name of the enumeration, forms a complete type speci cation. fi Enumerations Example Consider the following enumeration de nition: enum Direction { NORTH, EAST, SOUTH, WEST }; We can de ne a function turnRight() which takes the old direction and returns the new direction. The function would be used like so: enum Direction dir = NORTH; dir = turnRight(dir); fi fi Enumerations Example N One de nition of the turnRight() function is as follows: enum Direction turnRight(enum Direction dir){ W E if (dir == NORTH) return EAST; else if (dir == EAST) return SOUTH; S else if (dir == SOUTH) return WEST; else return NORTH; } fi Enumerations Example N Another possible de nition is this: enum Direction turnRight(enum Direction dir){ return (dir + 1) % 4; } W E The latter de nition takes advantage of the fact that enums are represented as integers in a sequence. S It is shorter, but potentially less readable fi fi Enums and typedefs Typedefs also work with enumerations, like this: enum Direction { NORTH, EAST, SOUTH, WEST }; typedef enum Direction Direction; Or like this: typedef enum Direction { NORTH, EAST, SOUTH, WEST } Direction; The two de nitions are equivalent and let us declare variables like this: Direction dir1 = NORTH; Direction dir2 = WEST; fi Complete Enumeration Example See directions.c in Week 5 examples for a more complete example. Enum guidelines Use them for types with a small number of discrete values E.g. days, months, cardinal directions, error codes, etc. Advantages: They make your code more readable - using named labels instead of magic constants is always a big win Allow for some elegant code (enum values could be used as array indices, for example) They also help developing good programming habits: In languages other than C that have enums (C#, C++, Swift, Java, etc.), the compiler enforces strong rules for enum use, and prevents you from making mistakes If you are used to using enums in C, you will carry this habit into other languages, and will be able to take advantage of stronger type systems Enum guidelines As a beginner, avoid relying too much on the integer representation, and always use the labels Relying on the integer representations can decrease readability It can also can break your code if the enum changes In later assignments we might add other error codes to enum (i.e. type VCardErrorCode) If the order of existing labels changes and you rely in a speci c int value, you code will not work correctly Searching with predicates Mental exercise Imagine an array of Person structs: typedef struct name { char* firstName; char* lastName; unsigned int age; } Person; How would you like to retrieve values from it? Now imagine that you want to write a function (or functions) for searching such an array Searching based on what? How would you design and implement this? What changes if the array contains value of a di erent type, instead of the Person struct? Mental exercise After working on this exercise, you will nd that your searching depends on conditions Return the element (or elements) for which a condition holds - or an indication that there are no elements for which a condition holds fi Predicates In discrete math, predicates (or predicate functions) are boolean-valued functions Given a logical proposition, they return true or false The notion of a predicate can be extended to concrete functions implemented in a programming language A predicate would be a function that accepts one or more arguments and returns a boolean value You can think of predicates as condition testers If a condition - that depends on the arguments of the function - hols, the function returns true Otherwise the function returns false Predicates The compare() ction that we use in our List API is somewhat similar to a predicate If two arguments are equal, return a value (0) Otherwise, return a positive or negative value that indicates how the arguments should be ordered However, the function in not boolean-valued - it returns an int Moreover, returned values of -1, 0, and 1 mean three di erent things fi Predicates To turn it into a predicate, we can simplify it: return true if two arguments are equal return false otherwise Use the bool type for clarity However, what does it mean for two “things” to be equal? Searching with predicates When we search a data collection, we often want to search by di erent criteria, e.g. Find student with rst name “Rick” and last name “Sanchez” Find a student with age 25 Find if the class has any students with the last name starting with an “F” etc. This can get very complex quickly, and for advanced functionality we need database query support However, we can do a relatively simple implementation: when we search, we pass the search condition as a predicate fi Searching with predicates Generic search function for an array: Person* search(Person* array[], int arrayLen, bool (*compare)(const void*, const void*), Person* searchName); 1st argument is the array we wish to search 2nd argument is the army length 3rd argument is the predicate - the function that speci es the comparison condition 4th argument contains the value we should be searching for Returns data associated with the 1st element that satis es the condition NULL if no elements in the array satisfy the condition fi Searching with predicates See StructListDemo.c (lines 161 - 172)