The readings for April 3, 2017 are:

Alternatively, if you have the Data Structures textbook:

1. Data Structures and Other Objects Using C++:

• Sections 12.2 - 12.4

#### TL;DR

The focus of this reading is to how integers and unions are represented in C and how hash tables work. You should become familiar with both separate chaining and open addressing forms of managing collisions.

## Activities

In your `reading09/README.md`, response to the following questions:

1. Given the C code below:

```struct Struct {
char *  string;
int     number;
};

union  Union {
char *  string;
int     number;
};

struct Struct s;
union  Union  u
```
1. What is the size of `s` and what is the size of `u`?

2. What is the difference between a union and a struct?

2. Given the C code below (message.c):

```/* message.c */

#include <stdio.h>
#include <stdlib.h>

union Value {
char    as_c;
short   as_s;
int     as_i;
long    as_l;
};

struct Thing {
union Value v0;
union Value v1;
union Value v2;
};

#define DUMP_BITS(_v) \
for (int i = sizeof(_v)*8 - 1; i >= 0; i--) {\
if ((i + 1) % 8 == 0) putc(' ', stdout); \
putc(((_v).as_l & 1UL<<i) ? '1' : '0', stdout); \
} \
putc('\n', stdout);

int main(int argc, char *argv[]) {
struct Thing t = {0};

t.v0.as_i  = 0x65746166;
t.v0.as_l |= (544434464UL << 32);

t.v1.as_l  = (0x6261726FUL << 32);
t.v1.as_i  = ((673304440UL * 3 + 1));

t.v2.as_l  = 0xA210000;
t.v2.as_s  = 25856;
t.v2.as_c  = 108;

char *s = (char *)&t;
for (size_t i = 0; i < sizeof(struct Thing); i++) {
putc(s[i], stdout);
}

return 0;
}
```
1. What message does this program output?

Note: this is only guaranteed to work on a `64`-bit Linux machine like the student machines.

2. Use the `DUMP_BITS` macro to explore this program and then explain how it works (that is, how does setting the values above in the ```struct Thing t``` object yield the final message).

```/* Use DUMP_BITS macro to view the binary contents of t.v0 */
DUMP_BITS(t.v0)
```
3. What does this program tell you about types, memory, and how data is represented in C? What are we really doing when we cast values in C?

#### Obfuscated C Code

C is notorious for permitting obfuscated or complex code. In fact, there is even an International Obfuscated C Code Contest. Check out some of the previous winners for some lulz and wtfs.

3. A hash table can be classified by how it handles collisions:

1. What exactly is a collision?

2. How are collisions handled in a hash table that uses separate chaining?

3. How are collisions handled in a hash table that uses open addressing (e.g. linear probing)?

4. Starting with an empty hash table:

Bucket Value
0
1
2
3
4
5
6
7
8
9

1. Using separate chaining and using the hash function `h(x) = x % 10`, show the result of inserting the following values into the table:

7, 3, 2, 78, 56, 72, 79, 68, 13, 14

2. Using open addressing (and linear probing with an interval of `1`), and using the hash function `h(x) = x % 10`, show the result of inserting the following values into the table:

7, 3, 2, 78, 56, 72, 79, 68, 13, 14

## Feedback

To submit your assignment, please commit your work to the `reading09` folder in your assignments GitLab repository. Your `reading09` folder should only contain the following files:
• `README.md`