[RFC PATCH] randr: crtc cursor confinement

[Mikhail Gusarov]

Twas brillig at 14:36:49 12.10.2010 UTC-04 when ajax at redhat.com did gyre and gimble:

 AJ> +/*
 AJ> + * This isn't really multiplication, but we don't need it to be.  All
 AJ> + * we need is a boolean for connectivity, not an integer for number of
 AJ> + * paths.  As a result we can scale to gratuitously large n without
 AJ> + * worrying about integer overflow.
 AJ> + */
 AJ> +static Bool
 AJ> +matrix_pseudomultiply(char *left, const char *right, int n)
 AJ> +{
 AJ> +    int i, j, k;
 AJ> +    char *res = calloc(1, n * n);
 AJ> +
 AJ> +    if (!res)
 AJ> +        return FALSE;
 AJ> +
 AJ> +    for (i = 0; i < n; i++)
 AJ> +        for (j = 0; j < n; j++)
 AJ> +            for (k = 0; k < n; k++)
 AJ> +                res[i*n + j] |= left[i*n + k] && right[k*n + j];
 AJ> +
 AJ> +    memcpy(left, res, n * n);
 AJ> +
 AJ> +    free(res);
 AJ> +
 AJ> +    return TRUE;
 AJ> +}
 AJ> +
 AJ> +static void
 AJ> +RRComputeContiguity (ScreenPtr pScreen)
 AJ> +{
 AJ> +    rrScrPriv(pScreen);
 AJ> +    Bool discontiguous = TRUE;
 AJ> +    int i, j, n = pScrPriv->numCrtcs;
 AJ> +    RRCrtcPtr a, b;
 AJ> +    char *matrix = NULL, *m = NULL;
 AJ> +
 AJ> +    matrix = calloc(1, n*n);
 AJ> +    m = calloc(1, n*n);
 AJ> +    if (!matrix || !m)
 AJ> +        goto out;
 AJ> +
 AJ> +    /* compute adjacency matrix; everything is adjacent with itself */
 AJ> +    for (i = 0; i < n; i++) {
 AJ> +        a = pScrPriv->crtcs[i];
 AJ> +
 AJ> +        if (!a->mode)
 AJ> +            continue;
 AJ> +
 AJ> +        for (j = 0; j < n; j++) {
 AJ> +            b = pScrPriv->crtcs[j];
 AJ> +
 AJ> +            if (!b->mode)
 AJ> +                continue;
 AJ> +
 AJ> +            if (a == b || crtcs_adjacent(a, b))
 AJ> +                matrix[i*n + j] = 1;
 AJ> +        }
 AJ> +    }
 AJ> +
 AJ> +    memcpy(m, matrix, n*n);
 AJ> +
 AJ> +    /* raise it to the n-1th; finds connected paths */
 AJ> +    for (i = 0; i < n-1; i++)
 AJ> +        if (!matrix_pseudomultiply(m, matrix, n))
 AJ> +            goto out;
 AJ> +
 AJ> +    /* check for connectivity */
 AJ> +    for (i = 0; i < n; i++)
 AJ> +        if (pScrPriv->crtcs[i]->mode && !m[i])
 AJ> +            goto out;
 AJ> +
 AJ> +    discontiguous = FALSE;
 AJ> +
 AJ> +out:
 AJ> +    free(matrix);
 AJ> +    free(m);
 AJ> +    pScrPriv->discontiguous = discontiguous;
 AJ> +}

Isn't it too indirect? Just scratched the following (not even
compile-tested). If recursion is a no-no due to systems with numCrtcs >
100k, then recursion is easily rewritten to queue.

/* Depth-first search and mark all CRTCs reachable from cur */
static void
dfs (rrScrPrivPtr pScrPriv, int *reachable, int cur)
{
    int i;
    reachable[cur] = TRUE;
    for (i = 0; i < pScrPriv->numCrtcs; ++i) {
        if (reachable[i])
            continue;
        if (crtcs_adjacent(pScrPriv->crtcs[cur], pScrPriv->crtcs[i]))
            dfs(pScrPriv, reachable, i);
    }
}

static void
RRComputeContiguity (ScreenPtr pScreen)
{
    rrScrPriv(pScreen);
    Bool discontiguous = TRUE;
    int i, n = pScrPriv->numCrtcs;

    int *reachable = calloc(1, n);
    if (!reachable)
        goto out;

    /* Find first enabled CRTC and start search for reachable CRTCs from it */
    for (i = 0; i < n; ++i)
        if (pScrPriv->crtcs[i]->mode) {
            dfs(pScrPriv, reachable, i);
            break;
        }

    /* Check that all enabled CRTCs were marked as reachable */
    for (i = 0; i < n; ++i)
        if (pScrPriv->crtcs[i]->mode && !reachable[i])
            goto out;

    discontiguous = FALSE;

out:
    free(reachable);
    pScrPriv->discontiguous = discontiguous;
}

-- 
  http://fossarchy.blogspot.com/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 489 bytes
Desc: not available
URL: <http://lists.x.org/archives/xorg-devel/attachments/20101012/8a903471/attachment.pgp>