Comparison of list implementation

Linux kernel list.h

• list.h source
• 《Linux Device Drivers 3/e》, ch11.5

特點

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

glib GList

• Doubly-Linked Lists, glib docs
• glist source

特點

• 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
  • 似乎還是用malloc配置節點記憶體
• 延伸資料結構: GQueue, GAsyncQueue, …

glib GQueue

GQueue source

glib GAsyncQueue

GAsyncQueue source

特點

• 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