zlist 链表分析

	typedef int (zlist_compare_fn) (
	void item1, void item2);

	typedef void (zlist_free_fn) (
	void *data);

	typedef struct _node_t {
	struct _node_t *next; // 指向下一个节点
	void *item; // 节点当中的元素
	zlist_free_fn *free_fn; // 元素对应的析构函数
	} node_t;

	struct _zlist_t {
	node_t *head; // 头节点
	node_t *tail; // 尾节点
	node_t *cursor; // 当前访问节点
	size_t size; // 元素数量
	bool autofree; // 如果为真，使用默认析构元素，否则使用节点自带的析构
	zlist_compare_fn *compare_fn; // 自定义的比较函数回调，用来比较两个元素
	};

	/* List constructor. */
	zlist_t *
	zlist_new (void)
	{
	zlist_t self = (zlist_t ) zmalloc (sizeof (zlist_t));
	assert (self);
	return self;
	}

	/* List destructor. */
	void
	zlist_destroy (zlist_t **self_p)
	{
	assert (self_p);
	if (*self_p) {
	zlist_t self = self_p;
	zlist_purge (self);
	freen (self);
	*self_p = NULL;
	}
	}

	/* Return the item at the head of list. If the list is empty, returns NULL.
	Leaves cursor pointing at the head item, or NULL if the list is empty. */
	void *
	zlist_first (zlist_t *self)
	{
	assert (self);
	// 将游标移动到链首位置
	self->cursor = self->head;
	// 返回链首元素
	if (self->cursor)
	return self->cursor->item;
	else
	return NULL;
	}

	/* Return the next item. If the list is empty, returns NULL. To move to
	the start of the list call zlist_first (). Advances the cursor. */
	void *
	zlist_next (zlist_t *self)
	{
	assert (self);
	// 将游标移动到下一个，如果是首次访问，那么设置为首节点
	if (self->cursor)
	self->cursor = self->cursor->next;
	else
	self->cursor = self->head;
	// 如果当前游标非空，那么返回里面的元素
	if (self->cursor)
	return self->cursor->item;
	else
	return NULL;
	}

	/* Return the item at the tail of list. If the list is empty, returns NULL.
	Leaves cursor pointing at the tail item, or NULL if the list is empty. */
	void *
	zlist_last (zlist_t *self)
	{
	assert (self);
	// 将游标移动到链尾位置
	self->cursor = self->tail;
	// 返回链尾元素
	if (self->cursor)
	return self->cursor->item;
	else
	return NULL;
	}

	/* Return current item in the list. If the list is empty, or the cursor
	passed the end of the list, returns NULL. Does not change the cursor. */
	void *
	zlist_item (zlist_t *self)
	{
	assert (self);
	// 访问当前游标的元素
	if (self->cursor)
	return self->cursor->item;
	else
	return NULL;
	}

	/* Append an item to the end of the list, return 0 if OK or -1 if this
	failed for some reason. */
	int
	zlist_append (zlist_t self, void item)
	{
	if (!item)
	return -1;

	// 构造节点
	node_t node = (node_t ) zmalloc (sizeof (node_t));
	assert (node);

	// 如果支持自动回收，那么按字符串的形式申请内存并拷贝一份
	if (self->autofree) {
	item = strdup ((char *) item);
	assert (item);
	}
	// 新节点中保存元素
	node->item = item;
	// 当前链尾与新节点进行链接
	if (self->tail)
	self->tail->next = node;
	// 链尾是空说明是首次操作，链头指向节点
	else
	self->head = node;

	// 新节点设为链尾
	self->tail = node;
	node->next = NULL;

	// 链尾大小 + 1
	self->size++;
	// 游标重置为空
	self->cursor = NULL;
	return 0;
	}

	/* Push an item to the start of the list, return 0 if OK or -1 if this
	failed for some reason. */
	int
	zlist_push (zlist_t self, void item)
	{
	if (!item)
	return -1;

	node_t node = (node_t ) zmalloc (sizeof (node_t));
	assert (node);

	// 如果支持自动回收，那么按字符串的形式申请内存并拷贝一份
	if (self->autofree) {
	item = strdup ((char *) item);
	assert (item);
	}
	node->item = item;
	// 设置新节点的下 1 个节点是链首节点
	node->next = self->head;
	// 链首属性设置为新节点
	self->head = node;
	// 如果链尾属性是空，说明是首次操作，设置为新节点
	if (self->tail == NULL)
	self->tail = node;

	self->size++;
	self->cursor = NULL;
	return 0;
	}

	/* Remove item from the beginning of the list, returns NULL if none. */
	void *
	zlist_pop (zlist_t *self)
	{
	node_t *node = self->head;
	void *item = NULL;
	if (node) {
	// 获得链首元素引用
	item = node->item;
	// 链首指向下 1 个节点（这时节点已从链表中删除）
	self->head = node->next;
	// 若链表里只有 1 个节点，那么链尾也置空
	if (self->tail == node)
	self->tail = NULL;
	// 释放已删除的节点
	freen (node);
	// 链表大小 - 1
	self->size--;
	}
	// 当前游标置空
	self->cursor = NULL;
	// 返回元素
	return item;
	}

	/* Checks if an item already is present. Uses compare method to determine if
	items are equal. If the compare method is NULL the check will only compare
	pointers. Returns true if item is present else false. */
	bool
	zlist_exists (zlist_t self, void item)
	{
	assert (self);
	assert (item);
	node_t *node = self->head;

	while (node) {
	// 链表有自定义比较函数，那就用它来比较
	if (self->compare_fn) {
	if ((*self->compare_fn)(node->item, item) == 0)
	return true;
	}
	// 否则直接用双等号比较
	else
	if (node->item == item)
	return true;
	// 取下 1 个节点比较
	node = node->next;
	}
	return false;
	}

	/* Remove the item from the list, if present. Safe to call on items that
	are not in the list. */
	void
	zlist_remove (zlist_t self, void item)
	{
	node_t node, prev = NULL;

	// 首先，我们通过遍历把这个节点找到
	for (node = self->head; node != NULL; node = node->next) {
	if (self->compare_fn) {
	if ((*self->compare_fn)(node->item, item) == 0)
	break;
	}
	// 找到了就跳出替换
	else
	if (node->item == item)
	break;

	// 每次保存遍历的节点，当下次找到，这个节点就是前节点
	prev = node;
	}

	// 将删的节点已找到
	if (node) {
	// 前节点指向节点的下 1 个节点
	if (prev)
	prev->next = node->next;
	// 这里说明链表只有 1 个节点，链头设置为空
	else
	self->head = node->next;

	// 这里说明节点在链尾
	if (node->next == NULL)
	// 前节点设置成链尾
	self->tail = prev;
	// 游标刚好指向节点
	if (self->cursor == node)
	// 游标设置成前节点
	self->cursor = prev;

	// 自动删除标志为真
	if (self->autofree)
	// 释放当前节点的元素的内存空间
	freen (node->item);
	// 不为真就用节点析构函数（如果有）
	else
	if (node->free_fn)
	(node->free_fn)(node->item);

	// 释放节点本身的内存空间
	freen (node);
	// 元素总数减 1
	self->size--;
	}
	}

	/* Make a copy of list. If the list has autofree set, the copied list will
	duplicate all items, which must be strings. Otherwise, the list will hold
	pointers back to the items in the original list. If list is null, returns
	NULL. */
	zlist_t *
	zlist_dup (zlist_t *self)
	{
	if (!self)
	return NULL;

	zlist_t *copy = zlist_new ();
	assert (copy);

	if (self->autofree)
	zlist_autofree(copy);

	copy->compare_fn = self->compare_fn;

	node_t *node;
	for (node = self->head; node; node = node->next) {
	if (zlist_append (copy, node->item) == -1) {
	zlist_destroy (&copy);
	break;
	}
	}
	return copy;
	}

	/* Purge all items from list. */
	void
	zlist_purge (zlist_t *self)
	{
	assert (self);
	node_t *node = self->head;
	while (node) {
	node_t *next = node->next;
	if (self->autofree)
	freen (node->item);
	else
	if (node->free_fn)
	(node->free_fn)(node->item);

	freen (node);
	node = next;
	}
	self->head = NULL;
	self->tail = NULL;
	self->cursor = NULL;
	self->size = 0;
	}

	/* Return the number of items in the list. */
	size_t
	zlist_size (zlist_t *self)
	{
	return self->size;
	}

	/* Sort the list. If the compare function is null, sorts the list by
	ascending key value using a straight ASCII comparison. If you specify
	a compare function, this decides how items are sorted. The sort is not
	stable, so may reorder items with the same keys. The algorithm used is
	combsort, a compromise between performance and simplicity. */
	void
	zlist_sort (zlist_t *self, zlist_compare_fn compare_fn)
	{
	zlist_compare_fn *compare = compare_fn;
	if (!compare) {
	compare = self->compare_fn;
	if (!compare)
	compare = (zlist_compare_fn *) strcmp;
	}
	// 梳排序算法:
	// 1. 算法从两个游标同时开始遍历
	// 2. 两个游标之间存在间隔 (gap)
	// 3. 第 1 个游标是链头，第 2 个游标按间隔计算
	// 4. 两个游标遍历的同时会交换元素
	// 5. 每一轮至少需要交换 1 次
	// 6. 间隔每 1 轮按递减率 1.3 进行缩短
	// 7. 当间隔小于等于 1 或者交换 0 次时算法终止
	size_t gap = self->size;
	bool swapped = false;
	while (gap > 1 \|\| swapped) {
	if (gap > 1)
	gap = (size_t) ((double) gap / 1.3);
	node_t *base = self->head;
	node_t *test = self->head;
	size_t jump = gap;
	while (jump--)
	test = test->next;

	swapped = false;
	while (base && test) {
	if ((*compare) (base->item, test->item) > 0) {
	// 依据比较函数进行元素交换
	void *item = base->item;
	base->item = test->item;
	test->item = item;
	swapped = true;
	}
	base = base->next;
	test = test->next;
	}
	}
	}

	/* Sets a compare function for this list. The function compares two items.
	It returns an integer less than, equal to, or greater than zero if the
	first item is found, respectively, to be less than, to match, or be
	greater than the second item.
	This function is used for sorting, removal and exists checking. */
	void
	zlist_comparefn (zlist_t *self, zlist_compare_fn fn)
	{
	assert (self);
	self->compare_fn = fn;
	}

	/* Set a free function for the specified list item. When the item is
	destroyed, the free function, if any, is called on that item.
	Use this when list items are dynamically allocated, to ensure that
	you don't have memory leaks. You can pass 'free' or NULL as a free_fn.
	Returns the item, or NULL if there is no such item. */
	void *
	zlist_freefn (zlist_t self, void item, zlist_free_fn fn, bool at_tail)
	{
	node_t *node = self->head;
	// 给链尾设置析构函数，这个标志是为了提高算法效率
	if (at_tail)
	node = self->tail;

	// 根据元素值遍历找节点并设置析构函数
	while (node) {
	if (node->item == item) {
	node->free_fn = fn;
	return item;
	}
	node = node->next;
	}
	return NULL;
	}

	/* Set list for automatic item destruction; item values MUST be strings.
	By default a list item refers to a value held elsewhere. When you set
	this, each time you append or push a list item, zlist will take a copy
	of the string value. Then, when you destroy the list, it will free all
	item values automatically. If you use any other technique to allocate
	list values, you must free them explicitly before destroying the list.
	The usual technique is to pop list items and destroy them, until the
	list is empty. */
	void
	zlist_autofree (zlist_t *self)
	{
	assert (self);
	self->autofree = true;
	}

# 数据结构定义

# 比较函数指针

# 析构函数指针

# 节点

# 链表

# 函数定义

# 创建链表对象

# 销毁链表对象

# 访问链表第一个元素

# 访问链表下一个元素

# 访问链表最后一个元素

# 访问链表当前元素

# 添加链尾元素

# 添加链首元素

# 删除链首元素

# 判断元素是否存在

# 查找并删除元素

# 复制链表对象

# 清理链表所有元素

# 获得链表大小

# 链表排序

# 设置比较函数

# 设置元素销毁函数

# 设置自动销毁状态

# 数据结构定义

# 比较函数指针

# 析构函数指针

# 节点

# 链表

# 函数定义

# 创建链表对象

# 销毁链表对象

# 访问链表第一个元素

# 访问链表下一个元素

# 访问链表最后一个元素

# 访问链表当前元素

# 添加链尾元素

# 添加链首元素

# 删除链首元素

# 判断元素是否存在

# 查找并删除元素

# 复制链表对象

# 清理链表所有元素

# 获得链表大小

# 链表排序

# 设置比较函数

# 设置元素销毁函数

# 设置自动销毁状态

Linux 网络管理套件

VMware 下 ubuntu 空间回收