list2.h

#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