lists.h File Reference

Here we define some general list macros. More...

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Defines
#define	MACRO_BEGIN   do {
	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_END   } while (0)
#define	list_forall(elt, list)   for (elt=list; elt!=NULL; elt=elt->next)
	Traverse list. At the end, elt is set to NULL.
#define	list_find(elt, list, c)   MACRO_BEGIN list_forall(elt, list) if (c) break; MACRO_END
	Set elt to the first element of list satisfying boolean condition c, or NULL if not found.
#define	list_forall2(elt, list, hook)   for (elt=list, hook=&list; elt!=NULL; hook=&elt->next, elt=elt->next)
	Like forall, 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 as list_find, except also set hook for elt.
#define	_list_forall_hook(list, hook)   for (hook=&list; *hook!=NULL; hook=&(*hook)->next)
	Same, except only use hook.
#define	_list_find_hook(list, c, hook)   MACRO_BEGIN _list_forall_hook(list, hook) if (c) break; MACRO_END
	Same, except only use hook.
#define	list_insert_athook(elt, hook)   MACRO_BEGIN elt->next = *hook; *hook = elt; MACRO_END
	Insert element after hook.
#define	list_insert_beforehook(elt, hook)   MACRO_BEGIN elt->next = *hook; *hook = elt; hook=&elt->next; MACRO_END
	Insert element before hook.
#define	list_unlink_athook(list, elt, hook)
	Unlink element after hook, let elt be unlinked element, or NULL. hook remains.
#define	list_unlink(listtype, list, elt)
	Unlink the specific element, if it is in the list. Otherwise, set elt to NULL.
#define	list_prepend(list, elt)   MACRO_BEGIN elt->next = list; list = elt; MACRO_END
	Prepend elt to list.
#define	list_append(listtype, list, elt)
	Append elt to list.
#define	list_unlink_cond(listtype, list, elt, c)
	Unlink the first element that satisfies the condition.
#define	list_nth(elt, list, n)
	Let elt be the nth element of the list, starting to count from 0.
#define	list_nth_hook(elt, list, n, hook)
	Let elt be the nth element of the list, starting to count from 0.
#define	list_length(listtype, list, n)
	Set n to the length of the list.
#define	list_index(list, n, elt, c)
	Set n to the index of the first element satisfying cond, or -1 if none found.
#define	list_count(list, n, elt, c)
	Set n to the number of elements in the list that satisfy condition c.
#define	list_forall_unlink(elt, list)   for (elt=list; elt ? (list=elt->next, elt->next=NULL), 1 : 0; elt=list)
	Let elt be each element of the list, unlinked.
#define	list_reverse(listtype, list)
	Reverse a list (efficient).
#define	list_insert_ordered(listtype, list, elt, tmp, cond)
	Insert the element ELT just before the first element TMP of the list for which COND holds.
#define	list_sort(listtype, list, a, b, cond)
	Sort the given list, according to the comparison condition.
#define	list_mergesort(listtype, list, a, b, cond)
	A much faster sort algorithm (merge sort, n log n worst case).
#define	_list_merge_cond(listtype, a, b, cond, result)
	Merge two sorted lists.
#define	dlist_append(head, end, elt)
#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)
	Let elt be each element of the list, unlinked.
#define	dlist_unlink_first(head, end, elt)
	Unlink the first element of the list.

---

Detailed Description

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 "_".

---

Copyright.

PCB, interactive printed circuit board design

Copyright (C) 2001-2007 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.

Definition in file lists.h.

---

Define Documentation

#define _list_find_hook	(		list,
			c,
			hook
	)		MACRO_BEGIN _list_forall_hook(list, hook) if (c) break; MACRO_END

Same, except only use hook.

Note:

c may only refer to *hook, not elt.

Definition at line 87 of file lists.h.

#define _list_forall_hook	(		list,
			hook
	)		for (hook=&list; *hook!=NULL; hook=&(*hook)->next)

Same, except only use hook.

Definition at line 79 of file lists.h.

#define _list_merge_cond	(		listtype,
			a,
			b,
			cond,
			result
	)

Value:

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

Merge two sorted lists.

Store result at &result.

Definition at line 308 of file lists.h.

#define dlist_append	(		head,
			end,
			elt
	)

Value:

MACRO_BEGIN                                              \
  elt->prev = end;                                       \
  elt->next = NULL;                                      \
  if (end) {                                             \
    end->next = elt;                                     \
  } else {                                               \
    head = elt;                                          \
  }                                                      \
  end = elt;                                             \
  MACRO_END

Definition at line 334 of file lists.h.

#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)

Let elt be each element of the list, unlinked.

At the end, set list=NULL.

Definition at line 351 of file lists.h.

#define dlist_unlink_first	(		head,
			end,
			elt
	)

Value:

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

Unlink the first element of the list.

Definition at line 357 of file lists.h.

#define list_append	(		listtype,
			list,
			elt
	)

Value:

MACRO_BEGIN                                \
  listtype **_hook;                          \
  _list_forall_hook(list, _hook) {}          \
  list_insert_athook(elt, _hook);            \
  MACRO_END

Append elt to list.

Definition at line 131 of file lists.h.

Referenced by pathlist_to_tree().

#define list_count	(		list,
			n,
			elt,
			c
	)

Value:

MACRO_BEGIN                                              \
  n=0;                                                   \
  list_forall(elt, list) {                               \
    if (c) n++;                                          \
  }                                                      \
  MACRO_END

Set n to the number of elements in the list that satisfy condition c.

Definition at line 204 of file lists.h.

#define list_find	(		elt,
			list,
			c
	)		MACRO_BEGIN list_forall(elt, list) if (c) break; MACRO_END

Set elt to the first element of list satisfying boolean condition c, or NULL if not found.

Definition at line 61 of file lists.h.

#define list_find2	(		elt,
			list,
			c,
			hook
	)		MACRO_BEGIN list_forall2(elt, list, hook) if (c) break; MACRO_END

Same as list_find, except also set hook for elt.

Definition at line 73 of file lists.h.

#define list_forall	(		elt,
			list
	)		for (elt=list; elt!=NULL; elt=elt->next)

Traverse list. At the end, elt is set to NULL.

Definition at line 56 of file lists.h.

Referenced by pathlist_to_tree(), and process_path().

#define list_forall2	(		elt,
			list,
			hook
	)		for (elt=list, hook=&list; elt!=NULL; hook=&elt->next, elt=elt->next)

Like forall, except also set hook for elt.

Definition at line 67 of file lists.h.

#define list_forall_unlink	(		elt,
			list
	)		for (elt=list; elt ? (list=elt->next, elt->next=NULL), 1 : 0; elt=list)

Let elt be each element of the list, unlinked.

At the end, set list=NULL.

Definition at line 217 of file lists.h.

Referenced by bm_to_pathlist(), pathlist_free(), and pathlist_to_tree().

#define list_index	(		list,
			n,
			elt,
			c
	)

Value:

MACRO_BEGIN                                              \
  n=0;                                                   \
  list_forall(elt, list) {                               \
    if (c) break;                                        \
    n++;                                                 \
  }                                                      \
  if (!elt)                                              \
    n=-1;                                                \
  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.

Definition at line 189 of file lists.h.

#define list_insert_athook	(		elt,
			hook
	)		MACRO_BEGIN elt->next = *hook; *hook = elt; MACRO_END

Insert element after hook.

Definition at line 93 of file lists.h.

#define list_insert_beforehook	(		elt,
			hook
	)		MACRO_BEGIN elt->next = *hook; *hook = elt; hook=&elt->next; MACRO_END

Insert element before hook.

Definition at line 99 of file lists.h.

Referenced by bm_to_pathlist(), and pathlist_to_tree().

#define list_insert_ordered	(		listtype,
			list,
			elt,
			tmp,
			cond
	)

Value:

MACRO_BEGIN                                               \
  listtype **_hook;                                         \
  _list_find_hook(list, (tmp=*_hook, (cond)), _hook);       \
  list_insert_athook(elt, _hook);                           \
  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.

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.

Definition at line 249 of file lists.h.

#define list_length	(		listtype,
			list,
			n
	)

Value:

MACRO_BEGIN                                              \
  listtype *_elt;                                        \
  n=0;                                                   \
  list_forall(_elt, list)                                \
    n++;                                                 \
  MACRO_END

Set n to the length of the list.

Definition at line 175 of file lists.h.

#define list_mergesort	(		listtype,
			list,
			a,
			b,
			cond
	)

Value:

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

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.

Definition at line 284 of file lists.h.

#define list_nth	(		elt,
			list,
			n
	)

Value:

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.

Returns:

NULL if out of bounds.

Definition at line 154 of file lists.h.

#define list_nth_hook	(		elt,
			list,
			n,
			hook
	)

Value:

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

Let elt be the nth element of the list, starting to count from 0.

Returns:

NULL if out of bounds.

Definition at line 166 of file lists.h.

#define list_prepend	(		list,
			elt
	)		MACRO_BEGIN elt->next = list; list = elt; MACRO_END

Prepend elt to list.

Definition at line 125 of file lists.h.

#define list_reverse	(		listtype,
			list
	)

Value:

MACRO_BEGIN                                     \
  listtype *_list1=NULL, *elt;                  \
  list_forall_unlink(elt, list)                 \
    list_prepend(_list1, elt);                  \
  list = _list1;                                \
  MACRO_END

Reverse a list (efficient).

Definition at line 223 of file lists.h.

#define list_sort	(		listtype,
			list,
			a,
			b,
			cond
	)

Value:

MACRO_BEGIN                                            \
  listtype *_newlist=NULL;                               \
  list_forall_unlink(a, list)                            \
    list_insert_ordered(listtype, _newlist, a, b, cond); \
  list = _newlist;                                       \
  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.

Definition at line 267 of file lists.h.

#define list_unlink	(		listtype,
			list,
			elt
	)

Value:

MACRO_BEGIN                                   \
  listtype **_hook;                           \
  _list_find_hook(list, *_hook==elt, _hook);  \
  list_unlink_athook(list, elt, _hook);       \
  MACRO_END

Unlink the specific element, if it is in the list. Otherwise, set elt to NULL.

Definition at line 115 of file lists.h.

#define list_unlink_athook	(		list,
			elt,
			hook
	)

Value:

MACRO_BEGIN \
  elt = hook ? *hook : NULL; if (elt) { *hook = elt->next; elt->next = NULL; }\
  MACRO_END

Unlink element after hook, let elt be unlinked element, or NULL. hook remains.

Definition at line 106 of file lists.h.

#define list_unlink_cond	(		listtype,
			list,
			elt,
			c
	)

Value:

MACRO_BEGIN                                        \
  listtype **_hook;                                  \
  list_find2(elt, list, c, _hook);                   \
  list_unlink_athook(list, elt, _hook);              \
  MACRO_END

Unlink the first element that satisfies the condition.

Definition at line 141 of file lists.h.

#define MACRO_BEGIN   do {

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.

Definition at line 48 of file lists.h.

#define MACRO_END   } while (0)

Definition at line 49 of file lists.h.