# [2020q3](http://wiki.csie.ncku.edu.tw/sysprog/schedule) 第 11 週測驗題
###### tags: `sysprog2020`

:::info
目的: 檢驗學員對 bitwise 運算及空間效率的認知
:::

==[作答表單](https://docs.google.com/forms/d/e/1FAIpQLSfpPYNJuGBPIyXXQgIBC8ebMpm_6lttqk9IqjZCTPy1kB7s4Q/viewform)==

### 測驗 `1`

考慮到一個針對空間處理最佳化的 vector 實作
支援以下操作:
* `vec_push_back` : 新增元素至 vector 的尾端，必要時會進行記憶體配置;
* `vec_pop_back()` : 刪除 vector 最尾端的元素;

每個 vector 都有兩個重要的屬性:
* 容量 (capacity) : 是這個 vector 擁有的空間。
* 長度 (size): 實際儲存了元素的空間大小。capacity 永遠不小於 size

使用示範:

int main()
{
    v(float, 3, vec1);
    v(int, 2, vec2, 13, 42);

    printf("pos(vec2,0)=%d, pos(vec2,1)=%d\n", vec_pos(vec2, 0),
           vec_pos(vec2, 1));
    vec_push_back(vec2, 88);
    vec_reserve(vec2, 100);
    printf("capacity(vec1)=%zu, capacity(vec2)=%zu\n", vec_capacity(vec1),
           vec_capacity(vec2));
    printf("pos(vec2,2)=%d\n", vec_pos(vec2, 2));

#define display(v)                               \
    do {                                         \
        for (size_t i = 0; i < vec_size(v); i++) \
            printf("%.2f ", vec_pos(v, i));      \
        puts(v.on_heap ? "heap" : "stack");      \
    } while (0)

    display(vec1);
    vec_push_back(vec1, 0.0);
    display(vec1);
    vec_push_back(vec1, 1.1);
    display(vec1);
    vec_push_back(vec1, 2.2);
    display(vec1);
    vec_push_back(vec1, 3.3);
    display(vec1);
    vec_push_back(vec1, 4.4);
    display(vec1);
    vec_push_back(vec1, 5.5);
    display(vec1);
    vec_pop_back(vec1);
    display(vec1);
    vec_pop_back(vec1);
    display(vec1);
    vec_pop_back(vec1);
    display(vec1);
    vec_pop_back(vec1);
    display(vec1);
    vec_pop_back(vec1);
    display(vec1);
    vec_pop_back(vec1);
    display(vec1);

    return 0;
}

預期輸出:

pos(vec2,0)=13, pos(vec2,1)=42
capacity(vec1)=4, capacity(vec2)=128
pos(vec2,2)=88
stack
0.00 stack
0.00 1.10 stack
0.00 1.10 2.20 stack
0.00 1.10 2.20 3.30 stack
0.00 1.10 2.20 3.30 4.40 heap
0.00 1.10 2.20 3.30 4.40 5.50 heap
0.00 1.10 2.20 3.30 4.40 heap
0.00 1.10 2.20 3.30 heap
0.00 1.10 2.20 heap
0.00 1.10 heap
0.00 heap
heap

本體的實作程式如下:

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

/* vector with small buffer optimization */

#define STRUCT_BODY(type)                                                  \
    struct {                                                               \
        size_t size : 54, on_heap : 1, capacity : 6, flag1 : 1, flag2 : 1, \
            flag3 : 1;                                                     \
        type *ptr;                                                         \
    }

#define NEXT_POWER_OF_2(s) \
    VV1                    \
        ? s                \
        : (size_t) 1 << (64 - __builtin_clzl(s)) /* next power of 2 */

#define v(t, s, name, ...)                                              \
    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])

#define vec_size(v) v.size
#define vec_capacity(v) \
    (v.on_heap ? (size_t) 1 << v.capacity : sizeof(v.buf) / sizeof(v.buf[0]))

#define vec_data(v) (v.on_heap ? v.ptr : v.buf) /* always contiguous buffer */

#define vec_elemsize(v) sizeof(v.buf[0])
#define vec_pos(v, n) vec_data(v)[n] /* lvalue */

#define vec_reserve(v, n) __vec_reserve(&v, n, vec_elemsize(v), vec_capacity(v))
#define vec_push_back(v, e)                                            \
    __vec_push_back(&v, &(__typeof__(v.buf[0])[]){e}, vec_elemsize(v), \
                    vec_capacity(v))

#define vec_pop_back(v) (void) (VV2)

/* This function attribute specifies function parameters that are not supposed
 * to be null pointers. This enables the compiler to generate a warning on
 * encountering such a parameter.
 */
#define NON_NULL __attribute__((nonnull))

static NON_NULL void vec_free(void *p)
{
    STRUCT_BODY(void) *s = p;
    if (s->on_heap)
        free(s->ptr);
}

static inline int ilog2(size_t n)
{
    return 64 - __builtin_clzl(n) - ((n & (n - 1)) == 0);
}

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

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

請補完程式碼。
> 參閱 [你所不知道的C語言：技巧篇](https://hackmd.io/@sysprog/c-trick) 以得知 GCC extension: attribute cleanup 使用技巧。

==作答區==

VV1 =
* `(a)` s
* `(b)` s - 1
* `(c)` s & (s - 1)
* `(d)` (s & (s - 1)) == 0

VV2 =
* `(a)` `v.size -= 1`
* `(b)` `v.capacity--`

:::success
延伸問題:
1. 解釋上述程式運作的原理，比照 [quiz2](https://hackmd.io/@sysprog/BJXNYx5NL) 進行效率分析;
2. 指出上述實作的限制並提出改進方案;
3. 參照 [folly::fbvector](https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md) 文件和對應原始程式碼，以上述程式為基礎，實作 vector 經典操作
:::