Cast to void to silence warnings
Purpose: Prevent compiler warnings about “unused variables.”
Key idea: Write the variable’s name on a line by itself. Cast the variable to void and add a comment to help the next reader.
Rationale: Our handout code asks the compiler to generate as many warnings as possible. Compiler warnings usually indicate problems, and for good hygiene, you should aim to eliminate all warnings in your own code. However, sometimes the compiler needs a little help, or it will generate too many warnings. A common example is where you’re writing a function that takes more arguments than it currently uses. For instance:
void* m61_malloc(size_t sz, const char* file, int line) {
return malloc(sz);
}
Eventually, this code will use all of its arguments (to report error messages); but in the meantime we’ll see these warnings:
x.c: In function ‘m61\_malloc’:
x.c:6:41: warning: unused parameter ‘file’ \[-Wunused-parameter\]
x.c:6:51: warning: unused parameter ‘line’ \[-Wunused-parameter\]These warnings are annoying and the compiler’s chatter may help the user miss more relevant warnings. So we advise that you silence the warnings. Tell the compiler these variables are meant to be unused. Here’s how:
void* m61_malloc(size_t sz, const char* file, int line) {
(void) file, (void) line; // silence warnings
return malloc(sz);
}
The (void) casts and the comment are for human readers. Casting an expression to void explicitly throws away that expression’s value. This tells readers that the programmer intended to write a do-nothing expression. Otherwise a reader might think it was a mistake.
Sized integers
Purpose: Use standard names for specific-sized integer types.
Key idea: Standard names for important integer types are provided by #include <inttypes.h>. These names include:
uint8_t
Unsigned integer type containing exactly 8 bits. Equals unsigned char on every machine we care about.
int8_t
Signed integer type containing exactly 8 bits. Equals signed char on every machine we care about.
uint16_t, int16_t
Same for 16-bit integers. Usually equals unsigned short and short.
uint32_t, int32_t
Same for 32-bit integers.
uint64_t, int64_t
Same for 64-bit integers.
uintptr_t, intptr_t
Integer types with the same size as pointer types. On machines with 32-bit addresses, such as x86, uintptr_t is the same type as uint32_t.
On machines with 64-bit addresses, such as x86_64, uintptr_t is the same type as uint64_t.
size_t
Unsigned integer type used to represent sizes of objects that can fit in memory. This is usually the same type as uintptr_t. Every sizeof(x) expression returns a value of type size_t.
off_t
Unsigned integer type used to represent file sizes and positions within files. This might be bigger than size_t, since most machines can manipulate disk files that are larger than memory.
You may also encounter these less common integer types, which we list for completeness.
ssize_t
Signed integer type with the same width as size_t.
ptrdiff_t
Pointer subtraction expressions, such as ptr1 - ptr2, have this type. It is generally the same as intptr_t.
Vector
Purpose: Manage a growable, dynamically-allocated array. A sequence of array operations should use at most O(log M) allocations, where M is the maximum size of the array.
Key idea: Maintain both a size and a capacity. The size must always be less than or equal to the capacity. To add an element to the array, check the size against the capacity. If there is room for the new element (size < capacity), simply add the new element. If there isn't room (size == capacity), double the capacity.
struct vector_of_T {
T *data;
size_t size; // or called "n"
size_t capacity;
};
typedef struct vector_of_T vector_of_T;
void vector_initialize(vector_of_T *v) {
v->data = NULL;
v->size = 0;
v->capacity = 0;
}
/** Access element 'i' of the array. */
T *vector_get(vector_of_T *v, size_t i) {
assert(i < v->size);
return &v->data[i];
}
/** Add a copy of 'new_element' to the end of the array. */
void vector_push_back(vector_of_T *v, T *new_element) {
if (v->size == v->capacity) {
size_t new_capacity;
// Double the capacity, or create an initial capacity of 8
if (v->capacity == 0) {
new_capacity = 8;
} else {
new_capacity = v->capacity * 2;
}
// Or shorter: "new_capacity = v->capacity ? v->capacity * 2 : 8;"
v->data = (T *) realloc(v->data, sizeof(T) * new_capacity);
v->capacity = new_capacity;
}
v->data[v->size] = *new_element; // Same as: "memcpy(vector_get(v, v->size), new_element, sizeof(T));"
++v->size;
}
Linked lists
Purpose: Manage an ordered set of items with O(1) insertion and O(1) deletion, but where searching for an item isn’t common and is therefore allowed to be expensive (O(N)).
Key idea: Linked lists are a fundamental data structure, but they are not trivial to get right. We provide several variants, coded in C, for your reference. Don’t understand one? Draw pictures!
Terminology: A node is an item on a list.
The head of a list is the first item in the list. If the list is empty, its head is NULL.
The tail of a list is the last item in the list. If the list is empty, its tail is NULL.
Moving from one item to another is called traversing the list. A local variable used for traversal is often called trav.
Next pointers are used to traverse the list from the head towards the tail. Prev or previous pointers are used to traverse the list from the tail towards the head. Next pointers are more fundamental: singly-linked lists have next pointers, but not prev pointers.
On global variables: We store head and tail pointers as global variables for exposition. It’s usually better to store them as local variables or on the heap.
Variant 1: Doubly-linked list with head
O(1) operations supported: insert at head, remove
struct node {
node* next;
node* prev;
};
node* head;
void insert_head(node* n) {
n->next = head;
n->prev = nullptr;
if (head) {
head->prev = n;
}
head = n;
}
void remove(node* n) {
if (n->next) {
n->next->prev = n->prev;
}
if (n->prev) {
n->prev->next = n->next;
} else {
head = n->next;
}
}
Variant 2: Doubly-linked list with head and tail
O(1) operations supported: insert at head, insert at tail, remove
struct node {
node* next;
node* prev;
};
node* head;
node* tail;
void insert_head(node* n) {
n->next = head;
n->prev = nullptr;
if (head) {
head->prev = n;
} else {
tail = n;
}
head = n;
}
void insert_tail(node* n) {
n->next = nullptr;
n->prev = tail;
if (tail) {
tail->next = n;
} else {
head = n;
}
tail = n;
}
void remove(node* n) {
if (n->next) {
n->next->prev = n->prev;
} else {
tail = n->prev;
}
if (n->prev) {
n->prev->next = n->next;
} else {
head = n->next;
}
}