6.087-5 Pointers and memory addressing. Arrays and Strings

6.087 Lecture 5 – January 15, 2010Review Pointers and Memory Addresses Physical and Virtual Memory Addressing and Indirection Functions with Multiple Outputs Arrays and Pointer Arithmetic Strings String Utility Functions Searching and Sorting Algorithms Linear Search A Simple Sort Faster Sorting Binary Search 1 Review: Unconditional jumps• goto keyword: jump somewhere else in the same function • Position identified using labels • Example (for loop) using goto: {int i=0, n=20; /∗ initialization ∗ /goto loop_cond ;loop_body : /∗ body of loop here ∗ /i ++;loop_cond :if (i • types: d, i (int), u, o, x, X (unsigned int), e, E, f, F, g, G (double), c (char), s (string) • flags, width, precision, length -modify meaning and number of characters printed • Formatted input: scanf() -similar form, takes pointers to arguments (except strings), ignores whitespace in input 3 Review: Strings and character arrays• Strings represented in C as an array of characters (char []) • String must be null-terminated (’\0’ at end) Declaration: • char str[] = "I am a string."; orchar str[20] = "I am a string.";• strcpy() -function for copying one string to another • More about strings and string functions today. . . 4 6.087 Lecture 5 – January 15, 2010Review Pointers and Memory Addresses Physical and Virtual Memory Addressing and Indirection Functions with Multiple Outputs Arrays and Pointer Arithmetic Strings String Utility Functions Searching and Sorting Algorithms Linear Search A Simple Sort Faster Sorting Binary Search 5 Pointers and addresses• Pointer: memory address of a variable • Address can be used to access/modify a variable from anywhere • Extremely useful, especially for data structures • Well known for obfuscating code 5 Physical and virtual memory• Physical memory: physical resources where data can be stored and accessed by your computercache• RAM• hard disk • • removable storage • Virtual memory: abstraction by OS, addressable space accessible by your code 6 Physical memory considerations• Different sizes and access speeds • Memory management – major function of OS • Optimization – to ensure your code makes the best use of physical memory available • OS moves around data in physical memory during execution • Embedded processors – may be very limited 7 Virtual memory• How much physical memory do I have? Answer: 2 MB (cache) + 2 GB (RAM) + 100 GB (hard drive) + ... • How much virtual memory do I have? Answer: <4 GB (32-bit OS), typically 2 GB for Windows, 3-4 GB for linux • Virtual memory maps to different parts of physical memory • Usable parts of virtual memory: stack and heap • stack: where declared variables go • heap: where dynamic memory goes 8 Addressing variables• Every variable residing in memory has an address! What doesn’t have an address? • • register variables • constants/literals/preprocessor defines • expressions (unless result is a variable) • How to find an address of a variable? The & operator int n= 4;double pi = 3.14159;int ∗pn =&n; /∗ address of integer n ∗ /double ∗ ppi =π /∗ address of double pi ∗ /• Address of a variable of type t has type t * 9 Dereferencing pointers• I have a pointer – now what? • Accessing/modifying addressed variable: dereferencing/indirection operator * /∗ prints "pi = 3.14159\n " ∗ /printf ( "pi = %g\n" ,∗ ppi ); /∗ pi now equals 7.14159 ∗ /∗ ppi = ∗ ppi + ∗pn ; • Dereferenced pointer like any other variable • null pointer, i.e. 0(NULL): pointer that does not reference anything 10 Casting pointers• Can explicitly cast any pointer type to any other pointer type ppi =(double ∗)pn; /∗ pn originally of type ( int ∗) ∗/• Implicit cast to/from void * also possible (more next week. . . ) • Dereferenced pointer has new type, regardless of real type of data • Possible to cause segmentation faults, other difficult-to-identify errors • What happens if we dereference ppi now? 11 Functions with multiple outputs• Consider the Extended Euclidean algorithm ext_euclid(a,b) function from Wednesday’s lecture • Returns gcd(a, b), x and y s.t. ax + by = gcd(a, b) • Used global variables for x and y • Can use pointers to pass back multiple outputs: int ext_euclid(int a, int b, int ∗x, int ∗y); • Calling ext_euclid(), pass pointers to variables to receive x and y:int x, y, g;/∗ assume a, b declared previously ∗ /g = ext _euclid(a,b,&x,&y); • Warning about x and y being used before initialized 12 Accessing caller’s variables• Want to write function to swap two integers • Need to modify variables in caller to swap them • Pointers to variables as arguments void swap( int ∗x, int ∗y) {int temp = ∗x;∗x= ∗y;∗y = temp ;} • Calling swap() function: int a= 5, b= 7;swap(&a, &b);/∗ now, a=7, b=5 ∗ /13 Variables passing out of scope• What is wrong with this code? #include char get_message ( ) {∗ char msg[] = "Aren’t pointers fun?" ; return msg; } int main ( void ){char string = get_message();∗ puts(string );return 0;}14 Variables passing out of scope• What is wrong with this code? #include char get_message ( ) {∗ char msg[] = "Aren’t pointers fun?" ; return msg; } int main ( void ){char string = get_message();∗ puts(string );return 0;} • Pointer invalid after variable passes out of scope 14 6.087 Lecture 5 – January 15, 2010Review Pointers and Memory Addresses Physical and Virtual Memory Addressing and Indirection Functions with Multiple Outputs Arrays and Pointer Arithmetic Strings String Utility Functions Searching and Sorting Algorithms Linear Search A Simple Sort Faster Sorting Binary Search 15 Arrays and pointers• Primitive arrays implemented in C using pointer to block of contiguous memory • Consider array of 8 ints: int arr [8]; • Accessing arr using array entry operator: int a = arr [0]; • arr is like a pointer to element 0 of the array: int ∗pa = arr; int ∗pa = &arr[0]; ⇔ • Not modifiable/reassignable like a pointer 15 The sizeof() operator• For primitive types/variables, size of type in bytes: int s= sizeof(char); /∗ == 1 ∗/double f; /∗ sizeof(f) ==8 ∗/(64-bit OS) • For primitive arrays, size of array in bytes: int arr [8]; /∗ sizeof(arr) == 32 ∗/(64-bit OS) long arr [5]; /∗ sizeof(arr) == 40 ∗/(64-bit OS) • Array length: /∗ needs to be on one line when implemented ∗ /#define array _length(arr) ( sizeof (arr) == 0? 0 : sizeof ( arr )/sizeof ((arr )[0])) • More about sizeof() next week. . . 16 Pointer arithmetic• Suppose int ∗pa = arr; • Pointer not an int, but can add or subtract an int from a pointer: pa + i points to arr[i] • Address value increments by i times size of data type Suppose arr[0] has address 100. Then arr[3] has address 112. • Suppose char ∗ pc= (char ∗)pa; What value of i satisfies (int ∗)(pc+i) == pa + 3? 17 Pointer arithmetic• Suppose int ∗pa = arr; • Pointer not an int, but can add or subtract an int from a pointer: pa + i points to arr[i] • Address value increments by i times size of data type Suppose arr[0] has address 100. Then arr[3] has address 112. • Suppose char ∗ pc= (char ∗)pa; What value of i satisfies (int ∗)(pc+i) == pa + 3? i = 12 • 17 6.087 Lecture 5 – January 15, 2010Review Pointers and Memory Addresses Physical and Virtual Memory Addressing and Indirection Functions with Multiple Outputs Arrays and Pointer Arithmetic Strings String Utility Functions Searching and Sorting Algorithms Linear Search A Simple Sort Faster Sorting Binary Search 18 Strings as arrays• Strings stored as null-terminated character arrays (last character == ’\0’) • Suppose char str[] = "This is a string."; and char ∗ pc= str; • Manipulate string as you would an array ∗(pc+10) = ’S’; puts(str ); /∗ prints "This is a String ." ∗/18 String utility functions• String functions in standard header string.h • Copy functions: strcpy(), strncpy() char ∗ strcpy(strto,strfrom); –copy strfrom to strto char ∗ strncpy(strto,strfrom,n); –copy n chars from strfrom to strto • Comparison functions: strcmp(), strncmp() int strcmp(str1,str2); – compare str1, str2; return 0 if equal, positive if str1>str2, negative if str1 ivalue; i −−) arr[i] = arr[i −1]; /∗ move element down ∗ /arr[i] = ivalue; /∗ insert element ∗ /} 24 Insertion sort• Main insertion sort loop /∗ iterate until out−of−order element found ; shift the element , and continue iterating ∗ /void insertion _sort ( void ){unsigned i n t i, len = array _length(arr);for (i =1; i= right)return ;/∗ nothing to sort ∗ //∗ pivot is midpoint; move to left side ∗ /swap(arr+left ,arr + (left+right)/2);pivot = arr[mid = left ];/∗ separate into side < pivot (left+1 to mid) and side >= pivot (mid+1 to right ) ∗ /for (i = left+1; i <= right; i++)if (arr[i] < pivot)swap(arr + ++mid,arr + i);[Kernighan and Ritchie. The C Programming Language. 2nd ed. Prentice Hall, 1988.] © Prentice Hall. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/fairuse. 27 Quicksort implementation• Restore the pivot; sort the sides separately: /∗ restore pivot position ∗ /swap(arr+left , arr+mid); /∗ sort two sides ∗ /if (mid > left) quick _sort(left , mid −1); if (mid < right ) quick _sort(mid+1,right ); } • Starting the recursion:quick_sort(0, array_length(arr) − 1);[Kernighan and Ritchie. The C Programming Language. 2nd ed. Prentice Hall, 1988.] © Prentice Hall. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/fairuse. 28 Discussion of quicksort• Not stable (equal-valued elements can get switched) in present form • Can sort in-place – especially desirable for low-memory environments • Choice of pivot influences performance; can use random pivot • Divide and conquer algorithm; easily parallelizeable • Recursive; in worst case, can cause stack overflow on large array 29 Searching a sorted array• Searching an arbitrary list requires visiting half the elements on average • Suppose list is sorted; can make use of sorting information: • if desired value greater than value and current index, only need to search after index • each comparison can split list into two pieces • solution: compare against middle of current piece; then new piece guaranteed to be half the size • divide and conquer! • More searching next week. . . 30 Binary search• Binary search: O(log n) average, worst case: int binary_search ( int val) {∗ unsigned i n t L = 0, R = array _length(arr), M; while (L