9 static SCM break_criterion;
11 set_break_subsititution (SCM criterion)
13 break_criterion = criterion;
17 Perform the substitution for a single grob.
20 substitute_grob (Grob *sc)
22 if (SCM_INUMP (break_criterion))
24 Item * i = dynamic_cast<Item*> (sc);
25 Direction d = to_dir (break_criterion);
26 if (i && i->break_status_dir () != d)
28 Item *br = i->find_prebroken_piece (d);
29 return (br) ? br->self_scm () : SCM_UNDEFINED;
35 = dynamic_cast<System*> (unsmob_grob (break_criterion));
36 if (sc->get_system () != line)
38 sc = sc->find_broken_piece (line);
42 /* now: !sc || (sc && sc->get_system () == line) */
46 /* now: sc && sc->get_system () == line */
48 return sc->self_scm();
51 We don't return SCM_UNDEFINED for
52 suicided grobs, for two reasons
54 - it doesn't work (strange disappearing objects)
56 - it forces us to mark the parents of a grob, leading to
57 a huge recursion in the GC routine.
61 This was introduced in 1.3.49 as a measure to prevent
62 programming errors. It looks rather expensive (?).
66 benchmark , document when (what kind of programming
69 if (sc->common_refpoint (line, X_AXIS)
70 && sc->common_refpoint (line, Y_AXIS))
72 return sc->self_scm ();
77 return sc->self_scm();
83 Do break substitution in S, using CRITERION. Return new value.
84 CRITERION is either a SMOB pointer to the desired line, or a number
85 representing the break direction. Do not modify SRC.
87 It is rather tightly coded, since it takes a lot of time; it is
88 one of the top functions in the profile.
90 We don't pass break_criterion as a parameter, since it is
91 `constant', but takes up stack space.
93 It would be nice if we could do this in-place partially. We now
94 generate a lot of garbage.
97 do_break_substitution (SCM src)
101 if (unsmob_grob (src))
103 return substitute_grob (unsmob_grob (src));
105 else if (gh_vector_p (src))
107 int l = SCM_VECTOR_LENGTH (src);
108 SCM nv = scm_c_make_vector (l, SCM_UNDEFINED);
110 for (int i =0 ; i< l ; i++)
112 SCM si = scm_int2num (i);
113 scm_vector_set_x (nv, si, do_break_substitution (scm_vector_ref (src, si)));
116 else if (ly_pair_p (src))
119 UGH! breaks on circular lists.
121 SCM newcar = do_break_substitution (ly_car (src));
122 SCM oldcdr = ly_cdr (src);
124 if (newcar == SCM_UNDEFINED
125 && (gh_pair_p (oldcdr) || oldcdr == SCM_EOL))
128 This is tail-recursion, ie.
130 return do_break_substution (cdr);
132 We don't want to rely on the compiler to do this. Without
133 tail-recursion, this easily crashes with a stack overflow. */
138 return scm_cons (newcar, do_break_substitution (oldcdr));
148 Perform substitution on GROB_LIST using a constant amount of stack.
151 substitute_grob_list (SCM grob_list)
156 for (SCM s = grob_list; gh_pair_p (s); s = gh_cdr (s))
158 SCM n= substitute_grob (unsmob_grob (gh_car (s)));
160 if (n != SCM_UNDEFINED)
162 *tail = gh_cons (n, SCM_EOL);
163 tail = SCM_CDRLOC(*tail);
173 forall b in broken-childs:
174 forall p in properties:
175 forall g in p (if grob-list):
178 for spanners since this is O(SYSTEMCOUNT * GROBCOUNT), and SYSTEMCOUNT =
179 O(GROBCOUNT), we have a quadratic algorithm. --for a single spanner
181 This is problematic: with large (long) scores, the costs can be
182 significant; especially all-elements in System, can become huge. For
183 a typical 50 page score, it requires running through a 100k list 50
188 forall p in properties:
191 put grob list in array,
193 reorder array so spanners are separate -- O(grobcount)
195 find first and last indexes of grobs on a specific system
197 for items this is O(itemcount)
199 for spanners this is O(sum-of spanner-system-ranges)
201 perform the substitution O(sum-of spanner-system-ranges)
204 The complexity is harder to determine, but should be subquadratic;
206 For the situation above, we run through the entire 100k list once,
207 and also (more or less) once through the item part of the 100k (say
208 98k elements) of the list.
211 These timings were measured without -O2.
213 lehre, before 28.98 seconds, after: 27.91 seconds, 3.5 %.
215 coriolan, before 2:30, after: 1:59. Increase of 20%.
217 moz-k498-p1, before 24.10, after: 19.790s, Increase of 18%
224 spanner_system_range (Spanner* sp)
228 if (System*st = sp->get_system())
230 rv = Slice (st->rank_, st->rank_);
234 if (sp->broken_intos_.size())
235 rv = Slice (sp->broken_intos_[0]->get_system()->rank_,
236 sp->broken_intos_.top()->get_system()->rank_);
242 item_system_range (Item* it)
244 if (System*st= it->get_system())
245 return Slice (st->rank_, st->rank_);
251 Item *bi = it->find_prebroken_piece (d);
252 if (bi && bi->get_system())
253 sr.add_point (bi->get_system()->rank_);
255 while (flip(&d)!=LEFT);
261 grob_system_range (Grob *g)
263 if (Spanner*s = dynamic_cast<Spanner*>(g))
264 return spanner_system_range (s);
265 else if (Item* it = dynamic_cast<Item*> (g))
266 return item_system_range (it);
273 struct Substitution_entry
279 void set (Grob*g, Slice sr)
283 duh, don't support scores with more than 32000 systems.
288 overflow if we don't treat this specially.
305 int length () { return right_ - left_ ; }
307 item_compare (void const * a , void const * b)
309 return ((Substitution_entry*)a)->left_ -
310 ((Substitution_entry*)b)->left_;
314 spanner_compare (void const * a , void const * b)
316 return ((Substitution_entry*)a)->length() -
317 ((Substitution_entry*)b)->length ();
324 Spanner::fast_fubstitute_grob_list (SCM sym,
327 int len = scm_ilength (grob_list);
330 Only do this complicated thing for large lists. This has the added
331 advantage that we won't screw up the ordering for elements in
332 alignments (which typically don't have more than 10 grobs.)
340 TODO : should not free it some time?
342 static Substitution_entry * vec;
347 vec = (Substitution_entry*) realloc (vec, sizeof (Substitution_entry) * len);
351 Slice system_range = spanner_system_range (this);
353 Array<Slice> it_indices;
354 Array<Slice> sp_indices;
355 for (int i = 0; i <= system_range.length (); i++)
357 it_indices.push (Slice (len, 0));
358 sp_indices.push (Slice (len, 0));
364 for (SCM s = grob_list; gh_pair_p (s); s = gh_cdr (s))
366 Grob * g = unsmob_grob (gh_car(s));
368 Slice sr = grob_system_range (g);
369 sr.intersect (system_range);
372 if (dynamic_cast<Spanner*>(g))
376 else if (dynamic_cast<Item*> (g))
381 vec[idx].set (g, sr);
384 qsort (vec, it_index,
385 sizeof (Substitution_entry), &Substitution_entry::item_compare);
387 Array<Slice> *arrs[] = {
388 &it_indices, &sp_indices
391 for (int i = 0; i < it_index ;i++)
393 for (int j = vec[i].left_; j <= vec[i].right_; j++)
395 it_indices[j - system_range[LEFT]].add_point (i);
400 sorting vec[sp_index.. len]
401 is a waste of time -- the staff-spanners screw up the
402 ordering, since they go across the entire score.
404 for (int i = sp_indices.size(); i--;)
405 sp_indices[i]= Slice (sp_index, len-1);
408 assert (it_index <= sp_index);
410 assert (broken_intos_.size () == system_range.length () + 1);
411 for (int i = 0; i < broken_intos_.size(); i++)
413 Grob * sc = broken_intos_[i];
414 System * l = sc->get_system ();
415 set_break_subsititution (l ? l->self_scm(): SCM_UNDEFINED);
417 SCM newval = SCM_EOL;
418 SCM * tail = &newval;
420 for (int k = 0; k < 2;k++)
421 for (int j = (*arrs[k])[i][LEFT]; j <= (*arrs[k])[i][RIGHT]; j++)
423 SCM subs =substitute_grob (vec[j].grob_);
424 if (subs!= SCM_UNDEFINED)
426 *tail = scm_cons (subs, SCM_EOL);
428 tail = SCM_CDRLOC(*tail);
435 printf ("%d (%d), sp %d (%d)\n",
436 it_indices [i].length (), it_index,
437 sp_indices[i].length() , len -sp_index);
440 SCM l1 =substitute_grob_list (grob_list);
441 assert (scm_ilength (l1) == scm_ilength (newval));
445 sc->mutable_property_alist_ = scm_acons (sym, newval,
446 sc->mutable_property_alist_);
456 Although the substitution can be written as
458 property_alist = do_substitution (other_property_alist),
460 we have a special function here: we want to invoke a special
461 function for lists of grobs. These can be very long for large
462 orchestral scores (eg. 1M elements). do_break_substitution() can
463 recurse many levels, taking lots of stack space.
465 This becomes a problem if lily is linked against guile with
466 pthreads. pthreads impose small limits on the stack size.
469 substitute_mutable_property_alist (SCM alist)
472 grob_list_p = scm_c_eval_string ("grob-list?");
476 for (SCM s = alist; gh_pair_p (s); s = gh_cdr (s))
478 SCM sym = gh_caar(s);
479 SCM val = gh_cdar(s);
480 SCM type = scm_object_property (sym, ly_symbol2scm ("backend-type?"));
482 if (type == grob_list_p)
483 val = substitute_grob_list (val);
485 val = do_break_substitution (val);
487 *tail = gh_cons (gh_cons (sym, val), SCM_EOL);
488 tail = SCM_CDRLOC (*tail);
496 Spanner::substitute_one_mutable_property (SCM sym,
499 SCM type = scm_object_property (sym, ly_symbol2scm ("backend-type?"));
502 bool fast_done = false;
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);
517 sc->mutable_property_alist_ = scm_cons (scm_cons (sym, newval),
518 sc->mutable_property_alist_);