# 2020q3 Homework6 (quiz6)
contributed by < [stonelin](https://github.com/StoneLin0708) >
###### tags: `sysprog2020`
# test 2
```c
#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.
```cpp
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;
}
};
```
```graphviz
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
```graphviz
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
```graphviz
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
```graphviz
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
```graphviz
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
```c
#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.
```c
#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
```c
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}}}$