diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/Makefile.am | 5 | ||||
| -rw-r--r-- | src/Makefile.sources | 2 | ||||
| -rw-r--r-- | src/cairo-bentley-ottmann.c | 341 | ||||
| -rw-r--r-- | src/cairo-freelist.c | 8 | ||||
| -rw-r--r-- | src/cairo-skiplist-private.h | 118 | ||||
| -rw-r--r-- | src/cairo-skiplist.c | 399 |
6 files changed, 212 insertions, 661 deletions
diff --git a/src/Makefile.am b/src/Makefile.am index e461fbde..dce2a08e 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -84,12 +84,9 @@ TESTS += check-link$(EXEEXT) endif EXTRA_DIST += $(TESTS_SH) check-has-hidden-symbols.c -check_PROGRAMS += check-link check-skiplist +check_PROGRAMS += check-link check_link_LDADD = libcairo.la -check_skiplist_SOURCES = cairo-skiplist.c -check_skiplist_CPPFLAGS = -DMAIN $(AM_CPPFLAGS) - check: headers-standalone PREPROCESS_ARGS = $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) diff --git a/src/Makefile.sources b/src/Makefile.sources index ca8d51df..b8404e3d 100644 --- a/src/Makefile.sources +++ b/src/Makefile.sources @@ -82,7 +82,6 @@ cairo_private = \ cairo-region-private.h \ cairo-rtree-private.h \ cairo-scaled-font-private.h \ - cairo-skiplist-private.h \ cairo-spans-private.h \ cairo-surface-fallback-private.h \ cairo-surface-private.h \ @@ -136,7 +135,6 @@ cairo_sources = \ cairo-region.c \ cairo-rtree.c \ cairo-scaled-font.c \ - cairo-skiplist.c \ cairo-slope.c \ cairo-spans.c \ cairo-spline.c \ diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c index 66d1a19c..3d3a3d60 100644 --- a/src/cairo-bentley-ottmann.c +++ b/src/cairo-bentley-ottmann.c @@ -38,7 +38,6 @@ /* Provide definitions for standalone compilation */ #include "cairoint.h" -#include "cairo-skiplist-private.h" #include "cairo-freelist-private.h" #include "cairo-combsort-private.h" @@ -59,7 +58,6 @@ typedef struct _cairo_bo_intersect_point { } cairo_bo_intersect_point_t; typedef struct _cairo_bo_edge cairo_bo_edge_t; -typedef struct _sweep_line_elt sweep_line_elt_t; typedef struct _cairo_bo_trap cairo_bo_trap_t; /* A deferred trapezoid of an edge */ @@ -73,16 +71,14 @@ struct _cairo_bo_edge { cairo_bo_edge_t *prev; cairo_bo_edge_t *next; cairo_bo_trap_t deferred_trap; - sweep_line_elt_t *sweep_line_elt; }; -struct _sweep_line_elt { - cairo_bo_edge_t *edge; - skip_elt_t elt; -}; +/* the parent is always given by index/2 */ +#define PQ_PARENT_INDEX(i) ((i) >> 1) +#define PQ_FIRST_ENTRY 1 -#define SKIP_ELT_TO_EDGE_ELT(elt) SKIP_LIST_ELT_TO_DATA (sweep_line_elt_t, (elt)) -#define SKIP_ELT_TO_EDGE(elt) (SKIP_ELT_TO_EDGE_ELT (elt)->edge) +/* left and right children are index * 2 and (index * 2) +1 respectively */ +#define PQ_LEFT_CHILD_INDEX(i) ((i) << 1) typedef enum { CAIRO_BO_EVENT_TYPE_STOP, @@ -101,23 +97,26 @@ typedef struct _cairo_bo_start_event { cairo_bo_edge_t edge; } cairo_bo_start_event_t; -typedef struct _cairo_bo_skiplist_event { +typedef struct _cairo_bo_queue_event { cairo_bo_event_type_t type; cairo_point_t point; cairo_bo_edge_t *e1; cairo_bo_edge_t *e2; - skip_elt_t elt; -} cairo_bo_skiplist_event_t; +} cairo_bo_queue_event_t; -#define SKIP_ELT_TO_EVENT(elt) ((cairo_bo_event_t *) SKIP_LIST_ELT_TO_DATA (cairo_bo_skiplist_event_t, (elt))) +typedef struct _pqueue { + int size, max_size; -typedef struct _cairo_bo_event_queue { - cairo_skip_list_t event_queue; + cairo_bo_event_t **elements; + cairo_bo_event_t *elements_embedded[1024]; +} pqueue_t; +typedef struct _cairo_bo_event_queue { + cairo_freepool_t pool; + pqueue_t pqueue; cairo_bo_event_t **start_events; } cairo_bo_event_queue_t; -/* This structure extends #cairo_skip_list_t, which must come first. */ typedef struct _cairo_bo_sweep_line { cairo_bo_edge_t *head; cairo_bo_edge_t *stopped; @@ -599,44 +598,10 @@ _cairo_bo_sweep_line_compare_edges (cairo_bo_sweep_line_t *sweep_line, cmp = _slope_compare (a, b); if (cmp) return cmp; - - /* We've got two collinear edges now. */ - - /* Since we're dealing with start events, prefer comparing top - * edges before bottom edges. */ - cmp = a->edge.top - b->edge.top; - if (cmp) - return cmp; - - cmp = a->edge.bottom - b->edge.bottom; - if (cmp) - return cmp; } - return 0; -} - -static inline int -cairo_bo_event_compare (const cairo_bo_event_t *a, - const cairo_bo_event_t *b) -{ - int cmp; - - cmp = _cairo_bo_point32_compare (&a->point, &b->point); - if (cmp) - return cmp; - - cmp = a->type - b->type; - if (cmp) - return cmp; - - return a - b; -} - -static int -cairo_bo_event_compare_skiplist (void *list, const void *a, const void *b) -{ - return cairo_bo_event_compare (a, b); + /* We've got two collinear edges now. */ + return b->edge.bottom - a->edge.bottom; } static inline cairo_int64_t @@ -687,8 +652,6 @@ intersect_lines (cairo_bo_edge_t *a, cairo_quorem64_t qr; den_det = det32_64 (dx1, dy1, dx2, dy2); - if (_cairo_int64_is_zero (den_det)) - return FALSE; /* Q: Can we determine that the lines do not intersect (within range) * much more cheaply than computing the intersection point i.e. by @@ -712,10 +675,6 @@ intersect_lines (cairo_bo_edge_t *a, R = det32_64 (dx2, dy2, b->edge.line.p1.x - a->edge.line.p1.x, b->edge.line.p1.y - a->edge.line.p1.y); - if (_cairo_int64_is_zero (R)) - return FALSE; - if (_cairo_int64_negative (den_det) ^ _cairo_int64_negative (R)) - return FALSE; if (_cairo_int64_negative (den_det)) { if (_cairo_int64_ge (den_det, R)) return FALSE; @@ -727,10 +686,6 @@ intersect_lines (cairo_bo_edge_t *a, R = det32_64 (dy1, dx1, a->edge.line.p1.y - b->edge.line.p1.y, a->edge.line.p1.x - b->edge.line.p1.x); - if (_cairo_int64_is_zero (R)) - return FALSE; - if (_cairo_int64_negative (den_det) ^ _cairo_int64_negative (R)) - return FALSE; if (_cairo_int64_negative (den_det)) { if (_cairo_int64_ge (den_det, R)) return FALSE; @@ -923,49 +878,161 @@ _cairo_bo_edge_intersect (cairo_bo_edge_t *a, return TRUE; } -static void -_cairo_bo_skiplist_event_init (cairo_bo_skiplist_event_t *event, - cairo_bo_event_type_t type, - cairo_bo_edge_t *e1, - cairo_bo_edge_t *e2, - const cairo_point_t *point) +static inline int +cairo_bo_event_compare (const cairo_bo_event_t *a, + const cairo_bo_event_t *b) { - event->type = type; - event->e1 = e1; - event->e2 = e2; - event->point = *point; + int cmp; + + cmp = _cairo_bo_point32_compare (&a->point, &b->point); + if (cmp) + return cmp; + + cmp = a->type - b->type; + if (cmp) + return cmp; + + return a - b; +} + +static inline void +_pqueue_init (pqueue_t *pq) +{ + pq->max_size = ARRAY_LENGTH (pq->elements_embedded); + pq->size = 0; + + pq->elements = pq->elements_embedded; +} + +static inline void +_pqueue_fini (pqueue_t *pq) +{ + if (pq->elements != pq->elements_embedded) + free (pq->elements); } static cairo_status_t -_cairo_bo_event_queue_insert (cairo_bo_event_queue_t *queue, - cairo_bo_skiplist_event_t *event) +_pqueue_grow (pqueue_t *pq) { - cairo_status_t status = CAIRO_STATUS_SUCCESS; + cairo_bo_event_t **new_elements; + pq->max_size *= 2; - /* Only insert if there is no prior identical intersection event. */ - if (unlikely (_cairo_skip_list_insert (&queue->event_queue, event) == NULL)) - status = _cairo_error (CAIRO_STATUS_NO_MEMORY); + if (pq->elements == pq->elements_embedded) { + new_elements = _cairo_malloc_ab (pq->max_size, + sizeof (cairo_bo_event_t *)); + if (unlikely (new_elements == NULL)) + return _cairo_error (CAIRO_STATUS_NO_MEMORY); - return status; + memcpy (new_elements, pq->elements_embedded, + sizeof (pq->elements_embedded)); + } else { + new_elements = _cairo_realloc_ab (pq->elements, + pq->max_size, + sizeof (cairo_bo_event_t *)); + if (unlikely (new_elements == NULL)) + return _cairo_error (CAIRO_STATUS_NO_MEMORY); + } + + pq->elements = new_elements; + return CAIRO_STATUS_SUCCESS; +} + +static inline cairo_status_t +_pqueue_push (pqueue_t *pq, cairo_bo_event_t *event) +{ + cairo_bo_event_t **elements; + int i, parent; + + if (unlikely (pq->size + 1 == pq->max_size)) { + cairo_status_t status; + + status = _pqueue_grow (pq); + if (unlikely (status)) + return status; + } + + elements = pq->elements; + + for (i = ++pq->size; + i != PQ_FIRST_ENTRY && + cairo_bo_event_compare (event, + elements[parent = PQ_PARENT_INDEX (i)]) < 0; + i = parent) + { + elements[i] = elements[parent]; + } + + elements[i] = event; + + return CAIRO_STATUS_SUCCESS; +} + +static inline void +_pqueue_pop (pqueue_t *pq) +{ + cairo_bo_event_t **elements = pq->elements; + cairo_bo_event_t *tail; + int child, i; + + tail = elements[pq->size--]; + if (pq->size == 0) { + elements[PQ_FIRST_ENTRY] = NULL; + return; + } + + for (i = PQ_FIRST_ENTRY; + (child = PQ_LEFT_CHILD_INDEX (i)) <= pq->size; + i = child) + { + if (child != pq->size && + cairo_bo_event_compare (elements[child+1], + elements[child]) < 0) + { + child++; + } + + if (cairo_bo_event_compare (elements[child], tail) >= 0) + break; + + elements[i] = elements[child]; + } + elements[i] = tail; +} + +static inline cairo_status_t +_cairo_bo_event_queue_insert (cairo_bo_event_queue_t *queue, + cairo_bo_event_type_t type, + cairo_bo_edge_t *e1, + cairo_bo_edge_t *e2, + const cairo_point_t *point) +{ + cairo_bo_queue_event_t *event; + + event = _cairo_freepool_alloc (&queue->pool); + if (unlikely (event == NULL)) + return _cairo_error (CAIRO_STATUS_NO_MEMORY); + + event->type = type; + event->e1 = e1; + event->e2 = e2; + event->point = *point; + + return _pqueue_push (&queue->pqueue, (cairo_bo_event_t *) event); } static void _cairo_bo_event_queue_delete (cairo_bo_event_queue_t *queue, cairo_bo_event_t *event) { - _cairo_skip_list_delete_given (&queue->event_queue, - &((cairo_bo_skiplist_event_t *) event)->elt); + _cairo_freepool_free (&queue->pool, event); } -#define NEXT_EVENT(Q) \ - ((Q)->chains[0] ? SKIP_ELT_TO_EVENT ((Q)->chains[0]) : NULL) static cairo_bo_event_t * _cairo_bo_event_dequeue (cairo_bo_event_queue_t *event_queue) { cairo_bo_event_t *event, *cmp; - event = NEXT_EVENT (&event_queue->event_queue); - + event = event_queue->pqueue.elements[PQ_FIRST_ENTRY]; cmp = *event_queue->start_events; if (event == NULL || (cmp != NULL && cairo_bo_event_compare (cmp, event) < 0)) @@ -973,6 +1040,10 @@ _cairo_bo_event_dequeue (cairo_bo_event_queue_t *event_queue) event = cmp; event_queue->start_events++; } + else + { + _pqueue_pop (&event_queue->pqueue); + } return event; } @@ -991,9 +1062,10 @@ _cairo_bo_event_queue_init (cairo_bo_event_queue_t *event_queue, event_queue->start_events = start_events; - _cairo_skip_list_init (&event_queue->event_queue, - cairo_bo_event_compare_skiplist, - sizeof (cairo_bo_skiplist_event_t)); + _cairo_freepool_init (&event_queue->pool, + sizeof (cairo_bo_queue_event_t)); + _pqueue_init (&event_queue->pqueue); + event_queue->pqueue.elements[PQ_FIRST_ENTRY] = NULL; } static cairo_status_t @@ -1001,23 +1073,21 @@ _cairo_bo_event_queue_insert_stop (cairo_bo_event_queue_t *event_queue, cairo_bo_edge_t *edge) { cairo_bo_point32_t point; - cairo_bo_skiplist_event_t event; point.y = edge->edge.bottom; point.x = _line_compute_intersection_x_for_y (&edge->edge.line, point.y); - _cairo_bo_skiplist_event_init (&event, - CAIRO_BO_EVENT_TYPE_STOP, - edge, NULL, - &point); - - return _cairo_bo_event_queue_insert (event_queue, &event); + return _cairo_bo_event_queue_insert (event_queue, + CAIRO_BO_EVENT_TYPE_STOP, + edge, NULL, + &point); } static void _cairo_bo_event_queue_fini (cairo_bo_event_queue_t *event_queue) { - _cairo_skip_list_fini (&event_queue->event_queue); + _pqueue_fini (&event_queue->pqueue); + _cairo_freepool_fini (&event_queue->pool); } static inline cairo_status_t @@ -1026,10 +1096,6 @@ _cairo_bo_event_queue_insert_if_intersect_below_current_y (cairo_bo_event_queue_ cairo_bo_edge_t *right) { cairo_bo_point32_t intersection; - cairo_bo_skiplist_event_t event; - - if (left == NULL || right == NULL) - return CAIRO_STATUS_SUCCESS; if (_line_equal (&left->edge.line, &right->edge.line)) return CAIRO_STATUS_SUCCESS; @@ -1045,12 +1111,10 @@ _cairo_bo_event_queue_insert_if_intersect_below_current_y (cairo_bo_event_queue_ if (! _cairo_bo_edge_intersect (left, right, &intersection)) return CAIRO_STATUS_SUCCESS; - _cairo_bo_skiplist_event_init (&event, - CAIRO_BO_EVENT_TYPE_INTERSECTION, - left, right, - &intersection); - - return _cairo_bo_event_queue_insert (event_queue, &event); + return _cairo_bo_event_queue_insert (event_queue, + CAIRO_BO_EVENT_TYPE_INTERSECTION, + left, right, + &intersection); } static void @@ -1088,7 +1152,7 @@ _cairo_bo_sweep_line_insert (cairo_bo_sweep_line_t *sweep_line, edge->next = next; if (next != NULL) next->prev = edge; - } else { + } else if (cmp > 0) { next = sweep_line->current_edge; prev = next->prev; while (prev != NULL && @@ -1105,6 +1169,13 @@ _cairo_bo_sweep_line_insert (cairo_bo_sweep_line_t *sweep_line, prev->next = edge; else sweep_line->head = edge; + } else { + prev = sweep_line->current_edge; + edge->prev = prev; + edge->next = prev->next; + if (prev->next != NULL) + prev->next->prev = edge; + prev->next = edge; } } else { sweep_line->head = edge; @@ -1186,22 +1257,14 @@ _cairo_bo_event_print (cairo_bo_event_t *event) static void _cairo_bo_event_queue_print (cairo_bo_event_queue_t *event_queue) { - skip_elt_t *elt; - /* XXX: fixme to print the start/stop array too. */ - cairo_skip_list_t *queue = &event_queue->event_queue; - printf ("Event queue:\n"); - - for (elt = queue->chains[0]; elt; elt = elt->next[0]) - _cairo_bo_event_print (SKIP_ELT_TO_EVENT (elt)); } static void _cairo_bo_sweep_line_print (cairo_bo_sweep_line_t *sweep_line) { cairo_bool_t first = TRUE; - skip_elt_t *elt; cairo_bo_edge_t *edge; printf ("Sweep line from edge list: "); @@ -1578,18 +1641,22 @@ _cairo_bentley_ottmann_tessellate_bo_edges (cairo_bo_event_t **start_events, left = e1->prev; right = e1->next; - status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, e1); - if (unlikely (status)) - goto unwind; + if (left != NULL) { + status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, e1); + if (unlikely (status)) + goto unwind; + } - status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, e1, right); - if (unlikely (status)) - goto unwind; + if (right != NULL) { + status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, e1, right); + if (unlikely (status)) + goto unwind; + } break; case CAIRO_BO_EVENT_TYPE_STOP: - e1 = ((cairo_bo_skiplist_event_t *) event)->e1; + e1 = ((cairo_bo_queue_event_t *) event)->e1; _cairo_bo_event_queue_delete (&event_queue, event); left = e1->prev; @@ -1606,15 +1673,17 @@ _cairo_bentley_ottmann_tessellate_bo_edges (cairo_bo_event_t **start_events, e1->prev = NULL; } - status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, right); - if (unlikely (status)) - goto unwind; + if (left != NULL && right != NULL) { + status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, right); + if (unlikely (status)) + goto unwind; + } break; case CAIRO_BO_EVENT_TYPE_INTERSECTION: - e1 = ((cairo_bo_skiplist_event_t *) event)->e1; - e2 = ((cairo_bo_skiplist_event_t *) event)->e2; + e1 = ((cairo_bo_queue_event_t *) event)->e1; + e2 = ((cairo_bo_queue_event_t *) event)->e2; _cairo_bo_event_queue_delete (&event_queue, event); /* skip this intersection if its edges are not adjacent */ @@ -1630,13 +1699,17 @@ _cairo_bentley_ottmann_tessellate_bo_edges (cairo_bo_event_t **start_events, /* after the swap e2 is left of e1 */ - status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, e2); - if (unlikely (status)) - goto unwind; + if (left != NULL) { + status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, e2); + if (unlikely (status)) + goto unwind; + } - status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, e1, right); - if (unlikely (status)) - goto unwind; + if (right != NULL) { + status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, e1, right); + if (unlikely (status)) + goto unwind; + } break; } @@ -1704,7 +1777,6 @@ _cairo_bentley_ottmann_tessellate_polygon (cairo_traps_t *traps, events[i].edge.deferred_trap.right = NULL; events[i].edge.prev = NULL; events[i].edge.next = NULL; - events[i].edge.sweep_line_elt = NULL; } #if DEBUG_TRAPS @@ -1765,7 +1837,6 @@ _add_event (const cairo_line_t *line, event->edge.deferred_trap.right = NULL; event->edge.prev = NULL; event->edge.next = NULL; - event->edge.sweep_line_elt = NULL; return 1; } diff --git a/src/cairo-freelist.c b/src/cairo-freelist.c index 83647f20..6bbee844 100644 --- a/src/cairo-freelist.c +++ b/src/cairo-freelist.c @@ -104,8 +104,9 @@ _cairo_freepool_init (cairo_freepool_t *freepool, unsigned nodesize) node->next = freepool->first_free_node; freepool->first_free_node = node; - VG (VALGRIND_MAKE_MEM_NOACCESS (node, freepool->nodesize)); } + VG (VALGRIND_MAKE_MEM_NOACCESS (freepool->embedded_pool, + sizeof (freepool->embedded_pool))); } void @@ -133,7 +134,7 @@ _cairo_freepool_alloc_from_new_pool (cairo_freepool_t *freepool) poolsize = (128 * freepool->nodesize + 8191) & -8192; node = malloc (poolsize); - if (node == NULL) + if (unlikely (node == NULL)) return node; node->next = freepool->pools; @@ -150,8 +151,9 @@ _cairo_freepool_alloc_from_new_pool (cairo_freepool_t *freepool) node->next = freepool->first_free_node; freepool->first_free_node = node; - VG (VALGRIND_MAKE_MEM_NOACCESS (node, freepool->nodesize)); } + VG (VALGRIND_MAKE_MEM_NOACCESS (freepool->pools, + (128 * freepool->nodesize + 8191) & -8192)); return ptr; } diff --git a/src/cairo-skiplist-private.h b/src/cairo-skiplist-private.h deleted file mode 100644 index c0e5bce5..00000000 --- a/src/cairo-skiplist-private.h +++ /dev/null @@ -1,118 +0,0 @@ -/* - * Copyright © 2006 Keith Packard - * Copyright © 2006 Carl Worth - * - * Permission to use, copy, modify, distribute, and sell this software and its - * documentation for any purpose is hereby granted without fee, provided that - * the above copyright notice appear in all copies and that both that copyright - * notice and this permission notice appear in supporting documentation, and - * that the name of the copyright holders not be used in advertising or - * publicity pertaining to distribution of the software without specific, - * written prior permission. The copyright holders make no representations - * about the suitability of this software for any purpose. It is provided "as - * is" without express or implied warranty. - * - * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, - * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO - * EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT OR - * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, - * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER - * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE - * OF THIS SOFTWARE. - */ - -#ifndef SKIPLIST_H -#define SKIPLIST_H - -#include "cairoint.h" - -/* - * Skip lists are described in detail here: - * - * http://citeseer.ist.psu.edu/pugh90skip.html - */ - -/* Note that random_level() called from alloc_node_for_level() depends on - * this being not more than 16. - */ -#define MAX_LEVEL 15 - -/* Returns the index of the free-list to use for a node at level 'level' */ -#define FREELIST_FOR_LEVEL(level) (((level) - 1) / 2) - -/* Returns the maximum level that uses the same free-list as 'level' does */ -#define FREELIST_MAX_LEVEL_FOR(level) (((level) + 1) & ~1) - -#define MAX_FREELIST_LEVEL (FREELIST_FOR_LEVEL (MAX_LEVEL - 1) + 1) - -/* - * Skip list element. In order to use the skip list, the caller must - * generate a structure for list elements that has as its final member - * a skip_elt_t, (which will be allocated with variable size). - * - * The caller must also pass the size of the structure to - * _cairo_skip_list_init. - */ -typedef struct _skip_elt { - int prev_index; - struct _skip_elt *prev; - struct _skip_elt *next[1]; -} skip_elt_t; - -#define SKIP_LIST_ELT_TO_DATA(type, elt) ((type *) ((char *) (elt) - (sizeof (type) - sizeof (skip_elt_t)))) - -typedef int -(*cairo_skip_list_compare_t) (void *list, const void *a, const void *b); - -typedef struct _skip_list { - cairo_skip_list_compare_t compare; - size_t elt_size; - size_t data_size; - skip_elt_t *chains[MAX_LEVEL]; - skip_elt_t *freelists[MAX_FREELIST_LEVEL]; - int max_level; - struct pool *pool; - char pool_embedded[1024]; -} cairo_skip_list_t; - -/* Initialize a new skip list. The compare function accepts a pointer - * to the list as well as pointers to two elements. The function must - * return a value greater than zero, zero, or less then 0 if the first - * element is considered respectively greater than, equal to, or less - * than the second element. The size of each object, (as computed by - * sizeof) is passed for elt_size. Note that the structure used for - * list elements must have as its final member a skip_elt_t - */ -cairo_private void -_cairo_skip_list_init (cairo_skip_list_t *list, - cairo_skip_list_compare_t compare, - size_t elt_size); - - -/* Deallocate resources associated with a skip list and all elements - * in it. (XXX: currently this simply deletes all elements.) - */ -cairo_private void -_cairo_skip_list_fini (cairo_skip_list_t *list); - -/* Insert a new element into the list at the correct sort order as - * determined by compare. If unique is true, then duplicate elements - * are ignored and the already inserted element is returned. - * Otherwise data will be copied (elt_size bytes from <data> via - * memcpy) and the new element is returned. */ -cairo_private void * -_cairo_skip_list_insert (cairo_skip_list_t *list, void *data); - -/* Find an element which compare considers equal to <data> */ -cairo_private void * -_cairo_skip_list_find (cairo_skip_list_t *list, void *data); - -/* Delete an element which compare considers equal to <data> */ -cairo_private void -_cairo_skip_list_delete (cairo_skip_list_t *list, void *data); - -/* Delete the given element from the list. */ -cairo_private void -_cairo_skip_list_delete_given (cairo_skip_list_t *list, skip_elt_t *given); - -#endif diff --git a/src/cairo-skiplist.c b/src/cairo-skiplist.c deleted file mode 100644 index 8d8c8d1f..00000000 --- a/src/cairo-skiplist.c +++ /dev/null @@ -1,399 +0,0 @@ -/* - * Copyright © 2006 Keith Packard - * Copyright © 2006 Carl Worth - * - * Permission to use, copy, modify, distribute, and sell this software and its - * documentation for any purpose is hereby granted without fee, provided that - * the above copyright notice appear in all copies and that both that copyright - * notice and this permission notice appear in supporting documentation, and - * that the name of the copyright holders not be used in advertising or - * publicity pertaining to distribution of the software without specific, - * written prior permission. The copyright holders make no representations - * about the suitability of this software for any purpose. It is provided "as - * is" without express or implied warranty. - * - * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, - * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO - * EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT OR - * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, - * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER - * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE - * OF THIS SOFTWARE. - */ - -#include "cairoint.h" - -#include "cairo-skiplist-private.h" - -#if HAVE_FFS -#include <strings.h> /* ffs() */ -#endif - -#define ELT_DATA(elt) (void *) ((char*) (elt) - list->data_size) -#define NEXT_TO_ELT(next) (skip_elt_t *) ((char *) (next) - offsetof (skip_elt_t, next)) - -static uint32_t -hars_petruska_f54_1_random (void) -{ -# define rol(x,k) ((x << k) | (x >> (32-k))) - static uint32_t x = 0; - x = (x ^ rol(x, 5) ^ rol(x, 24)) + 0x37798849; - return x; -# undef rol -} - -struct pool { - struct pool *next; - char *ptr; - unsigned int rem; -}; - -static struct pool * -pool_new (void) -{ - struct pool *pool; - - pool = malloc (8192 - 8); - if (unlikely (pool == NULL)) - return NULL; - - pool->next = NULL; - pool->rem = 8192 - 8 - sizeof (struct pool); - pool->ptr = (char *) (pool + 1); - - return pool; -} - -static void -pools_destroy (struct pool *pool) -{ - while (pool->next != NULL) { - struct pool *next = pool->next; - free (pool); - pool = next; - } -} - -/* - * Initialize an empty skip list - */ -void -_cairo_skip_list_init (cairo_skip_list_t *list, - cairo_skip_list_compare_t compare, - size_t elt_size) -{ - int i; - - list->compare = compare; - list->elt_size = elt_size; - list->data_size = elt_size - sizeof (skip_elt_t); - list->pool = (struct pool *) list->pool_embedded; - list->pool->next = NULL; - list->pool->rem = sizeof (list->pool_embedded) - sizeof (struct pool); - list->pool->ptr = list->pool_embedded + sizeof (struct pool); - - for (i = 0; i < MAX_LEVEL; i++) { - list->chains[i] = NULL; - } - - for (i = 0; i < MAX_FREELIST_LEVEL; i++) { - list->freelists[i] = NULL; - } - - list->max_level = 0; -} - -void -_cairo_skip_list_fini (cairo_skip_list_t *list) -{ - pools_destroy (list->pool); -} - -/* - * Generate a random level number, distributed - * so that each level is 1/4 as likely as the one before - * - * Note that level numbers run 1 <= level < MAX_LEVEL - */ -static int -random_level (void) -{ - /* tricky bit -- each bit is '1' 75% of the time. - * This works because we only use the lower MAX_LEVEL - * bits, and MAX_LEVEL < 16 */ - uint32_t bits = hars_petruska_f54_1_random (); -#if HAVE_FFS - return ffs (-(1<<MAX_LEVEL) | bits | bits >> 16); -#else - int level = 1; - - bits |= -(1<<MAX_LEVEL) | bits >> 16; - while ((bits & 1) == 0) { - level++; - bits >>= 1; - } - return level; -#endif -} - -static void * -pool_alloc (cairo_skip_list_t *list, - unsigned int level) -{ - unsigned int size; - struct pool *pool; - void *ptr; - - size = list->elt_size + - (FREELIST_MAX_LEVEL_FOR (level) - 1) * sizeof (skip_elt_t *); - - pool = list->pool; - if (size > pool->rem) { - pool = pool_new (); - if (unlikely (pool == NULL)) - return NULL; - - pool->next = list->pool; - list->pool = pool; - } - - ptr = pool->ptr; - pool->ptr += size; - pool->rem -= size; - - return ptr; -} - -static void * -alloc_node_for_level (cairo_skip_list_t *list, unsigned level) -{ - int freelist_level = FREELIST_FOR_LEVEL (level); - if (list->freelists[freelist_level]) { - skip_elt_t *elt = list->freelists[freelist_level]; - list->freelists[freelist_level] = elt->prev; - return ELT_DATA(elt); - } - return pool_alloc (list, level); -} - -static void -free_elt (cairo_skip_list_t *list, skip_elt_t *elt) -{ - int level = elt->prev_index + 1; - int freelist_level = FREELIST_FOR_LEVEL (level); - elt->prev = list->freelists[freelist_level]; - list->freelists[freelist_level] = elt; -} - -/* - * Insert 'data' into the list - */ -void * -_cairo_skip_list_insert (cairo_skip_list_t *list, void *data) -{ - skip_elt_t **update[MAX_LEVEL]; - skip_elt_t *prev[MAX_LEVEL]; - char *data_and_elt; - skip_elt_t *elt, **next; - int i, level, prev_index; - - /* - * Find links along each chain - */ - elt = NULL; - next = list->chains; - for (i = list->max_level; --i >= 0; ) - { - if (elt != next[i]) - { - for (; (elt = next[i]); next = elt->next) - { - int cmp = list->compare (list, ELT_DATA(elt), data); - if (0 == cmp) - return ELT_DATA(elt); - if (cmp > 0) - break; - } - } - update[i] = next; - if (next != list->chains) - prev[i] = NEXT_TO_ELT (next); - else - prev[i] = NULL; - } - level = random_level (); - prev_index = level - 1; - - /* - * Create new list element - */ - if (level > list->max_level) - { - level = list->max_level + 1; - prev_index = level - 1; - prev[prev_index] = NULL; - update[list->max_level] = list->chains; - list->max_level = level; - } - - data_and_elt = alloc_node_for_level (list, level); - if (unlikely (data_and_elt == NULL)) { - _cairo_error_throw (CAIRO_STATUS_NO_MEMORY); - return NULL; - } - - memcpy (data_and_elt, data, list->data_size); - elt = (skip_elt_t *) (data_and_elt + list->data_size); - - elt->prev_index = prev_index; - elt->prev = prev[prev_index]; - - /* - * Insert into all chains - */ - for (i = 0; i < level; i++) - { - elt->next[i] = update[i][i]; - if (elt->next[i] && elt->next[i]->prev_index == i) - elt->next[i]->prev = elt; - update[i][i] = elt; - } - - return data_and_elt; -} - -void * -_cairo_skip_list_find (cairo_skip_list_t *list, void *data) -{ - int i; - skip_elt_t **next = list->chains; - skip_elt_t *elt; - - /* - * Walk chain pointers one level at a time - */ - for (i = list->max_level; --i >= 0;) - while (next[i] && list->compare (list, data, ELT_DATA(next[i])) > 0) - { - next = next[i]->next; - } - /* - * Here we are - */ - elt = next[0]; - if (elt && list->compare (list, data, ELT_DATA (elt)) == 0) - return ELT_DATA (elt); - - return NULL; -} - -void -_cairo_skip_list_delete (cairo_skip_list_t *list, void *data) -{ - skip_elt_t **update[MAX_LEVEL], *prev[MAX_LEVEL]; - skip_elt_t *elt, **next; - int i; - - /* - * Find links along each chain - */ - next = list->chains; - for (i = list->max_level; --i >= 0; ) - { - for (; (elt = next[i]); next = elt->next) - { - if (list->compare (list, ELT_DATA (elt), data) >= 0) - break; - } - update[i] = &next[i]; - if (next == list->chains) - prev[i] = NULL; - else - prev[i] = NEXT_TO_ELT (next); - } - elt = next[0]; - assert (list->compare (list, ELT_DATA (elt), data) == 0); - for (i = 0; i < list->max_level && *update[i] == elt; i++) { - *update[i] = elt->next[i]; - if (elt->next[i] && elt->next[i]->prev_index == i) - elt->next[i]->prev = prev[i]; - } - while (list->max_level > 0 && list->chains[list->max_level - 1] == NULL) - list->max_level--; - free_elt (list, elt); -} - -void -_cairo_skip_list_delete_given (cairo_skip_list_t *list, skip_elt_t *given) -{ - skip_elt_t **update[MAX_LEVEL], *prev[MAX_LEVEL]; - skip_elt_t *elt, **next; - int i; - - /* - * Find links along each chain - */ - if (given->prev) - next = given->prev->next; - else - next = list->chains; - for (i = given->prev_index + 1; --i >= 0; ) - { - for (; (elt = next[i]); next = elt->next) - { - if (elt == given) - break; - } - update[i] = &next[i]; - if (next == list->chains) - prev[i] = NULL; - else - prev[i] = NEXT_TO_ELT (next); - } - elt = next[0]; - assert (elt == given); - for (i = 0; i < (given->prev_index + 1) && *update[i] == elt; i++) { - *update[i] = elt->next[i]; - if (elt->next[i] && elt->next[i]->prev_index == i) - elt->next[i]->prev = prev[i]; - } - while (list->max_level > 0 && list->chains[list->max_level - 1] == NULL) - list->max_level--; - free_elt (list, elt); -} - -#if MAIN -typedef struct { - int n; - skip_elt_t elt; -} test_elt_t; - -static int -test_cmp (void *list, const void *A, const void *B) -{ - const test_elt_t *a = A, *b = B; - return a->n - b->n; -} - -int -main (void) -{ - cairo_skip_list_t list; - test_elt_t elt; - int n; - - _cairo_skip_list_init (&list, test_cmp, sizeof (test_elt_t)); - for (n = 0; n < 10000000; n++) { - void *elt_and_data; - elt.n = n; - elt_and_data = _cairo_skip_list_insert (&list, &elt); - assert (elt_and_data != NULL); - } - _cairo_skip_list_fini (&list); - - return 0; -} - -/* required supporting stubs */ -cairo_status_t _cairo_error (cairo_status_t status) { return status; } -#endif |