l1fillar.c

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C语言 代码 · 共 542 行 · 第 1/2 页

/****************************************************************************
*
*                            Open Watcom Project
*
*    Portions Copyright (c) 1983-2002 Sybase, Inc. All Rights Reserved.
*
*  ========================================================================
*
*    This file contains Original Code and/or Modifications of Original
*    Code as defined in and that are subject to the Sybase Open Watcom
*    Public License version 1.0 (the 'License'). You may not use this file
*    except in compliance with the License. BY USING THIS FILE YOU AGREE TO
*    ALL TERMS AND CONDITIONS OF THE LICENSE. A copy of the License is
*    provided with the Original Code and Modifications, and is also
*    available at www.sybase.com/developer/opensource.
*
*    The Original Code and all software distributed under the License are
*    distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
*    EXPRESS OR IMPLIED, AND SYBASE AND ALL CONTRIBUTORS HEREBY DISCLAIM
*    ALL SUCH WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF
*    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR
*    NON-INFRINGEMENT. Please see the License for the specific language
*    governing rights and limitations under the License.
*
*  ========================================================================
*
* Description:  WHEN YOU FIGURE OUT WHAT THIS FILE DOES, PLEASE
*               DESCRIBE IT HERE!
*
****************************************************************************/


#include "gdefn.h"
#if !defined( _DEFAULT_WINDOWS )
#include <malloc.h>
#include "stkavail.h"


struct seg_entry {
    struct line_entry   line;
    short               end_pt;
    struct seg_entry    *link;
    short               delete;
};


static short            NumMinima;
static short            *MinList;
static struct seg_entry *LineList;
static struct seg_entry *FreeList;
static int              StackSize;
static char *           Stack;


static short NextPoint( short i, short dir, short n,
                        struct xycoord _WCI86FAR *points )
//===================================================

//  Find the next point after i, which has a different y value.

{
    short               p;
    short               y;

    y = points[ i ].ycoord;
    for( p = i + dir;; p += dir  ) {
        if( p == n ) {  // p %= n
            p = 0;
        } else if ( p < 0 ) {
            p = n - 1;
        }
        if( p == i ) {      // back to the start
            break;
        }
        if( points[ p ].ycoord != y ) {
            break;
        }
    }
    return( p );
}


static void CalcMinima( short n, struct xycoord _WCI86FAR *points )
//============================================================

//  Detect and store away all of the minimas. Sort the minima's
//  by y value.

{
    short               curr_y;
    short               i;
    short               j;
    short               start;
    short               next;
    short               prev;
    short               min;

    NumMinima = 0;
    start = NextPoint( 0, 1, n, points );
    i = start;
    do {
        next = NextPoint( i, 1, n, points );
        prev = NextPoint( i, -1, n, points );
        curr_y = points[ i ].ycoord;
        if( points[ prev ].ycoord > curr_y && points[ next ].ycoord > curr_y ) {
            // found a minima, add to min list, sort by y value
            if( ( NumMinima + 1 ) * sizeof( short ) > StackSize ) {
                _ErrorStatus = _GRINSUFFICIENTMEMORY;   // need room for 1 more
                NumMinima = 0;  // signal error
                return;
            }
            for( min = 0; min < NumMinima; ++min ) {
                if( curr_y < points[ MinList[ min ] ].ycoord ) {
                    // shift rest of list up
                    for( j = NumMinima; j > min; --j ) {
                        MinList[ j ] = MinList[ j - 1 ];
                    }
                    break;
                }
            }
            MinList[ min ] = i;
            ++NumMinima;
        }
        i = next;
    } while( next != start );
    if( NumMinima == 0 ) {
        _ErrorStatus = _GRINVALIDPARAMETER;     // no minima found
    }
}


static void OrderLines( void )
//======================

//  Order the line segments by x value.

{
    struct seg_entry    *curr;
    struct seg_entry    *next;
    struct seg_entry    *prev;
    char                swap;
    struct seg_entry    temp;   // dummy entry for start of list

    temp.link = LineList;   // place start of list in dummy so that
    do {                    // we can do swaps more easily
        swap = 0;
        prev = &temp;
        for( ;; ) {
            curr = prev->link;
            if( curr == NULL ) {
                break;
            }
            next = curr->link;
            if( next == NULL ) {
                break;
            }
            if( curr->line.curr_x > next->line.curr_x ) {
                prev->link = next;
                curr->link = next->link;
                next->link = curr;
                swap = 1;
            }
            prev = curr;
        }
    } while( swap );
    LineList = temp.link;       // reload start of list
}


static short AddLine( short p1, short p2, struct xycoord _WCI86FAR *points )
//=====================================================================

{
    struct seg_entry    *segment;

    segment = FreeList;         // get element from free list
    if( segment == NULL ) {
        _ErrorStatus = _GRINSUFFICIENTMEMORY;
        return( FALSE );
    }
    FreeList = FreeList->link;
    _LineInit( points[ p1 ].xcoord, points[ p1 ].ycoord,
               points[ p2 ].xcoord, points[ p2 ].ycoord, &segment->line );
    segment->end_pt = p2;
    segment->delete = FALSE;
    segment->link = LineList;
    LineList = segment;
    return( TRUE );
}


static short AddMinima( short y, short n, struct xycoord _WCI86FAR *points )
//=====================================================================

{
    short               p;
    short               prev;
    short               next;
    short               p2;

    p = MinList[ 0 ];
    for( ;; ) {
        prev = NextPoint( p, -1, n, points );
        p2 = prev + 1;
        if( p2 == n ) {
            p2 = 0;
        }
        if( !AddLine( p2, prev, points ) ) {
            return( FALSE );
        }
        next = NextPoint( p, 1, n, points );
        p2 = next - 1;
        if( p2 < 0 ) {
            p2 = n - 1;
        }
        if( !AddLine( p2, next, points ) ) {
            return( FALSE );
        }
        --NumMinima;
        if( NumMinima == 0 ) {
            break;
        }
        ++MinList;              // advance list
        p = MinList[ 0 ];
        if( points[ p ].ycoord != y ) {     // check for more on this line
            break;
        }
    }
    OrderLines();
    return( TRUE );
}


static void ExtendLines( short y, short n, struct xycoord _WCI86FAR *points )
//======================================================================

//  Replace line segments ending at the current y value with their
//  upward extension.

{
    struct seg_entry    *line;
    short               p;
    short               p1;
    short               p2;
    short               end_x;
    short               old_left;
    short               old_right;

    for( line = LineList; line != NULL; line = line->link ) {
        p = line->end_pt;
        if( points[ p ].ycoord == y ) {
            // current line ends at this point, so make sure the
            // line doesn't extend past the ending x value
            end_x = points[ p ].xcoord;
            if( line->line.sdx > 0 ) {
                line->line.right_x = end_x;
            } else {
                line->line.left_x = end_x;
            }
            p2 = NextPoint( p, -1, n, points );
            if( points[ p2 ].ycoord > y ) {
                p1 = p2 + 1;
                if( p1 == n ) {
                    p1 = 0;
                }
            } else {
                p2 = NextPoint( p, 1, n, points );
                if( points[ p2 ].ycoord > y ) {
                    p1 = p2 - 1;
                    if( p1 < 0 ) {
                        p1 = n - 1;