7 static SCM break_criterion;
9 set_break_subsititution (SCM criterion)
11 break_criterion = criterion;
15 Perform the substitution for a single grob.
18 substitute_grob (Grob *sc)
20 if (scm_is_integer (break_criterion))
22 Item * i = dynamic_cast<Item*> (sc);
23 Direction d = to_dir (break_criterion);
24 if (i && i->break_status_dir () != d)
26 Item *br = i->find_prebroken_piece (d);
27 return (br) ? br->self_scm () : SCM_UNDEFINED;
33 = dynamic_cast<System*> (unsmob_grob (break_criterion));
34 if (sc->get_system () != line)
36 sc = sc->find_broken_piece (line);
40 /* now: !sc || (sc && sc->get_system () == line) */
44 /* now: sc && sc->get_system () == line */
46 return sc->self_scm ();
49 We don't return SCM_UNDEFINED for
50 suicided grobs, for two reasons
52 - it doesn't work (strange disappearing objects)
54 - it forces us to mark the parents of a grob, leading to
55 a huge recursion in the GC routine.
58 if (sc->common_refpoint (line, X_AXIS)
59 && sc->common_refpoint (line, Y_AXIS))
61 return sc->self_scm ();
66 return sc->self_scm ();
72 Do break substitution in S, using CRITERION. Return new value.
73 CRITERION is either a SMOB pointer to the desired line, or a number
74 representing the break direction. Do not modify SRC.
76 It is rather tightly coded, since it takes a lot of time; it is
77 one of the top functions in the profile.
79 We don't pass break_criterion as a parameter, since it is
80 `constant', but takes up stack space.
82 It would be nice if we could do this in-place partially. We now
83 generate a lot of garbage.
86 do_break_substitution (SCM src)
90 if (unsmob_grob (src))
91 return substitute_grob (unsmob_grob (src));
92 else if (ly_c_vector_p (src))
94 int len = SCM_VECTOR_LENGTH (src);
95 SCM nv = scm_c_make_vector (len, SCM_UNDEFINED);
96 for (int i = 0; i < len; i++)
98 SCM si = scm_int2num (i);
99 scm_vector_set_x (nv, si,
100 do_break_substitution (scm_vector_ref (src, si)));
103 else if (scm_is_pair (src))
106 UGH! breaks on circular lists.
108 SCM newcar = do_break_substitution (scm_car (src));
109 SCM oldcdr = scm_cdr (src);
111 if (newcar == SCM_UNDEFINED
112 && (scm_is_pair (oldcdr) || oldcdr == SCM_EOL))
115 This is tail-recursion, ie.
117 return do_break_substution (cdr);
119 We don't want to rely on the compiler to do this. Without
120 tail-recursion, this easily crashes with a stack overflow. */
125 return scm_cons (newcar, do_break_substitution (oldcdr));
135 Perform substitution on GROB_LIST using a constant amount of stack.
138 substitute_grob_list (SCM grob_list)
143 for (SCM s = grob_list; scm_is_pair (s); s = scm_cdr (s))
145 SCM n = substitute_grob (unsmob_grob (scm_car (s)));
147 if (n != SCM_UNDEFINED)
149 *tail = scm_cons (n, SCM_EOL);
150 tail = SCM_CDRLOC (*tail);
160 forall b in broken-childs:
161 forall p in properties:
162 forall g in p (if grob-list):
165 for spanners since this is O (SYSTEMCOUNT * GROBCOUNT), and SYSTEMCOUNT =
166 O (GROBCOUNT), we have a quadratic algorithm. --for a single spanner
168 This is problematic: with large (long) scores, the costs can be
169 significant; especially all-elements in System, can become huge. For
170 a typical 50 page score, it requires running through a 100k list 50
175 forall p in properties:
178 put grob list in array,
180 reorder array so spanners are separate -- O (grobcount)
182 find first and last indexes of grobs on a specific system
184 for items this is O (itemcount)
186 for spanners this is O (sum-of spanner-system-ranges)
188 perform the substitution O (sum-of spanner-system-ranges)
191 The complexity is harder to determine, but should be subquadratic;
193 For the situation above, we run through the entire 100k list once,
194 and also (more or less) once through the item part of the 100k (say
195 98k elements) of the list.
198 These timings were measured without -O2.
200 lehre, before 28.98 seconds, after: 27.91 seconds, 3.5 %.
202 coriolan, before 2:30, after: 1:59. Increase of 20%.
204 moz-k498-p1, before 24.10, after: 19.790s, Increase of 18%
211 spanner_system_range (Spanner* sp)
215 if (System*st = sp->get_system ())
217 rv = Slice (st->rank_, st->rank_);
221 if (sp->broken_intos_.size ())
222 rv = Slice (sp->broken_intos_[0]->get_system ()->rank_,
223 sp->broken_intos_.top ()->get_system ()->rank_);
229 item_system_range (Item* it)
231 if (System*st = it->get_system ())
232 return Slice (st->rank_, st->rank_);
238 Item *bi = it->find_prebroken_piece (d);
239 if (bi && bi->get_system ())
240 sr.add_point (bi->get_system ()->rank_);
242 while (flip (&d)!= LEFT);
248 grob_system_range (Grob *g)
250 if (Spanner*s = dynamic_cast<Spanner*>(g))
251 return spanner_system_range (s);
252 else if (Item* it = dynamic_cast<Item*> (g))
253 return item_system_range (it);
260 struct Substitution_entry
266 void set (Grob*g, Slice sr)
270 duh, don't support scores with more than 32000 systems.
275 overflow if we don't treat this specially.
286 Substitution_entry ()
292 int length () { return right_ - left_ ; }
294 item_compare (void const * a , void const * b)
296 return ((Substitution_entry*)a)->left_ -
297 ((Substitution_entry*)b)->left_;
301 spanner_compare (void const * a , void const * b)
303 return ((Substitution_entry*)a)->length () -
304 ((Substitution_entry*)b)->length ();
311 Spanner::fast_fubstitute_grob_list (SCM sym,
314 int len = scm_ilength (grob_list);
317 Only do this complicated thing for large lists. This has the added
318 advantage that we won't screw up the ordering for elements in
319 alignments (which typically don't have more than 10 grobs.)
327 TODO : should not free it some time?
329 static Substitution_entry * vec;
334 vec = (Substitution_entry*) realloc (vec, sizeof (Substitution_entry) * len);
338 Slice system_range = spanner_system_range (this);
340 Array<Slice> it_indices;
341 Array<Slice> sp_indices;
342 for (int i = 0; i <= system_range.length (); i++)
344 it_indices.push (Slice (len, 0));
345 sp_indices.push (Slice (len, 0));
351 for (SCM s = grob_list; scm_is_pair (s); s = scm_cdr (s))
353 Grob * g = unsmob_grob (scm_car (s));
355 Slice sr = grob_system_range (g);
356 sr.intersect (system_range);
359 if (dynamic_cast<Spanner*>(g))
363 else if (dynamic_cast<Item*> (g))
368 vec[idx].set (g, sr);
371 qsort (vec, it_index,
372 sizeof (Substitution_entry), &Substitution_entry::item_compare);
374 Array<Slice> *arrs[] = {
375 &it_indices, &sp_indices
378 for (int i = 0; i < it_index ;i++)
380 for (int j = vec[i].left_; j <= vec[i].right_; j++)
382 it_indices[j - system_range[LEFT]].add_point (i);
387 sorting vec[sp_index.. len]
388 is a waste of time -- the staff-spanners screw up the
389 ordering, since they go across the entire score.
391 for (int i = sp_indices.size (); i--;)
392 sp_indices[i]= Slice (sp_index, len-1);
395 assert (it_index <= sp_index);
397 assert (broken_intos_.size () == system_range.length () + 1);
398 for (int i = 0; i < broken_intos_.size (); i++)
400 Grob * sc = broken_intos_[i];
401 System * l = sc->get_system ();
402 set_break_subsititution (l ? l->self_scm (): SCM_UNDEFINED);
404 SCM newval = SCM_EOL;
405 SCM * tail = &newval;
407 for (int k = 0; k < 2;k++)
408 for (int j = (*arrs[k])[i][LEFT]; j <= (*arrs[k])[i][RIGHT]; j++)
410 SCM subs = substitute_grob (vec[j].grob_);
411 if (subs!= SCM_UNDEFINED)
413 *tail = scm_cons (subs, SCM_EOL);
415 tail = SCM_CDRLOC (*tail);
422 printf ("%d (%d), sp %d (%d)\n",
423 it_indices [i].length (), it_index,
424 sp_indices[i].length () , len -sp_index);
427 SCM l1 = substitute_grob_list (grob_list);
428 assert (scm_ilength (l1) == scm_ilength (newval));
435 if (sym == ly_symbol2scm ("all-elements"))
436 sc->mutable_property_alist_
437 = scm_assq_remove_x (sc->mutable_property_alist_,
438 ly_symbol2scm ("all-elements"));
440 sc->mutable_property_alist_ = scm_acons (sym, newval,
441 sc->mutable_property_alist_);
449 Although the substitution can be written as
451 property_alist = do_substitution (other_property_alist),
453 we have a special function here: we want to invoke a special
454 function for lists of grobs. These can be very long for large
455 orchestral scores (eg. 1M elements). do_break_substitution () can
456 recurse many levels, taking lots of stack space.
458 This becomes a problem if lily is linked against guile with
459 pthreads. pthreads impose small limits on the stack size.
462 substitute_mutable_property_alist (SCM alist)
464 SCM grob_list_p = ly_scheme_function ("grob-list?");
468 for (SCM s = alist; scm_is_pair (s); s = scm_cdr (s))
470 SCM sym = scm_caar (s);
471 SCM val = scm_cdar (s);
472 SCM type = scm_object_property (sym, ly_symbol2scm ("backend-type?"));
474 if (type == grob_list_p)
475 val = substitute_grob_list (val);
477 val = do_break_substitution (val);
480 if (val != SCM_UNDEFINED)
483 for ly:grob? properties, SCM_UNDEFINED could leak out
484 through ly:grob-property
486 *tail = scm_cons (scm_cons (sym, val), SCM_EOL);
487 tail = SCM_CDRLOC (*tail);
495 Spanner::substitute_one_mutable_property (SCM sym,
498 SCM type = scm_object_property (sym, ly_symbol2scm ("backend-type?"));
501 bool fast_done = false;
502 SCM grob_list_p = ly_scheme_function ("grob-list?");
503 if (type == grob_list_p)
504 fast_done = s->fast_fubstitute_grob_list (sym, val);
507 for (int i = 0; i < s->broken_intos_ .size (); i++)
509 Grob * sc = s->broken_intos_[i];
510 System * l = sc->get_system ();
511 set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
513 SCM newval = (type == grob_list_p)
514 ? substitute_grob_list (val)
515 : do_break_substitution (val);
518 For the substitution of a single property, we tack the result onto
519 mutable_property_alist_ ; mutable_property_alist_ is empty after
520 Grob::Grob (Grob const&), except that System has all-elements set,
521 as a side product of typeset_grob () on newly copied spanners.
523 Here we clear that list explicitly to free some memory and
524 counter some of the confusion I encountered while debugging
529 if (sym == ly_symbol2scm ("all-elements"))
530 sc->mutable_property_alist_
531 = scm_assq_remove_x (sc->mutable_property_alist_,
532 ly_symbol2scm ("all-elements"));
534 sc->mutable_property_alist_ = scm_cons (scm_cons (sym, newval),
535 sc->mutable_property_alist_);