summaryrefslogtreecommitdiff
path: root/Build/source/texk/web2c/mfluadir/potrace/lists.h
diff options
context:
space:
mode:
authorLuigi Scarso <luigi.scarso@gmail.com>2022-02-12 18:02:57 +0000
committerLuigi Scarso <luigi.scarso@gmail.com>2022-02-12 18:02:57 +0000
commit0f358457f0c576c1ee06d77e82a077bc7b614cde (patch)
tree64a9dbefd8ea2b03203c514efc244d9aa39dd32e /Build/source/texk/web2c/mfluadir/potrace/lists.h
parent1f23f86e92f5e59c1b12b056b39a410b611c2dc8 (diff)
Updated MFLua.
git-svn-id: svn://tug.org/texlive/trunk@61986 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Build/source/texk/web2c/mfluadir/potrace/lists.h')
-rw-r--r--Build/source/texk/web2c/mfluadir/potrace/lists.h285
1 files changed, 285 insertions, 0 deletions
diff --git a/Build/source/texk/web2c/mfluadir/potrace/lists.h b/Build/source/texk/web2c/mfluadir/potrace/lists.h
new file mode 100644
index 00000000000..507cf15bdfb
--- /dev/null
+++ b/Build/source/texk/web2c/mfluadir/potrace/lists.h
@@ -0,0 +1,285 @@
+/* Copyright (C) 2001-2019 Peter Selinger.
+ This file is part of Potrace. It is free software and it is covered
+ by the GNU General Public License. See the file COPYING for details. */
+
+
+#ifndef _PS_LISTS_H
+#define _PS_LISTS_H
+
+/* here we define some general list macros. Because they are macros,
+ they should work on any datatype with a "->next" component. Some of
+ them use a "hook". If elt and list are of type t* then hook is of
+ type t**. A hook stands for an insertion point in the list, i.e.,
+ either before the first element, or between two elements, or after
+ the last element. If an operation "sets the hook" for an element,
+ then the hook is set to just before the element. One can insert
+ something at a hook. One can also unlink at a hook: this means,
+ unlink the element just after the hook. By "to unlink", we mean the
+ element is removed from the list, but not deleted. Thus, it and its
+ components still need to be freed. */
+
+/* Note: these macros are somewhat experimental. Only the ones that
+ are actually *used* have been tested. So be careful to test any
+ that you use. Looking at the output of the preprocessor, "gcc -E"
+ (possibly piped though "indent"), might help too. Also: these
+ macros define some internal (local) variables that start with
+ "_". */
+
+/* we enclose macro definitions whose body consists of more than one
+ statement in MACRO_BEGIN and MACRO_END, rather than '{' and '}'. The
+ reason is that we want to be able to use the macro in a context
+ such as "if (...) macro(...); else ...". If we didn't use this obscure
+ trick, we'd have to omit the ";" in such cases. */
+
+#define MACRO_BEGIN do {
+#define MACRO_END } while (0)
+
+/* ---------------------------------------------------------------------- */
+/* macros for singly-linked lists */
+
+/* traverse list. At the end, elt is set to NULL. */
+#define list_forall(elt, list) for (elt=list; elt!=NULL; elt=elt->next)
+
+/* set elt to the first element of list satisfying boolean condition
+ c, or NULL if not found */
+#define list_find(elt, list, c) \
+ MACRO_BEGIN list_forall(elt, list) if (c) break; MACRO_END
+
+/* like forall, except also set hook for elt. */
+#define list_forall2(elt, list, hook) \
+ for (elt=list, hook=&list; elt!=NULL; hook=&elt->next, elt=elt->next)
+
+/* same as list_find, except also set hook for elt. */
+#define list_find2(elt, list, c, hook) \
+ MACRO_BEGIN list_forall2(elt, list, hook) if (c) break; MACRO_END
+
+/* same, except only use hook. */
+#define _list_forall_hook(list, hook) \
+ for (hook=&list; *hook!=NULL; hook=&(*hook)->next)
+
+/* same, except only use hook. Note: c may only refer to *hook, not elt. */
+#define _list_find_hook(list, c, hook) \
+ MACRO_BEGIN _list_forall_hook(list, hook) if (c) break; MACRO_END
+
+/* insert element after hook */
+#define list_insert_athook(elt, hook) \
+ MACRO_BEGIN elt->next = *hook; *hook = elt; MACRO_END
+
+/* insert element before hook */
+#define list_insert_beforehook(elt, hook) \
+ MACRO_BEGIN elt->next = *hook; *hook = elt; hook=&elt->next; MACRO_END
+
+/* unlink element after hook, let elt be unlinked element, or NULL.
+ hook remains. */
+#define list_unlink_athook(list, elt, hook) \
+ MACRO_BEGIN \
+ elt = hook ? *hook : NULL; if (elt) { *hook = elt->next; elt->next = NULL; }\
+ MACRO_END
+
+/* unlink the specific element, if it is in the list. Otherwise, set
+ elt to NULL */
+#define list_unlink(listtype, list, elt) \
+ MACRO_BEGIN \
+ listtype **_hook; \
+ _list_find_hook(list, *_hook==elt, _hook); \
+ list_unlink_athook(list, elt, _hook); \
+ MACRO_END
+
+/* prepend elt to list */
+#define list_prepend(list, elt) \
+ MACRO_BEGIN elt->next = list; list = elt; MACRO_END
+
+/* append elt to list. */
+#define list_append(listtype, list, elt) \
+ MACRO_BEGIN \
+ listtype **_hook; \
+ _list_forall_hook(list, _hook) {} \
+ list_insert_athook(elt, _hook); \
+ MACRO_END
+
+/* unlink the first element that satisfies the condition. */
+#define list_unlink_cond(listtype, list, elt, c) \
+ MACRO_BEGIN \
+ listtype **_hook; \
+ list_find2(elt, list, c, _hook); \
+ list_unlink_athook(list, elt, _hook); \
+ MACRO_END
+
+/* let elt be the nth element of the list, starting to count from 0.
+ Return NULL if out of bounds. */
+#define list_nth(elt, list, n) \
+ MACRO_BEGIN \
+ int _x; /* only evaluate n once */ \
+ for (_x=(n), elt=list; _x && elt; _x--, elt=elt->next) {} \
+ MACRO_END
+
+/* let elt be the nth element of the list, starting to count from 0.
+ Return NULL if out of bounds. */
+#define list_nth_hook(elt, list, n, hook) \
+ MACRO_BEGIN \
+ int _x; /* only evaluate n once */ \
+ for (_x=(n), elt=list, hook=&list; _x && elt; _x--, hook=&elt->next, elt=elt->next) {} \
+ MACRO_END
+
+/* set n to the length of the list */
+#define list_length(listtype, list, n) \
+ MACRO_BEGIN \
+ listtype *_elt; \
+ n=0; \
+ list_forall(_elt, list) \
+ n++; \
+ MACRO_END
+
+/* set n to the index of the first element satisfying cond, or -1 if
+ none found. Also set elt to the element, or NULL if none found. */
+#define list_index(list, n, elt, c) \
+ MACRO_BEGIN \
+ n=0; \
+ list_forall(elt, list) { \
+ if (c) break; \
+ n++; \
+ } \
+ if (!elt) \
+ n=-1; \
+ MACRO_END
+
+/* set n to the number of elements in the list that satisfy condition c */
+#define list_count(list, n, elt, c) \
+ MACRO_BEGIN \
+ n=0; \
+ list_forall(elt, list) { \
+ if (c) n++; \
+ } \
+ MACRO_END
+
+/* let elt be each element of the list, unlinked. At the end, set list=NULL. */
+#define list_forall_unlink(elt, list) \
+ for (elt=list; elt ? (list=elt->next, elt->next=NULL), 1 : 0; elt=list)
+
+/* reverse a list (efficient) */
+#define list_reverse(listtype, list) \
+ MACRO_BEGIN \
+ listtype *_list1=NULL, *elt; \
+ list_forall_unlink(elt, list) \
+ list_prepend(_list1, elt); \
+ list = _list1; \
+ MACRO_END
+
+/* insert the element ELT just before the first element TMP of the
+ list for which COND holds. Here COND must be a condition of ELT and
+ TMP. Typical usage is to insert an element into an ordered list:
+ for instance, list_insert_ordered(listtype, list, elt, tmp,
+ elt->size <= tmp->size). Note: if we give a "less than or equal"
+ condition, the new element will be inserted just before a sequence
+ of equal elements. If we give a "less than" condition, the new
+ element will be inserted just after a list of equal elements.
+ Note: it is much more efficient to construct a list with
+ list_prepend and then order it with list_merge_sort, than to
+ construct it with list_insert_ordered. */
+#define list_insert_ordered(listtype, list, elt, tmp, cond) \
+ MACRO_BEGIN \
+ listtype **_hook; \
+ _list_find_hook(list, (tmp=*_hook, (cond)), _hook); \
+ list_insert_athook(elt, _hook); \
+ MACRO_END
+
+/* sort the given list, according to the comparison condition.
+ Typical usage is list_sort(listtype, list, a, b, a->size <
+ b->size). Note: if we give "less than or equal" condition, each
+ segment of equal elements will be reversed in order. If we give a
+ "less than" condition, each segment of equal elements will retain
+ the original order. The latter is slower but sometimes
+ prettier. Average running time: n*n/2. */
+#define list_sort(listtype, list, a, b, cond) \
+ MACRO_BEGIN \
+ listtype *_newlist=NULL; \
+ list_forall_unlink(a, list) \
+ list_insert_ordered(listtype, _newlist, a, b, cond); \
+ list = _newlist; \
+ MACRO_END
+
+/* a much faster sort algorithm (merge sort, n log n worst case). It
+ is required that the list type has an additional, unused next1
+ component. Note there is no curious reversal of order of equal
+ elements as for list_sort. */
+
+#define list_mergesort(listtype, list, a, b, cond) \
+ MACRO_BEGIN \
+ listtype *_elt, **_hook1; \
+ \
+ for (_elt=list; _elt; _elt=_elt->next1) { \
+ _elt->next1 = _elt->next; \
+ _elt->next = NULL; \
+ } \
+ do { \
+ _hook1 = &(list); \
+ while ((a = *_hook1) != NULL && (b = a->next1) != NULL ) { \
+ _elt = b->next1; \
+ _list_merge_cond(listtype, a, b, cond, *_hook1); \
+ _hook1 = &((*_hook1)->next1); \
+ *_hook1 = _elt; \
+ } \
+ } while (_hook1 != &(list)); \
+ MACRO_END
+
+/* merge two sorted lists. Store result at &result */
+#define _list_merge_cond(listtype, a, b, cond, result) \
+ MACRO_BEGIN \
+ listtype **_hook; \
+ _hook = &(result); \
+ while (1) { \
+ if (a==NULL) { \
+ *_hook = b; \
+ break; \
+ } else if (b==NULL) { \
+ *_hook = a; \
+ break; \
+ } else if (cond) { \
+ *_hook = a; \
+ _hook = &(a->next); \
+ a = a->next; \
+ } else { \
+ *_hook = b; \
+ _hook = &(b->next); \
+ b = b->next; \
+ } \
+ } \
+ MACRO_END
+
+/* ---------------------------------------------------------------------- */
+/* macros for doubly-linked lists */
+
+#define dlist_append(head, end, elt) \
+ MACRO_BEGIN \
+ elt->prev = end; \
+ elt->next = NULL; \
+ if (end) { \
+ end->next = elt; \
+ } else { \
+ head = elt; \
+ } \
+ end = elt; \
+ MACRO_END
+
+/* let elt be each element of the list, unlinked. At the end, set list=NULL. */
+#define dlist_forall_unlink(elt, head, end) \
+ for (elt=head; elt ? (head=elt->next, elt->next=NULL, elt->prev=NULL), 1 : (end=NULL, 0); elt=head)
+
+/* unlink the first element of the list */
+#define dlist_unlink_first(head, end, elt) \
+ MACRO_BEGIN \
+ elt = head; \
+ if (head) { \
+ head = head->next; \
+ if (head) { \
+ head->prev = NULL; \
+ } else { \
+ end = NULL; \
+ } \
+ elt->prev = NULL; \
+ elt->next = NULL; \
+ } \
+ MACRO_END
+
+#endif /* _PS_LISTS_H */
+