Use an R-Tree for operation recording

Change-Id: I1380ae53139d5f50a25ea5edb61ec8b6818112ca

10 files changed, 1936 insertions, 121 deletions

diff --git a/Source/WebCore/platform/graphics/android/context/GraphicsContextAndroid.cpp b/Source/WebCore/platform/graphics/android/context/GraphicsContextAndroid.cpp
index f2d1400..aceb82b 100644
--- a/Source/WebCore/platform/graphics/android/context/GraphicsContextAndroid.cpp
+++ b/Source/WebCore/platform/graphics/android/context/GraphicsContextAndroid.cpp
@@ -505,6 +505,8 @@ void GraphicsContext::translate(float x, float y)
 {
     if (paintingDisabled())
         return;
+    if (!x && !y)
+        return;
     platformContext()->translate(x, y);
 }
 
diff --git a/Source/WebCore/platform/graphics/android/context/GraphicsOperation.h b/Source/WebCore/platform/graphics/android/context/GraphicsOperation.h
index ae52b2b..3f39b38 100644
--- a/Source/WebCore/platform/graphics/android/context/GraphicsOperation.h
+++ b/Source/WebCore/platform/graphics/android/context/GraphicsOperation.h
@@ -100,7 +100,17 @@ public:
                   , DrawTextOperation
     } OperationType;
 
-    virtual bool apply(PlatformGraphicsContext* context) = 0;
+    Operation()
+        : m_state(0)
+    {}
+
+    PlatformGraphicsContext::State* m_state;
+    bool apply(PlatformGraphicsContext* context) {
+        if (m_state)
+            context->setRawState(m_state);
+        return applyImpl(context);
+    }
+    virtual bool applyImpl(PlatformGraphicsContext* context) = 0;
     virtual ~Operation() {}
     virtual OperationType type() { return UndefinedOperation; }
     virtual String parameters() { return ""; }
@@ -168,7 +178,7 @@ public:
 class BeginTransparencyLayer : public Operation {
 public:
     BeginTransparencyLayer(const float opacity) : m_opacity(opacity) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->beginTransparencyLayer(m_opacity);
         return true;
     }
@@ -179,7 +189,7 @@ private:
 class EndTransparencyLayer : public Operation {
 public:
     EndTransparencyLayer() {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->endTransparencyLayer();
         return true;
     }
@@ -187,7 +197,7 @@ public:
 };
 class Save : public Operation {
 public:
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->save();
         m_operations.apply(context);
         context->restore();
@@ -195,6 +205,7 @@ public:
     }
     virtual OperationType type() { return SaveOperation; }
     GraphicsOperationCollection* operations() { return &m_operations; }
+    FloatRect bounds;
 private:
     GraphicsOperationCollection m_operations;
 };
@@ -206,7 +217,7 @@ private:
 class SetAlpha : public Operation {
 public:
     SetAlpha(const float alpha) : m_alpha(alpha) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->setAlpha(m_alpha);
         return true;
     }
@@ -218,7 +229,7 @@ private:
 class SetCompositeOperation : public Operation {
 public:
     SetCompositeOperation(CompositeOperator op) : m_operator(op) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->setCompositeOperation(m_operator);
         return true;
     }
@@ -230,7 +241,7 @@ private:
 class SetFillColor : public Operation {
 public:
     SetFillColor(Color color) : m_color(color) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->setFillColor(m_color);
         return true;
     }
@@ -252,7 +263,7 @@ public:
         SkSafeRef(m_shader);
     }
     ~SetFillShader() { SkSafeUnref(m_shader); }
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->setFillShader(m_shader);
         return true;
     }
@@ -264,7 +275,7 @@ private:
 class SetLineCap : public Operation {
 public:
     SetLineCap(LineCap cap) : m_cap(cap) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->setLineCap(m_cap);
         return true;
     }
@@ -277,7 +288,7 @@ class SetLineDash : public Operation {
 public:
     SetLineDash(const DashArray& dashes, float dashOffset)
         : m_dashes(dashes), m_dashOffset(dashOffset) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->setLineDash(m_dashes, m_dashOffset);
         return true;
     }
@@ -290,7 +301,7 @@ private:
 class SetLineJoin : public Operation {
 public:
     SetLineJoin(LineJoin join) : m_join(join) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->setLineJoin(m_join);
         return true;
     }
@@ -302,7 +313,7 @@ private:
 class SetMiterLimit : public Operation {
 public:
     SetMiterLimit(float limit) : m_limit(limit) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->setMiterLimit(m_limit);
         return true;
     }
@@ -315,7 +326,7 @@ class SetShadow : public Operation {
 public:
     SetShadow(int radius, int dx, int dy, SkColor c)
         : m_radius(radius), m_dx(dx), m_dy(dy), m_color(c) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->setShadow(m_radius, m_dx, m_dy, m_color);
         return true;
     }
@@ -330,7 +341,7 @@ private:
 class SetShouldAntialias : public Operation {
 public:
     SetShouldAntialias(bool useAA) : m_useAA(useAA) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->setShouldAntialias(m_useAA);
         return true;
     }
@@ -342,7 +353,7 @@ private:
 class SetStrokeColor : public Operation {
 public:
     SetStrokeColor(const Color& c) : m_color(c) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->setStrokeColor(m_color);
         return true;
     }
@@ -357,7 +368,7 @@ public:
         SkSafeRef(m_shader);
     }
     ~SetStrokeShader() { SkSafeUnref(m_shader); }
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->setStrokeShader(m_shader);
         return true;
     }
@@ -369,7 +380,7 @@ private:
 class SetStrokeStyle : public Operation {
 public:
     SetStrokeStyle(StrokeStyle style) : m_style(style) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->setStrokeStyle(m_style);
         return true;
     }
@@ -381,7 +392,7 @@ private:
 class SetStrokeThickness : public Operation {
 public:
     SetStrokeThickness(float thickness) : m_thickness(thickness) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->setStrokeThickness(m_thickness);
         return true;
     }
@@ -397,7 +408,7 @@ private:
 class ConcatCTM : public Operation {
 public:
     ConcatCTM(const AffineTransform& affine) : m_matrix(affine) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->concatCTM(m_matrix);
         return true;
     }
@@ -409,7 +420,7 @@ private:
 class Rotate : public Operation {
 public:
     Rotate(float angleInRadians) : m_angle(angleInRadians) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->rotate(m_angle);
         return true;
     }
@@ -421,7 +432,7 @@ private:
 class Scale : public Operation {
 public:
     Scale(const FloatSize& size) : m_scale(size) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->scale(m_scale);
         return true;
     }
@@ -433,7 +444,7 @@ private:
 class Translate : public Operation {
 public:
     Translate(float x, float y) : m_x(x), m_y(y) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->translate(m_x, m_y);
         return true;
     }
@@ -451,7 +462,7 @@ class InnerRoundedRectClip : public Operation {
 public:
     InnerRoundedRectClip(const IntRect& rect, int thickness)
         : m_rect(rect), m_thickness(thickness) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->addInnerRoundedRectClip(m_rect, m_thickness);
         return true;
     }
@@ -464,10 +475,15 @@ private:
 class Clip : public Operation {
 public:
     Clip(const FloatRect& rect) : m_rect(rect) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         return context->clip(m_rect);
     }
     virtual OperationType type() { return ClipOperation; }
+    virtual String parameters() {
+        return String::format("[x=%.2f,y=%.2f,w=%.2f,h=%.2f]",
+                         m_rect.x(), m_rect.y(),
+                         m_rect.width(), m_rect.height());
+    }
 private:
     const FloatRect m_rect;
 };
@@ -477,7 +493,7 @@ public:
     ClipPath(const Path& path, bool clipout = false)
         : m_path(path), m_clipOut(clipout), m_hasWindRule(false) {}
     void setWindRule(WindRule rule) { m_windRule = rule; m_hasWindRule = true; }
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         if (m_hasWindRule) {
             return context->clipPath(m_path, m_windRule);
         }
@@ -497,7 +513,7 @@ private:
 class ClipOut : public Operation {
 public:
     ClipOut(const IntRect& rect) : m_rect(rect) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         return context->clipOut(m_rect);
     }
     virtual OperationType type() { return ClipOutOperation; }
@@ -508,7 +524,7 @@ private:
 class ClearRect : public Operation {
 public:
     ClearRect(const FloatRect& rect) : m_rect(rect) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->clearRect(m_rect);
         return true;
     }
@@ -526,7 +542,7 @@ public:
     DrawBitmapPattern(const SkBitmap& bitmap, const SkMatrix& matrix,
                       CompositeOperator op, const FloatRect& destRect)
         : m_bitmap(bitmap), m_matrix(matrix), m_operator(op), m_destRect(destRect) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->drawBitmapPattern(m_bitmap, m_matrix, m_operator, m_destRect);
         return true;
     }
@@ -544,7 +560,7 @@ public:
     DrawBitmapRect(const SkBitmap& bitmap, const SkIRect& srcR,
                    const SkRect& dstR, CompositeOperator op)
         : m_bitmap(bitmap), m_srcR(srcR), m_dstR(dstR), m_operator(op) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->drawBitmapRect(m_bitmap, &m_srcR, m_dstR, m_operator);
         return true;
     }
@@ -564,7 +580,7 @@ private:
 class DrawEllipse : public Operation {
 public:
     DrawEllipse(const IntRect& rect) : m_rect(rect) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->drawEllipse(m_rect);
         return true;
     }
@@ -577,7 +593,7 @@ class DrawLine : public Operation {
 public:
     DrawLine(const IntPoint& point1, const IntPoint& point2)
         : m_point1(point1), m_point2(point2) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->drawLine(m_point1, m_point2);
         return true;
     }
@@ -591,7 +607,7 @@ class DrawLineForText : public Operation {
 public:
     DrawLineForText(const FloatPoint& pt, float width)
         : m_point(pt), m_width(width) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->drawLineForText(m_point, m_width);
         return true;
     }
@@ -606,7 +622,7 @@ public:
     DrawLineForTextChecking(const FloatPoint& pt, float width,
                             GraphicsContext::TextCheckingLineStyle lineStyle)
         : m_point(pt), m_width(width), m_lineStyle(lineStyle) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->drawLineForTextChecking(m_point, m_width, m_lineStyle);
         return true;
     }
@@ -620,7 +636,7 @@ private:
 class DrawRect : public Operation {
 public:
     DrawRect(const IntRect& rect) : m_rect(rect) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->drawRect(m_rect);
         return true;
     }
@@ -633,7 +649,7 @@ class FillPath : public Operation {
 public:
     FillPath(const Path& pathToFill, WindRule fillRule)
         : m_path(pathToFill), m_fillRule(fillRule) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->fillPath(m_path, m_fillRule);
         return true;
     }
@@ -647,7 +663,7 @@ class FillRect : public Operation {
 public:
     FillRect(const FloatRect& rect) : m_rect(rect), m_hasColor(false) {}
     void setColor(Color c) { m_color = c; m_hasColor = true; }
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         if (m_hasColor)
              context->fillRect(m_rect, m_color);
         else
@@ -676,7 +692,7 @@ public:
         , m_bottomRight(bottomRight)
         , m_color(color)
     {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->fillRoundedRect(m_rect, m_topLeft, m_topRight,
                                  m_bottomLeft, m_bottomRight,
                                  m_color);
@@ -699,7 +715,7 @@ public:
         , m_startAngle(startAngle)
         , m_angleSpan(angleSpan)
     {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->strokeArc(m_rect, m_startAngle, m_angleSpan);
         return true;
     }
@@ -713,7 +729,7 @@ private:
 class StrokePath : public Operation {
 public:
     StrokePath(const Path& path) : m_path(path) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->strokePath(m_path);
         return true;
     }
@@ -727,7 +743,7 @@ class StrokeRect : public Operation {
 public:
     StrokeRect(const FloatRect& rect, float lineWidth)
         : m_rect(rect), m_lineWidth(lineWidth) {}
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         context->strokeRect(m_rect, m_lineWidth);
         return true;
     }
@@ -747,7 +763,7 @@ public:
         SkSafeRef(m_picture);
     }
     ~DrawComplexText() { SkSafeUnref(m_picture); }
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         if (!context->getCanvas())
             return true;
         context->getCanvas()->drawPicture(*m_picture);
@@ -776,7 +792,7 @@ public:
         m_picture = picture;
     }
     ~DrawText() { SkSafeUnref(m_picture); }
-    virtual bool apply(PlatformGraphicsContext* context) {
+    virtual bool applyImpl(PlatformGraphicsContext* context) {
         if (!context->getCanvas())
             return true;
         context->getCanvas()->drawPicture(*m_picture);
diff --git a/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContext.h b/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContext.h
index d30bac3..3056523 100644
--- a/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContext.h
+++ b/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContext.h
@@ -40,6 +40,8 @@ namespace WebCore {
 
 class PlatformGraphicsContext {
 public:
+    class State;
+
     PlatformGraphicsContext();
     virtual ~PlatformGraphicsContext();
     virtual bool isPaintingDisabled() = 0;
@@ -117,7 +119,7 @@ public:
     virtual void drawLine(const IntPoint& point1, const IntPoint& point2) = 0;
     virtual void drawLineForText(const FloatPoint& pt, float width) = 0;
     virtual void drawLineForTextChecking(const FloatPoint& pt, float width,
-                                 GraphicsContext::TextCheckingLineStyle) = 0;
+                                         GraphicsContext::TextCheckingLineStyle) = 0;
     virtual void drawRect(const IntRect& rect) = 0;
     virtual void fillPath(const Path& pathToFill, WindRule fillRule) = 0;
     virtual void fillRect(const FloatRect& rect) = 0;
@@ -139,9 +141,9 @@ public:
     virtual void strokeRect(const FloatRect& rect, float lineWidth) = 0;
 
     virtual SkCanvas* recordingCanvas() = 0;
-    virtual void endRecording(int type = 0) = 0;
+    virtual void endRecording(const SkRect& bounds) = 0;
 
-protected:
+    void setRawState(State* state) { m_state = state; }
 
     struct ShadowRec {
         SkScalar blur;
@@ -192,11 +194,11 @@ protected:
         friend class PlatformGraphicsContextSkia;
     };
 
+protected:
     virtual bool shadowsIgnoreTransforms() const = 0;
     void setupPaintCommon(SkPaint* paint) const;
     GraphicsContext* m_gc; // Back-ptr to our parent
 
-    struct State;
     WTF::Vector<State> m_stateStack;
     State* m_state;
 };
diff --git a/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContextRecording.cpp b/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContextRecording.cpp
index 6bbffcd..e64e886 100644
--- a/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContextRecording.cpp
+++ b/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContextRecording.cpp
@@ -5,29 +5,130 @@
 #include "PlatformGraphicsContextRecording.h"
 
 #include "AndroidLog.h"
+#include "FloatRect.h"
+#include "FloatQuad.h"
 #include "Font.h"
 #include "GraphicsContext.h"
 #include "GraphicsOperationCollection.h"
 #include "GraphicsOperation.h"
+#include "PlatformGraphicsContextSkia.h"
+#include "RTree.h"
+
+#include "wtf/NonCopyingSort.h"
 
 namespace WebCore {
 
+class RecordingData {
+public:
+    RecordingData(GraphicsOperation::Operation* ops, int orderBy)
+        : m_orderBy(orderBy)
+        , m_operation(ops)
+    {}
+    ~RecordingData() {
+        delete m_operation;
+    }
+
+    unsigned int m_orderBy;
+    GraphicsOperation::Operation* m_operation;
+};
+
+typedef RTree<RecordingData*, float, 2> RecordingTree;
+
+class RecordingImpl {
+public:
+    RecordingImpl()
+        : m_nodeCount(0)
+    {
+        m_states.reserveCapacity(50000);
+    }
+
+    ~RecordingImpl() {
+        clear();
+    }
+
+    void clear() {
+        RecordingTree::Iterator it;
+        for (m_tree.GetFirst(it); !m_tree.IsNull(it); m_tree.GetNext(it)) {
+            RecordingData* removeElem = m_tree.GetAt(it);
+            if (removeElem)
+                delete removeElem;
+        }
+        m_tree.RemoveAll();
+    }
+
+    RecordingTree m_tree;
+    Vector<PlatformGraphicsContext::State> m_states;
+    int m_nodeCount;
+};
+
+Recording::~Recording()
+{
+    delete m_recording;
+}
+
+static bool GatherSearchResults(RecordingData* data, void* context)
+{
+    ((Vector<RecordingData*>*)context)->append(data);
+    return true;
+}
+
+static bool CompareRecordingDataOrder(const RecordingData* a, const RecordingData* b)
+{
+    return a->m_orderBy < b->m_orderBy;
+}
+
+void Recording::draw(SkCanvas* canvas)
+{
+    if (!m_recording) {
+        ALOGW("No recording!");
+        return;
+    }
+    SkRect clip;
+    if (!canvas->getClipBounds(&clip)) {
+        ALOGW("Empty clip!");
+        return;
+    }
+    Vector<RecordingData*> nodes;
+    float searchMin[] = {clip.fLeft, clip.fTop};
+    float searchMax[] = {clip.fRight, clip.fBottom};
+    m_recording->m_tree.Search(searchMin, searchMax, GatherSearchResults, &nodes);
+    size_t count = nodes.size();
+    ALOGV("Drawing %d nodes out of %d", count, m_recording->m_nodeCount);
+    if (count) {
+        nonCopyingSort(nodes.begin(), nodes.end(), CompareRecordingDataOrder);
+        PlatformGraphicsContextSkia context(canvas);
+        for (size_t i = 0; i < count; i++)
+            nodes[i]->m_operation->apply(&context);
+    }
+    ALOGV("Using %dkb for state storage", (sizeof(PlatformGraphicsContext::State) * m_recording->m_states.size()) / 1024);
+}
+
+void Recording::setRecording(RecordingImpl* impl)
+{
+    if (m_recording == impl)
+        return;
+    if (m_recording)
+        delete m_recording;
+    m_recording = impl;
+}
+
 //**************************************
 // PlatformGraphicsContextRecording
 //**************************************
 
-PlatformGraphicsContextRecording::PlatformGraphicsContextRecording(GraphicsOperationCollection* picture)
+PlatformGraphicsContextRecording::PlatformGraphicsContextRecording(Recording* recording)
     : PlatformGraphicsContext()
     , mPicture(0)
-    , mPendingOperation(0)
+    , mRecording(recording)
+    , mOperationState(0)
 {
-    if (picture)
-        mGraphicsOperationStack.append(picture);
+    if (mRecording)
+        mRecording->setRecording(new RecordingImpl());
 }
 
 bool PlatformGraphicsContextRecording::isPaintingDisabled()
 {
-    return !mGraphicsOperationStack.size();
+    return !mRecording;
 }
 
 SkCanvas* PlatformGraphicsContextRecording::recordingCanvas()
@@ -37,13 +138,13 @@ SkCanvas* PlatformGraphicsContextRecording::recordingCanvas()
     return mPicture->beginRecording(0, 0, 0);
 }
 
-void PlatformGraphicsContextRecording::endRecording(int type)
+void PlatformGraphicsContextRecording::endRecording(const SkRect& bounds)
 {
     if (!mPicture)
         return;
     mPicture->endRecording();
     GraphicsOperation::DrawComplexText* text = new GraphicsOperation::DrawComplexText(mPicture);
-    appendDrawingOperation(text);
+    appendDrawingOperation(text, bounds);
     mPicture = 0;
 }
 
@@ -65,18 +166,18 @@ void PlatformGraphicsContextRecording::endTransparencyLayer()
 void PlatformGraphicsContextRecording::save()
 {
     PlatformGraphicsContext::save();
-    flushPendingOperations();
-    mPendingOperation = new GraphicsOperation::Save();
+    mRecordingStateStack.append(new GraphicsOperation::Save());
 }
 
 void PlatformGraphicsContextRecording::restore()
 {
     PlatformGraphicsContext::restore();
-    if (mPendingOperation) {
-        delete mPendingOperation;
-        mPendingOperation = 0;
-    } else
-        mGraphicsOperationStack.removeLast();
+    RecordingState state = mRecordingStateStack.last();
+    mRecordingStateStack.removeLast();
+    if (state.mHasDrawing)
+        appendDrawingOperation(state.mSaveOperation, state.mBounds);
+    else
+        delete state.mSaveOperation;
 }
 
 //**************************************
@@ -231,12 +332,16 @@ void PlatformGraphicsContextRecording::canvasClip(const Path& path)
 
 bool PlatformGraphicsContextRecording::clip(const FloatRect& rect)
 {
+    if (mRecordingStateStack.size())
+        mRecordingStateStack.last().clip(rect);
     appendStateOperation(new GraphicsOperation::Clip(rect));
     return true;
 }
 
 bool PlatformGraphicsContextRecording::clip(const Path& path)
 {
+    if (mRecordingStateStack.size())
+        mRecordingStateStack.last().clip(path.boundingRect());
     appendStateOperation(new GraphicsOperation::ClipPath(path));
     return true;
 }
@@ -262,6 +367,8 @@ bool PlatformGraphicsContextRecording::clipOut(const Path& path)
 
 bool PlatformGraphicsContextRecording::clipPath(const Path& pathToClip, WindRule clipRule)
 {
+    if (mRecordingStateStack.size())
+        mRecordingStateStack.last().clip(pathToClip.boundingRect());
     GraphicsOperation::ClipPath* operation = new GraphicsOperation::ClipPath(pathToClip);
     operation->setWindRule(clipRule);
     appendStateOperation(operation);
@@ -270,7 +377,7 @@ bool PlatformGraphicsContextRecording::clipPath(const Path& pathToClip, WindRule
 
 void PlatformGraphicsContextRecording::clearRect(const FloatRect& rect)
 {
-    appendDrawingOperation(new GraphicsOperation::ClearRect(rect));
+    appendDrawingOperation(new GraphicsOperation::ClearRect(rect), rect);
 }
 
 //**************************************
@@ -281,14 +388,16 @@ void PlatformGraphicsContextRecording::drawBitmapPattern(
         const SkBitmap& bitmap, const SkMatrix& matrix,
         CompositeOperator compositeOp, const FloatRect& destRect)
 {
-    appendDrawingOperation(new GraphicsOperation::DrawBitmapPattern(bitmap, matrix, compositeOp, destRect));
+    appendDrawingOperation(
+            new GraphicsOperation::DrawBitmapPattern(bitmap, matrix, compositeOp, destRect),
+            destRect);
 }
 
 void PlatformGraphicsContextRecording::drawBitmapRect(const SkBitmap& bitmap,
                                    const SkIRect* src, const SkRect& dst,
                                    CompositeOperator op)
 {
-    appendDrawingOperation(new GraphicsOperation::DrawBitmapRect(bitmap, *src, dst, op));
+    appendDrawingOperation(new GraphicsOperation::DrawBitmapRect(bitmap, *src, dst, op), dst);
 }
 
 void PlatformGraphicsContextRecording::drawConvexPolygon(size_t numPoints,
@@ -300,7 +409,7 @@ void PlatformGraphicsContextRecording::drawConvexPolygon(size_t numPoints,
 
 void PlatformGraphicsContextRecording::drawEllipse(const IntRect& rect)
 {
-    appendDrawingOperation(new GraphicsOperation::DrawEllipse(rect));
+    appendDrawingOperation(new GraphicsOperation::DrawEllipse(rect), rect);
 }
 
 void PlatformGraphicsContextRecording::drawFocusRing(const Vector<IntRect>& rects,
@@ -332,33 +441,39 @@ void PlatformGraphicsContextRecording::drawHighlightForText(
 void PlatformGraphicsContextRecording::drawLine(const IntPoint& point1,
                              const IntPoint& point2)
 {
-    appendDrawingOperation(new GraphicsOperation::DrawLine(point1, point2));
+    FloatRect bounds = FloatQuad(point1, point1, point2, point2).boundingBox();
+    float width = m_state->strokeThickness;
+    if (!width) width = 1;
+    bounds.inflate(width);
+    appendDrawingOperation(new GraphicsOperation::DrawLine(point1, point2), bounds);
 }
 
 void PlatformGraphicsContextRecording::drawLineForText(const FloatPoint& pt, float width)
 {
-    appendDrawingOperation(new GraphicsOperation::DrawLineForText(pt, width));
+    FloatRect bounds(pt.x(), pt.y(), width, m_state->strokeThickness);
+    appendDrawingOperation(new GraphicsOperation::DrawLineForText(pt, width), bounds);
 }
 
 void PlatformGraphicsContextRecording::drawLineForTextChecking(const FloatPoint& pt,
         float width, GraphicsContext::TextCheckingLineStyle lineStyle)
 {
-    appendDrawingOperation(new GraphicsOperation::DrawLineForTextChecking(pt, width, lineStyle));
+    FloatRect bounds(pt.x(), pt.y(), width, m_state->strokeThickness);
+    appendDrawingOperation(new GraphicsOperation::DrawLineForTextChecking(pt, width, lineStyle), bounds);
 }
 
 void PlatformGraphicsContextRecording::drawRect(const IntRect& rect)
 {
-    appendDrawingOperation(new GraphicsOperation::DrawRect(rect));
+    appendDrawingOperation(new GraphicsOperation::DrawRect(rect), rect);
 }
 
 void PlatformGraphicsContextRecording::fillPath(const Path& pathToFill, WindRule fillRule)
 {
-    appendDrawingOperation(new GraphicsOperation::FillPath(pathToFill, fillRule));
+    appendDrawingOperation(new GraphicsOperation::FillPath(pathToFill, fillRule), pathToFill.boundingRect());
 }
 
 void PlatformGraphicsContextRecording::fillRect(const FloatRect& rect)
 {
-    appendDrawingOperation(new GraphicsOperation::FillRect(rect));
+    appendDrawingOperation(new GraphicsOperation::FillRect(rect), rect);
 }
 
 void PlatformGraphicsContextRecording::fillRect(const FloatRect& rect,
@@ -366,7 +481,7 @@ void PlatformGraphicsContextRecording::fillRect(const FloatRect& rect,
 {
     GraphicsOperation::FillRect* operation = new GraphicsOperation::FillRect(rect);
     operation->setColor(color);
-    appendDrawingOperation(operation);
+    appendDrawingOperation(operation, rect);
 }
 
 void PlatformGraphicsContextRecording::fillRoundedRect(
@@ -375,45 +490,59 @@ void PlatformGraphicsContextRecording::fillRoundedRect(
         const Color& color)
 {
     appendDrawingOperation(new GraphicsOperation::FillRoundedRect(rect, topLeft,
-                 topRight, bottomLeft, bottomRight, color));
+                 topRight, bottomLeft, bottomRight, color), rect);
 }
 
 void PlatformGraphicsContextRecording::strokeArc(const IntRect& r, int startAngle,
                               int angleSpan)
 {
-    appendDrawingOperation(new GraphicsOperation::StrokeArc(r, startAngle, angleSpan));
+    appendDrawingOperation(new GraphicsOperation::StrokeArc(r, startAngle, angleSpan), r);
 }
 
 void PlatformGraphicsContextRecording::strokePath(const Path& pathToStroke)
 {
-    appendDrawingOperation(new GraphicsOperation::StrokePath(pathToStroke));
+    appendDrawingOperation(new GraphicsOperation::StrokePath(pathToStroke), pathToStroke.boundingRect());
 }
 
 void PlatformGraphicsContextRecording::strokeRect(const FloatRect& rect, float lineWidth)
 {
-    appendDrawingOperation(new GraphicsOperation::StrokeRect(rect, lineWidth));
+    FloatRect bounds = rect;
+    bounds.inflate(lineWidth);
+    appendDrawingOperation(new GraphicsOperation::StrokeRect(rect, lineWidth), bounds);
 }
 
-void PlatformGraphicsContextRecording::appendDrawingOperation(GraphicsOperation::Operation* operation)
+void PlatformGraphicsContextRecording::appendDrawingOperation(
+        GraphicsOperation::Operation* operation, const FloatRect& bounds)
 {
-    flushPendingOperations();
-    mGraphicsOperationStack.last()->adoptAndAppend(operation);
+    if (bounds.isEmpty()) {
+        ALOGW("Empty bounds for %s(%s)!", operation->name(), operation->parameters().ascii().data());
+        return;
+    }
+    if (mRecordingStateStack.size()) {
+        RecordingState& state = mRecordingStateStack.last();
+        state.mHasDrawing = true;
+        state.addBounds(bounds);
+        state.mSaveOperation->operations()->adoptAndAppend(operation);
+        return;
+    }
+    if (!mOperationState) {
+        mRecording->recording()->m_states.append(m_state->cloneInheritedProperties());
+        mOperationState = &mRecording->recording()->m_states.last();
+    }
+    operation->m_state = mOperationState;
+    RecordingData* data = new RecordingData(operation, mRecording->recording()->m_nodeCount++);
+    float min[] = {bounds.x(), bounds.y()};
+    float max[] = {bounds.maxX(), bounds.maxY()};
+    mRecording->recording()->m_tree.Insert(min, max, data);
 }
 
 void PlatformGraphicsContextRecording::appendStateOperation(GraphicsOperation::Operation* operation)
 {
-    if (mPendingOperation)
-        mPendingOperation->operations()->adoptAndAppend(operation);
-    else
-        mGraphicsOperationStack.last()->adoptAndAppend(operation);
-}
-
-void PlatformGraphicsContextRecording::flushPendingOperations()
-{
-    if (mPendingOperation) {
-        mGraphicsOperationStack.last()->adoptAndAppend(mPendingOperation);
-        mGraphicsOperationStack.append(mPendingOperation->operations());
-        mPendingOperation = 0;
+    if (mRecordingStateStack.size())
+        mRecordingStateStack.last().mSaveOperation->operations()->adoptAndAppend(operation);
+    else {
+        delete operation;
+        mOperationState = 0;
     }
 }
 
diff --git a/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContextRecording.h b/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContextRecording.h
index 4a202f9..95d4614 100644
--- a/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContextRecording.h
+++ b/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContextRecording.h
@@ -29,6 +29,9 @@
 #include "PlatformGraphicsContext.h"
 
 #include "GraphicsOperationCollection.h"
+#include "SkRefCnt.h"
+
+class SkCanvas;
 
 namespace WebCore {
 namespace GraphicsOperation {
@@ -36,15 +39,31 @@ class Operation;
 class Save;
 }
 
+class RecordingImpl;
+class Recording : public SkRefCnt {
+public:
+    Recording()
+        : m_recording(0)
+    {}
+    ~Recording();
+
+    void draw(SkCanvas* canvas);
+    void setRecording(RecordingImpl* impl);
+    RecordingImpl* recording() { return m_recording; }
+
+private:
+    RecordingImpl* m_recording;
+};
+
 class PlatformGraphicsContextRecording : public PlatformGraphicsContext {
 public:
-    PlatformGraphicsContextRecording(GraphicsOperationCollection* picture);
+    PlatformGraphicsContextRecording(Recording* picture);
     virtual ~PlatformGraphicsContextRecording() {}
     virtual bool isPaintingDisabled();
     virtual SkCanvas* getCanvas() { return 0; }
 
     virtual SkCanvas* recordingCanvas();
-    virtual void endRecording(int type = 0);
+    virtual void endRecording(const SkRect& bounds);
 
     virtual ContextType type() { return RecordingContext; }
 
@@ -105,7 +124,7 @@ public:
     virtual void drawLine(const IntPoint& point1, const IntPoint& point2);
     virtual void drawLineForText(const FloatPoint& pt, float width);
     virtual void drawLineForTextChecking(const FloatPoint& pt, float width,
-                                 GraphicsContext::TextCheckingLineStyle);
+                                         GraphicsContext::TextCheckingLineStyle);
     virtual void drawRect(const IntRect& rect);
     virtual void fillPath(const Path& pathToFill, WindRule fillRule);
     virtual void fillRect(const FloatRect& rect);
@@ -123,15 +142,48 @@ private:
         return false;
     }
 
-    void appendDrawingOperation(GraphicsOperation::Operation* operation);
+    void appendDrawingOperation(GraphicsOperation::Operation* operation, const FloatRect& bounds);
     void appendStateOperation(GraphicsOperation::Operation* operation);
-    void flushPendingOperations();
 
     SkPicture* mPicture;
     SkMatrix mCurrentMatrix;
 
-    Vector<GraphicsOperationCollection*> mGraphicsOperationStack;
-    GraphicsOperation::Save* mPendingOperation;
+    Recording* mRecording;
+    class RecordingState {
+    public:
+        RecordingState(GraphicsOperation::Save* saveOp)
+            : mSaveOperation(saveOp)
+            , mHasDrawing(false)
+            , mHasClip(false)
+        {}
+
+        RecordingState(const RecordingState& other)
+            : mSaveOperation(other.mSaveOperation)
+            , mHasDrawing(other.mHasDrawing)
+            , mHasClip(other.mHasClip)
+            , mBounds(other.mBounds)
+        {}
+
+        void addBounds(const FloatRect& bounds)
+        {
+            if (mHasClip)
+                return;
+            mBounds.unite(bounds);
+        }
+
+        void clip(const FloatRect& rect)
+        {
+            addBounds(rect);
+            mHasClip = true;
+        }
+
+        GraphicsOperation::Save* mSaveOperation;
+        bool mHasDrawing;
+        bool mHasClip;
+        FloatRect mBounds;
+    };
+    Vector<RecordingState> mRecordingStateStack;
+    State* mOperationState;
 };
 
 }
diff --git a/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContextSkia.h b/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContextSkia.h
index 7bb12ae..3c5e347 100644
--- a/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContextSkia.h
+++ b/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContextSkia.h
@@ -39,7 +39,7 @@ public:
 
     virtual ContextType type() { return PaintingContext; }
     virtual SkCanvas* recordingCanvas() { return mCanvas; }
-    virtual void endRecording(int type = 0) {}
+    virtual void endRecording(const SkRect& bounds) {}
 
     // FIXME: This is used by ImageBufferAndroid, which should really be
     //        managing the canvas lifecycle itself
@@ -87,7 +87,7 @@ public:
     virtual void drawLine(const IntPoint& point1, const IntPoint& point2);
     virtual void drawLineForText(const FloatPoint& pt, float width);
     virtual void drawLineForTextChecking(const FloatPoint& pt, float width,
-                                 GraphicsContext::TextCheckingLineStyle);
+                                         GraphicsContext::TextCheckingLineStyle);
     virtual void drawRect(const IntRect& rect);
     virtual void fillPath(const Path& pathToFill, WindRule fillRule);
     virtual void fillRect(const FloatRect& rect);
diff --git a/Source/WebCore/platform/graphics/android/context/RTree.h b/Source/WebCore/platform/graphics/android/context/RTree.h
new file mode 100644
index 0000000..cc4c856
--- /dev/null
+++ b/Source/WebCore/platform/graphics/android/context/RTree.h
@@ -0,0 +1,1588 @@
+#ifndef RTREE_H

+#define RTREE_H

+

+// NOTE This file compiles under MSVC 6 SP5 and MSVC .Net 2003 it may not work on other compilers without modification.

+

+// NOTE These next few lines may be win32 specific, you may need to modify them to compile on other platform

+#include <stdio.h>

+#include <math.h>

+#include <assert.h>

+#include <stdlib.h>

+

+#ifndef Min

+  #define Min(a,b) (((a)<(b))?(a):(b))

+#endif //Min

+#ifndef Max

+  #define Max(a,b) (((a)>(b))?(a):(b))

+#endif //Max

+

+//

+// RTree.h

+//

+

+#define RTREE_TEMPLATE template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>

+#define RTREE_QUAL RTree<DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES>

+

+#define RTREE_DONT_USE_MEMPOOLS // This version does not contain a fixed memory allocator, fill in lines with EXAMPLE to implement one.

+#define RTREE_USE_SPHERICAL_VOLUME // Better split classification, may be slower on some systems

+

+// Fwd decl

+class RTFileStream;  // File I/O helper class, look below for implementation and notes.

+

+/// \class RTree

+/// Implementation of RTree, a multidimensional bounding rectangle tree.

+/// Example usage: For a 3-dimensional tree use RTree<Object*, float, 3> myTree;

+///

+/// This modified, templated C++ version by Greg Douglas at Auran (http://www.auran.com)

+///

+/// DATATYPE Referenced data, should be int, void*, obj* etc. no larger than sizeof<void*> and simple type

+/// ELEMTYPE Type of element such as int or float

+/// NUMDIMS Number of dimensions such as 2 or 3

+/// ELEMTYPEREAL Type of element that allows fractional and large values such as float or double, for use in volume calcs

+///

+/// NOTES: Inserting and removing data requires the knowledge of its constant Minimal Bounding Rectangle.

+///        This version uses new/delete for nodes, I recommend using a fixed size allocator for efficiency.

+///        Instead of using a callback function for returned results, I recommend and efficient pre-sized, grow-only memory

+///        array similar to MFC CArray or STL Vector for returning search query result.

+///

+template<class DATATYPE, class ELEMTYPE, int NUMDIMS, 

+         class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

+class RTree

+{

+protected: 

+

+  struct Node;  // Fwd decl.  Used by other internal structs and iterator

+

+public:

+

+  // These constant must be declared after Branch and before Node struct

+  // Stuck up here for MSVC 6 compiler.  NSVC .NET 2003 is much happier.

+  enum

+  {

+    MAXNODES = TMAXNODES,                         ///< Max elements in node

+    MINNODES = TMINNODES,                         ///< Min elements in node

+  };

+

+

+public:

+

+  RTree();

+  virtual ~RTree();

+  

+  /// Insert entry

+  /// \param a_min Min of bounding rect

+  /// \param a_max Max of bounding rect

+  /// \param a_dataId Positive Id of data.  Maybe zero, but negative numbers not allowed.

+  void Insert(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE& a_dataId);

+  

+  /// Remove entry

+  /// \param a_min Min of bounding rect

+  /// \param a_max Max of bounding rect

+  /// \param a_dataId Positive Id of data.  Maybe zero, but negative numbers not allowed.

+  void Remove(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE& a_dataId);

+  

+  /// Find all within search rectangle

+  /// \param a_min Min of search bounding rect

+  /// \param a_max Max of search bounding rect

+  /// \param a_searchResult Search result array.  Caller should set grow size. Function will reset, not append to array.

+  /// \param a_resultCallback Callback function to return result.  Callback should return 'true' to continue searching

+  /// \param a_context User context to pass as parameter to a_resultCallback

+  /// \return Returns the number of entries found

+  int Search(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], bool a_resultCallback(DATATYPE a_data, void* a_context), void* a_context);

+  

+  /// Remove all entries from tree

+  void RemoveAll();

+

+  /// Count the data elements in this container.  This is slow as no internal counter is maintained.

+  int Count();

+

+  /// Load tree contents from file

+  bool Load(const char* a_fileName);

+  /// Load tree contents from stream

+  bool Load(RTFileStream& a_stream);

+

+  

+  /// Save tree contents to file

+  bool Save(const char* a_fileName);

+  /// Save tree contents to stream

+  bool Save(RTFileStream& a_stream);

+

+  /// Iterator is not remove safe.

+  class Iterator

+  {

+  private:

+  

+    enum { MAX_STACK = 32 }; //  Max stack size. Allows almost n^32 where n is number of branches in node

+    

+    struct StackElement

+    {

+      Node* m_node;

+      int m_branchIndex;

+    };

+    

+  public:

+  

+    Iterator()                                    { Init(); }

+

+    ~Iterator()                                   { }

+    

+    /// Is iterator invalid

+    bool IsNull()                                 { return (m_tos <= 0); }

+

+    /// Is iterator pointing to valid data

+    bool IsNotNull()                              { return (m_tos > 0); }

+

+    /// Access the current data element. Caller must be sure iterator is not NULL first.

+    DATATYPE& operator*()

+    {

+      ASSERT(IsNotNull());

+      StackElement& curTos = m_stack[m_tos - 1];

+      return curTos.m_node->m_branch[curTos.m_branchIndex].m_data;

+    } 

+

+    /// Access the current data element. Caller must be sure iterator is not NULL first.

+    const DATATYPE& operator*() const

+    {

+      ASSERT(IsNotNull());

+      StackElement& curTos = m_stack[m_tos - 1];

+      return curTos.m_node->m_branch[curTos.m_branchIndex].m_data;

+    } 

+

+    /// Find the next data element

+    bool operator++()                             { return FindNextData(); }

+

+    /// Get the bounds for this node

+    void GetBounds(ELEMTYPE a_min[NUMDIMS], ELEMTYPE a_max[NUMDIMS])

+    {

+      ASSERT(IsNotNull());

+      StackElement& curTos = m_stack[m_tos - 1];

+      Branch& curBranch = curTos.m_node->m_branch[curTos.m_branchIndex];

+      

+      for(int index = 0; index < NUMDIMS; ++index)

+      {

+        a_min[index] = curBranch.m_rect.m_min[index];

+        a_max[index] = curBranch.m_rect.m_max[index];

+      }

+    }

+

+    /// Reset iterator

+    void Init()                                   { m_tos = 0; }

+

+    /// Find the next data element in the tree (For internal use only)

+    bool FindNextData()

+    {

+      for(;;)

+      {

+        if(m_tos <= 0)

+        {

+          return false;

+        }

+        StackElement curTos = Pop(); // Copy stack top cause it may change as we use it

+

+        if(curTos.m_node->IsLeaf())

+        {

+          // Keep walking through data while we can

+          if(curTos.m_branchIndex+1 < curTos.m_node->m_count)

+          {

+            // There is more data, just point to the next one

+            Push(curTos.m_node, curTos.m_branchIndex + 1);

+            return true;

+          }

+          // No more data, so it will fall back to previous level

+        }

+        else

+        {

+          if(curTos.m_branchIndex+1 < curTos.m_node->m_count)

+          {

+            // Push sibling on for future tree walk

+            // This is the 'fall back' node when we finish with the current level

+            Push(curTos.m_node, curTos.m_branchIndex + 1);

+          }

+          // Since cur node is not a leaf, push first of next level to get deeper into the tree

+          Node* nextLevelnode = curTos.m_node->m_branch[curTos.m_branchIndex].m_child;

+          Push(nextLevelnode, 0);

+          

+          // If we pushed on a new leaf, exit as the data is ready at TOS

+          if(nextLevelnode->IsLeaf())

+          {

+            return true;

+          }

+        }

+      }

+    }

+

+    /// Push node and branch onto iteration stack (For internal use only)

+    void Push(Node* a_node, int a_branchIndex)

+    {

+      m_stack[m_tos].m_node = a_node;

+      m_stack[m_tos].m_branchIndex = a_branchIndex;

+      ++m_tos;

+      ASSERT(m_tos <= MAX_STACK);

+    }

+    

+    /// Pop element off iteration stack (For internal use only)

+    StackElement& Pop()

+    {

+      ASSERT(m_tos > 0);

+      --m_tos;

+      return m_stack[m_tos];

+    }

+

+    StackElement m_stack[MAX_STACK];              ///< Stack as we are doing iteration instead of recursion

+    int m_tos;                                    ///< Top Of Stack index

+  

+  };

+

+  /// Get 'first' for iteration

+  void GetFirst(Iterator& a_it)

+  {

+    a_it.Init();

+    Node* first = m_root;

+    while(first)

+    {

+      if(first->IsInternalNode() && first->m_count > 1)

+      {

+        a_it.Push(first, 1); // Descend sibling branch later

+      }

+      else if(first->IsLeaf())

+      {

+        if(first->m_count)

+        {

+          a_it.Push(first, 0);

+        }

+        break;

+      }

+      first = first->m_branch[0].m_child;

+    }

+  }  

+

+  /// Get Next for iteration

+  void GetNext(Iterator& a_it)                    { ++a_it; }

+

+  /// Is iterator NULL, or at end?

+  bool IsNull(Iterator& a_it)                     { return a_it.IsNull(); }

+

+  /// Get object at iterator position

+  DATATYPE& GetAt(Iterator& a_it)                 { return *a_it; }

+

+protected:

+

+  /// Minimal bounding rectangle (n-dimensional)

+  struct Rect

+  {

+    ELEMTYPE m_min[NUMDIMS];                      ///< Min dimensions of bounding box 

+    ELEMTYPE m_max[NUMDIMS];                      ///< Max dimensions of bounding box 

+  };

+

+  /// May be data or may be another subtree

+  /// The parents level determines this.

+  /// If the parents level is 0, then this is data

+  struct Branch

+  {

+    Rect m_rect;                                  ///< Bounds

+    union

+    {

+      Node* m_child;                              ///< Child node

+      DATATYPE m_data;                            ///< Data Id or Ptr

+    };

+  };

+

+  /// Node for each branch level

+  struct Node

+  {

+    bool IsInternalNode()                         { return (m_level > 0); } // Not a leaf, but a internal node

+    bool IsLeaf()                                 { return (m_level == 0); } // A leaf, contains data

+    

+    int m_count;                                  ///< Count

+    int m_level;                                  ///< Leaf is zero, others positive

+    Branch m_branch[MAXNODES];                    ///< Branch

+  };

+  

+  /// A link list of nodes for reinsertion after a delete operation

+  struct ListNode

+  {

+    ListNode* m_next;                             ///< Next in list

+    Node* m_node;                                 ///< Node

+  };

+

+  /// Variables for finding a split partition

+  struct PartitionVars

+  {

+    int m_partition[MAXNODES+1];

+    int m_total;

+    int m_minFill;

+    int m_taken[MAXNODES+1];

+    int m_count[2];

+    Rect m_cover[2];

+    ELEMTYPEREAL m_area[2];

+

+    Branch m_branchBuf[MAXNODES+1];

+    int m_branchCount;

+    Rect m_coverSplit;

+    ELEMTYPEREAL m_coverSplitArea;

+  }; 

+ 

+  Node* AllocNode();

+  void FreeNode(Node* a_node);

+  void InitNode(Node* a_node);

+  void InitRect(Rect* a_rect);

+  bool InsertRectRec(Rect* a_rect, const DATATYPE& a_id, Node* a_node, Node** a_newNode, int a_level);

+  bool InsertRect(Rect* a_rect, const DATATYPE& a_id, Node** a_root, int a_level);

+  Rect NodeCover(Node* a_node);

+  bool AddBranch(Branch* a_branch, Node* a_node, Node** a_newNode);

+  void DisconnectBranch(Node* a_node, int a_index);

+  int PickBranch(Rect* a_rect, Node* a_node);

+  Rect CombineRect(Rect* a_rectA, Rect* a_rectB);

+  void SplitNode(Node* a_node, Branch* a_branch, Node** a_newNode);

+  ELEMTYPEREAL RectSphericalVolume(Rect* a_rect);

+  ELEMTYPEREAL RectVolume(Rect* a_rect);

+  ELEMTYPEREAL CalcRectVolume(Rect* a_rect);

+  void GetBranches(Node* a_node, Branch* a_branch, PartitionVars* a_parVars);

+  void ChoosePartition(PartitionVars* a_parVars, int a_minFill);

+  void LoadNodes(Node* a_nodeA, Node* a_nodeB, PartitionVars* a_parVars);

+  void InitParVars(PartitionVars* a_parVars, int a_maxRects, int a_minFill);

+  void PickSeeds(PartitionVars* a_parVars);

+  void Classify(int a_index, int a_group, PartitionVars* a_parVars);

+  bool RemoveRect(Rect* a_rect, const DATATYPE& a_id, Node** a_root);

+  bool RemoveRectRec(Rect* a_rect, const DATATYPE& a_id, Node* a_node, ListNode** a_listNode);

+  ListNode* AllocListNode();

+  void FreeListNode(ListNode* a_listNode);

+  bool Overlap(Rect* a_rectA, Rect* a_rectB);

+  void ReInsert(Node* a_node, ListNode** a_listNode);

+  bool Search(Node* a_node, Rect* a_rect, int& a_foundCount, bool a_resultCallback(DATATYPE a_data, void* a_context), void* a_context);

+  void RemoveAllRec(Node* a_node);

+  void Reset();

+  void CountRec(Node* a_node, int& a_count);

+

+  bool SaveRec(Node* a_node, RTFileStream& a_stream);

+  bool LoadRec(Node* a_node, RTFileStream& a_stream);

+  

+  Node* m_root;                                    ///< Root of tree

+  ELEMTYPEREAL m_unitSphereVolume;                 ///< Unit sphere constant for required number of dimensions

+};

+

+

+// Because there is not stream support, this is a quick and dirty file I/O helper.

+// Users will likely replace its usage with a Stream implementation from their favorite API.

+class RTFileStream

+{

+  FILE* m_file;

+

+public:

+

+  

+  RTFileStream()

+  {

+    m_file = NULL;

+  }

+

+  ~RTFileStream()

+  {

+    Close();

+  }

+

+  bool OpenRead(const char* a_fileName)

+  {

+    m_file = fopen(a_fileName, "rb");

+    if(!m_file)

+    {

+      return false;

+    }

+    return true;

+  }

+

+  bool OpenWrite(const char* a_fileName)

+  {

+    m_file = fopen(a_fileName, "wb");

+    if(!m_file)

+    {

+      return false;

+    }

+    return true;

+  }

+

+  void Close()

+  {

+    if(m_file)

+    {

+      fclose(m_file);

+      m_file = NULL;

+    }

+  }

+

+  template< typename TYPE >

+  size_t Write(const TYPE& a_value)

+  {

+    ASSERT(m_file);

+    return fwrite((void*)&a_value, sizeof(a_value), 1, m_file);

+  }

+

+  template< typename TYPE >

+  size_t WriteArray(const TYPE* a_array, int a_count)

+  {

+    ASSERT(m_file);

+    return fwrite((void*)a_array, sizeof(TYPE) * a_count, 1, m_file);

+  }

+

+  template< typename TYPE >

+  size_t Read(TYPE& a_value)

+  {

+    ASSERT(m_file);

+    return fread((void*)&a_value, sizeof(a_value), 1, m_file);

+  }

+

+  template< typename TYPE >

+  size_t ReadArray(TYPE* a_array, int a_count)

+  {

+    ASSERT(m_file);

+    return fread((void*)a_array, sizeof(TYPE) * a_count, 1, m_file);

+  }

+};

+

+

+RTREE_TEMPLATE

+RTREE_QUAL::RTree()

+{

+  ASSERT(MAXNODES > MINNODES);

+  ASSERT(MINNODES > 0);

+

+

+  // We only support machine word size simple data type eg. integer index or object pointer.

+  // Since we are storing as union with non data branch

+  ASSERT(sizeof(DATATYPE) == sizeof(void*) || sizeof(DATATYPE) == sizeof(int));

+

+  // Precomputed volumes of the unit spheres for the first few dimensions

+  const float UNIT_SPHERE_VOLUMES[] = {

+    0.000000f, 2.000000f, 3.141593f, // Dimension  0,1,2

+    4.188790f, 4.934802f, 5.263789f, // Dimension  3,4,5

+    5.167713f, 4.724766f, 4.058712f, // Dimension  6,7,8

+    3.298509f, 2.550164f, 1.884104f, // Dimension  9,10,11

+    1.335263f, 0.910629f, 0.599265f, // Dimension  12,13,14

+    0.381443f, 0.235331f, 0.140981f, // Dimension  15,16,17

+    0.082146f, 0.046622f, 0.025807f, // Dimension  18,19,20 

+  };

+

+  m_root = AllocNode();

+  m_root->m_level = 0;

+  m_unitSphereVolume = (ELEMTYPEREAL)UNIT_SPHERE_VOLUMES[NUMDIMS];

+}

+

+

+RTREE_TEMPLATE

+RTREE_QUAL::~RTree()

+{

+  Reset(); // Free, or reset node memory

+}

+

+

+RTREE_TEMPLATE

+void RTREE_QUAL::Insert(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE& a_dataId)

+{

+#ifdef _DEBUG

+  for(int index=0; index<NUMDIMS; ++index)

+  {

+    ASSERT(a_min[index] <= a_max[index]);

+  }

+#endif //_DEBUG

+

+  Rect rect;

+  

+  for(int axis=0; axis<NUMDIMS; ++axis)

+  {

+    rect.m_min[axis] = a_min[axis];

+    rect.m_max[axis] = a_max[axis];

+  }

+  

+  InsertRect(&rect, a_dataId, &m_root, 0);

+}

+

+

+RTREE_TEMPLATE

+void RTREE_QUAL::Remove(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE& a_dataId)

+{

+#ifdef _DEBUG

+  for(int index=0; index<NUMDIMS; ++index)

+  {

+    ASSERT(a_min[index] <= a_max[index]);

+  }

+#endif //_DEBUG

+

+  Rect rect;

+  

+  for(int axis=0; axis<NUMDIMS; ++axis)

+  {

+    rect.m_min[axis] = a_min[axis];

+    rect.m_max[axis] = a_max[axis];

+  }

+

+  RemoveRect(&rect, a_dataId, &m_root);

+}

+

+

+RTREE_TEMPLATE

+int RTREE_QUAL::Search(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], bool a_resultCallback(DATATYPE a_data, void* a_context), void* a_context)

+{

+#ifdef _DEBUG

+  for(int index=0; index<NUMDIMS; ++index)

+  {

+    ASSERT(a_min[index] <= a_max[index]);

+  }

+#endif //_DEBUG

+

+  Rect rect;

+  

+  for(int axis=0; axis<NUMDIMS; ++axis)

+  {

+    rect.m_min[axis] = a_min[axis];

+    rect.m_max[axis] = a_max[axis];

+  }

+

+  // NOTE: May want to return search result another way, perhaps returning the number of found elements here.

+

+  int foundCount = 0;

+  Search(m_root, &rect, foundCount, a_resultCallback, a_context);

+

+  return foundCount;

+}

+

+

+RTREE_TEMPLATE

+int RTREE_QUAL::Count()

+{

+  int count = 0;

+  CountRec(m_root, count);

+  

+  return count;

+}

+

+

+

+RTREE_TEMPLATE

+void RTREE_QUAL::CountRec(Node* a_node, int& a_count)

+{

+  if(a_node->IsInternalNode())  // not a leaf node

+  {

+    for(int index = 0; index < a_node->m_count; ++index)

+    {

+      CountRec(a_node->m_branch[index].m_child, a_count);

+    }

+  }

+  else // A leaf node

+  {

+    a_count += a_node->m_count;

+  }

+}

+

+

+RTREE_TEMPLATE

+bool RTREE_QUAL::Load(const char* a_fileName)

+{

+  RemoveAll(); // Clear existing tree

+

+  RTFileStream stream;

+  if(!stream.OpenRead(a_fileName))

+  {

+    return false;

+  }

+

+  bool result = Load(stream);

+  

+  stream.Close();

+

+  return result;

+};

+

+

+

+RTREE_TEMPLATE

+bool RTREE_QUAL::Load(RTFileStream& a_stream)

+{

+  // Write some kind of header

+  int _dataFileId = ('R'<<0)|('T'<<8)|('R'<<16)|('E'<<24);

+  int _dataSize = sizeof(DATATYPE);

+  int _dataNumDims = NUMDIMS;

+  int _dataElemSize = sizeof(ELEMTYPE);

+  int _dataElemRealSize = sizeof(ELEMTYPEREAL);

+  int _dataMaxNodes = TMAXNODES;

+  int _dataMinNodes = TMINNODES;

+

+  int dataFileId = 0;

+  int dataSize = 0;

+  int dataNumDims = 0;

+  int dataElemSize = 0;

+  int dataElemRealSize = 0;

+  int dataMaxNodes = 0;

+  int dataMinNodes = 0;

+

+  a_stream.Read(dataFileId);

+  a_stream.Read(dataSize);

+  a_stream.Read(dataNumDims);

+  a_stream.Read(dataElemSize);

+  a_stream.Read(dataElemRealSize);

+  a_stream.Read(dataMaxNodes);

+  a_stream.Read(dataMinNodes);

+

+  bool result = false;

+

+  // Test if header was valid and compatible

+  if(    (dataFileId == _dataFileId) 

+      && (dataSize == _dataSize) 

+      && (dataNumDims == _dataNumDims) 

+      && (dataElemSize == _dataElemSize) 

+      && (dataElemRealSize == _dataElemRealSize) 

+      && (dataMaxNodes == _dataMaxNodes) 

+      && (dataMinNodes == _dataMinNodes) 

+    )

+  {

+    // Recursively load tree

+    result = LoadRec(m_root, a_stream);

+  }

+

+  return result;

+}

+

+

+RTREE_TEMPLATE

+bool RTREE_QUAL::LoadRec(Node* a_node, RTFileStream& a_stream)

+{

+  a_stream.Read(a_node->m_level);

+  a_stream.Read(a_node->m_count);

+

+  if(a_node->IsInternalNode())  // not a leaf node

+  {

+    for(int index = 0; index < a_node->m_count; ++index)

+    {

+      Branch* curBranch = &a_node->m_branch[index];

+

+      a_stream.ReadArray(curBranch->m_rect.m_min, NUMDIMS);

+      a_stream.ReadArray(curBranch->m_rect.m_max, NUMDIMS);

+

+      curBranch->m_child = AllocNode();

+      LoadRec(curBranch->m_child, a_stream);

+    }

+  }

+  else // A leaf node

+  {

+    for(int index = 0; index < a_node->m_count; ++index)

+    {

+      Branch* curBranch = &a_node->m_branch[index];

+

+      a_stream.ReadArray(curBranch->m_rect.m_min, NUMDIMS);

+      a_stream.ReadArray(curBranch->m_rect.m_max, NUMDIMS);

+

+      a_stream.Read(curBranch->m_data);

+    }

+  }

+

+  return true; // Should do more error checking on I/O operations

+}

+

+

+RTREE_TEMPLATE

+bool RTREE_QUAL::Save(const char* a_fileName)

+{

+  RTFileStream stream;

+  if(!stream.OpenWrite(a_fileName))

+  {

+    return false;

+  }

+

+  bool result = Save(stream);

+

+  stream.Close();

+

+  return result;

+}

+

+

+RTREE_TEMPLATE

+bool RTREE_QUAL::Save(RTFileStream& a_stream)

+{

+  // Write some kind of header

+  int dataFileId = ('R'<<0)|('T'<<8)|('R'<<16)|('E'<<24);

+  int dataSize = sizeof(DATATYPE);

+  int dataNumDims = NUMDIMS;

+  int dataElemSize = sizeof(ELEMTYPE);

+  int dataElemRealSize = sizeof(ELEMTYPEREAL);

+  int dataMaxNodes = TMAXNODES;

+  int dataMinNodes = TMINNODES;

+

+  a_stream.Write(dataFileId);

+  a_stream.Write(dataSize);

+  a_stream.Write(dataNumDims);

+  a_stream.Write(dataElemSize);

+  a_stream.Write(dataElemRealSize);

+  a_stream.Write(dataMaxNodes);

+  a_stream.Write(dataMinNodes);

+

+  // Recursively save tree

+  bool result = SaveRec(m_root, a_stream);

+  

+  return result;

+}

+

+

+RTREE_TEMPLATE

+bool RTREE_QUAL::SaveRec(Node* a_node, RTFileStream& a_stream)

+{

+  a_stream.Write(a_node->m_level);

+  a_stream.Write(a_node->m_count);

+

+  if(a_node->IsInternalNode())  // not a leaf node

+  {

+    for(int index = 0; index < a_node->m_count; ++index)

+    {

+      Branch* curBranch = &a_node->m_branch[index];

+

+      a_stream.WriteArray(curBranch->m_rect.m_min, NUMDIMS);

+      a_stream.WriteArray(curBranch->m_rect.m_max, NUMDIMS);

+

+      SaveRec(curBranch->m_child, a_stream);

+    }

+  }

+  else // A leaf node

+  {

+    for(int index = 0; index < a_node->m_count; ++index)

+    {

+      Branch* curBranch = &a_node->m_branch[index];

+

+      a_stream.WriteArray(curBranch->m_rect.m_min, NUMDIMS);

+      a_stream.WriteArray(curBranch->m_rect.m_max, NUMDIMS);

+

+      a_stream.Write(curBranch->m_data);

+    }

+  }

+

+  return true; // Should do more error checking on I/O operations

+}

+

+

+RTREE_TEMPLATE

+void RTREE_QUAL::RemoveAll()

+{

+  // Delete all existing nodes

+  Reset();

+

+  m_root = AllocNode();

+  m_root->m_level = 0;

+}

+

+

+RTREE_TEMPLATE

+void RTREE_QUAL::Reset()

+{

+#ifdef RTREE_DONT_USE_MEMPOOLS

+  // Delete all existing nodes

+  RemoveAllRec(m_root);

+#else // RTREE_DONT_USE_MEMPOOLS

+  // Just reset memory pools.  We are not using complex types

+  // EXAMPLE

+#endif // RTREE_DONT_USE_MEMPOOLS

+}

+

+

+RTREE_TEMPLATE

+void RTREE_QUAL::RemoveAllRec(Node* a_node)

+{

+  ASSERT(a_node);

+  ASSERT(a_node->m_level >= 0);

+

+  if(a_node->IsInternalNode()) // This is an internal node in the tree

+  {

+    for(int index=0; index < a_node->m_count; ++index)

+    {

+      RemoveAllRec(a_node->m_branch[index].m_child);

+    }

+  }

+  FreeNode(a_node); 

+}

+

+

+RTREE_TEMPLATE

+typename RTREE_QUAL::Node* RTREE_QUAL::AllocNode()

+{

+  Node* newNode;

+#ifdef RTREE_DONT_USE_MEMPOOLS

+  newNode = new Node;

+#else // RTREE_DONT_USE_MEMPOOLS

+  // EXAMPLE

+#endif // RTREE_DONT_USE_MEMPOOLS

+  InitNode(newNode);

+  return newNode;

+}

+

+

+RTREE_TEMPLATE

+void RTREE_QUAL::FreeNode(Node* a_node)

+{

+  ASSERT(a_node);

+

+#ifdef RTREE_DONT_USE_MEMPOOLS

+  delete a_node;

+#else // RTREE_DONT_USE_MEMPOOLS

+  // EXAMPLE

+#endif // RTREE_DONT_USE_MEMPOOLS

+}

+

+

+// Allocate space for a node in the list used in DeletRect to

+// store Nodes that are too empty.

+RTREE_TEMPLATE

+typename RTREE_QUAL::ListNode* RTREE_QUAL::AllocListNode()

+{

+#ifdef RTREE_DONT_USE_MEMPOOLS

+  return new ListNode;

+#else // RTREE_DONT_USE_MEMPOOLS

+  // EXAMPLE

+#endif // RTREE_DONT_USE_MEMPOOLS

+}

+

+

+RTREE_TEMPLATE

+void RTREE_QUAL::FreeListNode(ListNode* a_listNode)

+{

+#ifdef RTREE_DONT_USE_MEMPOOLS

+  delete a_listNode;

+#else // RTREE_DONT_USE_MEMPOOLS

+  // EXAMPLE

+#endif // RTREE_DONT_USE_MEMPOOLS

+}

+

+

+RTREE_TEMPLATE

+void RTREE_QUAL::InitNode(Node* a_node)

+{

+  a_node->m_count = 0;

+  a_node->m_level = -1;

+}

+

+

+RTREE_TEMPLATE

+void RTREE_QUAL::InitRect(Rect* a_rect)

+{

+  for(int index = 0; index < NUMDIMS; ++index)

+  {

+    a_rect->m_min[index] = (ELEMTYPE)0;

+    a_rect->m_max[index] = (ELEMTYPE)0;

+  }

+}

+

+

+// Inserts a new data rectangle into the index structure.

+// Recursively descends tree, propagates splits back up.

+// Returns 0 if node was not split.  Old node updated.

+// If node was split, returns 1 and sets the pointer pointed to by

+// new_node to point to the new node.  Old node updated to become one of two.

+// The level argument specifies the number of steps up from the leaf

+// level to insert; e.g. a data rectangle goes in at level = 0.

+RTREE_TEMPLATE

+bool RTREE_QUAL::InsertRectRec(Rect* a_rect, const DATATYPE& a_id, Node* a_node, Node** a_newNode, int a_level)

+{

+  ASSERT(a_rect && a_node && a_newNode);

+  ASSERT(a_level >= 0 && a_level <= a_node->m_level);

+

+  int index;

+  Branch branch;

+  Node* otherNode;

+

+  // Still above level for insertion, go down tree recursively

+  if(a_node->m_level > a_level)

+  {

+    index = PickBranch(a_rect, a_node);

+    if (!InsertRectRec(a_rect, a_id, a_node->m_branch[index].m_child, &otherNode, a_level))

+    {

+      // Child was not split

+      a_node->m_branch[index].m_rect = CombineRect(a_rect, &(a_node->m_branch[index].m_rect));

+      return false;

+    }

+    else // Child was split

+    {

+      a_node->m_branch[index].m_rect = NodeCover(a_node->m_branch[index].m_child);

+      branch.m_child = otherNode;

+      branch.m_rect = NodeCover(otherNode);

+      return AddBranch(&branch, a_node, a_newNode);

+    }

+  }

+  else if(a_node->m_level == a_level) // Have reached level for insertion. Add rect, split if necessary

+  {

+    branch.m_rect = *a_rect;

+    branch.m_child = (Node*) a_id;

+    // Child field of leaves contains id of data record

+    return AddBranch(&branch, a_node, a_newNode);

+  }

+  else

+  {

+    // Should never occur

+    ASSERT(0);

+    return false;

+  }

+}

+

+

+// Insert a data rectangle into an index structure.

+// InsertRect provides for splitting the root;

+// returns 1 if root was split, 0 if it was not.

+// The level argument specifies the number of steps up from the leaf

+// level to insert; e.g. a data rectangle goes in at level = 0.

+// InsertRect2 does the recursion.

+//

+RTREE_TEMPLATE

+bool RTREE_QUAL::InsertRect(Rect* a_rect, const DATATYPE& a_id, Node** a_root, int a_level)

+{

+  ASSERT(a_rect && a_root);

+  ASSERT(a_level >= 0 && a_level <= (*a_root)->m_level);

+#ifdef _DEBUG

+  for(int index=0; index < NUMDIMS; ++index)

+  {

+    ASSERT(a_rect->m_min[index] <= a_rect->m_max[index]);

+  }

+#endif //_DEBUG  

+

+  Node* newRoot;

+  Node* newNode;

+  Branch branch;

+

+  if(InsertRectRec(a_rect, a_id, *a_root, &newNode, a_level))  // Root split

+  {

+    newRoot = AllocNode();  // Grow tree taller and new root

+    newRoot->m_level = (*a_root)->m_level + 1;

+    branch.m_rect = NodeCover(*a_root);

+    branch.m_child = *a_root;

+    AddBranch(&branch, newRoot, NULL);

+    branch.m_rect = NodeCover(newNode);

+    branch.m_child = newNode;

+    AddBranch(&branch, newRoot, NULL);

+    *a_root = newRoot;

+    return true;

+  }

+

+  return false;

+}

+

+

+// Find the smallest rectangle that includes all rectangles in branches of a node.

+RTREE_TEMPLATE

+typename RTREE_QUAL::Rect RTREE_QUAL::NodeCover(Node* a_node)

+{

+  ASSERT(a_node);

+  

+  int firstTime = true;

+  Rect rect;

+  InitRect(&rect);

+  

+  for(int index = 0; index < a_node->m_count; ++index)

+  {

+    if(firstTime)

+    {

+      rect = a_node->m_branch[index].m_rect;

+      firstTime = false;

+    }

+    else

+    {

+      rect = CombineRect(&rect, &(a_node->m_branch[index].m_rect));

+    }

+  }

+  

+  return rect;

+}

+

+

+// Add a branch to a node.  Split the node if necessary.

+// Returns 0 if node not split.  Old node updated.

+// Returns 1 if node split, sets *new_node to address of new node.

+// Old node updated, becomes one of two.

+RTREE_TEMPLATE

+bool RTREE_QUAL::AddBranch(Branch* a_branch, Node* a_node, Node** a_newNode)

+{

+  ASSERT(a_branch);

+  ASSERT(a_node);

+

+  if(a_node->m_count < MAXNODES)  // Split won't be necessary

+  {

+    a_node->m_branch[a_node->m_count] = *a_branch;

+    ++a_node->m_count;

+

+    return false;

+  }

+  else

+  {

+    ASSERT(a_newNode);

+    

+    SplitNode(a_node, a_branch, a_newNode);

+    return true;

+  }

+}

+

+

+// Disconnect a dependent node.

+// Caller must return (or stop using iteration index) after this as count has changed

+RTREE_TEMPLATE

+void RTREE_QUAL::DisconnectBranch(Node* a_node, int a_index)

+{

+  ASSERT(a_node && (a_index >= 0) && (a_index < MAXNODES));

+  ASSERT(a_node->m_count > 0);

+

+  // Remove element by swapping with the last element to prevent gaps in array

+  a_node->m_branch[a_index] = a_node->m_branch[a_node->m_count - 1];

+  

+  --a_node->m_count;

+}

+

+

+// Pick a branch.  Pick the one that will need the smallest increase

+// in area to accomodate the new rectangle.  This will result in the

+// least total area for the covering rectangles in the current node.

+// In case of a tie, pick the one which was smaller before, to get

+// the best resolution when searching.

+RTREE_TEMPLATE

+int RTREE_QUAL::PickBranch(Rect* a_rect, Node* a_node)

+{

+  ASSERT(a_rect && a_node);

+  

+  bool firstTime = true;

+  ELEMTYPEREAL increase;

+  ELEMTYPEREAL bestIncr = (ELEMTYPEREAL)-1;

+  ELEMTYPEREAL area;

+  ELEMTYPEREAL bestArea;

+  int best;

+  Rect tempRect;

+

+  for(int index=0; index < a_node->m_count; ++index)

+  {

+    Rect* curRect = &a_node->m_branch[index].m_rect;

+    area = CalcRectVolume(curRect);

+    tempRect = CombineRect(a_rect, curRect);

+    increase = CalcRectVolume(&tempRect) - area;

+    if((increase < bestIncr) || firstTime)

+    {

+      best = index;

+      bestArea = area;

+      bestIncr = increase;

+      firstTime = false;

+    }

+    else if((increase == bestIncr) && (area < bestArea))

+    {

+      best = index;

+      bestArea = area;

+      bestIncr = increase;

+    }

+  }

+  return best;

+}

+

+

+// Combine two rectangles into larger one containing both

+RTREE_TEMPLATE

+typename RTREE_QUAL::Rect RTREE_QUAL::CombineRect(Rect* a_rectA, Rect* a_rectB)

+{

+  ASSERT(a_rectA && a_rectB);

+

+  Rect newRect;

+

+  for(int index = 0; index < NUMDIMS; ++index)

+  {

+    newRect.m_min[index] = Min(a_rectA->m_min[index], a_rectB->m_min[index]);

+    newRect.m_max[index] = Max(a_rectA->m_max[index], a_rectB->m_max[index]);

+  }

+

+  return newRect;

+}

+

+

+

+// Split a node.

+// Divides the nodes branches and the extra one between two nodes.

+// Old node is one of the new ones, and one really new one is created.

+// Tries more than one method for choosing a partition, uses best result.

+RTREE_TEMPLATE

+void RTREE_QUAL::SplitNode(Node* a_node, Branch* a_branch, Node** a_newNode)

+{

+  ASSERT(a_node);

+  ASSERT(a_branch);

+

+  // Could just use local here, but member or external is faster since it is reused

+  PartitionVars localVars;

+  PartitionVars* parVars = &localVars;

+  int level;

+

+  // Load all the branches into a buffer, initialize old node

+  level = a_node->m_level;

+  GetBranches(a_node, a_branch, parVars);

+

+  // Find partition

+  ChoosePartition(parVars, MINNODES);

+

+  // Put branches from buffer into 2 nodes according to chosen partition

+  *a_newNode = AllocNode();

+  (*a_newNode)->m_level = a_node->m_level = level;

+  LoadNodes(a_node, *a_newNode, parVars);

+  

+  ASSERT((a_node->m_count + (*a_newNode)->m_count) == parVars->m_total);

+}

+

+

+// Calculate the n-dimensional volume of a rectangle

+RTREE_TEMPLATE

+ELEMTYPEREAL RTREE_QUAL::RectVolume(Rect* a_rect)

+{

+  ASSERT(a_rect);

+  

+  ELEMTYPEREAL volume = (ELEMTYPEREAL)1;

+

+  for(int index=0; index<NUMDIMS; ++index)

+  {

+    volume *= a_rect->m_max[index] - a_rect->m_min[index];

+  }

+  

+  ASSERT(volume >= (ELEMTYPEREAL)0);

+  

+  return volume;

+}

+

+

+// The exact volume of the bounding sphere for the given Rect

+RTREE_TEMPLATE

+ELEMTYPEREAL RTREE_QUAL::RectSphericalVolume(Rect* a_rect)

+{

+  ASSERT(a_rect);

+   

+  ELEMTYPEREAL sumOfSquares = (ELEMTYPEREAL)0;

+  ELEMTYPEREAL radius;

+

+  for(int index=0; index < NUMDIMS; ++index) 

+  {

+    ELEMTYPEREAL halfExtent = ((ELEMTYPEREAL)a_rect->m_max[index] - (ELEMTYPEREAL)a_rect->m_min[index]) * 0.5f;

+    sumOfSquares += halfExtent * halfExtent;

+  }

+

+  radius = (ELEMTYPEREAL)sqrt(sumOfSquares);

+  

+  // Pow maybe slow, so test for common dims like 2,3 and just use x*x, x*x*x.

+  if(NUMDIMS == 3)

+  {

+    return (radius * radius * radius * m_unitSphereVolume);

+  }

+  else if(NUMDIMS == 2)

+  {

+    return (radius * radius * m_unitSphereVolume);

+  }

+  else

+  {

+    return (ELEMTYPEREAL)(pow(radius, NUMDIMS) * m_unitSphereVolume);

+  }

+}

+

+

+// Use one of the methods to calculate retangle volume

+RTREE_TEMPLATE

+ELEMTYPEREAL RTREE_QUAL::CalcRectVolume(Rect* a_rect)

+{

+#ifdef RTREE_USE_SPHERICAL_VOLUME

+  return RectSphericalVolume(a_rect); // Slower but helps certain merge cases

+#else // RTREE_USE_SPHERICAL_VOLUME

+  return RectVolume(a_rect); // Faster but can cause poor merges

+#endif // RTREE_USE_SPHERICAL_VOLUME  

+}

+

+

+// Load branch buffer with branches from full node plus the extra branch.

+RTREE_TEMPLATE

+void RTREE_QUAL::GetBranches(Node* a_node, Branch* a_branch, PartitionVars* a_parVars)

+{

+  ASSERT(a_node);

+  ASSERT(a_branch);

+

+  ASSERT(a_node->m_count == MAXNODES);

+    

+  // Load the branch buffer

+  for(int index=0; index < MAXNODES; ++index)

+  {

+    a_parVars->m_branchBuf[index] = a_node->m_branch[index];

+  }

+  a_parVars->m_branchBuf[MAXNODES] = *a_branch;

+  a_parVars->m_branchCount = MAXNODES + 1;

+

+  // Calculate rect containing all in the set

+  a_parVars->m_coverSplit = a_parVars->m_branchBuf[0].m_rect;

+  for(int index=1; index < MAXNODES+1; ++index)

+  {

+    a_parVars->m_coverSplit = CombineRect(&a_parVars->m_coverSplit, &a_parVars->m_branchBuf[index].m_rect);

+  }

+  a_parVars->m_coverSplitArea = CalcRectVolume(&a_parVars->m_coverSplit);

+

+  InitNode(a_node);

+}

+

+

+// Method #0 for choosing a partition:

+// As the seeds for the two groups, pick the two rects that would waste the

+// most area if covered by a single rectangle, i.e. evidently the worst pair

+// to have in the same group.

+// Of the remaining, one at a time is chosen to be put in one of the two groups.

+// The one chosen is the one with the greatest difference in area expansion

+// depending on which group - the rect most strongly attracted to one group

+// and repelled from the other.

+// If one group gets too full (more would force other group to violate min

+// fill requirement) then other group gets the rest.

+// These last are the ones that can go in either group most easily.

+RTREE_TEMPLATE

+void RTREE_QUAL::ChoosePartition(PartitionVars* a_parVars, int a_minFill)

+{

+  ASSERT(a_parVars);

+  

+  ELEMTYPEREAL biggestDiff;

+  int group, chosen, betterGroup;

+  

+  InitParVars(a_parVars, a_parVars->m_branchCount, a_minFill);

+  PickSeeds(a_parVars);

+

+  while (((a_parVars->m_count[0] + a_parVars->m_count[1]) < a_parVars->m_total)

+       && (a_parVars->m_count[0] < (a_parVars->m_total - a_parVars->m_minFill))

+       && (a_parVars->m_count[1] < (a_parVars->m_total - a_parVars->m_minFill)))

+  {

+    biggestDiff = (ELEMTYPEREAL) -1;

+    for(int index=0; index<a_parVars->m_total; ++index)

+    {

+      if(!a_parVars->m_taken[index])

+      {

+        Rect* curRect = &a_parVars->m_branchBuf[index].m_rect;

+        Rect rect0 = CombineRect(curRect, &a_parVars->m_cover[0]);

+        Rect rect1 = CombineRect(curRect, &a_parVars->m_cover[1]);

+        ELEMTYPEREAL growth0 = CalcRectVolume(&rect0) - a_parVars->m_area[0];

+        ELEMTYPEREAL growth1 = CalcRectVolume(&rect1) - a_parVars->m_area[1];

+        ELEMTYPEREAL diff = growth1 - growth0;

+        if(diff >= 0)

+        {

+          group = 0;

+        }

+        else

+        {

+          group = 1;

+          diff = -diff;

+        }

+

+        if(diff > biggestDiff)

+        {

+          biggestDiff = diff;

+          chosen = index;

+          betterGroup = group;

+        }

+        else if((diff == biggestDiff) && (a_parVars->m_count[group] < a_parVars->m_count[betterGroup]))

+        {

+          chosen = index;

+          betterGroup = group;

+        }

+      }

+    }

+    Classify(chosen, betterGroup, a_parVars);

+  }

+

+  // If one group too full, put remaining rects in the other

+  if((a_parVars->m_count[0] + a_parVars->m_count[1]) < a_parVars->m_total)

+  {

+    if(a_parVars->m_count[0] >= a_parVars->m_total - a_parVars->m_minFill)

+    {

+      group = 1;

+    }

+    else

+    {

+      group = 0;

+    }

+    for(int index=0; index<a_parVars->m_total; ++index)

+    {

+      if(!a_parVars->m_taken[index])

+      {

+        Classify(index, group, a_parVars);

+      }

+    }

+  }

+

+  ASSERT((a_parVars->m_count[0] + a_parVars->m_count[1]) == a_parVars->m_total);

+  ASSERT((a_parVars->m_count[0] >= a_parVars->m_minFill) && 

+        (a_parVars->m_count[1] >= a_parVars->m_minFill));

+}

+

+

+// Copy branches from the buffer into two nodes according to the partition.

+RTREE_TEMPLATE

+void RTREE_QUAL::LoadNodes(Node* a_nodeA, Node* a_nodeB, PartitionVars* a_parVars)

+{

+  ASSERT(a_nodeA);

+  ASSERT(a_nodeB);

+  ASSERT(a_parVars);

+

+  for(int index=0; index < a_parVars->m_total; ++index)

+  {

+    ASSERT(a_parVars->m_partition[index] == 0 || a_parVars->m_partition[index] == 1);

+    

+    if(a_parVars->m_partition[index] == 0)

+    {

+      AddBranch(&a_parVars->m_branchBuf[index], a_nodeA, NULL);

+    }

+    else if(a_parVars->m_partition[index] == 1)

+    {

+      AddBranch(&a_parVars->m_branchBuf[index], a_nodeB, NULL);

+    }

+  }

+}

+

+

+// Initialize a PartitionVars structure.

+RTREE_TEMPLATE

+void RTREE_QUAL::InitParVars(PartitionVars* a_parVars, int a_maxRects, int a_minFill)

+{

+  ASSERT(a_parVars);

+

+  a_parVars->m_count[0] = a_parVars->m_count[1] = 0;

+  a_parVars->m_area[0] = a_parVars->m_area[1] = (ELEMTYPEREAL)0;

+  a_parVars->m_total = a_maxRects;

+  a_parVars->m_minFill = a_minFill;

+  for(int index=0; index < a_maxRects; ++index)

+  {

+    a_parVars->m_taken[index] = false;

+    a_parVars->m_partition[index] = -1;

+  }

+}

+

+

+RTREE_TEMPLATE

+void RTREE_QUAL::PickSeeds(PartitionVars* a_parVars)

+{

+  int seed0, seed1;

+  ELEMTYPEREAL worst, waste;

+  ELEMTYPEREAL area[MAXNODES+1];

+

+  for(int index=0; index<a_parVars->m_total; ++index)

+  {

+    area[index] = CalcRectVolume(&a_parVars->m_branchBuf[index].m_rect);

+  }

+

+  worst = -a_parVars->m_coverSplitArea - 1;

+  for(int indexA=0; indexA < a_parVars->m_total-1; ++indexA)

+  {

+    for(int indexB = indexA+1; indexB < a_parVars->m_total; ++indexB)

+    {

+      Rect oneRect = CombineRect(&a_parVars->m_branchBuf[indexA].m_rect, &a_parVars->m_branchBuf[indexB].m_rect);

+      waste = CalcRectVolume(&oneRect) - area[indexA] - area[indexB];

+      if(waste > worst)

+      {

+        worst = waste;

+        seed0 = indexA;

+        seed1 = indexB;

+      }

+    }

+  }

+  Classify(seed0, 0, a_parVars);

+  Classify(seed1, 1, a_parVars);

+}

+

+

+// Put a branch in one of the groups.

+RTREE_TEMPLATE

+void RTREE_QUAL::Classify(int a_index, int a_group, PartitionVars* a_parVars)

+{

+  ASSERT(a_parVars);

+  ASSERT(!a_parVars->m_taken[a_index]);

+

+  a_parVars->m_partition[a_index] = a_group;

+  a_parVars->m_taken[a_index] = true;

+

+  if (a_parVars->m_count[a_group] == 0)

+  {

+    a_parVars->m_cover[a_group] = a_parVars->m_branchBuf[a_index].m_rect;

+  }

+  else

+  {

+    a_parVars->m_cover[a_group] = CombineRect(&a_parVars->m_branchBuf[a_index].m_rect, &a_parVars->m_cover[a_group]);

+  }

+  a_parVars->m_area[a_group] = CalcRectVolume(&a_parVars->m_cover[a_group]);

+  ++a_parVars->m_count[a_group];

+}

+

+

+// Delete a data rectangle from an index structure.

+// Pass in a pointer to a Rect, the tid of the record, ptr to ptr to root node.

+// Returns 1 if record not found, 0 if success.

+// RemoveRect provides for eliminating the root.

+RTREE_TEMPLATE

+bool RTREE_QUAL::RemoveRect(Rect* a_rect, const DATATYPE& a_id, Node** a_root)

+{

+  ASSERT(a_rect && a_root);

+  ASSERT(*a_root);

+

+  Node* tempNode;

+  ListNode* reInsertList = NULL;

+

+  if(!RemoveRectRec(a_rect, a_id, *a_root, &reInsertList))

+  {

+    // Found and deleted a data item

+    // Reinsert any branches from eliminated nodes

+    while(reInsertList)

+    {

+      tempNode = reInsertList->m_node;

+

+      for(int index = 0; index < tempNode->m_count; ++index)

+      {

+        InsertRect(&(tempNode->m_branch[index].m_rect),

+                   tempNode->m_branch[index].m_data,

+                   a_root,

+                   tempNode->m_level);

+      }

+      

+      ListNode* remLNode = reInsertList;

+      reInsertList = reInsertList->m_next;

+      

+      FreeNode(remLNode->m_node);

+      FreeListNode(remLNode);

+    }

+    

+    // Check for redundant root (not leaf, 1 child) and eliminate

+    if((*a_root)->m_count == 1 && (*a_root)->IsInternalNode())

+    {

+      tempNode = (*a_root)->m_branch[0].m_child;

+      

+      ASSERT(tempNode);

+      FreeNode(*a_root);

+      *a_root = tempNode;

+    }

+    return false;

+  }

+  else

+  {

+    return true;

+  }

+}

+

+

+// Delete a rectangle from non-root part of an index structure.

+// Called by RemoveRect.  Descends tree recursively,

+// merges branches on the way back up.

+// Returns 1 if record not found, 0 if success.

+RTREE_TEMPLATE

+bool RTREE_QUAL::RemoveRectRec(Rect* a_rect, const DATATYPE& a_id, Node* a_node, ListNode** a_listNode)

+{

+  ASSERT(a_rect && a_node && a_listNode);

+  ASSERT(a_node->m_level >= 0);

+

+  if(a_node->IsInternalNode())  // not a leaf node

+  {

+    for(int index = 0; index < a_node->m_count; ++index)

+    {

+      if(Overlap(a_rect, &(a_node->m_branch[index].m_rect)))

+      {

+        if(!RemoveRectRec(a_rect, a_id, a_node->m_branch[index].m_child, a_listNode))

+        {

+          if(a_node->m_branch[index].m_child->m_count >= MINNODES)

+          {

+            // child removed, just resize parent rect

+            a_node->m_branch[index].m_rect = NodeCover(a_node->m_branch[index].m_child);

+          }

+          else

+          {

+            // child removed, not enough entries in node, eliminate node

+            ReInsert(a_node->m_branch[index].m_child, a_listNode);

+            DisconnectBranch(a_node, index); // Must return after this call as count has changed

+          }

+          return false;

+        }

+      }

+    }

+    return true;

+  }

+  else // A leaf node

+  {

+    for(int index = 0; index < a_node->m_count; ++index)

+    {

+      if(a_node->m_branch[index].m_child == (Node*)a_id)

+      {

+        DisconnectBranch(a_node, index); // Must return after this call as count has changed

+        return false;

+      }

+    }

+    return true;

+  }

+}

+

+

+// Decide whether two rectangles overlap.

+RTREE_TEMPLATE

+bool RTREE_QUAL::Overlap(Rect* a_rectA, Rect* a_rectB)

+{

+  ASSERT(a_rectA && a_rectB);

+

+  for(int index=0; index < NUMDIMS; ++index)

+  {

+    if (a_rectA->m_min[index] > a_rectB->m_max[index] ||

+        a_rectB->m_min[index] > a_rectA->m_max[index])

+    {

+      return false;

+    }

+  }

+  return true;

+}

+

+

+// Add a node to the reinsertion list.  All its branches will later

+// be reinserted into the index structure.

+RTREE_TEMPLATE

+void RTREE_QUAL::ReInsert(Node* a_node, ListNode** a_listNode)

+{

+  ListNode* newListNode;

+

+  newListNode = AllocListNode();

+  newListNode->m_node = a_node;

+  newListNode->m_next = *a_listNode;

+  *a_listNode = newListNode;

+}

+

+

+// Search in an index tree or subtree for all data retangles that overlap the argument rectangle.

+RTREE_TEMPLATE

+bool RTREE_QUAL::Search(Node* a_node, Rect* a_rect, int& a_foundCount, bool a_resultCallback(DATATYPE a_data, void* a_context), void* a_context)

+{

+  ASSERT(a_node);

+  ASSERT(a_node->m_level >= 0);

+  ASSERT(a_rect);

+

+  if(a_node->IsInternalNode()) // This is an internal node in the tree

+  {

+    for(int index=0; index < a_node->m_count; ++index)

+    {

+      if(Overlap(a_rect, &a_node->m_branch[index].m_rect))

+      {

+        if(!Search(a_node->m_branch[index].m_child, a_rect, a_foundCount, a_resultCallback, a_context))

+        {

+          return false; // Don't continue searching

+        }

+      }

+    }

+  }

+  else // This is a leaf node

+  {

+    for(int index=0; index < a_node->m_count; ++index)

+    {

+      if(Overlap(a_rect, &a_node->m_branch[index].m_rect))

+      {

+        DATATYPE& id = a_node->m_branch[index].m_data;

+        

+        // NOTE: There are different ways to return results.  Here's where to modify

+        if(a_resultCallback)

+        {

+          ++a_foundCount;

+          if(!a_resultCallback(id, a_context))

+          {

+            return false; // Don't continue searching

+          }

+        }

+      }

+    }

+  }

+

+  return true; // Continue searching

+}

+

+

+#undef RTREE_TEMPLATE

+#undef RTREE_QUAL

+

+#endif //RTREE_H

diff --git a/Source/WebCore/platform/graphics/android/fonts/FontAndroid.cpp b/Source/WebCore/platform/graphics/android/fonts/FontAndroid.cpp
index d59674b..2bd77ee 100644
--- a/Source/WebCore/platform/graphics/android/fonts/FontAndroid.cpp
+++ b/Source/WebCore/platform/graphics/android/fonts/FontAndroid.cpp
@@ -26,6 +26,9 @@
 
 #include "config.h"
 
+#define LOG_TAG "FontAndroid"
+
+#include "AndroidLog.h"
 #include "EmojiFont.h"
 #include "GraphicsOperationCollection.h"
 #include "GraphicsOperation.h"
@@ -175,6 +178,16 @@ static bool setupForText(SkPaint* paint, GraphicsContext* gc,
     return true;
 }
 
+static FloatRect drawPosText(SkCanvas* canvas, const void* text, size_t byteLength,
+                             const SkPoint pos[], const SkPaint& paint)
+{
+    SkRect textBounds;
+    paint.measureText(text, byteLength, &textBounds);
+    textBounds.offset(pos[0].x(), pos[0].y());
+    canvas->drawPosText(text, byteLength, pos, paint);
+    return textBounds;
+}
+
 bool Font::canReturnFallbackFontsForComplexText()
 {
     return false;
@@ -192,6 +205,12 @@ void Font::drawGlyphs(GraphicsContext* gc, const SimpleFontData* font,
     // compile-time assert
     SkASSERT(sizeof(GlyphBufferGlyph) == sizeof(uint16_t));
 
+    if (numGlyphs == 1 && glyphBuffer.glyphAt(from) == 0x3) {
+        // Webkit likes to draw end text control command for some reason
+        // Just ignore it
+        return;
+    }
+
     SkPaint paint;
     if (!setupForText(&paint, gc, font)) {
         return;
@@ -213,6 +232,7 @@ void Font::drawGlyphs(GraphicsContext* gc, const SimpleFontData* font,
     if (font->platformData().orientation() == Vertical)
         y += SkFloatToScalar(font->fontMetrics().floatAscent(IdeographicBaseline) - font->fontMetrics().floatAscent());
 
+    FloatRect textBounds;
     if (EmojiFont::IsAvailable()) {
         // set filtering, to make scaled images look nice(r)
         paint.setFilterBitmap(true);
@@ -221,11 +241,15 @@ void Font::drawGlyphs(GraphicsContext* gc, const SimpleFontData* font,
         int localCount = 0;
         for (int i = 0; i < numGlyphs; i++) {
             if (EmojiFont::IsEmojiGlyph(glyphs[i])) {
-                if (localCount)
-                    canvas->drawPosText(&glyphs[localIndex],
-                                        localCount * sizeof(uint16_t),
-                                        &pos[localIndex], paint);
+                if (localCount) {
+                    textBounds.unite(drawPosText(canvas, &glyphs[localIndex],
+                                     localCount * sizeof(uint16_t),
+                                     &pos[localIndex], paint));
+                }
                 EmojiFont::Draw(canvas, glyphs[i], x, y, paint);
+                float size = paint.getTextSize();
+                FloatRect emojiBounds(x, y - size + 0.2f, size, size);
+                textBounds.unite(emojiBounds);
                 // reset local index/count track for "real" glyphs
                 localCount = 0;
                 localIndex = i + 1;
@@ -237,10 +261,11 @@ void Font::drawGlyphs(GraphicsContext* gc, const SimpleFontData* font,
             y += SkFloatToScalar(adv[i].height());
         }
         // draw the last run of glyphs (if any)
-        if (localCount)
-            canvas->drawPosText(&glyphs[localIndex],
-                                localCount * sizeof(uint16_t),
-                                &pos[localIndex], paint);
+        if (localCount) {
+            textBounds.unite(drawPosText(canvas, &glyphs[localIndex],
+                             localCount * sizeof(uint16_t),
+                             &pos[localIndex], paint));
+        }
     } else {
         for (int i = 0; i < numGlyphs; i++) {
             pos[i].set(x, y);
@@ -256,13 +281,13 @@ void Font::drawGlyphs(GraphicsContext* gc, const SimpleFontData* font,
             rotator.setRotate(90);
             rotator.mapPoints(pos, numGlyphs);
         }
-
-        canvas->drawPosText(glyphs, numGlyphs * sizeof(uint16_t), pos, paint);
+        textBounds.unite(drawPosText(canvas, glyphs, numGlyphs * sizeof(uint16_t),
+                                     pos, paint));
 
         if (font->platformData().orientation() == Vertical)
             canvas->restore();
     }
-    gc->platformContext()->endRecording();
+    gc->platformContext()->endRecording(textBounds);
 }
 
 void Font::drawEmphasisMarksForComplexText(WebCore::GraphicsContext*, WebCore::TextRun const&, WTF::AtomicString const&, WebCore::FloatPoint const&, int, int) const
@@ -1026,22 +1051,23 @@ void Font::drawComplexText(GraphicsContext* gc, TextRun const& run,
     walker.setWordAndLetterSpacing(wordSpacing(), letterSpacing());
     walker.setPadding(run.expansion());
 
+    FloatRect textBounds;
     while (walker.nextScriptRun()) {
         if (fill) {
             walker.fontPlatformDataForScriptRun()->setupPaint(&fillPaint);
             adjustTextRenderMode(&fillPaint, haveMultipleLayers);
-            canvas->drawPosText(walker.glyphs(), walker.length() << 1,
-                                walker.positions(), fillPaint);
+            textBounds.unite(drawPosText(canvas, walker.glyphs(), walker.length() << 1,
+                                         walker.positions(), fillPaint));
         }
         if (stroke) {
             walker.fontPlatformDataForScriptRun()->setupPaint(&strokePaint);
             adjustTextRenderMode(&strokePaint, haveMultipleLayers);
-            canvas->drawPosText(walker.glyphs(), walker.length() << 1,
-                                walker.positions(), strokePaint);
+            textBounds.unite(drawPosText(canvas, walker.glyphs(), walker.length() << 1,
+                                         walker.positions(), strokePaint));
         }
     }
 
-    gc->platformContext()->endRecording();
+    gc->platformContext()->endRecording(textBounds);
 }
 
 float Font::floatWidthForComplexText(const TextRun& run,
diff --git a/Source/WebKit/android/jni/PicturePile.cpp b/Source/WebKit/android/jni/PicturePile.cpp
index 6a36ccf..0567b62 100644
--- a/Source/WebKit/android/jni/PicturePile.cpp
+++ b/Source/WebKit/android/jni/PicturePile.cpp
@@ -275,15 +275,15 @@ PrerenderedInval* PicturePile::prerenderedInvalForArea(const IntRect& area)
 #if USE_RECORDING_CONTEXT
 void PicturePile::drawPicture(SkCanvas* canvas, PictureContainer& pc)
 {
-    PlatformGraphicsContextSkia pgc(canvas);
-    pc.picture->apply(&pgc);
+    TRACE_METHOD();
+    pc.picture->draw(canvas);
 }
 
 Picture* PicturePile::recordPicture(PicturePainter* painter, PictureContainer& pc)
 {
     // TODO: Support? Not needed?
     pc.prerendered.clear();
-    GraphicsOperationCollection* picture = new GraphicsOperationCollection();
+    Recording* picture = new Recording();
     WebCore::PlatformGraphicsContextRecording pgc(picture);
     WebCore::GraphicsContext gc(&pgc);
     painter->paintContents(&gc, pc.area);
diff --git a/Source/WebKit/android/jni/PicturePile.h b/Source/WebKit/android/jni/PicturePile.h
index 64caa95..a8175d9 100644
--- a/Source/WebKit/android/jni/PicturePile.h
+++ b/Source/WebKit/android/jni/PicturePile.h
@@ -38,12 +38,12 @@
 #include <wtf/ThreadSafeRefCounted.h>
 #include <wtf/Vector.h>
 
-#define USE_RECORDING_CONTEXT true
+#define USE_RECORDING_CONTEXT false
 #if USE_RECORDING_CONTEXT
 namespace WebCore {
-class GraphicsOperationCollection;
+class Recording;
 }
-typedef WebCore::GraphicsOperationCollection Picture;
+typedef WebCore::Recording Picture;
 #else
 class SkPicture;
 typedef SkPicture Picture;