-/* Copyright (C) 1995,1996,1997,2000,2001,2003,2004,2008,2009,2010,2011
- * Free Software Foundation, Inc.
+/* Copyright (C) 1995-1997, 2000, 2001, 2003, 2004, 2008-2011,
+ * 2014 Free Software Foundation, Inc.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public License
long" lists (i.e. lists with cycles in their cdrs), and returns -1
if it does find one. */
long
-scm_ilength(SCM sx)
+scm_ilength (SCM sx)
{
long i = 0;
SCM tortoise = sx;
SCM hare = sx;
- do {
- if (SCM_NULL_OR_NIL_P(hare)) return i;
- if (!scm_is_pair (hare)) return -1;
- hare = SCM_CDR(hare);
- i++;
- if (SCM_NULL_OR_NIL_P(hare)) return i;
- if (!scm_is_pair (hare)) return -1;
- hare = SCM_CDR(hare);
- i++;
- /* For every two steps the hare takes, the tortoise takes one. */
- tortoise = SCM_CDR(tortoise);
- }
+ do
+ {
+ if (!scm_is_pair (hare))
+ return SCM_NULL_OR_NIL_P (hare) ? i : -1;
+ hare = SCM_CDR (hare);
+ i++;
+ if (!scm_is_pair (hare))
+ return SCM_NULL_OR_NIL_P (hare) ? i : -1;
+ hare = SCM_CDR (hare);
+ i++;
+ /* For every two steps the hare takes, the tortoise takes one. */
+ tortoise = SCM_CDR (tortoise);
+ }
while (!scm_is_eq (hare, tortoise));
/* If the tortoise ever catches the hare, then the list must contain
"@code{reverse!}")
#define FUNC_NAME s_scm_reverse_x
{
- SCM_VALIDATE_LIST (1, lst);
+ SCM old_lst = lst;
+ SCM tail = SCM_BOOL_F;
+
if (SCM_UNBNDP (new_tail))
new_tail = SCM_EOL;
- while (!SCM_NULL_OR_NIL_P (lst))
+ if (SCM_NULL_OR_NIL_P (lst))
+ return new_tail;
+
+ /* SCM_VALIDATE_LIST would run through the whole list to make sure it
+ is not eventually circular. In contrast to most list operations,
+ reverse! cannot get stuck in an infinite loop but arrives back at
+ the start when given an eventually or fully circular list. Because
+ of that, we can save the cost of an upfront proper list check at
+ the price of having to do a double reversal in the error case.
+ */
+
+ while (scm_is_pair (lst))
{
SCM old_tail = SCM_CDR (lst);
- SCM_SETCDR (lst, new_tail);
- new_tail = lst;
+ SCM_SETCDR (lst, tail);
+ tail = lst;
lst = old_tail;
}
- return new_tail;
+
+ if (SCM_LIKELY (SCM_NULL_OR_NIL_P (lst)))
+ {
+ SCM_SETCDR (old_lst, new_tail);
+ return tail;
+ }
+
+ /* We did not start with a proper list. Undo the reversal. */
+
+ while (scm_is_pair (tail))
+ {
+ SCM old_tail = SCM_CDR (tail);
+ SCM_SETCDR (tail, lst);
+ lst = tail;
+ tail = old_tail;
+ }
+
+ SCM_WRONG_TYPE_ARG (1, lst);
+ return lst;
}
#undef FUNC_NAME