[PATCH v3 09/26] libiberty: add common methods for type-sensitive doubly linked lists
Matthieu Longo
matthieu.longo@arm.com
Fri May 9 15:12:59 GMT 2025
More information about the Binutils mailing list
Fri May 9 15:12:59 GMT 2025
- Previous message (by thread): [PATCH v3 08/26] gas/write.c: add explicitly flag SEC_HAS_CONTENT to object attributes section
- Next message (by thread): [PATCH v3 10/26] Object Attributes v2: new abstractions for subsections and attributes
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Those methods's implementation is relying on duck-typing at compile
time.
The structure corresponding to the node of a doubly linked list needs
to define attributes 'prev' and 'next' which are pointers on the type
of a node.
The structure wrapping the nodes and others metadata (first, last, size)
needs to define pointers 'first_', and 'last_' of the node's type, and
an integer type for 'size'.
Mutative methods are bundled together and are declarable once via a
same macro. The merge sort is bundled separately.
There are 3 types of macros:
1. for the declaration of protypes: to use in a header file for a
public declaration, or as a forward declaration in the souce file
for private declaration.
2. for the declaration of the implementation: to use always in a
source file.
3. for the invokation of the functions.
The methods can be declared either public or private via the second
argument of the declaration macros.
List of currently implemented methods:
- LINKED_LIST_*:
- APPEND: insert a node at the end of the list.
- PREPEND: insert a node at the beginning of the list.
- INSERT_BEFORE: insert a node before the given node.
- POP_FRONT: remove the first node of the list.
- POP_BACK: remove the last node of the list.
- REMOVE: remove the given node from the list.
- SWAP: swap the two given nodes in the list.
- LINKED_LIST_MERGE_SORT: a merge sort implementation.
---
include/doubly-linked-list.h | 355 ++++++++++++++++++
libiberty/Makefile.in | 1 +
libiberty/testsuite/Makefile.in | 12 +-
libiberty/testsuite/test-doubly-linked-list.c | 250 ++++++++++++
4 files changed, 617 insertions(+), 1 deletion(-)
create mode 100644 include/doubly-linked-list.h
create mode 100644 libiberty/testsuite/test-doubly-linked-list.c
diff --git a/include/doubly-linked-list.h b/include/doubly-linked-list.h
new file mode 100644
index 00000000000..520a3b0dd3c
--- /dev/null
+++ b/include/doubly-linked-list.h
@@ -0,0 +1,355 @@
+/* Copyright (C) 2025 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
+
+#include <assert.h>
+
+
+/***********************
+ * Mutative operations *
+ ***********************/
+
+#define LINKED_LIST_MUTATIVE_OPS_PROTOTYPE(LWRAPPERTYPE, LTYPE, EXPORT) \
+ EXPORT void \
+ LTYPE##_append (LWRAPPERTYPE *wrapper, LTYPE *new_); \
+ \
+ EXPORT void \
+ LTYPE##_prepend (LWRAPPERTYPE *wrapper, LTYPE *new_); \
+ \
+ EXPORT void \
+ LTYPE##_insert_before (LWRAPPERTYPE *wrapper, \
+ LTYPE *new_, \
+ LTYPE *where); \
+ \
+ EXPORT LTYPE * \
+ LTYPE##_pop_front (LWRAPPERTYPE *wrapper); \
+ \
+ EXPORT LTYPE * \
+ LTYPE##_pop_back (LWRAPPERTYPE *wrapper); \
+ \
+ EXPORT LTYPE * \
+ LTYPE##_remove (LWRAPPERTYPE *wrapper, LTYPE *node); \
+ \
+ EXPORT void \
+ LTYPE##_swap (LWRAPPERTYPE *wrapper, LTYPE *node1, LTYPE *node2)
+
+#define LINKED_LIST_APPEND(LTYPE) LTYPE##_append
+#define LINKED_LIST_PREPEND(LTYPE) LTYPE##_prepend
+#define LINKED_LIST_INSERT_BEFORE(LTYPE) LTYPE##_insert_before
+#define LINKED_LIST_POP_FRONT(LTYPE) LTYPE##_pop_front
+#define LINKED_LIST_POP_BACK(LTYPE) LTYPE##_pop_back
+#define LINKED_LIST_REMOVE(LTYPE) LTYPE##_remove
+#define LINKED_LIST_SWAP(LTYPE) LTYPE##_swap
+
+#define VALUE_SWAP(a, b) do { typeof(a) temp = a; a = b; b = temp; } while (0)
+
+#define LINKED_LIST_MUTATIVE_OPS_DECL(LWRAPPERTYPE, LTYPE, EXPORT) \
+/* Note: all the mutative operations below also update the data in */ \
+/* the wrapper, i.e. first_, last_ and size. */ \
+\
+/* Append the given node new_ to the exising list. */ \
+EXPORT void \
+LTYPE##_append (LWRAPPERTYPE *wrapper, LTYPE *new_) \
+{ \
+ if (wrapper->last_) \
+ { \
+ new_->prev = wrapper->last_; \
+ wrapper->last_->next = new_; \
+ } \
+ else \
+ { \
+ new_->prev = NULL; \
+ wrapper->first_ = new_; \
+ } \
+ wrapper->last_ = new_; \
+ ++wrapper->size; \
+} \
+\
+/* Prepend the given node new_ to the exiting list. */ \
+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_ after 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. */ \
+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. */ \
+EXPORT LTYPE * \
+LTYPE##_pop_front (LWRAPPERTYPE *wrapper) \
+{ \
+ LTYPE *front_node = wrapper->first_; \
+ if (front_node != NULL) \
+ { \
+ wrapper->first_ = front_node->next; \
+ if (front_node->next != NULL) \
+ { \
+ front_node->next->prev = NULL; \
+ front_node->next = NULL; \
+ } \
+ if (wrapper->last_ == front_node) \
+ wrapper->last_ = NULL; \
+ --wrapper->size; \
+ } \
+ return front_node; \
+} \
+\
+/* Pop the last node of the list. */ \
+EXPORT LTYPE * \
+LTYPE##_pop_back (LWRAPPERTYPE *wrapper) \
+{ \
+ LTYPE *back_node = wrapper->last_; \
+ if (back_node != NULL) \
+ { \
+ wrapper->last_ = back_node->prev; \
+ if (back_node->prev != NULL) \
+ { \
+ back_node->prev->next = NULL; \
+ back_node->prev = NULL; \
+ } \
+ if (wrapper->first_ == back_node) \
+ wrapper->first_ = NULL; \
+ --wrapper->size; \
+ } \
+ return back_node; \
+} \
+\
+/* Remove the given node from the existing list, and return the */ \
+/* previous node. */ \
+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; \
+ --wrapper->size; \
+ } \
+ else \
+ LTYPE##_pop_front (wrapper); \
+ \
+ node->next = NULL; \
+ node->prev = NULL; \
+ \
+ return previous; \
+} \
+\
+/* Swap two nodes in a list. */ \
+EXPORT void \
+LTYPE##_swap (LWRAPPERTYPE *wrapper, LTYPE *node1, LTYPE *node2) \
+{ \
+ if (node1->prev != NULL) \
+ node1->prev->next = node2; \
+ if (node2->prev != NULL) \
+ node2->prev->next = node1; \
+ if (node1->next != NULL) \
+ node1->next->prev = node2; \
+ if (node2->next != NULL) \
+ node2->next->prev = node1; \
+ \
+ VALUE_SWAP (node1->next, node2->next); \
+ VALUE_SWAP (node1->prev, node2->prev); \
+ \
+ if (wrapper->first_ == node1) \
+ wrapper->first_ = node2; \
+ else if (wrapper->first_ == node2) \
+ wrapper->first_ = node1; \
+ \
+ if (wrapper->last_ == node1) \
+ wrapper->last_ = node2; \
+ else if (wrapper->last_ == node2) \
+ wrapper->last_ = node1; \
+}
+
+
+/***********
+ * 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 *))
+
+#define LINKED_LIST_MERGE_SORT_DECL(LWRAPPERTYPE, LTYPE, EXPORT) \
+ \
+/* Note: all the functions 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. */ \
+static 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. */ \
+static 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. */ \
+static 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. */ \
+EXPORT LTYPE * \
+_##LTYPE##_merge_sort (LTYPE *node, \
+ int (*fn_cmp)(const LTYPE *, const LTYPE *)) \
+{ \
+ assert (fn_cmp != NULL); \
+ 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. */ \
+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; \
+}
+
+#endif /* _DOUBLY_LINKED_LIST_H */
diff --git a/libiberty/Makefile.in b/libiberty/Makefile.in
index b11df756b4b..1d682e4308e 100644
--- a/libiberty/Makefile.in
+++ b/libiberty/Makefile.in
@@ -236,6 +236,7 @@ CONFIGURED_OFILES = ./asprintf.$(objext) ./atexit.$(objext) \
INSTALLED_HEADERS = \
$(INCDIR)/ansidecl.h \
$(INCDIR)/demangle.h \
+ $(INCDIR)/doubly-linked-list.h \
$(INCDIR)/dyn-string.h \
$(INCDIR)/fibheap.h \
$(INCDIR)/floatformat.h \
diff --git a/libiberty/testsuite/Makefile.in b/libiberty/testsuite/Makefile.in
index 2b0883c7630..ef549ca910a 100644
--- a/libiberty/testsuite/Makefile.in
+++ b/libiberty/testsuite/Makefile.in
@@ -45,7 +45,8 @@ all:
check: @CHECK@
really-check: check-cplus-dem check-d-demangle check-rust-demangle \
- check-pexecute check-expandargv check-strtol
+ check-pexecute check-expandargv check-strtol \
+ check-doubly-linked-list
# Run some tests of the demangler.
check-cplus-dem: test-demangle $(srcdir)/demangle-expected
@@ -69,6 +70,10 @@ check-expandargv: test-expandargv
check-strtol: test-strtol
./test-strtol
+# Check the linked list functionality
+check-doubly-linked-list: test-doubly-linked-list
+ ./test-doubly-linked-list
+
# Run the demangler fuzzer
fuzz-demangler: demangler-fuzzer
./demangler-fuzzer
@@ -90,6 +95,10 @@ test-strtol: $(srcdir)/test-strtol.c ../libiberty.a
$(TEST_COMPILE) -DHAVE_CONFIG_H -I.. -o test-strtol \
$(srcdir)/test-strtol.c ../libiberty.a
+test-doubly-linked-list: $(srcdir)/test-doubly-linked-list.c
+ $(TEST_COMPILE) -DHAVE_CONFIG_H -I.. -o test-doubly-linked-list \
+ $(srcdir)/test-doubly-linked-list.c
+
demangler-fuzzer: $(srcdir)/demangler-fuzzer.c ../libiberty.a
$(TEST_COMPILE) -o demangler-fuzzer \
$(srcdir)/demangler-fuzzer.c ../libiberty.a
@@ -104,6 +113,7 @@ mostlyclean:
rm -f test-pexecute
rm -f test-expandargv
rm -f test-strtol
+ rm -f test-doubly-linked-list
rm -f demangler-fuzzer
rm -f core
clean: mostlyclean
diff --git a/libiberty/testsuite/test-doubly-linked-list.c b/libiberty/testsuite/test-doubly-linked-list.c
new file mode 100644
index 00000000000..821ac4d9b18
--- /dev/null
+++ b/libiberty/testsuite/test-doubly-linked-list.c
@@ -0,0 +1,250 @@
+#include <stdbool.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+#include "doubly-linked-list.h"
+
+#ifndef EXIT_SUCCESS
+#define EXIT_SUCCESS 0
+#endif
+
+#ifndef EXIT_FAILURE
+#define EXIT_FAILURE 1
+#endif
+
+/* Implementation */
+
+typedef int T;
+
+typedef struct ListNodeType
+{
+ T value;
+ struct ListNodeType *next;
+ struct ListNodeType *prev;
+} ListNodeType;
+
+ListNodeType * l_new_node (T value)
+{
+ ListNodeType *n = malloc (sizeof (ListNodeType));
+ n->next = NULL;
+ n->prev = NULL;
+ n->value = value;
+ return n;
+}
+
+typedef struct LinkedListWrapperType
+{
+ ListNodeType *first_;
+ ListNodeType *last_;
+ size_t size;
+} LinkedListWrapperType;
+
+int compare_nodes (const ListNodeType *n1, const ListNodeType *n2)
+{
+ if (n1->value == n2->value)
+ return 0;
+ else if (n1->value < n2->value)
+ return -1;
+ else
+ return 1;
+}
+
+LINKED_LIST_MUTATIVE_OPS_DECL (LinkedListWrapperType, ListNodeType, static)
+LINKED_LIST_MERGE_SORT_DECL (LinkedListWrapperType, ListNodeType, static)
+
+ListNodeType * find_last_node (ListNodeType *head)
+{
+ if (head == NULL)
+ return NULL;
+
+ ListNodeType *n = head;
+ while (n->next != NULL)
+ n = n->next;
+
+ return n;
+}
+
+void l_print (ListNodeType *node)
+{
+ for (ListNodeType *l = node; l != NULL; l = l->next)
+ printf ("%d ", l->value);
+ printf ("\n");
+}
+
+void l_reverse_print (ListNodeType *last_node)
+{
+ for (ListNodeType *l = last_node; l != NULL; l = l->prev)
+ printf ("%d ", l->value);
+ printf ("\n");
+}
+
+struct test_data_t
+{
+ T const *content;
+ size_t size;
+};
+
+bool run_test (const struct test_data_t *expect,
+ LinkedListWrapperType *current,
+ bool reversed)
+{
+ ListNodeType *node = (reversed) ? current->last_ : current->first_;
+ bool passed = true;
+ for (int i=0; i<expect->size && node != NULL; ++i)
+ {
+ if (reversed)
+ {
+ if (expect->content[expect->size - 1 - i] != node->value)
+ {
+ printf ("FAIL: mismatching expected (%d) VS current (%d).\n",
+ expect->content[expect->size - 1 - i], node->value);
+ passed = false;
+ }
+ if (node->prev == NULL && current->first_ != node)
+ {
+ printf ("FAIL: first_ is not matching the first node.\n");
+ passed = false;
+ }
+ }
+ else
+ {
+ if (expect->content[i] != node->value)
+ {
+ printf ("FAIL: mismatching expected (%d) VS current (%d).\n",
+ expect->content[i], node->value);
+ passed = false;
+ }
+ if (node->next == NULL && current->last_ != node)
+ {
+ printf ("FAIL: last_ is not matching the last node.\n");
+ passed = false;
+ }
+ }
+
+ if (!passed)
+ return false;
+
+ if (reversed)
+ node = node->prev;
+ else
+ node = node->next;
+ }
+
+ if (node != NULL)
+ {
+ printf ("FAIL: the list is longer than expected.\n");
+ passed = false;
+ }
+ if (expect->size != current->size)
+ {
+ printf ("FAIL: size (%d) is not matching the real size of the list (%d).\n",
+ current->size, expect->size);
+ passed = false;
+ }
+
+ return passed;
+}
+
+bool check(const char *op,
+ const struct test_data_t *expect,
+ LinkedListWrapperType *wrapper)
+{
+ bool success = true;
+ bool res;
+
+ l_print (wrapper->first_);
+ res = run_test (expect, wrapper, false);
+ printf ("%s: test-linked-list::%s: check forward conformity\n",
+ res ? "PASS": "FAIL", op);
+ success &= res;
+
+ l_reverse_print (wrapper->last_);
+ res = run_test (expect, wrapper, true);
+ printf ("%s: test-linked-list::%s: check backward conformity\n",
+ res ? "PASS": "FAIL", op);
+ success &= res;
+
+ return success;
+}
+
+const int EXPECT_0 [] = { 10, 4, 3, 1, 9, 2 };
+const int EXPECT_1 [] = { 1, 2, 3, 4, 9, 10 };
+const int EXPECT_2 [] = { 11, 1, 2, 3, 4, 9, 10 };
+const int EXPECT_3 [] = { 11, 1, 2, 3, 4, 9, 8, 10 };
+const int EXPECT_4 [] = { 11, 2, 3, 4, 9, 8, 10 };
+const int EXPECT_5 [] = { 10, 2, 3, 4, 9, 8, 11 };
+const int EXPECT_6 [] = { 2, 3, 4, 8, 9, 10, 11 };
+const int EXPECT_7 [] = { 3, 4, 8, 9, 10, 11 };
+const int EXPECT_8 [] = { 3, 4, 8, 9, 10 };
+const struct test_data_t test_data[] = {
+ { .content = EXPECT_0, .size = sizeof(EXPECT_0) / sizeof(EXPECT_0[0]) },
+ { .content = EXPECT_1, .size = sizeof(EXPECT_1) / sizeof(EXPECT_1[0]) },
+ { .content = EXPECT_2, .size = sizeof(EXPECT_2) / sizeof(EXPECT_2[0]) },
+ { .content = EXPECT_3, .size = sizeof(EXPECT_3) / sizeof(EXPECT_3[0]) },
+ { .content = EXPECT_4, .size = sizeof(EXPECT_4) / sizeof(EXPECT_4[0]) },
+ { .content = EXPECT_5, .size = sizeof(EXPECT_5) / sizeof(EXPECT_5[0]) },
+ { .content = EXPECT_6, .size = sizeof(EXPECT_6) / sizeof(EXPECT_6[0]) },
+ { .content = EXPECT_7, .size = sizeof(EXPECT_7) / sizeof(EXPECT_7[0]) },
+ { .content = EXPECT_8, .size = sizeof(EXPECT_8) / sizeof(EXPECT_8[0]) },
+};
+
+int main (void)
+{
+ int failures = 0;
+
+ LinkedListWrapperType wrapper = {
+ .first_ = NULL,
+ .last_ = NULL,
+ .size = 0,
+ };
+
+ /* Append nodes. */
+ LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (10));
+ LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (4));
+ LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (3));
+ LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (1));
+ LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (9));
+ LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (2));
+
+ failures += ! check ("append", &test_data[0], &wrapper);
+
+ /* Sort nodes (without updating wrapper). */
+ wrapper.first_ =
+ _LINKED_LIST_MERGE_SORT(ListNodeType) (wrapper.first_, compare_nodes);
+ wrapper.last_ = find_last_node (wrapper.first_);
+
+ failures += ! check ("sort", &test_data[1], &wrapper);
+
+ /* Save a reference to this node for later. */
+ ListNodeType *n_to_remove = wrapper.first_;
+
+ /* Prepend node. */
+ LINKED_LIST_PREPEND(ListNodeType) (&wrapper, l_new_node (11));
+ failures += ! check ("prepend", &test_data[2], &wrapper);
+
+ /* Insert node. */
+ LINKED_LIST_INSERT_BEFORE(ListNodeType) (&wrapper, l_new_node (8), wrapper.last_);
+ failures += ! check ("insert_before", &test_data[3], &wrapper);
+
+ /* Remove a node. */
+ LINKED_LIST_REMOVE(ListNodeType) (&wrapper, n_to_remove);
+ failures += ! check ("remove", &test_data[4], &wrapper);
+
+ /* Swap first and last. */
+ LINKED_LIST_SWAP(ListNodeType) (&wrapper, wrapper.first_, wrapper.last_);
+ failures += ! check ("swap", &test_data[5], &wrapper);
+
+ /* Sort nodes. */
+ LINKED_LIST_MERGE_SORT(ListNodeType) (&wrapper, compare_nodes);
+ failures += ! check ("sort", &test_data[6], &wrapper);
+
+ /* Pop front. */
+ LINKED_LIST_POP_FRONT(ListNodeType) (&wrapper);
+ failures += ! check ("pop_front", &test_data[7], &wrapper);
+
+ /* Pop back. */
+ LINKED_LIST_POP_BACK(ListNodeType) (&wrapper);
+ failures += ! check ("pop_back", &test_data[8], &wrapper);
+
+ exit (failures ? EXIT_FAILURE : EXIT_SUCCESS);
+}
--
2.49.0
- Previous message (by thread): [PATCH v3 08/26] gas/write.c: add explicitly flag SEC_HAS_CONTENT to object attributes section
- Next message (by thread): [PATCH v3 10/26] Object Attributes v2: new abstractions for subsections and attributes
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
More information about the Binutils mailing list