-#include <stdio.h>
-#include <stdlib.h>
+#include <cstdio>
+#include <cstdlib>
-#include "grob.hh"
#include "item.hh"
-#include "spanner.hh"
-#include "system.hh"
+#include "system.hh"
-static SCM break_criterion;
+static SCM break_criterion;
void
set_break_subsititution (SCM criterion)
{
}
/*
- Perform the substitution for a single grob.
- */
+ Perform the substitution for a single grob.
+*/
SCM
substitute_grob (Grob *sc)
{
- if (SCM_INUMP (break_criterion))
+ if (scm_is_integer (break_criterion))
{
- Item * i = dynamic_cast<Item*> (sc);
+ Item *i = dynamic_cast<Item *> (sc);
Direction d = to_dir (break_criterion);
if (i && i->break_status_dir () != d)
{
}
else
{
- System * line
- = dynamic_cast<System*> (unsmob_grob (break_criterion));
+ System *line
+ = dynamic_cast<System *> (unsmob_grob (break_criterion));
if (sc->get_system () != line)
{
sc = sc->find_broken_piece (line);
-
}
-
+
/* now: !sc || (sc && sc->get_system () == line) */
if (!sc)
return SCM_UNDEFINED;
/* now: sc && sc->get_system () == line */
if (!line)
- return sc->self_scm();
+ return sc->self_scm ();
/*
We don't return SCM_UNDEFINED for
- it forces us to mark the parents of a grob, leading to
a huge recursion in the GC routine.
- */
-
- /*
- This was introduced in 1.3.49 as a measure to prevent
- programming errors. It looks rather expensive (?).
-
- TODO:
-
- benchmark , document when (what kind of programming
- errors) this happens.
*/
+
if (sc->common_refpoint (line, X_AXIS)
&& sc->common_refpoint (line, Y_AXIS))
{
return SCM_UNDEFINED;
}
- return sc->self_scm();
+ return sc->self_scm ();
}
-
-
/*
Do break substitution in S, using CRITERION. Return new value.
CRITERION is either a SMOB pointer to the desired line, or a number
do_break_substitution (SCM src)
{
again:
-
+
if (unsmob_grob (src))
+ return substitute_grob (unsmob_grob (src));
+ else if (scm_is_vector (src))
{
- return substitute_grob (unsmob_grob (src));
- }
- else if (gh_vector_p (src))
- {
- int l = SCM_VECTOR_LENGTH (src);
- SCM nv = scm_c_make_vector (l, SCM_UNDEFINED);
-
- for (int i =0 ; i< l ; i++)
+ int len = scm_c_vector_length (src);
+ SCM nv = scm_c_make_vector (len, SCM_UNDEFINED);
+ for (int i = 0; i < len; i++)
{
SCM si = scm_int2num (i);
- scm_vector_set_x (nv, si, do_break_substitution (scm_vector_ref (src, si)));
+ scm_vector_set_x (nv, si,
+ do_break_substitution (scm_vector_ref (src, si)));
}
}
- else if (ly_pair_p (src))
+ else if (scm_is_pair (src))
{
/*
UGH! breaks on circular lists.
*/
- SCM newcar = do_break_substitution (ly_car (src));
- SCM oldcdr = ly_cdr (src);
-
+ SCM newcar = do_break_substitution (scm_car (src));
+ SCM oldcdr = scm_cdr (src);
+
if (newcar == SCM_UNDEFINED
- && (gh_pair_p (oldcdr) || oldcdr == SCM_EOL))
+ && (scm_is_pair (oldcdr) || oldcdr == SCM_EOL))
{
/*
- This is tail-recursion, ie.
-
+ This is tail-recursion, ie.
+
return do_break_substution (cdr);
We don't want to rely on the compiler to do this. Without
tail-recursion, this easily crashes with a stack overflow. */
- src = oldcdr;
+ src = oldcdr;
goto again;
}
return src;
}
-
/*
Perform substitution on GROB_LIST using a constant amount of stack.
- */
+*/
SCM
substitute_grob_list (SCM grob_list)
{
SCM l = SCM_EOL;
- SCM * tail = &l;
+ SCM *tail = &l;
- for (SCM s = grob_list; gh_pair_p (s); s = gh_cdr (s))
+ for (SCM s = grob_list; scm_is_pair (s); s = scm_cdr (s))
{
- SCM n= substitute_grob (unsmob_grob (gh_car (s)));
+ SCM n = substitute_grob (unsmob_grob (scm_car (s)));
if (n != SCM_UNDEFINED)
{
- *tail = gh_cons (n, SCM_EOL);
- tail = SCM_CDRLOC(*tail);
+ *tail = scm_cons (n, SCM_EOL);
+ tail = SCM_CDRLOC (*tail);
}
}
We don't do
forall b in broken-childs:
- forall p in properties:
- forall g in p (if grob-list):
- g := substitute (g)
+ forall p in properties:
+ forall g in p (if grob-list):
+ g := substitute (g)
- for spanners since this is O(SYSTEMCOUNT * GROBCOUNT), and SYSTEMCOUNT =
- O(GROBCOUNT), we have a quadratic algorithm. --for a single spanner
+ for spanners since this is O (SYSTEMCOUNT * GROBCOUNT), and SYSTEMCOUNT =
+ O (GROBCOUNT), we have a quadratic algorithm. --for a single spanner
This is problematic: with large (long) scores, the costs can be
significant; especially all-elements in System, can become huge. For
a typical 50 page score, it requires running through a 100k list 50
times.
-
+
Instead:
forall p in properties:
- (if grob list)
+ (if grob list)
- put grob list in array,
+ put grob list in array,
- reorder array so spanners are separate -- O(grobcount)
-
- find first and last indexes of grobs on a specific system
+ reorder array so spanners are separate -- O (grobcount)
- for items this is O(itemcount)
+ find first and last indexes of grobs on a specific system
- for spanners this is O(sum-of spanner-system-ranges)
+ for items this is O (itemcount)
- perform the substitution O(sum-of spanner-system-ranges)
+ for spanners this is O (sum-of spanner-system-ranges)
+
+ perform the substitution O (sum-of spanner-system-ranges)
The complexity is harder to determine, but should be subquadratic;
For the situation above, we run through the entire 100k list once,
and also (more or less) once through the item part of the 100k (say
- 98k elements) of the list.
+ 98k elements) of the list.
-These timings were measured without -O2.
+ These timings were measured without -O2.
- lehre, before 28.98 seconds, after: 27.91 seconds, 3.5 %.
+ lehre, before 28.98 seconds, after: 27.91 seconds, 3.5 %.
coriolan, before 2:30, after: 1:59. Increase of 20%.
moz-k498-p1, before 24.10, after: 19.790s, Increase of 18%
-
-
*/
-
Slice
-spanner_system_range (Spanner* sp)
+spanner_system_range (Spanner *sp)
{
Slice rv;
-
- if (System*st = sp->get_system())
+
+ if (System *st = sp->get_system ())
{
rv = Slice (st->rank_, st->rank_);
}
- else
+ else
{
- if (sp->broken_intos_.size())
- rv = Slice (sp->broken_intos_[0]->get_system()->rank_,
- sp->broken_intos_.top()->get_system()->rank_);
+ if (sp->broken_intos_.size ())
+ rv = Slice (sp->broken_intos_[0]->get_system ()->rank_,
+ sp->broken_intos_.top ()->get_system ()->rank_);
}
return rv;
}
Slice
-item_system_range (Item* it)
+item_system_range (Item *it)
{
- if (System*st= it->get_system())
+ if (System *st = it->get_system ())
return Slice (st->rank_, st->rank_);
Slice sr;
do
{
Item *bi = it->find_prebroken_piece (d);
- if (bi && bi->get_system())
- sr.add_point (bi->get_system()->rank_);
+ if (bi && bi->get_system ())
+ sr.add_point (bi->get_system ()->rank_);
}
- while (flip(&d)!=LEFT);
-
+ while (flip (&d) != LEFT);
+
return sr;
}
Slice
grob_system_range (Grob *g)
{
- if (Spanner*s = dynamic_cast<Spanner*>(g))
- return spanner_system_range (s);
- else if (Item* it = dynamic_cast<Item*> (g))
- return item_system_range (it);
- else
- return Slice();
+ if (Spanner *s = dynamic_cast<Spanner *> (g))
+ return spanner_system_range (s);
+ else if (Item *it = dynamic_cast<Item *> (g))
+ return item_system_range (it);
+ else
+ return Slice ();
}
-
-
struct Substitution_entry
{
- Grob * grob_;
+ Grob *grob_;
short left_;
short right_;
-
- void set (Grob*g, Slice sr)
+
+ void set (Grob *g, Slice sr)
{
grob_ = g;
/*
{
/*
overflow if we don't treat this specially.
- */
+ */
left_ = 1;
right_ = -1;
}
right_ = sr[RIGHT];
}
}
- Substitution_entry()
+ Substitution_entry ()
{
- grob_ =0;
+ grob_ = 0;
left_ = right_ = -2;
}
-
- int length () { return right_ - left_ ; }
+
+ int length () { return right_ - left_; }
static int
- item_compare (void const * a , void const * b)
+ item_compare (void const *a, void const *b)
{
- return ((Substitution_entry*)a)->left_ -
- ((Substitution_entry*)b)->left_;
+ return ((Substitution_entry *)a)->left_
+ - ((Substitution_entry *)b)->left_;
}
-
+
static int
- spanner_compare (void const * a , void const * b)
+ spanner_compare (void const *a, void const *b)
{
- return ((Substitution_entry*)a)->length() -
- ((Substitution_entry*)b)->length ();
+ return ((Substitution_entry *)a)->length ()
+ - ((Substitution_entry *)b)->length ();
}
};
-
-
bool
Spanner::fast_fubstitute_grob_list (SCM sym,
SCM grob_list)
Only do this complicated thing for large lists. This has the added
advantage that we won't screw up the ordering for elements in
alignments (which typically don't have more than 10 grobs.)
- */
-
+ */
+
if (len < 300)
return false;
-
/*
- TODO : should not free it some time?
- */
- static Substitution_entry * vec;
+ TODO : should not free it some time?
+ */
+ static Substitution_entry *vec;
static int vec_room;
if (vec_room < len)
{
- vec = (Substitution_entry*) realloc (vec, sizeof (Substitution_entry) * len);
+ vec = (Substitution_entry *) realloc (vec, sizeof (Substitution_entry) * len);
vec_room = len;
}
-
+
Slice system_range = spanner_system_range (this);
Array<Slice> it_indices;
it_indices.push (Slice (len, 0));
sp_indices.push (Slice (len, 0));
}
-
-
+
int sp_index = len;
int it_index = 0;
- for (SCM s = grob_list; gh_pair_p (s); s = gh_cdr (s))
+ for (SCM s = grob_list; scm_is_pair (s); s = scm_cdr (s))
{
- Grob * g = unsmob_grob (gh_car(s));
+ Grob *g = unsmob_grob (scm_car (s));
Slice sr = grob_system_range (g);
sr.intersect (system_range);
int idx = 0;
- if (dynamic_cast<Spanner*>(g))
+ if (dynamic_cast<Spanner *> (g))
{
idx =--sp_index;
}
- else if (dynamic_cast<Item*> (g))
+ else if (dynamic_cast<Item *> (g))
{
idx = it_index++;
}
qsort (vec, it_index,
sizeof (Substitution_entry), &Substitution_entry::item_compare);
- Array<Slice> *arrs[] = {
- &it_indices, &sp_indices
- };
-
- for (int i = 0; i < it_index ;i++)
- {
- for (int j = vec[i].left_; j <= vec[i].right_; j++)
- {
- it_indices[j - system_range[LEFT]].add_point (i);
- }
- }
-
- /*
- sorting vec[sp_index.. len]
- is a waste of time -- the staff-spanners screw up the
- ordering, since they go across the entire score.
- */
- for (int i = sp_indices.size(); i--;)
- sp_indices[i]= Slice (sp_index, len-1);
-
-
+ Array<Slice> *arrs[]
+ = {
+ &it_indices, &sp_indices
+ };
+
+ for (int i = 0; i < it_index;i++)
+ {
+ for (int j = vec[i].left_; j <= vec[i].right_; j++)
+ {
+ it_indices[j - system_range[LEFT]].add_point (i);
+ }
+ }
+
+ /*
+ sorting vec[sp_index.. len]
+ is a waste of time -- the staff-spanners screw up the
+ ordering, since they go across the entire score.
+ */
+ for (int i = sp_indices.size (); i--;)
+ sp_indices[i] = Slice (sp_index, len - 1);
+
assert (it_index <= sp_index);
- assert (broken_intos_.size () == system_range.length () + 1);
- for (int i = 0; i < broken_intos_.size(); i++)
+ assert (broken_intos_.size () == system_range.length () + 1);
+ for (int i = 0; i < broken_intos_.size (); i++)
{
- Grob * sc = broken_intos_[i];
- System * l = sc->get_system ();
- set_break_subsititution (l ? l->self_scm(): SCM_UNDEFINED);
+ Grob *sc = broken_intos_[i];
+ System *l = sc->get_system ();
+ set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
SCM newval = SCM_EOL;
- SCM * tail = &newval;
+ SCM *tail = &newval;
- for (int k = 0; k < 2;k++)
+ for (int k = 0; k < 2;k++)
for (int j = (*arrs[k])[i][LEFT]; j <= (*arrs[k])[i][RIGHT]; j++)
{
- SCM subs =substitute_grob (vec[j].grob_);
- if (subs!= SCM_UNDEFINED)
+ SCM subs = substitute_grob (vec[j].grob_);
+ if (subs != SCM_UNDEFINED)
{
*tail = scm_cons (subs, SCM_EOL);
-
- tail = SCM_CDRLOC(*tail);
- }
+ tail = SCM_CDRLOC (*tail);
+ }
}
-
+
#ifdef PARANOIA
-
+
printf ("%d (%d), sp %d (%d)\n",
it_indices [i].length (), it_index,
- sp_indices[i].length() , len -sp_index);
-
+ sp_indices[i].length (), len -sp_index);
+
{
- SCM l1 =substitute_grob_list (grob_list);
+ SCM l1 = substitute_grob_list (grob_list);
assert (scm_ilength (l1) == scm_ilength (newval));
}
#endif
+ /*
+ see below.
+ */
+ if (sym == ly_symbol2scm ("all-elements"))
+ sc->mutable_property_alist_
+ = scm_assq_remove_x (sc->mutable_property_alist_,
+ ly_symbol2scm ("all-elements"));
+
sc->mutable_property_alist_ = scm_acons (sym, newval,
sc->mutable_property_alist_);
}
return true;
}
-
-SCM grob_list_p;
-
/*
Although the substitution can be written as
we have a special function here: we want to invoke a special
function for lists of grobs. These can be very long for large
- orchestral scores (eg. 1M elements). do_break_substitution() can
+ orchestral scores (eg. 1M elements). do_break_substitution () can
recurse many levels, taking lots of stack space.
This becomes a problem if lily is linked against guile with
pthreads. pthreads impose small limits on the stack size.
- */
+*/
SCM
substitute_mutable_property_alist (SCM alist)
{
- if (!grob_list_p)
- grob_list_p = scm_c_eval_string ("grob-list?");
+ SCM grob_list_p = ly_lily_module_constant ("grob-list?");
SCM l = SCM_EOL;
SCM *tail = &l;
- for (SCM s = alist; gh_pair_p (s); s = gh_cdr (s))
+ for (SCM s = alist; scm_is_pair (s); s = scm_cdr (s))
{
- SCM sym = gh_caar(s);
- SCM val = gh_cdar(s);
+ SCM sym = scm_caar (s);
+ SCM val = scm_cdar (s);
SCM type = scm_object_property (sym, ly_symbol2scm ("backend-type?"));
if (type == grob_list_p)
else
val = do_break_substitution (val);
- *tail = gh_cons (gh_cons (sym, val), SCM_EOL);
- tail = SCM_CDRLOC (*tail);
+ if (val != SCM_UNDEFINED)
+ {
+ /*
+ for ly:grob? properties, SCM_UNDEFINED could leak out
+ through ly:grob-property
+ */
+ *tail = scm_cons (scm_cons (sym, val), SCM_EOL);
+ tail = SCM_CDRLOC (*tail);
+ }
}
-
return l;
}
-
void
Spanner::substitute_one_mutable_property (SCM sym,
SCM val)
{
SCM type = scm_object_property (sym, ly_symbol2scm ("backend-type?"));
- Spanner*s = this;
-
+ Spanner *s = this;
+
bool fast_done = false;
+ SCM grob_list_p = ly_lily_module_constant ("grob-list?");
if (type == grob_list_p)
fast_done = s->fast_fubstitute_grob_list (sym, val);
- if (!fast_done)
- for (int i = 0; i < s->broken_intos_ .size (); i++)
+ if (!fast_done)
+ for (int i = 0; i < s->broken_intos_.size (); i++)
{
- Grob * sc = s->broken_intos_[i];
- System * l = sc->get_system ();
+ Grob *sc = s->broken_intos_[i];
+ System *l = sc->get_system ();
set_break_subsititution (l ? l->self_scm () : SCM_UNDEFINED);
SCM newval = (type == grob_list_p)
? substitute_grob_list (val)
- : do_break_substitution(val);
+ : do_break_substitution (val);
+
+ /*
+ For the substitution of a single property, we tack the result onto
+ mutable_property_alist_ ; mutable_property_alist_ is empty after
+ Grob::Grob (Grob const&), except that System has all-elements set,
+ as a side product of typeset_grob () on newly copied spanners.
+
+ Here we clear that list explicitly to free some memory and
+ counter some of the confusion I encountered while debugging
+ another problem
+
+ (hwn 4/2/04)
+ */
+ if (sym == ly_symbol2scm ("all-elements"))
+ sc->mutable_property_alist_
+ = scm_assq_remove_x (sc->mutable_property_alist_,
+ ly_symbol2scm ("all-elements"));
sc->mutable_property_alist_ = scm_cons (scm_cons (sym, newval),
sc->mutable_property_alist_);
}
}
-
+
projects / lilypond.git / blobdiff