#46 qcachegrind: unterminated loop in libviews/treemap.cpp

closed-fixed
nobody
None
5
2011-09-01
2011-06-26
Wez Furlong
No

For some dimensions, the treemap code falls into an infinite loop because it doesn't adjust the usedWidth parameter.

This simple change allows it to make forward progress when the display is a couple of pixels too large for the available width (3 in my case)

Index: libviews/treemap.cpp

--- libviews/treemap.cpp (revision 1238414)
+++ libviews/treemap.cpp (working copy)
@@ -368,9 +368,12 @@
while(qAbs(maxWidth - usedWidth) > 3 * fm->maxWidth()) {
int halfPos = (bottomPos + breakPos)/2;
int halfWidth = fm->width(text, halfPos);
- if (halfWidth < maxWidth)
+ if (halfWidth < maxWidth) {
bottomPos = halfPos;
- else {
+ if (usedWidth > maxWidth) {
+ usedWidth--;
+ }
+ } else {
breakPos = halfPos;
usedWidth = halfWidth;
}

Discussion

  • Thanks for the patch. Strange, this code never was a problem on Linux.
    The progress should be to reduce the length of the interval [bottomPos,breakPos].
    So a better solution is to stop if the interval is small enough. Does the following
    patch also work for you?

    diff --git a/libviews/treemap.cpp b/libviews/treemap.cpp
    index 4732389..da3ac64 100644
    --- a/libviews/treemap.cpp
    +++ b/libviews/treemap.cpp
    @@ -362,18 +362,19 @@ int findBreak(int& breakPos, QString text, QFontMetrics* fm, int maxWidth)
    if (usedWidth < maxWidth)
    return usedWidth;

    - // now lower breakPos until best position is found.
    - // first by binary search, resulting in a position a little bit too large
    + // binary search for best break position in [bottomPos, breakPos].
    + // We want the result of the binary search to be a bit too large
    int bottomPos = 0;
    - while(qAbs(maxWidth - usedWidth) > 3 * fm->maxWidth()) {
    + while(1) {
    int halfPos = (bottomPos + breakPos)/2;
    int halfWidth = fm->width(text, halfPos);
    - if (halfWidth < maxWidth)
    - bottomPos = halfPos;
    - else {
    - breakPos = halfPos;
    - usedWidth = halfWidth;
    + if (halfWidth < maxWidth) {
    + bottomPos = halfPos+1;
    + continue;
    }
    + breakPos = halfPos;
    + usedWidth = halfWidth;
    + if (breakPos - bottomPos <3) break;
    }

     
  • Wez Furlong
    Wez Furlong
    2011-06-28

    Your patch works for me; thanks!

     
  • Closing. Fix was committed as r1238681 on Jun 28.

     
    • status: open --> closed-fixed