Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifndef _LIST2_H
- #define _LIST2_H
- // avp 2012, 2013 Более привычный (чем циклический в list.h) 2-напрвленный список.
- #include <stddef.h>
- // list2 item. Embed it in data structure. Поля связи во всех элементах списка.
- typedef struct l2item {
- struct l2item *next,
- *prev;
- } List2;
- // list2 head (представляет список в программе)
- typedef struct l2header {
- struct l2item *head,
- *tail;
- size_t size;
- } List2head;
- #define LIST2_HEAD(name) \
- List2head name = {0,0,0}
- #define INIT_LIST2_HEAD(ptr) ({List2head *_p = (ptr); \
- _p->head = 0; _p->tail = 0; _p->size = 0; })
- #define list2_power(ptr) ((ptr)->size)
- /*
- * Добавляем новую голову
- * returns предыдущую голову
- */
- static inline List2 *
- list2_add (List2 *_new, List2head *head)
- {
- List2 *ret = head->head;
- _new->prev = NULL;
- if (!ret)
- head->tail = _new;
- head->head = _new;
- head->size++;
- return _new->next = ret;
- }
- /*
- * Добавляем новый хвост
- * returns предыдущий хвост
- */
- static inline List2 *
- list2_add_tail (List2 *_new, List2head *head)
- {
- List2 *ret = head->tail;
- _new->next = NULL;
- if (!ret)
- head->head = _new;
- else
- ret->next = _new;
- head->tail = _new;
- head->size++;
- return _new->prev = ret;
- }
- /*
- * Удаляем голову и
- * returns ee
- */
- static inline List2 *
- list2_del_head (List2head *head)
- {
- List2 *ret = head->head;
- if (ret) {
- if (!(head->head = ret->next)) // empty
- head->tail = 0;
- else
- head->head->prev = 0;
- head->size--;
- ret->next = ret->prev = 0;
- }
- return ret;
- }
- /*
- * Удаляем хвост и
- * returns его
- */
- static inline List2 *
- list2_del_tail (List2head *head)
- {
- List2 *ret = head->tail;
- if (ret) {
- if (!(head->tail = ret->prev)) // empty
- head->head = 0;
- else
- head->tail->next = 0;
- head->size--;
- ret->next = ret->prev = 0;
- }
- return ret;
- }
- /*
- * Удаляем элемент списка
- * returns голову списка
- */
- static inline List2 *
- list2_del_item (List2 *item, List2head *head)
- {
- if (item->next)
- item->next->prev = item->prev;
- else // correct tail
- head->tail = item->prev;
- if (item->prev)
- item->prev->next = item->next;
- else // correct head
- head->head = item->next;
- head->size--;
- item->next = item->prev = 0;
- return head->head;
- }
- /**
- ** from include/linux/list.h **
- * list_entry - get the struct for this entry
- * @ptr: the &struct l2item pointer.
- * @type: the type of the struct this is embedded in.
- * @member: the name of the l2item_struct within the struct.
- */
- #define list_entry(ptr, type, member) \
- ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
- /*
- * Записывем первый список в хвост второго списка
- * первый обнуляется
- */
- static inline void
- list2_append (List2head *list1, List2head *list2)
- {
- if (list1->size) {
- if (list2->size) {
- list2->tail->next = list1->head;
- list1->head->prev = list2->tail;
- } else {
- list2->head = list1->head;
- }
- list2->tail = list1->tail;
- list2->size += list1->size;
- list1->head = list1->tail = 0;
- list1->size = 0;
- }
- }
- /*
- * Вставим первый список перед заданным элементом второго
- * (если item == NULL, то в начало)
- * первый список обнуляется
- */
- static inline void
- list2_insert (List2head *list1, List2head *list2, List2 *item)
- {
- if (list1->size) {
- if (list2->size) {
- if (item && item->prev) {
- item->prev->next = list1->head;
- list1->head->prev = item->prev;
- list1->tail->next = item;
- item->prev = list1->tail;
- } else { // вставим list1 перед list2
- list2->head->prev = list1->tail;
- list1->tail->next = list2->head;
- list2->head = list1->head;
- }
- } else {
- list2->head = list1->head;
- list2->tail = list1->tail;
- }
- list2->size += list1->size;
- list1->head = list1->tail = 0;
- list1->size = 0;
- }
- }
- // pos указатель на List2 в элементе списка
- #define list2_for_each(pos, _head) \
- for (pos = (_head)->head; pos; pos = pos->next)
- // _head указатель на список (заголовок списка)
- #define list2_for_each_prev(pos, _head) \
- for (pos = (_head)->tail; pos; pos = pos->prev)
- // tmp переменная типа List2 *
- // в этом цикле можно удалять pos
- #define list2_for_each_safe(pos,tmp,_head) \
- for (pos = (_head)->head, tmp = pos? pos->next: 0; pos; \
- pos = tmp, tmp = pos? pos->next: 0)
- /************ list mergesort avp 2013
- http://www.williamspublishing.com/PDF/978-5-8459-1650-1/part.pdf
- *************/
- /*
- * Слияние списков, завершающихся next == 0,
- * в соответствии с fcmp(elem1, elem2) (returns N < 0, 0 for EQUAL or N > 0)
- * l1, l2 указатели на первые элементы списков
- * указатели prev становятся неактуальными
- */
- static List2 *
- merge2lists (List2 *l1, List2 *l2, int (*fcmp)(List2 *e1, List2 *e2))
- {
- List2 result = {0, 0}, *cur = &result;
- while (l1 && l2)
- if (fcmp(l1, l2) <= 0) {
- cur->next = l1; cur = l1; l1 = l1->next;
- } else {
- cur->next = l2; cur = l2; l2 = l2->next;
- }
- cur->next = (l1 ? l1 : l2); // оставшиеся элементы запишем в хвост result
- return result.next;
- }
- /*
- * Сортировка списка по указателю на его первый элемент
- * в соответствии с fcmp(elem1, elem2) (returns N < 0, 0 for EQUAL or N > 0)
- * указатели prev становятся неактуальными
- */
- static List2 *
- l_mergesort (List2 *list, int (*fcmp)(List2 *e1, List2 *e2))
- {
- if (list == 0 || list->next == 0) return list;
- List2 *a = list, *b = list->next;
- // хитро делим список пополам. b бежит через элемент
- while (b && b->next) {
- list = list->next; b = b->next->next;
- }
- b = list->next;
- list->next = 0; // разделим, terminate первую половину
- return merge2lists(l_mergesort(a, fcmp), l_mergesort(b, fcmp), fcmp);
- }
- /*
- * mergesort двусвязного списка
- * в соответствии с fcmp(elem1, elem2) (returns N < 0, 0 for EQUAL or N > 0)
- */
- static void
- list2_sort (List2head *list, int (*fcmp)(List2 *e1, List2 *e2))
- {
- if (list->size < 2)
- return;
- List2 *slist = l_mergesort(list->head, fcmp), *p = 0;
- list->head = slist;
- // восстановим указатели prev
- while (slist) {
- slist->prev = p;
- p = slist;
- slist = slist->next;
- }
- list->tail = p;
- }
- // up_mergesort (UNSTABLE!!!) and not faster...
- #endif
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement