listspolygon-lists

2 files changed, 88 insertions, 133 deletions

diff --git a/pixman/pixman-polygon.c b/pixman/pixman-polygon.c
index a4b267b1..c4e15536 100644
--- a/pixman/pixman-polygon.c
+++ b/pixman/pixman-polygon.c
@@ -236,8 +236,7 @@ struct step_t
 
 struct edge_t
 {
-    int				next;
-    int				prev;
+    pixman_link_t		link;
     pixman_fixed_24_8_t		x;
     pixman_fixed_24_8_t		bottom;
     int				dir;
@@ -257,9 +256,8 @@ struct edge_t
 
 struct active_t
 {
-    int						head;
-    int						tail;
-    int						free;
+    pixman_list_t				active;
+    pixman_list_t				free;
     const sampling_strategy_t *			strategy;
     const pixman_segment_24_8_t *		global_next;
     const pixman_segment_24_8_t *		global_last;
@@ -276,121 +274,54 @@ struct active_t
     edge_t					edges[16];
 };
 
-static void
-list_append (active_t *active, edge_t *edge)
-{
-    int idx = edge - active->edges;
-
-    if (active->head == -1)
-    {
-	edge->next = -1;
-	edge->prev = -1;
-
-	active->head = idx;
-	active->tail = idx;
-    }
-    else
-    {
-	edge->prev = active->tail;
-	edge->next = -1;
-	active->edges[active->tail].next = idx;
-	active->tail = idx;
-    }
-
-    active->n_edges++;
-}
-
-static void
-list_remove (active_t *active, edge_t *edge)
-{
-    int next = edge->next;
-    int prev = edge->prev;
-
-    if (next != -1)
-	active->edges[next].prev = prev;
-    else
-	active->tail = prev;
-
-    if (prev != -1)
-	active->edges[prev].next = next;
-    else
-	active->head = next;
-
-    active->n_edges--;
-}
-
-static void
-move_after (active_t *active, edge_t *mover, int p)
-{
-    int idx = mover - active->edges;
-
-    list_remove (active, mover);
-
-    if (p == -1)
-    {
-	mover->next = active->head;
-	mover->prev = -1;
-
-	if (active->head != -1)
-	    active->edges[active->head].prev = idx;
-
-	active->head = idx;
-
-	if (active->tail == -1)
-	    active->tail = idx;
-    }
-    else
-    {
-	edge_t *prev = &active->edges[p];
-
-	mover->next = prev->next;
-	mover->prev = p;
-
-	if (prev->next != -1)
-	    active->edges[prev->next].prev = idx;
-	prev->next = idx;
-    }
-
-    active->n_edges++;
-}
-
 static active_t *
 allocate_edge (active_t *active, edge_t **edge)
 {
-    if (active->free == -1)
+    pixman_link_t *head;
+
+    if (pixman_list_is_empty (&active->free))
     {
 	int n = 2 * active->n_edges;
+	active_t *old;
+	intptr_t offset;
 	int n_bytes;
 	int i;
 
 	n_bytes = sizeof (*active) + n * sizeof (edge_t) - sizeof (active->edges);
 
+	old = active;
 	if (!(active = realloc (active, n_bytes)))
 	    return NULL;
 
+	offset = active - old;
+
+	active->active.head += offset;
+	active->active.tail += offset;
+	for (i = 0; i < active->n_edges; ++i)
+	{
+	    edge_t *e = &(active->edges[active->n_edges + i]);
+
+	    e->link.next += offset;
+	    e->link.prev += offset;
+	}
+
 	for (i = 0; i < n - active->n_edges; ++i)
 	{
 	    edge_t *e = &(active->edges[active->n_edges + i]);
 
-	    e->next = active->free;
-	    active->free = active->n_edges + i;
+	    pixman_list_prepend (&active->free, &e->link);
 	}
     }
 
-    *edge = &(active->edges[active->free]);
+    head = active->free.head;
+    
+    pixman_list_unlink (head);
 
-    active->free = (*edge)->next;
+    *edge = CONTAINER_OF (edge_t, link, head);
 
     return active;
 }
 
-static void
-free_edge (active_t *active, edge_t *edge)
-{
-    edge->next = active->free;
-    active->free = edge - active->edges;
-}
-
 static force_inline void
 edge_step (edge_t *edge, step_t *step)
 {
@@ -539,7 +470,7 @@ edge_init (edge_t *edge, const pixman_segment_24_8_t *segment,
 static active_t *
 update_active (active_t *active)
 {
-    int i;
+    pixman_link_t *link;
 
     /* Add new edges */
     while (active->global_next < active->global_last		&&
@@ -570,7 +501,7 @@ update_active (active_t *active)
 			   active->strategy->small_step,
 			   active->strategy->big_step);
 
-		list_append (active, edge);
+		pixman_list_append (&active->active, &edge->link);
 #if 0
 		printf ("New edge: %p\n", edge);
 #endif
@@ -586,44 +517,42 @@ oom_bail:
      * a new edge can be so close to horizontal that it lives and
      * dies without ever intersecting a sample row.
      */
-    i = active->head;
-    while (i != -1)
+    link = active->active.head;
+    while (link != (pixman_link_t *)&active->active)
     {
-	edge_t *edge = &(active->edges[i]);
-	int next = edge->next;
+	pixman_link_t *next = link->next;
+	edge_t *edge = CONTAINER_OF (edge_t, link, link);
 
 	if (edge->bottom <= active->yi)
 	{
 #ifdef PRINT_DEBUG_SPEW
 #endif
-#if 0
-	    printf ("Dead edge %p\n", edge);
-#endif
-	    list_remove (active, edge);
-	    free_edge (active, edge);
+	    pixman_list_unlink (link);
+	    pixman_list_prepend (&active->free, link);
+	    active->n_edges--;
 	}
 	else
 	{
-	    int k;
+	    pixman_link_t *k;
 
-	    for (k = edge->prev; k != -1; k = active->edges[k].prev)
+	    k = edge->link.prev;
+	    while (k != (pixman_link_t *)&active->active)
 	    {
-		if (active->edges[k].x <= edge->x)
+		edge_t *e = CONTAINER_OF (edge_t, link, k);
+
+		if (e->x <= edge->x)
 		    break;
-	    }
 
-	    if (k != edge->prev)
-	    {
-#if 0
-		printf ("Intersecting edge: %p\n", edge);
-#endif
-		move_after (active, edge, k);
+		k = k->prev;
 	    }
+
+	    if (k != edge->link.prev)
+		pixman_list_move_after (link, k);
 	}
 
-	i = next;
+	link = next;
     }
-
+	
 #ifdef PRINT_DEBUG_SPEW
     for (i = active->head; i != -1; i = active->edges[i].next)
     {
@@ -664,9 +593,9 @@ oom_bail:
 #define NON_VERTICAL		(1 << 3)
 #define NEW_SURVIVORS		(1 << 4)
 
-	for (i = active->head; i != -1; i = active->edges[i].next)
+	PIXMAN_LIST_FOREACH (&active->active, link)
 	{
-	    edge_t *edge = &(active->edges[i]);
+	    edge_t *edge = CONTAINER_OF (edge_t, link, link);
 
 	    if (edge->bottom < next)
 		flags |= DYING_EDGES;
@@ -815,14 +744,12 @@ create_active (polygon_t *polygon, pixman_iter_t *iter)
 	seg++;
     }
 
-    active->head = -1;
-    active->tail = -1;
-
-    active->free = -1;
+    pixman_list_init (&active->active);
+    pixman_list_init (&active->free);
 
     active->n_edges = 0;
     for (i = sizeof (active->edges) / sizeof (active->edges[0]) - 1; i >= 0; --i)
-	free_edge (active, &(active->edges[i]));
+	pixman_list_prepend (&active->free, &(active->edges[i].link));
 
     return update_active (active);
 }
@@ -878,15 +805,15 @@ step_active_inline (active_t *active, int offset, uint winding_mask, uint32_t *d
 {
     pixman_bool_t on = FALSE;
     unsigned winding = 0;
-    int i;
+    pixman_link_t *link;
 
 #if 0
     printf ("Active: %d (%x)\n", active->n_edges, active->yi);
 #endif
 
-    for (i = active->head; i != -1; i = active->edges[i].next)
+    PIXMAN_LIST_FOREACH (&active->active, link)
     {
-	edge_t *edge = &(active->edges[i]);
+	edge_t *edge = CONTAINER_OF (edge_t, link, link);
 
 	winding += edge->dir;
 
@@ -940,14 +867,15 @@ step_individually (active_t *active, uint32_t *dirty)
     unsigned winding = 0;
     const sampling_strategy_t *strategy = active->strategy;
     int n_small = strategy->n_grid_y - 1;
-    int i, j;
+    int j;
     pixman_bool_t on = FALSE;
+    pixman_link_t *link;
 
     if (active->winding_mask == 0xffffffff)
     {
-	for (i = active->head; i != -1; i = active->edges[i].next)
+	PIXMAN_LIST_FOREACH (&active->active, link)
 	{
-	    edge_t *edge = &(active->edges[i]);
+	    edge_t *edge = CONTAINER_OF (edge_t, link, link);
 	    winding += edge->dir;
 
 	    if (!!winding != on)
@@ -968,9 +896,9 @@ step_individually (active_t *active, uint32_t *dirty)
     }
     else
     {
-	for (i = active->head; i != -1; i = active->edges[i].next)
+	PIXMAN_LIST_FOREACH (&active->active, link)
 	{
-	    edge_t *edge = &(active->edges[i]);
+	    edge_t *edge = CONTAINER_OF (edge_t, link, link);
 	    winding += edge->dir;
 
 	    if ((winding & 1) != on)
diff --git a/pixman/pixman-private.h b/pixman/pixman-private.h
index 623b1b20..3de25664 100644
--- a/pixman/pixman-private.h
+++ b/pixman/pixman-private.h
@@ -750,6 +750,12 @@ pixman_list_init (pixman_list_t *list)
     list->tail = (pixman_link_t *)list;
 }
 
+static force_inline pixman_bool_t
+pixman_list_is_empty (pixman_list_t *list)
+{
+    return list->head == (pixman_link_t *)list;
+}
+
 static force_inline void
 pixman_list_prepend (pixman_list_t *list, pixman_link_t *link)
 {
@@ -760,6 +766,15 @@ pixman_list_prepend (pixman_list_t *list, pixman_link_t *link)
 }
 
 static force_inline void
+pixman_list_append (pixman_list_t *list, pixman_link_t *link)
+{
+    link->next = (pixman_link_t *)list;
+    link->prev = list->tail;
+    list->tail->next = link;
+    list->tail = link;
+}
+
+static force_inline void
 pixman_list_unlink (pixman_link_t *link)
 {
     link->prev->next = link->next;
@@ -773,6 +788,18 @@ pixman_list_move_to_front (pixman_list_t *list, pixman_link_t *link)
     pixman_list_prepend (list, link);
 }
 
+/* Move link so that it comes after @after */
+static force_inline void
+pixman_list_move_after (pixman_link_t *link, pixman_link_t *after)
+{
+    pixman_list_unlink (link);
+    
+    link->prev = after;
+    link->next = after->next;
+    after->next->prev = link;
+    after->next = link;
+}
+
 #define PIXMAN_LIST_FOREACH(list, link)					\
     for ((link) = (list)->head;						\
 	 (link) != (pixman_link_t *)(list);				\