xserver libX11 libxtrans mesa pixman xkeyboard-config git update 27 Apr 2011

4 files changed, 2273 insertions, 2207 deletions

diff --git a/xorg-server/dix/devices.c b/xorg-server/dix/devices.c
index 534931c3e..3f46ad6fb 100644
--- a/xorg-server/dix/devices.c
+++ b/xorg-server/dix/devices.c
@@ -1221,13 +1221,46 @@ InitButtonClassDeviceStruct(DeviceIntPtr dev, int numButtons, Atom* labels,
     return TRUE;
 }
 
+/**
+ * Allocate a valuator class and set up the pointers for the axis values
+ * appropriately.
+ *
+ * @param src If non-NULL, the memory is reallocated from src. If NULL, the
+ * memory is calloc'd.
+ * @parma numAxes Number of axes to allocate.
+ * @return The allocated valuator struct.
+ */
+ValuatorClassPtr
+AllocValuatorClass(ValuatorClassPtr src, int numAxes)
+{
+    ValuatorClassPtr v;
+    /* force alignment with double */
+    union align_u { ValuatorClassRec valc; double d; } *align;
+    int size;
+
+    size = sizeof(union align_u) + numAxes * (sizeof(double) + sizeof(AxisInfo));
+    align = (union align_u *) realloc(src, size);
+
+    if (!align)
+        return NULL;
+
+    if (!src)
+        memset(align, 0, size);
+
+    v = &align->valc;
+    v->numAxes = numAxes;
+    v->axisVal = (double*)(align + 1);
+    v->axes = (AxisInfoPtr)(v->axisVal + numAxes);
+
+    return v;
+}
+
 Bool
 InitValuatorClassDeviceStruct(DeviceIntPtr dev, int numAxes, Atom *labels,
                               int numMotionEvents, int mode)
 {
     int i;
     ValuatorClassPtr valc;
-    union align_u { ValuatorClassRec valc; double d; } *align;
 
     if (!dev)
         return FALSE;
@@ -1240,13 +1273,10 @@ InitValuatorClassDeviceStruct(DeviceIntPtr dev, int numAxes, Atom *labels,
         numAxes = MAX_VALUATORS;
     }
 
-    align = (union align_u *) calloc(1, sizeof(union align_u) +
-				     numAxes * sizeof(double) +
-				     numAxes * sizeof(AxisInfo));
-    if (!align)
-	return FALSE;
+    valc = AllocValuatorClass(NULL, numAxes);
+    if (!valc)
+        return FALSE;
 
-    valc = &align->valc;
     valc->sourceid = dev->id;
     valc->motion = NULL;
     valc->first_motion = 0;
@@ -1254,9 +1284,6 @@ InitValuatorClassDeviceStruct(DeviceIntPtr dev, int numAxes, Atom *labels,
 
     valc->numMotionEvents = numMotionEvents;
     valc->motionHintWindow = NullWindow;
-    valc->numAxes = numAxes;
-    valc->axisVal = (double *)(align + 1);
-    valc->axes = (AxisInfoPtr)(valc->axisVal + numAxes);
 
     if (mode & OutOfProximity)
         InitProximityClassDeviceStruct(dev);
@@ -2365,7 +2392,7 @@ ReleaseButtonsAndKeys(DeviceIntPtr dev)
     {
         if (BitIsOn(k->down, i))
         {
-            nevents = GetKeyboardEvents(eventlist, dev, KeyRelease, i);
+            nevents = GetKeyboardEvents(eventlist, dev, KeyRelease, i, NULL);
             for (j = 0; j < nevents; j++)
                 mieqProcessDeviceEvent(dev, (InternalEvent*)(eventlist+j)->event, NULL);
         }
diff --git a/xorg-server/dix/getevents.c b/xorg-server/dix/getevents.c
index 644b3887e..0fa8046df 100644
--- a/xorg-server/dix/getevents.c
+++ b/xorg-server/dix/getevents.c
@@ -616,8 +616,8 @@ updateMotionHistory(DeviceIntPtr pDev, CARD32 ms, ValuatorMask *mask,
 
 
 /**
- * Returns the maximum number of events GetKeyboardEvents,
- * GetKeyboardValuatorEvents, and GetPointerEvents will ever return.
+ * Returns the maximum number of events GetKeyboardEvents
+ * and GetPointerEvents will ever return.
  *
  * This MUST be absolutely constant, from init until exit.
  */
@@ -926,19 +926,6 @@ updateHistory(DeviceIntPtr dev, ValuatorMask *mask, CARD32 ms)
 }
 
 /**
- * Convenience wrapper around GetKeyboardValuatorEvents, that takes no
- * valuators.
- */
-int
-GetKeyboardEvents(EventList *events, DeviceIntPtr pDev, int type, int key_code) {
-    ValuatorMask mask;
-
-    valuator_mask_zero(&mask);
-    return GetKeyboardValuatorEvents(events, pDev, type, key_code, &mask);
-}
-
-
-/**
  * Returns a set of InternalEvents for KeyPress/KeyRelease, optionally
  * also with valuator events.
  *
@@ -947,8 +934,8 @@ GetKeyboardEvents(EventList *events, DeviceIntPtr pDev, int type, int key_code)
  * place via GetMaximumEventsNum(), and for freeing it.
  */
 int
-GetKeyboardValuatorEvents(EventList *events, DeviceIntPtr pDev, int type,
-                          int key_code, const ValuatorMask *mask_in) {
+GetKeyboardEvents(EventList *events, DeviceIntPtr pDev, int type,
+                  int key_code, const ValuatorMask *mask_in) {
     int num_events = 0;
     CARD32 ms = 0;
     DeviceEvent *event;
diff --git a/xorg-server/dix/ptrveloc.c b/xorg-server/dix/ptrveloc.c
index e95d804c2..dfccf1581 100644
--- a/xorg-server/dix/ptrveloc.c
+++ b/xorg-server/dix/ptrveloc.c
@@ -1,1216 +1,1268 @@
-/*

- *

- * Copyright © 2006-2009 Simon Thum             simon dot thum at gmx dot de

- *

- * Permission is hereby granted, free of charge, to any person obtaining a

- * copy of this software and associated documentation files (the "Software"),

- * to deal in the Software without restriction, including without limitation

- * the rights to use, copy, modify, merge, publish, distribute, sublicense,

- * and/or sell copies of the Software, and to permit persons to whom the

- * Software is furnished to do so, subject to the following conditions:

- *

- * The above copyright notice and this permission notice (including the next

- * paragraph) shall be included in all copies or substantial portions of the

- * Software.

- *

- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

- * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

- * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL

- * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

- * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING

- * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER

- * DEALINGS IN THE SOFTWARE.

- */

-

-#ifdef HAVE_DIX_CONFIG_H

-#include <dix-config.h>

-#endif

-

-#include <math.h>

-#include <ptrveloc.h>

-#include <exevents.h>

-#include <X11/Xatom.h>

-#include <os.h>

-

-#include <xserver-properties.h>

-

-/*****************************************************************************

- * Predictable pointer acceleration

- *

- * 2006-2009 by Simon Thum (simon [dot] thum [at] gmx de)

- *

- * Serves 3 complementary functions:

- * 1) provide a sophisticated ballistic velocity estimate to improve

- *    the relation between velocity (of the device) and acceleration

- * 2) make arbitrary acceleration profiles possible

- * 3) decelerate by two means (constant and adaptive) if enabled

- *

- * Important concepts are the

- *

- * - Scheme

- *      which selects the basic algorithm

- *      (see devices.c/InitPointerAccelerationScheme)

- * - Profile

- *      which returns an acceleration

- *      for a given velocity

- *

- *  The profile can be selected by the user at runtime.

- *  The classic profile is intended to cleanly perform old-style

- *  function selection (threshold =/!= 0)

- *

- ****************************************************************************/

-

-/* fwds */

-int

-SetAccelerationProfile(DeviceVelocityPtr vel, int profile_num);

-static float

-SimpleSmoothProfile(DeviceIntPtr dev, DeviceVelocityPtr vel, float velocity,

-                    float threshold, float acc);

-static PointerAccelerationProfileFunc

-GetAccelerationProfile(DeviceVelocityPtr vel, int profile_num);

-static BOOL

-InitializePredictableAccelerationProperties(DeviceIntPtr,

-                                            DeviceVelocityPtr,

-                                            PredictableAccelSchemePtr);

-static BOOL

-DeletePredictableAccelerationProperties(DeviceIntPtr,

-                                        PredictableAccelSchemePtr);

-

-/*#define PTRACCEL_DEBUGGING*/

-

-#ifdef PTRACCEL_DEBUGGING

-#define DebugAccelF ErrorF

-#else

-#define DebugAccelF(...) /* */

-#endif

-

-/********************************

- *  Init/Uninit

- *******************************/

-

-/* some int which is not a profile number */

-#define PROFILE_UNINITIALIZE (-100)

-

-/**

- * Init DeviceVelocity struct so it should match the average case

- */

-void

-InitVelocityData(DeviceVelocityPtr vel)

-{

-    memset(vel, 0, sizeof(DeviceVelocityRec));

-

-    vel->corr_mul = 10.0;      /* dots per 10 milisecond should be usable */

-    vel->const_acceleration = 1.0;   /* no acceleration/deceleration  */

-    vel->reset_time = 300;

-    vel->use_softening = 1;

-    vel->min_acceleration = 1.0; /* don't decelerate */

-    vel->max_rel_diff = 0.2;

-    vel->max_diff = 1.0;

-    vel->initial_range = 2;

-    vel->average_accel = TRUE;

-    SetAccelerationProfile(vel, AccelProfileClassic);

-    InitTrackers(vel, 16);

-}

-

-

-/**

- * Clean up DeviceVelocityRec

- */

-void

-FreeVelocityData(DeviceVelocityPtr vel){

-    free(vel->tracker);

-    SetAccelerationProfile(vel, PROFILE_UNINITIALIZE);

-}

-

-

-/**

- * Init predictable scheme

- */

-Bool

-InitPredictableAccelerationScheme(DeviceIntPtr dev,

-                                  ValuatorAccelerationPtr protoScheme) {

-    DeviceVelocityPtr vel;

-    ValuatorAccelerationRec scheme;

-    PredictableAccelSchemePtr schemeData;

-    scheme = *protoScheme;

-    vel = calloc(1, sizeof(DeviceVelocityRec));

-    schemeData = calloc(1, sizeof(PredictableAccelSchemeRec));

-    if (!vel || !schemeData)

-        return FALSE;

-    InitVelocityData(vel);

-    schemeData->vel = vel;

-    scheme.accelData = schemeData;

-    if (!InitializePredictableAccelerationProperties(dev, vel, schemeData))

-        return FALSE;

-    /* all fine, assign scheme to device */

-    dev->valuator->accelScheme = scheme;

-    return TRUE;

-}

-

-

-/**

- *  Uninit scheme

- */

-void

-AccelerationDefaultCleanup(DeviceIntPtr dev)

-{

-    DeviceVelocityPtr vel = GetDevicePredictableAccelData(dev);

-    if (vel) {

-        /* the proper guarantee would be that we're not inside of

-         * AccelSchemeProc(), but that seems impossible. Schemes don't get

-         * switched often anyway.

-         */

-        OsBlockSignals();

-        dev->valuator->accelScheme.AccelSchemeProc = NULL;

-        FreeVelocityData(vel);

-        free(vel);

-        DeletePredictableAccelerationProperties(dev,

-            (PredictableAccelSchemePtr) dev->valuator->accelScheme.accelData);

-        free(dev->valuator->accelScheme.accelData);

-        dev->valuator->accelScheme.accelData = NULL;

-        OsReleaseSignals();

-    }

-}

-

-

-/*************************

- * Input property support

- ************************/

-

-/**

- * choose profile

- */

-static int

-AccelSetProfileProperty(DeviceIntPtr dev, Atom atom,

-                        XIPropertyValuePtr val, BOOL checkOnly)

-{

-    DeviceVelocityPtr vel;

-    int profile, *ptr = &profile;

-    int rc;

-    int nelem = 1;

-

-    if (atom != XIGetKnownProperty(ACCEL_PROP_PROFILE_NUMBER))

-        return Success;

-

-    vel = GetDevicePredictableAccelData(dev);

-    if (!vel)

-        return BadValue;

-    rc = XIPropToInt(val, &nelem, &ptr);

-

-    if(checkOnly)

-    {

-        if (rc)

-            return rc;

-

-        if (GetAccelerationProfile(vel, profile) == NULL)

-            return BadValue;

-    } else

-	SetAccelerationProfile(vel, profile);

-

-    return Success;

-}

-

-static long

-AccelInitProfileProperty(DeviceIntPtr dev, DeviceVelocityPtr vel)

-{

-    int profile = vel->statistics.profile_number;

-    Atom prop_profile_number = XIGetKnownProperty(ACCEL_PROP_PROFILE_NUMBER);

-

-    XIChangeDeviceProperty(dev, prop_profile_number, XA_INTEGER, 32,

-                           PropModeReplace, 1, &profile, FALSE);

-    XISetDevicePropertyDeletable(dev, prop_profile_number, FALSE);

-    return XIRegisterPropertyHandler(dev, AccelSetProfileProperty, NULL, NULL);

-}

-

-/**

- * constant deceleration

- */

-static int

-AccelSetDecelProperty(DeviceIntPtr dev, Atom atom,

-                      XIPropertyValuePtr val, BOOL checkOnly)

-{

-    DeviceVelocityPtr vel;

-    float v, *ptr = &v;

-    int rc;

-    int nelem = 1;

-

-    if (atom != XIGetKnownProperty(ACCEL_PROP_CONSTANT_DECELERATION))

-        return Success;

-

-    vel = GetDevicePredictableAccelData(dev);

-    if (!vel)

-        return BadValue;

-    rc = XIPropToFloat(val, &nelem, &ptr);

-

-    if(checkOnly)

-    {

-        if (rc)

-            return rc;

-	return (v >= 1.0f) ? Success : BadValue;

-    }

-

-    if(v >= 1.0f)

-	vel->const_acceleration = 1/v;

-

-    return Success;

-}

-

-static long

-AccelInitDecelProperty(DeviceIntPtr dev, DeviceVelocityPtr vel)

-{

-    float fval = 1.0/vel->const_acceleration;

-    Atom prop_const_decel = XIGetKnownProperty(ACCEL_PROP_CONSTANT_DECELERATION);

-    XIChangeDeviceProperty(dev, prop_const_decel,

-                           XIGetKnownProperty(XATOM_FLOAT), 32,

-                           PropModeReplace, 1, &fval, FALSE);

-    XISetDevicePropertyDeletable(dev, prop_const_decel, FALSE);

-    return XIRegisterPropertyHandler(dev, AccelSetDecelProperty, NULL, NULL);

-}

-

-

-/**

- * adaptive deceleration

- */

-static int

-AccelSetAdaptDecelProperty(DeviceIntPtr dev, Atom atom,

-                           XIPropertyValuePtr val, BOOL checkOnly)

-{

-    DeviceVelocityPtr veloc;

-    float v, *ptr = &v;

-    int rc;

-    int nelem = 1;

-

-    if (atom != XIGetKnownProperty(ACCEL_PROP_ADAPTIVE_DECELERATION))

-        return Success;

-

-    veloc = GetDevicePredictableAccelData(dev);

-    if (!veloc)

-        return BadValue;

-    rc = XIPropToFloat(val, &nelem, &ptr);

-

-    if(checkOnly)

-    {

-        if (rc)

-            return rc;

-	return (v >= 1.0f) ? Success : BadValue;

-    }

-

-    if(v >= 1.0f)

-	veloc->min_acceleration = 1/v;

-

-    return Success;

-}

-

-static long

-AccelInitAdaptDecelProperty(DeviceIntPtr dev, DeviceVelocityPtr vel)

-{

-    float fval = 1.0/vel->min_acceleration;

-    Atom prop_adapt_decel = XIGetKnownProperty(ACCEL_PROP_ADAPTIVE_DECELERATION);

-

-    XIChangeDeviceProperty(dev, prop_adapt_decel, XIGetKnownProperty(XATOM_FLOAT), 32,

-                           PropModeReplace, 1, &fval, FALSE);

-    XISetDevicePropertyDeletable(dev, prop_adapt_decel, FALSE);

-    return XIRegisterPropertyHandler(dev, AccelSetAdaptDecelProperty, NULL, NULL);

-}

-

-

-/**

- * velocity scaling

- */

-static int

-AccelSetScaleProperty(DeviceIntPtr dev, Atom atom,

-                      XIPropertyValuePtr val, BOOL checkOnly)

-{

-    DeviceVelocityPtr vel;

-    float v, *ptr = &v;

-    int rc;

-    int nelem = 1;

-

-    if (atom != XIGetKnownProperty(ACCEL_PROP_VELOCITY_SCALING))

-        return Success;

-

-    vel = GetDevicePredictableAccelData(dev);

-    if (!vel)

-        return BadValue;

-    rc = XIPropToFloat(val, &nelem, &ptr);

-

-    if (checkOnly)

-    {

-        if (rc)

-            return rc;

-

-        return (v > 0) ? Success : BadValue;

-    }

-

-    if(v > 0)

-	vel->corr_mul = v;

-

-    return Success;

-}

-

-static long

-AccelInitScaleProperty(DeviceIntPtr dev, DeviceVelocityPtr vel)

-{

-    float fval = vel->corr_mul;

-    Atom prop_velo_scale = XIGetKnownProperty(ACCEL_PROP_VELOCITY_SCALING);

-

-    XIChangeDeviceProperty(dev, prop_velo_scale, XIGetKnownProperty(XATOM_FLOAT), 32,

-                           PropModeReplace, 1, &fval, FALSE);

-    XISetDevicePropertyDeletable(dev, prop_velo_scale, FALSE);

-    return XIRegisterPropertyHandler(dev, AccelSetScaleProperty, NULL, NULL);

-}

-

-static BOOL

-InitializePredictableAccelerationProperties(

-    DeviceIntPtr dev,

-    DeviceVelocityPtr  vel,

-    PredictableAccelSchemePtr schemeData)

-{

-    int num_handlers = 4;

-    if(!vel)

-        return FALSE;

-

-    schemeData->prop_handlers = calloc(num_handlers, sizeof(long));

-    if (!schemeData->prop_handlers)

-        return FALSE;

-    schemeData->num_prop_handlers = num_handlers;

-    schemeData->prop_handlers[0] = AccelInitProfileProperty(dev, vel);

-    schemeData->prop_handlers[1] = AccelInitDecelProperty(dev, vel);

-    schemeData->prop_handlers[2] = AccelInitAdaptDecelProperty(dev, vel);

-    schemeData->prop_handlers[3] = AccelInitScaleProperty(dev, vel);

-

-    return TRUE;

-}

-

-BOOL

-DeletePredictableAccelerationProperties(

-    DeviceIntPtr dev,

-    PredictableAccelSchemePtr scheme)

-{

-    DeviceVelocityPtr vel;

-    Atom prop;

-    int i;

-

-    prop = XIGetKnownProperty(ACCEL_PROP_VELOCITY_SCALING);

-    XIDeleteDeviceProperty(dev, prop, FALSE);

-    prop = XIGetKnownProperty(ACCEL_PROP_ADAPTIVE_DECELERATION);

-    XIDeleteDeviceProperty(dev, prop, FALSE);

-    prop = XIGetKnownProperty(ACCEL_PROP_CONSTANT_DECELERATION);

-    XIDeleteDeviceProperty(dev, prop, FALSE);

-    prop = XIGetKnownProperty(ACCEL_PROP_PROFILE_NUMBER);

-    XIDeleteDeviceProperty(dev, prop, FALSE);

-

-    vel = GetDevicePredictableAccelData(dev);

-    if (vel) {

-        for (i = 0; i < scheme->num_prop_handlers; i++)

-            if (scheme->prop_handlers[i])

-                XIUnregisterPropertyHandler(dev, scheme->prop_handlers[i]);

-    }

-

-    free(scheme->prop_handlers);

-    scheme->prop_handlers = NULL;

-    scheme->num_prop_handlers = 0;

-    return TRUE;

-}

-

-/*********************

- * Tracking logic

- ********************/

-

-void

-InitTrackers(DeviceVelocityPtr vel, int ntracker)

-{

-    if(ntracker < 1){

-	ErrorF("(dix ptracc) invalid number of trackers\n");

-	return;

-    }

-    free(vel->tracker);

-    vel->tracker = (MotionTrackerPtr)calloc(ntracker, sizeof(MotionTracker));

-    vel->num_tracker = ntracker;

-}

-

-/**

- * return a bit field of possible directions.

- * 0 = N, 2 = E, 4 = S, 6 = W, in-between is as you guess.

- * There's no reason against widening to more precise directions (<45 degrees),

- * should it not perform well. All this is needed for is sort out non-linear

- * motion, so precision isn't paramount. However, one should not flag direction

- * too narrow, since it would then cut the linear segment to zero size way too

- * often.

- */

-static int

-DoGetDirection(int dx, int dy){

-    float r;

-    int i1, i2;

-    /* on insignificant mickeys, flag 135 degrees */

-    if(abs(dx) < 2 && abs(dy < 2)){

-	/* first check diagonal cases */

-	if(dx > 0 && dy > 0)

-	    return 4+8+16;

-	if(dx > 0 && dy < 0)

-	    return 1+2+4;

-	if(dx < 0 && dy < 0)

-	    return 1+128+64;

-	if(dx < 0 && dy > 0)

-	    return 16+32+64;

-        /* check axis-aligned directions */

-	if(dx > 0)

-            return 2+4+8; /*E*/

-        if(dx < 0)

-            return 128+64+32; /*W*/

-        if(dy > 0)

-            return 32+16+8; /*S*/

-        if(dy < 0)

-            return 128+1+2; /*N*/

-        return 255; /* shouldn't happen */

-    }

-    /* else, compute angle and set appropriate flags */

-#ifdef _ISOC99_SOURCE

-    r = atan2f(dy, dx);

-#else

-    r = atan2(dy, dx);

-#endif

-    /* find direction. We avoid r to become negative,

-     * since C has no well-defined modulo for such cases. */

-    r = (r+(M_PI*2.5))/(M_PI/4);

-    /* this intends to flag 2 directions (90 degrees),

-     * except on very well-aligned mickeys. */

-    i1 = (int)(r+0.1) % 8;

-    i2 = (int)(r+0.9) % 8;

-    if(i1 < 0 || i1 > 7 || i2 < 0 || i2 > 7)

-	return 255; /* shouldn't happen */

-    return 1 << i1 | 1 << i2;

-}

-

-#define DIRECTION_CACHE_RANGE 5

-#define DIRECTION_CACHE_SIZE (DIRECTION_CACHE_RANGE*2+1)

-

-/* cache DoGetDirection(). */

-static int

-GetDirection(int dx, int dy){

-    static int cache[DIRECTION_CACHE_SIZE][DIRECTION_CACHE_SIZE];

-    int i;

-    if (abs(dx) <= DIRECTION_CACHE_RANGE &&

-	abs(dy) <= DIRECTION_CACHE_RANGE) {

-	/* cacheable */

-	i = cache[DIRECTION_CACHE_RANGE+dx][DIRECTION_CACHE_RANGE+dy];

-	if(i != 0){

-	    return i;

-	}else{

-	    i = DoGetDirection(dx, dy);

-	    cache[DIRECTION_CACHE_RANGE+dx][DIRECTION_CACHE_RANGE+dy] = i;

-	    return i;

-	}

-    }else{

-	/* non-cacheable */

-	return DoGetDirection(dx, dy);

-    }

-}

-

-#undef DIRECTION_CACHE_RANGE

-#undef DIRECTION_CACHE_SIZE

-

-

-/* convert offset (age) to array index */

-#define TRACKER_INDEX(s, d) (((s)->num_tracker + (s)->cur_tracker - (d)) % (s)->num_tracker)

-

-static inline void

-FeedTrackers(DeviceVelocityPtr vel, int dx, int dy, int cur_t)

-{

-    int n;

-    for(n = 0; n < vel->num_tracker; n++){

-	vel->tracker[n].dx += dx;

-	vel->tracker[n].dy += dy;

-    }

-    n = (vel->cur_tracker + 1) % vel->num_tracker;

-    vel->tracker[n].dx = 0;

-    vel->tracker[n].dy = 0;

-    vel->tracker[n].time = cur_t;

-    vel->tracker[n].dir = GetDirection(dx, dy);

-    DebugAccelF("(dix prtacc) motion [dx: %i dy: %i dir:%i diff: %i]\n",

-                dx, dy, vel->tracker[n].dir,

-                cur_t - vel->tracker[vel->cur_tracker].time);

-    vel->cur_tracker = n;

-}

-

-/**

- * calc velocity for given tracker, with

- * velocity scaling.

- * This assumes linear motion.

- */

-static float

-CalcTracker(DeviceVelocityPtr vel, int offset, int cur_t){

-    int index = TRACKER_INDEX(vel, offset);

-    float dist = sqrt(  vel->tracker[index].dx * vel->tracker[index].dx

-                      + vel->tracker[index].dy * vel->tracker[index].dy);

-    int dtime = cur_t - vel->tracker[index].time;

-    if(dtime > 0)

-	return dist / dtime;

-    else

-	return 0;/* synonymous for NaN, since we're not C99 */

-}

-

-/* find the most plausible velocity. That is, the most distant

- * (in time) tracker which isn't too old, beyond a linear partition,

- * or simply too much off initial velocity.

- *

- * May return 0.

- */

-static float

-QueryTrackers(DeviceVelocityPtr vel, int cur_t){

-    int n, offset, dir = 255, i = -1, age_ms;

-    /* initial velocity: a low-offset, valid velocity */

-    float iveloc = 0, res = 0, tmp, vdiff;

-    float vfac =  vel->corr_mul * vel->const_acceleration; /* premultiply */

-    /* loop from current to older data */

-    for(offset = 1; offset < vel->num_tracker; offset++){

-	n = TRACKER_INDEX(vel, offset);

-

-	age_ms = cur_t - vel->tracker[n].time;

-

-	/* bail out if data is too old and protect from overrun */

-	if (age_ms >= vel->reset_time || age_ms < 0) {

-	    DebugAccelF("(dix prtacc) query: tracker too old\n");

-	    break;

-	}

-

-	/*

-	 * this heuristic avoids using the linear-motion velocity formula

-	 * in CalcTracker() on motion that isn't exactly linear. So to get

-	 * even more precision we could subdivide as a final step, so possible

-	 * non-linearities are accounted for.

-	 */

-	dir &= vel->tracker[n].dir;

-	if(dir == 0){

-	    DebugAccelF("(dix prtacc) query: no longer linear\n");

-	    /* instead of breaking it we might also inspect the partition after,

-	     * but actual improvement with this is probably rare. */

-	    break;

-	}

-

-	tmp = CalcTracker(vel, offset, cur_t) * vfac;

-

-	if ((iveloc == 0 || offset <= vel->initial_range) && tmp != 0) {

-	    /* set initial velocity and result */

-	    res = iveloc = tmp;

-	    i = offset;

-	} else if (iveloc != 0 && tmp != 0) {

-	    vdiff = fabs(iveloc - tmp);

-	    if (vdiff <= vel->max_diff ||

-		vdiff/(iveloc + tmp) < vel->max_rel_diff) {

-		/* we're in range with the initial velocity,

-		 * so this result is likely better

-		 * (it contains more information). */

-		res = tmp;

-		i = offset;

-	    }else{

-		/* we're not in range, quit - it won't get better. */

-		DebugAccelF("(dix prtacc) query: tracker too different:"

-		            " old %2.2f initial %2.2f diff: %2.2f\n",

-		            tmp, iveloc, vdiff);

-		break;

-	    }

-	}

-    }

-    if(offset == vel->num_tracker){

-	DebugAccelF("(dix prtacc) query: last tracker in effect\n");

-	i = vel->num_tracker-1;

-    }

-    if(i>=0){

-        n = TRACKER_INDEX(vel, i);

-	DebugAccelF("(dix prtacc) result: offset %i [dx: %i dy: %i diff: %i]\n",

-	            i,

-	            vel->tracker[n].dx,

-	            vel->tracker[n].dy,

-	            cur_t - vel->tracker[n].time);

-    }

-    return res;

-}

-

-#undef TRACKER_INDEX

-

-/**

- * Perform velocity approximation based on 2D 'mickeys' (mouse motion delta).

- * return true if non-visible state reset is suggested

- */

-short

-ProcessVelocityData2D(

-    DeviceVelocityPtr vel,

-    int dx,

-    int dy,

-    int time)

-{

-    float velocity;

-

-    vel->last_velocity = vel->velocity;

-

-    FeedTrackers(vel, dx, dy, time);

-

-    velocity = QueryTrackers(vel, time);

-

-    vel->velocity = velocity;

-    return velocity == 0;

-}

-

-/**

- * this flattens significant ( > 1) mickeys a little bit for more steady

- * constant-velocity response

- */

-static inline float

-ApplySimpleSoftening(int od, int d)

-{

-    float res = d;

-    if (d <= 1 && d >= -1)

-        return res;

-    if (d > od)

-        res -= 0.5;

-    else if (d < od)

-        res += 0.5;

-    return res;

-}

-

-

-static void

-ApplySofteningAndConstantDeceleration(

-        DeviceVelocityPtr vel,

-        int dx,

-        int dy,

-        float* fdx,

-        float* fdy,

-        short do_soften)

-{

-    if (do_soften && vel->use_softening) {

-        *fdx = ApplySimpleSoftening(vel->last_dx, dx);

-        *fdy = ApplySimpleSoftening(vel->last_dy, dy);

-    } else {

-        *fdx = dx;

-        *fdy = dy;

-    }

-

-    *fdx *= vel->const_acceleration;

-    *fdy *= vel->const_acceleration;

-}

-

-/*

- * compute the acceleration for given velocity and enforce min_acceleartion

- */

-float

-BasicComputeAcceleration(

-    DeviceIntPtr dev,

-    DeviceVelocityPtr vel,

-    float velocity,

-    float threshold,

-    float acc){

-

-    float result;

-    result = vel->Profile(dev, vel, velocity, threshold, acc);

-

-    /* enforce min_acceleration */

-    if (result < vel->min_acceleration)

-	result = vel->min_acceleration;

-    return result;

-}

-

-/**

- * Compute acceleration. Takes into account averaging, nv-reset, etc.

- */

-static float

-ComputeAcceleration(

-    DeviceIntPtr dev,

-    DeviceVelocityPtr vel,

-    float threshold,

-    float acc){

-    float res;

-

-    if(vel->velocity <= 0){

-	DebugAccelF("(dix ptracc) profile skipped\n");

-        /*

-         * If we have no idea about device velocity, don't pretend it.

-         */

-	return 1;

-    }

-

-    if(vel->average_accel && vel->velocity != vel->last_velocity){

-	/* use simpson's rule to average acceleration between

-	 * current and previous velocity.

-	 * Though being the more natural choice, it causes a minor delay

-	 * in comparison, so it can be disabled. */

-	res = BasicComputeAcceleration(

-	          dev, vel, vel->velocity, threshold, acc);

-	res += BasicComputeAcceleration(

-	          dev, vel, vel->last_velocity, threshold, acc);

-	res += 4.0f * BasicComputeAcceleration(dev, vel,

-	                   (vel->last_velocity + vel->velocity) / 2,

-	                   threshold, acc);

-	res /= 6.0f;

-	DebugAccelF("(dix ptracc) profile average [%.2f ... %.2f] is %.3f\n",

-	            vel->velocity, vel->last_velocity, res);

-        return res;

-    }else{

-	res = BasicComputeAcceleration(dev, vel,

-	                               vel->velocity, threshold, acc);

-	DebugAccelF("(dix ptracc) profile sample [%.2f] is %.3f\n",

-               vel->velocity, res);

-	return res;

-    }

-}

-

-

-/*****************************************

- *  Acceleration functions and profiles

- ****************************************/

-

-/**

- * Polynomial function similar previous one, but with f(1) = 1

- */

-static float

-PolynomialAccelerationProfile(

-    DeviceIntPtr dev,

-    DeviceVelocityPtr vel,

-    float velocity,

-    float ignored,

-    float acc)

-{

-   return pow(velocity, (acc - 1.0) * 0.5);

-}

-

-

-/**

- * returns acceleration for velocity.

- * This profile selects the two functions like the old scheme did

- */

-static float

-ClassicProfile(

-    DeviceIntPtr dev,

-    DeviceVelocityPtr vel,

-    float velocity,

-    float threshold,

-    float acc)

-{

-    if (threshold > 0) {

-	return SimpleSmoothProfile (dev,

-	                            vel,

-	                            velocity,

-                                    threshold,

-                                    acc);

-    } else {

-	return PolynomialAccelerationProfile (dev,

-	                                      vel,

-	                                      velocity,

-                                              0,

-                                              acc);

-    }

-}

-

-

-/**

- * Power profile

- * This has a completely smooth transition curve, i.e. no jumps in the

- * derivatives.

- *

- * This has the expense of overall response dependency on min-acceleration.

- * In effect, min_acceleration mimics const_acceleration in this profile.

- */

-static float

-PowerProfile(

-    DeviceIntPtr dev,

-    DeviceVelocityPtr vel,

-    float velocity,

-    float threshold,

-    float acc)

-{

-    float vel_dist;

-

-    acc = (acc-1.0) * 0.1f + 1.0; /* without this, acc of 2 is unuseable */

-

-    if (velocity <= threshold)

-        return vel->min_acceleration;

-    vel_dist = velocity - threshold;

-    return (pow(acc, vel_dist)) * vel->min_acceleration;

-}

-

-

-/**

- * just a smooth function in [0..1] -> [0..1]

- *  - point symmetry at 0.5

- *  - f'(0) = f'(1) = 0

- *  - starts faster than a sinoid

- *  - smoothness C1 (Cinf if you dare to ignore endpoints)

- */

-static inline float

-CalcPenumbralGradient(float x){

-    x *= 2.0f;

-    x -= 1.0f;

-    return 0.5f + (x * sqrt(1.0f - x*x) + asin(x))/M_PI;

-}

-

-

-/**

- * acceleration function similar to classic accelerated/unaccelerated,

- * but with smooth transition in between (and towards zero for adaptive dec.).

- */

-static float

-SimpleSmoothProfile(

-    DeviceIntPtr dev,

-    DeviceVelocityPtr vel,

-    float velocity,

-    float threshold,

-    float acc)

-{

-    if(velocity < 1.0f)

-        return CalcPenumbralGradient(0.5 + velocity*0.5) * 2.0f - 1.0f;

-    if(threshold < 1.0f)

-        threshold = 1.0f;

-    if (velocity <= threshold)

-        return 1;

-    velocity /= threshold;

-    if (velocity >= acc)

-        return acc;

-    else

-        return 1.0f + (CalcPenumbralGradient(velocity/acc) * (acc - 1.0f));

-}

-

-

-/**

- * This profile uses the first half of the penumbral gradient as a start

- * and then scales linearly.

- */

-static float

-SmoothLinearProfile(

-    DeviceIntPtr dev,

-    DeviceVelocityPtr vel,

-    float velocity,

-    float threshold,

-    float acc)

-{

-    float res, nv;

-

-    if(acc > 1.0f)

-        acc -= 1.0f; /*this is so acc = 1 is no acceleration */

-    else

-        return 1.0f;

-

-    nv = (velocity - threshold) * acc * 0.5f;

-

-    if(nv < 0){

-        res = 0;

-    }else if(nv < 2){

-        res = CalcPenumbralGradient(nv*0.25f)*2.0f;

-    }else{

-        nv -= 2.0f;

-        res = nv * 2.0f / M_PI  /* steepness of gradient at 0.5 */

-              + 1.0f; /* gradient crosses 2|1 */

-    }

-    res += vel->min_acceleration;

-    return res;

-}

-

-

-/**

- * From 0 to threshold, the response graduates smoothly from min_accel to

- * acceleration. Beyond threshold it is exactly the specified acceleration.

- */

-static float

-SmoothLimitedProfile(

-    DeviceIntPtr dev,

-    DeviceVelocityPtr vel,

-    float velocity,

-    float threshold,

-    float acc)

-{

-    float res;

-

-    if(velocity >= threshold || threshold == 0.0f)

-	return acc;

-

-    velocity /= threshold; /* should be [0..1[ now */

-

-    res = CalcPenumbralGradient(velocity) * (acc - vel->min_acceleration);

-

-    return vel->min_acceleration + res;

-}

-

-

-static float

-LinearProfile(

-    DeviceIntPtr dev,

-    DeviceVelocityPtr vel,

-    float velocity,

-    float threshold,

-    float acc)

-{

-    return acc * velocity;

-}

-

-static float

-NoProfile(

-    DeviceIntPtr dev,

-    DeviceVelocityPtr vel,

-    float velocity,

-    float threshold,

-    float acc)

-{

-    return 1.0f;

-}

-

-static PointerAccelerationProfileFunc

-GetAccelerationProfile(

-    DeviceVelocityPtr vel,

-    int profile_num)

-{

-    switch(profile_num){

-        case AccelProfileClassic:

-            return ClassicProfile;

-        case AccelProfileDeviceSpecific:

-            return vel->deviceSpecificProfile;

-        case AccelProfilePolynomial:

-            return PolynomialAccelerationProfile;

-        case AccelProfileSmoothLinear:

-            return SmoothLinearProfile;

-        case AccelProfileSimple:

-            return SimpleSmoothProfile;

-        case AccelProfilePower:

-            return PowerProfile;

-        case AccelProfileLinear:

-            return LinearProfile;

-        case AccelProfileSmoothLimited:

-            return SmoothLimitedProfile;

-        case AccelProfileNone:

-            return NoProfile;

-        default:

-            return NULL;

-    }

-}

-

-/**

- * Set the profile by number.

- * Intended to make profiles exchangeable at runtime.

- * If you created a profile, give it a number here and in the header to

- * make it selectable. In case some profile-specific init is needed, here

- * would be a good place, since FreeVelocityData() also calls this with

- * PROFILE_UNINITIALIZE.

- *

- * returns FALSE if profile number is unavailable, TRUE otherwise.

- */

-int

-SetAccelerationProfile(

-    DeviceVelocityPtr vel,

-    int profile_num)

-{

-    PointerAccelerationProfileFunc profile;

-    profile = GetAccelerationProfile(vel, profile_num);

-

-    if(profile == NULL && profile_num != PROFILE_UNINITIALIZE)

-	return FALSE;

-

-    /* Here one could free old profile-private data */

-    free(vel->profile_private);

-    vel->profile_private = NULL;

-    /* Here one could init profile-private data */

-    vel->Profile = profile;

-    vel->statistics.profile_number = profile_num;

-    return TRUE;

-}

-

-/**********************************************

- * driver interaction

- **********************************************/

-

-

-/**

- * device-specific profile

- *

- * The device-specific profile is intended as a hook for a driver

- * which may want to provide an own acceleration profile.

- * It should not rely on profile-private data, instead

- * it should do init/uninit in the driver (ie. with DEVICE_INIT and friends).

- * Users may override or choose it.

- */

-void

-SetDeviceSpecificAccelerationProfile(

-        DeviceVelocityPtr vel,

-        PointerAccelerationProfileFunc profile)

-{

-    if(vel)

-	vel->deviceSpecificProfile = profile;

-}

-

-/**

- * Use this function to obtain a DeviceVelocityPtr for a device. Will return NULL if

- * the predictable acceleration scheme is not in effect.

- */

-DeviceVelocityPtr

-GetDevicePredictableAccelData(

-	DeviceIntPtr dev)

-{

-    /*sanity check*/

-    if(!dev){

-	ErrorF("[dix] accel: DeviceIntPtr was NULL");

-	return NULL;

-    }

-    if( dev->valuator &&

-	dev->valuator->accelScheme.AccelSchemeProc ==

-	    acceleratePointerPredictable &&

-	dev->valuator->accelScheme.accelData != NULL){

-

-	return ((PredictableAccelSchemePtr)

-		dev->valuator->accelScheme.accelData)->vel;

-    }

-    return NULL;

-}

-

-/********************************

- *  acceleration schemes

- *******************************/

-

-/**

- * Modifies valuators in-place.

- * This version employs a velocity approximation algorithm to

- * enable fine-grained predictable acceleration profiles.

- */

-void

-acceleratePointerPredictable(

-    DeviceIntPtr dev,

-    ValuatorMask* val,

-    CARD32 evtime)

-{

-    float fdx, fdy, tmp, mult; /* no need to init */

-    int dx = 0, dy = 0, tmpi;

-    DeviceVelocityPtr velocitydata = GetDevicePredictableAccelData(dev);

-    Bool soften = TRUE;

-

-    if (!velocitydata)

-        return;

-

-    if (velocitydata->statistics.profile_number == AccelProfileNone &&

-        velocitydata->const_acceleration == 1.0f) {

-        return; /*we're inactive anyway, so skip the whole thing.*/

-    }

-

-    if (valuator_mask_isset(val, 0)) {

-        dx = valuator_mask_get(val, 0);

-    }

-

-    if (valuator_mask_isset(val, 1)) {

-        dy = valuator_mask_get(val, 1);

-    }

-

-    if (dx || dy){

-        /* reset non-visible state? */

-        if (ProcessVelocityData2D(velocitydata, dx , dy, evtime)) {

-            soften = FALSE;

-        }

-

-        if (dev->ptrfeed && dev->ptrfeed->ctrl.num) {

-            /* invoke acceleration profile to determine acceleration */

-            mult = ComputeAcceleration (dev, velocitydata,

-                                        dev->ptrfeed->ctrl.threshold,

-                                        (float)dev->ptrfeed->ctrl.num /

-                                            (float)dev->ptrfeed->ctrl.den);

-

-            if(mult != 1.0f || velocitydata->const_acceleration != 1.0f) {

-                ApplySofteningAndConstantDeceleration(velocitydata,

-                                                      dx, dy,

-                                                      &fdx, &fdy,

-                                                      (mult > 1.0f) && soften);

-

-                if (dx) {

-                    tmp = mult * fdx + dev->last.remainder[0];

-                    /* Since it may not be apparent: lrintf() does not offer

-                     * strong statements about rounding; however because we

-                     * process each axis conditionally, there's no danger

-                     * of a toggling remainder. Its lack of guarantees likely

-                     * makes it faster on the average target. */

-                    tmpi = lrintf(tmp);

-                    valuator_mask_set(val, 0, tmpi);

-                    dev->last.remainder[0] = tmp - (float)tmpi;

-                }

-                if (dy) {

-                    tmp = mult * fdy + dev->last.remainder[1];

-                    tmpi = lrintf(tmp);

-                    valuator_mask_set(val, 1, tmpi);

-                    dev->last.remainder[1] = tmp - (float)tmpi;

-                }

-                DebugAccelF("pos (%i | %i) remainders x: %.3f y: %.3f delta x:%.3f y:%.3f\n",

-                            *px, *py, dev->last.remainder[0], dev->last.remainder[1], fdx, fdy);

-            }

-        }

-    }

-    /* remember last motion delta (for softening/slow movement treatment) */

-    velocitydata->last_dx = dx;

-    velocitydata->last_dy = dy;

-}

-

-

-

-/**

- * Originally a part of xf86PostMotionEvent; modifies valuators

- * in-place. Retained mostly for embedded scenarios.

- */

-void

-acceleratePointerLightweight(

-    DeviceIntPtr dev,

-    ValuatorMask* val,

-    CARD32 ignored)

-{

-    float mult = 0.0, tmpf;

-    int dx = 0, dy = 0, tmpi;

-

-    if (valuator_mask_isset(val, 0)) {

-        dx = valuator_mask_get(val, 0);

-    }

-

-    if (valuator_mask_isset(val, 1)) {

-        dy = valuator_mask_get(val, 1);

-    }

-

-    if (!dx && !dy)

-        return;

-

-    if (dev->ptrfeed && dev->ptrfeed->ctrl.num) {

-        /* modeled from xf86Events.c */

-        if (dev->ptrfeed->ctrl.threshold) {

-            if ((abs(dx) + abs(dy)) >= dev->ptrfeed->ctrl.threshold) {

-                tmpf = ((float)dx *

-                        (float)(dev->ptrfeed->ctrl.num)) /

-                       (float)(dev->ptrfeed->ctrl.den) +

-                       dev->last.remainder[0];

-                if (dx) {

-                    tmpi = (int) tmpf;

-                    valuator_mask_set(val, 0, tmpi);

-                    dev->last.remainder[0] = tmpf - (float)tmpi;

-                }

-

-                tmpf = ((float)dy *

-                        (float)(dev->ptrfeed->ctrl.num)) /

-                       (float)(dev->ptrfeed->ctrl.den) +

-                       dev->last.remainder[1];

-                if (dy) {

-                    tmpi = (int) tmpf;

-                    valuator_mask_set(val, 1, tmpi);

-                    dev->last.remainder[1] = tmpf - (float)tmpi;

-                }

-            }

-        }

-        else {

-            mult = pow((float)dx * (float)dx + (float)dy * (float)dy,

-                       ((float)(dev->ptrfeed->ctrl.num) /

-                        (float)(dev->ptrfeed->ctrl.den) - 1.0) /

-                       2.0) / 2.0;

-            if (dx) {

-                tmpf = mult * (float)dx +

-                       dev->last.remainder[0];

-                tmpi = (int) tmpf;

-                valuator_mask_set(val, 0, tmpi);

-                dev->last.remainder[0] = tmpf - (float)tmpi;

-            }

-            if (dy) {

-                tmpf = mult * (float)dy +

-                       dev->last.remainder[1];

-                tmpi = (int)tmpf;

-                valuator_mask_set(val, 1, tmpi);

-                dev->last.remainder[1] = tmpf - (float)tmpi;

-            }

-        }

-    }

-}

+/*
+ *
+ * Copyright © 2006-2009 Simon Thum             simon dot thum at gmx dot de
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ */
+
+#ifdef HAVE_DIX_CONFIG_H
+#include <dix-config.h>
+#endif
+
+#include <math.h>
+#include <ptrveloc.h>
+#include <exevents.h>
+#include <X11/Xatom.h>
+#include <os.h>
+
+#include <xserver-properties.h>
+
+/*****************************************************************************
+ * Predictable pointer acceleration
+ *
+ * 2006-2009 by Simon Thum (simon [dot] thum [at] gmx de)
+ *
+ * Serves 3 complementary functions:
+ * 1) provide a sophisticated ballistic velocity estimate to improve
+ *    the relation between velocity (of the device) and acceleration
+ * 2) make arbitrary acceleration profiles possible
+ * 3) decelerate by two means (constant and adaptive) if enabled
+ *
+ * Important concepts are the
+ *
+ * - Scheme
+ *      which selects the basic algorithm
+ *      (see devices.c/InitPointerAccelerationScheme)
+ * - Profile
+ *      which returns an acceleration
+ *      for a given velocity
+ *
+ *  The profile can be selected by the user at runtime.
+ *  The classic profile is intended to cleanly perform old-style
+ *  function selection (threshold =/!= 0)
+ *
+ ****************************************************************************/
+
+/* fwds */
+int
+SetAccelerationProfile(DeviceVelocityPtr vel, int profile_num);
+static float
+SimpleSmoothProfile(DeviceIntPtr dev, DeviceVelocityPtr vel, float velocity,
+                    float threshold, float acc);
+static PointerAccelerationProfileFunc
+GetAccelerationProfile(DeviceVelocityPtr vel, int profile_num);
+static BOOL
+InitializePredictableAccelerationProperties(DeviceIntPtr,
+                                            DeviceVelocityPtr,
+                                            PredictableAccelSchemePtr);
+static BOOL
+DeletePredictableAccelerationProperties(DeviceIntPtr,
+                                        PredictableAccelSchemePtr);
+
+/*#define PTRACCEL_DEBUGGING*/
+
+#ifdef PTRACCEL_DEBUGGING
+#define DebugAccelF ErrorF
+#else
+#define DebugAccelF(...) /* */
+#endif
+
+/********************************
+ *  Init/Uninit
+ *******************************/
+
+/* some int which is not a profile number */
+#define PROFILE_UNINITIALIZE (-100)
+
+/**
+ * Init DeviceVelocity struct so it should match the average case
+ */
+void
+InitVelocityData(DeviceVelocityPtr vel)
+{
+    memset(vel, 0, sizeof(DeviceVelocityRec));
+
+    vel->corr_mul = 10.0;      /* dots per 10 milisecond should be usable */
+    vel->const_acceleration = 1.0;   /* no acceleration/deceleration  */
+    vel->reset_time = 300;
+    vel->use_softening = 1;
+    vel->min_acceleration = 1.0; /* don't decelerate */
+    vel->max_rel_diff = 0.2;
+    vel->max_diff = 1.0;
+    vel->initial_range = 2;
+    vel->average_accel = TRUE;
+    SetAccelerationProfile(vel, AccelProfileClassic);
+    InitTrackers(vel, 16);
+}
+
+
+/**
+ * Clean up DeviceVelocityRec
+ */
+void
+FreeVelocityData(DeviceVelocityPtr vel){
+    free(vel->tracker);
+    SetAccelerationProfile(vel, PROFILE_UNINITIALIZE);
+}
+
+
+/**
+ * Init predictable scheme
+ */
+Bool
+InitPredictableAccelerationScheme(DeviceIntPtr dev,
+                                  ValuatorAccelerationPtr protoScheme) {
+    DeviceVelocityPtr vel;
+    ValuatorAccelerationRec scheme;
+    PredictableAccelSchemePtr schemeData;
+    scheme = *protoScheme;
+    vel = calloc(1, sizeof(DeviceVelocityRec));
+    schemeData = calloc(1, sizeof(PredictableAccelSchemeRec));
+    if (!vel || !schemeData)
+        return FALSE;
+    InitVelocityData(vel);
+    schemeData->vel = vel;
+    scheme.accelData = schemeData;
+    if (!InitializePredictableAccelerationProperties(dev, vel, schemeData))
+        return FALSE;
+    /* all fine, assign scheme to device */
+    dev->valuator->accelScheme = scheme;
+    return TRUE;
+}
+
+
+/**
+ *  Uninit scheme
+ */
+void
+AccelerationDefaultCleanup(DeviceIntPtr dev)
+{
+    DeviceVelocityPtr vel = GetDevicePredictableAccelData(dev);
+    if (vel) {
+        /* the proper guarantee would be that we're not inside of
+         * AccelSchemeProc(), but that seems impossible. Schemes don't get
+         * switched often anyway.
+         */
+        OsBlockSignals();
+        dev->valuator->accelScheme.AccelSchemeProc = NULL;
+        FreeVelocityData(vel);
+        free(vel);
+        DeletePredictableAccelerationProperties(dev,
+            (PredictableAccelSchemePtr) dev->valuator->accelScheme.accelData);
+        free(dev->valuator->accelScheme.accelData);
+        dev->valuator->accelScheme.accelData = NULL;
+        OsReleaseSignals();
+    }
+}
+
+
+/*************************
+ * Input property support
+ ************************/
+
+/**
+ * choose profile
+ */
+static int
+AccelSetProfileProperty(DeviceIntPtr dev, Atom atom,
+                        XIPropertyValuePtr val, BOOL checkOnly)
+{
+    DeviceVelocityPtr vel;
+    int profile, *ptr = &profile;
+    int rc;
+    int nelem = 1;
+
+    if (atom != XIGetKnownProperty(ACCEL_PROP_PROFILE_NUMBER))
+        return Success;
+
+    vel = GetDevicePredictableAccelData(dev);
+    if (!vel)
+        return BadValue;
+    rc = XIPropToInt(val, &nelem, &ptr);
+
+    if(checkOnly)
+    {
+        if (rc)
+            return rc;
+
+        if (GetAccelerationProfile(vel, profile) == NULL)
+            return BadValue;
+    } else
+	SetAccelerationProfile(vel, profile);
+
+    return Success;
+}
+
+static long
+AccelInitProfileProperty(DeviceIntPtr dev, DeviceVelocityPtr vel)
+{
+    int profile = vel->statistics.profile_number;
+    Atom prop_profile_number = XIGetKnownProperty(ACCEL_PROP_PROFILE_NUMBER);
+
+    XIChangeDeviceProperty(dev, prop_profile_number, XA_INTEGER, 32,
+                           PropModeReplace, 1, &profile, FALSE);
+    XISetDevicePropertyDeletable(dev, prop_profile_number, FALSE);
+    return XIRegisterPropertyHandler(dev, AccelSetProfileProperty, NULL, NULL);
+}
+
+/**
+ * constant deceleration
+ */
+static int
+AccelSetDecelProperty(DeviceIntPtr dev, Atom atom,
+                      XIPropertyValuePtr val, BOOL checkOnly)
+{
+    DeviceVelocityPtr vel;
+    float v, *ptr = &v;
+    int rc;
+    int nelem = 1;
+
+    if (atom != XIGetKnownProperty(ACCEL_PROP_CONSTANT_DECELERATION))
+        return Success;
+
+    vel = GetDevicePredictableAccelData(dev);
+    if (!vel)
+        return BadValue;
+    rc = XIPropToFloat(val, &nelem, &ptr);
+
+    if(checkOnly)
+    {
+        if (rc)
+            return rc;
+	return (v >= 1.0f) ? Success : BadValue;
+    }
+
+    if(v >= 1.0f)
+	vel->const_acceleration = 1/v;
+
+    return Success;
+}
+
+static long
+AccelInitDecelProperty(DeviceIntPtr dev, DeviceVelocityPtr vel)
+{
+    float fval = 1.0/vel->const_acceleration;
+    Atom prop_const_decel = XIGetKnownProperty(ACCEL_PROP_CONSTANT_DECELERATION);
+    XIChangeDeviceProperty(dev, prop_const_decel,
+                           XIGetKnownProperty(XATOM_FLOAT), 32,
+                           PropModeReplace, 1, &fval, FALSE);
+    XISetDevicePropertyDeletable(dev, prop_const_decel, FALSE);
+    return XIRegisterPropertyHandler(dev, AccelSetDecelProperty, NULL, NULL);
+}
+
+
+/**
+ * adaptive deceleration
+ */
+static int
+AccelSetAdaptDecelProperty(DeviceIntPtr dev, Atom atom,
+                           XIPropertyValuePtr val, BOOL checkOnly)
+{
+    DeviceVelocityPtr veloc;
+    float v, *ptr = &v;
+    int rc;
+    int nelem = 1;
+
+    if (atom != XIGetKnownProperty(ACCEL_PROP_ADAPTIVE_DECELERATION))
+        return Success;
+
+    veloc = GetDevicePredictableAccelData(dev);
+    if (!veloc)
+        return BadValue;
+    rc = XIPropToFloat(val, &nelem, &ptr);
+
+    if(checkOnly)
+    {
+        if (rc)
+            return rc;
+	return (v >= 1.0f) ? Success : BadValue;
+    }
+
+    if(v >= 1.0f)
+	veloc->min_acceleration = 1/v;
+
+    return Success;
+}
+
+static long
+AccelInitAdaptDecelProperty(DeviceIntPtr dev, DeviceVelocityPtr vel)
+{
+    float fval = 1.0/vel->min_acceleration;
+    Atom prop_adapt_decel = XIGetKnownProperty(ACCEL_PROP_ADAPTIVE_DECELERATION);
+
+    XIChangeDeviceProperty(dev, prop_adapt_decel, XIGetKnownProperty(XATOM_FLOAT), 32,
+                           PropModeReplace, 1, &fval, FALSE);
+    XISetDevicePropertyDeletable(dev, prop_adapt_decel, FALSE);
+    return XIRegisterPropertyHandler(dev, AccelSetAdaptDecelProperty, NULL, NULL);
+}
+
+
+/**
+ * velocity scaling
+ */
+static int
+AccelSetScaleProperty(DeviceIntPtr dev, Atom atom,
+                      XIPropertyValuePtr val, BOOL checkOnly)
+{
+    DeviceVelocityPtr vel;
+    float v, *ptr = &v;
+    int rc;
+    int nelem = 1;
+
+    if (atom != XIGetKnownProperty(ACCEL_PROP_VELOCITY_SCALING))
+        return Success;
+
+    vel = GetDevicePredictableAccelData(dev);
+    if (!vel)
+        return BadValue;
+    rc = XIPropToFloat(val, &nelem, &ptr);
+
+    if (checkOnly)
+    {
+        if (rc)
+            return rc;
+
+        return (v > 0) ? Success : BadValue;
+    }
+
+    if(v > 0)
+	vel->corr_mul = v;
+
+    return Success;
+}
+
+static long
+AccelInitScaleProperty(DeviceIntPtr dev, DeviceVelocityPtr vel)
+{
+    float fval = vel->corr_mul;
+    Atom prop_velo_scale = XIGetKnownProperty(ACCEL_PROP_VELOCITY_SCALING);
+
+    XIChangeDeviceProperty(dev, prop_velo_scale, XIGetKnownProperty(XATOM_FLOAT), 32,
+                           PropModeReplace, 1, &fval, FALSE);
+    XISetDevicePropertyDeletable(dev, prop_velo_scale, FALSE);
+    return XIRegisterPropertyHandler(dev, AccelSetScaleProperty, NULL, NULL);
+}
+
+static BOOL
+InitializePredictableAccelerationProperties(
+    DeviceIntPtr dev,
+    DeviceVelocityPtr  vel,
+    PredictableAccelSchemePtr schemeData)
+{
+    int num_handlers = 4;
+    if(!vel)
+        return FALSE;
+
+    schemeData->prop_handlers = calloc(num_handlers, sizeof(long));
+    if (!schemeData->prop_handlers)
+        return FALSE;
+    schemeData->num_prop_handlers = num_handlers;
+    schemeData->prop_handlers[0] = AccelInitProfileProperty(dev, vel);
+    schemeData->prop_handlers[1] = AccelInitDecelProperty(dev, vel);
+    schemeData->prop_handlers[2] = AccelInitAdaptDecelProperty(dev, vel);
+    schemeData->prop_handlers[3] = AccelInitScaleProperty(dev, vel);
+
+    return TRUE;
+}
+
+BOOL
+DeletePredictableAccelerationProperties(
+    DeviceIntPtr dev,
+    PredictableAccelSchemePtr scheme)
+{
+    DeviceVelocityPtr vel;
+    Atom prop;
+    int i;
+
+    prop = XIGetKnownProperty(ACCEL_PROP_VELOCITY_SCALING);
+    XIDeleteDeviceProperty(dev, prop, FALSE);
+    prop = XIGetKnownProperty(ACCEL_PROP_ADAPTIVE_DECELERATION);
+    XIDeleteDeviceProperty(dev, prop, FALSE);
+    prop = XIGetKnownProperty(ACCEL_PROP_CONSTANT_DECELERATION);
+    XIDeleteDeviceProperty(dev, prop, FALSE);
+    prop = XIGetKnownProperty(ACCEL_PROP_PROFILE_NUMBER);
+    XIDeleteDeviceProperty(dev, prop, FALSE);
+
+    vel = GetDevicePredictableAccelData(dev);
+    if (vel) {
+        for (i = 0; i < scheme->num_prop_handlers; i++)
+            if (scheme->prop_handlers[i])
+                XIUnregisterPropertyHandler(dev, scheme->prop_handlers[i]);
+    }
+
+    free(scheme->prop_handlers);
+    scheme->prop_handlers = NULL;
+    scheme->num_prop_handlers = 0;
+    return TRUE;
+}
+
+/*********************
+ * Tracking logic
+ ********************/
+
+void
+InitTrackers(DeviceVelocityPtr vel, int ntracker)
+{
+    if(ntracker < 1){
+	ErrorF("(dix ptracc) invalid number of trackers\n");
+	return;
+    }
+    free(vel->tracker);
+    vel->tracker = (MotionTrackerPtr)calloc(ntracker, sizeof(MotionTracker));
+    vel->num_tracker = ntracker;
+}
+
+enum directions {
+    N   = (1 << 0),
+    NE  = (1 << 1),
+    E   = (1 << 2),
+    SE  = (1 << 3),
+    S   = (1 << 4),
+    SW  = (1 << 5),
+    W   = (1 << 6),
+    NW  = (1 << 7),
+    UNDEFINED = 0xFF
+};
+/**
+ * return a bit field of possible directions.
+ * There's no reason against widening to more precise directions (<45 degrees),
+ * should it not perform well. All this is needed for is sort out non-linear
+ * motion, so precision isn't paramount. However, one should not flag direction
+ * too narrow, since it would then cut the linear segment to zero size way too
+ * often.
+ *
+ * @return A bitmask for N, NE, S, SE, etc. indicating the directions for
+ * this movement.
+ */
+static int
+DoGetDirection(int dx, int dy){
+    int dir = 0;
+
+    /* on insignificant mickeys, flag 135 degrees */
+    if(abs(dx) < 2 && abs(dy) < 2){
+        /* first check diagonal cases */
+        if(dx > 0 && dy > 0)
+            dir = E | SE | S;
+        else if(dx > 0 && dy < 0)
+            dir =  N | NE | E;
+        else if(dx < 0 && dy < 0)
+            dir =  W | NW | N;
+        else if(dx < 0 && dy > 0)
+            dir =  W | SW | S;
+        /* check axis-aligned directions */
+        else if(dx > 0)
+            dir =  NE | E | SE;
+        else if(dx < 0)
+            dir =  NW | W | SW;
+        else if(dy > 0)
+            dir =  SE | S | SW;
+        else if(dy < 0)
+            dir =  NE | N | NW;
+        else
+            dir = UNDEFINED; /* shouldn't happen */
+    } else { /* compute angle and set appropriate flags */
+        float r;
+        int i1, i2;
+
+#ifdef _ISOC99_SOURCE
+        r = atan2f(dy, dx);
+#else
+        r = atan2(dy, dx);
+#endif
+        /* find direction.
+         *
+         * Add 360° to avoid r become negative since C has no well-defined
+         * modulo for such cases. Then divide by 45° to get the octant
+         * number,  e.g.
+         *          0 <= r <= 1 is [0-45]°
+         *          1 <= r <= 2 is [45-90]°
+         *          etc.
+         * But we add extra 90° to match up with our N, S, etc. defines up
+         * there, rest stays the same.
+         */
+        r = (r+(M_PI*2.5))/(M_PI/4);
+        /* this intends to flag 2 directions (45 degrees),
+         * except on very well-aligned mickeys. */
+        i1 = (int)(r+0.1) % 8;
+        i2 = (int)(r+0.9) % 8;
+        if(i1 < 0 || i1 > 7 || i2 < 0 || i2 > 7)
+            dir = UNDEFINED; /* shouldn't happen */
+        else
+            dir = (1 << i1 | 1 << i2);
+    }
+    return dir;
+}
+
+#define DIRECTION_CACHE_RANGE 5
+#define DIRECTION_CACHE_SIZE (DIRECTION_CACHE_RANGE*2+1)
+
+/* cache DoGetDirection().
+ * To avoid excessive use of direction calculation, cache the values for
+ * [-5..5] for both x/y. Anything outside of that is calcualted on the fly.
+ *
+ * @return A bitmask for N, NE, S, SE, etc. indicating the directions for
+ * this movement.
+ */
+static int
+GetDirection(int dx, int dy){
+    static int cache[DIRECTION_CACHE_SIZE][DIRECTION_CACHE_SIZE];
+    int dir;
+    if (abs(dx) <= DIRECTION_CACHE_RANGE &&
+	abs(dy) <= DIRECTION_CACHE_RANGE) {
+	/* cacheable */
+	dir = cache[DIRECTION_CACHE_RANGE+dx][DIRECTION_CACHE_RANGE+dy];
+	if(dir == 0) {
+	    dir = DoGetDirection(dx, dy);
+	    cache[DIRECTION_CACHE_RANGE+dx][DIRECTION_CACHE_RANGE+dy] = dir;
+	}
+    }else{
+	/* non-cacheable */
+	dir = DoGetDirection(dx, dy);
+    }
+
+    return dir;
+}
+
+#undef DIRECTION_CACHE_RANGE
+#undef DIRECTION_CACHE_SIZE
+
+
+/* convert offset (age) to array index */
+#define TRACKER_INDEX(s, d) (((s)->num_tracker + (s)->cur_tracker - (d)) % (s)->num_tracker)
+#define TRACKER(s, d) &(s)->tracker[TRACKER_INDEX(s,d)]
+
+/**
+ * Add the delta motion to each tracker, then reset the latest tracker to
+ * 0/0 and set it as the current one.
+ */
+static inline void
+FeedTrackers(DeviceVelocityPtr vel, int dx, int dy, int cur_t)
+{
+    int n;
+    for(n = 0; n < vel->num_tracker; n++){
+	vel->tracker[n].dx += dx;
+	vel->tracker[n].dy += dy;
+    }
+    n = (vel->cur_tracker + 1) % vel->num_tracker;
+    vel->tracker[n].dx = 0;
+    vel->tracker[n].dy = 0;
+    vel->tracker[n].time = cur_t;
+    vel->tracker[n].dir = GetDirection(dx, dy);
+    DebugAccelF("(dix prtacc) motion [dx: %i dy: %i dir:%i diff: %i]\n",
+                dx, dy, vel->tracker[n].dir,
+                cur_t - vel->tracker[vel->cur_tracker].time);
+    vel->cur_tracker = n;
+}
+
+/**
+ * calc velocity for given tracker, with
+ * velocity scaling.
+ * This assumes linear motion.
+ */
+static float
+CalcTracker(const MotionTracker *tracker, int cur_t){
+    float dist = sqrt(tracker->dx * tracker->dx + tracker->dy * tracker->dy);
+    int dtime = cur_t - tracker->time;
+    if(dtime > 0)
+	return dist / dtime;
+    else
+	return 0;/* synonymous for NaN, since we're not C99 */
+}
+
+/* find the most plausible velocity. That is, the most distant
+ * (in time) tracker which isn't too old, the movement vector was
+ * in the same octant, and where the velocity is within an
+ * acceptable range to the inital velocity.
+ *
+ * @return The tracker's velocity or 0 if the above conditions are unmet
+ */
+static float
+QueryTrackers(DeviceVelocityPtr vel, int cur_t){
+    int offset, dir = UNDEFINED, used_offset = -1, age_ms;
+    /* initial velocity: a low-offset, valid velocity */
+    float initial_velocity = 0, result = 0, velocity_diff;
+    float velocity_factor =  vel->corr_mul * vel->const_acceleration; /* premultiply */
+    /* loop from current to older data */
+    for(offset = 1; offset < vel->num_tracker; offset++){
+	MotionTracker *tracker = TRACKER(vel, offset);
+	float tracker_velocity;
+
+	age_ms = cur_t - tracker->time;
+
+	/* bail out if data is too old and protect from overrun */
+	if (age_ms >= vel->reset_time || age_ms < 0) {
+	    DebugAccelF("(dix prtacc) query: tracker too old\n");
+	    break;
+	}
+
+	/*
+	 * this heuristic avoids using the linear-motion velocity formula
+	 * in CalcTracker() on motion that isn't exactly linear. So to get
+	 * even more precision we could subdivide as a final step, so possible
+	 * non-linearities are accounted for.
+	 */
+	dir &= tracker->dir;
+	if(dir == 0){ /* we've changed octant of movement (e.g. NE → NW) */
+	    DebugAccelF("(dix prtacc) query: no longer linear\n");
+	    /* instead of breaking it we might also inspect the partition after,
+	     * but actual improvement with this is probably rare. */
+	    break;
+	}
+
+	tracker_velocity = CalcTracker(tracker, cur_t) * velocity_factor;
+
+	if ((initial_velocity == 0 || offset <= vel->initial_range) && tracker_velocity != 0) {
+	    /* set initial velocity and result */
+	    result = initial_velocity = tracker_velocity;
+	    used_offset = offset;
+	} else if (initial_velocity != 0 && tracker_velocity != 0) {
+	    velocity_diff = fabs(initial_velocity - tracker_velocity);
+
+	    if (velocity_diff > vel->max_diff &&
+		velocity_diff/(initial_velocity + tracker_velocity) >= vel->max_rel_diff) {
+		/* we're not in range, quit - it won't get better. */
+		DebugAccelF("(dix prtacc) query: tracker too different:"
+		            " old %2.2f initial %2.2f diff: %2.2f\n",
+		            tracker_velocity, initial_velocity, velocity_diff);
+		break;
+	    }
+	    /* we're in range with the initial velocity,
+	     * so this result is likely better
+	     * (it contains more information). */
+	    result = tracker_velocity;
+	    used_offset = offset;
+	}
+    }
+    if(offset == vel->num_tracker){
+	DebugAccelF("(dix prtacc) query: last tracker in effect\n");
+	used_offset = vel->num_tracker-1;
+    }
+#ifdef PTRACCEL_DEBUGGING
+    if(used_offset >= 0){
+	MotionTracker *tracker = TRACKER(vel, used_offset);
+	DebugAccelF("(dix prtacc) result: offset %i [dx: %i dy: %i diff: %i]\n",
+	            used_offset, tracker->dx, tracker->dy, cur_t - tracker->time);
+    }
+#endif
+    return result;
+}
+
+#undef TRACKER_INDEX
+#undef TRACKER
+
+/**
+ * Perform velocity approximation based on 2D 'mickeys' (mouse motion delta).
+ * return true if non-visible state reset is suggested
+ */
+BOOL
+ProcessVelocityData2D(
+    DeviceVelocityPtr vel,
+    int dx,
+    int dy,
+    int time)
+{
+    float velocity;
+
+    vel->last_velocity = vel->velocity;
+
+    FeedTrackers(vel, dx, dy, time);
+
+    velocity = QueryTrackers(vel, time);
+
+    vel->velocity = velocity;
+    return velocity == 0;
+}
+
+/**
+ * this flattens significant ( > 1) mickeys a little bit for more steady
+ * constant-velocity response
+ */
+static inline float
+ApplySimpleSoftening(int prev_delta, int delta)
+{
+    float result = delta;
+
+    if (delta < -1 || delta > 1) {
+	if (delta > prev_delta)
+	    result -= 0.5;
+	else if (delta < prev_delta)
+	    result += 0.5;
+    }
+    return result;
+}
+
+
+/**
+ * Soften the delta based on previous deltas stored in vel.
+ *
+ * @param[in,out] fdx Delta X, modified in-place.
+ * @param[in,out] fdx Delta Y, modified in-place.
+ */
+static void
+ApplySoftening(
+        DeviceVelocityPtr vel,
+        float* fdx,
+        float* fdy)
+{
+    if (vel->use_softening) {
+        *fdx = ApplySimpleSoftening(vel->last_dx, *fdx);
+        *fdy = ApplySimpleSoftening(vel->last_dy, *fdy);
+    }
+}
+
+static void
+ApplyConstantDeceleration(DeviceVelocityPtr vel, float *fdx, float *fdy)
+{
+    *fdx *= vel->const_acceleration;
+    *fdy *= vel->const_acceleration;
+}
+
+/*
+ * compute the acceleration for given velocity and enforce min_acceleartion
+ */
+float
+BasicComputeAcceleration(
+    DeviceIntPtr dev,
+    DeviceVelocityPtr vel,
+    float velocity,
+    float threshold,
+    float acc){
+
+    float result;
+    result = vel->Profile(dev, vel, velocity, threshold, acc);
+
+    /* enforce min_acceleration */
+    if (result < vel->min_acceleration)
+	result = vel->min_acceleration;
+    return result;
+}
+
+/**
+ * Compute acceleration. Takes into account averaging, nv-reset, etc.
+ * If the velocity has changed, an average is taken of 6 velocity factors:
+ * current velocity, last velocity and 4 times the average between the two.
+ */
+static float
+ComputeAcceleration(
+    DeviceIntPtr dev,
+    DeviceVelocityPtr vel,
+    float threshold,
+    float acc){
+    float result;
+
+    if(vel->velocity <= 0){
+	DebugAccelF("(dix ptracc) profile skipped\n");
+        /*
+         * If we have no idea about device velocity, don't pretend it.
+         */
+	return 1;
+    }
+
+    if(vel->average_accel && vel->velocity != vel->last_velocity){
+	/* use simpson's rule to average acceleration between
+	 * current and previous velocity.
+	 * Though being the more natural choice, it causes a minor delay
+	 * in comparison, so it can be disabled. */
+	result = BasicComputeAcceleration(
+	          dev, vel, vel->velocity, threshold, acc);
+	result += BasicComputeAcceleration(
+	          dev, vel, vel->last_velocity, threshold, acc);
+	result += 4.0f * BasicComputeAcceleration(dev, vel,
+	                   (vel->last_velocity + vel->velocity) / 2,
+	                   threshold, acc);
+	result /= 6.0f;
+	DebugAccelF("(dix ptracc) profile average [%.2f ... %.2f] is %.3f\n",
+	            vel->velocity, vel->last_velocity, result);
+    }else{
+	result = BasicComputeAcceleration(dev, vel,
+	                                  vel->velocity, threshold, acc);
+	DebugAccelF("(dix ptracc) profile sample [%.2f] is %.3f\n",
+               vel->velocity, res);
+    }
+
+    return result;
+}
+
+
+/*****************************************
+ *  Acceleration functions and profiles
+ ****************************************/
+
+/**
+ * Polynomial function similar previous one, but with f(1) = 1
+ */
+static float
+PolynomialAccelerationProfile(
+    DeviceIntPtr dev,
+    DeviceVelocityPtr vel,
+    float velocity,
+    float ignored,
+    float acc)
+{
+   return pow(velocity, (acc - 1.0) * 0.5);
+}
+
+
+/**
+ * returns acceleration for velocity.
+ * This profile selects the two functions like the old scheme did
+ */
+static float
+ClassicProfile(
+    DeviceIntPtr dev,
+    DeviceVelocityPtr vel,
+    float velocity,
+    float threshold,
+    float acc)
+{
+    if (threshold > 0) {
+	return SimpleSmoothProfile (dev,
+	                            vel,
+	                            velocity,
+                                    threshold,
+                                    acc);
+    } else {
+	return PolynomialAccelerationProfile (dev,
+	                                      vel,
+	                                      velocity,
+                                              0,
+                                              acc);
+    }
+}
+
+
+/**
+ * Power profile
+ * This has a completely smooth transition curve, i.e. no jumps in the
+ * derivatives.
+ *
+ * This has the expense of overall response dependency on min-acceleration.
+ * In effect, min_acceleration mimics const_acceleration in this profile.
+ */
+static float
+PowerProfile(
+    DeviceIntPtr dev,
+    DeviceVelocityPtr vel,
+    float velocity,
+    float threshold,
+    float acc)
+{
+    float vel_dist;
+
+    acc = (acc-1.0) * 0.1f + 1.0; /* without this, acc of 2 is unuseable */
+
+    if (velocity <= threshold)
+        return vel->min_acceleration;
+    vel_dist = velocity - threshold;
+    return (pow(acc, vel_dist)) * vel->min_acceleration;
+}
+
+
+/**
+ * just a smooth function in [0..1] -> [0..1]
+ *  - point symmetry at 0.5
+ *  - f'(0) = f'(1) = 0
+ *  - starts faster than a sinoid
+ *  - smoothness C1 (Cinf if you dare to ignore endpoints)
+ */
+static inline float
+CalcPenumbralGradient(float x){
+    x *= 2.0f;
+    x -= 1.0f;
+    return 0.5f + (x * sqrt(1.0f - x*x) + asin(x))/M_PI;
+}
+
+
+/**
+ * acceleration function similar to classic accelerated/unaccelerated,
+ * but with smooth transition in between (and towards zero for adaptive dec.).
+ */
+static float
+SimpleSmoothProfile(
+    DeviceIntPtr dev,
+    DeviceVelocityPtr vel,
+    float velocity,
+    float threshold,
+    float acc)
+{
+    if(velocity < 1.0f)
+        return CalcPenumbralGradient(0.5 + velocity*0.5) * 2.0f - 1.0f;
+    if(threshold < 1.0f)
+        threshold = 1.0f;
+    if (velocity <= threshold)
+        return 1;
+    velocity /= threshold;
+    if (velocity >= acc)
+        return acc;
+    else
+        return 1.0f + (CalcPenumbralGradient(velocity/acc) * (acc - 1.0f));
+}
+
+
+/**
+ * This profile uses the first half of the penumbral gradient as a start
+ * and then scales linearly.
+ */
+static float
+SmoothLinearProfile(
+    DeviceIntPtr dev,
+    DeviceVelocityPtr vel,
+    float velocity,
+    float threshold,
+    float acc)
+{
+    float res, nv;
+
+    if(acc > 1.0f)
+        acc -= 1.0f; /*this is so acc = 1 is no acceleration */
+    else
+        return 1.0f;
+
+    nv = (velocity - threshold) * acc * 0.5f;
+
+    if(nv < 0){
+        res = 0;
+    }else if(nv < 2){
+        res = CalcPenumbralGradient(nv*0.25f)*2.0f;
+    }else{
+        nv -= 2.0f;
+        res = nv * 2.0f / M_PI  /* steepness of gradient at 0.5 */
+              + 1.0f; /* gradient crosses 2|1 */
+    }
+    res += vel->min_acceleration;
+    return res;
+}
+
+
+/**
+ * From 0 to threshold, the response graduates smoothly from min_accel to
+ * acceleration. Beyond threshold it is exactly the specified acceleration.
+ */
+static float
+SmoothLimitedProfile(
+    DeviceIntPtr dev,
+    DeviceVelocityPtr vel,
+    float velocity,
+    float threshold,
+    float acc)
+{
+    float res;
+
+    if(velocity >= threshold || threshold == 0.0f)
+	return acc;
+
+    velocity /= threshold; /* should be [0..1[ now */
+
+    res = CalcPenumbralGradient(velocity) * (acc - vel->min_acceleration);
+
+    return vel->min_acceleration + res;
+}
+
+
+static float
+LinearProfile(
+    DeviceIntPtr dev,
+    DeviceVelocityPtr vel,
+    float velocity,
+    float threshold,
+    float acc)
+{
+    return acc * velocity;
+}
+
+static float
+NoProfile(
+    DeviceIntPtr dev,
+    DeviceVelocityPtr vel,
+    float velocity,
+    float threshold,
+    float acc)
+{
+    return 1.0f;
+}
+
+static PointerAccelerationProfileFunc
+GetAccelerationProfile(
+    DeviceVelocityPtr vel,
+    int profile_num)
+{
+    switch(profile_num){
+        case AccelProfileClassic:
+            return ClassicProfile;
+        case AccelProfileDeviceSpecific:
+            return vel->deviceSpecificProfile;
+        case AccelProfilePolynomial:
+            return PolynomialAccelerationProfile;
+        case AccelProfileSmoothLinear:
+            return SmoothLinearProfile;
+        case AccelProfileSimple:
+            return SimpleSmoothProfile;
+        case AccelProfilePower:
+            return PowerProfile;
+        case AccelProfileLinear:
+            return LinearProfile;
+        case AccelProfileSmoothLimited:
+            return SmoothLimitedProfile;
+        case AccelProfileNone:
+            return NoProfile;
+        default:
+            return NULL;
+    }
+}
+
+/**
+ * Set the profile by number.
+ * Intended to make profiles exchangeable at runtime.
+ * If you created a profile, give it a number here and in the header to
+ * make it selectable. In case some profile-specific init is needed, here
+ * would be a good place, since FreeVelocityData() also calls this with
+ * PROFILE_UNINITIALIZE.
+ *
+ * returns FALSE if profile number is unavailable, TRUE otherwise.
+ */
+int
+SetAccelerationProfile(
+    DeviceVelocityPtr vel,
+    int profile_num)
+{
+    PointerAccelerationProfileFunc profile;
+    profile = GetAccelerationProfile(vel, profile_num);
+
+    if(profile == NULL && profile_num != PROFILE_UNINITIALIZE)
+	return FALSE;
+
+    /* Here one could free old profile-private data */
+    free(vel->profile_private);
+    vel->profile_private = NULL;
+    /* Here one could init profile-private data */
+    vel->Profile = profile;
+    vel->statistics.profile_number = profile_num;
+    return TRUE;
+}
+
+/**********************************************
+ * driver interaction
+ **********************************************/
+
+
+/**
+ * device-specific profile
+ *
+ * The device-specific profile is intended as a hook for a driver
+ * which may want to provide an own acceleration profile.
+ * It should not rely on profile-private data, instead
+ * it should do init/uninit in the driver (ie. with DEVICE_INIT and friends).
+ * Users may override or choose it.
+ */
+void
+SetDeviceSpecificAccelerationProfile(
+        DeviceVelocityPtr vel,
+        PointerAccelerationProfileFunc profile)
+{
+    if(vel)
+	vel->deviceSpecificProfile = profile;
+}
+
+/**
+ * Use this function to obtain a DeviceVelocityPtr for a device. Will return NULL if
+ * the predictable acceleration scheme is not in effect.
+ */
+DeviceVelocityPtr
+GetDevicePredictableAccelData(
+	DeviceIntPtr dev)
+{
+    /*sanity check*/
+    if(!dev){
+	ErrorF("[dix] accel: DeviceIntPtr was NULL");
+	return NULL;
+    }
+    if( dev->valuator &&
+	dev->valuator->accelScheme.AccelSchemeProc ==
+	    acceleratePointerPredictable &&
+	dev->valuator->accelScheme.accelData != NULL){
+
+	return ((PredictableAccelSchemePtr)
+		dev->valuator->accelScheme.accelData)->vel;
+    }
+    return NULL;
+}
+
+/********************************
+ *  acceleration schemes
+ *******************************/
+
+/**
+ * Modifies valuators in-place.
+ * This version employs a velocity approximation algorithm to
+ * enable fine-grained predictable acceleration profiles.
+ */
+void
+acceleratePointerPredictable(
+    DeviceIntPtr dev,
+    ValuatorMask* val,
+    CARD32 evtime)
+{
+    int dx = 0, dy = 0, tmpi;
+    DeviceVelocityPtr velocitydata = GetDevicePredictableAccelData(dev);
+    Bool soften = TRUE;
+
+    if (!velocitydata)
+        return;
+
+    if (velocitydata->statistics.profile_number == AccelProfileNone &&
+        velocitydata->const_acceleration == 1.0f) {
+        return; /*we're inactive anyway, so skip the whole thing.*/
+    }
+
+    if (valuator_mask_isset(val, 0)) {
+        dx = valuator_mask_get(val, 0);
+    }
+
+    if (valuator_mask_isset(val, 1)) {
+        dy = valuator_mask_get(val, 1);
+    }
+
+    if (dx || dy){
+        /* reset non-visible state? */
+        if (ProcessVelocityData2D(velocitydata, dx , dy, evtime)) {
+            soften = FALSE;
+        }
+
+        if (dev->ptrfeed && dev->ptrfeed->ctrl.num) {
+            float mult;
+
+            /* invoke acceleration profile to determine acceleration */
+            mult = ComputeAcceleration (dev, velocitydata,
+                                        dev->ptrfeed->ctrl.threshold,
+                                        (float)dev->ptrfeed->ctrl.num /
+                                            (float)dev->ptrfeed->ctrl.den);
+
+            if(mult != 1.0f || velocitydata->const_acceleration != 1.0f) {
+                float fdx = dx,
+                      fdy = dy;
+
+                if (mult > 1.0f && soften)
+                    ApplySoftening(velocitydata, &fdx, &fdy);
+                ApplyConstantDeceleration(velocitydata, &fdx, &fdy);
+
+                /* Calculate the new delta (with accel) and drop it back
+                 * into the valuator masks */
+                if (dx) {
+                    float tmp;
+                    tmp = mult * fdx + dev->last.remainder[0];
+                    /* Since it may not be apparent: lrintf() does not offer
+                     * strong statements about rounding; however because we
+                     * process each axis conditionally, there's no danger
+                     * of a toggling remainder. Its lack of guarantees likely
+                     * makes it faster on the average target. */
+                    tmpi = lrintf(tmp);
+                    valuator_mask_set(val, 0, tmpi);
+                    dev->last.remainder[0] = tmp - (float)tmpi;
+                }
+                if (dy) {
+                    float tmp;
+                    tmp = mult * fdy + dev->last.remainder[1];
+                    tmpi = lrintf(tmp);
+                    valuator_mask_set(val, 1, tmpi);
+                    dev->last.remainder[1] = tmp - (float)tmpi;
+                }
+                DebugAccelF("pos (%i | %i) remainders x: %.3f y: %.3f delta x:%.3f y:%.3f\n",
+                            *px, *py, dev->last.remainder[0], dev->last.remainder[1], fdx, fdy);
+            }
+        }
+    }
+    /* remember last motion delta (for softening/slow movement treatment) */
+    velocitydata->last_dx = dx;
+    velocitydata->last_dy = dy;
+}
+
+
+
+/**
+ * Originally a part of xf86PostMotionEvent; modifies valuators
+ * in-place. Retained mostly for embedded scenarios.
+ */
+void
+acceleratePointerLightweight(
+    DeviceIntPtr dev,
+    ValuatorMask* val,
+    CARD32 ignored)
+{
+    float mult = 0.0, tmpf;
+    int dx = 0, dy = 0, tmpi;
+
+    if (valuator_mask_isset(val, 0)) {
+        dx = valuator_mask_get(val, 0);
+    }
+
+    if (valuator_mask_isset(val, 1)) {
+        dy = valuator_mask_get(val, 1);
+    }
+
+    if (!dx && !dy)
+        return;
+
+    if (dev->ptrfeed && dev->ptrfeed->ctrl.num) {
+        /* modeled from xf86Events.c */
+        if (dev->ptrfeed->ctrl.threshold) {
+            if ((abs(dx) + abs(dy)) >= dev->ptrfeed->ctrl.threshold) {
+                tmpf = ((float)dx *
+                        (float)(dev->ptrfeed->ctrl.num)) /
+                       (float)(dev->ptrfeed->ctrl.den) +
+                       dev->last.remainder[0];
+                if (dx) {
+                    tmpi = (int) tmpf;
+                    valuator_mask_set(val, 0, tmpi);
+                    dev->last.remainder[0] = tmpf - (float)tmpi;
+                }
+
+                tmpf = ((float)dy *
+                        (float)(dev->ptrfeed->ctrl.num)) /
+                       (float)(dev->ptrfeed->ctrl.den) +
+                       dev->last.remainder[1];
+                if (dy) {
+                    tmpi = (int) tmpf;
+                    valuator_mask_set(val, 1, tmpi);
+                    dev->last.remainder[1] = tmpf - (float)tmpi;
+                }
+            }
+        }
+        else {
+            mult = pow((float)dx * (float)dx + (float)dy * (float)dy,
+                       ((float)(dev->ptrfeed->ctrl.num) /
+                        (float)(dev->ptrfeed->ctrl.den) - 1.0) /
+                       2.0) / 2.0;
+            if (dx) {
+                tmpf = mult * (float)dx +
+                       dev->last.remainder[0];
+                tmpi = (int) tmpf;
+                valuator_mask_set(val, 0, tmpi);
+                dev->last.remainder[0] = tmpf - (float)tmpi;
+            }
+            if (dy) {
+                tmpf = mult * (float)dy +
+                       dev->last.remainder[1];
+                tmpi = (int)tmpf;
+                valuator_mask_set(val, 1, tmpi);
+                dev->last.remainder[1] = tmpf - (float)tmpi;
+            }
+        }
+    }
+}
diff --git a/xorg-server/dix/resource.c b/xorg-server/dix/resource.c
index 339ab403b..eb9f0492a 100644
--- a/xorg-server/dix/resource.c
+++ b/xorg-server/dix/resource.c
@@ -1,963 +1,963 @@
-/************************************************************

-

-Copyright 1987, 1998  The Open Group

-

-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.

-

-The above copyright notice and this permission notice shall be included in

-all copies or substantial portions of the Software.

-

-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

-IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

-FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE

-OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN

-AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN

-CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

-

-Except as contained in this notice, the name of The Open Group shall not be

-used in advertising or otherwise to promote the sale, use or other dealings

-in this Software without prior written authorization from The Open Group.

-

-

-Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.

-

-                        All Rights Reserved

-

-Permission to use, copy, modify, and distribute this software and its 

-documentation for any purpose and without fee is hereby granted, 

-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 Digital not be

-used in advertising or publicity pertaining to distribution of the

-software without specific, written prior permission.  

-

-DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING

-ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL

-DIGITAL 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.

-

-********************************************************/

-/* The panoramix components contained the following notice */

-/*****************************************************************

-

-Copyright (c) 1991, 1997 Digital Equipment Corporation, Maynard, Massachusetts.

-

-Permission is hereby granted, free of charge, to any person obtaining a copy

-of this software and associated documentation files (the "Software"), to deal

-in the Software without restriction, including without limitation the rights

-to use, copy, modify, merge, publish, distribute, sublicense, and/or sell

-copies of the Software.

-

-The above copyright notice and this permission notice shall be included in

-all copies or substantial portions of the Software.

-

-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

-IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

-FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL

-DIGITAL EQUIPMENT CORPORATION BE LIABLE FOR ANY CLAIM, DAMAGES, INCLUDING,

-BUT NOT LIMITED TO CONSEQUENTIAL OR INCIDENTAL DAMAGES, OR OTHER LIABILITY,

-WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR

-IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

-

-Except as contained in this notice, the name of Digital Equipment Corporation

-shall not be used in advertising or otherwise to promote the sale, use or other

-dealings in this Software without prior written authorization from Digital

-Equipment Corporation.

-

-******************************************************************/

-/* XSERVER_DTRACE additions:

- * Copyright (c) 2005-2006, Oracle and/or its affiliates. All rights reserved.

- *

- * Permission is hereby granted, free of charge, to any person obtaining a

- * copy of this software and associated documentation files (the "Software"),

- * to deal in the Software without restriction, including without limitation

- * the rights to use, copy, modify, merge, publish, distribute, sublicense,

- * and/or sell copies of the Software, and to permit persons to whom the

- * Software is furnished to do so, subject to the following conditions:

- *

- * The above copyright notice and this permission notice (including the next

- * paragraph) shall be included in all copies or substantial portions of the

- * Software.

- *

- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

- * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

- * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL

- * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

- * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING

- * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER

- * DEALINGS IN THE SOFTWARE.

- */

-

-/*	Routines to manage various kinds of resources:

- *

- *	CreateNewResourceType, CreateNewResourceClass, InitClientResources,

- *	FakeClientID, AddResource, FreeResource, FreeClientResources,

- *	FreeAllResources, LookupIDByType, LookupIDByClass, GetXIDRange

- */

-

-/* 

- *      A resource ID is a 32 bit quantity, the upper 2 bits of which are

- *	off-limits for client-visible resources.  The next 8 bits are

- *      used as client ID, and the low 22 bits come from the client.

- *	A resource ID is "hashed" by extracting and xoring subfields

- *      (varying with the size of the hash table).

- *

- *      It is sometimes necessary for the server to create an ID that looks

- *      like it belongs to a client.  This ID, however,  must not be one

- *      the client actually can create, or we have the potential for conflict.

- *      The 31st bit of the ID is reserved for the server's use for this

- *      purpose.  By setting CLIENT_ID(id) to the client, the SERVER_BIT to

- *      1, and an otherwise arbitrary ID in the low 22 bits, we can create a

- *      resource "owned" by the client.

- */

-

-#ifdef HAVE_DIX_CONFIG_H

-#include <dix-config.h>

-#endif

-

-#include <X11/X.h>

-#include "misc.h"

-#include "os.h"

-#include "resource.h"

-#include "dixstruct.h" 

-#include "opaque.h"

-#include "windowstr.h"

-#include "dixfont.h"

-#include "colormap.h"

-#include "inputstr.h"

-#include "dixevents.h"

-#include "dixgrabs.h"

-#include "cursor.h"

-#ifdef PANORAMIX

-#include "panoramiX.h"

-#include "panoramiXsrv.h"

-#endif

-#include "xace.h"

-#include <assert.h>

-#include "registry.h"

-

-#ifdef XSERVER_DTRACE

-#include <sys/types.h>

-typedef const char *string;

-#include "Xserver-dtrace.h"

-

-#define TypeNameString(t) LookupResourceName(t)

-#endif

-

-static void RebuildTable(

-    int /*client*/

-);

-

-#define SERVER_MINID 32

-

-#define INITBUCKETS 64

-#define INITHASHSIZE 6

-#define MAXHASHSIZE 11

-

-typedef struct _Resource {

-    struct _Resource	*next;

-    XID			id;

-    RESTYPE		type;

-    pointer		value;

-} ResourceRec, *ResourcePtr;

-

-typedef struct _ClientResource {

-    ResourcePtr *resources;

-    int		elements;

-    int		buckets;

-    int		hashsize;	/* log(2)(buckets) */

-    XID		fakeID;

-    XID		endFakeID;

-} ClientResourceRec;

-

-RESTYPE lastResourceType;

-static RESTYPE lastResourceClass;

-RESTYPE TypeMask;

-

-struct ResourceType {

-    DeleteType deleteFunc;

-    int errorValue;

-};

-

-static struct ResourceType *resourceTypes;

-static const struct ResourceType predefTypes[] = {

-    [RT_NONE & (RC_LASTPREDEF - 1)] = {

-	.deleteFunc = (DeleteType)NoopDDA,

-	.errorValue = BadValue,

-    },

-    [RT_WINDOW & (RC_LASTPREDEF - 1)] = {

-	.deleteFunc = DeleteWindow,

-	.errorValue = BadWindow,

-    },

-    [RT_PIXMAP & (RC_LASTPREDEF - 1)] = {

-	.deleteFunc = dixDestroyPixmap,

-	.errorValue = BadPixmap,

-    },

-    [RT_GC & (RC_LASTPREDEF - 1)] = {

-	.deleteFunc = FreeGC,

-	.errorValue = BadGC,

-    },

-    [RT_FONT & (RC_LASTPREDEF - 1)] = {

-	.deleteFunc = CloseFont,

-	.errorValue = BadFont,

-    },

-    [RT_CURSOR & (RC_LASTPREDEF - 1)] = {

-	.deleteFunc = FreeCursor,

-	.errorValue = BadCursor,

-    },

-    [RT_COLORMAP & (RC_LASTPREDEF - 1)] = {

-	.deleteFunc = FreeColormap,

-	.errorValue = BadColor,

-    },

-    [RT_CMAPENTRY & (RC_LASTPREDEF - 1)] = {

-	.deleteFunc = FreeClientPixels,

-	.errorValue = BadColor,

-    },

-    [RT_OTHERCLIENT & (RC_LASTPREDEF - 1)] = {

-	.deleteFunc = OtherClientGone,

-	.errorValue = BadValue,

-    },

-    [RT_PASSIVEGRAB & (RC_LASTPREDEF - 1)] = {

-	.deleteFunc = DeletePassiveGrab,

-	.errorValue = BadValue,

-    },

-};

-

-CallbackListPtr ResourceStateCallback;

-

-static _X_INLINE void

-CallResourceStateCallback(ResourceState state, ResourceRec *res)

-{

-    if (ResourceStateCallback) {

-	ResourceStateInfoRec rsi = { state, res->id, res->type, res->value };

-	CallCallbacks(&ResourceStateCallback, &rsi);

-    }

-}

-

-RESTYPE

-CreateNewResourceType(DeleteType deleteFunc, char *name)

-{

-    RESTYPE next = lastResourceType + 1;

-    struct ResourceType *types;

-

-    if (next & lastResourceClass)

-	return 0;

-    types = realloc(resourceTypes, (next + 1) * sizeof(*resourceTypes));

-    if (!types)

-	return 0;

-

-    lastResourceType = next;

-    resourceTypes = types;

-    resourceTypes[next].deleteFunc = deleteFunc;

-    resourceTypes[next].errorValue = BadValue;

-

-    /* Called even if name is NULL, to remove any previous entry */

-    RegisterResourceName(next, name);

-

-    return next;

-}

-

-void

-SetResourceTypeErrorValue(RESTYPE type, int errorValue)

-{

-    resourceTypes[type & TypeMask].errorValue = errorValue;

-}

-

-RESTYPE

-CreateNewResourceClass(void)

-{

-    RESTYPE next = lastResourceClass >> 1;

-

-    if (next & lastResourceType)

-	return 0;

-    lastResourceClass = next;

-    TypeMask = next - 1;

-    return next;

-}

-

-static ClientResourceRec clientTable[MAXCLIENTS];

-

-/*****************

- * InitClientResources

- *    When a new client is created, call this to allocate space

- *    in resource table

- *****************/

-

-Bool

-InitClientResources(ClientPtr client)

-{

-    int i, j;

- 

-    if (client == serverClient)

-    {

-	lastResourceType = RT_LASTPREDEF;

-	lastResourceClass = RC_LASTPREDEF;

-	TypeMask = RC_LASTPREDEF - 1;

-	free(resourceTypes);

-	resourceTypes = malloc(sizeof(predefTypes));

-	if (!resourceTypes)

-	    return FALSE;

-	memcpy(resourceTypes, predefTypes, sizeof(predefTypes));

-    }

-    clientTable[i = client->index].resources =

-	malloc(INITBUCKETS*sizeof(ResourcePtr));

-    if (!clientTable[i].resources)

-	return FALSE;

-    clientTable[i].buckets = INITBUCKETS;

-    clientTable[i].elements = 0;

-    clientTable[i].hashsize = INITHASHSIZE;

-    /* Many IDs allocated from the server client are visible to clients,

-     * so we don't use the SERVER_BIT for them, but we have to start

-     * past the magic value constants used in the protocol.  For normal

-     * clients, we can start from zero, with SERVER_BIT set.

-     */

-    clientTable[i].fakeID = client->clientAsMask |

-			    (client->index ? SERVER_BIT : SERVER_MINID);

-    clientTable[i].endFakeID = (clientTable[i].fakeID | RESOURCE_ID_MASK) + 1;

-    for (j=0; j<INITBUCKETS; j++) 

-    {

-        clientTable[i].resources[j] = NULL;

-    }

-    return TRUE;

-}

-

-

-static int

-Hash(int client, XID id)

-{

-    id &= RESOURCE_ID_MASK;

-    switch (clientTable[client].hashsize)

-    {

-	case 6:

-	    return ((int)(0x03F & (id ^ (id>>6) ^ (id>>12))));

-	case 7:

-	    return ((int)(0x07F & (id ^ (id>>7) ^ (id>>13))));

-	case 8:

-	    return ((int)(0x0FF & (id ^ (id>>8) ^ (id>>16))));

-	case 9:

-	    return ((int)(0x1FF & (id ^ (id>>9))));

-	case 10:

-	    return ((int)(0x3FF & (id ^ (id>>10))));

-	case 11:

-	    return ((int)(0x7FF & (id ^ (id>>11))));

-    }

-    return -1;

-}

-

-static XID

-AvailableID(

-    int client,

-    XID id,

-    XID maxid,

-    XID goodid)

-{

-    ResourcePtr res;

-

-    if ((goodid >= id) && (goodid <= maxid))

-	return goodid;

-    for (; id <= maxid; id++)

-    {

-	res = clientTable[client].resources[Hash(client, id)];

-	while (res && (res->id != id))

-	    res = res->next;

-	if (!res)

-	    return id;

-    }

-    return 0;

-}

-

-void

-GetXIDRange(int client, Bool server, XID *minp, XID *maxp)

-{

-    XID id, maxid;

-    ResourcePtr *resp;

-    ResourcePtr res;

-    int i;

-    XID goodid;

-

-    id = (Mask)client << CLIENTOFFSET;

-    if (server)

-	id |= client ? SERVER_BIT : SERVER_MINID;

-    maxid = id | RESOURCE_ID_MASK;

-    goodid = 0;

-    for (resp = clientTable[client].resources, i = clientTable[client].buckets;

-	 --i >= 0;)

-    {

-	for (res = *resp++; res; res = res->next)

-	{

-	    if ((res->id < id) || (res->id > maxid))

-		continue;

-	    if (((res->id - id) >= (maxid - res->id)) ?

-		(goodid = AvailableID(client, id, res->id - 1, goodid)) :

-		!(goodid = AvailableID(client, res->id + 1, maxid, goodid)))

-		maxid = res->id - 1;

-	    else

-		id = res->id + 1;

-	}

-    }

-    if (id > maxid)

-	id = maxid = 0;

-    *minp = id;

-    *maxp = maxid;

-}

-

-/**

- *  GetXIDList is called by the XC-MISC extension's MiscGetXIDList function.

- *  This function tries to find count unused XIDs for the given client.  It 

- *  puts the IDs in the array pids and returns the number found, which should

- *  almost always be the number requested.

- *

- *  The circumstances that lead to a call to this function are very rare.

- *  Xlib must run out of IDs while trying to generate a request that wants

- *  multiple ID's, like the Multi-buffering CreateImageBuffers request.

- *

- *  No rocket science in the implementation; just iterate over all

- *  possible IDs for the given client and pick the first count IDs

- *  that aren't in use.  A more efficient algorithm could probably be

- *  invented, but this will be used so rarely that this should suffice.

- */

-

-unsigned int

-GetXIDList(ClientPtr pClient, unsigned count, XID *pids)

-{

-    unsigned int found = 0;

-    XID rc, id = pClient->clientAsMask;

-    XID maxid;

-    pointer val;

-

-    maxid = id | RESOURCE_ID_MASK;

-    while ( (found < count) && (id <= maxid) )

-    {

-	rc = dixLookupResourceByClass(&val, id, RC_ANY, serverClient,

-				      DixGetAttrAccess);

-	if (rc == BadValue)

-	{

-	    pids[found++] = id;

-	}

-	id++;

-    }

-    return found;

-}

-

-/*

- * Return the next usable fake client ID.

- *

- * Normally this is just the next one in line, but if we've used the last

- * in the range, we need to find a new range of safe IDs to avoid

- * over-running another client.

- */

-

-XID

-FakeClientID(int client)

-{

-    XID id, maxid;

-

-    id = clientTable[client].fakeID++;

-    if (id != clientTable[client].endFakeID)

-	return id;

-    GetXIDRange(client, TRUE, &id, &maxid);

-    if (!id) {

-	if (!client)

-	    FatalError("FakeClientID: server internal ids exhausted\n");

-	MarkClientException(clients[client]);

-	id = ((Mask)client << CLIENTOFFSET) | (SERVER_BIT * 3);

-	maxid = id | RESOURCE_ID_MASK;

-    }

-    clientTable[client].fakeID = id + 1;

-    clientTable[client].endFakeID = maxid + 1;

-    return id;

-}

-

-Bool

-AddResource(XID id, RESTYPE type, pointer value)

-{

-    int client;

-    ClientResourceRec *rrec;

-    ResourcePtr res, *head;

-    	

-#ifdef XSERVER_DTRACE

-    XSERVER_RESOURCE_ALLOC(id, type, value, TypeNameString(type));

-#endif

-    client = CLIENT_ID(id);

-    rrec = &clientTable[client];

-    if (!rrec->buckets)

-    {

-	ErrorF("[dix] AddResource(%lx, %lx, %lx), client=%d \n",

-		(unsigned long)id, type, (unsigned long)value, client);

-        FatalError("client not in use\n");

-    }

-    if ((rrec->elements >= 4*rrec->buckets) &&

-	(rrec->hashsize < MAXHASHSIZE))

-	RebuildTable(client);

-    head = &rrec->resources[Hash(client, id)];

-    res = malloc(sizeof(ResourceRec));

-    if (!res)

-    {

-	(*resourceTypes[type & TypeMask].deleteFunc)(value, id);

-	return FALSE;

-    }

-    res->next = *head;

-    res->id = id;

-    res->type = type;

-    res->value = value;

-    *head = res;

-    rrec->elements++;

-    CallResourceStateCallback(ResourceStateAdding, res);

-    return TRUE;

-}

-

-static void

-RebuildTable(int client)

-{

-    int j;

-    ResourcePtr res, next;

-    ResourcePtr **tails, *resources;

-    ResourcePtr **tptr, *rptr;

-

-    /*

-     * For now, preserve insertion order, since some ddx layers depend

-     * on resources being free in the opposite order they are added.

-     */

-

-    j = 2 * clientTable[client].buckets;

-    tails = malloc(j * sizeof(ResourcePtr *));

-    if (!tails)

-	return;

-    resources = malloc(j * sizeof(ResourcePtr));

-    if (!resources)

-    {

-	free(tails);

-	return;

-    }

-    for (rptr = resources, tptr = tails; --j >= 0; rptr++, tptr++)

-    {

-	*rptr = NULL;

-	*tptr = rptr;

-    }

-    clientTable[client].hashsize++;

-    for (j = clientTable[client].buckets,

-	 rptr = clientTable[client].resources;

-	 --j >= 0;

-	 rptr++)

-    {

-	for (res = *rptr; res; res = next)

-	{

-	    next = res->next;

-	    res->next = NULL;

-	    tptr = &tails[Hash(client, res->id)];

-	    **tptr = res;

-	    *tptr = &res->next;

-	}

-    }

-    free(tails);

-    clientTable[client].buckets *= 2;

-    free(clientTable[client].resources);

-    clientTable[client].resources = resources;

-}

-

-static void

-doFreeResource(ResourcePtr res, Bool skip)

-{

-    CallResourceStateCallback(ResourceStateFreeing, res);

-

-    if (!skip)

-	resourceTypes[res->type & TypeMask].deleteFunc(res->value, res->id);

-

-    free(res);

-}

-

-void

-FreeResource(XID id, RESTYPE skipDeleteFuncType)

-{

-    int		cid;

-    ResourcePtr res;

-    ResourcePtr *prev, *head;

-    int *eltptr;

-    int		elements;

-

-    if (((cid = CLIENT_ID(id)) < MAXCLIENTS) && clientTable[cid].buckets)

-    {

-	head = &clientTable[cid].resources[Hash(cid, id)];

-	eltptr = &clientTable[cid].elements;

-

-	prev = head;

-	while ( (res = *prev) )

-	{

-	    if (res->id == id)

-	    {

-		RESTYPE rtype = res->type;

-

-#ifdef XSERVER_DTRACE

-		XSERVER_RESOURCE_FREE(res->id, res->type,

-			      res->value, TypeNameString(res->type));

-#endif		    

-		*prev = res->next;

-		elements = --*eltptr;

-

-		doFreeResource(res, rtype == skipDeleteFuncType);

-

-		if (*eltptr != elements)

-		    prev = head; /* prev may no longer be valid */

-	    }

-	    else

-		prev = &res->next;

-        }

-    }

-}

-

-void

-FreeResourceByType(XID id, RESTYPE type, Bool skipFree)

-{

-    int		cid;

-    ResourcePtr res;

-    ResourcePtr *prev, *head;

-    if (((cid = CLIENT_ID(id)) < MAXCLIENTS) && clientTable[cid].buckets)

-    {

-	head = &clientTable[cid].resources[Hash(cid, id)];

-

-	prev = head;

-	while ( (res = *prev) )

-	{

-	    if (res->id == id && res->type == type)

-	    {

-#ifdef XSERVER_DTRACE

-		XSERVER_RESOURCE_FREE(res->id, res->type,

-			      res->value, TypeNameString(res->type));

-#endif		    		    

-		*prev = res->next;

-		clientTable[cid].elements--;

-

-		doFreeResource(res, skipFree);

-

-		break;

-	    }

-	    else

-		prev = &res->next;

-        }

-    }

-}

-

-/*

- * Change the value associated with a resource id.  Caller

- * is responsible for "doing the right thing" with the old

- * data

- */

-

-Bool

-ChangeResourceValue (XID id, RESTYPE rtype, pointer value)

-{

-    int    cid;

-    ResourcePtr res;

-

-    if (((cid = CLIENT_ID(id)) < MAXCLIENTS) && clientTable[cid].buckets)

-    {

-	res = clientTable[cid].resources[Hash(cid, id)];

-

-	for (; res; res = res->next)

-	    if ((res->id == id) && (res->type == rtype))

-	    {

-		res->value = value;

-		return TRUE;

-	    }

-    }

-    return FALSE;

-}

-

-/* Note: if func adds or deletes resources, then func can get called

- * more than once for some resources.  If func adds new resources,

- * func might or might not get called for them.  func cannot both

- * add and delete an equal number of resources!

- */

-

-void

-FindClientResourcesByType(

-    ClientPtr client,

-    RESTYPE type,

-    FindResType func,

-    pointer cdata

-){

-    ResourcePtr *resources;

-    ResourcePtr this, next;

-    int i, elements;

-    int *eltptr;

-

-    if (!client)

-	client = serverClient;

-

-    resources = clientTable[client->index].resources;

-    eltptr = &clientTable[client->index].elements;

-    for (i = 0; i < clientTable[client->index].buckets; i++) 

-    {

-        for (this = resources[i]; this; this = next)

-	{

-	    next = this->next;

-	    if (!type || this->type == type) {

-		elements = *eltptr;

-		(*func)(this->value, this->id, cdata);

-		if (*eltptr != elements)

-		    next = resources[i]; /* start over */

-	    }

-	}

-    }

-}

-

-void

-FindAllClientResources(

-    ClientPtr client,

-    FindAllRes func,

-    pointer cdata

-){

-    ResourcePtr *resources;

-    ResourcePtr this, next;

-    int i, elements;

-    int *eltptr;

-

-    if (!client)

-        client = serverClient;

-

-    resources = clientTable[client->index].resources;

-    eltptr = &clientTable[client->index].elements;

-    for (i = 0; i < clientTable[client->index].buckets; i++)

-    {

-        for (this = resources[i]; this; this = next)

-        {

-            next = this->next;

-            elements = *eltptr;

-            (*func)(this->value, this->id, this->type, cdata);

-            if (*eltptr != elements)

-                next = resources[i]; /* start over */

-        }

-    }

-}

-

-

-pointer

-LookupClientResourceComplex(

-    ClientPtr client,

-    RESTYPE type,

-    FindComplexResType func,

-    pointer cdata

-){

-    ResourcePtr *resources;

-    ResourcePtr this, next;

-    pointer value;

-    int i;

-

-    if (!client)

-	client = serverClient;

-

-    resources = clientTable[client->index].resources;

-    for (i = 0; i < clientTable[client->index].buckets; i++) {

-        for (this = resources[i]; this; this = next) {

-	    next = this->next;

-	    if (!type || this->type == type) {

-		/* workaround func freeing the type as DRI1 does */

-		value = this->value;

-		if((*func)(value, this->id, cdata))

-		    return value;

-	    }

-	}

-    }

-    return NULL;

-}

-

-

-void

-FreeClientNeverRetainResources(ClientPtr client)

-{

-    ResourcePtr *resources;

-    ResourcePtr this;

-    ResourcePtr *prev;

-    int j, elements;

-    int *eltptr;

-

-    if (!client)

-	return;

-

-    resources = clientTable[client->index].resources;

-    eltptr = &clientTable[client->index].elements;

-    for (j=0; j < clientTable[client->index].buckets; j++) 

-    {

-	prev = &resources[j];

-        while ( (this = *prev) )

-	{

-	    RESTYPE rtype = this->type;

-	    if (rtype & RC_NEVERRETAIN)

-	    {

-#ifdef XSERVER_DTRACE

-		XSERVER_RESOURCE_FREE(this->id, this->type,

-			      this->value, TypeNameString(this->type));

-#endif		    

-		*prev = this->next;

-		clientTable[client->index].elements--;

-		elements = *eltptr;

-

-		doFreeResource(this, FALSE);

-

-		if (*eltptr != elements)

-		    prev = &resources[j]; /* prev may no longer be valid */

-	    }

-	    else

-		prev = &this->next;

-	}

-    }

-}

-

-void

-FreeClientResources(ClientPtr client)

-{

-    ResourcePtr *resources;

-    ResourcePtr this;

-    int j;

-

-    /* This routine shouldn't be called with a null client, but just in

-	case ... */

-

-    if (!client)

-	return;

-

-    HandleSaveSet(client);

-

-    resources = clientTable[client->index].resources;

-    for (j=0; j < clientTable[client->index].buckets; j++) 

-    {

-        /* It may seem silly to update the head of this resource list as

-	we delete the members, since the entire list will be deleted any way, 

-	but there are some resource deletion functions "FreeClientPixels" for 

-	one which do a LookupID on another resource id (a Colormap id in this

-	case), so the resource list must be kept valid up to the point that

-	it is deleted, so every time we delete a resource, we must update the

-	head, just like in FreeResource. I hope that this doesn't slow down

-	mass deletion appreciably. PRH */

-

-	ResourcePtr *head;

-

-	head = &resources[j];

-

-        for (this = *head; this; this = *head)

-	{

-#ifdef XSERVER_DTRACE

-	    XSERVER_RESOURCE_FREE(this->id, this->type,

-			  this->value, TypeNameString(this->type));

-#endif		    

-	    *head = this->next;

-	    clientTable[client->index].elements--;

-

-	    doFreeResource(this, FALSE);

-	}

-    }

-    free(clientTable[client->index].resources);

-    clientTable[client->index].resources = NULL;

-    clientTable[client->index].buckets = 0;

-}

-

-void

-FreeAllResources(void)

-{

-    int	i;

-

-    for (i = currentMaxClients; --i >= 0; ) 

-    {

-        if (clientTable[i].buckets) 

-	    FreeClientResources(clients[i]);

-    }

-}

-

-Bool

-LegalNewID(XID id, ClientPtr client)

-{

-    pointer val;

-    int rc;

-

-#ifdef PANORAMIX

-    XID 	minid, maxid;

-

-    if (!noPanoramiXExtension) {

-        minid = client->clientAsMask | (client->index ?

-                                        SERVER_BIT : SERVER_MINID);

-        maxid = (clientTable[client->index].fakeID | RESOURCE_ID_MASK) + 1;

-        if ((id >= minid) && (id <= maxid))

-            return TRUE;

-    }

-#endif /* PANORAMIX */

-    if (client->clientAsMask == (id & ~RESOURCE_ID_MASK))

-    {

-        rc = dixLookupResourceByClass(&val, id, RC_ANY, serverClient,

-                                      DixGetAttrAccess);

-        return rc == BadValue;

-    }

-    return FALSE;

-}

-

-int

-dixLookupResourceByType(pointer *result, XID id, RESTYPE rtype,

-			ClientPtr client, Mask mode)

-{

-    int cid = CLIENT_ID(id);

-    ResourcePtr res = NULL;

-

-    *result = NULL;

-    if ((rtype & TypeMask) > lastResourceType)

-	return BadImplementation;

-

-    if ((cid < MAXCLIENTS) && clientTable[cid].buckets) {

-	res = clientTable[cid].resources[Hash(cid, id)];

-

-	for (; res; res = res->next)

-	    if (res->id == id && res->type == rtype)

-		break;

-    }

-    if (!res)

-	return resourceTypes[rtype & TypeMask].errorValue;

-

-    if (client) {

-	client->errorValue = id;

-	cid = XaceHook(XACE_RESOURCE_ACCESS, client, id, res->type,

-		       res->value, RT_NONE, NULL, mode);

-	if (cid == BadValue)

-	    return resourceTypes[rtype & TypeMask].errorValue;

-	if (cid != Success)

-	    return cid;

-    }

-

-    *result = res->value;

-    return Success;

-}

-

-int

-dixLookupResourceByClass(pointer *result, XID id, RESTYPE rclass,

-			 ClientPtr client, Mask mode)

-{

-    int cid = CLIENT_ID(id);

-    ResourcePtr res = NULL;

-

-    *result = NULL;

-

-    if ((cid < MAXCLIENTS) && clientTable[cid].buckets) {

-	res = clientTable[cid].resources[Hash(cid, id)];

-

-	for (; res; res = res->next)

-	    if (res->id == id && (res->type & rclass))

-		break;

-    }

-    if (!res)

-	return BadValue;

-

-    if (client) {

-	client->errorValue = id;

-	cid = XaceHook(XACE_RESOURCE_ACCESS, client, id, res->type,

-		       res->value, RT_NONE, NULL, mode);

-	if (cid != Success)

-	    return cid;

-    }

-

-    *result = res->value;

-    return Success;

-}

+/************************************************************
+
+Copyright 1987, 1998  The Open Group
+
+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.
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
+OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
+AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+
+Except as contained in this notice, the name of The Open Group shall not be
+used in advertising or otherwise to promote the sale, use or other dealings
+in this Software without prior written authorization from The Open Group.
+
+
+Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
+
+                        All Rights Reserved
+
+Permission to use, copy, modify, and distribute this software and its 
+documentation for any purpose and without fee is hereby granted, 
+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 Digital not be
+used in advertising or publicity pertaining to distribution of the
+software without specific, written prior permission.  
+
+DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
+ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
+DIGITAL 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.
+
+********************************************************/
+/* The panoramix components contained the following notice */
+/*****************************************************************
+
+Copyright (c) 1991, 1997 Digital Equipment Corporation, Maynard, Massachusetts.
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software.
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+DIGITAL EQUIPMENT CORPORATION BE LIABLE FOR ANY CLAIM, DAMAGES, INCLUDING,
+BUT NOT LIMITED TO CONSEQUENTIAL OR INCIDENTAL DAMAGES, OR OTHER LIABILITY,
+WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+
+Except as contained in this notice, the name of Digital Equipment Corporation
+shall not be used in advertising or otherwise to promote the sale, use or other
+dealings in this Software without prior written authorization from Digital
+Equipment Corporation.
+
+******************************************************************/
+/* XSERVER_DTRACE additions:
+ * Copyright (c) 2005-2006, Oracle and/or its affiliates. All rights reserved.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ */
+
+/*	Routines to manage various kinds of resources:
+ *
+ *	CreateNewResourceType, CreateNewResourceClass, InitClientResources,
+ *	FakeClientID, AddResource, FreeResource, FreeClientResources,
+ *	FreeAllResources, LookupIDByType, LookupIDByClass, GetXIDRange
+ */
+
+/* 
+ *      A resource ID is a 32 bit quantity, the upper 2 bits of which are
+ *	off-limits for client-visible resources.  The next 8 bits are
+ *      used as client ID, and the low 22 bits come from the client.
+ *	A resource ID is "hashed" by extracting and xoring subfields
+ *      (varying with the size of the hash table).
+ *
+ *      It is sometimes necessary for the server to create an ID that looks
+ *      like it belongs to a client.  This ID, however,  must not be one
+ *      the client actually can create, or we have the potential for conflict.
+ *      The 31st bit of the ID is reserved for the server's use for this
+ *      purpose.  By setting CLIENT_ID(id) to the client, the SERVER_BIT to
+ *      1, and an otherwise arbitrary ID in the low 22 bits, we can create a
+ *      resource "owned" by the client.
+ */
+
+#ifdef HAVE_DIX_CONFIG_H
+#include <dix-config.h>
+#endif
+
+#include <X11/X.h>
+#include "misc.h"
+#include "os.h"
+#include "resource.h"
+#include "dixstruct.h" 
+#include "opaque.h"
+#include "windowstr.h"
+#include "dixfont.h"
+#include "colormap.h"
+#include "inputstr.h"
+#include "dixevents.h"
+#include "dixgrabs.h"
+#include "cursor.h"
+#ifdef PANORAMIX
+#include "panoramiX.h"
+#include "panoramiXsrv.h"
+#endif
+#include "xace.h"
+#include <assert.h>
+#include "registry.h"
+
+#ifdef XSERVER_DTRACE
+#include <sys/types.h>
+typedef const char *string;
+#include "Xserver-dtrace.h"
+
+#define TypeNameString(t) LookupResourceName(t)
+#endif
+
+static void RebuildTable(
+    int /*client*/
+);
+
+#define SERVER_MINID 32
+
+#define INITBUCKETS 64
+#define INITHASHSIZE 6
+#define MAXHASHSIZE 11
+
+typedef struct _Resource {
+    struct _Resource	*next;
+    XID			id;
+    RESTYPE		type;
+    pointer		value;
+} ResourceRec, *ResourcePtr;
+
+typedef struct _ClientResource {
+    ResourcePtr *resources;
+    int		elements;
+    int		buckets;
+    int		hashsize;	/* log(2)(buckets) */
+    XID		fakeID;
+    XID		endFakeID;
+} ClientResourceRec;
+
+RESTYPE lastResourceType;
+static RESTYPE lastResourceClass;
+RESTYPE TypeMask;
+
+struct ResourceType {
+    DeleteType deleteFunc;
+    int errorValue;
+};
+
+static struct ResourceType *resourceTypes;
+static const struct ResourceType predefTypes[] = {
+    [RT_NONE & (RC_LASTPREDEF - 1)] = {
+	.deleteFunc = (DeleteType)NoopDDA,
+	.errorValue = BadValue,
+    },
+    [RT_WINDOW & (RC_LASTPREDEF - 1)] = {
+	.deleteFunc = DeleteWindow,
+	.errorValue = BadWindow,
+    },
+    [RT_PIXMAP & (RC_LASTPREDEF - 1)] = {
+	.deleteFunc = dixDestroyPixmap,
+	.errorValue = BadPixmap,
+    },
+    [RT_GC & (RC_LASTPREDEF - 1)] = {
+	.deleteFunc = FreeGC,
+	.errorValue = BadGC,
+    },
+    [RT_FONT & (RC_LASTPREDEF - 1)] = {
+	.deleteFunc = CloseFont,
+	.errorValue = BadFont,
+    },
+    [RT_CURSOR & (RC_LASTPREDEF - 1)] = {
+	.deleteFunc = FreeCursor,
+	.errorValue = BadCursor,
+    },
+    [RT_COLORMAP & (RC_LASTPREDEF - 1)] = {
+	.deleteFunc = FreeColormap,
+	.errorValue = BadColor,
+    },
+    [RT_CMAPENTRY & (RC_LASTPREDEF - 1)] = {
+	.deleteFunc = FreeClientPixels,
+	.errorValue = BadColor,
+    },
+    [RT_OTHERCLIENT & (RC_LASTPREDEF - 1)] = {
+	.deleteFunc = OtherClientGone,
+	.errorValue = BadValue,
+    },
+    [RT_PASSIVEGRAB & (RC_LASTPREDEF - 1)] = {
+	.deleteFunc = DeletePassiveGrab,
+	.errorValue = BadValue,
+    },
+};
+
+CallbackListPtr ResourceStateCallback;
+
+static _X_INLINE void
+CallResourceStateCallback(ResourceState state, ResourceRec *res)
+{
+    if (ResourceStateCallback) {
+	ResourceStateInfoRec rsi = { state, res->id, res->type, res->value };
+	CallCallbacks(&ResourceStateCallback, &rsi);
+    }
+}
+
+RESTYPE
+CreateNewResourceType(DeleteType deleteFunc, char *name)
+{
+    RESTYPE next = lastResourceType + 1;
+    struct ResourceType *types;
+
+    if (next & lastResourceClass)
+	return 0;
+    types = realloc(resourceTypes, (next + 1) * sizeof(*resourceTypes));
+    if (!types)
+	return 0;
+
+    lastResourceType = next;
+    resourceTypes = types;
+    resourceTypes[next].deleteFunc = deleteFunc;
+    resourceTypes[next].errorValue = BadValue;
+
+    /* Called even if name is NULL, to remove any previous entry */
+    RegisterResourceName(next, name);
+
+    return next;
+}
+
+void
+SetResourceTypeErrorValue(RESTYPE type, int errorValue)
+{
+    resourceTypes[type & TypeMask].errorValue = errorValue;
+}
+
+RESTYPE
+CreateNewResourceClass(void)
+{
+    RESTYPE next = lastResourceClass >> 1;
+
+    if (next & lastResourceType)
+	return 0;
+    lastResourceClass = next;
+    TypeMask = next - 1;
+    return next;
+}
+
+static ClientResourceRec clientTable[MAXCLIENTS];
+
+/*****************
+ * InitClientResources
+ *    When a new client is created, call this to allocate space
+ *    in resource table
+ *****************/
+
+Bool
+InitClientResources(ClientPtr client)
+{
+    int i, j;
+ 
+    if (client == serverClient)
+    {
+	lastResourceType = RT_LASTPREDEF;
+	lastResourceClass = RC_LASTPREDEF;
+	TypeMask = RC_LASTPREDEF - 1;
+	free(resourceTypes);
+	resourceTypes = malloc(sizeof(predefTypes));
+	if (!resourceTypes)
+	    return FALSE;
+	memcpy(resourceTypes, predefTypes, sizeof(predefTypes));
+    }
+    clientTable[i = client->index].resources =
+	malloc(INITBUCKETS*sizeof(ResourcePtr));
+    if (!clientTable[i].resources)
+	return FALSE;
+    clientTable[i].buckets = INITBUCKETS;
+    clientTable[i].elements = 0;
+    clientTable[i].hashsize = INITHASHSIZE;
+    /* Many IDs allocated from the server client are visible to clients,
+     * so we don't use the SERVER_BIT for them, but we have to start
+     * past the magic value constants used in the protocol.  For normal
+     * clients, we can start from zero, with SERVER_BIT set.
+     */
+    clientTable[i].fakeID = client->clientAsMask |
+			    (client->index ? SERVER_BIT : SERVER_MINID);
+    clientTable[i].endFakeID = (clientTable[i].fakeID | RESOURCE_ID_MASK) + 1;
+    for (j=0; j<INITBUCKETS; j++) 
+    {
+        clientTable[i].resources[j] = NULL;
+    }
+    return TRUE;
+}
+
+
+static int
+Hash(int client, XID id)
+{
+    id &= RESOURCE_ID_MASK;
+    switch (clientTable[client].hashsize)
+    {
+	case 6:
+	    return ((int)(0x03F & (id ^ (id>>6) ^ (id>>12))));
+	case 7:
+	    return ((int)(0x07F & (id ^ (id>>7) ^ (id>>13))));
+	case 8:
+	    return ((int)(0x0FF & (id ^ (id>>8) ^ (id>>16))));
+	case 9:
+	    return ((int)(0x1FF & (id ^ (id>>9))));
+	case 10:
+	    return ((int)(0x3FF & (id ^ (id>>10))));
+	case 11:
+	    return ((int)(0x7FF & (id ^ (id>>11))));
+    }
+    return -1;
+}
+
+static XID
+AvailableID(
+    int client,
+    XID id,
+    XID maxid,
+    XID goodid)
+{
+    ResourcePtr res;
+
+    if ((goodid >= id) && (goodid <= maxid))
+	return goodid;
+    for (; id <= maxid; id++)
+    {
+	res = clientTable[client].resources[Hash(client, id)];
+	while (res && (res->id != id))
+	    res = res->next;
+	if (!res)
+	    return id;
+    }
+    return 0;
+}
+
+void
+GetXIDRange(int client, Bool server, XID *minp, XID *maxp)
+{
+    XID id, maxid;
+    ResourcePtr *resp;
+    ResourcePtr res;
+    int i;
+    XID goodid;
+
+    id = (Mask)client << CLIENTOFFSET;
+    if (server)
+	id |= client ? SERVER_BIT : SERVER_MINID;
+    maxid = id | RESOURCE_ID_MASK;
+    goodid = 0;
+    for (resp = clientTable[client].resources, i = clientTable[client].buckets;
+	 --i >= 0;)
+    {
+	for (res = *resp++; res; res = res->next)
+	{
+	    if ((res->id < id) || (res->id > maxid))
+		continue;
+	    if (((res->id - id) >= (maxid - res->id)) ?
+		(goodid = AvailableID(client, id, res->id - 1, goodid)) :
+		!(goodid = AvailableID(client, res->id + 1, maxid, goodid)))
+		maxid = res->id - 1;
+	    else
+		id = res->id + 1;
+	}
+    }
+    if (id > maxid)
+	id = maxid = 0;
+    *minp = id;
+    *maxp = maxid;
+}
+
+/**
+ *  GetXIDList is called by the XC-MISC extension's MiscGetXIDList function.
+ *  This function tries to find count unused XIDs for the given client.  It 
+ *  puts the IDs in the array pids and returns the number found, which should
+ *  almost always be the number requested.
+ *
+ *  The circumstances that lead to a call to this function are very rare.
+ *  Xlib must run out of IDs while trying to generate a request that wants
+ *  multiple ID's, like the Multi-buffering CreateImageBuffers request.
+ *
+ *  No rocket science in the implementation; just iterate over all
+ *  possible IDs for the given client and pick the first count IDs
+ *  that aren't in use.  A more efficient algorithm could probably be
+ *  invented, but this will be used so rarely that this should suffice.
+ */
+
+unsigned int
+GetXIDList(ClientPtr pClient, unsigned count, XID *pids)
+{
+    unsigned int found = 0;
+    XID rc, id = pClient->clientAsMask;
+    XID maxid;
+    pointer val;
+
+    maxid = id | RESOURCE_ID_MASK;
+    while ( (found < count) && (id <= maxid) )
+    {
+	rc = dixLookupResourceByClass(&val, id, RC_ANY, serverClient,
+				      DixGetAttrAccess);
+	if (rc == BadValue)
+	{
+	    pids[found++] = id;
+	}
+	id++;
+    }
+    return found;
+}
+
+/*
+ * Return the next usable fake client ID.
+ *
+ * Normally this is just the next one in line, but if we've used the last
+ * in the range, we need to find a new range of safe IDs to avoid
+ * over-running another client.
+ */
+
+XID
+FakeClientID(int client)
+{
+    XID id, maxid;
+
+    id = clientTable[client].fakeID++;
+    if (id != clientTable[client].endFakeID)
+	return id;
+    GetXIDRange(client, TRUE, &id, &maxid);
+    if (!id) {
+	if (!client)
+	    FatalError("FakeClientID: server internal ids exhausted\n");
+	MarkClientException(clients[client]);
+	id = ((Mask)client << CLIENTOFFSET) | (SERVER_BIT * 3);
+	maxid = id | RESOURCE_ID_MASK;
+    }
+    clientTable[client].fakeID = id + 1;
+    clientTable[client].endFakeID = maxid + 1;
+    return id;
+}
+
+Bool
+AddResource(XID id, RESTYPE type, pointer value)
+{
+    int client;
+    ClientResourceRec *rrec;
+    ResourcePtr res, *head;
+    	
+#ifdef XSERVER_DTRACE
+    XSERVER_RESOURCE_ALLOC(id, type, value, TypeNameString(type));
+#endif
+    client = CLIENT_ID(id);
+    rrec = &clientTable[client];
+    if (!rrec->buckets)
+    {
+	ErrorF("[dix] AddResource(%lx, %x, %lx), client=%d \n",
+		(unsigned long)id, type, (unsigned long)value, client);
+        FatalError("client not in use\n");
+    }
+    if ((rrec->elements >= 4*rrec->buckets) &&
+	(rrec->hashsize < MAXHASHSIZE))
+	RebuildTable(client);
+    head = &rrec->resources[Hash(client, id)];
+    res = malloc(sizeof(ResourceRec));
+    if (!res)
+    {
+	(*resourceTypes[type & TypeMask].deleteFunc)(value, id);
+	return FALSE;
+    }
+    res->next = *head;
+    res->id = id;
+    res->type = type;
+    res->value = value;
+    *head = res;
+    rrec->elements++;
+    CallResourceStateCallback(ResourceStateAdding, res);
+    return TRUE;
+}
+
+static void
+RebuildTable(int client)
+{
+    int j;
+    ResourcePtr res, next;
+    ResourcePtr **tails, *resources;
+    ResourcePtr **tptr, *rptr;
+
+    /*
+     * For now, preserve insertion order, since some ddx layers depend
+     * on resources being free in the opposite order they are added.
+     */
+
+    j = 2 * clientTable[client].buckets;
+    tails = malloc(j * sizeof(ResourcePtr *));
+    if (!tails)
+	return;
+    resources = malloc(j * sizeof(ResourcePtr));
+    if (!resources)
+    {
+	free(tails);
+	return;
+    }
+    for (rptr = resources, tptr = tails; --j >= 0; rptr++, tptr++)
+    {
+	*rptr = NULL;
+	*tptr = rptr;
+    }
+    clientTable[client].hashsize++;
+    for (j = clientTable[client].buckets,
+	 rptr = clientTable[client].resources;
+	 --j >= 0;
+	 rptr++)
+    {
+	for (res = *rptr; res; res = next)
+	{
+	    next = res->next;
+	    res->next = NULL;
+	    tptr = &tails[Hash(client, res->id)];
+	    **tptr = res;
+	    *tptr = &res->next;
+	}
+    }
+    free(tails);
+    clientTable[client].buckets *= 2;
+    free(clientTable[client].resources);
+    clientTable[client].resources = resources;
+}
+
+static void
+doFreeResource(ResourcePtr res, Bool skip)
+{
+    CallResourceStateCallback(ResourceStateFreeing, res);
+
+    if (!skip)
+	resourceTypes[res->type & TypeMask].deleteFunc(res->value, res->id);
+
+    free(res);
+}
+
+void
+FreeResource(XID id, RESTYPE skipDeleteFuncType)
+{
+    int		cid;
+    ResourcePtr res;
+    ResourcePtr *prev, *head;
+    int *eltptr;
+    int		elements;
+
+    if (((cid = CLIENT_ID(id)) < MAXCLIENTS) && clientTable[cid].buckets)
+    {
+	head = &clientTable[cid].resources[Hash(cid, id)];
+	eltptr = &clientTable[cid].elements;
+
+	prev = head;
+	while ( (res = *prev) )
+	{
+	    if (res->id == id)
+	    {
+		RESTYPE rtype = res->type;
+
+#ifdef XSERVER_DTRACE
+		XSERVER_RESOURCE_FREE(res->id, res->type,
+			      res->value, TypeNameString(res->type));
+#endif		    
+		*prev = res->next;
+		elements = --*eltptr;
+
+		doFreeResource(res, rtype == skipDeleteFuncType);
+
+		if (*eltptr != elements)
+		    prev = head; /* prev may no longer be valid */
+	    }
+	    else
+		prev = &res->next;
+        }
+    }
+}
+
+void
+FreeResourceByType(XID id, RESTYPE type, Bool skipFree)
+{
+    int		cid;
+    ResourcePtr res;
+    ResourcePtr *prev, *head;
+    if (((cid = CLIENT_ID(id)) < MAXCLIENTS) && clientTable[cid].buckets)
+    {
+	head = &clientTable[cid].resources[Hash(cid, id)];
+
+	prev = head;
+	while ( (res = *prev) )
+	{
+	    if (res->id == id && res->type == type)
+	    {
+#ifdef XSERVER_DTRACE
+		XSERVER_RESOURCE_FREE(res->id, res->type,
+			      res->value, TypeNameString(res->type));
+#endif		    		    
+		*prev = res->next;
+		clientTable[cid].elements--;
+
+		doFreeResource(res, skipFree);
+
+		break;
+	    }
+	    else
+		prev = &res->next;
+        }
+    }
+}
+
+/*
+ * Change the value associated with a resource id.  Caller
+ * is responsible for "doing the right thing" with the old
+ * data
+ */
+
+Bool
+ChangeResourceValue (XID id, RESTYPE rtype, pointer value)
+{
+    int    cid;
+    ResourcePtr res;
+
+    if (((cid = CLIENT_ID(id)) < MAXCLIENTS) && clientTable[cid].buckets)
+    {
+	res = clientTable[cid].resources[Hash(cid, id)];
+
+	for (; res; res = res->next)
+	    if ((res->id == id) && (res->type == rtype))
+	    {
+		res->value = value;
+		return TRUE;
+	    }
+    }
+    return FALSE;
+}
+
+/* Note: if func adds or deletes resources, then func can get called
+ * more than once for some resources.  If func adds new resources,
+ * func might or might not get called for them.  func cannot both
+ * add and delete an equal number of resources!
+ */
+
+void
+FindClientResourcesByType(
+    ClientPtr client,
+    RESTYPE type,
+    FindResType func,
+    pointer cdata
+){
+    ResourcePtr *resources;
+    ResourcePtr this, next;
+    int i, elements;
+    int *eltptr;
+
+    if (!client)
+	client = serverClient;
+
+    resources = clientTable[client->index].resources;
+    eltptr = &clientTable[client->index].elements;
+    for (i = 0; i < clientTable[client->index].buckets; i++) 
+    {
+        for (this = resources[i]; this; this = next)
+	{
+	    next = this->next;
+	    if (!type || this->type == type) {
+		elements = *eltptr;
+		(*func)(this->value, this->id, cdata);
+		if (*eltptr != elements)
+		    next = resources[i]; /* start over */
+	    }
+	}
+    }
+}
+
+void
+FindAllClientResources(
+    ClientPtr client,
+    FindAllRes func,
+    pointer cdata
+){
+    ResourcePtr *resources;
+    ResourcePtr this, next;
+    int i, elements;
+    int *eltptr;
+
+    if (!client)
+        client = serverClient;
+
+    resources = clientTable[client->index].resources;
+    eltptr = &clientTable[client->index].elements;
+    for (i = 0; i < clientTable[client->index].buckets; i++)
+    {
+        for (this = resources[i]; this; this = next)
+        {
+            next = this->next;
+            elements = *eltptr;
+            (*func)(this->value, this->id, this->type, cdata);
+            if (*eltptr != elements)
+                next = resources[i]; /* start over */
+        }
+    }
+}
+
+
+pointer
+LookupClientResourceComplex(
+    ClientPtr client,
+    RESTYPE type,
+    FindComplexResType func,
+    pointer cdata
+){
+    ResourcePtr *resources;
+    ResourcePtr this, next;
+    pointer value;
+    int i;
+
+    if (!client)
+	client = serverClient;
+
+    resources = clientTable[client->index].resources;
+    for (i = 0; i < clientTable[client->index].buckets; i++) {
+        for (this = resources[i]; this; this = next) {
+	    next = this->next;
+	    if (!type || this->type == type) {
+		/* workaround func freeing the type as DRI1 does */
+		value = this->value;
+		if((*func)(value, this->id, cdata))
+		    return value;
+	    }
+	}
+    }
+    return NULL;
+}
+
+
+void
+FreeClientNeverRetainResources(ClientPtr client)
+{
+    ResourcePtr *resources;
+    ResourcePtr this;
+    ResourcePtr *prev;
+    int j, elements;
+    int *eltptr;
+
+    if (!client)
+	return;
+
+    resources = clientTable[client->index].resources;
+    eltptr = &clientTable[client->index].elements;
+    for (j=0; j < clientTable[client->index].buckets; j++) 
+    {
+	prev = &resources[j];
+        while ( (this = *prev) )
+	{
+	    RESTYPE rtype = this->type;
+	    if (rtype & RC_NEVERRETAIN)
+	    {
+#ifdef XSERVER_DTRACE
+		XSERVER_RESOURCE_FREE(this->id, this->type,
+			      this->value, TypeNameString(this->type));
+#endif		    
+		*prev = this->next;
+		clientTable[client->index].elements--;
+		elements = *eltptr;
+
+		doFreeResource(this, FALSE);
+
+		if (*eltptr != elements)
+		    prev = &resources[j]; /* prev may no longer be valid */
+	    }
+	    else
+		prev = &this->next;
+	}
+    }
+}
+
+void
+FreeClientResources(ClientPtr client)
+{
+    ResourcePtr *resources;
+    ResourcePtr this;
+    int j;
+
+    /* This routine shouldn't be called with a null client, but just in
+	case ... */
+
+    if (!client)
+	return;
+
+    HandleSaveSet(client);
+
+    resources = clientTable[client->index].resources;
+    for (j=0; j < clientTable[client->index].buckets; j++) 
+    {
+        /* It may seem silly to update the head of this resource list as
+	we delete the members, since the entire list will be deleted any way, 
+	but there are some resource deletion functions "FreeClientPixels" for 
+	one which do a LookupID on another resource id (a Colormap id in this
+	case), so the resource list must be kept valid up to the point that
+	it is deleted, so every time we delete a resource, we must update the
+	head, just like in FreeResource. I hope that this doesn't slow down
+	mass deletion appreciably. PRH */
+
+	ResourcePtr *head;
+
+	head = &resources[j];
+
+        for (this = *head; this; this = *head)
+	{
+#ifdef XSERVER_DTRACE
+	    XSERVER_RESOURCE_FREE(this->id, this->type,
+			  this->value, TypeNameString(this->type));
+#endif		    
+	    *head = this->next;
+	    clientTable[client->index].elements--;
+
+	    doFreeResource(this, FALSE);
+	}
+    }
+    free(clientTable[client->index].resources);
+    clientTable[client->index].resources = NULL;
+    clientTable[client->index].buckets = 0;
+}
+
+void
+FreeAllResources(void)
+{
+    int	i;
+
+    for (i = currentMaxClients; --i >= 0; ) 
+    {
+        if (clientTable[i].buckets) 
+	    FreeClientResources(clients[i]);
+    }
+}
+
+Bool
+LegalNewID(XID id, ClientPtr client)
+{
+    pointer val;
+    int rc;
+
+#ifdef PANORAMIX
+    XID 	minid, maxid;
+
+    if (!noPanoramiXExtension) {
+        minid = client->clientAsMask | (client->index ?
+                                        SERVER_BIT : SERVER_MINID);
+        maxid = (clientTable[client->index].fakeID | RESOURCE_ID_MASK) + 1;
+        if ((id >= minid) && (id <= maxid))
+            return TRUE;
+    }
+#endif /* PANORAMIX */
+    if (client->clientAsMask == (id & ~RESOURCE_ID_MASK))
+    {
+        rc = dixLookupResourceByClass(&val, id, RC_ANY, serverClient,
+                                      DixGetAttrAccess);
+        return rc == BadValue;
+    }
+    return FALSE;
+}
+
+int
+dixLookupResourceByType(pointer *result, XID id, RESTYPE rtype,
+			ClientPtr client, Mask mode)
+{
+    int cid = CLIENT_ID(id);
+    ResourcePtr res = NULL;
+
+    *result = NULL;
+    if ((rtype & TypeMask) > lastResourceType)
+	return BadImplementation;
+
+    if ((cid < MAXCLIENTS) && clientTable[cid].buckets) {
+	res = clientTable[cid].resources[Hash(cid, id)];
+
+	for (; res; res = res->next)
+	    if (res->id == id && res->type == rtype)
+		break;
+    }
+    if (!res)
+	return resourceTypes[rtype & TypeMask].errorValue;
+
+    if (client) {
+	client->errorValue = id;
+	cid = XaceHook(XACE_RESOURCE_ACCESS, client, id, res->type,
+		       res->value, RT_NONE, NULL, mode);
+	if (cid == BadValue)
+	    return resourceTypes[rtype & TypeMask].errorValue;
+	if (cid != Success)
+	    return cid;
+    }
+
+    *result = res->value;
+    return Success;
+}
+
+int
+dixLookupResourceByClass(pointer *result, XID id, RESTYPE rclass,
+			 ClientPtr client, Mask mode)
+{
+    int cid = CLIENT_ID(id);
+    ResourcePtr res = NULL;
+
+    *result = NULL;
+
+    if ((cid < MAXCLIENTS) && clientTable[cid].buckets) {
+	res = clientTable[cid].resources[Hash(cid, id)];
+
+	for (; res; res = res->next)
+	    if (res->id == id && (res->type & rclass))
+		break;
+    }
+    if (!res)
+	return BadValue;
+
+    if (client) {
+	client->errorValue = id;
+	cid = XaceHook(XACE_RESOURCE_ACCESS, client, id, res->type,
+		       res->value, RT_NONE, NULL, mode);
+	if (cid != Success)
+	    return cid;
+    }
+
+    *result = res->value;
+    return Success;
+}