# Comparison of list implementation

## Linux kernel list.h
* [list.h source]( https://github.com/torvalds/linux/blob/master/include/linux/list.h)
* 《Linux Device Drivers 3/e》, ch11.5

特點

* doubly linked list, circular
* API操作對象為struct list_head, 使用者需自行管理記憶體
* non thread-safe

## glib GList
* [Doubly-Linked Lists](https://developer.gnome.org/glib/stable/glib-Doubly-Linked-Lists.html), glib docs
* [glist source](https://git.gnome.org/browse/glib/tree/glib/glist.c)

特點

* doubly linked list
* API操作對象為pointer to entry data (as void*), glib內部以`struct Glist`表示節點, 用法較接近C++ std::list

struct _GList
{
  gpointer data;
  GList *next;
  GList *prev;
};

* 記憶體管理: [GNOME memory slice](https://developer.gnome.org/glib/stable/glib-Memory-Slices.html)
* 似乎還是用malloc配置節點記憶體
* 延伸資料結構: GQueue, GAsyncQueue, ...

## glib GQueue

[GQueue source](https://git.gnome.org/browse/glib/tree/glib/gqueue.c)

## glib GAsyncQueue
[GAsyncQueue source]( https://git.gnome.org/browse/glib/tree/glib/gasyncqueue.c)

特點

* reference counting (g_async_queue_ref() and g_async_queue_unref())
* thread-safe: 以GAsyncQueue::mutex保護, 同一時間只有一個thread可變更queue
* 可自行管理lock (g_async_queue_lock() and g_async_queue_xxx_unlock())

API

// create
GAsyncQueue *	g_async_queue_new ()
GAsyncQueue *	g_async_queue_new_full ()

// operations
void	g_async_queue_push ()
void	g_async_queue_push_front ()
void	g_async_queue_push_sorted () // the queue should be sorted
gpointer	g_async_queue_pop () // blocking
gpointer	g_async_queue_try_pop () // non-blocking
gpointer	g_async_queue_timed_pop ()
gpointer	g_async_queue_timeout_pop () // non-blocking
gboolean	g_async_queue_remove ()
void	g_async_queue_sort ()
gint	g_async_queue_length ()

// reference counting
GAsyncQueue *	g_async_queue_ref ()
void	g_async_queue_unref ()
void	g_async_queue_ref_unlocked ()
void	g_async_queue_unref_and_unlock ()

// operations for manual lock/unlock
void	g_async_queue_lock ()
void	g_async_queue_unlock ()
void	g_async_queue_push_unlocked ()
void	g_async_queue_push_front_unlocked ()
void	g_async_queue_push_sorted_unlocked ()
gpointer	g_async_queue_pop_unlocked ()
gpointer	g_async_queue_try_pop_unlocked ()
gpointer	g_async_queue_timed_pop_unlocked ()
gpointer	g_async_queue_timeout_pop_unlocked ()
gboolean	g_async_queue_remove_unlocked ()
void	g_async_queue_sort_unlocked ()
gint	g_async_queue_length_unlocked ()

## C++ std::queue

* vector<int>不保證是thread safe
* 《Standard for Programming Language C++》2014-11 working draft, ch23.2.2
* 其他container是否為thread safe?

## 其他

* 吳彥寬同學的做法: 以C11 _Generic處理
https://hackmd.io/s/BykQDVTp
https://hackmd.io/s/S1ezGhIA