# 2021q1 Homework5 (quiz5)
contributed by < `secminhr` >
# Quiz Problems
## VV1 = ?
```c
#define NEXT_POWER_OF_2(s) \
VV1 ? s : (size_t) 1 << (64 - __builtin_clzl(s))
```
We can see that if `VV1` is true then `s` will be returned, which indicates that `s` is a power of 2.
Since a power of 2 has only a bit set, we can easily see that `s & (s-1)` must be 0, so `VV1` is `!(s & (s-1))`.
The answer is `(e)`.
## VV2 = ?
```c
#define vec_pop_back(v) (void) (VV2)
```
When we pop an item from a vector, the size of the vector should decrease by 1.`VV2` is therefore `v.size -= 1`.
The anwser is `(a)`.
## VV3 = ?
```c
static NON_NULL void __vec_push_back(void *restrict vec,
void *restrict e,
size_t elemsize,
size_t capacity)
{
...
if (v->on_heap) {
if (v->size == capacity)
v->ptr = realloc(v->ptr, VV3);
memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
} else {
...
}
}
```
We have to know first that the representation of `capacity` depends on wherther it's on heap or on stack. [See this section first](https://hackmd.io/1eFVSD3VQ2iwFB4Bly4Lcw#vec_capacity).
After figuring out the representation, it's clear now that `VV3` should be
```
(v->capacity)++;
elemsize * (size_t) 1 << v->capacity
```
Put it into one line we have:
`elemsize * (size_t) 1 << ++v->capacity`
The answer is `(b)`.
## WWW = ?
```c
static void socket_write_loop(struct cr *o, int fd, byte_queue_t *in)
{
static uint8_t *b;
cr_begin(o);
for (;;) {
cr_wait(o, WWW);
b = cr_queue_pop(in);
cr_sys(o, send(fd, b, 1, 0));
}
cr_end(o);
}
```
`WWW` is used with `cr_wait`, let's check that:
```c
#define cr_wait(o, cond) \
do { \
cr_label(o, CR_BLOCKED); \
if (!(cond)) \
return; \
} while (0)
```
When `cond` isn't satisfied, `return` will be called to exit current function. We can view this behaviour as a protection for the following lines.
Since next line is `cr_queue_pop`, we want to make sure that the queue isn't empty, `WWW` is therefore `!cr_queue_empty(in)`.
The answer is `(b)`.
## LLL = ?
```c
static void stdin_loop(struct cr *o, byte_queue_t *out)
{
static uint8_t b;
static int r;
cr_begin(o);
for (;;) {
cr_sys(o, r = read(STDIN_FILENO, &b, 1));
if (r == 0) {
cr_wait(o, cr_queue_empty(out));
cr_exit(o, 1);
}
cr_wait(o, LLL);
cr_queue_push(out, b);
}
cr_end(o);
}
```
Same idea as `WWW`, except that this time we want to make sure the queue isn't full before push.
So `LLL` should be `!cr_queue_full(out)`.
The answer is `(d)`.
# Extended Problems
## Test 1
### Principle
### Core Structure
The structure of our vector is in one of the following form:
- on-stack
```graphviz
graph {
struct[label="{metadata|{size|on_heap=0|capacity|unused}}|buf[0]|buf[1]|...", shape=record]
}
```
- on-heap
```graphviz
graph {
struct[label="{metadata|{size|on_heap=1|capacity|unused}}|ptr", shape=record]
}
```
Note that the representation of `capacity` [is different in 2 forms](https://hackmd.io/1eFVSD3VQ2iwFB4Bly4Lcw#vec_capacity).
### Macros
### Supportive Macros
These macros are used by other macros.
#### STRUCT_BODY
```c
#define STRUCT_BODY(type) \
struct { \
size_t size : 54, on_heap : 1, capacity : 6, flag1 : 1, flag2 : 1, \
flag3 : 1; \
type *ptr; \
}
```
This macro declare a struct corresponds to the on-heap form.
#### NEXT_POWER_OF_2
```c
#define NEXT_POWER_OF_2(s) \
!(s & (s - 1)) ? s : (size_t) 1 << (64 - __builtin_clzl(s))
```
Find a power of 2 that is greater or equal to `s` .
#### vec_data
```c
#define vec_data(v) (v.on_heap ? v.ptr : v.buf) /* always contiguous buffer */
```
Provide a way to access stored data without concerning vector's structure.
#### vec_elemsize
```c
#define vec_elemsize(v) sizeof(v.buf[0])
```
Get size of element.
Note that this macro can be used even if the vector stores its data on heap.
### Vector Macros
These macros provide ways to manipulate a vector without exposing its actual structure.
#### v
```c
#define v(t, s, name, ...) \
(void) ((struct { \
_Static_assert(s <= 8, "it is too big"); \
int dummy; \
}){1}); \
union { \
STRUCT_BODY(t); \
struct { \
size_t filler; \
t buf[NEXT_POWER_OF_2(s)]; \
}; \
} name __attribute__((cleanup(vec_free))) = {.buf = {__VA_ARGS__}}; \
name.size = sizeof((__typeof__(name.buf[0])[]){0, __VA_ARGS__}) / \
sizeof(name.buf[0]) - \
1; \
name.capacity = sizeof(name.buf) / sizeof(name.buf[0])
```
Create a vector called `name` with on-stack form.
if `s` is greater than 8, compile will not pass due to `_Static_assert`.
#### vec_size
```c
#define vec_size(v) v.size
```
The size of `v`.
#### vec_capacity
```c
#define vec_capacity(v) \
(v.on_heap ? (size_t) 1 << v.capacity : sizeof(v.buf) / sizeof(v.buf[0]))
```
`vec_capacity` gives the capacity of `v`.
The ternary operator `?:` indicates that the representation of `v.capacity` is different, and it depends on whether it's on stack or on heap.
If the vector stores it's elements on stack, then the capacity is calculated by `sizeof(v.buf) / sizeof(v.buf[0])`.
Otherwise, the capacity is `(size_t) 1 << v.capacity`, which is essentially $2^{\ v.capacity}$.
Notice that if the vector is on heap, when `v.capacity` increases by 1, the space the vector uses is doubled.
#### vec_pos
```c
#define vec_pos(v, n) vec_data(v)[n] /* lvalue */
```
Access to n-th element of vector data.
#### vec_reserve
```c
#define vec_reserve(v, n) __vec_reserve(&v, n, vec_elemsize(v), vec_capacity(v))
```
Reserve space for at least `n` elements.
This macro will expand to the [__vec_reserve](https://hackmd.io/1eFVSD3VQ2iwFB4Bly4Lcw#__vec_reserve) functon call.
#### vec_push_back
```c
#define vec_push_back(v, e) \
__vec_push_back(&v, &(__typeof__(v.buf[0])[]){e}, vec_elemsize(v), \
vec_capacity(v))
```
Push `e` into the vector.
Thsimacro will expand to the [__vec_push_back](https://hackmd.io/1eFVSD3VQ2iwFB4Bly4Lcw#__vec_push_back) function call.
`&(__typeof__(v.buf[0])[]){e}` will create a pointer of an array whose first element is `e`.
Note that the address of an array and that of the first element in array is the same, this gives a reason why `__vec_push_back` can directly use `memcpy`.
#### vec_pop_back
```c
#define vec_pop_back(v) (void) (v.size -= 1)
```
Decrease `size` by 1 to give the **effect** of poping out an element.
### Functions
#### ilog2
```c
static inline int ilog2(size_t n)
{
return 64 - __builtin_clzl(n) - ((n & (n - 1)) == 0);
}
```
Calculate `ceil(log2(n))`.
Examples:
- `ilog2(7)` returns 3
- `ilog2(5)` returns 3
- `ilog2(4)` returns 2
#### __vec_reserve
```c
static NON_NULL void __vec_reserve(void *vec,
size_t n,
size_t elemsize,
size_t capacity)
{
union {
STRUCT_BODY(void);
struct {
size_t filler;
char buf[];
};
} *v = vec;
if (n > capacity) {
if (v->on_heap) {
v->ptr = realloc(v->ptr,
elemsize * (size_t) 1 << (v->capacity = ilog2(n)));
} else {
void *tmp =
malloc(elemsize * (size_t) 1 << (v->capacity = ilog2(n)));
memcpy(tmp, v->buf, elemsize * v->size);
v->ptr = tmp;
v->on_heap = 1;
}
}
}
```
`NON_NULL` will expand to `__attribute__((nonnull))` to avoid `vec` being a null pointer.
This function make `v`'s capacity being the smalllest power of 2 that is greater than or equal to `n`.
#### __vec_push_back
```c
static NON_NULL void __vec_push_back(void *restrict vec,
void *restrict e,
size_t elemsize,
size_t capacity)
{
union {
STRUCT_BODY(char);
struct {
size_t filler;
char buf[];
};
} *v = vec;
if (v->on_heap) {
if (v->size == capacity)
v->ptr = realloc(v->ptr, elemsize * (size_t) 1 << ++v->capacity);
memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
} else {
if (v->size == capacity) {
void *tmp =
malloc(elemsize * (size_t) 1 << (v->capacity = capacity + 1));
memcpy(tmp, v->buf, elemsize * v->size);
v->ptr = tmp;
v->on_heap = 1;
memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
} else
memcpy(&v->buf[v->size++ * elemsize], e, elemsize);
}
}
```
Put `*e` to the end of `vec`.
If the capacity of `vec` is not big enough, it will expand in order to accept more elements.
The expanding behaviour of capacity is described as below:
- When elements of `vec` stores on heap
In this case, the capacity is doubled. Check [the representation of capacity](https://hackmd.io/1eFVSD3VQ2iwFB4Bly4Lcw#vec_capacity) in case you forgot.
- When elements of `vec` stores on stack
In this case, the elements will be moved to heap, and the capacity of `vec` will become $2^{1+(old\ capacity)}$.
For example, given a vector `v(float, 8, vec)`, its capacity after 9-th `vec_push_back` will be $512=2^{1+8}$.
### Verify layout
## Test 2
Sign in with Wallet
Connect another wallet