Message ID | m3sjmlewbe.fsf@redhat.com |
---|---|
State | New |
Headers | show |
On 10/21/2011 07:53 PM, Dodji Seketeli wrote: > - do > + while (mx - mn> 1) > { > md = (mx + mn) / 2; > if (MAP_START_LOCATION (LINEMAPS_MACRO_MAP_AT (set, md))> line) > mn = md; > else > mx = md; > - } while (mx - mn> 1); > + } > + > + /* There are cases where mx - mn = 1 and where the map we want is > + mn. Let's not miss it. */ > + if (MAP_START_LOCATION (LINEMAPS_MACRO_MAP_AT (set, mn))<= line) > + mx = mn; I think a better fix to your binary search algorithm would be to change mn = md; to be mn = md + 1; since you've eliminated md as a possibility. And then change the test to (mn < mx). Jason
diff --git a/libcpp/line-map.c b/libcpp/line-map.c index 352d697..ecfcfd0 100644 --- a/libcpp/line-map.c +++ b/libcpp/line-map.c @@ -588,14 +588,19 @@ linemap_macro_map_lookup (struct line_maps *set, source_location line) mn = 0; } - do + while (mx - mn > 1) { md = (mx + mn) / 2; if (MAP_START_LOCATION (LINEMAPS_MACRO_MAP_AT (set, md)) > line) mn = md; else mx = md; - } while (mx - mn > 1); + } + + /* There are cases where mx - mn = 1 and where the map we want is + mn. Let's not miss it. */ + if (MAP_START_LOCATION (LINEMAPS_MACRO_MAP_AT (set, mn)) <= line) + mx = mn; LINEMAPS_MACRO_CACHE (set) = mx; result = LINEMAPS_MACRO_MAP_AT (set, LINEMAPS_MACRO_CACHE (set));