Reading 09: Data Representation

Readings

The readings for April 3, 2017 are:

Alternatively, if you have the Data Structures textbook:

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.

Optional Resources

Data Structures & Algorithm Analysis
- 9.4 Hashing
Algorithms
- 3.4 Hash Tables
Designing a fast Hash Table

Activities

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

Given the C code below:

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

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

struct Struct s;
union  Union  u

What is the size of s and what is the size of u?
What is the difference between a union and a struct?

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;
}

What message does this program output?

Note: this is only guaranteed to work on a 64-bit Linux machine like the student machines.
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)
```
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.

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)?
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

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

Feedback

If you have any questions, comments, or concerns regarding the course, please provide your feedback at the end of your response.

Submission

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