# 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