Lines Matching refs:initial
97 an initial segment and an endlessly repeated loop segment.
98 A finite sequence is represented entirely in the initial segment; the
101 struct segment initial; /* Initial arguments segment. */
165 ASSERT (list->initial.count <= list->initial.allocated);
167 for (i = 0; i < list->initial.count; i++)
169 verify_element (&list->initial.element[i]);
170 total_repcount += list->initial.element[i].repcount;
172 ASSERT (total_repcount == list->initial.length);
204 for (i = 0; i < list->initial.count; i++)
205 free_element (&list->initial.element[i]);
206 if (list->initial.element != NULL)
207 free (list->initial.element);
243 newlist->initial.count = newlist->initial.allocated = list->initial.count;
245 if (list->initial.count == 0)
246 newlist->initial.element = NULL;
249 newlist->initial.element =
250 XNMALLOC (newlist->initial.allocated, struct format_arg);
251 for (i = 0; i < list->initial.count; i++)
253 copy_element (&newlist->initial.element[i],
254 &list->initial.element[i]);
255 length += list->initial.element[i].repcount;
258 ASSERT (length == list->initial.length);
259 newlist->initial.length = length;
308 n = list1->initial.count;
309 if (n != list2->initial.count)
313 const struct format_arg * e1 = &list1->initial.element[i];
314 const struct format_arg * e2 = &list2->initial.element[i];
338 /* Ensure list->initial.allocated >= newcount. */
342 if (newcount > list->initial.allocated)
344 list->initial.allocated =
345 MAX (2 * list->initial.allocated + 1, newcount);
346 list->initial.element =
348 xrealloc (list->initial.element,
349 list->initial.allocated * sizeof (struct format_arg));
353 /* Ensure list->initial.allocated > list->initial.count. */
357 if (list->initial.count >= list->initial.allocated)
359 list->initial.allocated =
360 MAX (2 * list->initial.allocated + 1, list->initial.count + 1);
361 list->initial.element =
363 xrealloc (list->initial.element,
364 list->initial.allocated * sizeof (struct format_arg));
412 n = list->initial.count;
415 && equal_element (&list->initial.element[i],
416 &list->initial.element[j-1]))
418 list->initial.element[j-1].repcount +=
419 list->initial.element[i].repcount;
420 free_element (&list->initial.element[i]);
425 list->initial.element[j] = list->initial.element[i];
428 list->initial.count = j;
493 /* Step 3: Roll as much as possible of the initial segment's tail
497 if (list->initial.count > 0
498 && equal_element (&list->initial.element[list->initial.count-1],
501 /* Roll the last element of the initial segment into the loop.
504 list->initial.length -=
505 list->initial.element[list->initial.count-1].repcount;
506 list->initial.count--;
511 while (list->initial.count > 0
512 && equal_element (&list->initial.element[list->initial.count-1],
516 MIN (list->initial.element[list->initial.count-1].repcount,
544 /* Remove the element from the end of list->initial. */
545 list->initial.element[list->initial.count-1].repcount -=
547 if (list->initial.element[list->initial.count-1].repcount == 0)
549 free_element (&list->initial.element[list->initial.count-1]);
550 list->initial.count--;
552 list->initial.length -= moved_repcount;
568 n = list->initial.count;
570 if (list->initial.element[i].type == FAT_LIST)
571 normalize_list (list->initial.element[i].list);
598 list->initial.count = 0;
599 list->initial.allocated = 0;
600 list->initial.element = NULL;
601 list->initial.length = 0;
624 list->initial.count = 0;
625 list->initial.allocated = 0;
626 list->initial.element = NULL;
627 list->initial.length = 0;
644 return (list->initial.count == 0 && list->repeated.count == 0);
671 /* Ensure list->initial.length := m, where m >= list->initial.length.
677 if (m == list->initial.length)
683 copy with higher repcount is appended to list->initial. */
686 newcount = list->initial.count + 1;
688 i = list->initial.count;
689 copy_element (&list->initial.element[i], &list->repeated.element[0]);
690 list->initial.element[i].repcount = m - list->initial.length;
691 list->initial.count = newcount;
692 list->initial.length = m;
698 /* Write m = list->initial.length + q * n + r with 0 <= r < n. */
699 unsigned int q = (m - list->initial.length) / n;
700 unsigned int r = (m - list->initial.length) % n;
715 /* So we need to add to list->initial:
722 i = list->initial.count;
727 copy_element (&list->initial.element[i],
730 copy_element (&list->initial.element[i], &list->repeated.element[j]);
733 copy_element (&list->initial.element[i],
735 list->initial.element[i].repcount = t;
739 list->initial.count = newcount;
740 /* The new length of the initial segment is
741 = list->initial.length
744 = list->initial.length + q * n + r
747 list->initial.length = m;
777 /* Ensure index n in the initial segment falls on a split between elements,
778 i.e. if 0 < n < list->initial.length, then n-1 and n are covered by two
792 if (n > list->initial.length)
796 ASSERT (n <= list->initial.length);
799 /* Determine how many entries of list->initial need to be skipped. */
801 s < list->initial.count && t >= list->initial.element[s].repcount;
802 t -= list->initial.element[s].repcount, s++)
808 ASSERT (s < list->initial.count);
811 oldrepcount = list->initial.element[s].repcount;
812 newcount = list->initial.count + 1;
814 for (i = list->initial.count - 1; i > s; i--)
815 list->initial.element[i+1] = list->initial.element[i];
816 copy_element (&list->initial.element[s+1], &list->initial.element[s]);
817 list->initial.element[s].repcount = t;
818 list->initial.element[s+1].repcount = oldrepcount - t;
819 list->initial.count = newcount;
827 /* Ensure index n in the initial segment is not shared. Return its index. */
841 if (n >= list->initial.length)
845 ASSERT (n < list->initial.length);
848 /* Determine how many entries of list->initial need to be skipped. */
850 s < list->initial.count && t >= list->initial.element[s].repcount;
851 t -= list->initial.element[s].repcount, s++)
854 /* s must be < list->initial.count. */
855 ASSERT (s < list->initial.count);
857 if (list->initial.element[s].repcount > 1)
861 unsigned int oldrepcount = list->initial.element[s].repcount;
863 list->initial.count + (t == 0 || t == oldrepcount - 1 ? 1 : 2);
869 for (i = list->initial.count - 1; i > s; i--)
870 list->initial.element[i+1] = list->initial.element[i];
871 copy_element (&list->initial.element[s+1], &list->initial.element[s]);
874 list->initial.element[s].repcount = 1;
875 list->initial.element[s+1].repcount = oldrepcount - 1;
879 list->initial.element[s].repcount = oldrepcount - 1;
880 list->initial.element[s+1].repcount = 1;
887 for (i = list->initial.count - 1; i > s; i--)
888 list->initial.element[i+2] = list->initial.element[i];
889 copy_element (&list->initial.element[s+2], &list->initial.element[s]);
890 copy_element (&list->initial.element[s+1], &list->initial.element[s]);
891 list->initial.element[s].repcount = t;
892 list->initial.element[s+1].repcount = 1;
893 list->initial.element[s+2].repcount = oldrepcount - 1 - t;
895 list->initial.count = newcount;
901 ASSERT (list->initial.element[s].repcount == 1);
921 for (i = list->initial.count; i > 0; i--)
922 list->initial.element[i] = list->initial.element[i-1];
923 list->initial.element[0].repcount = n;
924 list->initial.element[0].presence = FCT_REQUIRED;
925 list->initial.element[0].type = FAT_OBJECT;
926 list->initial.count++;
927 list->initial.length += n;
1041 /* Append list->repeated to list->initial, and clear list->repeated. */
1048 /* Move list->repeated over to list->initial. */
1051 newcount = list->initial.count + list->repeated.count;
1053 i = list->initial.count;
1055 list->initial.element[i] = list->repeated.element[j];
1056 list->initial.count = newcount;
1057 list->initial.length = list->initial.length + list->repeated.length;
1067 The list consists only of an initial segment. The repeated segment is
1077 while (list->initial.count > 0)
1079 unsigned int i = list->initial.count - 1;
1080 if (list->initial.element[i].presence == FCT_REQUIRED)
1083 list->initial.length -= list->initial.element[i].repcount;
1084 free_element (&list->initial.element[i]);
1085 list->initial.count = i;
1087 else /* list->initial.element[i].presence == FCT_OPTIONAL */
1090 list->initial.length--;
1091 if (list->initial.element[i].repcount > 1)
1092 list->initial.element[i].repcount--;
1095 free_element (&list->initial.element[i]);
1096 list->initial.count = i;
1136 /* Step 2: Ensure the initial segment of the result can be computed
1137 from the initial segments of list1 and list2. If both have a
1139 list1->initial.length == list2->initial.length. */
1141 unsigned int m = MAX (list1->initial.length, list2->initial.length);
1151 ASSERT (list1->initial.length == list2->initial.length);
1157 result->initial.count = 0;
1158 result->initial.allocated = 0;
1159 result->initial.element = NULL;
1160 result->initial.length = 0;
1166 /* Step 4: Elementwise intersection of list1->initial, list2->initial. */
1173 e1 = list1->initial.element; c1 = list1->initial.count;
1174 e2 = list2->initial.element; c2 = list2->initial.count;
1179 /* Ensure room in result->initial. */
1181 re = &result->initial.element[result->initial.count];
1194 result->initial.count++;
1195 result->initial.length += re->repcount;
1326 if (list->initial.count > 0
1327 ? list->initial.element[0].presence == FCT_REQUIRED
1498 /* Step 2: Ensure that list1->initial.length == list2->initial.length. */
1500 unsigned int m = MAX (list1->initial.length, list2->initial.length);
1506 ASSERT (list1->initial.length == list2->initial.length);
1511 /* Ensure the initial segment of the result can be computed from the
1512 initial segment of list1. */
1513 if (list2->initial.length >= list1->initial.length)
1515 rotate_loop (list1, list2->initial.length);
1517 rotate_loop (list1, list1->initial.length + 1);
1522 /* Ensure the initial segment of the result can be computed from the
1523 initial segment of list2. */
1524 if (list1->initial.length >= list2->initial.length)
1526 rotate_loop (list2, list1->initial.length);
1528 rotate_loop (list2, list2->initial.length + 1);
1534 result->initial.count = 0;
1535 result->initial.allocated = 0;
1536 result->initial.element = NULL;
1537 result->initial.length = 0;
1543 /* Step 4: Elementwise union of list1->initial, list2->initial. */
1550 e1 = list1->initial.element; c1 = list1->initial.count;
1551 e2 = list2->initial.element; c2 = list2->initial.count;
1556 /* Ensure room in result->initial. */
1558 re = &result->initial.element[result->initial.count];
1564 result->initial.count++;
1565 result->initial.length += re->repcount;
1583 /* list2 already terminated, but still more elements in list1->initial.
1591 /* Ensure room in result->initial. */
1593 re = &result->initial.element[result->initial.count];
1597 result->initial.count++;
1598 result->initial.length += 1;
1607 /* Ensure room in result->initial. */
1608 ensure_initial_alloc (result, result->initial.count + c1);
1613 re = &result->initial.element[result->initial.count];
1615 result->initial.count++;
1616 result->initial.length += re->repcount;
1623 /* list1 already terminated, but still more elements in list2->initial.
1631 /* Ensure room in result->initial. */
1633 re = &result->initial.element[result->initial.count];
1637 result->initial.count++;
1638 result->initial.length += 1;
1647 /* Ensure room in result->initial. */
1648 ensure_initial_alloc (result, result->initial.count + c2);
1653 re = &result->initial.element[result->initial.count];
1655 result->initial.count++;
1656 result->initial.length += re->repcount;
1707 initial segment. Just copy the repeated segment of list1. */
1722 initial segment. Just copy the repeated segment of list2. */
1754 if (list->initial.count > 0
1755 ? list->initial.element[0].presence == FCT_REQUIRED
1760 ASSERT (list->initial.count > 0);
1761 ASSERT (list->initial.element[0].repcount == 1);
1762 ASSERT (list->initial.element[0].presence == FCT_REQUIRED);
1763 list->initial.element[0].presence = FCT_OPTIONAL;
1765 /* We might need to merge list->initial.element[0] and
1766 list->initial.element[1]. */
1814 /* Walk the list->initial segment. */
1816 s < list->initial.count && t >= list->initial.element[s].repcount;
1817 t -= list->initial.element[s].repcount, s++)
1818 if (list->initial.element[s].presence != FCT_REQUIRED)
1824 if (s < list->initial.count)
1826 if (list->initial.element[s].presence != FCT_REQUIRED)
1873 if (list->repeated.count == 0 && list->initial.length <= n)
1885 list->initial.element[i].presence = FCT_REQUIRED;
1886 rest -= list->initial.element[i].repcount;
1911 if (list->repeated.count == 0 && list->initial.length <= n)
1917 (s < list->initial.count
1918 ? /* n < list->initial.length */ list->initial.element[s].presence
1919 : /* n >= list->initial.length */ list->repeated.element[0].presence);
1921 for (i = s; i < list->initial.count; i++)
1923 list->initial.length -= list->initial.element[i].repcount;
1924 free_element (&list->initial.element[i]);
1926 list->initial.count = s;
1960 list->initial.length >= n+1. */
1967 &list->initial.element[s], &newconstraint))
1969 free_element (&list->initial.element[s]);
1970 list->initial.element[s].type = tmpelement.type;
1971 list->initial.element[s].list = tmpelement.list;
1996 list->initial.length >= n+1. */
2004 &list->initial.element[s], &newconstraint))
2006 free_element (&list->initial.element[s]);
2007 list->initial.element[s].type = tmpelement.type;
2008 list->initial.element[s].list = tmpelement.list;
2052 listlist->initial.count = 0;
2053 listlist->initial.allocated = 0;
2054 listlist->initial.element = NULL;
2055 listlist->initial.length = 0;
2099 if (sublist->initial.length < period)
2104 srcseg = &sublist->initial;
2117 /* Concatenate the initial and the repeated segments into a single
2119 tmp.count = sublist->initial.count + sublist->repeated.count;
2122 for (i = 0; i < sublist->initial.count; i++)
2123 tmp.element[i] = sublist->initial.element[i];
2125 tmp.element[i] = sublist->initial.element[j];
2126 tmp.length = sublist->initial.length + sublist->repeated.length;
2141 Thus the result has an initial segment of length n - p and a period
2147 list->initial.count = 0;
2148 list->initial.allocated = 0;
2149 list->initial.element = NULL;
2150 list->initial.length = 0;
2158 list->initial.element[i] = srcseg->element[i];
2159 list->initial.element[0].presence = FCT_OPTIONAL; // union with empty list
2161 list->initial.element[i] = srcseg->element[i] & list->initial.element[j];
2171 /* Ensure room in list->initial. */
2173 copy_element (&list->initial.element[list->initial.count],
2175 list->initial.element[list->initial.count].repcount = k;
2176 list->initial.count++;
2177 list->initial.length += k;
2188 ASSERT (list->initial.count > 0);
2189 if (list->initial.element[0].presence == FCT_REQUIRED)
2192 ASSERT (list->initial.element[0].presence == FCT_REQUIRED);
2193 ASSERT (list->initial.element[0].repcount == 1);
2194 list->initial.element[0].presence = FCT_OPTIONAL;
2202 list->initial.element[sj].repcount - tj);
2204 /* Ensure room in list->initial. */
2206 if (!make_intersected_element (&list->initial.element[list->initial.count],
2208 &list->initial.element[sj]))
2210 if (list->initial.element[list->initial.count].presence == FCT_REQUIRED)
2224 list->initial.element[list->initial.count].repcount = k;
2225 list->initial.count++;
2226 list->initial.length += k;
2238 if (tj == list->initial.element[sj].repcount)
2245 ASSERT (list->initial.length == n);
2249 for (i = 0; i < list->initial.length; i += period)
2252 list->initial.element[si].presence = FCT_OPTIONAL;
2259 newcount = list->initial.count - splitindex;
2266 list->repeated.element[j] = list->initial.element[i];
2269 list->initial.count = splitindex;
2270 list->initial.length = n - p;
3581 for (i = 0; i < list->initial.count; i++)
3582 for (j = 0; j < list->initial.element[i].repcount; j++)
3586 print_element (&list->initial.element[i]);