cairo/src/cairo-path-fixed.c

   1 /* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
   2 /* cairo - a vector graphics library with display and print output
   3  *
   4  * Copyright © 2002 University of Southern California
   5  * Copyright © 2005 Red Hat, Inc.
   6   *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it either under the terms of the GNU Lesser General Public
   9  * License version 2.1 as published by the Free Software Foundation
  10  * (the "LGPL") or, at your option, under the terms of the Mozilla
  11  * Public License Version 1.1 (the "MPL"). If you do not alter this
  12  * notice, a recipient may use your version of this file under either
  13  * the MPL or the LGPL.
  14  *
  15  * You should have received a copy of the LGPL along with this library
  16  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  18  * You should have received a copy of the MPL along with this library
  19  * in the file COPYING-MPL-1.1
  20  *
  21  * The contents of this file are subject to the Mozilla Public License
  22  * Version 1.1 (the "License"); you may not use this file except in
  23  * compliance with the License. You may obtain a copy of the License at
  24  * http://www.mozilla.org/MPL/
  25  *
  26  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  27  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  28  * the specific language governing rights and limitations.
  29  *
  30  * The Original Code is the cairo graphics library.
  31  *
  32  * The Initial Developer of the Original Code is University of Southern
  33  * California.
  34  *
  35  * Contributor(s):
  36  *      Carl D. Worth <cworth@cworth.org>
  37  */
  38
  39 #include "cairoint.h"
  40
  41 #include "cairo-path-fixed-private.h"
  42
  43 /* private functions */
  44 static cairo_status_t
  45 _cairo_path_fixed_add (cairo_path_fixed_t *path,
  46                        cairo_path_op_t     op,
  47                        cairo_point_t      *points,
  48                        int                 num_points);
  49
  50 static void
  51 _cairo_path_fixed_add_buf (cairo_path_fixed_t *path,
  52                            cairo_path_buf_t   *buf);
  53
  54 static cairo_path_buf_t *
  55 _cairo_path_buf_create (int buf_size);
  56
  57 static void
  58 _cairo_path_buf_destroy (cairo_path_buf_t *buf);
  59
  60 static void
  61 _cairo_path_buf_add_op (cairo_path_buf_t *buf,
  62                         cairo_path_op_t   op);
  63
  64 static void
  65 _cairo_path_buf_add_points (cairo_path_buf_t *buf,
  66                             cairo_point_t    *points,
  67                             int               num_points);
  68
  69 void
  70 _cairo_path_fixed_init (cairo_path_fixed_t *path)
  71 {
  72     path->buf_head.base.next = NULL;
  73     path->buf_head.base.prev = NULL;
  74     path->buf_tail = &path->buf_head.base;
  75
  76     path->buf_head.base.num_ops = 0;
  77     path->buf_head.base.num_points = 0;
  78     path->buf_head.base.buf_size = CAIRO_PATH_BUF_SIZE;
  79     path->buf_head.base.op = path->buf_head.op;
  80     path->buf_head.base.points = path->buf_head.points;
  81
  82     path->current_point.x = 0;
  83     path->current_point.y = 0;
  84     path->has_current_point = FALSE;
  85     path->has_curve_to = FALSE;
  86     path->last_move_point = path->current_point;
  87 }
  88
  89 cairo_status_t
  90 _cairo_path_fixed_init_copy (cairo_path_fixed_t *path,
  91                              cairo_path_fixed_t *other)
  92 {
  93     cairo_path_buf_t *buf, *other_buf;
  94     unsigned int num_points, num_ops, buf_size;
  95
  96     _cairo_path_fixed_init (path);
  97
  98     path->current_point = other->current_point;
  99     path->has_current_point = other->has_current_point;
 100     path->has_curve_to = other->has_curve_to;
 101     path->last_move_point = other->last_move_point;
 102
 103     path->buf_head.base.num_ops = other->buf_head.base.num_ops;
 104     path->buf_head.base.num_points = other->buf_head.base.num_points;
 105     path->buf_head.base.buf_size = other->buf_head.base.buf_size;
 106     memcpy (path->buf_head.op, other->buf_head.base.op,
 107             other->buf_head.base.num_ops * sizeof (other->buf_head.op[0]));
 108     memcpy (path->buf_head.points, other->buf_head.points,
 109             other->buf_head.base.num_points * sizeof (other->buf_head.points[0]));
 110
 111     num_points = num_ops = 0;
 112     for (other_buf = other->buf_head.base.next;
 113          other_buf != NULL;
 114          other_buf = other_buf->next)
 115     {
 116         num_ops    += other_buf->num_ops;
 117         num_points += other_buf->num_points;
 118     }
 119
 120     buf_size = MAX (num_ops, (num_points + 1) / 2);
 121     if (buf_size) {
 122         buf = _cairo_path_buf_create (buf_size);
 123         if (buf == NULL) {
 124             _cairo_path_fixed_fini (path);
 125             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 126         }
 127
 128         for (other_buf = other->buf_head.base.next;
 129              other_buf != NULL;
 130              other_buf = other_buf->next)
 131         {
 132             memcpy (buf->op + buf->num_ops, other_buf->op,
 133                     other_buf->num_ops * sizeof (buf->op[0]));
 134             buf->num_ops += other_buf->num_ops;
 135
 136             memcpy (buf->points + buf->num_points, other_buf->points,
 137                     other_buf->num_points * sizeof (buf->points[0]));
 138             buf->num_points += other_buf->num_points;
 139         }
 140
 141         _cairo_path_fixed_add_buf (path, buf);
 142     }
 143
 144     return CAIRO_STATUS_SUCCESS;
 145 }
 146
 147 cairo_path_fixed_t *
 148 _cairo_path_fixed_create (void)
 149 {
 150     cairo_path_fixed_t  *path;
 151
 152     path = malloc (sizeof (cairo_path_fixed_t));
 153     if (!path) {
 154         _cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
 155         return NULL;
 156     }
 157
 158     _cairo_path_fixed_init (path);
 159     return path;
 160 }
 161
 162 void
 163 _cairo_path_fixed_fini (cairo_path_fixed_t *path)
 164 {
 165     cairo_path_buf_t *buf;
 166
 167     buf = path->buf_head.base.next;
 168     while (buf) {
 169         cairo_path_buf_t *this = buf;
 170         buf = buf->next;
 171         _cairo_path_buf_destroy (this);
 172     }
 173     path->buf_head.base.next = NULL;
 174     path->buf_head.base.prev = NULL;
 175     path->buf_tail = &path->buf_head.base;
 176     path->buf_head.base.num_ops = 0;
 177     path->buf_head.base.num_points = 0;
 178
 179     path->has_current_point = FALSE;
 180     path->has_curve_to = FALSE;
 181 }
 182
 183 void
 184 _cairo_path_fixed_destroy (cairo_path_fixed_t *path)
 185 {
 186     _cairo_path_fixed_fini (path);
 187     free (path);
 188 }
 189
 190 cairo_status_t
 191 _cairo_path_fixed_move_to (cairo_path_fixed_t  *path,
 192                            cairo_fixed_t        x,
 193                            cairo_fixed_t        y)
 194 {
 195     cairo_status_t status;
 196     cairo_point_t point;
 197
 198     point.x = x;
 199     point.y = y;
 200
 201     /* If the previous op was also a MOVE_TO, then just change its
 202      * point rather than adding a new op. */
 203     if (path->buf_tail && path->buf_tail->num_ops &&
 204         path->buf_tail->op[path->buf_tail->num_ops - 1] == CAIRO_PATH_OP_MOVE_TO)
 205     {
 206         cairo_point_t *last_move_to_point;
 207         last_move_to_point = &path->buf_tail->points[path->buf_tail->num_points - 1];
 208         *last_move_to_point = point;
 209     } else {
 210         status = _cairo_path_fixed_add (path, CAIRO_PATH_OP_MOVE_TO, &point, 1);
 211         if (status)
 212             return status;
 213     }
 214
 215     path->current_point = point;
 216     path->has_current_point = TRUE;
 217     path->last_move_point = path->current_point;
 218
 219     return CAIRO_STATUS_SUCCESS;
 220 }
 221
 222 void
 223 _cairo_path_fixed_new_sub_path (cairo_path_fixed_t *path)
 224 {
 225     path->has_current_point = FALSE;
 226 }
 227
 228 cairo_status_t
 229 _cairo_path_fixed_rel_move_to (cairo_path_fixed_t *path,
 230                                cairo_fixed_t       dx,
 231                                cairo_fixed_t       dy)
 232 {
 233     cairo_fixed_t x, y;
 234
 235     if (! path->has_current_point)
 236         return _cairo_error (CAIRO_STATUS_NO_CURRENT_POINT);
 237
 238     x = path->current_point.x + dx;
 239     y = path->current_point.y + dy;
 240
 241     return _cairo_path_fixed_move_to (path, x, y);
 242 }
 243
 244 cairo_status_t
 245 _cairo_path_fixed_line_to (cairo_path_fixed_t *path,
 246                            cairo_fixed_t        x,
 247                            cairo_fixed_t        y)
 248 {
 249     cairo_status_t status;
 250     cairo_point_t point;
 251
 252     point.x = x;
 253     point.y = y;
 254
 255     /* When there is not yet a current point, the line_to operation
 256      * becomes a move_to instead. Note: We have to do this by
 257      * explicitly calling into _cairo_path_fixed_line_to to ensure
 258      * that the last_move_point state is updated properly.
 259      */
 260     if (! path->has_current_point)
 261         status = _cairo_path_fixed_move_to (path, point.x, point.y);
 262     else
 263         status = _cairo_path_fixed_add (path, CAIRO_PATH_OP_LINE_TO, &point, 1);
 264
 265     if (status)
 266         return status;
 267
 268     path->current_point = point;
 269     path->has_current_point = TRUE;
 270
 271     return CAIRO_STATUS_SUCCESS;
 272 }
 273
 274 cairo_status_t
 275 _cairo_path_fixed_rel_line_to (cairo_path_fixed_t *path,
 276                                cairo_fixed_t       dx,
 277                                cairo_fixed_t       dy)
 278 {
 279     cairo_fixed_t x, y;
 280
 281     if (! path->has_current_point)
 282         return _cairo_error (CAIRO_STATUS_NO_CURRENT_POINT);
 283
 284     x = path->current_point.x + dx;
 285     y = path->current_point.y + dy;
 286
 287     return _cairo_path_fixed_line_to (path, x, y);
 288 }
 289
 290 cairo_status_t
 291 _cairo_path_fixed_curve_to (cairo_path_fixed_t  *path,
 292                             cairo_fixed_t x0, cairo_fixed_t y0,
 293                             cairo_fixed_t x1, cairo_fixed_t y1,
 294                             cairo_fixed_t x2, cairo_fixed_t y2)
 295 {
 296     cairo_status_t status;
 297     cairo_point_t point[3];
 298
 299     point[0].x = x0; point[0].y = y0;
 300     point[1].x = x1; point[1].y = y1;
 301     point[2].x = x2; point[2].y = y2;
 302
 303     if (! path->has_current_point) {
 304         status = _cairo_path_fixed_add (path, CAIRO_PATH_OP_MOVE_TO,
 305                                         &point[0], 1);
 306         if (status)
 307             return status;
 308     }
 309
 310     status = _cairo_path_fixed_add (path, CAIRO_PATH_OP_CURVE_TO, point, 3);
 311     if (status)
 312         return status;
 313
 314     path->current_point = point[2];
 315     path->has_current_point = TRUE;
 316     path->has_curve_to = TRUE;
 317
 318     return CAIRO_STATUS_SUCCESS;
 319 }
 320
 321 cairo_status_t
 322 _cairo_path_fixed_rel_curve_to (cairo_path_fixed_t *path,
 323                                 cairo_fixed_t dx0, cairo_fixed_t dy0,
 324                                 cairo_fixed_t dx1, cairo_fixed_t dy1,
 325                                 cairo_fixed_t dx2, cairo_fixed_t dy2)
 326 {
 327     cairo_fixed_t x0, y0;
 328     cairo_fixed_t x1, y1;
 329     cairo_fixed_t x2, y2;
 330
 331     if (! path->has_current_point)
 332         return _cairo_error (CAIRO_STATUS_NO_CURRENT_POINT);
 333
 334     x0 = path->current_point.x + dx0;
 335     y0 = path->current_point.y + dy0;
 336
 337     x1 = path->current_point.x + dx1;
 338     y1 = path->current_point.y + dy1;
 339
 340     x2 = path->current_point.x + dx2;
 341     y2 = path->current_point.y + dy2;
 342
 343     return _cairo_path_fixed_curve_to (path,
 344                                        x0, y0,
 345                                        x1, y1,
 346                                        x2, y2);
 347 }
 348
 349 cairo_status_t
 350 _cairo_path_fixed_close_path (cairo_path_fixed_t *path)
 351 {
 352     cairo_status_t status;
 353
 354     if (! path->has_current_point)
 355         return CAIRO_STATUS_SUCCESS;
 356
 357     status = _cairo_path_fixed_add (path, CAIRO_PATH_OP_CLOSE_PATH, NULL, 0);
 358     if (status)
 359         return status;
 360
 361     status = _cairo_path_fixed_move_to (path,
 362                                         path->last_move_point.x,
 363                                         path->last_move_point.y);
 364     if (status)
 365         return status;
 366
 367     return CAIRO_STATUS_SUCCESS;
 368 }
 369
 370 cairo_bool_t
 371 _cairo_path_fixed_get_current_point (cairo_path_fixed_t *path,
 372                                      cairo_fixed_t      *x,
 373                                      cairo_fixed_t      *y)
 374 {
 375     if (! path->has_current_point)
 376         return FALSE;
 377
 378     *x = path->current_point.x;
 379     *y = path->current_point.y;
 380
 381     return TRUE;
 382 }
 383
 384 static cairo_status_t
 385 _cairo_path_fixed_add (cairo_path_fixed_t *path,
 386                        cairo_path_op_t     op,
 387                        cairo_point_t      *points,
 388                        int                 num_points)
 389 {
 390     cairo_path_buf_t *buf = path->buf_tail;
 391
 392     if (buf->num_ops + 1 > buf->buf_size ||
 393         buf->num_points + num_points > 2 * buf->buf_size)
 394     {
 395         buf = _cairo_path_buf_create (buf->buf_size * 2);
 396         if (buf == NULL)
 397             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 398
 399         _cairo_path_fixed_add_buf (path, buf);
 400     }
 401
 402     _cairo_path_buf_add_op (buf, op);
 403     _cairo_path_buf_add_points (buf, points, num_points);
 404
 405     return CAIRO_STATUS_SUCCESS;
 406 }
 407
 408 static void
 409 _cairo_path_fixed_add_buf (cairo_path_fixed_t *path,
 410                            cairo_path_buf_t   *buf)
 411 {
 412     buf->next = NULL;
 413     buf->prev = path->buf_tail;
 414
 415     path->buf_tail->next = buf;
 416     path->buf_tail = buf;
 417 }
 418
 419 static cairo_path_buf_t *
 420 _cairo_path_buf_create (int buf_size)
 421 {
 422     cairo_path_buf_t *buf;
 423
 424     /* adjust buf_size to ensure that buf->points is naturally aligned */
 425     buf_size += sizeof (double)
 426                - ((buf_size + sizeof (cairo_path_buf_t)) & (sizeof (double)-1));
 427     buf = _cairo_malloc_ab_plus_c (buf_size,
 428                                    sizeof (cairo_path_op_t) +
 429                                    2 * sizeof (cairo_point_t),
 430                                    sizeof (cairo_path_buf_t));
 431     if (buf) {
 432         buf->next = NULL;
 433         buf->prev = NULL;
 434         buf->num_ops = 0;
 435         buf->num_points = 0;
 436         buf->buf_size = buf_size;
 437
 438         buf->op = (cairo_path_op_t *) (buf + 1);
 439         buf->points = (cairo_point_t *) (buf->op + buf_size);
 440     }
 441
 442     return buf;
 443 }
 444
 445 static void
 446 _cairo_path_buf_destroy (cairo_path_buf_t *buf)
 447 {
 448     free (buf);
 449 }
 450
 451 static void
 452 _cairo_path_buf_add_op (cairo_path_buf_t *buf,
 453                         cairo_path_op_t   op)
 454 {
 455     buf->op[buf->num_ops++] = op;
 456 }
 457
 458 static void
 459 _cairo_path_buf_add_points (cairo_path_buf_t *buf,
 460                             cairo_point_t    *points,
 461                             int               num_points)
 462 {
 463     int i;
 464
 465     for (i=0; i < num_points; i++) {
 466         buf->points[buf->num_points++] = points[i];
 467     }
 468 }
 469
 470 static int const num_args[] =
 471 {
 472     1, /* cairo_path_move_to */
 473     1, /* cairo_path_op_line_to */
 474     3, /* cairo_path_op_curve_to */
 475     0, /* cairo_path_op_close_path */
 476 };
 477
 478 cairo_status_t
 479 _cairo_path_fixed_interpret (const cairo_path_fixed_t           *path,
 480                              cairo_direction_t                   dir,
 481                              cairo_path_fixed_move_to_func_t    *move_to,
 482                              cairo_path_fixed_line_to_func_t    *line_to,
 483                              cairo_path_fixed_curve_to_func_t   *curve_to,
 484                              cairo_path_fixed_close_path_func_t *close_path,
 485                              void                               *closure)
 486 {
 487     cairo_status_t status;
 488     const cairo_path_buf_t *buf;
 489     cairo_path_op_t op;
 490     cairo_bool_t forward = (dir == CAIRO_DIRECTION_FORWARD);
 491     int step = forward ? 1 : -1;
 492
 493     for (buf = forward ? &path->buf_head.base : path->buf_tail;
 494          buf;
 495          buf = forward ? buf->next : buf->prev)
 496     {
 497         cairo_point_t *points;
 498         int start, stop, i;
 499         if (forward) {
 500             start = 0;
 501             stop = buf->num_ops;
 502             points = buf->points;
 503         } else {
 504             start = buf->num_ops - 1;
 505             stop = -1;
 506             points = buf->points + buf->num_points;
 507         }
 508
 509         for (i=start; i != stop; i += step) {
 510             op = buf->op[i];
 511
 512             if (! forward) {
 513                 points -= num_args[(int) op];
 514             }
 515
 516             switch (op) {
 517             case CAIRO_PATH_OP_MOVE_TO:
 518                 status = (*move_to) (closure, &points[0]);
 519                 break;
 520             case CAIRO_PATH_OP_LINE_TO:
 521                 status = (*line_to) (closure, &points[0]);
 522                 break;
 523             case CAIRO_PATH_OP_CURVE_TO:
 524                 status = (*curve_to) (closure, &points[0], &points[1], &points[2]);
 525                 break;
 526             case CAIRO_PATH_OP_CLOSE_PATH:
 527             default:
 528                 status = (*close_path) (closure);
 529                 break;
 530             }
 531             if (status)
 532                 return status;
 533
 534             if (forward) {
 535                 points += num_args[(int) op];
 536             }
 537
 538         }
 539     }
 540
 541     return CAIRO_STATUS_SUCCESS;
 542 }
 543
 544 static cairo_status_t
 545 _append_move_to (void            *closure,
 546           cairo_point_t  *point)
 547 {
 548     cairo_path_fixed_t *path = (cairo_path_fixed_t *) closure;
 549     return _cairo_path_fixed_move_to (path, point->x, point->y);
 550 }
 551
 552 static cairo_status_t
 553 _append_line_to (void            *closure,
 554           cairo_point_t *point)
 555 {
 556     cairo_path_fixed_t *path = (cairo_path_fixed_t *) closure;
 557     return _cairo_path_fixed_line_to (path, point->x, point->y);
 558 }
 559
 560 static cairo_status_t
 561 _append_curve_to (void    *closure,
 562            cairo_point_t *p0,
 563            cairo_point_t *p1,
 564            cairo_point_t *p2)
 565 {
 566     cairo_path_fixed_t *path = (cairo_path_fixed_t *) closure;
 567     return _cairo_path_fixed_curve_to (path, p0->x, p0->y, p1->x, p1->y, p2->x, p2->y);
 568 }
 569
 570 static cairo_status_t
 571 _append_close_path (void *closure)
 572 {
 573     cairo_path_fixed_t *path = (cairo_path_fixed_t *) closure;
 574     return _cairo_path_fixed_close_path (path);
 575 }
 576
 577 cairo_private cairo_status_t
 578 _cairo_path_fixed_append (cairo_path_fixed_t              *path,
 579                           const cairo_path_fixed_t        *other,
 580                           cairo_direction_t                dir)
 581 {
 582     return _cairo_path_fixed_interpret (other, dir,
 583                                         _append_move_to,
 584                                         _append_line_to,
 585                                         _append_curve_to,
 586                                         _append_close_path,
 587                                         path);
 588 }
 589
 590 static void
 591 _cairo_path_fixed_offset_and_scale (cairo_path_fixed_t *path,
 592                                     cairo_fixed_t offx,
 593                                     cairo_fixed_t offy,
 594                                     cairo_fixed_t scalex,
 595                                     cairo_fixed_t scaley)
 596 {
 597     cairo_path_buf_t *buf = &path->buf_head.base;
 598     int i;
 599
 600     while (buf) {
 601          for (i = 0; i < buf->num_points; i++) {
 602              if (scalex != CAIRO_FIXED_ONE)
 603                  buf->points[i].x = _cairo_fixed_mul (buf->points[i].x, scalex);
 604              buf->points[i].x += offx;
 605
 606              if (scaley != CAIRO_FIXED_ONE)
 607                  buf->points[i].y = _cairo_fixed_mul (buf->points[i].y, scaley);
 608              buf->points[i].y += offy;
 609          }
 610
 611          buf = buf->next;
 612     }
 613 }
 614
 615 /**
 616  * _cairo_path_fixed_transform:
 617  * @path: a #cairo_path_fixed_t to be transformed
 618  * @matrix: a #cairo_matrix_t
 619  *
 620  * Transform the fixed-point path according to the given matrix.
 621  * There is a fast path for the case where @matrix has no rotation
 622  * or shear.
 623  **/
 624 void
 625 _cairo_path_fixed_transform (cairo_path_fixed_t *path,
 626                              cairo_matrix_t     *matrix)
 627 {
 628     cairo_path_buf_t *buf;
 629     int i;
 630     double dx, dy;
 631
 632     if (matrix->yx == 0.0 && matrix->xy == 0.0) {
 633         /* Fast path for the common case of scale+transform */
 634         _cairo_path_fixed_offset_and_scale (path,
 635                                             _cairo_fixed_from_double (matrix->x0),
 636                                             _cairo_fixed_from_double (matrix->y0),
 637                                             _cairo_fixed_from_double (matrix->xx),
 638                                             _cairo_fixed_from_double (matrix->yy));
 639         return;
 640     }
 641
 642     buf = &path->buf_head.base;
 643     while (buf) {
 644          for (i = 0; i < buf->num_points; i++) {
 645             dx = _cairo_fixed_to_double (buf->points[i].x);
 646             dy = _cairo_fixed_to_double (buf->points[i].y);
 647
 648             cairo_matrix_transform_point (matrix, &dx, &dy);
 649
 650             buf->points[i].x = _cairo_fixed_from_double (dx);
 651             buf->points[i].y = _cairo_fixed_from_double (dy);
 652          }
 653
 654          buf = buf->next;
 655     }
 656 }
 657
 658 cairo_bool_t
 659 _cairo_path_fixed_is_equal (cairo_path_fixed_t *path,
 660                             cairo_path_fixed_t *other)
 661 {
 662     cairo_path_buf_t *path_buf, *other_buf;
 663
 664     if (path->current_point.x != other->current_point.x ||
 665         path->current_point.y != other->current_point.y ||
 666         path->has_current_point != other->has_current_point ||
 667         path->has_curve_to != other->has_curve_to ||
 668         path->last_move_point.x != other->last_move_point.x ||
 669         path->last_move_point.y != other->last_move_point.y)
 670         return FALSE;
 671
 672     other_buf = &other->buf_head.base;
 673     for (path_buf = &path->buf_head.base;
 674          path_buf != NULL;
 675          path_buf = path_buf->next)
 676     {
 677         if (other_buf == NULL ||
 678             path_buf->num_ops != other_buf->num_ops ||
 679             path_buf->num_points != other_buf->num_points ||
 680             memcmp (path_buf->op, other_buf->op,
 681                     sizeof (cairo_path_op_t) * path_buf->num_ops) != 0 ||
 682             memcmp (path_buf->points, other_buf->points,
 683                     sizeof (cairo_point_t) * path_buf->num_points) != 0)
 684         {
 685             return FALSE;
 686         }
 687         other_buf = other_buf->next;
 688     }
 689     return TRUE;
 690 }
 691
 692 /* Closure for path flattening */
 693 typedef struct cairo_path_flattener {
 694     double tolerance;
 695     cairo_point_t current_point;
 696     cairo_path_fixed_move_to_func_t     *move_to;
 697     cairo_path_fixed_line_to_func_t     *line_to;
 698     cairo_path_fixed_close_path_func_t  *close_path;
 699     void *closure;
 700 } cpf_t;
 701
 702 static cairo_status_t
 703 _cpf_move_to (void *closure, cairo_point_t *point)
 704 {
 705     cpf_t *cpf = closure;
 706
 707     cpf->current_point = *point;
 708
 709     return cpf->move_to (cpf->closure, point);
 710 }
 711
 712 static cairo_status_t
 713 _cpf_line_to (void *closure, cairo_point_t *point)
 714 {
 715     cpf_t *cpf = closure;
 716
 717     cpf->current_point = *point;
 718
 719     return cpf->line_to (cpf->closure, point);
 720 }
 721
 722 static cairo_status_t
 723 _cpf_curve_to (void             *closure,
 724                cairo_point_t    *p1,
 725                cairo_point_t    *p2,
 726                cairo_point_t    *p3)
 727 {
 728     cpf_t *cpf = closure;
 729     cairo_status_t status;
 730     cairo_spline_t spline;
 731     int i;
 732
 733     cairo_point_t *p0 = &cpf->current_point;
 734
 735     status = _cairo_spline_init (&spline, p0, p1, p2, p3);
 736     if (status == CAIRO_INT_STATUS_DEGENERATE)
 737         return CAIRO_STATUS_SUCCESS;
 738
 739     status = _cairo_spline_decompose (&spline, cpf->tolerance);
 740     if (status)
 741       goto out;
 742
 743     for (i=1; i < spline.num_points; i++) {
 744         status = cpf->line_to (cpf->closure, &spline.points[i]);
 745         if (status)
 746             goto out;
 747     }
 748
 749     cpf->current_point = *p3;
 750
 751     status = CAIRO_STATUS_SUCCESS;
 752
 753  out:
 754     _cairo_spline_fini (&spline);
 755     return status;
 756 }
 757
 758 static cairo_status_t
 759 _cpf_close_path (void *closure)
 760 {
 761     cpf_t *cpf = closure;
 762
 763     return cpf->close_path (cpf->closure);
 764 }
 765
 766
 767 cairo_status_t
 768 _cairo_path_fixed_interpret_flat (const cairo_path_fixed_t              *path,
 769                                   cairo_direction_t                     dir,
 770                                   cairo_path_fixed_move_to_func_t       *move_to,
 771                                   cairo_path_fixed_line_to_func_t       *line_to,
 772                                   cairo_path_fixed_close_path_func_t    *close_path,
 773                                   void                                  *closure,
 774                                   double                                tolerance)
 775 {
 776     cpf_t flattener;
 777
 778     flattener.tolerance = tolerance;
 779     flattener.move_to = move_to;
 780     flattener.line_to = line_to;
 781     flattener.close_path = close_path;
 782     flattener.closure = closure;
 783     return _cairo_path_fixed_interpret (path, dir,
 784                                         _cpf_move_to,
 785                                         _cpf_line_to,
 786                                         _cpf_curve_to,
 787                                         _cpf_close_path,
 788                                         &flattener);
 789 }
 790
 791 cairo_bool_t
 792 _cairo_path_fixed_is_empty (cairo_path_fixed_t *path)
 793 {
 794     if (path->buf_head.base.num_ops == 0)
 795         return TRUE;
 796
 797     return FALSE;
 798 }
 799
 800 /**
 801  * Check whether the given path contains a single rectangle.
 802  */
 803 cairo_bool_t
 804 _cairo_path_fixed_is_box (cairo_path_fixed_t *path,
 805                           cairo_box_t *box)
 806 {
 807     cairo_path_buf_t *buf = &path->buf_head.base;
 808
 809     /* We can't have more than one buf for this check */
 810     if (buf->next != NULL)
 811         return FALSE;
 812
 813     /* Do we have the right number of ops? */
 814     if (buf->num_ops != 5 && buf->num_ops != 6)
 815         return FALSE;
 816
 817     /* Check whether the ops are those that would be used for a rectangle */
 818     if (buf->op[0] != CAIRO_PATH_OP_MOVE_TO ||
 819         buf->op[1] != CAIRO_PATH_OP_LINE_TO ||
 820         buf->op[2] != CAIRO_PATH_OP_LINE_TO ||
 821         buf->op[3] != CAIRO_PATH_OP_LINE_TO)
 822     {
 823         return FALSE;
 824     }
 825
 826     /* Now, there are choices. The rectangle might end with a LINE_TO
 827      * (to the original point), but this isn't required. If it
 828      * doesn't, then it must end with a CLOSE_PATH. */
 829     if (buf->op[4] == CAIRO_PATH_OP_LINE_TO) {
 830         if (buf->points[4].x != buf->points[0].x ||
 831             buf->points[4].y != buf->points[0].y)
 832             return FALSE;
 833     } else if (buf->op[4] != CAIRO_PATH_OP_CLOSE_PATH) {
 834         return FALSE;
 835     }
 836
 837     if (buf->num_ops == 6) {
 838         /* A trailing CLOSE_PATH or MOVE_TO is ok */
 839         if (buf->op[5] != CAIRO_PATH_OP_MOVE_TO &&
 840             buf->op[5] != CAIRO_PATH_OP_CLOSE_PATH)
 841             return FALSE;
 842     }
 843
 844     /* Ok, we may have a box, if the points line up */
 845     if (buf->points[0].y == buf->points[1].y &&
 846         buf->points[1].x == buf->points[2].x &&
 847         buf->points[2].y == buf->points[3].y &&
 848         buf->points[3].x == buf->points[0].x)
 849     {
 850         if (box) {
 851             box->p1 = buf->points[0];
 852             box->p2 = buf->points[2];
 853         }
 854         return TRUE;
 855     }
 856
 857     if (buf->points[0].x == buf->points[1].x &&
 858         buf->points[1].y == buf->points[2].y &&
 859         buf->points[2].x == buf->points[3].x &&
 860         buf->points[3].y == buf->points[0].y)
 861     {
 862         if (box) {
 863             box->p1 = buf->points[0];
 864             box->p2 = buf->points[2];
 865         }
 866         return TRUE;
 867     }
 868
 869     return FALSE;
 870 }
 871
 872 /*
 873  * Check whether the given path contains a single rectangle
 874  * that is logically equivalent to:
 875  * <informalexample><programlisting>
 876  *   cairo_move_to (cr, x, y);
 877  *   cairo_rel_line_to (cr, width, 0);
 878  *   cairo_rel_line_to (cr, 0, height);
 879  *   cairo_rel_line_to (cr, -width, 0);
 880  *   cairo_close_path (cr);
 881  * </programlisting></informalexample>
 882  */
 883 cairo_bool_t
 884 _cairo_path_fixed_is_rectangle (cairo_path_fixed_t *path,
 885                                 cairo_box_t        *box)
 886 {
 887     cairo_path_buf_t *buf = &path->buf_head.base;
 888
 889     if (!_cairo_path_fixed_is_box (path, box))
 890         return FALSE;
 891
 892     if (buf->points[0].y == buf->points[1].y)
 893         return TRUE;
 894
 895     return FALSE;
 896 }