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 ();
70 Do break substitution in S, using CRITERION. Return new value.
71 CRITERION is either a SMOB pointer to the desired line, or a number
72 representing the break direction. Do not modify SRC.
74 It is rather tightly coded, since it takes a lot of time; it is
75 one of the top functions in the profile.
77 We don't pass break_criterion as a parameter, since it is
78 `constant', but takes up stack space.
80 It would be nice if we could do this in-place partially. We now
81 generate a lot of garbage.
84 do_break_substitution (SCM src)
88 if (unsmob_grob (src))
89 return substitute_grob (unsmob_grob (src));
90 else if (scm_is_vector (src))
92 int len = scm_c_vector_length (src);
93 SCM nv = scm_c_make_vector (len, SCM_UNDEFINED);
94 for (int i = 0; i < len; i++)
96 SCM si = scm_int2num (i);
97 scm_vector_set_x (nv, si,
98 do_break_substitution (scm_vector_ref (src, si)));
101 else if (scm_is_pair (src))
104 UGH! breaks on circular lists.
106 SCM newcar = do_break_substitution (scm_car (src));
107 SCM oldcdr = scm_cdr (src);
109 if (newcar == SCM_UNDEFINED
110 && (scm_is_pair (oldcdr) || oldcdr == SCM_EOL))
113 This is tail-recursion, ie.
115 return do_break_substution (cdr);
117 We don't want to rely on the compiler to do this. Without
118 tail-recursion, this easily crashes with a stack overflow. */
123 return scm_cons (newcar, do_break_substitution (oldcdr));
132 Perform substitution on GROB_LIST using a constant amount of stack.
135 substitute_grob_list (SCM grob_list)
140 for (SCM s = grob_list; scm_is_pair (s); s = scm_cdr (s))
142 SCM n = substitute_grob (unsmob_grob (scm_car (s)));
144 if (n != SCM_UNDEFINED)
146 *tail = scm_cons (n, SCM_EOL);
147 tail = SCM_CDRLOC (*tail);
157 forall b in broken-childs:
158 forall p in properties:
159 forall g in p (if grob-list):
162 for spanners since this is O (SYSTEMCOUNT * GROBCOUNT), and SYSTEMCOUNT =
163 O (GROBCOUNT), we have a quadratic algorithm. --for a single spanner
165 This is problematic: with large (long) scores, the costs can be
166 significant; especially all-elements in System, can become huge. For
167 a typical 50 page score, it requires running through a 100k list 50
172 forall p in properties:
175 put grob list in array,
177 reorder array so spanners are separate -- O (grobcount)
179 find first and last indexes of grobs on a specific system
181 for items this is O (itemcount)
183 for spanners this is O (sum-of spanner-system-ranges)
185 perform the substitution O (sum-of spanner-system-ranges)
188 The complexity is harder to determine, but should be subquadratic;
190 For the situation above, we run through the entire 100k list once,
191 and also (more or less) once through the item part of the 100k (say
192 98k elements) of the list.
195 These timings were measured without -O2.
197 lehre, before 28.98 seconds, after: 27.91 seconds, 3.5 %.
199 coriolan, before 2:30, after: 1:59. Increase of 20%.
201 moz-k498-p1, before 24.10, after: 19.790s, Increase of 18%
205 spanner_system_range (Spanner *sp)
209 if (System *st = sp->get_system ())
211 rv = Slice (st->rank_, st->rank_);
215 if (sp->broken_intos_.size ())
216 rv = Slice (sp->broken_intos_[0]->get_system ()->rank_,
217 sp->broken_intos_.top ()->get_system ()->rank_);
223 item_system_range (Item *it)
225 if (System *st = it->get_system ())
226 return Slice (st->rank_, st->rank_);
232 Item *bi = it->find_prebroken_piece (d);
233 if (bi && bi->get_system ())
234 sr.add_point (bi->get_system ()->rank_);
236 while (flip (&d)!= LEFT);
242 grob_system_range (Grob *g)
244 if (Spanner *s = dynamic_cast<Spanner *> (g))
245 return spanner_system_range (s);
246 else if (Item *it = dynamic_cast<Item *> (g))
247 return item_system_range (it);
252 struct Substitution_entry
258 void set (Grob *g, Slice sr)
262 duh, don't support scores with more than 32000 systems.
267 overflow if we don't treat this specially.
278 Substitution_entry ()
284 int length () { return right_ - left_; }
286 item_compare (void const *a, void const *b)
288 return ((Substitution_entry *)a)->left_
289 - ((Substitution_entry *)b)->left_;
293 spanner_compare (void const *a, void const *b)
295 return ((Substitution_entry *)a)->length ()
296 - ((Substitution_entry *)b)->length ();
301 Spanner::fast_fubstitute_grob_list (SCM sym,
304 int len = scm_ilength (grob_list);
307 Only do this complicated thing for large lists. This has the added
308 advantage that we won't screw up the ordering for elements in
309 alignments (which typically don't have more than 10 grobs.)
316 TODO : should not free it some time?
318 static Substitution_entry *vec;
323 vec = (Substitution_entry *) realloc (vec, sizeof (Substitution_entry) * len);
327 Slice system_range = spanner_system_range (this);
329 Array<Slice> it_indices;
330 Array<Slice> sp_indices;
331 for (int i = 0; i <= system_range.length (); i++)
333 it_indices.push (Slice (len, 0));
334 sp_indices.push (Slice (len, 0));
339 for (SCM s = grob_list; scm_is_pair (s); s = scm_cdr (s))
341 Grob *g = unsmob_grob (scm_car (s));
343 Slice sr = grob_system_range (g);
344 sr.intersect (system_range);
347 if (dynamic_cast<Spanner *> (g))
351 else if (dynamic_cast<Item *> (g))
356 vec[idx].set (g, sr);
359 qsort (vec, it_index,
360 sizeof (Substitution_entry), &Substitution_entry::item_compare);
364 &it_indices, &sp_indices
367 for (int i = 0; i < it_index;i++)
369 for (int j = vec[i].left_; j <= vec[i].right_; j++)
371 it_indices[j - system_range[LEFT]].add_point (i);
376 sorting vec[sp_index.. len]
377 is a waste of time -- the staff-spanners screw up the
378 ordering, since they go across the entire score.
380 for (int i = sp_indices.size (); i--;)
381 sp_indices[i]= Slice (sp_index, len - 1);
383 assert (it_index <= sp_index);
385 assert (broken_intos_.size () == system_range.length () + 1);
386 for (int i = 0; i < broken_intos_.size (); i++)
388 Grob *sc = broken_intos_[i];
389 System *l = sc->get_system ();
390 set_break_subsititution (l ? l->self_scm (): SCM_UNDEFINED);
392 SCM newval = SCM_EOL;
395 for (int k = 0; k < 2;k++)
396 for (int j = (*arrs[k])[i][LEFT]; j <= (*arrs[k])[i][RIGHT]; j++)
398 SCM subs = substitute_grob (vec[j].grob_);
399 if (subs!= SCM_UNDEFINED)
401 *tail = scm_cons (subs, SCM_EOL);
403 tail = SCM_CDRLOC (*tail);
410 printf ("%d (%d), sp %d (%d)\n",
411 it_indices [i].length (), it_index,
412 sp_indices[i].length (), len -sp_index);
415 SCM l1 = substitute_grob_list (grob_list);
416 assert (scm_ilength (l1) == scm_ilength (newval));
423 if (sym == ly_symbol2scm ("all-elements"))
424 sc->mutable_property_alist_
425 = scm_assq_remove_x (sc->mutable_property_alist_,
426 ly_symbol2scm ("all-elements"));
428 sc->mutable_property_alist_ = scm_acons (sym, newval,
429 sc->mutable_property_alist_);
436 Although the substitution can be written as
438 property_alist = do_substitution (other_property_alist),
440 we have a special function here: we want to invoke a special
441 function for lists of grobs. These can be very long for large
442 orchestral scores (eg. 1M elements). do_break_substitution () can
443 recurse many levels, taking lots of stack space.
445 This becomes a problem if lily is linked against guile with
446 pthreads. pthreads impose small limits on the stack size.
449 substitute_mutable_property_alist (SCM alist)
451 SCM grob_list_p = ly_lily_module_constant ("grob-list?");
455 for (SCM s = alist; scm_is_pair (s); s = scm_cdr (s))
457 SCM sym = scm_caar (s);
458 SCM val = scm_cdar (s);
459 SCM type = scm_object_property (sym, ly_symbol2scm ("backend-type?"));
461 if (type == grob_list_p)
462 val = substitute_grob_list (val);
464 val = do_break_substitution (val);
466 if (val != SCM_UNDEFINED)
469 for ly:grob? properties, SCM_UNDEFINED could leak out
470 through ly:grob-property
472 *tail = scm_cons (scm_cons (sym, val), SCM_EOL);
473 tail = SCM_CDRLOC (*tail);
480 Spanner::substitute_one_mutable_property (SCM sym,
483 SCM type = scm_object_property (sym, ly_symbol2scm ("backend-type?"));
486 bool fast_done = false;
487 SCM grob_list_p = ly_lily_module_constant ("grob-list?");
488 if (type == grob_list_p)
489 fast_done = s->fast_fubstitute_grob_list (sym, val);
492 for (int i = 0; i < s->broken_intos_ .size (); i++)
494 Grob *sc = s->broken_intos_[i];
495 System *l = sc->get_system ();
496 set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
498 SCM newval = (type == grob_list_p)
499 ? substitute_grob_list (val)
500 : do_break_substitution (val);
503 For the substitution of a single property, we tack the result onto
504 mutable_property_alist_ ; mutable_property_alist_ is empty after
505 Grob::Grob (Grob const&), except that System has all-elements set,
506 as a side product of typeset_grob () on newly copied spanners.
508 Here we clear that list explicitly to free some memory and
509 counter some of the confusion I encountered while debugging
514 if (sym == ly_symbol2scm ("all-elements"))
515 sc->mutable_property_alist_
516 = scm_assq_remove_x (sc->mutable_property_alist_,
517 ly_symbol2scm ("all-elements"));
519 sc->mutable_property_alist_ = scm_cons (scm_cons (sym, newval),
520 sc->mutable_property_alist_);