Remove the remainder of the skia source code from the Chromium repo....

skia/sgl/SkRegion_path.cpp

Index: skia/sgl/SkRegion_path.cpp
===================================================================
--- skia/sgl/SkRegion_path.cpp	(revision 16859)
+++ skia/sgl/SkRegion_path.cpp	(working copy)
@@ -1,480 +0,0 @@
-/* libs/graphics/sgl/SkRegion_path.cpp
-**
-** Copyright 2006, The Android Open Source Project
-**
-** Licensed under the Apache License, Version 2.0 (the "License"); 
-** you may not use this file except in compliance with the License. 
-** You may obtain a copy of the License at 
-**
-**     http://www.apache.org/licenses/LICENSE-2.0 
-**
-** Unless required by applicable law or agreed to in writing, software 
-** distributed under the License is distributed on an "AS IS" BASIS, 
-** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 
-** See the License for the specific language governing permissions and 
-** limitations under the License.
-*/
-
-#include "SkRegionPriv.h"
-#include "SkBlitter.h"
-#include "SkScan.h"
-#include "SkTDArray.h"
-#include "SkPath.h"
-
-class SkRgnBuilder : public SkBlitter {
-public:
-    virtual ~SkRgnBuilder();
-    
-    // returns true if it could allocate the working storage needed
-    bool init(int maxHeight, int maxTransitions);
-
-    void done() {
-        if (fCurrScanline != NULL) {
-            fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
-            if (!this->collapsWithPrev()) { // flush the last line
-                fCurrScanline = fCurrScanline->nextScanline();
-            }
-        }
-    }
-
-    int     computeRunCount() const;
-    void    copyToRect(SkIRect*) const;
-    void    copyToRgn(SkRegion::RunType runs[]) const;
-
-    virtual void blitH(int x, int y, int width);
-
-#ifdef SK_DEBUG
-    void dump() const {
-        SkDebugf("SkRgnBuilder: Top = %d\n", fTop);
-        const Scanline* line = (Scanline*)fStorage;
-        while (line < fCurrScanline) {
-            SkDebugf("SkRgnBuilder::Scanline: LastY=%d, fXCount=%d", line->fLastY, line->fXCount);
-            for (int i = 0; i < line->fXCount; i++) {
-                SkDebugf(" %d", line->firstX()[i]);
-            }
-            SkDebugf("\n");
-
-            line = line->nextScanline();
-        }
-    }
-#endif
-private:
-    struct Scanline {
-        SkRegion::RunType fLastY;
-        SkRegion::RunType fXCount;
-
-        SkRegion::RunType* firstX() const { return (SkRegion::RunType*)(this + 1); }
-        Scanline* nextScanline() const {
-            return (Scanline*)((SkRegion::RunType*)(this + 1) + fXCount);
-        }
-    };
-    SkRegion::RunType*  fStorage;
-    Scanline*           fCurrScanline;
-    Scanline*           fPrevScanline;
-    //  points at next avialable x[] in fCurrScanline
-    SkRegion::RunType*  fCurrXPtr;
-    SkRegion::RunType   fTop;           // first Y value
-    
-    int fStorageCount;
-
-    bool collapsWithPrev() {
-        if (fPrevScanline != NULL &&
-            fPrevScanline->fLastY + 1 == fCurrScanline->fLastY &&
-            fPrevScanline->fXCount == fCurrScanline->fXCount &&
-            !memcmp(fPrevScanline->firstX(),
-                    fCurrScanline->firstX(),
-                    fCurrScanline->fXCount * sizeof(SkRegion::RunType)))
-        {
-            // update the height of fPrevScanline
-            fPrevScanline->fLastY = fCurrScanline->fLastY;
-            return true;
-        }
-        return false;
-    }
-};
-
-SkRgnBuilder::~SkRgnBuilder() {
-    sk_free(fStorage);
-}
-
-bool SkRgnBuilder::init(int maxHeight, int maxTransitions) {
-    if ((maxHeight | maxTransitions) < 0) {
-        return false;
-    }
-
-    Sk64 count, size;
-
-    // compute the count with +1 and +3 slop for the working buffer
-    count.setMul(maxHeight + 1, 3 + maxTransitions);
-    if (!count.is32() || count.isNeg()) {
-        return false;
-    }
-    fStorageCount = count.get32();
-
-    size.setMul(fStorageCount, sizeof(SkRegion::RunType));
-    if (!size.is32() || size.isNeg()) {
-        return false;
-    }
-
-    fStorage = (SkRegion::RunType*)sk_malloc_flags(size.get32(), 0);
-    if (NULL == fStorage) {
-        return false;
-    }
-
-    fCurrScanline = NULL;    // signal empty collection
-    fPrevScanline = NULL;    // signal first scanline
-    return true;
-}
-
-void SkRgnBuilder::blitH(int x, int y, int width) {
-    if (fCurrScanline == NULL) {  // first time
-        fTop = (SkRegion::RunType)(y);
-        fCurrScanline = (Scanline*)fStorage;
-        fCurrScanline->fLastY = (SkRegion::RunType)(y);
-        fCurrXPtr = fCurrScanline->firstX();
-    } else {
-        SkASSERT(y >= fCurrScanline->fLastY);
-
-        if (y > fCurrScanline->fLastY) {
-            // if we get here, we're done with fCurrScanline
-            fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
-
-            int prevLastY = fCurrScanline->fLastY;
-            if (!this->collapsWithPrev()) {
-                fPrevScanline = fCurrScanline;
-                fCurrScanline = fCurrScanline->nextScanline();
-
-            }
-            if (y - 1 > prevLastY) {  // insert empty run
-                fCurrScanline->fLastY = (SkRegion::RunType)(y - 1);
-                fCurrScanline->fXCount = 0;
-                fCurrScanline = fCurrScanline->nextScanline();
-            }
-            // setup for the new curr line
-            fCurrScanline->fLastY = (SkRegion::RunType)(y);
-            fCurrXPtr = fCurrScanline->firstX();
-        }
-    }
-    //  check if we should extend the current run, or add a new one
-    if (fCurrXPtr > fCurrScanline->firstX() && fCurrXPtr[-1] == x) {
-        fCurrXPtr[-1] = (SkRegion::RunType)(x + width);
-    } else {
-        fCurrXPtr[0] = (SkRegion::RunType)(x);
-        fCurrXPtr[1] = (SkRegion::RunType)(x + width);
-        fCurrXPtr += 2;
-    }
-    SkASSERT(fCurrXPtr - fStorage < fStorageCount);
-}
-
-int SkRgnBuilder::computeRunCount() const {
-    if (fCurrScanline == NULL) {
-        return 0;
-    }
-
-    const SkRegion::RunType*  line = fStorage;
-    const SkRegion::RunType*  stop = (const SkRegion::RunType*)fCurrScanline;
-
-    return 2 + (int)(stop - line);
-}
-
-void SkRgnBuilder::copyToRect(SkIRect* r) const {
-    SkASSERT(fCurrScanline != NULL);
-    SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage == 4);
-
-    const Scanline* line = (const Scanline*)fStorage;
-    SkASSERT(line->fXCount == 2);
-
-    r->set(line->firstX()[0], fTop, line->firstX()[1], line->fLastY + 1);
-}
-
-void SkRgnBuilder::copyToRgn(SkRegion::RunType runs[]) const {
-    SkASSERT(fCurrScanline != NULL);
-    SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage > 4);
-
-    const Scanline* line = (const Scanline*)fStorage;
-    const Scanline* stop = fCurrScanline;
-
-    *runs++ = fTop;
-    do {
-        *runs++ = (SkRegion::RunType)(line->fLastY + 1);
-        int count = line->fXCount;
-        if (count) {
-            memcpy(runs, line->firstX(), count * sizeof(SkRegion::RunType));
-            runs += count;
-        }
-        *runs++ = SkRegion::kRunTypeSentinel;
-        line = line->nextScanline();
-    } while (line < stop);
-    SkASSERT(line == stop);
-    *runs = SkRegion::kRunTypeSentinel;
-}
-
-static int count_path_runtype_values(const SkPath& path, int* itop, int* ibot) {
-    static const uint8_t gPathVerbToInitialLastIndex[] = {
-        0,  //  kMove_Verb
-        1,  //  kLine_Verb
-        2,  //  kQuad_Verb
-        3,  //  kCubic_Verb
-        0,  //  kClose_Verb
-        0   //  kDone_Verb
-    };
-
-    static const uint8_t gPathVerbToMaxEdges[] = {
-        0,  //  kMove_Verb
-        1,  //  kLine_Verb
-        2,  //  kQuad_VerbB
-        3,  //  kCubic_Verb
-        0,  //  kClose_Verb
-        0   //  kDone_Verb
-    };
-
-    SkPath::Iter    iter(path, true);
-    SkPoint         pts[4];
-    SkPath::Verb    verb;
-
-    int maxEdges = 0;
-    SkScalar    top = SkIntToScalar(SK_MaxS16);
-    SkScalar    bot = SkIntToScalar(SK_MinS16);
-
-    while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
-        maxEdges += gPathVerbToMaxEdges[verb];
-
-        int lastIndex = gPathVerbToInitialLastIndex[verb];
-        if (lastIndex > 0) {
-            for (int i = 1; i <= lastIndex; i++) {
-                if (top > pts[i].fY) {
-                    top = pts[i].fY;
-                } else if (bot < pts[i].fY) {
-                    bot = pts[i].fY;
-                }
-            }
-        } else if (SkPath::kMove_Verb == verb) {
-            if (top > pts[0].fY) {
-                top = pts[0].fY;
-            } else if (bot < pts[0].fY) {
-                bot = pts[0].fY;
-            }
-        }
-    }
-    SkASSERT(top <= bot);
-
-    *itop = SkScalarRound(top);
-    *ibot = SkScalarRound(bot);
-    return maxEdges;
-}
-
-bool SkRegion::setPath(const SkPath& path, const SkRegion& clip) {
-    SkDEBUGCODE(this->validate();)
-
-    if (clip.isEmpty()) {
-        return this->setEmpty();
-    }
-
-    if (path.isEmpty()) {
-        if (path.isInverseFillType()) {
-            return this->set(clip);
-        } else {
-            return this->setEmpty();
-        }
-    }
-
-    //  compute worst-case rgn-size for the path
-    int pathTop, pathBot;
-    int pathTransitions = count_path_runtype_values(path, &pathTop, &pathBot);
-    int clipTop, clipBot;
-    int clipTransitions;
-    
-    clipTransitions = clip.count_runtype_values(&clipTop, &clipBot);
-
-    int top = SkMax32(pathTop, clipTop);
-    int bot = SkMin32(pathBot, clipBot);
-
-    if (top >= bot)
-        return this->setEmpty();
-
-    SkRgnBuilder builder;
-    
-    if (!builder.init(bot - top, SkMax32(pathTransitions, clipTransitions))) {
-        // can't allocate working space, so return false
-        return this->setEmpty();
-    }
-
-    SkScan::FillPath(path, clip, &builder);
-    builder.done();
-
-    int count = builder.computeRunCount();
-    if (count == 0) {
-        return this->setEmpty();
-    } else if (count == kRectRegionRuns) {
-        builder.copyToRect(&fBounds);
-        this->setRect(fBounds);
-    } else {
-        SkRegion    tmp;
-
-        tmp.fRunHead = RunHead::Alloc(count);
-        builder.copyToRgn(tmp.fRunHead->writable_runs());
-        ComputeRunBounds(tmp.fRunHead->readonly_runs(), count, &tmp.fBounds);
-        this->swap(tmp);
-    }
-    SkDEBUGCODE(this->validate();)
-    return true;
-}
-
-/////////////////////////////////////////////////////////////////////////////////////////////////
-/////////////////////////////////////////////////////////////////////////////////////////////////
-
-struct Edge {
-    enum {
-        kY0Link = 0x01,
-        kY1Link = 0x02,
-        
-        kCompleteLink = (kY0Link | kY1Link)
-    };
-
-    SkRegion::RunType fX;
-    SkRegion::RunType fY0, fY1;
-    uint8_t fFlags;
-    Edge*   fNext;
-    
-    void set(int x, int y0, int y1) {
-        SkASSERT(y0 != y1);
-
-        fX = (SkRegion::RunType)(x);
-        fY0 = (SkRegion::RunType)(y0);
-        fY1 = (SkRegion::RunType)(y1);
-        fFlags = 0;
-        SkDEBUGCODE(fNext = NULL;)
-    }
-    
-    int top() const {
-        return SkFastMin32(fY0, fY1);
-    }
-};
-
-static void find_link(Edge* base, Edge* stop) {
-    SkASSERT(base < stop);
-
-    if (base->fFlags == Edge::kCompleteLink) {
-        SkASSERT(base->fNext);
-        return;
-    }
-
-    SkASSERT(base + 1 < stop);
-
-    int y0 = base->fY0;
-    int y1 = base->fY1;
-
-    Edge* e = base;
-    if ((base->fFlags & Edge::kY0Link) == 0) {
-        for (;;) {
-            e += 1;
-            if ((e->fFlags & Edge::kY1Link) == 0 && y0 == e->fY1) {
-                SkASSERT(NULL == e->fNext);
-                e->fNext = base;
-                e->fFlags = SkToU8(e->fFlags | Edge::kY1Link);
-                break;
-            }
-        }
-    }
-    
-    e = base;
-    if ((base->fFlags & Edge::kY1Link) == 0) {
-        for (;;) {
-            e += 1;
-            if ((e->fFlags & Edge::kY0Link) == 0 && y1 == e->fY0) {
-                SkASSERT(NULL == base->fNext);
-                base->fNext = e;
-                e->fFlags = SkToU8(e->fFlags | Edge::kY0Link);
-                break;
-            }
-        }
-    }
-        
-    base->fFlags = Edge::kCompleteLink;
-}
-
-static int extract_path(Edge* edge, Edge* stop, SkPath* path) {
-    while (0 == edge->fFlags) {
-        edge++; // skip over "used" edges
-    }
-
-    SkASSERT(edge < stop);
-
-    Edge* base = edge;
-    Edge* prev = edge;
-    edge = edge->fNext;
-    SkASSERT(edge != base);
-
-    int count = 1;
-    path->moveTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY0));
-    prev->fFlags = 0;
-    do {
-        if (prev->fX != edge->fX || prev->fY1 != edge->fY0) { // skip collinear
-            path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1));    // V
-            path->lineTo(SkIntToScalar(edge->fX), SkIntToScalar(edge->fY0));    // H
-        }
-        prev = edge;
-        edge = edge->fNext;
-        count += 1;
-        prev->fFlags = 0;
-    } while (edge != base);
-    path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1));    // V
-    path->close();
-    return count;
-}
-
-#include "SkTSearch.h"
-
-static int EdgeProc(const Edge* a, const Edge* b) {
-    return (a->fX == b->fX) ? a->top() - b->top() : a->fX - b->fX;
-}
-
-bool SkRegion::getBoundaryPath(SkPath* path) const {
-    if (this->isEmpty()) {
-        return false;
-    }
-
-    const SkIRect& bounds = this->getBounds();
-
-    if (this->isRect()) {
-        SkRect  r;        
-        r.set(bounds);      // this converts the ints to scalars
-        path->addRect(r);
-        return true;
-    }
-
-    SkRegion::Iterator  iter(*this);
-    SkTDArray<Edge>     edges;
-    
-    for (const SkIRect& r = iter.rect(); !iter.done(); iter.next()) {
-        Edge* edge = edges.append(2);
-        edge[0].set(r.fLeft, r.fBottom, r.fTop);
-        edge[1].set(r.fRight, r.fTop, r.fBottom);
-    }
-    SkQSort(edges.begin(), edges.count(), sizeof(Edge), (SkQSortCompareProc)EdgeProc);
-    
-    int count = edges.count();
-    Edge* start = edges.begin();
-    Edge* stop = start + count;
-    Edge* e;
-
-    for (e = start; e != stop; e++) {
-        find_link(e, stop);
-    }
-
-#ifdef SK_DEBUG
-    for (e = start; e != stop; e++) {
-        SkASSERT(e->fNext != NULL);
-        SkASSERT(e->fFlags == Edge::kCompleteLink);
-    }
-#endif
-
-    path->incReserve(count << 1);
-    do {
-        SkASSERT(count > 1);
-        count -= extract_path(start, stop, path);
-    } while (count > 0);
-
-    return true;
-}
-