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 qsort (vec + sp_index, len - sp_index,
401 sizeof (Substitution_entry), &Substitution_entry::spanner_compare);
403 This is a waste of time -- the staff-spanners screw up the
404 ordering, since they go across the entire score.
406 for (int i = sp_index; i < len ;i++)
409 for (int j = vec[i].left_; j <= vec[i].right_; j++)
411 sp_indices[j - system_range[LEFT]].add_point (i);
415 for (int i = sp_indices.size(); i--;)
416 sp_indices[i]= Slice (sp_index, len-1);
420 assert (it_index <= sp_index);
422 assert (broken_intos_.size () == system_range.length () + 1);
423 for (int i = 0; i < broken_intos_.size(); i++)
425 Grob * sc = broken_intos_[i];
426 System * l = sc->get_system ();
427 set_break_subsititution (l ? l->self_scm(): SCM_UNDEFINED);
429 SCM newval = SCM_EOL;
430 SCM * tail = &newval;
432 for (int k = 0; k < 2;k++)
433 for (int j = (*arrs[k])[i][LEFT]; j <= (*arrs[k])[i][RIGHT]; j++)
435 SCM subs =substitute_grob (vec[j].grob_);
436 if (subs!= SCM_UNDEFINED)
438 *tail = scm_cons (subs, SCM_EOL);
440 tail = SCM_CDRLOC(*tail);
447 printf ("%d (%d), sp %d (%d)\n",
448 it_indices [i].length (), it_index,
449 sp_indices[i].length() , len -sp_index);
452 SCM l1 =substitute_grob_list (grob_list);
453 assert (scm_ilength (l1) == scm_ilength (newval));
457 sc->mutable_property_alist_ = scm_acons (sym, newval,
458 sc->mutable_property_alist_);
468 Although the substitution can be written as
470 property_alist = do_substitution (other_property_alist),
472 we have a special function here: we want to invoke a special
473 function for lists of grobs. These can be very long for large
474 orchestral scores (eg. 1M elements). do_break_substitution() can
475 recurse many levels, taking lots of stack space.
477 This becomes a problem if lily is linked against guile with
478 pthreads. pthreads impose small limits on the stack size.
481 substitute_mutable_property_alist (SCM alist)
484 grob_list_p = scm_c_eval_string ("grob-list?");
488 for (SCM s = alist; gh_pair_p (s); s = gh_cdr (s))
490 SCM sym = gh_caar(s);
491 SCM val = gh_cdar(s);
492 SCM type = scm_object_property (sym, ly_symbol2scm ("backend-type?"));
494 if (type == grob_list_p)
495 val = substitute_grob_list (val);
497 val = do_break_substitution (val);
499 *tail = gh_cons (gh_cons (sym, val), SCM_EOL);
500 tail = SCM_CDRLOC (*tail);
508 Spanner::substitute_one_mutable_property (SCM sym,
511 SCM type = scm_object_property (sym, ly_symbol2scm ("backend-type?"));
514 bool fast_done = false;
515 if (type == grob_list_p)
516 fast_done = s->fast_fubstitute_grob_list (sym, val);
519 for (int i = 0; i < s->broken_intos_ .size (); i++)
521 Grob * sc = s->broken_intos_[i];
522 System * l = sc->get_system ();
523 set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
525 SCM newval = (type == grob_list_p)
526 ? substitute_grob_list (val)
527 : do_break_substitution(val);
529 sc->mutable_property_alist_ = scm_cons (scm_cons (sym, newval),
530 sc->mutable_property_alist_);