Lines Matching refs:initial
100 an initial segment and an endlessly repeated loop segment.
101 A finite sequence is represented entirely in the initial segment; the
104 struct segment initial; /* Initial arguments segment. */
168 ASSERT (list->initial.count <= list->initial.allocated);
170 for (i = 0; i < list->initial.count; i++)
172 verify_element (&list->initial.element[i]);
173 total_repcount += list->initial.element[i].repcount;
175 ASSERT (total_repcount == list->initial.length);
207 for (i = 0; i < list->initial.count; i++)
208 free_element (&list->initial.element[i]);
209 if (list->initial.element != NULL)
210 free (list->initial.element);
246 newlist->initial.count = newlist->initial.allocated = list->initial.count;
248 if (list->initial.count == 0)
249 newlist->initial.element = NULL;
252 newlist->initial.element =
253 XNMALLOC (newlist->initial.allocated, struct format_arg);
254 for (i = 0; i < list->initial.count; i++)
256 copy_element (&newlist->initial.element[i],
257 &list->initial.element[i]);
258 length += list->initial.element[i].repcount;
261 ASSERT (length == list->initial.length);
262 newlist->initial.length = length;
311 n = list1->initial.count;
312 if (n != list2->initial.count)
316 const struct format_arg * e1 = &list1->initial.element[i];
317 const struct format_arg * e2 = &list2->initial.element[i];
341 /* Ensure list->initial.allocated >= newcount. */
345 if (newcount > list->initial.allocated)
347 list->initial.allocated =
348 MAX (2 * list->initial.allocated + 1, newcount);
349 list->initial.element =
351 xrealloc (list->initial.element,
352 list->initial.allocated * sizeof (struct format_arg));
356 /* Ensure list->initial.allocated > list->initial.count. */
360 if (list->initial.count >= list->initial.allocated)
362 list->initial.allocated =
363 MAX (2 * list->initial.allocated + 1, list->initial.count + 1);
364 list->initial.element =
366 xrealloc (list->initial.element,
367 list->initial.allocated * sizeof (struct format_arg));
415 n = list->initial.count;
418 && equal_element (&list->initial.element[i],
419 &list->initial.element[j-1]))
421 list->initial.element[j-1].repcount +=
422 list->initial.element[i].repcount;
423 free_element (&list->initial.element[i]);
428 list->initial.element[j] = list->initial.element[i];
431 list->initial.count = j;
496 /* Step 3: Roll as much as possible of the initial segment's tail
500 if (list->initial.count > 0
501 && equal_element (&list->initial.element[list->initial.count-1],
504 /* Roll the last element of the initial segment into the loop.
507 list->initial.length -=
508 list->initial.element[list->initial.count-1].repcount;
509 list->initial.count--;
514 while (list->initial.count > 0
515 && equal_element (&list->initial.element[list->initial.count-1],
519 MIN (list->initial.element[list->initial.count-1].repcount,
547 /* Remove the element from the end of list->initial. */
548 list->initial.element[list->initial.count-1].repcount -=
550 if (list->initial.element[list->initial.count-1].repcount == 0)
552 free_element (&list->initial.element[list->initial.count-1]);
553 list->initial.count--;
555 list->initial.length -= moved_repcount;
571 n = list->initial.count;
573 if (list->initial.element[i].type == FAT_LIST)
574 normalize_list (list->initial.element[i].list);
601 list->initial.count = 0;
602 list->initial.allocated = 0;
603 list->initial.element = NULL;
604 list->initial.length = 0;
627 list->initial.count = 0;
628 list->initial.allocated = 0;
629 list->initial.element = NULL;
630 list->initial.length = 0;
647 return (list->initial.count == 0 && list->repeated.count == 0);
674 /* Ensure list->initial.length := m, where m >= list->initial.length.
680 if (m == list->initial.length)
686 copy with higher repcount is appended to list->initial. */
689 newcount = list->initial.count + 1;
691 i = list->initial.count;
692 copy_element (&list->initial.element[i], &list->repeated.element[0]);
693 list->initial.element[i].repcount = m - list->initial.length;
694 list->initial.count = newcount;
695 list->initial.length = m;
701 /* Write m = list->initial.length + q * n + r with 0 <= r < n. */
702 unsigned int q = (m - list->initial.length) / n;
703 unsigned int r = (m - list->initial.length) % n;
718 /* So we need to add to list->initial:
725 i = list->initial.count;
730 copy_element (&list->initial.element[i],
733 copy_element (&list->initial.element[i], &list->repeated.element[j]);
736 copy_element (&list->initial.element[i],
738 list->initial.element[i].repcount = t;
742 list->initial.count = newcount;
743 /* The new length of the initial segment is
744 = list->initial.length
747 = list->initial.length + q * n + r
750 list->initial.length = m;
780 /* Ensure index n in the initial segment falls on a split between elements,
781 i.e. if 0 < n < list->initial.length, then n-1 and n are covered by two
795 if (n > list->initial.length)
799 ASSERT (n <= list->initial.length);
802 /* Determine how many entries of list->initial need to be skipped. */
804 s < list->initial.count && t >= list->initial.element[s].repcount;
805 t -= list->initial.element[s].repcount, s++)
811 ASSERT (s < list->initial.count);
814 oldrepcount = list->initial.element[s].repcount;
815 newcount = list->initial.count + 1;
817 for (i = list->initial.count - 1; i > s; i--)
818 list->initial.element[i+1] = list->initial.element[i];
819 copy_element (&list->initial.element[s+1], &list->initial.element[s]);
820 list->initial.element[s].repcount = t;
821 list->initial.element[s+1].repcount = oldrepcount - t;
822 list->initial.count = newcount;
830 /* Ensure index n in the initial segment is not shared. Return its index. */
844 if (n >= list->initial.length)
848 ASSERT (n < list->initial.length);
851 /* Determine how many entries of list->initial need to be skipped. */
853 s < list->initial.count && t >= list->initial.element[s].repcount;
854 t -= list->initial.element[s].repcount, s++)
857 /* s must be < list->initial.count. */
858 ASSERT (s < list->initial.count);
860 if (list->initial.element[s].repcount > 1)
864 unsigned int oldrepcount = list->initial.element[s].repcount;
866 list->initial.count + (t == 0 || t == oldrepcount - 1 ? 1 : 2);
872 for (i = list->initial.count - 1; i > s; i--)
873 list->initial.element[i+1] = list->initial.element[i];
874 copy_element (&list->initial.element[s+1], &list->initial.element[s]);
877 list->initial.element[s].repcount = 1;
878 list->initial.element[s+1].repcount = oldrepcount - 1;
882 list->initial.element[s].repcount = oldrepcount - 1;
883 list->initial.element[s+1].repcount = 1;
890 for (i = list->initial.count - 1; i > s; i--)
891 list->initial.element[i+2] = list->initial.element[i];
892 copy_element (&list->initial.element[s+2], &list->initial.element[s]);
893 copy_element (&list->initial.element[s+1], &list->initial.element[s]);
894 list->initial.element[s].repcount = t;
895 list->initial.element[s+1].repcount = 1;
896 list->initial.element[s+2].repcount = oldrepcount - 1 - t;
898 list->initial.count = newcount;
904 ASSERT (list->initial.element[s].repcount == 1);
924 for (i = list->initial.count; i > 0; i--)
925 list->initial.element[i] = list->initial.element[i-1];
926 list->initial.element[0].repcount = n;
927 list->initial.element[0].presence = FCT_REQUIRED;
928 list->initial.element[0].type = FAT_OBJECT;
929 list->initial.count++;
930 list->initial.length += n;
1054 /* Append list->repeated to list->initial, and clear list->repeated. */
1061 /* Move list->repeated over to list->initial. */
1064 newcount = list->initial.count + list->repeated.count;
1066 i = list->initial.count;
1068 list->initial.element[i] = list->repeated.element[j];
1069 list->initial.count = newcount;
1070 list->initial.length = list->initial.length + list->repeated.length;
1080 The list consists only of an initial segment. The repeated segment is
1090 while (list->initial.count > 0)
1092 unsigned int i = list->initial.count - 1;
1093 if (list->initial.element[i].presence == FCT_REQUIRED)
1096 list->initial.length -= list->initial.element[i].repcount;
1097 free_element (&list->initial.element[i]);
1098 list->initial.count = i;
1100 else /* list->initial.element[i].presence == FCT_OPTIONAL */
1103 list->initial.length--;
1104 if (list->initial.element[i].repcount > 1)
1105 list->initial.element[i].repcount--;
1108 free_element (&list->initial.element[i]);
1109 list->initial.count = i;
1149 /* Step 2: Ensure the initial segment of the result can be computed
1150 from the initial segments of list1 and list2. If both have a
1152 list1->initial.length == list2->initial.length. */
1154 unsigned int m = MAX (list1->initial.length, list2->initial.length);
1164 ASSERT (list1->initial.length == list2->initial.length);
1170 result->initial.count = 0;
1171 result->initial.allocated = 0;
1172 result->initial.element = NULL;
1173 result->initial.length = 0;
1179 /* Step 4: Elementwise intersection of list1->initial, list2->initial. */
1186 e1 = list1->initial.element; c1 = list1->initial.count;
1187 e2 = list2->initial.element; c2 = list2->initial.count;
1192 /* Ensure room in result->initial. */
1194 re = &result->initial.element[result->initial.count];
1207 result->initial.count++;
1208 result->initial.length += re->repcount;
1339 if (list->initial.count > 0
1340 ? list->initial.element[0].presence == FCT_REQUIRED
1521 /* Step 2: Ensure that list1->initial.length == list2->initial.length. */
1523 unsigned int m = MAX (list1->initial.length, list2->initial.length);
1529 ASSERT (list1->initial.length == list2->initial.length);
1534 /* Ensure the initial segment of the result can be computed from the
1535 initial segment of list1. */
1536 if (list2->initial.length >= list1->initial.length)
1538 rotate_loop (list1, list2->initial.length);
1540 rotate_loop (list1, list1->initial.length + 1);
1545 /* Ensure the initial segment of the result can be computed from the
1546 initial segment of list2. */
1547 if (list1->initial.length >= list2->initial.length)
1549 rotate_loop (list2, list1->initial.length);
1551 rotate_loop (list2, list2->initial.length + 1);
1557 result->initial.count = 0;
1558 result->initial.allocated = 0;
1559 result->initial.element = NULL;
1560 result->initial.length = 0;
1566 /* Step 4: Elementwise union of list1->initial, list2->initial. */
1573 e1 = list1->initial.element; c1 = list1->initial.count;
1574 e2 = list2->initial.element; c2 = list2->initial.count;
1579 /* Ensure room in result->initial. */
1581 re = &result->initial.element[result->initial.count];
1587 result->initial.count++;
1588 result->initial.length += re->repcount;
1606 /* list2 already terminated, but still more elements in list1->initial.
1614 /* Ensure room in result->initial. */
1616 re = &result->initial.element[result->initial.count];
1620 result->initial.count++;
1621 result->initial.length += 1;
1630 /* Ensure room in result->initial. */
1631 ensure_initial_alloc (result, result->initial.count + c1);
1636 re = &result->initial.element[result->initial.count];
1638 result->initial.count++;
1639 result->initial.length += re->repcount;
1646 /* list1 already terminated, but still more elements in list2->initial.
1654 /* Ensure room in result->initial. */
1656 re = &result->initial.element[result->initial.count];
1660 result->initial.count++;
1661 result->initial.length += 1;
1670 /* Ensure room in result->initial. */
1671 ensure_initial_alloc (result, result->initial.count + c2);
1676 re = &result->initial.element[result->initial.count];
1678 result->initial.count++;
1679 result->initial.length += re->repcount;
1730 initial segment. Just copy the repeated segment of list1. */
1745 initial segment. Just copy the repeated segment of list2. */
1777 if (list->initial.count > 0
1778 ? list->initial.element[0].presence == FCT_REQUIRED
1783 ASSERT (list->initial.count > 0);
1784 ASSERT (list->initial.element[0].repcount == 1);
1785 ASSERT (list->initial.element[0].presence == FCT_REQUIRED);
1786 list->initial.element[0].presence = FCT_OPTIONAL;
1788 /* We might need to merge list->initial.element[0] and
1789 list->initial.element[1]. */
1837 /* Walk the list->initial segment. */
1839 s < list->initial.count && t >= list->initial.element[s].repcount;
1840 t -= list->initial.element[s].repcount, s++)
1841 if (list->initial.element[s].presence != FCT_REQUIRED)
1847 if (s < list->initial.count)
1849 if (list->initial.element[s].presence != FCT_REQUIRED)
1896 if (list->repeated.count == 0 && list->initial.length <= n)
1908 list->initial.element[i].presence = FCT_REQUIRED;
1909 rest -= list->initial.element[i].repcount;
1934 if (list->repeated.count == 0 && list->initial.length <= n)
1940 (s < list->initial.count
1941 ? /* n < list->initial.length */ list->initial.element[s].presence
1942 : /* n >= list->initial.length */ list->repeated.element[0].presence);
1944 for (i = s; i < list->initial.count; i++)
1946 list->initial.length -= list->initial.element[i].repcount;
1947 free_element (&list->initial.element[i]);
1949 list->initial.count = s;
1983 list->initial.length >= n+1. */
1990 &list->initial.element[s], &newconstraint))
1992 free_element (&list->initial.element[s]);
1993 list->initial.element[s].type = tmpelement.type;
1994 list->initial.element[s].list = tmpelement.list;
2019 list->initial.length >= n+1. */
2027 &list->initial.element[s], &newconstraint))
2029 free_element (&list->initial.element[s]);
2030 list->initial.element[s].type = tmpelement.type;
2031 list->initial.element[s].list = tmpelement.list;
2075 listlist->initial.count = 0;
2076 listlist->initial.allocated = 0;
2077 listlist->initial.element = NULL;
2078 listlist->initial.length = 0;
2122 if (sublist->initial.length < period)
2127 srcseg = &sublist->initial;
2140 /* Concatenate the initial and the repeated segments into a single
2142 tmp.count = sublist->initial.count + sublist->repeated.count;
2145 for (i = 0; i < sublist->initial.count; i++)
2146 tmp.element[i] = sublist->initial.element[i];
2148 tmp.element[i] = sublist->initial.element[j];
2149 tmp.length = sublist->initial.length + sublist->repeated.length;
2164 Thus the result has an initial segment of length n - p and a period
2170 list->initial.count = 0;
2171 list->initial.allocated = 0;
2172 list->initial.element = NULL;
2173 list->initial.length = 0;
2181 list->initial.element[i] = srcseg->element[i];
2182 list->initial.element[0].presence = FCT_OPTIONAL; // union with empty list
2184 list->initial.element[i] = srcseg->element[i] & list->initial.element[j];
2194 /* Ensure room in list->initial. */
2196 copy_element (&list->initial.element[list->initial.count],
2198 list->initial.element[list->initial.count].repcount = k;
2199 list->initial.count++;
2200 list->initial.length += k;
2211 ASSERT (list->initial.count > 0);
2212 if (list->initial.element[0].presence == FCT_REQUIRED)
2215 ASSERT (list->initial.element[0].presence == FCT_REQUIRED);
2216 ASSERT (list->initial.element[0].repcount == 1);
2217 list->initial.element[0].presence = FCT_OPTIONAL;
2225 list->initial.element[sj].repcount - tj);
2227 /* Ensure room in list->initial. */
2229 if (!make_intersected_element (&list->initial.element[list->initial.count],
2231 &list->initial.element[sj]))
2233 if (list->initial.element[list->initial.count].presence == FCT_REQUIRED)
2247 list->initial.element[list->initial.count].repcount = k;
2248 list->initial.count++;
2249 list->initial.length += k;
2261 if (tj == list->initial.element[sj].repcount)
2268 ASSERT (list->initial.length == n);
2272 for (i = 0; i < list->initial.length; i += period)
2275 list->initial.element[si].presence = FCT_OPTIONAL;
2282 newcount = list->initial.count - splitindex;
2289 list->repeated.element[j] = list->initial.element[i];
2292 list->initial.count = splitindex;
2293 list->initial.length = n - p;
3504 for (i = 0; i < list->initial.count; i++)
3505 for (j = 0; j < list->initial.element[i].repcount; j++)
3509 print_element (&list->initial.element[i]);