Use the new lists to maintain the fast path cache.lists

Previously, the fast path cache would be maintained as an array, which
meant that some amount of copying would be necessary whenever a fast
path was moved to the front of the array.

This patch changes the cache to use a doubly linked most-recently-used
list of fast paths, which avoids this copying.

With move-to-front taking constant time, the number of cached fast
paths can be increased to 32.

1 files changed, 114 insertions, 0 deletions

diff --git a/pixman/pixman.c b/pixman/pixman.c
index 8fb53568..b2747939 100644
--- a/pixman/pixman.c
+++ b/pixman/pixman.c
@@ -335,6 +335,120 @@ pixman_compute_composite_region32 (pixman_region32_t * region,
     return TRUE;
 }
 
+#define N_CACHED_FAST_PATHS 32
+
+typedef struct
+{
+    pixman_implementation_t *	imp;
+    pixman_fast_path_t		fast_path;
+    pixman_link_t		mru_link;
+} cache_item_t;
+
+typedef struct
+{
+    cache_item_t	items[N_CACHED_FAST_PATHS];
+    pixman_list_t	mru;
+} cache_t;
+
+PIXMAN_DEFINE_THREAD_LOCAL (cache_t, fast_path_cache);
+
+static force_inline pixman_bool_t
+lookup_composite_function (pixman_op_t			op,
+			   pixman_format_code_t		src_format,
+			   uint32_t			src_flags,
+			   pixman_format_code_t		mask_format,
+			   uint32_t			mask_flags,
+			   pixman_format_code_t		dest_format,
+			   uint32_t			dest_flags,
+			   pixman_implementation_t    **out_imp,
+			   pixman_composite_func_t     *out_func)
+{
+    pixman_implementation_t *imp;
+    cache_t *cache;
+    pixman_link_t *link;
+    cache_item_t *item;
+
+    cache = PIXMAN_GET_THREAD_LOCAL (fast_path_cache);
+
+    if (!cache->mru.head)
+    {
+	int i;
+
+	pixman_list_init (&cache->mru);
+	for (i = 0; i < N_CACHED_FAST_PATHS; ++i)
+	    pixman_list_prepend (&cache->mru, &cache->items[i].mru_link);
+    }
+
+    /* Check cache for fast paths */
+    PIXMAN_LIST_FOREACH (&cache->mru, link)
+    {
+	item = CONTAINER_OF (cache_item_t, mru_link, link);
+
+	if (!item->fast_path.func)
+	    break;
+
+	/* Note that we check for equality here, not whether
+	 * the cached fast path matches. This is to prevent
+	 * us from selecting an overly general fast path
+	 * when a more specific one would work.
+	 */
+	if (item->fast_path.op == op			&&
+	    item->fast_path.src_format == src_format	&&
+	    item->fast_path.mask_format == mask_format	&&
+	    item->fast_path.dest_format == dest_format	&&
+	    item->fast_path.src_flags == src_flags	&&
+	    item->fast_path.mask_flags == mask_flags	&&
+	    item->fast_path.dest_flags == dest_flags)
+	{
+	    *out_imp = item->imp;
+	    *out_func = item->fast_path.func;
+
+	    pixman_list_move_to_front (&cache->mru, &item->mru_link);
+	    return TRUE;
+	}
+    }
+
+    /* Not found in cache, do the full search */
+    for (imp = get_implementation (); imp != NULL; imp = imp->delegate)
+    {
+	const pixman_fast_path_t *info = imp->fast_paths;
+
+	while (info->op != PIXMAN_OP_NONE)
+	{
+	    if ((info->op == op || info->op == PIXMAN_OP_any)		&&
+		((info->src_format == src_format) ||
+		 (info->src_format == PIXMAN_any))			&&
+		((info->mask_format == mask_format) ||
+		 (info->mask_format == PIXMAN_any))			&&
+		((info->dest_format == dest_format) ||
+		 (info->dest_format == PIXMAN_any))			&&
+		(info->src_flags & src_flags) == info->src_flags	&&
+		(info->mask_flags & mask_flags) == info->mask_flags	&&
+		(info->dest_flags & dest_flags) == info->dest_flags)
+	    {
+		/* Evict least recently used */
+		item = CONTAINER_OF (cache_item_t, mru_link, cache->mru.tail);
+
+		item->imp = *out_imp = imp;
+		item->fast_path.func = *out_func = info->func;
+		item->fast_path.op = op;
+		item->fast_path.src_format = src_format;
+		item->fast_path.src_flags = src_flags;
+		item->fast_path.mask_format = mask_format;
+		item->fast_path.mask_flags = mask_flags;
+		item->fast_path.dest_format = dest_format;
+		item->fast_path.dest_flags = dest_flags;
+
+		pixman_list_move_to_front (&cache->mru, &item->mru_link);
+		return TRUE;
+	    }
+
+	    ++info;
+	}
+    }
+    return FALSE;
+}
+
 typedef struct
 {
     pixman_fixed_48_16_t	x1;