Односвязные списки

Односвязный список начинается со структуры, определённой макросом SLIST_HEAD. В этой структуре содержится одиночный указатель на первый элемент списка. Элементы имеют по одной связи для минимизации занимаемого пространства, а дополнительный расход на операции с указателями равен O(n) при удалении произвольного элемента. Новые элементы можно добавлять в список после существующего элемента или в начало списка. Структура SLIST_HEAD объявляется следующим образом:

SLIST_HEAD(HEADNAME, TYPE) head;

где HEADNAME — имя определяемой структуры, а TYPE — тип элементов, объединяемых в список. Указатель на начало списка может в дальнейшем объявляться так:

struct HEADNAME *headp;

(Имена head и headp могут выбираться пользователем.)

Макрос SLIST_HEAD_INITIALIZER запускает инициализатор для head списка.

Макрос SLIST_EMPTY возвращает true, если в списке нет элементов.

Макрос SLIST_ENTRY объявляет структуру, которая добавляет элементы в список.

Макрос SLIST_FIRST возвращает первый элемент списка или NULL, если список пуст.

Макрос SLIST_FOREACH обходит список, на который ссылается head, от начало в конец, назначая var каждый элемент.

Макрос SLIST_INIT инициализирует список, на который ссылается head.

Макрос SLIST_INSERT_HEAD вставляет новый элемент elm в начало списка.

Макрос SLIST_INSERT_AFTER вставляет новый элемент elm за элементом listelm.

Макрос SLIST_NEXT возвращает следующий элемент списка.

Макрос SLIST_REMOVE_HEAD удаляет элемент elm из начала списка. В целях эффективности удаления элемента из начала списка нужно использовать именно этот макрос вместо обычного SLIST_REMOVE.

Макрос SLIST_REMOVE удаляет элемент elm из списка.

Пример односвязного списка

SLIST_HEAD(slisthead, entry) head =
    SLIST_HEAD_INITIALIZER(head);
struct slisthead *headp;		/* начало односвязного
                                           списка */
struct entry {
	...
	SLIST_ENTRY(entry) entries;	/* односвязный список */
	...
} *n1, *n2, *n3, *np;

SLIST_INIT(&head);			/* инициализация списка */

n1 = malloc(sizeof(struct entry));	/* вставка начального элемента */
SLIST_INSERT_HEAD(&head, n1, entries);

n2 = malloc(sizeof(struct entry));	/* вставка последующих */
SLIST_INSERT_AFTER(n1, n2, entries);

SLIST_REMOVE(&head, n2, entry, entries);/* удаление */
free(n2);

n3 = SLIST_FIRST(&head);
SLIST_REMOVE_HEAD(&head, entries);	/* удаление начального элемента */
free(n3);
					/* обход из начала в конец */
SLIST_FOREACH(np, &head, entries)
	np-> ...

while (!SLIST_EMPTY(&head)) {		/* удаление списка */
	n1 = SLIST_FIRST(&head);
	SLIST_REMOVE_HEAD(&head, entries);
	free(n1);
}

Односвязные хвостовые очереди

Односвязная хвостовая очередь начинается со структуры, определяемой макросом STAILQ_HEAD. В этой структуре содержится пара указателей, один на первый элемент хвостовой очереди, а другой на последний элемент. Элементы имеют по одной связи для минимизации занимаемого пространства, а дополнительный расход на операции с указателями равен O(n) при удалении произвольного элемента. Новые элементы можно добавлять в хвостовую очередь после существующего элемента, в начало или конец хвостовой очереди, Структура STAILQ_HEAD объявляется следующим образом:

STAILQ_HEAD(HEADNAME, TYPE) head;

где HEADNAME — имя определяемой структуры, а TYPE — тип связанных элементов в хвостовой очереди. Указатель на начало хвостовой очереди может в дальнейшем объявляться так:

struct HEADNAME *headp;

(Имена head и headp могут выбираться пользователем.)

Макрос STAILQ_HEAD_INITIALIZER запускает инициализатор для head хвостовой очереди.

Макрос STAILQ_CONCAT добавляет хвостовую очередь с началом head2 в конец очереди с началом head1, удаляя все элементы из первой.

Макрос STAILQ_EMPTY возвращает true, если в хвостовой очереди нет элементов.

Макрос STAILQ_ENTRY объявляет структуру, которая подключает элементы в хвостовую очередь.

Макрос STAILQ_FIRST возвращает первый элемент из хвостовой очереди или NULL, если очередь пуста.

Макрос STAILQ_FOREACH обходит хвостовую очередь, на которую ссылается head, из начала в конец, назначая var каждый элемент.

Макрос STAILQ_INIT инициализирует хвостовую очередь, на которую ссылается head.

Макрос STAILQ_INSERT_HEAD вставляет новый элемент I elm в начало хвостовой очереди.

Макрос STAILQ_INSERT_TAIL вставляет новый элемент elm в конец хвостовой очереди.

Макрос STAILQ_INSERT_AFTER вставляет новый элемент elm за элементом listelm.

Макрос STAILQ_NEXT возвращает следующий элемент из хвостовой очереди или NULL, если элемент последний.

Макрос STAILQ_REMOVE_HEAD удаляет элемент из начала хвостовой очереди. В целях эффективности удаления элемента из начала хвостовой очереди нужно использовать именно этот макрос вместо обычного STAILQ_REMOVE.

Макрос STAILQ_REMOVE удаляет элемент elm из хвостовой очереди.

Пример односвязной хвостовой очереди

STAILQ_HEAD(stailhead, entry) head =
    STAILQ_HEAD_INITIALIZER(head);
struct stailhead *headp;		/* начало односвязной хвостовой
                               очереди */
struct entry {
	...
	STAILQ_ENTRY(entry) entries;	/* хвостовая очередь */
	...
} *n1, *n2, *n3, *np;

STAILQ_INIT(&head);			/* инициализация очереди */

n1 = malloc(sizeof(struct entry));	/* вставка начального элемента */
STAILQ_INSERT_HEAD(&head, n1, entries);

n1 = malloc(sizeof(struct entry));	/* вставка в очередь */
STAILQ_INSERT_TAIL(&head, n1, entries);

n2 = malloc(sizeof(struct entry));	/* вставка последующего */
STAILQ_INSERT_AFTER(&head, n1, n2, entries);
					/* удаление */
STAILQ_REMOVE(&head, n2, entry, entries);
free(n2);
					/* удаление из начала */
n3 = STAILQ_FIRST(&head);
STAILQ_REMOVE_HEAD(&head, entries);
free(n3);
					/* обход от начала в конец */
STAILQ_FOREACH(np, &head, entries)
	np-> ...
					/* удаление TailQ */
while (!STAILQ_EMPTY(&head)) {
	n1 = STAILQ_FIRST(&head);
	STAILQ_REMOVE_HEAD(&head, entries);
	free(n1);
}
					/* быстрое удаление TailQ */
n1 = STAILQ_FIRST(&head);
while (n1 != NULL) {
	n2 = STAILQ_NEXT(n1, entries);
	free(n1);
	n1 = n2;
}
STAILQ_INIT(&head);

Списки

Список начинается структурой, определённой макросом LIST_HEAD. Эта структура содержит единственный указатель на первый элемент списка. Элементы дважды связаны, поэтому произвольный элемент можно удалить без прохода по всему списку. Новые элементы могут быть добавлены в список перед или после существующего элемента, а также в начало списка. Структура LIST_HEAD объявляется следующим образом:

LIST_HEAD(HEADNAME, TYPE) head;

где HEADNAME — имя определяемой структуры, а TYPE — тип элементов, объединяемых в список. Указатель на начало списка может в дальнейшем объявляться так:

struct HEADNAME *headp;

(Имена head и headp могут выбираться пользователем.)

Макрос LIST_HEAD_INITIALIZER запускает инициализатор для head списка.

Макрос LIST_EMPTY возвращает true, если в списке нет элементов.

Макрос LIST_ENTRY объявляет структуру, которая добавляет элементы в список.

Макрос LIST_FIRST возвращает первый элемент списка или NULL, если список пуст.

Макрос LIST_FOREACH обходит список, на который ссылается head, от начало в конец, назначая var каждый элемент.

Макрос LIST_INIT инициализирует список, на который ссылается head.

Макрос LIST_INSERT_HEAD вставляет новый элемент elm в начало списка.

Макрос LIST_INSERT_AFTER вставляет новый элемент elm за элементом listelm.

Макрос LIST_INSERT_AFTER вставляет новый элемент elm перед элементом listelm.

Макрос LIST_NEXT возвращает следующий элемент списка или NULL, если элемент последний.

Макрос LIST_REMOVE удаляет элемент elm из списка.

Пример списка

LIST_HEAD(listhead, entry) head =
    LIST_HEAD_INITIALIZER(head);
struct listhead *headp;			/* начало списка */
struct entry {
	...
	LIST_ENTRY(entry) entries;	/* список */
	...
} *n1, *n2, *n3, *np, *np_temp;

LIST_INIT(&head);			/* инициализация списка */

n1 = malloc(sizeof(struct entry));	/* вставка в начало */
LIST_INSERT_HEAD(&head, n1, entries);

n2 = malloc(sizeof(struct entry));	/* вставка последующего */
LIST_INSERT_AFTER(n1, n2, entries);

n3 = malloc(sizeof(struct entry));	/* вставка перед */
LIST_INSERT_BEFORE(n2, n3, entries);

LIST_REMOVE(n2, entries);		/* удаление */
free(n2);
					/* обход из начала в конец */
LIST_FOREACH(np, &head, entries)
	np-> ...

while (!LIST_EMPTY(&head)) {		/* удаление списка */
	n1 = LIST_FIRST(&head);
	LIST_REMOVE(n1, entries);
	free(n1);
}

n1 = LIST_FIRST(&head);			/* быстрое удаление списка */
while (n1 != NULL) {
	n2 = LIST_NEXT(n1, entries);
	free(n1);
	n1 = n2;
}
LIST_INIT(&head);

Хвостовые очереди

Хвостовая очередь начинается со структуры, определяемой макросом TAILQ_HEAD. Эта структура содержит пару указателей, один для первого элемента хвостовой очереди, а другой для последнего элемента хвостовой очереди. Элементы связаны дважды так, что любой элемент может быть удалён без прохождения по всей очереди. Новые элементы могут быть добавлены в хвостовую очередь перед и после существующего элемента, в конец или в начало очереди. Структура TAILQ_HEAD объявляется следующим образом:

TAILQ_HEAD(HEADNAME, TYPE) head;

где HEADNAME — имя определяемой структуры, а TYPE — тип связанных элементов в хвостовой очереди. Указатель на начало хвостовой очереди может в дальнейшем объявляться так:

struct HEADNAME *headp;

(Имена head и headp могут выбираться пользователем.)

Макрос TAILQ_HEAD_INITIALIZER запускает инициализатор для head хвостовой очереди.

Макрос TAILQ_CONCAT добавляет хвостовую очередь с началом head2 в конец очереди с началом head1, удаляя все элементы из первой.

Макрос TAILQ_EMPTY возвращает true, если в хвостовой очереди нет элементов.

Макрос TAILQ_ENTRY объявляет структуру, которая подключает элементы в хвостовую очередь.

Макрос TAILQ_FIRST возвращает первый элемент из хвостовой очереди или NULL, если очередь пуста.

Макрос TAILQ_FOREACH обходит хвостовую очередь, на которую ссылается head, из начала в конец, назначая var каждый элемент. Значение var равно NULL, если пройдена вся очередь или в ней нет элементов.

Макрос TAILQ_FOREACH_REVERSE обходит хвостовую очередь, на которую ссылается head, в обратном направлении, назначая var каждый элемент.

Макрос TAILQ_INIT инициализирует хвостовую очередь, на которую ссылается head.

Макрос TAILQ_INSERT_HEAD вставляет новый элемент I elm в начало хвостовой очереди.

Макрос TAILQ_INSERT_TAIL вставляет новый элемент elm в конец хвостовой очереди.

Макрос TAILQ_INSERT_AFTER вставляет новый элемент elm за элементом listelm.

Макрос TAILQ_INSERT_BEFORE вставляет новый элемент elm перед элементом listelm.

Макрос TAILQ_LAST возвращает последний элемент из хвостовой очереди или NULL, если очередь пуста.

Макрос TAILQ_NEXT возвращает следующий элемент из хвостовой очереди или NULL, если элемент последний.

Макрос TAILQ_PREV возвращает предыдущий элемент из хвостовой очереди или NULL, если элемент первый.

Макрос TAILQ_REMOVE удаляет элемент elm из хвостовой очереди.

Макрос TAILQ_SWAP меняет местами содержимое head1 и head2.

Пример хвостовой очереди

TAILQ_HEAD(tailhead, entry) head =
    TAILQ_HEAD_INITIALIZER(head);
struct tailhead *headp;			/* начало хвостовой очереди */
struct entry {
	...
	TAILQ_ENTRY(entry) entries;	/* хвостовая очередь */
	...
} *n1, *n2, *n3, *np;

TAILQ_INIT(&head);			/* инициализация очереди */

n1 = malloc(sizeof(struct entry));	/* вставка в начало */
TAILQ_INSERT_HEAD(&head, n1, entries);

n1 = malloc(sizeof(struct entry));	/* вставка в конец */
TAILQ_INSERT_TAIL(&head, n1, entries);

n2 = malloc(sizeof(struct entry));	/* вставка последующего */
TAILQ_INSERT_AFTER(&head, n1, n2, entries);

n3 = malloc(sizeof(struct entry));	/* вставка перед */
TAILQ_INSERT_BEFORE(n2, n3, entries);

TAILQ_REMOVE(&head, n2, entries);	/* удаление */
free(n2);
					/* обход из начало в конец */
TAILQ_FOREACH(np, &head, entries)
	np-> ...
					/* обход в обратном направлении */
TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
	np-> ...
					/* удаление TailQ */
while (!TAILQ_EMPTY(&head)) {
	n1 = TAILQ_FIRST(&head);
	TAILQ_REMOVE(&head, n1, entries);
	free(n1);
}
					/* быстрое удаление TailQ */
n1 = TAILQ_FIRST(&head);
while (n1 != NULL) {
	n2 = TAILQ_NEXT(n1, entries);
	free(n1);
	n1 = n2;
}

TAILQ_INIT(&head);
n2 = malloc(sizeof(struct entry));  /* вставка перед */
CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
                                    /* обход из начала в конец */
for (np = head.cqh_first; np != (void *)&head;
        np = np->entries.cqe_next)
    np-> ...
                                    /* обход в обратном направлении */
for (np = head.cqh_last; np != (void *)&head; np = np->entries.cqe_prev)
    np-> ...
                                    /* удаление */
while (head.cqh_first != (void *)&head)
    CIRCLEQ_REMOVE(&head, head.cqh_first, entries);