/src/binutils-gdb/include/doubly-linked-list.h

Source
/* Manipulate doubly linked lists.
   Copyright (C) 2025-2026 Free Software Foundation, Inc.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */


#ifndef _DOUBLY_LINKED_LIST_H
#define _DOUBLY_LINKED_LIST_H

/* Doubly linked list implementation enforcing typing.

   This implementation of doubly linked list tries to achieve the enforcement of
   typing similarly to C++ templates, but without encapsulation.

   All the functions are prefixed with the type of the value: "AType_xxx".
   Some functions are prefixed with "_AType_xxx" and are not part of the public
   API, so should not be used, except for _##LTYPE##_merge_sort with a caveat
   (see note above its definition).

   Each function (### is a placeholder for method name) has a macro for:
   (1) its invocation LINKED_LIST_###(LTYPE).
   (2) its prototype LINKED_LIST_DECL_###(A, A2, scope). To add in a header
       file, or a source file for forward declaration. 'scope' should be set
       respectively to 'extern', or 'static'.
   (3) its definition LINKED_LIST_DEFN_###(A, A2, scope). To add in a source
       file with the 'scope' set respectively to nothing, or 'static' depending
       on (2).

   Data structures requirements:
   - LTYPE corresponds to the node of a doubly linked list. It needs to define
     attributes 'prev' and 'next' which are pointers on the type of a node.
     For instance:
       struct my_list_node
       {
   T value;
   struct my_list_node *prev;
   struct my_list_node *next;
       };
   - LWRAPPERTYPE is a structure wrapping the nodes and others metadata (first,
     last, size).
 */


/* Mutative operations:
    - append
    - prepend
    - insert_before
    - pop_front
    - pop_back
    - remove
    - swap
   The header and body of each of those operation can be declared individually,
   or as a whole via LINKED_LIST_MUTATIVE_OPS_PROTOTYPE for the prototypes, and
   LINKED_LIST_MUTATIVE_OPS_DECL for the implementations.  */

/* Append the given node new_ to the exising list.
   Precondition: prev and next of new_ must be NULL.  */
#define LINKED_LIST_APPEND(LTYPE)   LTYPE##_append

#define LINKED_LIST_DECL_APPEND(LWRAPPERTYPE, LTYPE, EXPORT)    \
  EXPORT void               \
  LTYPE##_append (LWRAPPERTYPE *wrapper, LTYPE *new_)

#define LINKED_LIST_DEFN_APPEND(LWRAPPERTYPE, LTYPE, EXPORT)    \
EXPORT void               \
LTYPE##_append (LWRAPPERTYPE *wrapper, LTYPE *new_)     \
{                 \
  if (wrapper->last == NULL)           \
    wrapper->first = new_;           \
  else                  \
    {                 \
      new_->prev = wrapper->last;         \
      wrapper->last->next = new_;         \
    }                  \
  wrapper->last = new_;             \
  ++wrapper->size;              \
}

/* Prepend the given node new_ to the existing list.
   Precondition: prev and next of new_ must be NULL.  */
#define LINKED_LIST_PREPEND(LTYPE)    LTYPE##_prepend

#define LINKED_LIST_DECL_PREPEND(LWRAPPERTYPE, LTYPE, EXPORT)   \
  EXPORT void               \
  LTYPE##_prepend (LWRAPPERTYPE *wrapper, LTYPE *new_)

#define LINKED_LIST_DEFN_PREPEND(LWRAPPERTYPE, LTYPE, EXPORT)   \
EXPORT void               \
LTYPE##_prepend (LWRAPPERTYPE *wrapper, LTYPE *new_)      \
{                 \
  if (wrapper->first == NULL)           \
    wrapper->last = new_;           \
  else                  \
    {                 \
      new_->next = wrapper->first;          \
      wrapper->first->prev = new_;          \
    }                  \
  wrapper->first = new_;            \
  ++wrapper->size;              \
}

/* Insert the given node new_ before 'where' in the existing list.
   If where == NULL, the insertion is equivalent to an append.
   If where == first, the insertion is equivalent to a prepend.  */
#define LINKED_LIST_INSERT_BEFORE(LTYPE)  LTYPE##_insert_before

#define LINKED_LIST_DECL_INSERT_BEFORE(LWRAPPERTYPE, LTYPE, EXPORT) \
  EXPORT void               \
  LTYPE##_insert_before (LWRAPPERTYPE *wrapper,       \
       LTYPE *new_,         \
       LTYPE *where)

#define LINKED_LIST_DEFN_INSERT_BEFORE(LWRAPPERTYPE, LTYPE, EXPORT) \
EXPORT void               \
LTYPE##_insert_before (LWRAPPERTYPE *wrapper,       \
           LTYPE *new_,         \
           LTYPE *where)          \
{                 \
  if (where == wrapper->first)           \
    LTYPE##_prepend (wrapper, new_);         \
  else if (where == NULL)           \
    LTYPE##_append (wrapper, new_);          \
  else                  \
    {                 \
      where->prev->next = new_;           \
      new_->prev = where->prev;           \
      where->prev = new_;           \
      new_->next = where;           \
      ++wrapper->size;              \
    }                  \
}

/* Pop the first node of the list.  */
#define LINKED_LIST_POP_FRONT(LTYPE)    LTYPE##_pop_front

#define LINKED_LIST_DECL_POP_FRONT(LWRAPPERTYPE, LTYPE, EXPORT)   \
  EXPORT LTYPE *              \
  LTYPE##_pop_front (LWRAPPERTYPE *wrapper)

#define LINKED_LIST_DEFN_POP_FRONT(LWRAPPERTYPE, LTYPE, EXPORT)   \
EXPORT LTYPE *                \
LTYPE##_pop_front (LWRAPPERTYPE *wrapper)       \
{                 \
  LTYPE *front_node = wrapper->first;         \
  if (front_node != NULL)           \
    {                 \
      wrapper->first = front_node->next;        \
      if (wrapper->last == front_node)         \
  wrapper->last = NULL;           \
      else                \
  {               \
    front_node->next->prev = NULL;        \
    front_node->next = NULL;          \
  }                \
      front_node->next = NULL;            \
      --wrapper->size;              \
    }                 \
  return front_node;              \
}

/* Pop the last node of the list.  */
#define LINKED_LIST_POP_BACK(LTYPE)   LTYPE##_pop_back

#define LINKED_LIST_DECL_POP_BACK(LWRAPPERTYPE, LTYPE, EXPORT)    \
  EXPORT LTYPE *              \
  LTYPE##_pop_back (LWRAPPERTYPE *wrapper)

#define LINKED_LIST_DEFN_POP_BACK(LWRAPPERTYPE, LTYPE, EXPORT)    \
EXPORT LTYPE *                \
LTYPE##_pop_back (LWRAPPERTYPE *wrapper)        \
{                 \
  LTYPE *back_node = wrapper->last;         \
  if (back_node != NULL)           \
    {                 \
      wrapper->last = back_node->prev;          \
      if (wrapper->first == back_node)         \
  wrapper->first = NULL;           \
      else                \
  {               \
    back_node->prev->next = NULL;         \
    back_node->prev = NULL;         \
  }                \
      back_node->prev = NULL;           \
      --wrapper->size;              \
    }                 \
  return back_node;             \
}

/* Remove the given node from the existing list, and return the previous
   node.  */
#define LINKED_LIST_REMOVE(LTYPE)   LTYPE##_remove

#define LINKED_LIST_DECL_REMOVE(LWRAPPERTYPE, LTYPE, EXPORT)    \
  EXPORT LTYPE *              \
  LTYPE##_remove (LWRAPPERTYPE *wrapper, LTYPE *node)

#define LINKED_LIST_DEFN_REMOVE(LWRAPPERTYPE, LTYPE, EXPORT)    \
EXPORT LTYPE *                \
LTYPE##_remove (LWRAPPERTYPE *wrapper, LTYPE *node)     \
{                 \
  LTYPE *previous = NULL;           \
                  \
  if (node->prev != NULL)           \
    {                 \
      node->prev->next = node->next;          \
      if (node->next == NULL)           \
  wrapper->last = node->prev;         \
      else                \
  node->next->prev = node->prev;         \
      previous = node->prev;            \
      node->next = NULL;            \
      node->prev = NULL;            \
      --wrapper->size;              \
    }                  \
  else                  \
    LTYPE##_pop_front (wrapper);         \
                  \
  return previous;              \
}

/* Swap two nodes in a list.  */
#define LINKED_LIST_SWAP(LTYPE)     LTYPE##_swap

#define LINKED_LIST_DECL_SWAP(LWRAPPERTYPE, LTYPE, EXPORT)    \
  EXPORT void               \
  LTYPE##_swap (LWRAPPERTYPE *wrapper, LTYPE *node1, LTYPE *node2)

#define LINKED_LIST_DEFN_SWAP(LWRAPPERTYPE, LTYPE, EXPORT)    \
EXPORT void               \
LTYPE##_swap (LWRAPPERTYPE *wrapper, LTYPE *node1, LTYPE *node2)  \
{                 \
  LTYPE *prev1 = node1->prev;           \
  LTYPE *next1 = node1->next;           \
  LTYPE *prev2 = node2->prev;           \
  LTYPE *next2 = node2->next;           \
                  \
  if (prev1 != NULL)             \
    prev1->next = node2;           \
  else                  \
    wrapper->first = node2;           \
  if (prev2 != NULL)             \
    prev2->next = node1;           \
  else                  \
    wrapper->first = node1;           \
                  \
  if (next1 != NULL)             \
    next1->prev = node2;           \
  else                  \
    wrapper->last = node2;           \
  if (next2 != NULL)             \
    next2->prev = node1;           \
  else                  \
    wrapper->last = node1;           \
                  \
  {                 \
    LTYPE *temp = node1->next;            \
    node1->next = node2->next;            \
    node2->next = temp;             \
  }                 \
  {                 \
    LTYPE *temp = node1->prev;            \
    node1->prev = node2->prev;            \
    node2->prev = temp;             \
  }                 \
}

/* Swap two lists, i.e. swap two wrappers.  */
#define LINKED_LIST_SWAP_LISTS(LWRAPPERTYPE)  LWRAPPERTYPE##_swap_lists

#define LINKED_LIST_DECL_SWAP_LISTS(LWRAPPERTYPE, LTYPE, EXPORT)  \
  EXPORT void               \
  LWRAPPERTYPE##_swap_lists (LWRAPPERTYPE *left_w, LWRAPPERTYPE *right_w)

#define LINKED_LIST_DEFN_SWAP_LISTS(LWRAPPERTYPE, LTYPE, EXPORT)  \
EXPORT void               \
LWRAPPERTYPE##_swap_lists (LWRAPPERTYPE *left_w, LWRAPPERTYPE *right_w) \
{                 \
  {                 \
    LTYPE *temp = left_w->first;          \
    left_w->first = right_w->first;         \
    right_w->first = temp;            \
  }                 \
  {                 \
    LTYPE *temp = left_w->last;           \
    left_w->last = right_w->last;         \
    right_w->last = temp;           \
  }                 \
  {                 \
    unsigned int temp = left_w->size;         \
    left_w->size = right_w->size;         \
    right_w->size = temp;           \
  }                 \
}

/* Note: all the mutative operations below also update the data in the wrapper,
   i.e. first, last and size.  */
#define LINKED_LIST_MUTATIVE_OPS_PROTOTYPE(LWRAPPERTYPE, LTYPE, EXPORT) \
  LINKED_LIST_DECL_APPEND(LWRAPPERTYPE, LTYPE, EXPORT);     \
  LINKED_LIST_DECL_PREPEND(LWRAPPERTYPE, LTYPE, EXPORT);    \
  LINKED_LIST_DECL_INSERT_BEFORE(LWRAPPERTYPE, LTYPE, EXPORT);    \
  LINKED_LIST_DECL_POP_FRONT(LWRAPPERTYPE, LTYPE, EXPORT);    \
  LINKED_LIST_DECL_POP_BACK(LWRAPPERTYPE, LTYPE, EXPORT);   \
  LINKED_LIST_DECL_REMOVE(LWRAPPERTYPE, LTYPE, EXPORT);     \
  LINKED_LIST_DECL_SWAP(LWRAPPERTYPE, LTYPE, EXPORT);     \
  LINKED_LIST_DECL_SWAP_LISTS(LWRAPPERTYPE, LTYPE, EXPORT)

#define LINKED_LIST_MUTATIVE_OPS_DECL(LWRAPPERTYPE, LTYPE, EXPORT)  \
  LINKED_LIST_DEFN_APPEND(LWRAPPERTYPE, LTYPE, EXPORT)      \
  LINKED_LIST_DEFN_PREPEND(LWRAPPERTYPE, LTYPE, EXPORT)     \
  LINKED_LIST_DEFN_INSERT_BEFORE(LWRAPPERTYPE, LTYPE, EXPORT)   \
  LINKED_LIST_DEFN_POP_FRONT(LWRAPPERTYPE, LTYPE, EXPORT)   \
  LINKED_LIST_DEFN_POP_BACK(LWRAPPERTYPE, LTYPE, EXPORT)    \
  LINKED_LIST_DEFN_REMOVE(LWRAPPERTYPE, LTYPE, EXPORT)      \
  LINKED_LIST_DEFN_SWAP(LWRAPPERTYPE, LTYPE, EXPORT);     \
  LINKED_LIST_DEFN_SWAP_LISTS(LWRAPPERTYPE, LTYPE, EXPORT)


/* Sorting.  */

#define LINKED_LIST_MERGE_SORT_(LTYPE)  LTYPE##_merge_sort_

#define LINKED_LIST_MERGE_SORT(LTYPE) LTYPE##_merge_sort

#define LINKED_LIST_MERGE_SORT_PROTOTYPE_(LTYPE, EXPORT)    \
  EXPORT LTYPE *              \
  LTYPE##_merge_sort_ (LTYPE *node,         \
           int (*fn_cmp) (const LTYPE *, const LTYPE *))

#define LINKED_LIST_MERGE_SORT_PROTOTYPE(LWRAPPERTYPE, LTYPE, EXPORT) \
  EXPORT void               \
  LTYPE##_merge_sort (LWRAPPERTYPE *wrapper,        \
          int (*fn_cmp) (const LTYPE *, const LTYPE *))

/* Note: all the functions and macros below starting with "_" should be
   considered private.  */

/* Compute the middle element of the list based on the turtle and hare
   approach, i.e. the hare runs twice faster than the turtle.  */
#define _MERGE_SORT_IMPL_COMPUTE_TURTLE(LTYPE)        \
static inline LTYPE *             \
LTYPE##_merge_sort_compute_turtle_ (LTYPE *node)      \
{                 \
  if (node == NULL)             \
    return node;             \
                  \
  LTYPE *turtle = node, *hare = node->next;       \
  while (hare != NULL && hare->next != NULL)       \
    {                 \
      turtle = turtle->next;            \
      hare = hare->next->next;            \
    }                  \
  return turtle;              \
}

/* Append n at the end of l_out, and return the next node after n.
   l_out and l_last should be ideally encapsulated into a list structure
   but this is overkill for what we need here.  */
#define _MERGE_SORT_IMPL_OUT_APPEND(LTYPE)        \
static inline LTYPE *             \
LTYPE##_merge_sort_out_append_ (LTYPE **l_out, LTYPE **l_last,    \
        LTYPE *n)       \
{                 \
  if (*l_last == NULL)             \
    {                 \
      *l_last = n;              \
      *l_out = n;             \
      n->prev = NULL;             \
    }                  \
  else                  \
    {                 \
      (*l_last)->next = n;            \
      n->prev = *l_last;            \
      *l_last = n;              \
    }                  \
                  \
  return n->next;             \
}

/* Merge two sorted lists together.
   The returned value corresponds to the first element of the list.
   Note: both input lists are invalidated after the call.  */
#define _MERGE_SORT_IMPL_MERGE(LTYPE)         \
static inline LTYPE *             \
LTYPE##_merge_sort_merge_ (LTYPE *l_left, LTYPE *l_right,   \
         int (*fn_cmp) (const LTYPE *, const LTYPE *))\
{                 \
  if (l_left == NULL)             \
    return l_right;             \
  else if (l_right == NULL)           \
    return l_left;             \
                  \
  LTYPE *l_out = NULL, *l_last = NULL;          \
                  \
  LTYPE *l_l = l_left, *l_r = l_right;          \
  while (l_l != NULL && l_r != NULL)         \
    {                 \
      int cmp = fn_cmp (l_l, l_r);          \
      if (cmp <= 0)             \
  l_l = LTYPE##_merge_sort_out_append_ (&l_out, &l_last, l_l); \
      else                \
  l_r = LTYPE##_merge_sort_out_append_ (&l_out, &l_last, l_r); \
    }                 \
                  \
  LTYPE *l_remaining = (l_l != NULL) ? l_l : l_r;     \
  while (l_remaining != NULL)           \
    l_remaining =             \
      LTYPE##_merge_sort_out_append_ (&l_out, &l_last, l_remaining); \
                  \
  return l_out;               \
}

/* Merge sort implementation taking the first node of the list to sort,
   and the comparison function. Returns the first node of the sorted list.
   Note: use this if you don't care about updating the information in the
   wrapper.  */
#define _MERGE_SORT_DEFN_SORT(LTYPE, EXPORT)        \
EXPORT LTYPE *                \
LTYPE##_merge_sort_ (LTYPE *node,         \
         int (*fn_cmp)(const LTYPE *, const LTYPE *)) \
{                 \
  if (node == NULL)             \
    return NULL;             \
  else if (node->next == NULL)           \
    return node;             \
                  \
  LTYPE *left_end = LTYPE##_merge_sort_compute_turtle_ (node);   \
  LTYPE *left_begin = node;           \
  LTYPE *right_begin = left_end->next;          \
  /* break the list. */             \
  left_end->next = NULL;            \
  right_begin->prev = NULL;           \
                  \
  left_begin = LTYPE##_merge_sort_ (left_begin, fn_cmp);    \
  right_begin = LTYPE##_merge_sort_ (right_begin, fn_cmp);   \
  return LTYPE##_merge_sort_merge_ (left_begin, right_begin, fn_cmp); \
}

/* Merge sort wrapper that the end-user should be using as it updates the
   first and last metadata of the list in wrapper as well.
   If the user does not want to pay the cost of the update of the data,
   it can directly use _##LTYPE##_merge_sort_merge.  */
#define _MERGE_SORT_DEFN_WRAPPER_SORT(LWRAPPERTYPE, LTYPE, EXPORT)  \
EXPORT void               \
LTYPE##_merge_sort (LWRAPPERTYPE *wrapper,        \
        int (*fn_cmp) (const LTYPE *, const LTYPE *)) \
{                 \
  wrapper->first = LTYPE##_merge_sort_ (wrapper->first, fn_cmp);  \
                  \
  if (wrapper->first == NULL || wrapper->first->next == NULL)   \
    wrapper->last = wrapper->first;         \
  else                  \
    for (LTYPE *node = wrapper->first;          \
   node != NULL;             \
   node = node->next)           \
      wrapper->last = node;           \
}

#define LINKED_LIST_MERGE_SORT_DECL(LWRAPPERTYPE, LTYPE, EXPORT)  \
  _MERGE_SORT_IMPL_COMPUTE_TURTLE(LTYPE)        \
  _MERGE_SORT_IMPL_OUT_APPEND(LTYPE)          \
  _MERGE_SORT_IMPL_MERGE(LTYPE)           \
  _MERGE_SORT_DEFN_SORT(LTYPE, EXPORT)          \
  _MERGE_SORT_DEFN_WRAPPER_SORT(LWRAPPERTYPE, LTYPE, EXPORT)

#endif /* _DOUBLY_LINKED_LIST_H */

Coverage Report

Created: 2026-03-10 08:46

Line	Count	Source
1		/* Manipulate doubly linked lists.
2		Copyright (C) 2025-2026 Free Software Foundation, Inc.
3
4		This program is free software; you can redistribute it and/or modify
5		it under the terms of the GNU General Public License as published by
6		the Free Software Foundation; either version 3 of the License, or
7		(at your option) any later version.
8
9		This program is distributed in the hope that it will be useful,
10		but WITHOUT ANY WARRANTY; without even the implied warranty of
11		MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12		GNU General Public License for more details.
13
14		You should have received a copy of the GNU General Public License
15		along with this program. If not, see <http://www.gnu.org/licenses/>. */
16
17
18		#ifndef _DOUBLY_LINKED_LIST_H
19		#define _DOUBLY_LINKED_LIST_H
20
21		/* Doubly linked list implementation enforcing typing.
22
23		This implementation of doubly linked list tries to achieve the enforcement of
24		typing similarly to C++ templates, but without encapsulation.
25
26		All the functions are prefixed with the type of the value: "AType_xxx".
27		Some functions are prefixed with "_AType_xxx" and are not part of the public
28		API, so should not be used, except for _##LTYPE##_merge_sort with a caveat
29		(see note above its definition).
30
31		Each function (### is a placeholder for method name) has a macro for:
32		(1) its invocation LINKED_LIST_###(LTYPE).
33		(2) its prototype LINKED_LIST_DECL_###(A, A2, scope). To add in a header
34		file, or a source file for forward declaration. 'scope' should be set
35		respectively to 'extern', or 'static'.
36		(3) its definition LINKED_LIST_DEFN_###(A, A2, scope). To add in a source
37		file with the 'scope' set respectively to nothing, or 'static' depending
38		on (2).
39
40		Data structures requirements:
41		- LTYPE corresponds to the node of a doubly linked list. It needs to define
42		attributes 'prev' and 'next' which are pointers on the type of a node.
43		For instance:
44		struct my_list_node
45		{
46		T value;
47		struct my_list_node *prev;
48		struct my_list_node *next;
49		};
50		- LWRAPPERTYPE is a structure wrapping the nodes and others metadata (first,
51		last, size).
52		*/
53
54
55		/* Mutative operations:
56		- append
57		- prepend
58		- insert_before
59		- pop_front
60		- pop_back
61		- remove
62		- swap
63		The header and body of each of those operation can be declared individually,
64		or as a whole via LINKED_LIST_MUTATIVE_OPS_PROTOTYPE for the prototypes, and
65		LINKED_LIST_MUTATIVE_OPS_DECL for the implementations. */
66
67		/* Append the given node new_ to the exising list.
68		Precondition: prev and next of new_ must be NULL. */
69	38.6k	#define LINKED_LIST_APPEND(LTYPE) LTYPE##_append
70
71		#define LINKED_LIST_DECL_APPEND(LWRAPPERTYPE, LTYPE, EXPORT) \
72		EXPORT void \
73		LTYPE##_append (LWRAPPERTYPE wrapper, LTYPE new_)
74
75		#define LINKED_LIST_DEFN_APPEND(LWRAPPERTYPE, LTYPE, EXPORT) \
76		EXPORT void \
77	38.6k	LTYPE##_append (LWRAPPERTYPE wrapper, LTYPE new_) \
78	38.6k	{ \
79	38.6k	if (wrapper->last == NULL) \
80	38.6k	wrapper->first = new_; \
81	38.6k	else \
82	38.6k	{ \
83	38.2k	new_->prev = wrapper->last; \
84	38.2k	wrapper->last->next = new_; \
85	38.2k	} \
86	38.6k	wrapper->last = new_; \
87	38.6k	++wrapper->size; \
88	38.6k	}
89
90		/* Prepend the given node new_ to the existing list.
91		Precondition: prev and next of new_ must be NULL. */
92		#define LINKED_LIST_PREPEND(LTYPE) LTYPE##_prepend
93
94		#define LINKED_LIST_DECL_PREPEND(LWRAPPERTYPE, LTYPE, EXPORT) \
95		EXPORT void \
96		LTYPE##_prepend (LWRAPPERTYPE wrapper, LTYPE new_)
97
98		#define LINKED_LIST_DEFN_PREPEND(LWRAPPERTYPE, LTYPE, EXPORT) \
99		EXPORT void \
100	0	LTYPE##_prepend (LWRAPPERTYPE wrapper, LTYPE new_) \
101	0	{ \
102	0	if (wrapper->first == NULL) \
103	0	wrapper->last = new_; \
104	0	else \
105	0	{ \
106	0	new_->next = wrapper->first; \
107	0	wrapper->first->prev = new_; \
108	0	} \
109	0	wrapper->first = new_; \
110	0	++wrapper->size; \
111	0	}
112
113		/* Insert the given node new_ before 'where' in the existing list.
114		If where == NULL, the insertion is equivalent to an append.
115		If where == first, the insertion is equivalent to a prepend. */
116	0	#define LINKED_LIST_INSERT_BEFORE(LTYPE) LTYPE##_insert_before
117
118		#define LINKED_LIST_DECL_INSERT_BEFORE(LWRAPPERTYPE, LTYPE, EXPORT) \
119		EXPORT void \
120		LTYPE##_insert_before (LWRAPPERTYPE *wrapper, \
121		LTYPE *new_, \
122		LTYPE *where)
123
124		#define LINKED_LIST_DEFN_INSERT_BEFORE(LWRAPPERTYPE, LTYPE, EXPORT) \
125		EXPORT void \
126		LTYPE##_insert_before (LWRAPPERTYPE *wrapper, \
127		LTYPE *new_, \
128	0	LTYPE *where) \
129	0	{ \
130	0	if (where == wrapper->first) \
131	0	LTYPE##_prepend (wrapper, new_); \
132	0	else if (where == NULL) \
133	0	LTYPE##_append (wrapper, new_); \
134	0	else \
135	0	{ \
136	0	where->prev->next = new_; \
137	0	new_->prev = where->prev; \
138	0	where->prev = new_; \
139	0	new_->next = where; \
140	0	++wrapper->size; \
141	0	} \
142	0	}
143
144		/* Pop the first node of the list. */
145		#define LINKED_LIST_POP_FRONT(LTYPE) LTYPE##_pop_front
146
147		#define LINKED_LIST_DECL_POP_FRONT(LWRAPPERTYPE, LTYPE, EXPORT) \
148		EXPORT LTYPE * \
149		LTYPE##_pop_front (LWRAPPERTYPE *wrapper)
150
151		#define LINKED_LIST_DEFN_POP_FRONT(LWRAPPERTYPE, LTYPE, EXPORT) \
152		EXPORT LTYPE * \
153	224	LTYPE##_pop_front (LWRAPPERTYPE *wrapper) \
154	224	{ \
155	224	LTYPE *front_node = wrapper->first; \
156	224	if (front_node != NULL) \
157	224	{ \
158	224	wrapper->first = front_node->next; \
159	224	if (wrapper->last == front_node) \
160	224	wrapper->last = NULL; \
161	224	else \
162	224	{ \
163	81	front_node->next->prev = NULL; \
164	81	front_node->next = NULL; \
165	81	} \
166	224	front_node->next = NULL; \
167	224	--wrapper->size; \
168	224	} \
169	224	return front_node; \
170	224	}
171
172		/* Pop the last node of the list. */
173		#define LINKED_LIST_POP_BACK(LTYPE) LTYPE##_pop_back
174
175		#define LINKED_LIST_DECL_POP_BACK(LWRAPPERTYPE, LTYPE, EXPORT) \
176		EXPORT LTYPE * \
177		LTYPE##_pop_back (LWRAPPERTYPE *wrapper)
178
179		#define LINKED_LIST_DEFN_POP_BACK(LWRAPPERTYPE, LTYPE, EXPORT) \
180		EXPORT LTYPE * \
181	0	LTYPE##_pop_back (LWRAPPERTYPE *wrapper) \
182	0	{ \
183	0	LTYPE *back_node = wrapper->last; \
184	0	if (back_node != NULL) \
185	0	{ \
186	0	wrapper->last = back_node->prev; \
187	0	if (wrapper->first == back_node) \
188	0	wrapper->first = NULL; \
189	0	else \
190	0	{ \
191	0	back_node->prev->next = NULL; \
192	0	back_node->prev = NULL; \
193	0	} \
194	0	back_node->prev = NULL; \
195	0	--wrapper->size; \
196	0	} \
197	0	return back_node; \
198	0	}
199
200		/* Remove the given node from the existing list, and return the previous
201		node. */
202	224	#define LINKED_LIST_REMOVE(LTYPE) LTYPE##_remove
203
204		#define LINKED_LIST_DECL_REMOVE(LWRAPPERTYPE, LTYPE, EXPORT) \
205		EXPORT LTYPE * \
206		LTYPE##_remove (LWRAPPERTYPE wrapper, LTYPE node)
207
208		#define LINKED_LIST_DEFN_REMOVE(LWRAPPERTYPE, LTYPE, EXPORT) \
209		EXPORT LTYPE * \
210	224	LTYPE##_remove (LWRAPPERTYPE wrapper, LTYPE node) \
211	224	{ \
212	224	LTYPE *previous = NULL; \
213	224	\
214	224	if (node->prev != NULL) \
215	224	{ \
216	0	node->prev->next = node->next; \
217	0	if (node->next == NULL) \
218	0	wrapper->last = node->prev; \
219	0	else \
220	0	node->next->prev = node->prev; \
221	0	previous = node->prev; \
222	0	node->next = NULL; \
223	0	node->prev = NULL; \
224	0	--wrapper->size; \
225	0	} \
226	224	else \
227	224	LTYPE##_pop_front (wrapper); \
228	224	\
229	224	return previous; \
230	224	}
231
232		/* Swap two nodes in a list. */
233		#define LINKED_LIST_SWAP(LTYPE) LTYPE##_swap
234
235		#define LINKED_LIST_DECL_SWAP(LWRAPPERTYPE, LTYPE, EXPORT) \
236		EXPORT void \
237		LTYPE##_swap (LWRAPPERTYPE wrapper, LTYPE node1, LTYPE *node2)
238
239		#define LINKED_LIST_DEFN_SWAP(LWRAPPERTYPE, LTYPE, EXPORT) \
240		EXPORT void \
241	0	LTYPE##_swap (LWRAPPERTYPE wrapper, LTYPE node1, LTYPE *node2) \
242	0	{ \
243	0	LTYPE *prev1 = node1->prev; \
244	0	LTYPE *next1 = node1->next; \
245	0	LTYPE *prev2 = node2->prev; \
246	0	LTYPE *next2 = node2->next; \
247	0	\
248	0	if (prev1 != NULL) \
249	0	prev1->next = node2; \
250	0	else \
251	0	wrapper->first = node2; \
252	0	if (prev2 != NULL) \
253	0	prev2->next = node1; \
254	0	else \
255	0	wrapper->first = node1; \
256	0	\
257	0	if (next1 != NULL) \
258	0	next1->prev = node2; \
259	0	else \
260	0	wrapper->last = node2; \
261	0	if (next2 != NULL) \
262	0	next2->prev = node1; \
263	0	else \
264	0	wrapper->last = node1; \
265	0	\
266	0	{ \
267	0	LTYPE *temp = node1->next; \
268	0	node1->next = node2->next; \
269	0	node2->next = temp; \
270	0	} \
271	0	{ \
272	0	LTYPE *temp = node1->prev; \
273	0	node1->prev = node2->prev; \
274	0	node2->prev = temp; \
275	0	} \
276	0	}
277
278		/* Swap two lists, i.e. swap two wrappers. */
279	0	#define LINKED_LIST_SWAP_LISTS(LWRAPPERTYPE) LWRAPPERTYPE##_swap_lists
280
281		#define LINKED_LIST_DECL_SWAP_LISTS(LWRAPPERTYPE, LTYPE, EXPORT) \
282		EXPORT void \
283		LWRAPPERTYPE##_swap_lists (LWRAPPERTYPE left_w, LWRAPPERTYPE right_w)
284
285		#define LINKED_LIST_DEFN_SWAP_LISTS(LWRAPPERTYPE, LTYPE, EXPORT) \
286		EXPORT void \
287	0	LWRAPPERTYPE##_swap_lists (LWRAPPERTYPE left_w, LWRAPPERTYPE right_w) \
288	0	{ \
289	0	{ \
290	0	LTYPE *temp = left_w->first; \
291	0	left_w->first = right_w->first; \
292	0	right_w->first = temp; \
293	0	} \
294	0	{ \
295	0	LTYPE *temp = left_w->last; \
296	0	left_w->last = right_w->last; \
297	0	right_w->last = temp; \
298	0	} \
299	0	{ \
300	0	unsigned int temp = left_w->size; \
301	0	left_w->size = right_w->size; \
302	0	right_w->size = temp; \
303	0	} \
304	0	} Unexecuted instantiation: obj_attr_subsection_v2_t_swap_lists Unexecuted instantiation: obj_attr_subsection_list_t_swap_lists
305
306		/* Note: all the mutative operations below also update the data in the wrapper,
307		i.e. first, last and size. */
308		#define LINKED_LIST_MUTATIVE_OPS_PROTOTYPE(LWRAPPERTYPE, LTYPE, EXPORT) \
309		LINKED_LIST_DECL_APPEND(LWRAPPERTYPE, LTYPE, EXPORT); \
310		LINKED_LIST_DECL_PREPEND(LWRAPPERTYPE, LTYPE, EXPORT); \
311		LINKED_LIST_DECL_INSERT_BEFORE(LWRAPPERTYPE, LTYPE, EXPORT); \
312		LINKED_LIST_DECL_POP_FRONT(LWRAPPERTYPE, LTYPE, EXPORT); \
313		LINKED_LIST_DECL_POP_BACK(LWRAPPERTYPE, LTYPE, EXPORT); \
314		LINKED_LIST_DECL_REMOVE(LWRAPPERTYPE, LTYPE, EXPORT); \
315		LINKED_LIST_DECL_SWAP(LWRAPPERTYPE, LTYPE, EXPORT); \
316		LINKED_LIST_DECL_SWAP_LISTS(LWRAPPERTYPE, LTYPE, EXPORT)
317
318		#define LINKED_LIST_MUTATIVE_OPS_DECL(LWRAPPERTYPE, LTYPE, EXPORT) \
319		LINKED_LIST_DEFN_APPEND(LWRAPPERTYPE, LTYPE, EXPORT) \
320		LINKED_LIST_DEFN_PREPEND(LWRAPPERTYPE, LTYPE, EXPORT) \
321		LINKED_LIST_DEFN_INSERT_BEFORE(LWRAPPERTYPE, LTYPE, EXPORT) \
322		LINKED_LIST_DEFN_POP_FRONT(LWRAPPERTYPE, LTYPE, EXPORT) \
323		LINKED_LIST_DEFN_POP_BACK(LWRAPPERTYPE, LTYPE, EXPORT) \
324		LINKED_LIST_DEFN_REMOVE(LWRAPPERTYPE, LTYPE, EXPORT) \
325		LINKED_LIST_DEFN_SWAP(LWRAPPERTYPE, LTYPE, EXPORT); \
326		LINKED_LIST_DEFN_SWAP_LISTS(LWRAPPERTYPE, LTYPE, EXPORT)
327
328
329		/* Sorting. */
330
331		#define LINKED_LIST_MERGE_SORT_(LTYPE) LTYPE##_merge_sort_
332
333	0	#define LINKED_LIST_MERGE_SORT(LTYPE) LTYPE##_merge_sort
334
335		#define LINKED_LIST_MERGE_SORT_PROTOTYPE_(LTYPE, EXPORT) \
336		EXPORT LTYPE * \
337		LTYPE##_merge_sort_ (LTYPE *node, \
338		int (fn_cmp) (const LTYPE , const LTYPE *))
339
340		#define LINKED_LIST_MERGE_SORT_PROTOTYPE(LWRAPPERTYPE, LTYPE, EXPORT) \
341		EXPORT void \
342		LTYPE##_merge_sort (LWRAPPERTYPE *wrapper, \
343		int (fn_cmp) (const LTYPE , const LTYPE *))
344
345		/* Note: all the functions and macros below starting with "_" should be
346		considered private. */
347
348		/* Compute the middle element of the list based on the turtle and hare
349		approach, i.e. the hare runs twice faster than the turtle. */
350		#define _MERGE_SORT_IMPL_COMPUTE_TURTLE(LTYPE) \
351		static inline LTYPE * \
352	0	LTYPE##_merge_sort_compute_turtle_ (LTYPE *node) \
353	0	{ \
354	0	if (node == NULL) \
355	0	return node; \
356	0	\
357	0	LTYPE turtle = node, hare = node->next; \
358	0	while (hare != NULL && hare->next != NULL) \
359	0	{ \
360	0	turtle = turtle->next; \
361	0	hare = hare->next->next; \
362	0	} \
363	0	return turtle; \
364	0	}
365
366		/* Append n at the end of l_out, and return the next node after n.
367		l_out and l_last should be ideally encapsulated into a list structure
368		but this is overkill for what we need here. */
369		#define _MERGE_SORT_IMPL_OUT_APPEND(LTYPE) \
370		static inline LTYPE * \
371		LTYPE##_merge_sort_out_append_ (LTYPE l_out, LTYPE l_last, \
372	0	LTYPE *n) \
373	0	{ \
374	0	if (*l_last == NULL) \
375	0	{ \
376	0	*l_last = n; \
377	0	*l_out = n; \
378	0	n->prev = NULL; \
379	0	} \
380	0	else \
381	0	{ \
382	0	(*l_last)->next = n; \
383	0	n->prev = *l_last; \
384	0	*l_last = n; \
385	0	} \
386	0	\
387	0	return n->next; \
388	0	}
389
390		/* Merge two sorted lists together.
391		The returned value corresponds to the first element of the list.
392		Note: both input lists are invalidated after the call. */
393		#define _MERGE_SORT_IMPL_MERGE(LTYPE) \
394		static inline LTYPE * \
395		LTYPE##_merge_sort_merge_ (LTYPE l_left, LTYPE l_right, \
396	0	int (fn_cmp) (const LTYPE , const LTYPE *))\
397	0	{ \
398	0	if (l_left == NULL) \
399	0	return l_right; \
400	0	else if (l_right == NULL) \
401	0	return l_left; \
402	0	\
403	0	LTYPE l_out = NULL, l_last = NULL; \
404	0	\
405	0	LTYPE l_l = l_left, l_r = l_right; \
406	0	while (l_l != NULL && l_r != NULL) \
407	0	{ \
408	0	int cmp = fn_cmp (l_l, l_r); \
409	0	if (cmp <= 0) \
410	0	l_l = LTYPE##_merge_sort_out_append_ (&l_out, &l_last, l_l); \
411	0	else \
412	0	l_r = LTYPE##_merge_sort_out_append_ (&l_out, &l_last, l_r); \
413	0	} \
414	0	\
415	0	LTYPE *l_remaining = (l_l != NULL) ? l_l : l_r; \
416	0	while (l_remaining != NULL) \
417	0	l_remaining = \
418	0	LTYPE##_merge_sort_out_append_ (&l_out, &l_last, l_remaining); \
419	0	\
420	0	return l_out; \
421	0	}
422
423		/* Merge sort implementation taking the first node of the list to sort,
424		and the comparison function. Returns the first node of the sorted list.
425		Note: use this if you don't care about updating the information in the
426		wrapper. */
427		#define _MERGE_SORT_DEFN_SORT(LTYPE, EXPORT) \
428		EXPORT LTYPE * \
429		LTYPE##_merge_sort_ (LTYPE *node, \
430	0	int (fn_cmp)(const LTYPE , const LTYPE *)) \
431	0	{ \
432	0	if (node == NULL) \
433	0	return NULL; \
434	0	else if (node->next == NULL) \
435	0	return node; \
436	0	\
437	0	LTYPE *left_end = LTYPE##_merge_sort_compute_turtle_ (node); \
438	0	LTYPE *left_begin = node; \
439	0	LTYPE *right_begin = left_end->next; \
440	0	/* break the list. */ \
441	0	left_end->next = NULL; \
442	0	right_begin->prev = NULL; \
443	0	\
444	0	left_begin = LTYPE##_merge_sort_ (left_begin, fn_cmp); \
445	0	right_begin = LTYPE##_merge_sort_ (right_begin, fn_cmp); \
446	0	return LTYPE##_merge_sort_merge_ (left_begin, right_begin, fn_cmp); \
447	0	}
448
449		/* Merge sort wrapper that the end-user should be using as it updates the
450		first and last metadata of the list in wrapper as well.
451		If the user does not want to pay the cost of the update of the data,
452		it can directly use _##LTYPE##_merge_sort_merge. */
453		#define _MERGE_SORT_DEFN_WRAPPER_SORT(LWRAPPERTYPE, LTYPE, EXPORT) \
454		EXPORT void \
455		LTYPE##_merge_sort (LWRAPPERTYPE *wrapper, \
456	0	int (fn_cmp) (const LTYPE , const LTYPE *)) \
457	0	{ \
458	0	wrapper->first = LTYPE##_merge_sort_ (wrapper->first, fn_cmp); \
459	0	\
460	0	if (wrapper->first == NULL \|\| wrapper->first->next == NULL) \
461	0	wrapper->last = wrapper->first; \
462	0	else \
463	0	for (LTYPE *node = wrapper->first; \
464	0	node != NULL; \
465	0	node = node->next) \
466	0	wrapper->last = node; \
467	0	}
468
469		#define LINKED_LIST_MERGE_SORT_DECL(LWRAPPERTYPE, LTYPE, EXPORT) \
470		_MERGE_SORT_IMPL_COMPUTE_TURTLE(LTYPE) \
471		_MERGE_SORT_IMPL_OUT_APPEND(LTYPE) \
472		_MERGE_SORT_IMPL_MERGE(LTYPE) \
473		_MERGE_SORT_DEFN_SORT(LTYPE, EXPORT) \
474		_MERGE_SORT_DEFN_WRAPPER_SORT(LWRAPPERTYPE, LTYPE, EXPORT)
475
476		#endif /* _DOUBLY_LINKED_LIST_H */