• Mihai Popa's avatar
    Optimise the hit test algorithm · 89be24c6
    Mihai Popa authored
    Layout#getOffsetForHorizontal was running in O(n^2) time, where n is the
    length of the current line. The method is used when a touch event
    happens on a text line, to compute the cursor offset (and the character)
    where it happened. Although this is not an issue in common usecases,
    where the number of characters on a line is relatively small, this can
    be very inefficient as a consequence of Unicode containing 0-width
    (invisible) characters. Specifically, there are characters defining the
    text direction (LTR or RTL), which cause our algorithm to touch the
    worst case quadratic runtime. For example, a person is able to send a
    message containing a few visible characters, and also a lot of these
    direction changing invisible ones. When the receiver touches the message
    (causing the Layout#getOffsetForHorizontal method to be called), the
    receiver's application would become not responsive.
    
    This CL optimizes the method to run in O(n) worst case. This is achieved
    by computing the measurements of all line prefixes at first, which can
    be done in a single pass. Then, all the prefix measurement queries will
    be answered in O(1), rather than O(n) as it was happening before.
    
    Bug: 79215201
    Test: manual testing
    Change-Id: Ib66ef392c19c937718e7101f6d48fac3abe51ad0
    Merged-In: Ib66ef392c19c937718e7101f6d48fac3abe51ad0
    (cherry picked from commit 69b589b2)
    89be24c6
Name
Last commit
Last update
apct-tests/perftests Loading commit data...
api Loading commit data...
cmds Loading commit data...
config Loading commit data...
core Loading commit data...
data Loading commit data...
docs Loading commit data...
drm Loading commit data...
graphics/java/android Loading commit data...
keystore Loading commit data...
legacy-test Loading commit data...
libs Loading commit data...
location Loading commit data...
lowpan Loading commit data...
media Loading commit data...
native Loading commit data...
nfc-extras Loading commit data...
obex Loading commit data...
opengl/java Loading commit data...
packages Loading commit data...
proto Loading commit data...
rs Loading commit data...
samples/training/network-usage Loading commit data...
sax Loading commit data...
services Loading commit data...
telecomm/java Loading commit data...
telephony/java Loading commit data...
test-runner Loading commit data...
tests Loading commit data...
tools Loading commit data...
vr Loading commit data...
wifi Loading commit data...
Android.bp Loading commit data...
Android.mk Loading commit data...
CleanSpec.mk Loading commit data...
MODULE_LICENSE_APACHE2 Loading commit data...
NOTICE Loading commit data...
PREUPLOAD.cfg Loading commit data...
pathmap.mk Loading commit data...