[数据结构与算法]【demo】基于链表的通用queue

ulist.h

#ifndef _U_LIST_H_
#define _U_LIST_H_

#undef offsetof
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

#define container_of(ptr, type, member) ({                      \
        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
        (type *)( (char *)__mptr - offsetof(type,member) );})

struct ulist_head {
	struct ulist_head *next, *prev;
	int id;
};

static inline void list_init(struct ulist_head *head)
{
	head->next = head;
	head->prev = head;
	head->id = -1;
}

static inline void __list_add(struct ulist_head *entry, struct ulist_head *prev, struct ulist_head *next)
{
	prev->next = entry;
	entry->prev = prev;
	entry->next = next;
	next->prev = entry;
}

static inline void list_add(struct ulist_head *entry, struct ulist_head *head)
{
	__list_add(entry, head, head->next);
}

static inline void list_add_tail(struct ulist_head *entry, struct ulist_head *head)
{
	__list_add(entry, head->prev, head);
}

static inline void __list_del(struct ulist_head *prev, struct ulist_head *next)
{
	next->prev = prev;
	prev->next = next;
}

static inline void list_del(struct ulist_head *entry)
{
	__list_del(entry->prev, entry->next);
	entry->prev = entry;
	entry->next = entry;
}

static inline int list_empty(struct ulist_head *head)
{
	return head->prev == head;
}

#endif

uqueue.h

#ifndef _U_QUEUE_H_
#define _U_QUEUE_H_
#include "ulist.h"

struct queuelist {
	struct ulist_head head;
	int max;
	int cur;
};

struct sendmsg {
	struct ulist_head node;
	int id;
	int size;
	void *vaddr;
};

#define queue_init(q, m) \
	do {\
		list_init(&(q)->head);  \
		(q)->max = (m); \
		(q)->cur = 0;   \
	} while(0)

#define enqueue(q, n) \
	({\
		int ret = 0; \
		if ((q)->max <= (q)->cur) { \
			printf("%s %d, queue full\n", __func__, __LINE__); \
			ret = -1; \
		} else { \
			list_add(&(n)->node, &(q)->head); \
			(q)->cur++; \
			printf("%s %d, nd %p %d, p.c.n %p %p %p\n", __func__, __LINE__, &(n)->node, (n)->id, (q)->head.prev, &(q)->head, (q)->head.next); \
		}\
		ret; \
	 })

#define enqueue_tail(q, n) \
	({\
		int ret = 0; \
		if ((q)->max <= (q)->cur) { \
			printf("%s %d, queue full\n", __func__, __LINE__); \
			ret = -1; \
		} else {\
			list_add_tail(&(n)->node, &(q)->head); \
			(q)->cur++; \
			printf("%s %d, nd %p %d, p.c.n %p %p %p\n", __func__, __LINE__, &(n)->node, (n)->id, (q)->head.prev, &(q)->head, (q)->head.next); \
		}\
		ret; \
	 })

#define dequeue(q, n) \
	({\
		int ret = 0; \
		typeof((q)->head) *__qh_tmp = (q)->head.next;\
		if ((q)->cur == 0) {\
			printf("%s %d, queue empty\n", __func__, __LINE__);\
			ret = -1;\
		}\
		(q)->cur--;\
		n = (typeof(n))(__qh_tmp - (size_t)&(((typeof(n))0)->node)); \
		printf("%s %d, nd %p %d, p.c.n %p %p %p\n", __func__, __LINE__, &n->node, n->id, qh->head.prev, &qh->head, qh->head.next); \
		list_del(__qh_tmp); \
		ret;\
	})

#define dequeue_tail(q, n) \
	({\
		int ret = 0; \
		typeof((q)->head) *__qh_tmp = (q)->head.prev;\
		if ((q)->cur == 0) {\
			printf("%s %d, queue empty\n", __func__, __LINE__);\
			ret = -1;\
		}\
		(q)->cur--;\
		n = (typeof(n))(__qh_tmp - (size_t)&(((typeof(n))0)->node)); \
		printf("%s %d, nd %p %d, p.c.n %p %p %p\n", __func__, __LINE__, &n->node, n->id, qh->head.prev, &qh->head, qh->head.next); \
		list_del(__qh_tmp); \
		ret;\
	})

#endif

test.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h> 

#include "ulist.h"
#include "uqueue.h"

void pr_list(struct ulist_head *hd)
{
	struct ulist_head *tmp = hd;

	if (list_empty(hd))
		return;

	do {
		tmp = tmp->next;
		if(tmp == hd)
			break;
		printf("%d, ", tmp->id);
	} while(1);

	printf("\n");
}

void destroy_list(struct ulist_head *hd)
{
	struct ulist_head *tmp = hd->next;

	while (!list_empty(hd)) {
		list_del(tmp);
		printf("%d, ", tmp->id);
		free(tmp);
		tmp = hd->next;
	}
	printf("\n\n");
}

void test_list(struct ulist_head *hd)
{
	int i = 0;
	struct ulist_head *tmp = NULL;
	//
	list_init(hd);
	//
	for (i = 0; i < 5; i++) {
		tmp = (struct ulist_head *)malloc(sizeof(struct ulist_head));
		bzero(tmp, sizeof(struct ulist_head));
		tmp->id = i;
		list_add(tmp, hd);
		pr_list(hd);
	}
	printf("----------\n");
	destroy_list(hd);
	//
	for (i = 0; i < 5; i++) {
		tmp = (struct ulist_head *)malloc(sizeof(struct ulist_head));
		bzero(tmp, sizeof(struct ulist_head));
		tmp->id = i;
		list_add_tail(tmp, hd);
		pr_list(hd);
	}
	printf("----------\n");
	destroy_list(hd);
}

void test_queue(struct queuelist *qh)
{
	int i = 0;
	struct sendmsg *tmp = NULL;

	queue_init(qh, 5);
	//
	for (i = 0; i <= 5; i++) {
		tmp = (struct sendmsg *)malloc(sizeof(struct sendmsg));
		bzero(tmp, sizeof(struct sendmsg));
		tmp->id = i;
		enqueue(qh, tmp);
		/** enqueue_tail(qh, tmp); */
	}
	tmp = NULL;
	do {
		if (qh->cur == 0) {
			printf("%s %d, queue empty\n", __func__, __LINE__);
			break;
		}
		dequeue(qh, tmp);
		//dequeue_tail(qh, tmp);
		free(tmp);
		tmp = NULL;
	} while(1);
}


int main(int argc, char const *argv[])
{
	/** struct ulist_head hd; */
	/** test_list(&hd); */

	struct queuelist qh;
	test_queue(&qh);

	return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖