# Jserv 問答集 - Linked List

## malloc 用法 - 是否需要 type - cast ?
* in CSAPP p.590. Dynamic memory Allocation.
* is type cast ```(int *)``` needed?

int p = (int *)malloc(n * sizeof(int));

Example, in OscarShiang's [lab0-c](https://github.com/OscarShiang/lab0-c/blob/master/queue.c)

queue_t *q = malloc(sizeof(queue_t));

### Stack Overflow 問答:
[ashiquzzaman33 and klutt](https://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc)

From the Wikipedia:

> # Advantages to casting
> Including the cast may allow a C program or function to compile as C++.
>
> The cast allows for pre-1989 versions of malloc that originally returned a char *.
> Casting can help the developer identify inconsistencies in type sizing should the destination pointer type change, particularly if the pointer is declared far from the malloc() call (although modern compilers and static analyzers can warn on such behaviour without requiring the cast).
>
> # Disadvantages to casting
> Under the ANSI C standard, the cast is redundant.
>
> Adding the cast may mask failure to include the header stdlib.h, in which the prototype for malloc is found. In the absence of a prototype for malloc, the standard requires that the C compiler assume malloc returns an int. If there is no cast, a warning is issued when this integer is assigned to the pointer; however, with the cast, this warning is not produced, hiding a bug. On certain architectures and data models (such as LP64 on 64-bit systems, where long and pointers are 64-bit and int is 32-bit), this error can actually result in undefined behaviour, as the implicitly declared malloc returns a 32-bit value whereas the actually defined function returns a 64-bit value. Depending on calling conventions and memory layout, this may result in stack smashing. This issue is less likely to go unnoticed in modern compilers, as they uniformly produce warnings that an undeclared function has been used, so a warning will still appear. For example, GCC's default behaviour is to show a warning that reads "incompatible implicit declaration of built-in function" regardless of whether the cast is present or not.
>
> If the type of the pointer is changed at its declaration, one may also, need to change all lines where malloc is called and cast.

---

考慮以下程式碼:

int *p = NULL;
void *q = (void *) p; // can be casted, can't dereference
uintptr_t s = (uintptr_t) q;

C99, 6.3.2.3:
> A pointer to void may be converted to or from a pointer to any incomplete or object type. A pointer to any incomplete or object type may be converted to a pointer to void and back again; the result shall compare equal to the original pointer.

C99, 7.20.1.4:
> The following type designates an unsigned integer type with the property that any valid pointer to void can be converted to this type, then converted back to pointer to void, and the result will compare equal to the original pointer: `uintptr_t`

---

## CMU linked list tutuorial 中 Dummy node 的作用

queue* queue_new()
//@ensures is_queue(\result) // 這兩行 \result 是啥東東
//@ensures queue_empty(\result)
{
    queue *Q = alloc(queue);
    list *dummy = alloc(list);
    Q->front = dummy;
    Q->back = dummy;
    return Q;
}

@ \:
給 工具使用

:::warning
這與 [Doxygen](http://www.doxygen.nl/) 有關
:notes: jserv
:::

Doxygen 自動解析程式碼
參考 oracle java
[javadoc](https://docs.oracle.com/javase/8/docs/technotes/tools/windows/javadoc.html)
### 我的理解
* 避免在結尾使用 Null pointer
* 可以避免 head 不見造成 memory leak?
* 但是在 lab0-c 好像大家都用 NULL-pointer ?

## Cycle Detection Proof wiki ?

:::warning
正規數學證明就要去翻閱教科書，不要太依賴線上教材
:notes: jserv
:::

* 好像沒看到數學式證明？
* 我的搜尋
* 把演算法換成數學式子的方法
* 在離散數學符號轉換有看到
## indent: tab v.s spaces
* editor 中設定 tab = 4 spaces 後，是否可以直接用 tab 了？
> in lab0-c 老師介紹過 每個編輯器 tab 設定不同，還是統一使用 4 space 比較好。

## 總結

* malloc 用法 - 是否需要 type - cast ?
* 使用 type - cast 好處
* C89 以前沒有 void 這個概念，使用 type - cast 確保相容性
* CMU linked list tutuorial 中 Dummy node 的作用
* 做實驗確認
* indent: tab v.s spaces
* editor 中設定 tab = 4 spaces 後，是否可以直接用 tab 了？
> in lab0-c 老師介紹過 每個編輯器 tab 設定不同，還是統一使用 4 space 比較好。