Arrays and Strings

Question 1

Making Arrays

Answer 1

• When you declare an array, you get to specify
  – The type of its elements
  – How many elements it will have
  – How they will be initialized (if at all)
  Example: int a[ 10 ];
• Notice, part of the type is given before the
  variable name, part after.
• In many contexts, the number of elements must be an integer constant expression

Question 2

Meet the Array(Notation and Similarity to Java)

Answer 2

• Array notation is similar to Java
• You can access element i in array a: a[ i ]
  – For an n-element array, indices range from 0 to n-1
• You can also say it backward: i[ a ]
  – Why can you do this?
  – It’s a consequence of what the a[ i ] notation
  really means in C
  – We’ll learn about this later

Question 3

C vs Java

Answer 3

• In C, declaring an array variable
  allocates the array.
  int a[10];
• In C, arrays can be allocated statically,
  on the stack or on the heap (later).
• In Java, you need to declare and allocate
  an array.
  int[] a = new int [ 10 ];
• In Java, all arrays are always allocated on
  the heap.

Question 4

Array Initialization

Answer 4

• Initialization rules are like other variables
  – If you don’t initialize a stack-allocated array, it will contain whatever was previously in that memory.
  int a[ 20 ];
  for ( int i = 0; i < 20; i++ )
  printf( “%d “, a[ i ] ); –> Outputs Garbage
  – If you don’t initialize a statically-allocated array, it starts out full of zeros.
• You can fill in the elements one at a time.
  int a[ 20 ];
  a[ 0 ] = 7;
  a[ 1 ] = 14;
  …;

Question 5

Array Initialization

Answer 5

• Or, you can ask the compiler to initialize it for
  you:
  int a[ 5 ] = { 7, 14, 21, 28, 35 };
• If you initialize just some of the array, the rest
  will be initialized to zero.
  – This is called partial initialization.
  int a[ 5 ] = { 7, 14, 21 };

Question 6

Array Initialization

Answer 6

You can let the compiler determine the size
– by measuring the length of your initialization list
int a[] = { 7, 14, 21, 28, 35 };
* C99 offers an alternative initialization syntax
int a[] = { [7] = 10, [2] = 40, [5] = 35 };
0 0 40 0 0 35 0 10
* You can even mix the two notations
– Where you give an index, C will put the given
value there.
– Where there’s no index, C will fill the subsequent index.
– If you don’t give an array size, you’ll get an array that’s just large enough to hold the last value
int a[] = { 1, [7] = 10, 90, [2] = 40, 2,
[5] = 35 };
1 0 40 2 0 35 0 10 90

Question 7

Array Bounds Checking

Answer 7

• C does no bounds checking for array access
  – Like many things in C, this decision favors
  performance over security
  – And, in many situations, the compiler may not even know the size of the array anyway.
  more program memory … 0 0 0 0 0 0 … more program memory
• Accessing memory outside an array’s bounds can do lots of neat things.
  – Accidentally overwrite some of your program’s variables
  – Segmentation fault, bus error.
• These errors can be difficult to debug.
  – Maybe you overwrite an important variable or something your program needs to keep running.
  – If you’re lucky, this may crash your program right away.
  – If you’re unlucky, your program may crash … later

Question 8

Looking at Memory when Array goes out of Bounds

Answer 8

• What do you get if you index off the end?
• Example program howdyNeighbor.c
  int x = 25;
  int a[ 3 ] = { 10, 20, 30 };
  int y = 50;
  printf( “Array a: %d %d %d\n”, a[ 0 ], a[ 1 ], a[ 2 ] );
  printf( “A little before a: %d %d\n”, a[ -2 ], a[ -1 ] );
  printf( “A little after a: %d %d\n”, a[ 3 ], a[ 4 ] );
  Output:
  Array a: 10 20 30
  A little before a: 4195712 50
  A little after a: 25 1876150896
• From the example, I think this is what we’re
  seeing:
  …y 0 0 0 0 0 0 x…
• In this example, we’re looking around in other
  parts of the stack frame.
  – Where the function stores its local variables and
  other values it needs.
• So every array is like a little window into our
  program’s memory

Question 9

Array Bounds Checking Java vs C

Answer 9

• In Java, a bad index has defined behavior … it will throw an exception.
• C says behavior is undefined … it could do
  anything … probably nothing good … for us.
• Accidentally writing past array bounds could be an exploitable vulnerability in our programs.
• An attacker could use this to change the data or behavior of a program.

Question 10

Buffer Overflow

Answer 10

• A buffer overflow happens when a program
  writes into memory past the end of an array.
  – Typically while reading input from a user or
  another program.
  It’s an easy mistake to make:
  printf( ”Please enter some numbers\n” );
  int list[ 20 ];
  int i = 0;
  while ( scanf( ”%d”, &list[ i ] ) == 1 )
  i++;

Question 11

Operations on Array

Answer 11

• Normally, we work with an array one element
  at a time.
• C syntax includes very little for working with
  the whole array at once.
  – You can’t copy from one array to another:
  list2 = list;
  – Or concatenate two arrays, etc.
  list3 = list + list2;
• Instead, we typically need loops to process
  everything in an array:
  int list2[ SIZE ];
  for ( int j = 0; j < SIZE; j++ ) {
  list2[ j ] = list[ j ];
  }

Question 12

Choosing Array Size

Answer 12

The size of a statically allocated array must be
a constant expression.
int sequence[ 100 ];
int main(){
…
* This is true in some other contexts also.
* … and used to be true for stack-allocated
arrays.

Question 13

Variable-Length Arrays

Answer 13

• C99 permits the size of stack-allocated arrays
  to be determined during execution.
  int main( void )
  {
  int n;
  printf( “How many values would you like: “ );
  scanf( “%d”, &n );
  int list[ n ];
  …
  }
  This is called a
  variable-length array.
  What if n is zero? or negative? - undefined behavior
• Variable-length arrays aren’t resizable
  – Once you choose the size, you’re stuck with it for the array’s lifetime.
  int n;
  printf( ”How many values? ” );
  scanf( “%d”, &n );
  int list[ n ];
  … do some stuff…
  printf( ”Now how many? ” );
  scanf( “%d”, &n );
  int list[ n ]; -> This won’t work; looks like
  you’re trying to declare a new array.
• But, you can choose a different size every time the variable goes into scope:
  for ( int i = 0; i < 10; i++ ) {
  int n;
  printf( ”How many values? ” );
  scanf( “%d”, &n );
  int list[ n ]; -> This will work.
  A new array on each
  iteration.
  }

Question 14

Array Size in Memory

Answer 14

• You remember the sizeof operator … right?
• It reports the size of its argument, including array arguments.
  – An array’s size is the number of elements times the size of each element.
  #include <stdlib.h>
  int a;
  float b[100];
  double c[ 16 ];
  size_t aSize = sizeof( a );
  size_t bSize = sizeof( b );
  size_t cSize = sizeof( c );</stdlib.h>

Question 15

Variable-Length Array Initilization

Answer 15

• Initialization syntax doesn’t work with variablelength arrays.
  – Maybe that’s no surprise. How many values would you need?
  int a[ n ] = { 1, 2, 3 };
  – Not even the empty initializer syntax.
  int a[ n ] = { };

Question 16

Computing Array Size

Answer 16

• The sizeof operator can (sometimes) let you
  figure out array length (number of elements)
  float b[ 100 ];
  …
  int len;
  len = sizeof( b ) / sizeof( b[0] );
  It may not look like it, but this is really a constant expression.
  This is a great trick … but it doesn’t work everywhere.’
  Here, sizeof() can be evaluated at compile time

Question 17

Allocating Large Arrays

Answer 17

• Larger arrays can be allocated statically
  – The compiler can plan ahead for static storage.
  int bigTable[ 100000000 ];
  int bill()
  {
  bigTable[ 0 ] = 1;
  return bigTable[ 0 ];
  }
  int bill()
  {
  static int bigTable[ 100000000 ];
  bigTable[ 0 ] = 1;
  return bigTable[ 0 ];
  }
• Or a large array could be dynamically allocated
  … more about this later.

Question 17

Arrays and Stack Space

Answer 17

• Arrays can be stack-allocated.
• But, in practice, stack space is limited.
• A big array on the stack is an easy way to use
  it up.
• Or, deeply nested recursion will do it too.
  int bill()
  {
  int bigTable[ 100000000 ]; -> probably going to segfault
  bigTable[ 0 ] = 1;
  return bigTable[ 0 ];
  }

Question 18

Array and Functions

Answer 18

• Functions can have array parameters
• … but not array return values.
• Arrays are automatically passed by reference

Question 19

Arrays as Parameters

Answer 19

• Arrays are automatically passed by reference
  – The function uses the same array used by the caller (not a copy of it)
  void printList( int list[5] )
  {
  for ( int i = 0; i < 5; i++ )
  …;
  }
  int a[5] = { 7, 20, 35, 51, 77 };
  . . .
  printList( a );
  – The function can change the contents of the array
  – … and the changes will still be there after the function returns (just
  like in Java).
  void addList( int list[5] )
  {
  for ( int i = 0; i < 5; i++ )
  list[ i ] += 1;
  }
  int a[5] = { 7, 20, 35, 51, 77 };
  . . .
  addList( a ); –> 8, 21,36, 52, 78

Question 20

Array Parameter Size

Answer 20

• An array parameter can omit the array size
  (this is common)
  – The function can be called on an array of any size
  void printList( int list[] )
  {
  for ( int i = 0; i < 5; i++ )
  …;
  }
  int a[5] = { 7, 20, 35, 51, 77 };
  . . .
  printList( a );
• If an array parameter could have any number
  of elements …
• … how can the function tell how many there
  are?
  void printList( int list[] )
  {
  for ( int i = 0; i < 5; i++ ) –> how many? 5?
  …;
  }
  int a[7] = { 7, 20, 35, 51
  77, 84, 103 };
  printList( a );
• Using sizeof() won’t work here.
  – It will compile, but it doesn’t give you the value you want.
  void printList( int list[] )
  {
  int len = sizeof( list ) / sizeof( int ); ->
  This doesn’t work here! Gievs size of pointer
  for ( int i = 0; i < len; i++ )
  …;
  }
  int a[8] = { 7, 20, 35, 51
  77, 84, 103, 118 };
  printList( a );
• Typically, you need an extra parameter to pass
  the array length.
  void printList( int len, int list[len] )
  {
  for ( int i = 0; i < len; i++ )
  …;
  }
  int a[9] = { 7, 20, 35, 51, 77
  84, 103, 118, 142 };
  printList( 9, a );

Question 21

Working with Strings

Answer 21

• A string is a sequence of character codes
  – Just like in java
• In C, a string is stored as a char array.
  – With a zero byte to mark the end of the string.
  Pic on doc: https://docs.google.com/document/d/1L2NK8XdgVRe6QhtoSR1Rtp7bu08axBrCecPwqu22vyQ/edit?usp=sharing

Question 22

Initializing a String

Answer 22

• Strings have a short-hand initialization syntax.
  – Automatically puts a null terminator at the end.
  char astr[10] = “hello”;
  – This is another example of partial initialization.
  – … remaining elements will be set to zero.
• You can let the compiler determine array size.
  – Reserves exactly enough space for the contents and the terminator.
  char astr[] = “hello”;

Question 23

Strings in C

Answer 23

• To store a string, you can make a char array.
  – Be sure to reserve enough space for …
  – … the string’s contents …
  – … plus one more element for the null terminator.
  char astr[10]; -> 9 character string
  char bstr[25]; -> 24 character string

Question 24

Iterating over a String

Answer 24

* The null terminator marks the end of the string’s body. * The null terminator evaluates to false, every other character evaluates to true. * This is how you’d normally iterate over characters in a string: for ( int i = 0; str[ i ]; i++ ) if ( str[ i ] >= ‘a’ && str[ i ] <= ‘z’ ) str[ i ] = ‘#";

Question 25

String Parameters

Answer 25

* Normally, we might need to pass array length to a function. void processList( int len, int list[len] ); * But not with strings. – The null terminator says how long the string is – … without needing to pass this as an extra parameter. void processList( int len, int list[len] ); void processString( char str[] );

Question 26

String I/O

Answer 26

* printf()can print the string in a char array * That’s what the conversion specifier %s does. char name[] = "Theodore"; printf( "Hello %s\n", name ); * scanf() will read strings with %s – It reads a single word – A space-delimited sequence of non-whitespace characters. * Scanf follows the convention of null-terminating the string it reads. char str[ 30 ]; --> room for 29-character string scanf( "%s", str );

Question 27

Reading Strings

Answer 27

char str[30]; scanf( “%s”, str ); -> No & on a string parameter.. * Why no & on the str parameter? – Arrays are automatically passed by reference. – We don’t need extra syntax to ask for this. char str[30]; scanf( “%s”, str ); -> buffer overflow vulnerability To avoid buffer overflow: * scanf() lets you limit the length of a word you will read. – That’s what the field width char str[30]; scanf( “%29s”, str ); I have room for a 29-character string.I won’t store more than 29 characters. Then the null terminator.

Question 29

Copying Strings

Answer 29

* You can’t copy between strings with the assignment operator. char buffer[100] = “abc123”; buffer = “Welcome to C”; * This doesn’t work for arrays … and strings are stored in arrays …so * … but, there are library functions to help us out

Question 30

Help from the Standard Library

Answer 30

* The C standard library offers functions to work with strings. * String functions are declared in the string.h header: #include * All these functions expect null terminated strings. * Today, we’ll look at functions to: – Measure string length – Copy between strings – Compare strings – Convert strings to ints, doubles, longs, etc.

Question 31

String Length

Answer 31

* We have strlen() to obtain string length: size_t strlen( const char s[] ); – Counts characters up to (but not including) the null terminator. * The prototype tells us a lot about the function: size_t strlen( const char s[] ); I take an array of characters. But, I promise not to modify it(const) I return the length, as a size_t (which will convert to int if you want)

Question 32

String Length

Answer 32

* It’s easy to use: int len = strlen( name ); * It’s not too smart. – It just looks for the null terminator. – So, it has a cost that’s linear in the string length. * This is a bad way to iterate over a string: for ( int i = 0; i < strlen( word ); i++ ) ...; * This is much more efficient (and maybe easier): for ( int i = 0; word[ i ]; i++ ) ...;

Question 33

strlen() vs sizeof

Answer 33

* Sometimes, people have some confusion between strlen() and sizeof. char buffer[ 16 ] = “testing”; size_t s = sizeof buffer; I’m an operator, usually evaluated at compile time. I don’t depend on what’s in the string. I’ll say 16. size_t n = strlen( buffer ); I’m a function call, executed at runtime. buffer[ 1 ] = ‘\0’; n = strlen( buffer ); I’ll say 7. I depend on what’s in the string. s = sizeof buffer; Now, I’ll say 1. But still 16 here.

Question 34

Copying Strings

Answer 34

* We have strcpy() to copy strings: – Copies from src to dest, up to and including the null terminator. – Return a pointer to the start of the destination string (in case you want to do something else with it) void strcpy(char dest[], char src[]); -> return type is not really void – Copies from src to dest, up to and including the null terminator. – Return a pointer to the start of the destination string (in case you want to do something else with it) * We can copy from literal strings strcpy( myString, “Greetings Program” ); * We can copy from one char array to another strcpy( myString, name ); * But, there’s a potential for buffer overflow: strcpy( myString, “Big, giant string that you ” “weren’t planning for and you don’t have enough “ “room to store” );

Question 35

Copying Strings, with Restraint

Answer 35

Its friend, strncpy(), can make it easier to prevent this. – It takes an extra parameter, n, limiting the number of characters written to dest. – It pads with zeros up to n Copying Strings, with Restraint void strncpy(char dest[], char src[], size_t n); strncpy( dest, src, 10 ); * So, this might be typical usage, if it did the right thing … which it doesn’t. strncpy( dest, src, sizeof( dest ) ); * Caution, strncpy() won’t null terminate if it runs out of room. * If we want to guarantee null termination, we will need to do it ourselves: strncpy( buffer, word, sizeof( buffer ) - 1 ); buffer[ sizeof( buffer ) – 1 ] = ‘\0’;

Question 36

Comparing Strings

Answer 36

* We have strcmp() to compare strings: int strcmp( char s1[], char s2[] ); – Lexicographically compares strings s1 and s2, returning: * Less than zero if s1 is before s2 * Zero if they are equal * Greater than zero if s1 is after s2 – Stops when it hits a null terminator or a character on which they differ * We can use it to compare strings for equality: if ( strcmp( name1, name2 ) == 0 ) ...; * It’s easy to make a mistake if you just use strcmp() as a truth value. if ( strcmp( passwd, “joshua” ) ) printf( “They’re equal\n");

Question 37

Comparing with Caution

Answer 37

* There are bounded versions of lots of the string-handling functions. * Want to look at just part of a string? We’ve got a function for that: int strncmp( char s1[], char s2[], size_t n); – Compares at most n characters in s1 and s2. – Useful if one of your strings isn’t null terminated – … or you just want to look at the start of a string

Question 38

Literal String Concatenation

Answer 38

* The compiler will automatically concatenate consecutive string literals. char s1[] = "Now " "is " "the " "time"; int len = strlen( s1 ); * This is a way to break up really long string literals (e.g., over multiple lines). * It doesn’t work for arbitrary strings. char s3[] = s1 s1;

Question 39

Concatenating String

Answer 39

* There’s a standard library function to do concatenation. void strcat(char dest[], char src[]); – Copies the string from source to the end of dest. – Overwriting the null terminator and writing out a new one. – You have to consider possible buffer overflows. * strncat() can help. – It lets you give a bound on the length of the string appended void strncat(char dest[], char src[], size_t n); – So, you might use it like: strncat( dest, src, 4 ); – Or, more generally: strncat( dest, src, sizeof(dest) – strlen(dest) – 1 );

Question 40

Parsing Numerical Values

Answer 40

* We can parse strings as numeric values * Say you want to parse an int out of a string? – atoi() will do that for you (declared in stdlib.h) int atoi(char str[]); * atoi() has some friends, for other types of conversions – There’s atof() for parsing strings as doubles. double atof(char str[]); – There’s atol() for parsing strings as long ints. long atol(char str[]); – There’s atoll() for parsing strings as long long ints. long long atoll(char str[]); * These functions are OK (but I almost never use them)

Question 41

Problems with atoi() and Friends

Answer 41

* Given an invalid parameter value, these functions return zero. * So, you can’t tell the difference between: int x = atoi( “0” ); and int x = atoi( “garbage” ); * Later, we’ll see a general-purpose way to do all these conversions.