Initial revisionXORG-STABLE

1 files changed, 1614 insertions, 0 deletions

diff --git a/src/Clip.c b/src/Clip.c
new file mode 100644
index 0000000..0f6d410
--- /dev/null
+++ b/src/Clip.c
@@ -0,0 +1,1614 @@
+/*
+ * Copyright (c) 1998 by The XFree86 Project, Inc.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE XFREE86 PROJECT BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
+ * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ *
+ * Except as contained in this notice, the name of the XFree86 Project shall
+ * not be used in advertising or otherwise to promote the sale, use or other
+ * dealings in this Software without prior written authorization from the
+ * XFree86 Project.
+ */
+/* $XFree86: xc/lib/Xmu/Clip.c,v 1.2 1999/08/15 13:00:44 dawes Exp $ */
+
+#include <stdlib.h>
+
+#include <X11/IntrinsicP.h>
+#include <X11/Xmu/Xmu.h>
+
+#define XmuMax(a, b)	((a) > (b) ? (a) : (b))
+#define XmuMin(a, b)	((a) < (b) ? (a) : (b))
+
+/*
+ * Function:
+ *	XmuNewArea
+ *
+ * Parameters:
+ *	x1 - Coordinates of the rectangle
+ *	y1 - ""
+ *	x2 - ""
+ *	y2 - ""
+ *
+ * Description:
+ *	Creates a new rectangular clipping area
+ */
+XmuArea *
+XmuNewArea(int x1, int y1, int x2, int y2)
+{
+  XmuArea *area;
+
+  area = (XmuArea *)XtMalloc(sizeof(XmuArea));
+  if (x2 > x1 && y2 > y1)
+    {
+      area->scanline = XmuNewScanline(y1, x1, x2);
+      area->scanline->next = XmuNewScanline(y2, 0, 0);
+    }
+  else
+    area->scanline = (XmuScanline *)NULL;
+
+  return (area);
+}
+
+/*
+ * Function:
+ *	XmuAreaDup
+ *
+ * Parameters:
+ *	area - Area to copy
+ *
+ * Description:
+ *	Returns a copy of its argument
+ */
+XmuArea *
+XmuAreaDup(XmuArea *area)
+{
+  XmuArea *dst;
+
+  if (!area)
+    return ((XmuArea *)NULL);
+
+  dst = XmuCreateArea();
+  XmuAreaCopy(dst, area);
+  return (dst);
+}
+
+/*
+ * Function:
+ *	XmuAreaCopy
+ *
+ * Parameters:
+ *	dst - destination area
+ *	src - source area
+ *
+ * Description:
+ *	Minimizes memory alocation, trying to use already alocated memory
+ *	in dst, freeing what is not required anymore.
+ */
+XmuArea *
+XmuAreaCopy(XmuArea *dst, XmuArea *src)
+{
+  XmuScanline *z, *p, *Z;
+
+  if (!dst || !src || dst == src)
+    return (dst);
+
+  z = p = dst->scanline;
+  Z = src->scanline;
+
+  /*CONSTCOND*/
+  while (1)
+    {
+      if (!Z)
+	{
+	  if (z == dst->scanline)
+	    {
+	      XmuDestroyScanlineList(dst->scanline);
+	      dst->scanline = (XmuScanline *)NULL;
+	    }
+	  else
+	    {
+	      XmuDestroyScanlineList(p->next);
+	      p->next = (XmuScanline *)NULL;
+	    }
+	  return (dst);
+	}
+      if (z)
+	{
+	  XmuScanlineCopy(z, Z);
+	  z->y = Z->y;
+	}
+      else
+	{
+	  z = XmuNewScanline(Z->y, 0, 0);
+	  XmuScanlineCopy(z, Z);
+	  if (p == dst->scanline && !dst->scanline)
+	    p = dst->scanline = z;
+	  else
+	    p->next = z;
+	}
+      p = z;
+      z = z->next;
+      Z = Z->next;
+    }
+
+  return (dst);
+}
+
+/*
+ * Function:
+ *   XmuAreaNot
+ *
+ * Parameters:
+ *	area - area to operate
+ *	x1   - retangle to clip the result against
+ *	y1   - ""
+ *	x2   - ""
+ *	y2   - ""
+ *
+ * Description:
+ * (Input)
+ * (x1, y1)                                                (x2, y1)
+ *                   +-------------+
+ *      +------------+             +----+
+ *      |                +--------------+
+ *      +----------------+
+ * (x1, y2)                                                (x2, y2)
+ *
+ * (Output)
+ * (x1, y1)                                                (x2, y1)
+ *    +--------------+             +--------------------------+
+ *    | +------------+             +----+                     |
+ *    | |                +--------------+                     |
+ *    +-+                +------------------------------------+
+ * (x1, y2)                                                (x2, y2)
+ */
+XmuArea *
+XmuAreaNot(XmuArea *area, int x1, int y1, int x2, int y2)
+{
+  XmuScanline *z;
+  XmuArea *and;
+
+  if (!area)
+    return (area);
+
+  if (x1 > x2)
+    {
+      x1 ^= x2; x2 ^= x1; x1 ^= x2;
+    }
+    if (y1 > y2)
+      {
+	y1 ^= y2; y2 ^= y1; y1 ^= y2;
+      }
+    if (!area->scanline)
+      {
+	if ((area->scanline = XmuNewScanline(y1, x1, x2)) != NULL)
+	  area->scanline->next = XmuNewScanline(y2, 0, 0);
+	return (area);
+      }
+    and = XmuNewArea(x1, y1, x2, y2);
+    XmuAreaAnd(area, and);
+    XmuDestroyArea(and);
+    z = area->scanline;
+    if (z->y != y1)
+      {
+	XmuScanline *q = XmuNewScanline(y1, x1, x2);
+	q->next = z;
+	area->scanline = q;
+      }
+    else
+      {
+	area->scanline = area->scanline->next;
+	XmuDestroyScanline(z);
+	XmuOptimizeArea(area);
+	if((z = area->scanline) == (XmuScanline *)NULL)
+	  return (area);
+      }
+
+    /* CONSTCOND */
+    while (1)
+      {
+	XmuScanlineNot(z, x1, x2);
+	if (!z->next)
+	  {
+	    z->next = XmuNewScanline(y2, 0, 0);
+	    break;
+	  }
+	if (z->next->y == y2)
+	  {
+	    XmuDestroyScanlineList(z->next);
+	    z->next = XmuNewScanline(y2, 0, 0);
+	    break;
+	  }
+	z = z->next;
+      }
+
+    return (area);
+}
+
+/*
+ * Function:
+ *	XmuAreaOrXor
+ *
+ * Parameters:
+ *	dst - destination area
+ *	src - source area
+ *	or  - or operation if true, else xor operation
+ *
+ * Description:
+ *	Executes Or (Union) or Xor (Reverse intesection) of the areas
+ */
+XmuArea *
+XmuAreaOrXor(XmuArea *dst, XmuArea *src, Bool or)
+{
+  XmuScanline *z, *p, *Z, *P, *ins, *top;
+
+  if (!dst || !src)
+    return (dst);
+
+  if (dst == src)
+    {
+      if (or)
+	return (dst);
+      XmuDestroyScanlineList(dst->scanline);
+      dst->scanline = (XmuScanline *)NULL;
+      return (dst);
+    }
+  if (!XmuValidArea(src))
+    return (dst);
+  if (!XmuValidArea(dst))
+    {
+      XmuAreaCopy(dst, src);
+      return (dst);
+    }
+
+  p = z = dst->scanline;
+  P = Z = src->scanline;
+  ins = XmuNewScanline(dst->scanline->y, 0, 0);
+  top = XmuNewScanline(dst->scanline->y, 0, 0);
+  XmuScanlineCopy(ins, dst->scanline);
+  XmuScanlineCopy(top, dst->scanline);
+
+  /*CONSTCOND*/
+  while (1)
+    {
+      if (!Z)
+	break;
+      else if (Z->y < z->y)
+	{
+	  XmuScanline  *q = XmuNewScanline(Z->y, 0, 0);
+	  XmuScanlineCopy(q, Z);
+
+	  if (z == dst->scanline)
+	    {
+	      dst->scanline = p = q;
+	      q->next = z;
+            }
+	  else
+	    {
+	      p->next = q;
+	      q->next = z;
+	      if (Z->y >= p->y)
+		{
+		  if (ins->y >= top->y
+		      && (p->y != P->y || !XmuScanlineEqu(p, P)
+			  || (ins->y <= P->y && !XmuScanlineEqu(ins, P))))
+		    {
+		      if (or)
+			XmuScanlineOr(q, ins);
+		      else
+			XmuScanlineXor(q, ins);
+                    }
+		  else if (Z->y >= top->y
+			   && (top->y == p->y || top->y > ins->y
+			       || !XmuValidScanline(Z)
+			       || (p->y == P->y && XmuValidScanline(p)
+				   && XmuValidScanline(P))
+			       || XmuScanlineEqu(ins, top)))
+		    {
+		      if (or)
+			XmuScanlineOr(q, top);
+		      else
+			XmuScanlineXor(q, top);
+		    }
+		  if (ins->y != p->y && p->y != P->y)
+		    {
+		      XmuScanlineCopy(ins, p);
+		      ins->y = p->y;
+		    }
+		}
+	      if (!XmuValidScanline(p) || Z->y <= p->y)
+		{
+		  XmuScanlineCopy(top, p);
+		  top->y = p->y;
+                }
+	      p = q;
+	    }
+	  P = Z;
+	  Z = Z->next;
+	  continue;
+        }
+      else if (Z->y == z->y)
+	{
+	  if (top->y != z->y)
+	    {
+	      XmuScanlineCopy(top, z);
+	      top->y = z->y;
+	    }
+	  if (or)
+	    XmuScanlineOr(z, Z);
+	  else
+	    XmuScanlineXor(z, Z);
+	  P = Z;
+	  Z = Z->next;
+	}
+      else if (P != Z)		/* && Z->y > z->y */
+	{
+	  if (top->y == ins->y && top->y != z->y)
+	    {
+	      XmuScanlineCopy(top, z);
+	      top->y = z->y;
+	    }
+	  if (ins->y != z->y)
+	    {
+	      XmuScanlineCopy(ins, z);
+	      ins->y = z->y;
+	    }
+	  if (or)
+	    XmuScanlineOr(z, P);
+	  else
+	    XmuScanlineXor(z, P);
+	}
+      else if (ins->y != z->y)
+	{
+	  XmuScanlineCopy(ins, z);
+	  ins->y = z->y;
+	}
+      p = z;
+      z = z->next;
+      if (!z)
+	{
+	  while (Z)
+	    {
+	      p->next = XmuNewScanline(Z->y, 0, 0);
+	      XmuScanlineCopy(p->next, Z);
+	      p = p->next;
+	      Z = Z->next;
+	    }
+	  break;
+	}
+      else if (ins->y > top->y && !XmuValidScanline(z)
+	       && XmuValidScanline(ins))
+	{
+	  XmuScanlineCopy(top, ins);
+	  top->y = ins->y;
+	}
+    }
+  XmuOptimizeArea(dst);
+  XmuDestroyScanline(ins);
+  XmuDestroyScanline(top);
+
+  return (dst);
+}
+
+/*
+ * Function:
+ *	XmuAreaAnd(dst, src)
+ *
+ * Parameters:
+ *	dst - destination area
+ *	src - source area
+ *
+ * Description:
+ *	Executes And (intersection) of the areas
+ */
+XmuArea *
+XmuAreaAnd(XmuArea *dst, XmuArea *src)
+{
+  XmuScanline *z, *p, *Z, *P, *top;
+
+  if (!dst || !src || dst == src)
+    return (dst);
+  if (!XmuValidArea(dst) || !XmuValidArea(src))
+    {
+      XmuDestroyScanlineList(dst->scanline);
+      dst->scanline = (XmuScanline *)NULL;
+      return (dst);
+    }
+  z = p = dst->scanline;
+  Z = P = src->scanline;
+  top = XmuNewScanline(dst->scanline->y, 0, 0);
+  XmuScanlineCopy(top, dst->scanline);
+
+  while (z)
+    {
+      while (Z->next && Z->next->y < z->y)
+	{
+	  P = Z;
+	  Z = Z->next;
+	  if (Z->y >= p->y)
+	    {
+	      XmuScanline *q = XmuNewScanline(Z->y, 0, 0); 
+	      XmuScanlineCopy(q, Z);
+
+	      XmuScanlineAnd(q, top);
+	      if (p->y != P->y)
+		{
+		  XmuScanlineAnd(p, P);
+		  p->y = XmuMax(p->y, P->y);
+		}
+	      p->next = q;
+	      q->next = z;
+	      p = q;
+	    }
+	}
+      if (!z->next)
+	{
+	  z->y = XmuMax(z->y, Z->y);
+	  break;
+        }
+      while (Z->y >= z->next->y)
+	{
+	  if (z == dst->scanline)
+	    {
+	      p = dst->scanline = dst->scanline->next;
+	      XmuDestroyScanline(z);
+	      z = dst->scanline;
+	    }
+	  else
+	    {
+	      p->next = z->next;
+	      XmuDestroyScanline(z);
+	      z = p;
+	    }
+	  if (!z || !z->next)
+	    {
+	      XmuOptimizeArea(dst);
+	      XmuDestroyScanline(top);
+
+	      return (dst);
+	    }
+	}
+      if (Z->y > p->y)
+	z->y = XmuMax(z->y, Z->y);
+      if (top->y != z->y)
+	{
+	  XmuScanlineCopy(top, z);
+	  top->y = z->y;
+	}
+      XmuScanlineAnd(z, Z);
+      p = z;
+      z = z->next;
+    }
+  XmuOptimizeArea(dst);
+  XmuDestroyScanline(top);
+
+  return (dst);
+}
+
+/*
+ * Function:
+ *   XmuValidArea(area)
+ *
+ * Parameters:
+ *	area - area to verify
+ *
+ * Description:
+ *	Verifies if the area is valid and/or useful
+ */
+Bool
+XmuValidArea(XmuArea *area)
+{
+  XmuScanline *at;
+
+  if (!area || !area->scanline)
+    return (False);
+
+  at = area->scanline;
+  while (at)
+    {
+      if (XmuValidScanline(at))
+	return (True);
+      at = at->next;
+    }
+
+  return (False);
+}
+
+/*
+ * Function:
+ *	XmuValidScanline
+ *
+ * Parameters:
+ *	scanline - scanline to verify
+ *
+ * Description:
+ *	Verifies if a scanline is useful
+ */
+Bool
+XmuValidScanline(XmuScanline *scanline)
+{
+  XmuSegment *z;
+
+  if (!scanline)
+    return (False);
+
+  z = scanline->segment;
+  while (z)
+    {
+      if (XmuValidSegment(z))
+	return (True);
+      z = z->next;
+    }
+
+  return (False);
+}
+
+/*
+ * Function:
+ *   XmuScanlineEqu
+ *
+ * Parameters:
+ *	s1 - scanline 1
+ *	s2 - scanline 2
+ *
+ * Description:
+ *	Checks if s1 and s2 are equal
+ */
+Bool
+XmuScanlineEqu(XmuScanline *s1, XmuScanline *s2)
+{
+  XmuSegment *z, *Z;
+
+  if ((!s1 && !s2) || s1 == s2)
+    return (True);
+  if (!s1 || !s2)
+    return (False);
+
+  z = s1->segment;
+  Z = s2->segment;
+
+  /*CONSTCOND*/
+  while (1)
+    {
+      if (!z && !Z)
+	return (True);
+      if (!z || !Z)
+	return (False);
+      if (!XmuSegmentEqu(z, Z))
+	return (False);
+      z = z->next;
+      Z = Z->next;
+    }
+  /*NOTREACHED*/
+}
+
+/*
+ * Function:
+ *	XmuNewSegment
+ *
+ * Parameters:
+ *	x1 - coordinates of the segment
+ *	x2 - ""
+ *
+ * Description:
+ *	Creates a new segments with the coordinates x1 and x2
+ *
+ * Returns:
+ *	New Segment of NULL
+ */
+XmuSegment *
+XmuNewSegment(int x1, int x2)
+{
+  XmuSegment *segment;
+
+  if ((segment = (XmuSegment *)XtMalloc(sizeof(XmuSegment))) == NULL)
+    return (segment);
+
+  segment->x1 = x1;
+  segment->x2 = x2;
+  segment->next = (XmuSegment *)NULL;
+
+  return (segment);
+}
+
+/*
+ * Function:
+ *	XmuDestroySegmentList
+ *
+ * Parameters:
+ *	segment - Segment to destroy
+ *
+ * Description:
+ *	Frees the memory used by the list headed by segment
+ */
+void
+XmuDestroySegmentList(XmuSegment *segment)
+{
+  XmuSegment *z;
+
+  if (!segment)
+    return;
+
+  while (segment)
+    {
+      z = segment;
+      segment = segment->next;
+      XmuDestroySegment(z);
+    }
+}
+
+/*
+ * Function:
+ *	XmuScanlineCopy
+ *
+ * Parameters:
+ *	dst - destination scanline
+ *	src - source scanline
+ *
+ * Description:
+ *	Makes dst contain the same data as src
+ */
+XmuScanline *
+XmuScanlineCopy(XmuScanline *dst, XmuScanline *src)
+{
+  XmuSegment *z, *p, *Z;
+
+  if (!dst || !src || dst == src)
+    return (dst);
+
+  z = p = dst->segment;
+  Z = src->segment;
+
+  /*CONSTCOND*/
+  while (1)
+    {
+      if (!Z)
+	{
+	  if (z == dst->segment)
+	    dst->segment = (XmuSegment *)NULL;
+	  else
+	    p->next = (XmuSegment *)NULL;
+	  XmuDestroySegmentList(z);
+	  return (dst);
+	}
+      if (z)
+	{
+	  z->x1 = Z->x1;
+	  z->x2 = Z->x2;
+	}
+      else
+	{
+	  z = XmuNewSegment(Z->x1, Z->x2);
+	  if (p == dst->segment && !dst->segment)
+	    p = dst->segment = z;
+	  else
+	    p->next = z;
+	}
+      p = z;
+      z = z->next;
+      Z = Z->next;
+    }
+  /*NOTREACHED*/
+}
+
+/*
+ * Function:
+ *	XmuAppendSegment
+ *
+ * Parameters:
+ *	segment - destination segment
+ *	append  - segment to add
+ *
+ * Description:
+ *	Adds a copy of the append list at the end of the segment list
+ */
+Bool
+XmuAppendSegment(XmuSegment *segment, XmuSegment *append)
+{
+  if (!segment || !append)
+    return (False);
+
+  if (segment->next)
+    /* Should not happen! */
+    XmuDestroySegmentList(segment->next);
+
+  while (append)
+    {
+      if (XmuValidSegment(append))
+	{
+	  if ((segment->next = XmuNewSegment(append->x1, append->x2)) == NULL)
+	    return (False);
+	  segment = segment->next;
+	}
+      append = append->next;
+    }
+
+  return (True);
+}
+
+/*
+ * Function:
+ *	XmuOptimizeScanline
+ *
+ * Parameters:
+ *	scanline - scanline to optimize
+ *
+ * Description:
+ *	  Some functions, when transforming Segments of Scanlines, left these
+ *	with unnecessary data (that may cause error in these same functions).
+ *	  This function corrects these incorrect segments.
+ */
+XmuScanline *
+XmuOptimizeScanline(XmuScanline *scanline)
+{
+  XmuSegment *z, *p;
+
+  while (scanline->segment && !XmuValidSegment(scanline->segment))
+    {
+      XmuSegment *s = scanline->segment;
+
+      scanline->segment = scanline->segment->next;
+      XmuDestroySegment(s);
+    }
+  for (z = p = scanline->segment; z; p = z, z = z->next)
+    {
+      if (!XmuValidSegment(z))
+	{
+	  p->next = z->next;
+	  XmuDestroySegment(z);
+	  z = p;
+	}
+    }
+  return (scanline);
+}
+
+/*
+ * Name:
+ *	XmuScanlineNot(scanline, minx, maxx)
+ *
+ * Parameters:
+ *	scanline - scanlines operate
+ *	minx	 - minimum x coordinate
+ *	maxx	 - maximum x coordinate
+ *
+ * Description:
+ *         (minx)                                                        (maxx)
+ *           +                                                             +
+ * (input)         +---------+     +--------+        +--------+
+ * (output)  +-----+         +-----+        +--------+        +------------+
+ */
+XmuScanline *
+XmuScanlineNot(XmuScanline *scanline, int minx, int maxx)
+{
+  XmuSegment *z;
+  static XmuSegment x = { 0, 0, 0 };
+  static XmuScanline and = { 0, &x, 0 };
+
+  if (!scanline)
+    return (scanline);
+
+  XmuOptimizeScanline(scanline);
+  if (minx > maxx)
+    {
+      minx ^= maxx; maxx ^= minx; minx ^= maxx;
+    }
+  and.segment->x1 = minx;
+  and.segment->x2 = maxx;
+  XmuScanlineAnd(scanline, &and);
+  if (!scanline->segment)
+    {
+      scanline->segment = XmuNewSegment(minx, maxx);
+      return (scanline);
+    }
+  z = scanline->segment;
+  if (z->x1 != minx)
+    {
+      XmuSegment *q = XmuNewSegment(minx, z->x1);
+
+      q->next = z;
+      scanline->segment = q;
+    }
+
+  /*CONSTCOND*/
+  while (1)
+    {
+      z->x1 = z->x2;
+      if (!z->next)
+	{
+	  z->x2 = maxx;
+	  break;
+	}
+      z->x2 = z->next->x1;
+      if (z->next->x2 == maxx)
+	{
+	  XmuDestroySegment(z->next);
+	  z->next = (XmuSegment *)NULL;
+	  break;
+	}
+      z = z->next;
+    }
+
+  return (scanline);
+}
+
+
+#ifndef notdef
+/*
+ * Function:
+ *	XmuScanlineOrSegment
+ *
+ * Parameters:
+ *	dst - destionation scanline
+ *	src - source segment
+ *
+ * Description:
+ * (input)      +-----------+  +--------+    +---------+
+ * (src)              +-------------------+
+ * (output)     +-------------------------+  +---------+
+ */
+XmuScanline *
+XmuScanlineOrSegment(XmuScanline *dst, XmuSegment *src)
+{
+  XmuSegment *z, *p, ins;
+
+  if (!src || !dst || !XmuValidSegment(src))
+    return (dst);
+
+  if (!dst->segment)
+    {
+      dst->segment = XmuNewSegment(src->x1, src->x2);
+      return (dst);
+    }
+
+  z = p = dst->segment;
+  ins.x1 = src->x1;
+  ins.x2 = src->x2;
+
+  /*CONSTCOND*/
+  while (1)
+    {
+      if (!z)
+	{
+            XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);
+
+	    if (p == dst->segment && z == p)
+	      dst->segment = q;
+	    else
+	      p->next = q;
+	    break;
+	}
+      else if (ins.x2 < z->x1)
+	{
+	  XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);
+
+	  if (p == dst->segment && z == p)
+	    {
+	      q->next = dst->segment;
+	      dst->segment = q;
+	    }
+	  else
+	    {
+	      p->next = q;
+	      q->next = z;
+	    }
+	  break;
+        }
+      else if (ins.x2 <= z->x2)
+	{
+	  z->x1 = XmuMin(z->x1, ins.x1);
+	  break;
+	}
+      else if (ins.x1 <= z->x2)
+	{
+	  ins.x1 = XmuMin(z->x1, ins.x1);
+	  if (!z->next)
+	    {
+	      z->x1 = ins.x1;
+	      z->x2 = ins.x2;
+	      break;
+	    }
+	  else
+	    {
+	      if (z == dst->segment)
+		{
+		  p = dst->segment = dst->segment->next;
+		  XmuDestroySegment(z);
+		  z = dst->segment;
+		  continue;
+		}
+	      else
+		{
+		  p->next = z->next;
+		  XmuDestroySegment(z);
+		  z = p;
+		}
+	    }
+	}
+      p = z;
+      z = z->next;
+    }
+
+  return (dst);
+}
+
+/*
+ * Function:
+ *	XmuScanlineAndSegment
+ *
+ * Parameters:
+ *	dst - destination scanline
+ *	src - source segment
+ *
+ * Description:
+ * (input)      +------------+   +------+     +----------+
+ * (src)             +---------------------+
+ * (output)          +-------+   +------+
+ */
+XmuScanline *
+XmuScanlineAndSegment(XmuScanline *dst, XmuSegment *src)
+{
+  XmuSegment *z, *p;
+
+  if (!dst || !src)
+    return (dst);
+
+  if (!XmuValidSegment(src))
+    {
+      XmuDestroySegmentList(dst->segment);
+      dst->segment = (XmuSegment *)NULL;
+      return (dst);
+    }
+  if (!dst->segment)
+    return (dst);
+
+  z = p = dst->segment;
+  while (z)
+    {
+      if (src->x2 <= z->x1 || src->x1 >= z->x2)
+	{
+	  if (z == dst->segment)
+	    {
+	      p = dst->segment = dst->segment->next;
+	      XmuDestroySegment(z);
+	      z = dst->segment;
+	      continue;
+	    }
+	  else
+	    {
+	      p->next = z->next;
+	      XmuDestroySegment(z);
+	      z = p;
+	    }
+	}
+      else
+	{
+	  z->x1 = XmuMax(z->x1, src->x1);
+	  z->x2 = XmuMin(z->x2, src->x2);
+	}
+      p = z;
+      z = z->next;
+    }
+
+  return (dst);
+}
+
+/*
+ * Function:
+ *	XmuScanlineXorSegment
+ *
+ * Parameters:
+ *	dst - destionation scanline
+ *	src - source segment
+ *
+ * Descriptipn:
+ * (input)     +------------+  +----------+    +-----------+
+ * (src)           +------------------------+
+ * (output)    +---+        +--+          +-+  +-----------+
+ */
+XmuScanline *
+XmuScanlineXorSegment(XmuScanline *dst, XmuSegment *src)
+{
+  XmuSegment *p, *z, ins;
+  int tmp1, tmp2;
+
+  if (!dst || !src || !XmuValidSegment(src))
+    return (dst);
+  if (!dst->segment)
+    {
+      dst->segment = XmuNewSegment(src->x1, src->x2);
+      return (dst);
+    }
+
+  p = z = dst->segment;
+  ins.x1 = src->x1;
+  ins.x2 = src->x2;
+
+  /*CONSTCOND*/
+  while (1)
+    {
+      if (!XmuValidSegment((&ins)))
+	break;
+      if (!z || ins.x2 < z->x1)
+	{
+	  XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);
+
+	  q->next = z;
+	  if (z == dst->segment)
+	    dst->segment = q;
+	  else
+	    p->next = q;
+	  break;
+	}
+      else if (ins.x2 == z->x1)
+	{
+	  z->x1 = ins.x1;
+	  break;
+	}
+      else if (ins.x1 < z->x2)
+	{
+	  if (ins.x1 < z->x1)
+	    {
+	      tmp1 = ins.x2;
+	      tmp2 = z->x2;
+	      ins.x2 = XmuMax(ins.x2, z->x2);
+	      z->x2 = z->x1;
+	      z->x1 = ins.x1;
+	      ins.x1 = XmuMin(tmp1, tmp2);
+	    }
+	  else if (ins.x1 > z->x1)
+	    {
+	      tmp1 = ins.x1;
+	      ins.x1 = XmuMin(ins.x2, z->x2);
+	      ins.x2 = XmuMax(z->x2, ins.x2);
+	      z->x2 = tmp1;
+	    }
+	  else	/* ins.x1 == z->x1 */
+	    {
+	      if (ins.x2 < z->x2)
+		{
+		  z->x1 = ins.x2;
+		  break;
+		}
+	      else
+		{
+		  ins.x1 = z->x2;
+		  if (z == dst->segment)
+		    p = dst->segment = dst->segment->next;
+		  else
+		    p->next = z->next;
+		  XmuDestroySegment(z);
+		  z = p;
+		  continue;
+		}
+	    }
+	}
+      else if (ins.x1 == z->x2)
+	{
+	  ins.x1 = z->x1;
+	  if (z == dst->segment)
+	    p = dst->segment = dst->segment->next;
+	  else
+	    p->next = z->next;
+	  XmuDestroySegment(z);
+	  z = p;
+	  continue;
+	}
+      p = z;
+      z = z->next;
+    }
+
+  return (dst);
+}
+#endif /* notdef */
+
+/*
+ * Function:
+ *	ScanlineOr
+ *
+ * Parameters:
+ *	dst - destionation scanline
+ *	src - source scanline
+ *
+ * Description:
+ * (input)    +--------------+  +-----+    +----------+
+ * (src)          +---------------------+       +-----------+
+ * (output)   +-------------------------+  +----------------+
+ */
+XmuScanline *
+XmuScanlineOr(XmuScanline *dst, XmuScanline *src)
+{
+  XmuSegment *z, *p, *Z, ins;
+
+  if (!src || !src->segment || !dst || dst == src)
+    return (dst);
+  if (!dst->segment)
+    {
+      XmuScanlineCopy(dst, src);
+      return (dst);
+    }
+
+  z = p = dst->segment;
+  Z = src->segment;
+  ins.x1 = Z->x1;
+  ins.x2 = Z->x2;
+
+  /*CONSTCOND*/
+  while (1)
+    {
+      while (!XmuValidSegment((&ins)))
+	{
+	  if ((Z = Z->next) == (XmuSegment *)NULL)
+	    return (dst);
+	  ins.x1 = Z->x1;
+	  ins.x2 = Z->x2;
+	}
+        if (!z)
+	  {
+            XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);
+
+            if (p == dst->segment && z == p)
+	      dst->segment = p = q;
+            else
+	      {
+		p->next = q;
+		p = q;
+	      }
+	    Z = Z->next;
+	    XmuAppendSegment(p, Z);
+	    break;
+	  }
+        else if (ins.x2 < z->x1)
+	  {
+	    XmuSegment *r = XmuNewSegment(ins.x1, ins.x2);
+
+	    if (p == dst->segment && z == p)
+	      {
+		r->next = dst->segment;
+		dst->segment = p = r;
+	      }
+	    else
+	      {
+		p->next = r;
+		r->next = z;
+		p = r;
+	      }
+	    Z = Z->next;
+            if (!Z)
+	      break;
+            else
+	      {
+		ins.x1 = Z->x1;
+		ins.x2 = Z->x2;
+		continue;
+	      }
+	  }
+	else if (ins.x2 <= z->x2)
+	  {
+	    z->x1 = XmuMin(z->x1, ins.x1);
+	    Z = Z->next;
+	    if (!Z)
+	      break;
+            else
+	      {
+		ins.x1 = Z->x1;
+		ins.x2 = Z->x2;
+		continue;
+	      }
+	  }
+	else if (ins.x1 <= z->x2)
+	  {
+	    ins.x1 = XmuMin(z->x1, ins.x1);
+	    if (!z->next)
+	      {
+		z->x1 = ins.x1;
+		z->x2 = ins.x2;
+		p = z;
+		Z = Z->next;
+		XmuAppendSegment(p, Z);
+		break;
+	      }
+            else
+	      {
+		if (z == dst->segment)
+		  {
+		    p = dst->segment = dst->segment->next;
+		    XmuDestroySegment(z);
+		    z = p;
+		    continue;
+		  }
+                else
+		  {
+		    p->next = z->next;
+		    XmuDestroySegment(z);
+		    z = p;
+		  }
+	      }
+	  }
+	p = z;
+	z = z->next;
+    }
+
+  return (dst);
+}
+
+/*
+ * Function:
+ *	XmuScanlineAnd
+ *
+ * Parameters:
+ *	dst - destination scanline
+ *	src - source scanline
+ *
+ * Description:
+ * (input)    +--------------+  +-----+    +----------+
+ * (src)          +---------------------+       +-----------+
+ * (output)       +----------+  +-----+         +-----+
+ */
+XmuScanline *
+XmuScanlineAnd(XmuScanline *dst, XmuScanline *src)
+{
+  XmuSegment  *z, *p, *Z;
+
+  if (!dst || !src || dst == src || !dst->segment) {
+        return (dst);
+  }
+  if (!src->segment)
+    {
+      XmuDestroySegmentList(dst->segment);
+      dst->segment = (XmuSegment *)NULL;
+      return (dst);
+    }
+  z = p = dst->segment;
+  Z = src->segment;
+
+  while (z)
+    {
+      while (!XmuValidSegment(Z) || Z->x2 <= z->x1)
+	{
+	  Z = Z->next;
+	  if (!Z)
+	    {
+	      if (z == dst->segment)
+		dst->segment = (XmuSegment *)NULL;
+	      else
+		p->next = (XmuSegment *)0;
+	      XmuDestroySegmentList(z);
+	      return (dst);
+	    }
+	}
+      if (Z->x1 >= z->x2)
+	{
+	  if (z == dst->segment)
+	    {
+	      p = dst->segment = dst->segment->next;
+	      XmuDestroySegment(z);
+	      z = dst->segment;
+	    }
+	  else
+	    {
+	      p->next = z->next;
+	      XmuDestroySegment(z);
+	      z = p->next;
+	    }
+	  if (!z)
+	    return (dst);
+	  else
+	    continue;
+	}
+        z->x1 = XmuMax(z->x1, Z->x1);
+	if (z->x2 > Z->x2)
+	  {
+            if (Z->next)
+	      {
+                XmuSegment *q = XmuNewSegment(Z->x2, z->x2);
+
+		q->next = z->next;
+		z->next = q;
+	      }
+	    z->x2 = Z->x2;
+	  }
+	p = z;
+	z = z->next;
+    }
+
+  return (dst);
+}
+
+/*
+ * Function:
+ *	ScanlineXor
+ *
+ * Parameters:
+ *	dst - destination scanline
+ *	src - source scanline
+ *
+ * Description:
+ * (input)    +--------------+  +-----+    +----------+
+ * (src)          +---------------------+       +-----------+
+ * (output)   +---+          +--+     +-+  +----+     +-----+
+ */
+XmuScanline *
+XmuScanlineXor(XmuScanline *dst, XmuScanline *src)
+{
+  XmuSegment *z, *p, *Z, ins;
+  int tmp1, tmp2;
+
+  if (!src || !dst || !src->segment)
+    return (dst);
+  if (src == dst)
+    {
+      XmuDestroySegmentList(dst->segment);
+      dst->segment = (XmuSegment *)NULL;
+      return (dst);
+    }
+  if (!dst->segment)
+    {
+      XmuScanlineCopy(dst, src);
+      return (dst);
+    }
+
+  z = p = dst->segment;
+  Z = src->segment;
+  ins.x1 = Z->x1;
+  ins.x2 = Z->x2;
+
+  /*CONSTCOND*/
+  while (1)
+    {
+      while (!XmuValidSegment((&ins)))
+	{
+	  if ((Z = Z->next) == (XmuSegment *)NULL)
+	    return (dst);
+	  ins.x1 = Z->x1;
+	  ins.x2 = Z->x2;
+	}
+      if (!z)
+	{
+	  XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);
+
+            if (!dst->segment)
+	      dst->segment = q;
+            else
+	      p->next = q;
+	    p = q;
+	    Z = Z->next;
+	    XmuAppendSegment(p, Z);
+	    break;
+	}
+      else if (ins.x2 < z->x1)
+	{
+	  XmuSegment *q = XmuNewSegment(ins.x1, ins.x2);
+
+	  q->next = z;
+	  if (z == dst->segment)
+	    dst->segment = q;
+	  else
+	    p->next = q;
+	  if ((Z = Z->next) == (XmuSegment *)NULL)
+	    return (dst);
+
+	  p = q;
+	  ins.x1 = Z->x1;
+	  ins.x2 = Z->x2;
+	  continue;
+	}
+      else if (ins.x2 == z->x1)
+	{
+	  z->x1 = ins.x1;
+	  if ((Z = Z->next) == (XmuSegment *)NULL)
+	    break;
+	  ins.x1 = Z->x1;
+	  ins.x2 = Z->x2;
+	  continue;
+	}
+      else if (ins.x1 < z->x2)
+	{
+	  if (ins.x1 == z->x1)
+	    {
+	      if (ins.x2 < z->x2)
+		{
+		  z->x1 = ins.x2;
+		  if ((Z = Z->next) == (XmuSegment *)NULL)
+		    break;
+		  ins.x1 = Z->x1;
+		  ins.x2 = Z->x2;
+		  continue;
+		}
+	      else
+		{
+		  ins.x1 = z->x2;
+		  if (z == dst->segment)
+		    p = dst->segment = dst->segment->next;
+		  else
+		    p->next = z->next;
+		  XmuDestroySegment(z);
+		  z = p;
+		  continue;
+		}
+	    }
+	  else
+	    {
+	      if (Z->x2 < z->x2)
+		{
+		  XmuSegment  *q = XmuNewSegment(XmuMin(ins.x1, z->x1),
+						 XmuMax(z->x1, ins.x1));
+
+		  q->next = z;
+		  if (z == dst->segment)
+		    dst->segment = q;
+		  else
+		    p->next = q;
+		  ins.x1 = z->x2;
+		  z->x1 = ins.x2;
+		  p = q;
+		  continue;
+		}
+	      else
+		{
+		  tmp1 = ins.x2;
+		  tmp2 = z->x2;
+		  ins.x2 = XmuMax(ins.x2, z->x2);
+		  z->x2 = XmuMax(z->x1, ins.x1);
+		  z->x1 = XmuMin(ins.x1, z->x1);
+		  ins.x1 = XmuMin(tmp1, tmp2);
+		}
+	    }
+	}
+      else if (ins.x1 == z->x2)
+	{
+	  ins.x1 = z->x1;
+	  if (z == dst->segment)
+	    p = dst->segment = dst->segment->next;
+	  else
+	    p->next = z->next;
+	  XmuDestroySegment(z);
+	  z = p;
+	  continue;
+	}
+      p = z;
+      z = z->next;
+    }
+
+  return (dst);
+}
+
+/*
+ * Function:
+ *	XmuNewScanline
+ *
+ * Parameters:
+ *	y  - y coordinate
+ *	x1 - left coordinate
+ *	x2 - right coordinate
+ *
+ * Description:
+ *	Creates a new Scanline
+ */
+XmuScanline *
+XmuNewScanline(int y, int x1, int x2)
+{
+  XmuScanline *scanline;
+
+  scanline = (XmuScanline *)XtMalloc(sizeof(XmuScanline));
+  scanline->y = y;
+  if (x1 < x2)
+    scanline->segment = XmuNewSegment(x1, x2);
+  else
+    scanline->segment = (XmuSegment *)NULL;
+
+  scanline->next = (XmuScanline *)NULL;
+
+  return (scanline);
+}
+
+/*
+ * Function:
+ *	XmuDestroyScanlineList
+ *
+ * Parameters:
+ *	scanline - scanline list to destroy
+ *
+ * Description:
+ *	Destroy a scanline list
+ *
+ * Observation:
+ *	Use as follow:
+ *	XmuDestroyScanlineList(area->scanline);
+ *	area->scanline = (XmuScanline *)NULL;
+ */
+void
+XmuDestroyScanlineList(XmuScanline *scanline)
+{
+  XmuScanline *z;
+
+  if (!scanline)
+    return;
+
+  while (scanline)
+    {
+      z = scanline;
+      scanline = scanline->next;
+      XmuDestroyScanline(z);
+    }
+}
+
+/*
+ * Function:
+ *	XmuOptimizeArea
+ *
+ * Parameters:
+ *	area - area to optimize
+ *
+ * Description:
+ *	  Optimizes an area. This function is called when finishing a
+ *	operation between areas, since they can end with redundant data,
+ *	and the algorithms for area combination waits a area with
+ *	correct data (but can left unnecessary data in the area, to avoid
+ *	to much paranoia tests).
+ */
+XmuArea *XmuOptimizeArea(XmuArea *area)
+{
+  XmuScanline *pr, *at;
+
+  if (!area || !area->scanline)
+    return (area);
+
+  if (!area->scanline->next)
+    {
+      XmuDestroyScanlineList(area->scanline);
+      area->scanline = (XmuScanline *)0;
+      return (area);
+    }
+
+  pr = area->scanline;
+  at = area->scanline->next;
+  while (area->scanline && (!XmuValidScanline(area->scanline)
+			    || (area->scanline->next && area->scanline->y
+				>= area->scanline->next->y)))
+    {
+      area->scanline = area->scanline->next;
+      XmuDestroyScanline(pr);
+      pr = area->scanline;
+      if (pr)
+	at = pr->next;
+    }
+
+  for (; at; pr = at, at = at->next)
+    {
+      if (XmuScanlineEqu(at, pr)
+	  || (!XmuValidScanline(at) && !XmuValidScanline(pr))
+	  || (at->next && at->y >= at->next->y))
+	{
+	  pr->next = at->next;
+	  XmuDestroyScanline(at);
+	  at = pr;
+	}
+    }
+  if (pr && XmuValidScanline(pr))
+    {
+      XmuDestroySegmentList(pr->segment);
+      pr->segment = (XmuSegment *)NULL;
+    }
+  if (area->scanline && !area->scanline->next)
+    {
+      XmuDestroyScanlineList(area->scanline);
+      area->scanline = (XmuScanline *)NULL;
+    }
+
+  return (area);
+}