# 2020q3 Homework6 (quiz6)
contributed by < [stonelin](https://github.com/StoneLin0708) >

###### tags: `sysprog2020`

# test 2

#define RINGBUF_DECL(T, NAME) \
    typedef struct {          \
        int size;             \
        int start, end;       \
        T *elements;          \
    } NAME

#define RINGBUF_INIT(BUF, S, T)             \
    {                                       \
        static T static_ringbuf_mem[S + 1]; \
        BUF.elements = static_ringbuf_mem;  \
    }                                       \
    BUF.size = S;                           \
    BUF.start = 0;                          \
    BUF.end = 0;

#define NEXT_START_INDEX(BUF) \
    (((BUF)->start != (BUF)->size) ? ((BUF)->start + RB1) : 0)
#define NEXT_END_INDEX(BUF) (((BUF)->end != (BUF)->size) ? ((BUF)->end + RB2) : 0)

#define is_ringbuf_empty(BUF) ((BUF)->end == (BUF)->start)
#define is_ringbuf_full(BUF) (NEXT_END_INDEX(BUF) == (BUF)->start)

#define ringbuf_write_peek(BUF) (BUF)->elements[(BUF)->end]
#define ringbuf_write_skip(BUF)                   \
    do {                                          \
        (BUF)->end = NEXT_END_INDEX(BUF);         \
        if (is_ringbuf_empty(BUF))                \
            (BUF)->start = NEXT_START_INDEX(BUF); \
    } while (0)

#define ringbuf_read_peek(BUF) (BUF)->elements[(BUF)->start]
#define ringbuf_read_skip(BUF) (BUF)->start = NEXT_START_INDEX(BUF);

#define ringbuf_write(BUF, ELEMENT)        \
    do {                                   \
        ringbuf_write_peek(BUF) = ELEMENT; \
        ringbuf_write_skip(BUF);           \
    } while (0)

#define ringbuf_read(BUF, ELEMENT)        \
    do {                                  \
        ELEMENT = ringbuf_read_peek(BUF); \
        ringbuf_read_skip(BUF);           \
    } while (0)

The **start** is an index to next read, and the **end** is an index to next write.
Therefore after each read and writes the index should increment by one and circle back to 0 if needed.

Syntax highlight hates macro, and c doesn't work well with type polymorphism.

template <typename T, int Size>
struct buf {
  int size = Size;
  int start = 0, end = 0;
  std::array<T, Size + 1> elements;

  int next_start_idx() { return start != size ? (start + 1) : 0; }
  int next_end_idx() { return end != size ? (end + 1) : 0; }
  bool is_empty() { return end == start; }
  bool is_full() { return next_end_idx() == start; }

  T& write_peek() { return elements[end]; }
  void write_skip() {
    end = next_end_idx();
    if (is_empty()) start = next_start_idx();
  }

  T& read_peek() { return elements[start]; }
  void read_skip() { start = next_start_idx(); }

  void write(T element) {
    write_peek() = element;
    write_skip();
  }
  T read() {
    T e = read_peek();
    read_skip();
    return e;
  }
};

digraph{
    node[shape=box]
    n0->n1->n2
    n2->n0[style=dashed]
    {rank=same n0 n1 n2}
    start[shape=invtriangle,label="start=0",fontsize=9]
    start->n0
    end[shape=invtriangle,label="end=0",fontsize=9]
    end->n0
}

write A

digraph{
    node[shape=box]
    n0[label=A]
    n0->n1->n2
    n2->n0[style=dashed]
    {rank=same n0 n1 n2}
    start[shape=invtriangle,label="start=0",fontsize=9]
    start->n0
    end[shape=invtriangle,label="end=1",fontsize=9]
    end->n1
}

write B

digraph{
    node[shape=box]
    n0[label=A]
    n1[label=B]
    n0->n1->n2
    n2->n0[style=dashed]
    {rank=same n0 n1 n2}
    start[shape=invtriangle,label="start=0",fontsize=9]
    start->n0
    end[shape=invtriangle,label="end=2",fontsize=9]
    end->n2
}

read

digraph{
    node[shape=box]
    ele[shape=circle,label=A]
    n0->ele[label=pop]
    n1[label=B]
    n0->n1->n2
    n2->n0[style=dashed]
    {rank=same n0 n1 n2}
    start[shape=invtriangle,label="start=1",fontsize=9]
    start->n1
    end[shape=invtriangle,label="end=2",fontsize=9]
    end->n2
}

write C

digraph{
    node[shape=box]
    n0
    n1[label=B]
    n2[label=C]
    n0->n1->n2
    n2->n0[style=dashed]
    {rank=same n0 n1 n2}
    start[shape=invtriangle,label="start=1",fontsize=9]
    start->n1
    end[shape=invtriangle,label="end=0",fontsize=9]
    end->n0
}

# test 3

#include <stdio.h>

/* clang-format off */
#define cons(x, y) (struct llist[]){{y, x}}
/* clang-format on */

struct llist {
    int val;
    struct llist *next;
};

void sorted_insert(struct llist **head, struct llist *node)
{
    if (!*head || (*head)->val >= node->val) {
        node->next = *head;
        *head = node;
        return;
    }
    struct llist *current = *head;
    while (current->next && current->next->val < node->val)
        current = current->next;
    node->next = current->next;
    current->next = node;
}

void sort(struct llist **head)
{
    struct llist *sorted = NULL;
    for (struct llist *current = *head; current;) {
        struct llist *next = current->next;
        sorted_insert(&sorted, current);
        current = next;
    }
    *head = sorted;
}

int main()
{
    struct llist *list = cons(cons(cons(cons(NULL, 7), 4), 5), 9);
    struct llist *p;
    for (p = list; p; p = p->next)
        printf("%d", p->val);
    printf("\n");

    sort(&list);
    for (p = list; p; p = p->next)
        printf("%d", p->val);
    printf("\n");
    return 0;
}

The cons macro for list initialization.

#define cons(x, y) (struct llist[]){{y, x}}
struct llist *list = cons(cons(cons(cons(NULL, A), B), C), D);

After macro expansion, the order is reversed.

{D,{C,{B,{A, NULL}}}};

I don't understand is there any reason to statically initialize a linked list. :-/

# test 4

int findDuplicate(int *nums, int numsSize)
{
    int res = 0;
    const size_t log_2 = 8 * sizeof(int) - __builtin_clz(numsSize);
    for (size_t i = 0; i < log_2; i++) {
        int bit = 1 << i;
        int c1 = 0, c2 = 0;
        for (size_t k = 0; k < numsSize; k++) {
            if (k & bit)
                ++c1;
            if (nums[k] & bit)
                ++c2;
        }
        if (c1<c2)
            res += bit;
    }
    return res;
}

By counting bit in each position, if there is a difference between counting result of $1-N$ and $nums_{1-N}$

$nums=1\ ...\ N$ with some number replaced by $D\in[1...N]$
$nums=N_1,N_2,...,N_{N-k},D_0,...,D_k|k>1\ and\ N_i!=N_j\ \forall{i!=j}\ and \ D_o=D_p\forall{o,p}$
$Ni=b_{Ni0},b_{Ni1},...,b_{Ni8*sizeof(int)}$
$D=b_{d0},b_{d1},...,b_{d8*sizeof(int)}\\
b_{dk}=1|\forall{\Sigma_{i=1}^N{b_{Nik}}!=\Sigma_{i=0}^{N}{b_{ik}}}$