diff options
Diffstat (limited to 'Build/source/texk/dvisvgm/dvisvgm-src/libs/potrace/lists.h')
-rw-r--r-- | Build/source/texk/dvisvgm/dvisvgm-src/libs/potrace/lists.h | 285 |
1 files changed, 0 insertions, 285 deletions
diff --git a/Build/source/texk/dvisvgm/dvisvgm-src/libs/potrace/lists.h b/Build/source/texk/dvisvgm/dvisvgm-src/libs/potrace/lists.h deleted file mode 100644 index 507cf15bdfb..00000000000 --- a/Build/source/texk/dvisvgm/dvisvgm-src/libs/potrace/lists.h +++ /dev/null @@ -1,285 +0,0 @@ -/* 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 */ - |