Use radix heap.

FIXME: clip compression is disabled.
       malloc returns are not checked.

1 files changed, 207 insertions, 206 deletions

diff --git a/pixman/pixman-polygon.c b/pixman/pixman-polygon.c
index 61b63436..83002a02 100644
--- a/pixman/pixman-polygon.c
+++ b/pixman/pixman-polygon.c
@@ -38,6 +38,7 @@ typedef union event_t event_t;
 typedef struct event_queue_t event_queue_t;
 typedef struct trap_iter_t trap_iter_t;
 typedef struct step_t step_t;
+typedef struct bucket_t bucket_t;
 
 /*
  * The sample grid.
@@ -702,70 +703,21 @@ typedef struct
     event_t *			event;
 } event_key_t;
 
-struct event_queue_t
+struct bucket_t
 {
-    size_t	n;
+    int		n_entries;
+    int		n_allocated;
+    int		minimum;	/* index of minimum event */
     event_key_t	events[1];
 };
 
-#define FAN_OUT 4
-
-static force_inline int
-get_parent (int i)
-{
-    return (i - 1) / FAN_OUT;
-}
-
-static force_inline ssize_t
-get_child (int i, int c)
-{
-    return i * FAN_OUT + c + 1;
-}
-
-static force_inline pixman_fixed_24_8_t
-y_value (const event_key_t *key)
-{
-    return key->y_value;
-}
-
-static force_inline pixman_bool_t
-less_than (event_queue_t *queue, int idx1, int idx2)
-{
-    pixman_fixed_24_8_t y1, y2;
-
-    y1 = queue->events[idx1].y_value;
-    y2 = queue->events[idx2].y_value;
-
-    return y1 < y2;
-}
-
-static force_inline void
-swap (event_queue_t *queue, int i1, int i2)
-{
-    event_key_t tmp = queue->events[i1];
-
-    queue->events[i1] = queue->events[i2];
-    queue->events[i2] = tmp;
-}
-
-#define INITIAL_SIZE 1024
-
-static unsigned int
-queue_size (unsigned int n_events)
+struct event_queue_t
 {
-    if (n_events < INITIAL_SIZE)
-	n_events = INITIAL_SIZE;
-
-    n_events |= n_events >> 1;
-    n_events |= n_events >> 2;
-    n_events |= n_events >> 4;
-    n_events |= n_events >> 8;
-    n_events |= n_events >> 16;
-
-    n_events++;
-
-    return n_events;
-}
+    int		min_bucket;
+    bucket_t *	buckets[33];
+    bucket_t *  aux_bucket;
+    int32_t	last_del;
+};
 
 static __thread event_t *free_list;
 
@@ -799,57 +751,118 @@ free_event (event_t *event)
     free_list = event;
 }
 
-static event_t *
-event_queue_insert (event_queue_t **    queue,
-		    event_type_t        type,
-		    pixman_fixed_24_8_t y_value)
+#define BUCKET_SIZE(n)							\
+    ((sizeof (bucket_t)) + ((n) - 1) * sizeof (event_key_t))
+
+#define INITIAL_SIZE 64
+
+static bucket_t *
+bucket_create (void)
 {
-    event_queue_t *q;
-    ssize_t idx, p;
-    event_key_t *key;
-    event_t *event;
-    ssize_t n, size;
+    bucket_t *bucket = malloc (BUCKET_SIZE (INITIAL_SIZE));
 
-    q = *queue;
+    bucket->n_entries = 0;
+    bucket->n_allocated = INITIAL_SIZE;
+    bucket->minimum = -1;
 
-    n = 1;
-    if (q)
-	n += q->n;
+    return bucket;
+}
 
-    size = queue_size (n);
-    if (!q || queue_size (q->n) < size)
+static bucket_t *
+bucket_append (bucket_t *bucket, int32_t y_value, event_t *event)
+{
+    int n = bucket->n_entries;
+    int m;
+
+    if (n == bucket->n_allocated)
     {
-	if (!(q = realloc (q, sizeof (*queue) + (size - 1) * sizeof (event_t))))
-	    return NULL;
+	bucket = realloc (bucket, BUCKET_SIZE (2 * n));
+
+	bucket->n_allocated = 2 * n;
     }
 
-    q->n = n;
+    bucket->events[n].y_value = y_value;
+    bucket->events[n].event = event;;
 
-    idx = q->n - 1;
+    m = bucket->minimum;
+    if (m == -1 || y_value < bucket->events[m].y_value)
+	bucket->minimum = n;
 
-    key = &(q->events[idx]);
-    key->y_value = y_value;
-    key->event = event = alloc_event();
+    bucket->n_entries = n + 1;
+    return bucket;
+}
 
-    key->event->common.type = type;
-    key->event->common.y_value = y_value;
+static event_queue_t *
+event_queue_create (void)
+{
+    event_queue_t *event_queue = malloc (sizeof *event_queue);
+    int i;
 
-    p = get_parent (idx);
-    while (idx > 0 && less_than (q, idx, p))
-    {
-	swap (q, idx, p);
+    for (i = 0; i < 33; ++i)
+	event_queue->buckets[i] = bucket_create();
 
-	idx = p;
-	p = get_parent (idx);
-    }
+    event_queue->aux_bucket = bucket_create();
+
+    event_queue->min_bucket = 33;
+    event_queue->last_del = INT32_MIN;
+
+    return event_queue;
+}
+
+static void
+event_queue_destroy (event_queue_t *event_queue)
+{
+    int i;
+
+    for (i = 0; i < 33; ++i)
+	free (event_queue->buckets[i]);
+    free (event_queue->aux_bucket);
+    free (event_queue);
+}
+
+static inline int
+clz (int32_t v)
+{
+    return (v == 0)? 32 : __builtin_clz (v);
+}
+
+#define BUCKET_NO(r, value)						\
+    (32 - clz (((value) ^ (r)->last_del)))
+
+static void
+event_queue_insert_internal (event_queue_t *event_queue,
+			     int32_t        value,
+			     event_t       *event)
+{
+    int bucket_no = BUCKET_NO (event_queue, value);
+    bucket_t *bucket = event_queue->buckets[bucket_no];
+
+    bucket = bucket_append (bucket, value, event);
+
+    if (bucket_no < event_queue->min_bucket)
+	event_queue->min_bucket = bucket_no;
+
+    event_queue->buckets[bucket_no] = bucket;
+
+}
+
+static event_t *
+event_queue_insert (event_queue_t *	event_queue,
+		    event_type_t	type,
+		    int32_t		value)
+{
+    event_t *event = alloc_event();
+
+    event_queue_insert_internal (event_queue, value, event);
 
-    *queue = q;
+    event->common.type = type;
+    event->common.y_value = value;
 
     return event;
 }
 
 static void
-event_queue_insert_new (event_queue_t **       queue,
+event_queue_insert_new (event_queue_t *        queue,
 			pixman_fixed_24_8_t    y_value,
 			pixman_segment_24_8_t *segment)
 {
@@ -860,7 +873,7 @@ event_queue_insert_new (event_queue_t **       queue,
 }
 
 static void
-event_queue_insert_dead (event_queue_t **    queue,
+event_queue_insert_dead (event_queue_t *     queue,
 			 pixman_fixed_24_8_t y_value,
 			 int                 edge_idx)
 {
@@ -871,7 +884,7 @@ event_queue_insert_dead (event_queue_t **    queue,
 }
 
 static void
-event_queue_insert_clip (event_queue_t **    queue,
+event_queue_insert_clip (event_queue_t *     queue,
 			 pixman_fixed_24_8_t y_value,
 			 int		     dir)
 {
@@ -882,7 +895,7 @@ event_queue_insert_clip (event_queue_t **    queue,
 }
 
 static void
-event_queue_insert_replace (event_queue_t **    queue,
+event_queue_insert_replace (event_queue_t *     queue,
 			    pixman_fixed_24_8_t	y_value,
 			    int			edge_idx,
 			    pixman_fixed_24_8_t bottom)
@@ -897,80 +910,17 @@ event_queue_insert_replace (event_queue_t **    queue,
 }
 
 static void
-event_queue_insert_general (event_queue_t **queue, pixman_fixed_24_8_t y_value)
+event_queue_insert_general (event_queue_t *queue, pixman_fixed_24_8_t y_value)
 {
     event_queue_insert (queue, GENERAL, y_value);
 }
 
-static noinline void
-event_queue_pop (event_queue_t *queue)
-{
-    event_key_t *kchild, *kend, tmp;
-    event_key_t *qend, *qbegin, *key;
-
-    free_event (queue->events[0].event);
-
-    queue->events[0] = queue->events[--queue->n];
-
-    qend = &(queue->events[queue->n]);
-    key = qbegin = &queue->events[0];
-    for (;;)
-    {
-	event_key_t *min_child;
-	pixman_fixed_24_8_t minv;
-
-	kchild = &(queue->events[get_child (key - qbegin, 0)]);
-	kend = kchild + FAN_OUT;
-	if (kend > qend)
-	    kend = qend;
-
-	min_child = key;
-	minv = key->y_value;
-	while (kchild < kend)
-	{
-	    pixman_fixed_24_8_t t;
-
-	    if ((t = kchild->y_value) < minv)
-	    {
-		min_child = kchild;
-		minv = t;
-	    }
-	    kchild++;
-	}
-
-	if (min_child == key)
-	    break;
-
-	tmp = *min_child;
-	*min_child = *key;
-	*key = tmp;
-
-	key = min_child;
-    }
-}
-
-static const event_t *
-event_queue_peek (event_queue_t *queue)
+const event_t *
+event_queue_peek (event_queue_t *event_queue)
 {
-    if (queue->n)
-	return queue->events[0].event;
-    else
-	return NULL;
-}
+    bucket_t *bucket = event_queue->buckets [event_queue->min_bucket];
 
-static void
-dump_queue (event_queue_t *queue)
-{
-    int i;
-    char *n[] = { "new", "replace", "dead", "general" };
-
-    for (i = 0; i < queue->n; ++i)
-    {
-	event_key_t *key = &(queue->events[i]);
-
-	printf ("[%s %d %d] ", n[key->event->common.type], y_value (key), get_parent (i));
-    }
-    printf ("\n");
+    return bucket->events[bucket->minimum].event;
 }
 
 static pixman_bool_t
@@ -982,7 +932,8 @@ trap_iter_init (trap_iter_t *iter,
     int i;
     pixman_fixed_24_8_t clip_top, clip_bottom;
 
-    iter->queue = NULL;
+    /* FIXME: check malloc return */
+    iter->queue = event_queue_create();
     if (!(iter->strip = malloc (sizeof (trap_strip_t))))
 	return FALSE;
 
@@ -1007,18 +958,18 @@ trap_iter_init (trap_iter_t *iter,
 	{
 	    if (segment->line.p1.x <= (x1 << 8) && segment->line.p2.x <= (x1 << 8))
 	    {
-		event_queue_insert_clip (&iter->queue, top, segment->dir);
-		event_queue_insert_clip (&iter->queue, bottom, - segment->dir);
+		event_queue_insert_clip (iter->queue, top, segment->dir);
+		event_queue_insert_clip (iter->queue, bottom, - segment->dir);
 	    }
 	    else
 	    {
-		event_queue_insert_new (&iter->queue, top, segment);
+		event_queue_insert_new (iter->queue, top, segment);
 	    }
 	}
     }
 
     event_queue_insert_general (
-	&iter->queue, (y2 << 8) | strategy->y_frac_first);
+	iter->queue, (y2 << 8) | strategy->y_frac_first);
 
     iter->x1 = x1 << 8;
     iter->x2 = x2 << 8;
@@ -1044,7 +995,7 @@ static void
 trap_iter_fini (trap_iter_t *iter)
 {
     free (iter->strip);
-    free (iter->queue);
+    event_queue_destroy (iter->queue);
 }
 
 static force_inline int32_t
@@ -1228,10 +1179,10 @@ check_intersection (trap_iter_t *iter, edge_t *this, edge_t *prev)
 	/* These can fail due to OOM, but if they do, it will simply
 	 * cause misrendering, not crashes.
 	 */
-	event_queue_insert_replace (&iter->queue, intersect,
+	event_queue_insert_replace (iter->queue, intersect,
 				    prev - strip->edges,
 				    prev->bottom);
-	event_queue_insert_replace (&iter->queue, intersect,
+	event_queue_insert_replace (iter->queue, intersect,
 				    this - strip->edges,
 				    this->bottom);
 
@@ -1350,13 +1301,13 @@ add_regular_edge (trap_iter_t *iter,
 	list_append (iter->strip, edge);
 
 	dead = sample_ceil_y (bottom, iter->strategy);
-	event_queue_insert_dead (&iter->queue, dead, edge - iter->strip->edges);
+	event_queue_insert_dead (iter->queue, dead, edge - iter->strip->edges);
 
 	return FALSE;
     }
     else
     {
-	event_queue_insert_new (&iter->queue, top, segment);
+	event_queue_insert_new (iter->queue, top, segment);
 
 	return TRUE;
     }
@@ -1375,10 +1326,10 @@ add_clip_edge (trap_iter_t *iter,
     if (top <= yi)
 	iter->strip->initial += dir;
     else
-	event_queue_insert_clip (&iter->queue, top, dir);
+	event_queue_insert_clip (iter->queue, top, dir);
 
     bottom = sample_ceil_y (bottom, iter->strategy);
-    event_queue_insert_clip (&iter->queue, bottom, - dir);
+    event_queue_insert_clip (iter->queue, bottom, - dir);
 }
 
 static void
@@ -1431,6 +1382,37 @@ handle_new_edge (trap_iter_t *iter, const event_t *event)
     }
 }
 
+static bucket_t *
+event_queue_get_min_bucket (event_queue_t *event_queue)
+{
+    bucket_t *bucket = event_queue->buckets [event_queue->min_bucket];
+    int i;
+
+    event_queue->buckets [event_queue->min_bucket] = event_queue->aux_bucket;
+
+    for (i = event_queue->min_bucket + 1; i < 33; ++i)
+    {
+	bucket_t *b = event_queue->buckets[i];
+
+	if (b->n_entries)
+	    break;
+    }
+    event_queue->min_bucket = i;
+
+    event_queue->last_del = bucket->events[bucket->minimum].y_value;
+
+    return bucket;
+}
+
+static void
+event_queue_put_min_bucket (event_queue_t *event_queue, bucket_t *bucket)
+{
+    bucket->n_entries = 0;
+    bucket->minimum = -1;
+
+    event_queue->aux_bucket = bucket;
+}
+
 static noinline trap_strip_t *
 trap_iter_get_strip (trap_iter_t *iter)
 {
@@ -1444,53 +1426,71 @@ trap_iter_get_strip (trap_iter_t *iter)
      */
     while ((event = event_queue_peek (iter->queue))->common.y_value == iter->yi)
     {
+	bucket_t *bucket = event_queue_get_min_bucket (iter->queue);
+	pixman_fixed_24_8_t m = bucket->events[bucket->minimum].y_value;
 	pixman_bool_t need_update = FALSE;
-	do
-	{
-	    switch (event->common.type)
-	    {
-	    case NEW:
-		handle_new_edge (iter, event);
-		need_update = TRUE;
-		break;
-
-	    case REPLACE:
-		edge = &(iter->strip->edges[event->replace.edge_idx]);
-		edge->bottom = event->replace.bottom;
-		need_update = TRUE;
-		break;
+	int i;
 
-	    case CLIP:
-		iter->strip->initial += event->clip.dir;
-		break;
+	for (i = 0; i < bucket->n_entries; ++i)
+	{
+	    event_key_t *key = &(bucket->events[i]);
 
-	    case DEAD:
-		edge = &iter->strip->edges[event->dead.edge_idx];
+	    event = key->event;
 
-		list_remove (iter->strip, edge);
-		free_edge (iter->strip, edge);
-		need_update = TRUE;
-		break;
+	    if (key->y_value == m)
+	    {
+		switch (event->common.type)
+		{
+		case NEW:
+		    handle_new_edge (iter, event);
+		    need_update = TRUE;
+		    break;
+
+		case REPLACE:
+		    edge = &(iter->strip->edges[event->replace.edge_idx]);
+		    edge->bottom = event->replace.bottom;
+		    need_update = TRUE;
+		    break;
+
+		case CLIP:
+		    iter->strip->initial += event->clip.dir;
+		    break;
+
+		case DEAD:
+		    edge = &iter->strip->edges[event->dead.edge_idx];
+
+		    list_remove (iter->strip, edge);
+		    free_edge (iter->strip, edge);
+		    need_update = TRUE;
+		    break;
+
+		case GENERAL:
+		    break;
+		}
 
-	    case GENERAL:
-		break;
+		free_event ((event_t *)event);
+	    }
+	    else
+	    {
+		event_queue_insert_internal (
+		    iter->queue, key->y_value, key->event);
 	    }
-	    event_queue_pop (iter->queue);
 	}
-	while ((event = event_queue_peek (iter->queue))->common.y_value == iter->yi);
+
+	event_queue_put_min_bucket (iter->queue, bucket);
 
 	if (need_update)
 	    sort_edges (iter);
     }
 
     iter->strip->top = iter->yi;
+    iter->yi = event->common.y_value;
+    iter->strip->bottom = event->common.y_value;
 
+#if 0
     /* Compress clip events */
     do
     {
-	iter->strip->bottom = event->common.y_value;
-	iter->yi = event->common.y_value;
-
 	dir = 0;
 	while ((event = event_queue_peek (iter->queue))->common.type == CLIP &&
 	       event->common.y_value == iter->yi)
@@ -1502,7 +1502,8 @@ trap_iter_get_strip (trap_iter_t *iter)
     while (dir == 0 && event->common.y_value > iter->yi);
 
     if (dir != 0)
-	event_queue_insert_clip (&iter->queue, iter->yi, dir);
+	event_queue_insert_clip (iter->queue, iter->yi, dir);
+#endif
 
     return iter->strip;
 }