+/*---------------------- list traversal macros -------------------------*/
+
+/* Note: These macros are for traversing through a list in some format,
+ and executing code that you specify on each member of the list.
+
+ There are two kinds of macros, those requiring surrounding braces, and
+ those not requiring this. Which type of macro will be indicated.
+ The general format for using a brace-requiring macro is
+
+ {
+ LIST_LOOP_3 (elt, list, tail)
+ execute_code_here;
+ }
+
+ or
+
+ {
+ LIST_LOOP_3 (elt, list, tail)
+ {
+ execute_code_here;
+ }
+ }
+
+ You can put variable declarations between the brace and beginning of
+ macro, but NOTHING ELSE.
+
+ The brace-requiring macros typically declare themselves any arguments
+ that are initialized and iterated by the macros. If for some reason
+ you need to declare these arguments yourself (e.g. to do something on
+ them before the iteration starts, use the _NO_DECLARE versions of the
+ macros.)
+*/
+
+/* There are two basic kinds of macros: those that handle "internal" lists
+ that are known to be correctly structured (i.e. first element is a cons
+ or nil, and the car of each cons is also a cons or nil, and there are
+ no circularities), and those that handle "external" lists, where the
+ list may have any sort of invalid formation. This is reflected in
+ the names: those with "EXTERNAL_" work with external lists, and those
+ without this prefix work with internal lists. The internal-list
+ macros will hit an assertion failure if the structure is ill-formed;
+ the external-list macros will signal an error in this case, either a
+ malformed-list error or a circular-list error.
+
+ Note also that the simplest external list iterator, EXTERNAL_LIST_LOOP,
+ does *NOT* check for circularities. Therefore, make sure you call
+ QUIT each iteration or so. However, it's probably easier just to use
+ EXTERNAL_LIST_LOOP_2, which is easier to use in any case.
+*/
+
+/* LIST_LOOP and EXTERNAL_LIST_LOOP are the simplest macros. They don't
+ require brace surrounding, and iterate through a list, which may or may
+ not known to be syntactically correct. EXTERNAL_LIST_LOOP is for those
+ not known to be correct, and it detects and signals a malformed list
+ error when encountering a problem. Circularities, however, are not
+ handled, and cause looping forever, so make sure to include a QUIT.
+ These functions also accept two args, TAIL (set progressively to each
+ cons starting with the first), and LIST, the list to iterate over.
+ TAIL needs to be defined by the program.
+
+ In each iteration, you can retrieve the current list item using XCAR
+ (tail), or destructively modify the list using XSETCAR (tail,
+ ...). */
+
+#define LIST_LOOP(tail, list) \
+ for (tail = list; \
+ !NILP (tail); \
+ tail = XCDR (tail))
+
+#define EXTERNAL_LIST_LOOP(tail, list) \
+ for (tail = list; !NILP (tail); tail = XCDR (tail)) \
+ if (!CONSP (tail)) \
+ signal_malformed_list_error (list); \
+ else
+
+/* The following macros are the "core" macros for list traversal.
+
+ *** ALL OF THESE MACROS MUST BE DECLARED INSIDE BRACES -- SEE ABOVE. ***
+
+ LIST_LOOP_2 and EXTERNAL_LIST_LOOP_2 are the standard, most-often used
+ macros. They take two arguments, an element variable ELT and the list
+ LIST. ELT is automatically declared, and set to each element in turn
+ from LIST.
+
+ LIST_LOOP_3 and EXTERNAL_LIST_LOOP_3 are the same, but they have a third
+ argument TAIL, another automatically-declared variable. At each iteration,
+ this one points to the cons cell for which ELT is the car.
+
+ EXTERNAL_LIST_LOOP_4 is like EXTERNAL_LIST_LOOP_3 but takes an additional
+ LEN argument, again automatically declared, which counts the number of
+ iterations gone by. It is 0 during the first iteration.
+
+ EXTERNAL_LIST_LOOP_4_NO_DECLARE is like EXTERNAL_LIST_LOOP_4 but none
+ of the variables are automatically declared, and so you need to declare
+ them yourself. (ELT and TAIL are Lisp_Objects, and LEN is an EMACS_INT.)
+*/
+
+#define LIST_LOOP_2(elt, list) \
+ LIST_LOOP_3(elt, list, unused_tail_##elt)
+
+#define LIST_LOOP_3(elt, list, tail) \
+ Lisp_Object elt, tail; \
+ for (tail = list; \
+ NILP (tail) ? \
+ 0 : (elt = XCAR (tail), 1); \
+ tail = XCDR (tail))
+
+/* The following macros are for traversing lisp lists.
+ Signal an error if LIST is not properly acyclic and nil-terminated.
+
+ Use tortoise/hare algorithm to check for cycles, but only if it
+ looks like the list is getting too long. Not only is the hare
+ faster than the tortoise; it even gets a head start! */
+
+/* Optimized and safe macros for looping over external lists. */
+#define CIRCULAR_LIST_SUSPICION_LENGTH 1024
+
+#define EXTERNAL_LIST_LOOP_1(list) \
+Lisp_Object ELL1_elt, ELL1_hare, ELL1_tortoise; \
+EMACS_INT ELL1_len; \
+PRIVATE_EXTERNAL_LIST_LOOP_6 (ELL1_elt, list, ELL1_len, ELL1_hare, \
+ ELL1_tortoise, CIRCULAR_LIST_SUSPICION_LENGTH)
+
+#define EXTERNAL_LIST_LOOP_2(elt, list) \
+Lisp_Object elt, hare_##elt, tortoise_##elt; \
+EMACS_INT len_##elt; \
+PRIVATE_EXTERNAL_LIST_LOOP_6 (elt, list, len_##elt, hare_##elt, \
+ tortoise_##elt, CIRCULAR_LIST_SUSPICION_LENGTH)
+
+#define EXTERNAL_LIST_LOOP_3(elt, list, tail) \
+Lisp_Object elt, tail, tortoise_##elt; \
+EMACS_INT len_##elt; \
+PRIVATE_EXTERNAL_LIST_LOOP_6 (elt, list, len_##elt, tail, \
+ tortoise_##elt, CIRCULAR_LIST_SUSPICION_LENGTH)
+
+#define EXTERNAL_LIST_LOOP_4_NO_DECLARE(elt, list, tail, len) \
+Lisp_Object tortoise_##elt; \
+PRIVATE_EXTERNAL_LIST_LOOP_6 (elt, list, len, tail, \
+ tortoise_##elt, CIRCULAR_LIST_SUSPICION_LENGTH)
+
+#define EXTERNAL_LIST_LOOP_4(elt, list, tail, len) \
+Lisp_Object elt, tail, tortoise_##elt; \
+EMACS_INT len; \
+PRIVATE_EXTERNAL_LIST_LOOP_6 (elt, list, len, tail, \
+ tortoise_##elt, CIRCULAR_LIST_SUSPICION_LENGTH)
+
+
+#define PRIVATE_EXTERNAL_LIST_LOOP_6(elt, list, len, hare, \
+ tortoise, suspicion_length) \
+ for (tortoise = hare = list, len = 0; \
+ \
+ (CONSP (hare) ? ((elt = XCAR (hare)), 1) : \
+ (NILP (hare) ? 0 : \
+ (signal_malformed_list_error (list), 0))); \
+ \
+ hare = XCDR (hare), \
+ (void) \
+ ((++len > suspicion_length) \
+ && \
+ ((((len & 1) != 0) && (tortoise = XCDR (tortoise), 0)), \
+ (EQ (hare, tortoise) && (signal_circular_list_error (list), 0)))))
+
+/* GET_LIST_LENGTH and GET_EXTERNAL_LIST_LENGTH:
+
+ These two macros return the length of LIST (either an internal or external
+ list, according to which macro is used), stored into LEN (which must
+ be declared by the caller). Circularities are trapped in external lists
+ (and cause errors). Neither macro need be declared inside brackets. */
+
+#define GET_LIST_LENGTH(list, len) do { \
+ Lisp_Object GLL_tail; \
+ for (GLL_tail = list, len = 0; \
+ !NILP (GLL_tail); \
+ GLL_tail = XCDR (GLL_tail), ++len) \
+ DO_NOTHING; \
+} while (0)
+
+#define GET_EXTERNAL_LIST_LENGTH(list, len) \
+do { \
+ Lisp_Object GELL_elt, GELL_tail; \
+ EXTERNAL_LIST_LOOP_4_NO_DECLARE (GELL_elt, list, GELL_tail, len) \
+ ; \
+} while (0)